第二章 线性表

2023-10-08 19:19:28

目录

第二章 线性表

2.5.3循环链表

定义

顾名思义，循环链表的尾指针指向当前链表的头部，形成一个环，或者其尾指针接到第二个链表的头部，第二个链表尾部与第一个链表相连，并释放其头结点，形成一个环，称作循环链表

A->尾结点=B->next;//A尾结点与B的头结点相连
B->尾结点=A;//B的尾结点与A的头结点相连
delete B;//释放B的头结点

2.5.4双向链表

定义

双向链表有两个指针域，一个前驱指针一个后驱指针，其余和单链表的组成是相似的，前驱指针指向链表前面的结点，后驱指针指向链表后面的结点

双向链表的循环链表

双向链表的循环链表有两个环，如图

第二章 线性表

一个是由后驱指针形成的，一个是由前驱指针形成的

双向链表的插入操作

双向链表的插入操作比较复杂，需要移动两个指针

第二章 线性表

如图

  1. 插入结点的前驱指针指向前一个结点
  2. 前一个结点的后驱指针指向插入的结点
  3. 插入结点的后驱指针指向后一个结点
  4. 后一个结点的前驱指着指向插入的结点

代码实现

Status InsertNode(DuLinkList &A,DulNode *B)
{
    B->next=A->next->next;
    A->next->next->prior=B;
    B->prior=A->next;
    A->next->next=B;
    return true;
}

双向链表的删除结点操作

第二章 线性表

如图

  1. 被删除结点的后一个结点的地址赋值给被删除结点的前一个结点的后驱指针中
  2. 被删除结点的前一个结点的地址赋值给被删除结点的后一个结点的前驱指针中

代码实现

Status DeleteNode(DuLinkList &A)
{
    DuLinkList p;
    p=A->next->next;
    A->next->next=p->next;
    p->next->prior=A->next;
    delete p;
    return true;
}

完整代码实现

#include<iostream>
using namespace std;
typedef int ElemType;
typedef bool Status;
typedef struct DulNode
{
    ElemType data;
    DulNode *prior;
    DulNode *next;
}DulNode,*DuLinkList;
int main()
{
    DuLinkList A;
    DulNode *B;
    B=new DulNode;
    B->next= nullptr;
    B->prior= nullptr;
    B->data=5;
    Status InitList(DuLinkList &A);//创建双向链表
    Status InsertNode(DuLinkList &A,DulNode *B);//插入一个结点
    Status DeleteNode(DuLinkList &A);//删除一个结点
    cout << InitList(A) << endl;
    cout << InsertNode(A,B);
    void DisPlay(DuLinkList A);//输出链表数据
    DisPlay(A);
    cout << DeleteNode(A)<< endl;
    DisPlay(A);
    return 0;
}
Status InitList(DuLinkList &A)
{
    A=new DulNode;
    A->prior= nullptr;
    A->next=new DulNode;
    A->next->next= new DulNode;
    A->next->data=1;
    A->next->next->next= nullptr;
    A->next->next->data=3;
    A->next->next->prior=A->next->next;
    A->next->prior=A->next;
    return true;
}
Status InsertNode(DuLinkList &A,DulNode *B)
{
    B->next=A->next->next;
    A->next->next->prior=B;
    B->prior=A->next;
    A->next->next=B;
    return true;
}
void DisPlay(DuLinkList A)
{
    cout << "输出：" << endl;
    A=A->next;
    while(A)
    {
        cout << A->data << endl;
        A=A->next;
    }
}
Status DeleteNode(DuLinkList &A)
{
    DuLinkList p;
    p=A->next->next;
    A->next->next=p->next;
    p->next->prior=A->next;
    delete p;
    return true;
}

2.6顺序表和链表的比较

  1. 顺序表的内存需预先分配，易造成空间浪费和溢出现象，而链表可随意扩充大小
  2. 顺序表的取值性能强，时间复杂度O（1），但是链表想要取值必须从第一个结点开始遍历，时间复杂度为n

所以，当需要频繁的进行插入删除操作时，选择链表更好，反之选择顺序表。

代码实现.cpp

2.7线性表的应用

2.7.1线性表的合并

思路

两链表分别遍历，相当于集合的并集，合并两链表，相同元素不合并

