尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


主题:hexo-theme-lyrics
作者:尼采般地抒情

站点信息

文章数目:133
已运行时间:
目录
  1. 实验报告要求
  2. 概念理解
    1. 链表数据结构
    2. 首元节点、头节点、头指针
    3. 关于链表的指向
    4. 关于 p=L 的理解
  3. 代码
    1. 实验报告代码
    2. 尾插法的理解
    3. 整体实现代码
  4. 参考

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


主题:hexo-theme-lyrics
作者:尼采般地抒情

站点信息

文章数目:133
已运行时间:

实验报告要求

1、建立一个顺序表,输入 n 个元素并输出;
2、查找线性表中的最大元素并输出;
3、在线性表的第 i 个元素前插入一个正整数 x;
4、删除线性表中的第 j 个元素;
5、将线性表中的元素按升序排列;
*6、将线性表中的元素就地逆序(只允许用一个暂存单元);

概念理解

链表数据结构

链表是一种数据结构,和数组同级。之前 JAVA 里面的 ArrayList 数据结构,其实现原理是数组,而 JAVA 的 LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高,但是插入和删除时优势明显,其实 C/C++抑或是 JAVA 这些数据结构都一样——地址……引用……

单向链表是一种线性表,实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。其数据在内存中存储是不连续的,它存储的数据分散在内存中,每个结点只能也只有它能知道下一个结点的存储位置。由 N 各节点(Node)组成单向链表,每一个 Node 记录本 Node 的数据及下一个 Node。向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。

上图中最左边的节点即为头结点(Head),但是添加节点的顺序是从右向左的,添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一个节点而非下一个节点的对象。因为有着不断的引用,所以头节点就可以操作所有节点了。

下图描述了单向链表存储情况。存储是分散的,每一个节点只要记录下一节点,就把所有数据串了起来,形成了一个单向链表。

节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说,节点拥有两个成员:储存的对象、对下一个节点的引用。下面图是具体的说明:

首元节点、头节点、头指针

一些概念

  • 首元结点:第一个有元素的结点
  • 头结点:一般不放元素,“L”
  • 头指针:指向链表的第一个结点,有头结点则为头结点的指针,反之,指向首元结点的指针

关于链表的指向

【1】何为指向?

个人觉得链表的相关问题及操作就是理解链表的“指向”这么个概念,先明确以下几点

  • 每个节点的next用来存放下一个节点的“地址”
  • 每个节点的自身就是地址,相当于 C 语言中数组的数组名就是本数组的地址

【2】谁指向谁?

总结:做题用下面总结的方法,绝对好用
huaji1558a846ddf2e12b.jpeg

  • 读的时候:从左往右读,一般左边是某某的 next 域,右边是具体的结点
  • 画的时候:在图中表示为等号左边指向等号右边

**
例子:
node.next = prev.next;
prev.next = node
读法:
①“node 的 next 指向 prev 的下一个结点”
(用指针的概念通俗地说,其实就是 prev 的下一个结点的地址由 prev 的指针域里面赋值给了 node 的 next 指针域里面)
②“prev 的 next 指向 node 这个结点”
(还可以这么说:将 node 赋值给 prev 的 next,也就是说 prev 的下一个结点是 node)
**



【3】指向错位?

关注第一个元素节点是不是 head,因为有的链表不声明头节点(head),直接就是第一个结点就是元素结点

关于 p=L 的理解

写代码的时候,还经常遇到下面的情况
image.png
p、L 就是指向结点的指针类型,将 L 的值赋给 p,也就是 p、L 指向同一个结点。具体理解可以用下面一个例子来说明:
下面图片这个函数就是在一个单链表中,功能就是指定 i 位置插入 e 值。下图箭头处如果 TraverseList 返回的是 p 那么得出的链表结果就是从插入的那个元素往后这样一个部分链表,返回的是 L 就是想要的结果,p 的功能有点类似在 L 的中间做了手脚……
image.png

代码

实验报告代码

#include<bits/stdc++.h>
using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}Lnode, *LinkList;

LinkList L;

void InitList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
}

