C严蔚敏数据结构-单链表

客官°小女子只卖身不卖艺 2022-01-07 10:51 257阅读 0赞

##  单链表的插入 ##

> **时间复杂度：O(n)** 
> 
>  *  **查找节点ai-1并由指针指向该节点**
>  *  **生成一个新节点\*s**
>  *  **将新节点\*s的数据域置为e**
>  *  **将新节点\*s的指针域指向节点ai**
>  *  **将节点\*p的指针域指向新节点\*s**

Status ListInsert(List *L,int i,ElemType e)     //在指定位置插入数据域为e的节点
    {
        List* p = L,*node;
        int j = 0;                                  //从头结点开始
        while(p&&j<i-1)                             //顺序往后扫描，直到p为空或p所指节点为指定位置的上一个节点
        {
            p = p->next;
            ++j;
        }
        if(!p||j>i-1)                               //i>n+1或i<1,因为j的初始值为0
            return ERROR;
        node = (List*)malloc(sizeof(List));         //为新建节点申请堆空间
        node->data = e;
        node->next = p->next;                       //将新建节点的指针域指向原i位置节点的地址
        p->next = node;                             //p节点的指针域指向新建节点
        return OK;
    }

## 单链表的删除 ##

>  **时间复杂度：O(n)** 
> 
>  *  **查找节点ai-1并由指针指向该节点**
>  *  **临时保存待删除节点ai的地址在q中，以备释放**
>  *  **将节点\*p的指针域指向ai的直接后继节点**
>  *  **释放节点ai的空间**

Status ListDelete(List *L,int i,ElemType &e)    //删除指定位置的节点，并返回该节点的值
    {
        List *p = L,*q;                             //p指向头结点
        int j = 0;                                  //j初始化为0，因为可能删除首元节点
        while(p->next&&j<i-1)                       //当p的下一个节点不为空或p指向第i-1个节点
        {
            p = p->next;
            ++j;
        }
        if(!p->next||j>i-1)                         //如果p的指针域为空或i<1,返回假
            return ERROR;                           //删除位置不合理
        q = p->next;                                //q指向p的下一个节点（删除节点）
        e = q->data;                                //将q的数据域的值赋给e
        p->next = q->next;                          //将p的指针域指向删除节点的下一个节点
        free(q);                                    //释放删除节点所申请的空间
        return OK;
    }

## 单链表的合并（递增有序） ##

> **问题：A和B是两个单链表（带表头节点），其中元素递增有序。设计一个算法，将A和B归并成一个按元素值非递减有序（允许有重复值）的链表C，C由A和B中的节点组成**
> 
> **解决方法：从A和B挑出最小的元素插入到C的尾部**

