【数据结构】第2章线性表单链表整理

约定不等于承诺〃 2022-11-27 03:28 195阅读 0赞

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

--------------------

## 一、单链表基本操作 ##

1、单链表是**顺序存取**、**随机存储**

2、为了提高程序的可读性，单链表对同一结构体指针类型起了两个名称，`LinkList` 与 `LNode*`，两者本质上是等价的。  
习惯上用`LinkList`定义单链表，强调定义的是某个单链表的头指针，如`LinkList L`；  
用`LNode*`定义指向单链表中任意结点的指针变量，如`LNode *p`。

3、一般为了处理方便，初始化时在单链表的第一个结点之前附设一个结点，称之为头结点L，本文均为带头结点的单链表：  
（1）带头结点的单链表：  
![在这里插入图片描述][2020081617334389.png_pic_center]  
头指针（L）->头结点（阴影）->首元结点（ZHAO）  
L是头指针，L指向头结点，L->next指向首元结点  
空表：`L->next == NULL`  
链表不存在：`L == NULL`  
（2）不带头结点的单链表：  
![在这里插入图片描述][20200816174741190.png_pic_center]

头指针（L）->首元结点（ZHAO）  
L是头指针，L指向首元结点，L->next就指向第二个元素结点了！  
空表：`L == NULL`

4、插入结点一般先接后链，在接前链