代码实现

Status InsertElem(DuLinkList &A,DuLinkList &B)
{
    DuLinkList AA,BB;
    AA=A;
    BB=B;
    int ab=1;
    while(BB)
    {
        ab=1;
        AA=A;
        while(AA->next)
//这里不是AA的原因是：当是AA循环结束后AA被空置，没有地址，就算是在这个重新创建一个变量，
//但是原来A->next已经指向NULL而不是指向这个新变量的地址，但如果在其上一步，就可以直接对A->next重新赋值
        {
            if(BB->data==AA->data)
            {
                ab=0;
            }
            if(BB->data==AA->next->data)//最后一个结点未被遍历，这里增加一个条件，遍历最后一个结点的数据
            {
                ab=0;
            }
            AA=AA->next;
        }
        if(ab==1)//如果没有这个元素在A中

        {
            AA->next=new DulNode;//此时AA就是A最后一个结点的地址
            AA->next->next= nullptr;
            AA->next->data=BB->data;
        }
        BB=BB->next;
    }
    return OK;
}

注意点写在上面了

2.7.2有序表的合并（顺序表）

比链表要简单一些，不写了，思路都差不多。不用考虑结点，直接遍历两个数组，参考我写的随想录中的双指针法，不再赘述。。。

2.7.3有序表的合并（链表）

思路

第二章 线性表

两个有序表进行合并，合并之后仍是一个有序表，如上图，可以采用类似双指针的办法，将A，B两个链表一一比较大小，小的放新的链表中，即可得出答案

代码实现

#include<iostream>
#define OK "OK"
using namespace std;
typedef int ElemType;
typedef string Status;
typedef struct DulNode
{
    ElemType data;
    DulNode *next;
}DulNode,*DuLinkList;
int main()
{
    DuLinkList A;
    DuLinkList B;
    DuLinkList C;
    Status CreatList(DuLinkList &L);//初始化链表
    Status InsertElem(DuLinkList &A,DuLinkList &B);
    Status InsertElem2(DuLinkList &A,DuLinkList &B,DuLinkList &C);
    Status DisplayList(DuLinkList L);
    cout << "初始化线性表:" << CreatList(A) << CreatList(B) << CreatList(C) <<endl;
    B->next->next=new DulNode;//给B增加一个结点
    B->next->next->data=6;
    B->next->next->next= nullptr;
    cout << "输出链表:" << DisplayList(A) << endl;
    cout << "执行插入操作:" <<InsertElem(A,B) << endl;
    cout << "输出链表:" << DisplayList(A) << endl;
    cout << "执行有序插入:" << InsertElem2(A,B,C) << endl;
    cout << "输出链表:" << DisplayList(C);
    return 0;
}
Status CreatList(DuLinkList &L)
{
    L=new DulNode;
    L->next=new DulNode;
    L->data=3;
    L->next->next= nullptr;
    L->next->data=5;
    return OK;
}
Status InsertElem(DuLinkList &A,DuLinkList &B)
{
    DuLinkList AA,BB;
    AA=A;
    BB=B;
    int ab=1;
    while(BB)
    {
        ab=1;
        AA=A;
        while(AA->next)
//这里不是AA的原因是：当是AA循环结束后AA被空置，没有地址，就算是在这个重新创建一个变量，
//但是原来A->next已经指向NULL而不是指向这个新变量的地址，但如果在其上一步，就可以直接对A->next重新赋值
        {
            if(BB->data==AA->data)
            {
                ab=0;
            }
            if(BB->data==AA->next->data)
            {
                ab=0;
            }
            AA=AA->next;
        }
        if(ab==1)//如果没有这个元素在A中

        {
            AA->next=new DulNode;//此时AA就是A最后一个结点的地址
            AA->next->next= nullptr;
            AA->next->data=BB->data;
        }
        BB=BB->next;
    }
    return OK;
}
Status DisplayList(DuLinkList L)
{
    while(L)
    {
        cout << L->data <<" ";
        L=L->next;
    }
    cout << endl;
    return OK;
}
Status InsertElem2(DuLinkList &A,DuLinkList &B,DuLinkList &C)
{
    DulNode *pa=A;
    DulNode *pb=B;
    DulNode *pc=C;
    while(pa&&pb)
    {
        if(pa->data<=pb->data)
        {
            pc->data=pa->data;
            pc->next=new DulNode;//分配下一节点的空间
            pa=pa->next;
            pc=pc->next;
            //pc->next= nullptr;
        }
        else
        {
            pc->data=pb->data;
            pc->next=new DulNode;//分配下一节点的空间
            pb=pb->next;
            pc=pc->next;
            //pc->next= nullptr;//这一句和上面那一句可以不需要
        }
    }
    DuLinkList ppp;
    if(pa== nullptr)
    {
        while(pb)
        {
            pc->data=pb->data;
            pc->next=new DulNode;//分配下一节点的空间
            pb=pb->next;
            ppp=pc;
            pc=pc->next;
            pc->next= nullptr;
        }
    }
    else if(pb== nullptr)
    {
        while(pa)
        {
            pc->data=pa->data;
            pc->next=new DulNode;//分配下一节点的空间
            pa=pa->next;
            ppp=pc;
            pc=pc->next;
            pc->next= nullptr;
        }
    }
    delete pc;//删除最后一个多余的结点
    ppp->next= nullptr;//这个辅助变量存放多余结点的上一个结点，方便把这个结点的指针域设为NULL
    cout << endl;
    return OK;
}