void merge(List *L1,List *L2,List *&L3)
    {
        List *p = L1->next;     //p指向L1的首元节点
        List *q = L2->next;     //q指向L2的首元节点
        List *pr = L3;          
        L3 = L1;                //将L1的头结点赋给L3
        L3->next = NULL;        
        free(L2);               //释放L2的头结点
        pr = L3;                //pr指向L3
        while(p&&q)             //当p和q均不为空时，即当L1,L2表长短的一方遍历完结束循环
        {
            if(p->data<q->data)    //当p所指节点的数据域的值小于q，将其插入到L3尾部
            {
                pr->next = p;        
                p = p->next;
                pr = pr->next;
            }
            else
            {
                pr->next = q;
                q = q->next;
                pr = pr->next;
            }
        }
        if(p)                      //当p不为空时，即p没有遍历结束，p剩下的元素一定比q大，直接插入到L3尾部
        {
            pr->next = p;
        }
        if(q)
        {
            pr->next = q;
        }
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

#include <stdio.h>
    #include <stdlib.h>
    #define OK 1
    #define ERROR 0
    typedef int ElemType;
    typedef int Status;
    typedef struct list List;
    struct list
    {
        ElemType data;
        List* next;
    };
    List* CreateList01(List *L,int n);
    List* CreateList(List *L,int n);
    Status ListPrintf(List *L);
    Status Getelem(List *L,int i,ElemType &e);
    Status LocateElem(List *L,int i,ElemType &e);
    List* LocateElem(List *L,ElemType e);
    Status ListInsert(List *L,int i,ElemType e);
    Status ListDelete(List *L,int i,ElemType &e);
    Status CreateList02(List *&L,int n);
    void merge(List *L1,List *L2,List *&L3);
    int main()
    {
        int n,a,b;
        char c;
        List* L;
        while(true)
        {
            printf("请选择执行的操作:\n1.创建链表\n2.取值\n3.按值查找\n4.插入\n5.删除\n6.链表合并\n7.打印链表\n8.退出程序\n");
            scanf(" %c",&c);
            if(c=='1')
            {
                printf("请输入链表的长度:\n");
                scanf("%d",&n);
                CreateList02(L,n);
                ListPrintf(L);
            }
            else if(c=='2')
            {
                printf("请输入获取元素的序号:\n");
                scanf("%d",&a);
                Getelem(L,a,b);
                printf("位置%d的元素为%d\n",a,b);
            }
            else if(c=='3')
            {
                printf("请输入你想要查询的数据:\n");
                scanf("%d",&a);
                /*
                if(LocateElem(L,a,b))
                {
                    printf("该数据在链表中的节点下标为:%d\n",b);
                }
                else
                {
                    printf("该元素链表中不存在!\n");
                }   */
                if(LocateElem(L,a))
                {
                    printf("该元素存在!\n");
                }
                else
                {
                    printf("该元素链表中不存在!\n");
                }
    
            }
            else if(c=='4')
            {
                printf("请输入插入的位置和元素:\n");
                scanf("%d %d",&a,&b);
                if(!ListInsert(L,a,b))
                {
                    printf("插入位置不合法!\n");
                }
                ListPrintf(L);
            }
            else if(c=='5')
            {
                printf("请输入删除的位置:\n");
                scanf("%d",&a);
                if(ListDelete(L,a,b))
                {
                    printf("删除的元素为%d\n",b);
                    ListPrintf(L);
                }
                else
                {
                    printf("删除位置不合理!\n");
                }
            }
            else if(c=='6')
            {
                List *L1,*L2,*L3;
                printf("请输入链表L1的长度:\n");
                scanf("%d",&a);
                CreateList02(L1,a);
                ListPrintf(L1);
                printf("请输入链表L2的长度:\n");
                scanf("%d",&b);
                CreateList02(L2,b);
                ListPrintf(L2);
                printf("合并后:\n");
                merge(L1,L2,L3);
                ListPrintf(L3);
            }
            else if(c=='7')
            {
                ListPrintf(L);
            }
            else
            {
                exit(0);
            }
        }
    }
    List* CreateList01(List *L,int n)       //创建链表，返回链表的地址-----尾插法创建链表，链表是顺序插入的
    {
        List *end,*node;
        L = (List*)malloc(sizeof(List));    //创建头结点，并申请堆空间
        L->next = NULL;                     //头结点指针域置空
        end = L;                            //使尾结点指向头结点
        printf("请输入链表中的数据:\n");
        for(int i=0;i<n;i++)
        {
            node = (List *)malloc(sizeof(List));     //创建子节点，并申请堆空间
            scanf("%d",&node->data);
            node->next = NULL;                       //新建子节点的指针域置空
            end->next = node;                        //尾结点的指针域指向新建子节点(让上一个节点指针域保存下一个节点的地址)
            end = node;                              //尾结点指向新建子节点
        }
        return L;
    }
    Status CreateList02(List* &L,int n)       //创建链表，返回链表的地址-----尾插法创建链表，链表是顺序插入的
    {
        List *end,*node;
        L = (List*)malloc(sizeof(List));    //创建头结点，并申请堆空间
        L->next = NULL;                     //头结点指针域置空
        end = L;                            //使尾结点指向头结点
        printf("请输入链表中的数据:\n");
        for(int i=0;i<n;i++)
        {
            node = (List *)malloc(sizeof(List));     //创建子节点，并申请堆空间
            scanf("%d",&node->data);
            node->next = NULL;                       //新建子节点的指针域置空
            end->next = node;                        //尾结点的指针域指向新建子节点(让上一个节点指针域保存下一个节点的地址)
            end = node;                              //尾结点指向新建子节点
        }
    }
    List* CreateList(List *L,int n)         //创建链表，返回链表的地址-----前插法创建链表，链表是逆序插入的
    {
        L = (List*)malloc(sizeof(List));    //创建头结点，并申请堆空间
        L->next = NULL;                     //头结点指针域置空
        printf("请输入链表中的数据:\n");
        for(int i=0; i<n; i++)
        {
            List* p = (List*)malloc(sizeof(List));  //创建子节点，并申请堆空间
            scanf("%d",&p->data);
            p->next = L->next;                      //将头节点的指针域赋给新建节点
            L->next = p;                            //头结点指针域指向新建节点
        }
        return L;
    }
    Status Getelem(List *L,int i,ElemType &e)       //获取指定位置的值
    {
        List* p = L->next;                          //初始化，p指向首元节点
        int j = 1;                                  //j的值初始化为1，等于节点在链表中的下标
        while(p&&j<i)                               //当p不为空且j<i时，即此时p指向待取节点
        {
            p = p->next;
            ++j;
        }
        if(!p||j>i)                                 //(!p)表示此时i>链表长度，此时p==NULL，j>i表示i<=0
        {
            return ERROR;                           //i值不合理，返回0
        }
        e = p->data;                                //将待取节点的值赋给e，因为e是地址传递，所以可以直接修改e的值
        return OK;
    }
    List* LocateElem(List *L,ElemType e)            //查找值为e的节点，并返回其地址
    {
        List* p = L->next;                          //初始化，p指向首元节点
        while(p&&p->data!=e)                        //从前往后扫描，直到p为空或p所指节点的数据域为e为止
        {
            p=p->next;
        }
        return p;                                   //若链表中存在节点数据域为e，则返回该节点地址，若不存在，则返回NULL
    }
    Status LocateElem(List *L,int i,ElemType &e)    //返回指定值在链表中节点的下标（自己写的，好像没什么用）
    {
        List* p = L->next;
        int j=1;
        while(p&&p->data!=i)                        //从前往后扫描，直到p为空或p所指节点的数据域为e为止
        {
            p=p->next;
            ++j;
        }
        if(p==NULL||p->data!=i)return ERROR;        //如果此时p为空或p所指节点的数据域不为i，则说明链表中不存在，返回假
        e = j;                                      //将下标赋给e
        return OK;
    }
    Status ListInsert(List *L,int i,ElemType e)     //在指定位置插入数据域为e的节点
    {
        List* p = L,*node;
        int j = 0;                                  //从头结点开始
        while(p&&j<i-1)                             //顺序往后扫描，直到p为空或p所指节点为指定位置的上一个节点
        {
            p = p->next;
            ++j;
        }
        if(!p||j>i-1)                               //i>n+1或i<1,因为j的初始值为0
            return ERROR;
        node = (List*)malloc(sizeof(List));         //为新建节点申请堆空间
        node->data = e;
        node->next = p->next;                       //将新建节点的指针域指向原i位置节点的地址
        p->next = node;                             //p节点的指针域指向新建节点
        return OK;
    }
    Status ListDelete(List *L,int i,ElemType &e)    //删除指定位置的节点，并返回该节点的值
    {
        List *p = L,*q;                             //p指向头结点
        int j = 0;                                  //j初始化为0，因为可能删除首元节点
        while(p->next&&j<i-1)                       //当p的下一个节点不为空或p指向第i-1个节点
        {
            p = p->next;
            ++j;
        }
        if(!p->next||j>i-1)                         //如果p的指针域为空或i<1,返回假
            return ERROR;                           //删除位置不合理
        q = p->next;                                //q指向p的下一个节点（删除节点）
        e = q->data;                                //将q的数据域的值赋给e
        p->next = q->next;                          //将p的指针域指向删除节点的下一个节点
        free(q);                                    //释放删除节点所申请的空间
        return OK;
    }
    void merge(List *L1,List *L2,List *&L3)
    {
        List *p = L1->next;
        List *q = L2->next;
        List *pr = L3;
        L3 = L1;  //将L1的头结点赋给L3
        L3->next = NULL;
        free(L2);   //释放L2的头结点
        pr = L3;   //pr指向L3
        while(p&&q)
        {
            if(p->data<q->data)
            {
                pr->next = p;
                p = p->next;
                pr = pr->next;
            }
            else
            {
                pr->next = q;
                q = q->next;
                pr = pr->next;
            }
        }
        if(p)
        {
            pr->next = p;
        }
        if(q)
        {
            pr->next = q;
        }
    
    }
    Status ListPrintf(List *L)
    {
        List* p = L->next;
        while(p)
        {
            printf("%d\t",p->data);
            p = p->next;
        }
        printf("\n");
        return OK;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211223/65db7dc9fbfa46a3a0387df6dcf93916.png