C++链表设计

实验报告要求

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】谁指向谁？

总结：做题用下面总结的方法，绝对好用

• 读的时候：从左往右读，一般左边是某某的 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 的理解

写代码的时候，还经常遇到下面的情况

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

代码

实验报告代码

#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
}

尾插法的理解

• https://blog.csdn.net/sinat_41721615/article/details/105031104
• https://zhidao.baidu.com/question/944472157933268532.html

整体实现代码

#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;
}

参考

• 链表 p->next=q->next,q->next=p,q=p;的一些解释
• p->next=q 与 q=p->next 区分
• 数据结构：链表