5、删除结点要释放空间`delete q`

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----单链表的储存结构-----
    typedef struct LNode
    {
        
        ElemType data;              //结点的数据域
        struct LNode *next;         //结点的指针域
    }LNode, *LinkList;              //LinkList为指向结构体LNode的指针类型
    
    LinkList L;
    
    //1、单链表初始化 O(1)
    Status InitList(LinkList &L)
    {
        //构造一个带头结点的空单链表L
        L = new LNode;              //生成新的结点作为头结点，用头指针L指向头结点
        L->next = NULL;             //头结点的指针域置空
        return OK;
    }
    
    //2、单链表销毁 O(n)
    Status DestroyList(LinkList &L)
    {
        //销毁头结点L，表头后的一个个销毁，此链表不能再使用
        if(L == NULL)
            return ERROR;
        while(L)
        {
        
            LNode *p = L->next;
            delete L;                
            L = p;
        }
        return OK;
    }
    
    //3、单链表清空 O(n)
    Status ClearList(LinkList &L)
    {
        //保留头结点L，表头后的一个个销毁，最后把L的next指针置为空，此链表还可以使用
        if(L == NULL)
            return ERROR;
        LNode *p = L->next;
        while(p)
        {
        
            LNode *q = p->next;
            delete p;
            p = q;
        }
        L->next = NULL;
        return OK;
    }
    
    //4、单链表判空 O(1)
    Status ListEmpty(LinkList L)
    {
        //判断带头结点的单链表是否为空表
        if(L->next == NULL)
            return OK;
        return ERROR;
    }
    
    //5、单链表长度 O(n)
    Status ListLength(LinkList L)
    {
        //返回带头结点的单链表的长度
        LNode *p = L;                   //p指向头结点
        int j = 0;                      //计数器j初值赋为0
        while(p->next)                  //直到p的后继为空时停止
        {
        
            p = p->next;                //p指向下一个结点
            j++;                        //计数器j相应加1
        }
        return j;
    }
    
    //6、单链表取值 O(n)
    Status GetElem(LinkList L, int i, ElemType &e)
    {
        //在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个元素的值
        LNode *p = L->next;             //p指向首元结点
        int j = 1;                      //计数器j初值赋为1
        while(p && j < i)               //直到p为空或p指向第i个元素时停止
        {
        
            p = p->next;                //p指向下一个结点               
            j++;                        //计数器j相应加1                       
        }
        if(!p || j > i)                 //i值不合法，即i > n或i < 1
            return ERROR;
        e = p->data;                    //取第i个结点的数据域
        return OK;
    }
    
    //7、单链表查找 O(n)
    LNode *LocateElem(LinkList L, ElemType e)
    {
        //在带头结点的单链表中查找值为e的元素，返回e的地址（所以LNode *LocateElem）
        LNode *p = L->next;             //p指向首元结点
        while(p && p->data != e)        //直到p为空或p所指结点的数据域等于e时停止
            p = p->next;                //p指向下一个结点
        return p;                       //查找成功返回值为e的结点地址p，查找失败p为NULL
    }
    
    //8、单链表前驱 O(n)
    Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
    {
        
        LNode *p = L->next;                 
        while(p && p->next->data != cur_e)  //直到p为空或p指向cur_e的前驱时停止
            p = p->next;
        if(p)
        {
        
            pre_e = p->data;
            return OK;
        }
        else
            return ERROR; 
    }
    
    //9、单链表后继 O(n)
    Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
    {
        
        LNode *p = L->next;
        while(p->next && p->data != cur_e)  //直到p的后继为空或p指向cur_e时停止
            p = p->next;
        if(p->next)
        {
        
            next_e = p->next->data;
            return OK;
        }
        else
            return ERROR;   
    }
    
    //10、单链表插入 O(n)
    Status ListInsert(LinkList &L, int i, ElemType e)
    {
        //在带头结点的单链表L中第i个位置插入值为e的新结点
        LNode *p = L;                   //p指向头结点
        int j = 0;                      //计数器j初值赋为0
        while(p && j < i - 1)           //直到p为空或p指向第i-1个结点时停止
        {
        
            p = p->next;                //p指向下一个结点
            j++;                        //计数器j相应加1
        }                               
        if(!p || j > i - 1)             //i值不合法，即i > n + 1或i < 1
            return ERROR;
        LNode *s = new LNode;           //生成新结点*s
        s->data = e;                    //将结点*s的数据域置为e
        s->next = p->next;              //先接后链
        p->next = s;                    //再接前链
        return OK; 
    }
    
    //11、单链表删除 O(n)
    Status ListDelete(LinkList &L, int i)
    {
        //在带头结点的单链表L中，删除第i个元素
        LNode *p = L;                   //p指向头结点
        int j = 0;                      //计数器j初值赋为0
        while(p->next && j < i - 1)     //直到p的后继为空或p指向第i-1个结点时停止
        {
        
            p = p->next;                //p指向下一个结点
            j++;                        //计数器j相应加1
        }                               
        if(!(p->next) || j > i - 1)     //i值不合法，即i > n或i < 1
            return ERROR;               
        LNode *q = p->next;             //临时保存被删结点的地址以备释放
        p->next = q->next;              //前驱接后驱
        delete q;                       //释放删除结点的空间
    }   
    
    // //12、单链表遍历 O(n) 
    // Status TraverseList(LinkList L)
    // {
        
    //     LNode *p = L->next;             
    //     while(p->next)
    //     {
        
    //         cout<<p->data<<' ';
    //         p = p->next;
    //     }
    //     cout<<p->data<<'\n';
    //     return OK;
    // }
    
    //12、单链表递归遍历
    void TraverseList(LinkList L)
    {
        
        if(L == NULL)
        {
        
            cout<<endl;
            return;                  //递归中止
        }
        else
        {
        
            cout<<L->data<<ends;     //输出当前数据域
            TraverseList(L->next);   //p指向后继结点继续递归
        }
    }
    
    //13、前插法创建单链表 O(n)
    void CreateList_H(LinkList &L, int n)
    {
        //逆位序输入n个元素的值，建立带头结点的单链表L
        L = new LNode;                  //先初始化一个带头结点的空链表
        L->next = NULL;                 
        for(int i = 0; i < n; i++)
        {
        
            LNode *p = new LNode;       //生成新结点*p
            cin>>p->data;               //输入元素值赋给新结点*p的数据域
            p->next = L->next;          //先接后链
            L->next = p;                //再接前链，将新结点*p插入到头结点之后
        }
    }
    
    //14、后插法创建单链表 O(n)
    void CreateList_R(LinkList &L, int n)
    {
        //正位序输入n个元素的值，建立带头结点的单链表L
        L = new LNode;                  //先初始化一个带头结点的空链表
        L->next = NULL;                 
        LNode *r = L;                   //尾指针r先指向头结点
        for(int i = 0; i < n; i++)
        {
        
            LNode *p = new LNode;       //生成新结点*p
            cin>>p->data;               //输入元素值赋给新结点*p的数据域
            p->next = NULL;             //后置空后链             
            r->next = p;                //再接前链
            r = p;                      //r指向新的尾结点*p
        }
    }
    
    //15、单链表就地逆置 O(n)
    void ReverseList(LinkList &L)
    {
        
        LNode *p = L->next;             //p指向首元结点，保留原链表往后的所有结点
        L->next = NULL;                 //逆置链表的首元结点置为空
        while(p)                        //直到p为空时停止
        {
        
            LNode *q = p->next;         //q指向当前处理结点的下一个结点，保留原链表往后所有节点
            p->next = L->next;          //先接后链
            L->next = p;                //在接前链
            p = q;                      //把q保留的还给p
        }
    }

## 二、单链合并及有序单链表 ##

#### 16、单链表合并 O(m \* n) ####

//16、单链表并集 O(m * n)
    void MergeList(LinkList &LA, LinkList LB)
    {
        //将所有在线性表LB中但不在LA中的数据元素插入到LA中，无重复
        int m = ListLength(LA), n = ListLength(LB);     //求线性表长度
        for(int i = 1; i <= n; i++) 
        {
        
            ElemType e;
            GetElem(LB, i, e);                          //取LB中的第i个元素赋给e
            if(!LocateElem(LA, e))                      //LA中不存在与e相同的数据元素
                ListInsert(LA, ++m, e);                 //将e插在LA的最后，先++，再传值
        }
    }

