c语言数据结构--链表（1）

亦凉 2024-03-23 13:00 42阅读 0赞

这一期主要讲顺序表的插入和删除操作、头插法和尾插法、链表的插入和删除操作

一、顺序表的插入和删除操作

利用定义的顺序表的数据类型SeqList就可以定义变量了。变量L的定义与使用方法有以下两种：

*  通过变量定义语句：

将L定义成SeqList类型的变量，利用L.elem\[ i-1 \]来访问顺序表中序号为 i 的元素*ai*![696516018acb47fc916c31f673d46891.png][]；通过L.last 可得到顺序表中最后的一个元素的下标，而L.last+1就是顺序表的长度。

*  通过指针变量定义语句：

将L定义为指向SeqList类型的指针变量，使用时，可通过L->elem\[ i-1 \] 来访问顺序表中的序号为i的元素*ai*![fc1b513953064eda89c14b1e27d36bd9.png][]，使用L->last+1 则得到顺序表的长度。

（1）插入操作

int InsList(SeqList *L,int i,int e)
    {
        int k;
        if((i<1)||(L->last+2))     //（1）//判断插入位置是否合法，如果小于1或者大于表长加1，则返回错误
        {
            printf("插入位置i不合法");
            return ERROR;
        }
        if(L->last>=MAXSIZE-1)     //（2）
        {
            printf("表已满");
            return ERROR;
        }
        for (k=L->last;k>=i-1;k--)//（3）//从表尾开始，将第i个位置及之后的元素依次后移一位，为插入元素腾出空间
        {
            L->elem[k+1] = L->elem[k];   //依次后移
        }
        L->elem[i-1]=e;       //将元素e放入第i个位置
        L->last++;             //更新表长
        return OK;
    }

（1）段代码 i 表示为要插入的位置，它的合法取值范围是1<= i< =L->last+2，插入的位置可以是表的末尾，所以 L->last+1 可以再加1变成 L->last+2

（2）段代码L->last >=MAXSIZE-1，说明已经超出顺序表的长度，表示表已经满了

（3）段怎么理解呢？

假设线性表有（28，31，10，21，25，38），要在第三个元素之前插入一个元素999

那么就需要将最后一个元素和第三个位置的元素依次后移，然后插入999

此时 i = 3，e = 999，L->last=5

① 先将元素依次往后移

for (k=L->last;k>=i-1;k--)//（3）//从表尾开始，将第i个位置及之后的元素依次后移一位，为插入元素腾出空间
        {
            L->elem[k+1] = L->elem[k];   //依次后移
        }

![666d50e60239471ebba0da4f902ed662.jpeg][]

②插入元素和更新表长

L->elem[i-1]=e;       //将元素e放入第i个位置
        L->last++;             //更新表长

![858eebddfe4a43a8bd27c5b9cfb329c3.jpeg][]

（2）删除操作

int DelList(SeqList *L,int i,int *e)
    {
        int k;
        if((i<1) || (i>L->last+1))     //（1）判断删除位置是否合法，如果小于1或者大于表长，则返回错
        {
            printf("删除的位置不合法！");
            return ERROR;
        }
        *e = L->elem[i-1];                //（2）将第i个位置的元素的值赋给e
        for(k=i;i<=L->last;k++)          //（3）从第i+1个位置开始，将之后的元素依次前移一位，覆盖被删除的元素
        {
            L->elem[k-1] = L->elem[k];     //将元素依次往前移
        }
        L->last--;                     //更新表长
        return OK;
    }

（1）段代码 i 表示为要删除的位置，它的合法取值范围是1<= i< =L->last+1；因为序号i里不能是空的，得有元素才能删除，所以相比于插入操作长度就少了1。

（2）段代码 将第i个位置的元素的值赋给e

（3）段代码怎么理解呢？

假设线性表有（28，31，10，21，25，38），删除第四个元素，即

那么就需要将第五个元素和最后一个元素依次往前移

此时 i = 4，\*e=21，L->last=5

①将元素往前移

for(k=i;i<=L->last;k++)          //（3）从第i+1个位置开始，将之后的元素依次前移一位，覆盖被删除的元素
        {
            L->elem[k-1] = L->elem[k];     //将元素依次往前移
        }