这个算法存在一定的问题，最后会多出一个结点出来，以后看到这里的时候可以调试一下，或者用新的方法改进一下

注意点

  1. 利用辅助指针协助原链表完成一些操作的时候一定最开始不要把新分分配一个内存空间直接就赋值给这个辅助指针了，这样这个辅助指针就跑的别的内存中去了，根本对链表的操作无影响
    例如这两句pc=C; pc=new DulNode;，此时的pc已经指向了新分配的空间，已经不指向原链表了，正确的方式应该是，pc的指针域=新分配的空间
  2. 分配新结点内存的时候一定要把结点封住，就是给当前结点的指针域置空（NULL），否则指针域随机，指向随机内存，随机内存对应的结点的指针域又会指向另一个随机内存，如此循环，会有无数个结点
  3. 改进：
    1.上面那个已经标出的封住链表的操作可以不要，就搞一个无限的链表，后面最后的时候再封住
    2.最后把剩余结点附上去的时候，可以直接一次性到位，把剩下的全部一下接上去，而不用一个一个接，我实在是太傻了。。。

书上的做法，貌似C表不是无限的，不知到到尾结点后还怎么添加，是把A表直接复制给C表当初始化C表

第二章 线性表

2.8案例分析与实现

2.8.1多项式相加

多项式的链表表示

typedef struct PNode
{
    float coef;//系数
    int expn;//指数
    struct PNode *next;
}PNode,*PolyNomial;

用顺序表是一个道理

思路

利用类双指针的办法，分别遍历两个链表，讨论大于小于等于的情况，把需要的数据输入新链表

代码实现

#include<iostream>
#include<cmath>
#define OK "OK"
using namespace std;
typedef string Status;
typedef struct PNode
{
    float coef;//系数
    int expn;//指数
    struct PNode *next;
}PNode,*PolyNomial;
int main()
{
    PolyNomial A;
    PolyNomial B;
    PolyNomial C;
    Status CreatList(PolyNomial &L);//初始化链表
    Status AddList(PolyNomial &A,PolyNomial &B,PolyNomial &C);//链表相加
    Status DispalyList(PolyNomial L);//输出链表
    cout << CreatList(A) << CreatList(B) << endl;
    cout << DispalyList(A) << endl;
    cout << DispalyList(B) << endl;
    cout << AddList(A,B,C) << endl;
    cout << DispalyList(C) << endl;
    return 0；
}
Status CreatList(PolyNomial &L)
{
    L=new PNode;
    L->next= nullptr;
    PolyNomial p;
    p=L;
    cout << "初始化链表:" << endl;
    for(int i=0;i<3;i++)//默认三个结点
    {
        p->next=new PNode;
        p=p->next;
        cin >> p->coef >> p->expn;
    }
    p->next= nullptr;
    cout << endl;
    return OK;
}
Status DispalyList(PolyNomial L)
{
    cout << "输出链表:" << endl;
    PolyNomial p=L;
    p=p->next;
    while(p)
    {
        cout << p->coef << "^" << p->expn << "  ";
        p=p->next;
    }
    cout << endl;
    return OK;

}
Status AddList(PolyNomial &A,PolyNomial &B,PolyNomial &C)
{
    cout << "链表相加:" << endl;
    PolyNomial a,b,c,p;
    a=A->next;
    b=B->next;
    C=new PNode;
    C->next= nullptr;
    c=C;
    while(a&&b)
    {
        c->next=new PNode;
        p=c;
        c=c->next;
        if(a->expn < b->expn)
        {
            c->coef=a->coef;
            c->expn=a->expn;
            a=a->next;
        }
        else if(a->expn > b->expn)
        {
            c->coef=b->coef;
            c->expn=b->expn;
            b=b->next;
        }
        else
        {
            if(a->coef != -1*b->coef)
            {
                c->expn=a->expn;
                c->coef=a->coef+b->coef;
                a=a->next;
                b=b->next;
            }
            else
            {
                c=p;
                a=a->next;
                b=b->next;
            }
        }
    }
    if(!a)//把余下的结点放入C链表中
    {c->next=b;}
    else
    {c->next=a;}
    return OK;
}