//16、单链表交集 O(m * n)
    void MixList(LinkList LA, LinkList LB, LinkList &LC)
    {
        //将线性表LB中和LA中共有的数据元素插入到LC中
        int m = ListLength(LA), n = ListLength(LB);     //求线性表长度
        int k = 0;
        for(int i = 1; i <= n; i++) 
        {
        
            ElemType e;
            GetElem(LB, i, e);                          //取LB中的第i个元素赋给e
            if(LocateElem(LA, e))                       //LA中存在与e相同的数据元素
                ListInsert(LC, ++k, e);                 //将e插在LC的最后，先++，再传值
        }
    }

#### 17、有序单链表创建 O(n^2) ####

//17、有序单链表创建_非递减 O(n^2)                                             
    void CreateOrderList(LinkList &L, int n)
    {
        //输入n个元素，建立非递减有序单链表L，允许有重复
        L = new LNode;
        L->next = NULL;                     
        for(int i = 1; i <= n; i++)         
        {
        
            LNode *s = new LNode;           //生成新结点
            cin>>s->data;
            LNode *pre = L;                 //pre指向头结点，在前
            LNode *q = L->next;             //q指向首元结点，在后
            while(q && q->data < s->data)   //通过比较指数找到第一个大于输入元素的结点*q
            {
        
                pre = q;                    //q先把当前结点传给pre
                q = q->next;                //q再指向下一个结点
            }
            s->next = q;                    //先接后链
            pre->next = s;                  //再接前链
        }
    }

#### 18、有序单链表的并集 空间O(1) ####

//18、有序单链表并集_非递减 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值非递减排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列，允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较小的结点插入到LC的最后
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next; 
            }
        }
        pc->next = pa ? pa: pb;         //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

//18、有序单链表并集_非递增 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值非递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值非递增排列，允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较大的结点插入到LC的最后
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
        }
        pc->next = pa ? pa: pb;         //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

//18、有序单链表并集_递增 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值递增排列，不允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        LNode *q;
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较小的结点插入到LC的最后
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else if(pa->data < pb->data)     
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else                        //当两表值相等时，将pa的插入到LC的最后，pb的删除                
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
                q = pb;
                pb = pb->next;
                delete q;
            }
        }
        pc->next = pa ? pa : pb;        //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

//18、有序单链表并集_递减 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值递增排列，不允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        LNode *q;
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较大的结点插入到LC的最后
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else if(pa->data < pb->data)     
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else                        //当两表值相等时，将pa的插入到LC的最后，pb的删除                
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
                q = pb;
                pb = pb->next;
                delete q;
            }
        }
        pc->next = pa ? pa : pb;        //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

#### 19、有序单链表交集 ####

//19、有序单链表交集_递增
    void MixOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值递增排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值递增排列
        LC = new LNode;
        LC = LA;
        LNode *pa = LA->next;
        LNode *pb = LB->next;
        LNode *pc = LC;
        LNode *q;
        while(pa && pb)
        {
        
            if(pa->data > pb->data)
            {
        
                q = pb;
                pb = pb->next;
                delete q;
            }
            else if(pa->data < pb->data)
            {
        
                q = pa;
                pa = pa->next;
                delete q;
            }
            else
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next;
                q = pb;
                pb = pb->next;
                delete q;
            } 
        }
        while(pa)
        {
        
            q = pa;
            pa = pa->next;
            delete q;
        }
        while(pb)
        {
        
            q = pb;
            pb = pb->next;
            delete q;
        }
        pc->next = NULL;
        delete LB;
    }

#### 20、有序单链表差集 ####

//20、有序单链表差集_递增
    void DifferOrderList(LinkList &LA, LinkList LB, LinkList &C)
    {
        //将LA中存在且LB中不存在的元素存放在LA中
        LC = new LNode;
        LC = LA;
        LNode *pa = LA->next;
        LNode *pb = LB->next;
        LNode *pc = LC;
        LNode *q;
        while(pa && pb)
        {
        
            if(pa->data > pb->data)         //LA的大于LB的，LB向后移
                pb = pb->next;
            else if(pa->data < pb->data)    //LA，小于LB的，添加到LC
            {
        
                pc = pa;
                pa = pa->next;
            }
            else                            //若相同，删除LA中的结点
            {
        
                pc->next = pa->next;
                q = pa;
                pa = pa->next;
                delete q;
            }
        }
    }

[2020081617334389.png_pic_center]: /images/20221124/4d002955f2904b838b0ef69e9df1a486.png
[20200816174741190.png_pic_center]: /images/20221124/69f48ea8d90c465eb17949a3b06113c7.png