![ce94d55f4abd4e6cade75e9151893be7.jpeg][]

②更新表长

L->last--;                     //更新表长

二、头插法和尾插法

1、头插法

void CreateFromHead(LinkList L)
    {
        Node *s;                  //定义一个新节点指针s
        char c;                   //定义一个字符变量c，用于存储输入的数据
        int flag=1;               //定义一个标志变量flag，用于控制循环结束
        while(flag)             //循环输入数据，直到输入-99为止
        {
            scanf("%d",&c);
            if(c!=-99)                    //如果输入的数据不是-99，表示还要继续插入节点
            {
                s = (Node*) malloc(sizeof(Node));
                s->data = c;            //将输入的数据赋给新节点的数据域
                s->next = L->next;      //将新节点的指针域指向原来的第一个节点
                L->next = s;           //将头节点的指针域指向新节点，完成头插操作
            }
            else                      //如果输入的数据是-99，表示结束插入
            {
                flag = 0;            //将标志变量置为0，退出循环
            }
        }
    }

① 初始化链表

void InitList(LinkList *L)
    {
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;
    }

② 申请新结点并赋值

s = (Node*) malloc(sizeof(Node));  //动态分配一个结点的内存空间，并让s指向它
          s->data = c;                            //将c的值赋给s所指结点的数据域

③插入结点

r->next = s;                             //将s所指结点链接到r所指结点的后面
         r=s;                                     //让r指向s，即更新尾结点的位置

图解：

![a7494a8418d5428db966c4e20c5e13e1.jpeg][]

2、尾插法

void CreateTail(LinkList L)
    {
        Node *r,*s;                  //定义两个指针变量，r指向链表的尾结点，s指向新创建的结点
        int flag=1;                  //定义一个标志变量，用于控制循环的结束
        int c;                       //定义一个整型变量，用于存储输入的数据
        r=L;                        //让r指向链表的头结点
        while(flag)                 //循环直到flag为0
        {
            scanf("%d",&c);         //从标准输入读取一个整数赋值给c
            if(c!=-99)                     //如果c不等于-99，表示还有数据需要插入链表
            {
                s = (Node*) malloc(sizeof(Node));  //动态分配一个结点的内存空间，并让s指向它
                s->data = c;                            //将c的值赋给s所指结点的数据域
                r->next = s;                             //将s所指结点链接到r所指结点的后面
                r=s;                                     //让r指向s，即更新尾结点的位置
            }
            else                                        //如果c等于-99，表示没有数据需要插入链表
            {
                flag = 0;                              //将flag置为0，结束循环
                r->next = NULL;                        //将尾结点的指针域置为NULL，表示链表结束
            }
        }
    }

①初始化

void InitList(LinkList *L)
    {
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;
    }

②申请新节点并赋值

s = (Node*) malloc(sizeof(Node));  //动态分配一个结点的内存空间，并让s指向它
          s->data = c;                            //将c的值赋给s所指结点的数据域

③插入节点

r->next = s;                             //将s所指结点链接到r所指结点的后面
              r=s;                                     //让r指向s，即更新尾结点的位置

图解：

![59cdbdd72a4a48f6bf3c3cdb0b9cb096.jpeg][]

三、链表的插入和删除操作

（1）插入操作

（在第i个结点前插入一个节点）

int InsList(LinkList L,int i,int e)
    
    {
        Node *pre,*s;              //定义两个指针变量，pre指向插入位置的前一个结点，s指向新创建的结点
        int k;                     //定义一个整型变量，用于记录当前遍历到的结点的位置
        pre=L;                    //让pre指向链表的头结点
        k=0;                      //将k初始化为0
        while(pre!=NULL&&k<i-1)   //循环直到pre指向NULL或者k等于i-1
        {
            pre=pre->next;        //让pre指向下一个结点
            k=k+1;                //将k加1，表示移动了一个位置
        }
        if(!pre)                  //如果pre为空，表示插入位置不合理
        {
            printf("插入位置不合理!");
            return ERROR;
        }
        s=(Node*)malloc(sizeof(Node));     //动态分配一个结点的内存空间，并让s指向它
        s->data=e;                            //将e的值赋给s所指结点的数据域
        s->next=pre->next;                     //将s所指结点链接到pre所指结点的后面
        pre->next=s;                         //将pre所指结点链接到s所指结点的前面
        return OK;
    }