2.8案例分析与实现

2.8.1多项式相加

多项式的链表表示

typedef struct PNode
{
    float coef;//系数
    int expn;//指数
    struct PNode *next;
}PNode,*PolyNomial;

用顺序表是一个道理

思路

利用类双指针的办法，分别遍历两个链表，讨论大于小于等于的情况，把需要的数据输入新链表

代码实现

#include<iostream>
#include<cmath>
#define OK "OK"
using namespace std;
typedef string Status;
typedef struct PNode
{
    float coef;//系数
    int expn;//指数
    struct PNode *next;
}PNode,*PolyNomial;
int main()
{
    PolyNomial A;
    PolyNomial B;
    PolyNomial C;
    Status CreatList(PolyNomial &L);//初始化链表
    Status AddList(PolyNomial &A,PolyNomial &B,PolyNomial &C);//链表相加
    Status DispalyList(PolyNomial L);//输出链表
    cout << CreatList(A) << CreatList(B) << endl;
    cout << DispalyList(A) << endl;
    cout << DispalyList(B) << endl;
    cout << AddList(A,B,C) << endl;
    cout << DispalyList(C) << endl;
    return 0；
}
Status CreatList(PolyNomial &L)
{
    L=new PNode;
    L->next= nullptr;
    PolyNomial p;
    p=L;
    cout << "初始化链表:" << endl;
    for(int i=0;i<3;i++)//默认三个结点
    {
        p->next=new PNode;
        p=p->next;
        cin >> p->coef >> p->expn;
    }
    p->next= nullptr;
    cout << endl;
    return OK;
}
Status DispalyList(PolyNomial L)
{
    cout << "输出链表:" << endl;
    PolyNomial p=L;
    p=p->next;
    while(p)
    {
        cout << p->coef << "^" << p->expn << "  ";
        p=p->next;
    }
    cout << endl;
    return OK;

}
Status AddList(PolyNomial &A,PolyNomial &B,PolyNomial &C)
{
    cout << "链表相加:" << endl;
    PolyNomial a,b,c,p;
    a=A->next;
    b=B->next;
    C=new PNode;
    C->next= nullptr;
    c=C;
    while(a&&b)
    {
        c->next=new PNode;
        p=c;
        c=c->next;
        if(a->expn < b->expn)
        {
            c->coef=a->coef;
            c->expn=a->expn;
            a=a->next;
        }
        else if(a->expn > b->expn)
        {
            c->coef=b->coef;
            c->expn=b->expn;
            b=b->next;
        }
        else
        {
            if(a->coef != -1*b->coef)
            {
                c->expn=a->expn;
                c->coef=a->coef+b->coef;
                a=a->next;
                b=b->next;
            }
            else
            {
                c=p;
                a=a->next;
                b=b->next;
            }
        }
    }
    if(!a)//把余下的结点放入C链表中
    {c->next=b;}
    else
    {c->next=a;}
    return OK;
}
上一篇：记录登录状态的功能的实现


下一篇：python学习笔记（9）——数据乱码的处理之重新编码和解码