void CreateList_H(LinkList &L) {
    InitList(L);
    int n;
    cout << "请输入要使用前插法插入的元素个数:";
    cin >> n;
    for (int i = 0; i < n; i++){
        LNode *p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}
void TraverseList(LinkList &L){
    LNode *p = new LNode;
    p = L->next;
    cout << "此链表打印的结果为:"<<"\n";
    while (p != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << "\n";
}
void GetElem(LinkList &L) {
    int n;
    cout << "请输入要查询的链表中第i个数:";
    cin >> n;
    LNode *p = new LNode;
    p = L;
    for (int i = 0; i < n;i++){
        p = p->next;
    }
    cout << "查询的结果为:" << p->data<<"\n";
}
void ListInsert(LinkList &L){
    LNode *p = new LNode;
    p = L;
    int n;
    int e;
    cout << "请分别输入要在第n个位置插入的e值:";
    cin >> n>> e ;
    for (int i = 0; i < n;i++) {
        if (n == i+1){
            LNode *temp = new LNode;
            temp->data = e;
            temp->next = p->next;
            p->next = temp;
            break;
        }
        p = p->next;
    }
    TraverseList(L); // 直接返回L就可以了,之前返回p是不可以的!!!唉,大意了~
}
void ListDelete(LinkList &L){
    cout << "请输入要删除的第j个位置的j值:";
    LNode *p = new LNode;
    p = L;
    int j;
    cin >> j;
    for (int i = 0; i < j;i++) {
        if (j == i+1) {
            p->next = p->next->next;
            break;
        }
        p = p->next;
    }
    TraverseList(L);
}
void ReverseList(LinkList &L) {
    LNode *p = L->next;
    L->next = NULL;
    while(p)
    {
        LNode *q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
    cout << "通过逆置之后……";
    TraverseList(L);
}

int main() {
    LNode *test = new LNode;
    CreateList_H(test);//1
    TraverseList(test);//1
    GetElem(test);//2
    ListInsert(test);//3
    ListDelete(test);//4
    ReverseList(test);//5
}

尾插法的理解

整体实现代码

#include<iostream>
#include<string>
#include<iomanip>
#include<stdlib.h>
using namespace std;


typedef struct LNode {
    int data; //结点的数据域
    struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

bool InitList_L(LinkList &L)//构造一个空的单链表L//结构体指针类型变量做为函数的形式参数
{
    L=new LNode;     //生成新结点作为头结点,用头指针L指向头结点//变量名 = new 类型
    if(!L)
      return false;  //生成结点失败
    L->next=NULL;   //头结点的指针域置空
    return true;
}

void CreateList_H(LinkList &L)//前插法创建单链表
{
    //输入n个元素的值,建立到头结点的单链表L
    int n;
    LinkList s; //定义一个所建立的结构体指针变量
    L=new LNode; //生成新结点作为头结点,用头指针L指向头结点
    L->next=NULL; //先建立一个带头结点的空链表
    cout <<"请输入元素个数n:" << endl;
    cin>>n;
    cout <<"请依次输入n个元素:" <<endl;
    cout <<"前插法创建单链表..." <<endl;
    while(n--)
    {
        s=new LNode; //生成新结点s
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=L->next;
        L->next=s; //将新结点s插入到头结点之后
    }
}

void CreateList_R(LinkList &L)//尾插法创建单链表
{
    //输入n个元素的值,建立带表头结点的单链表L
    int n;
    LinkList s, r;
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的空链表
    r=L; //尾指针r指向头结点
    cout <<"请输入元素个数n:" <<endl;
    cin>>n;
    cout <<"请依次输入n个元素:" <<endl;
    cout <<"尾插法创建单链表..." <<endl;
    while(n--)
    {
        s=new LNode;//生成新结点
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=NULL;
        r->next=s;//将新结点s插入尾结点*r之后
        r=s;//r指向新的尾结点s
    }
}

bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
    //在带头结点的单链表L中查找第i个元素
    //用e记录L中第i个数据元素的值
    int j;
    LinkList p;
    p=L->next;//p指向首元结点
    j=1; //j为计数器
    while (j<i && p) //顺链域向后扫描,直到p指向第i个元素或p为空
    {
        p=p->next; //p指向下一个结点    类似结点的自加
        j++; //计数器j相应加1
    }
    if (!p || j>i)
        return false; //i值不合法i>n或i<=0
    e=p->data; //取第i个结点的数据域
    return true;
}

bool LocateElem_L(LinkList L, int e) //按值查找
{
    //在带头结点的单链表L中查找值为e的元素
    LinkList p;
    p=L->next;
    while (p && p->data!=e)//顺链域向后扫描,直到p为空或p所指结点的数据域等于e
        p=p->next; //p指向下一个结点
    if(!p)
        return false; //查找失败p为NULL
    return true;
}

bool ListInsert_L(LinkList &L, int i, int e)//单链表的插入
{
    //在带头结点的单链表L中第i个位置插入值为e的新结点
    int j;
    LinkList p, s;
    p=L;
    j=0;
    while (p&&j<i-1) //查找第i-1个结点,p指向该结点
    {
        p=p->next;
        j++;
    }
    if (!p || j>i-1)//i>n+1或者i<1
        return false;
    s=new LNode;     //生成新结点
    s->data=e;       //将新结点的数据域置为e
    s->next=p->next; //将新结点的指针域指向结点ai
    p->next=s;       //将结点p的指针域指向结点s
    return true;
}

bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
    //在带头结点的单链表L中,删除第i个位置
    LinkList p, q;
    int j;
    p=L;
    j=0;
    while((p->next)&&(j<i-1)) //查找第i-1个结点,p指向该结点
    {
        p=p->next;
        j++;
    }
    if (!(p->next)||(j>i-1))//当i>n或i<1时,删除位置不合理
        return false;
    q=p->next;        //临时保存被删结点的地址以备释放空间
    p->next=q->next; //改变删除结点前驱结点的指针域
    delete q;        //释放被删除结点的空间
    return true;
}

void Listprint_L(LinkList L) //单链表的输出
{
    LinkList p;
    p=L->next;
    while (p)
    {
        cout<<p->data<<"\t";
        p=p->next;
    }
    cout<<endl;
}

int main()
{
    int i,x,e,choose;
    LinkList L;
    cout << "1. 初始化\n";
    cout << "2. 创建单链表(前插法)\n";
    cout << "3. 创建单链表(尾插法)\n";
    cout << "4. 取值\n";
    cout << "5. 查找\n";
    cout << "6. 插入\n";
    cout << "7. 删除\n";
    cout << "8. 输出\n";
    cout << "0. 退出\n";
    choose=-1;
    while (choose!=0)
    {
        cout<<"请输入数字选择:";
        cin>>choose;
        switch (choose)
        {
        case 1: //初始化一个空的单链表
            if (InitList_L(L))
                cout << "初始化一个空的单链表!\n";
            break;
        case 2: //创建单链表(前插法)
            CreateList_H(L);
            cout << "前插法创建单链表输出结果:\n";
            Listprint_L(L);
            break;
        case 3: //创建单链表(尾插法)
            CreateList_R(L);
            cout << "尾插法创建单链表输出结果:\n";
            Listprint_L(L);
            break;
        case 4: //单链表的按序号取值
            cout << "请输入一个位置i用来取值:";
            cin >> i;
            if (GetElem_L(L,i,e))
            {
                cout << "查找成功\n";
                cout << "第" << i << "个元素是:"<<e<< endl;
            }
            else
                cout << "查找失败\n\n";
            break;
        case 5: //单链表的按值查找
            cout<<"请输入所要查找元素x:";
            cin>>x;
            if (LocateElem_L(L,x))
                cout << "查找成功\n";
            else
                cout << "查找失败! " <<endl;
            break;
        case 6: //单链表的插入
            cout << "请输入插入的位置和元素(用空格隔开):";
            cin >> i;
            cin >> x;
            if (ListInsert_L(L, i, x))
                cout << "插入成功.\n\n";
            else
                cout << "插入失败!\n\n";
            break;
        case 7: //单链表的删除
            cout<<"请输入所要删除的元素位置i:";
            cin>>i;
            if (ListDelete_L(L, i))
                cout<<"删除成功!\n";
            else
                cout<<"删除失败!\n";
            break;
        case 8: //单链表的输出
            cout << "当前单链表的数据元素分别为:\n";
            Listprint_L(L);
            cout << endl;
            break;
        }
    }
    system("pause");
    return 0;
}

参考

版权声明:署名-非商业性使用-禁止演绎 4.0 国际 (CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/gu92gu/

评论区

Twikoo 转换 utterances

最新评论

Loading...