①先寻找第i-1个节点

while(pre!=NULL && k<i-1)   //循环直到pre指向NULL或者k等于i-1
        {
            pre=pre->next;        //让pre指向下一个结点
            k=k+1;                //将k加1，表示移动了一个位置
        }
        if(!pre)                  //如果pre为空，表示插入位置不合理
        {
            printf("插入位置不合理!");
            return ERROR;
        }

②申请新结点

s=(Node*)malloc(sizeof(Node));     //动态分配一个结点的内存空间，并让s指向它
        s->data=e;                            //将e的值赋给s所指结点的数据域

③ 插入节点

s->next=pre->next;                     //将s所指结点链接到pre所指结点的后面
        pre->next=s;                         //将pre所指结点链接到s所指结点的前面

图解：

![9fec5f6a447d4fe9896472a16dc74ffc.jpeg][]

（2）删除操作

（删除第 i 个结点）

int DelList(LinkList L,int i)
    {
        Node *pre,*r;              //定义两个指针变量，pre指向删除位置的前一个结点，r指向删除的结点
        int k;                     //定义一个整型变量，用于记录当前遍历到的结点的位置
        pre=L;                    //让pre指向链表的头结点
        k=0;                      //将k初始化为0
        while(pre->next!=NULL && k<i-1)   //循环直到pre的下一个结点为空或者k等于i-1
        {
            pre=pre->next;                //让pre指向下一个结点
            k=k+1;                        //将k加1，表示移动了一个位置
        }
        if(!(pre->next))                //如果pre的下一个结点为空，表示删除位置不合理
        {
            printf("删除结点的位置i不合理!");
            return ERROR;
        }
        r=pre->next;                      //让r指向pre的下一个结点，即要删除的结点
        pre->next=pre->next->next;        //将pre所指结点链接到r所指结点的后面，即跳过r所指结点
        free(r);                 //释放r所指结点的内存空间
        printf("成功删除结点!");
        return OK;
    }

① 寻找第 i-1个结点

while(pre->next!=NULL && k<i-1)   //循环直到pre的下一个结点为空或者k等于i-1
        {
            pre=pre->next;                //让pre指向下一个结点
            k=k+1;                        //将k加1，表示移动了一个位置
        }
        if(!(pre->next))                //如果pre的下一个结点为空，表示删除位置不合理
        {
            printf("删除结点的位置i不合理!");
            return ERROR;
        }

②删除并释放 i 结点

r=pre->next;                      //让r指向pre的下一个结点，即要删除的结点
        pre->next=pre->next->next;        //将pre所指结点链接到r所指结点的后面，即跳过r所指结点
        free(r);                 //释放r所指结点的内存空间

图解：

![5f904bdfafe449cbb873dc0bfb27cdee.jpeg][]

总结：

插入操作的循环条件 while(pre!=NULL && k<i-1) 跟删除操作循环条件 while(pre->next!=NULL && k<i-1) 不一样的原因是：假设当前表中有元素m个，插入一个元素就是m+1个 ，即可以在表的末尾插入元素。删除操作只能删除当前的m个元素。

[696516018acb47fc916c31f673d46891.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c571d7fc959a43fe8e944d3b3a674109.png
[fc1b513953064eda89c14b1e27d36bd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6679ec45c2864a8198b2e23d57b7b337.png
[666d50e60239471ebba0da4f902ed662.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/ce53cdcad270497bb1669127a4d19fed.png
[858eebddfe4a43a8bd27c5b9cfb329c3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/7aaa17e9a3274005ae95041b9c4617ac.png
[ce94d55f4abd4e6cade75e9151893be7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8492aa4d30964a7885bff2b40bb848d2.png
[a7494a8418d5428db966c4e20c5e13e1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/0a8981b7300542b0b9851977ec073b7f.png
[59cdbdd72a4a48f6bf3c3cdb0b9cb096.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/4f6f93fd4dff4cbab08f6f5838b6d134.png
[9fec5f6a447d4fe9896472a16dc74ffc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c0b11958cb724216aff9c5acb1756d0b.png
[5f904bdfafe449cbb873dc0bfb27cdee.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/96618a5639794794a3c56e4eff63c9eb.png