线性表的顺序存储与链接存储的基本运算---数据结构

川长思鸟来 2022-04-08 12:00 275阅读 0赞

下面，小编将详细介绍一下线性表的顺序存储与链接存储的基本运算

首先是顺序存储---

顺序存储实现的线性表称为顺序表

顺序表的插入和删除操作

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70][]

插入代码

//顺序表插入元素
    void InsertSeqlist(SeqList L,DataType x,int i)
    //将元素x插入到顺序表L的第i个数据元素之前
    {
        if(L.length==Maxsize)  exit("表已满");
        if(i<1||i>L.length+1)  exit("位置错");//检查插入位置是否合法
        for(j=L.length;j>=i;j--)              //初始j=L.length
            L.data[j]=L.data[j-1];            //依次后移
        L.data[i-1]=x;                        //元素x置入到下标为i-1的位置
        L.length++;                           //表长度+1
    }

删除代码

//顺序表删除元素
    void DeleteSeqList(SeqList L,int i)
    //删除线性表L中的第i个数据结点
    {
        if(i<1||i>L.length)         //检查位置是否合法
            exit("非法位置")；
        for(j=i;j<L.length;j++)     //第i个元素的下标为i-1
            L.data[j-1]=L.data[j];  //依次左移
        L.length--;                 //表长度减一
    }

小结：

顺序表的插入和删除操作相对于来说还是很简单的，在这里，我他们简单的分为三个步骤：

首先，我们需要判断插入和删除是否合法（插入时---如果表已满，不能插入，同时也不能插入到超出表范围的元素；删除时---不能删除超出表范围的元素）；

然后，在相应的位置进行插入或者删除操作；

最后，插入元素的表长度加1，删除元素的表长度减1

结束。

接下来是链接存储---

线性表常见的链式存储结构有单链表、循环链表和双向循环链表

我们先来学习一下单链表

单链表的插入与删除操作

单链表插入

![20181213202551327.png][]

插入代码

//单链表插入运算
    void InsertLinklist(LinkList head,DataType x,int i)
    //在表head的第i个数据元素结点之前插入一个以x为值的新结点
    {
        Node *p,*q;
        if(i==1)  q=head;
        else q=GetLinkList(head,i-1);   //读表元素，找第i个数据元素结点
        if(q==NULL)                     //第i-1个结点不存在
            exit("");
        else{
            p=malloc(sizeof(Node));p->data=x;//生成新结点
            p->next=q->next;                 //新结点链域指向*q的后继结点
            q->next=p;                       //修改*q的链域
        }   
    }

小结：

单链表插入运算，相对于顺序表来说，单链表各个节点在内存中的存储位置并不一定连续，可以通过指针找到本结点的直接后继结点，但是，插入删除操作就相对于来说复杂一些。拿上面的例子来说的话，

1.首先我们需要找到第i个数据元素结点之前的结点q，如果不存在，那么没有插入的位置

2.如果能找到结点q，接下来，我们要生成一个值为x的新结点p

3.p的指针域指向q的直接后继结点，q的指针域指向p

这样，就完成了单链表的插入运算。

值得注意的是，链接操作 p->next=q->next和q->next=p两条语句执行顺序不能颠倒，为什么呢，小编来带你缕一缕，如果先执行q->next=p时，的确将p放到q后面了，但是接下来再执行 p->next=q->nex的时候，此时p->next=q->next中的q->next变成了p， p->next就是p了，这样的话，并不符合逻辑啊，所以顺序不能颠倒。

单链表删除

![201812132028109.png][]

删除代码

//单链表删除运算
    void DeleteLinklist(Linklist head,int i)
    //链式存储——删除结点，删除表head的第i个结点
    {
        Node *q;
        if(i==1) q=head;
        else q=GetLinklist(head,i-1);     //先找待删结点的直接前驱
        if(q!=NULL && q->next!=NULL)      //若直接前驱存在且待删结点存在
        {
            p=q->next;                    //p指向待删结点
            q->next=p->next;              //移出待删结点
            free(p);                      //释放已移出结点p的空间
        }
        else exit("找不到要删除的结点");  //结点不存在
    }

小结：

单链表删除运算

1.首先找到待删结点的直接前驱，若直接前驱存在且待删结点存在；

在这里开始的时候小编有一个问题，删除一个结点就直接判断待删结点是否存在不就好了，为什么还要满足直接前驱结点也存在呢？后来小编明白了，如果这里我们进行删除运算的是一个带头结点的空单链表呢，难道把头结点删掉？

2.p结点指向待删结点；

3.移出待删结点，释放已移出结点p的空间；

4.如果不满足1，表示找不到要删除的结点。

接下来是循环链表

定义：在单链表中，如果让最后一个结点的指针域指向第一个节点就可以构成循环链表。

a、b分别表示带头结点的非空循环链表和空循环链表，头指针是head，这种结底，要找到尾结点可以从头指针head出发扫描所有节点；c、d分别表示带尾指针的非空循环链表和空循环链表，链表没有头指针，只设尾指针rear，首结点表示为rear->next->next（分析：rear->next表示尾结点，rear->next->next表示首结点），首尾结点都能方便的访问。

循环链表只是在单链表的基础上让最后一个结点的指针域指向第一个结点，其他并没有太大的差别，因此，循环链表的插入和删除操作与单链表的插入和删除操作十分类似，这里就不再说啦！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70 1][]

最后，是双向循环链表

定义：在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior（与next类型相同，它指向直接前驱结点），这样每个结点有两个指针。头结点的prior指向最后一个结点，最后一个结点的next指向头结点，由这种结点构成的链表称为双向循环链表。

双向循环链表的对称性可以用下列等式表示：

p= p->prior->next=p->next->prior

双向循环链表的插入：

在p所指结点的后面插入一个新结点\*t,需要修改四个指针：

1.t->prior=p;

2.t->next=p->next;

3.p->next->prior=t;

4.p->next=t;

插入操作如图所示，注意这些语之间的顺序（这里是为什么呢？）

小编发现，如果上面的步骤按照1、3、4、2来进行的话，第一步t->prior=p完全没有问题，第二步p->next=t也没有什么问题，前两个步骤将结点t插入到了结点p的后面，但接下来，进行第三部的时候t->next=p->next，此时，由于第二步的操作，第三部变成了t->next=t，这时，很明显，逻辑出现了问题，用专业一点的话来解释，进行第二部时，丢失了指向原表第i个结点的指针，也就是丢失了原来p->next中的指针。因此，一定要注意这些步骤之间的顺序。小编只是举了一个例子，大家可以尝试下其他的搭配哦！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70 2][]

双向循环链表的删除

设p指向待删结点，删除\*p可以通过下面语句完成：

1.p->prior->next=p->next；

2.p->next->prior=p->prior；

3.free(p)；

1、2两个步骤可以颠倒

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70 3][]

总结：

对于插入和删除操作，在顺序存储和链式存储结构中，各有其优缺点，不能笼统地说哪一个更好，只能根据实际问题具体需要，并对各方面的优缺点加以综合平衡，最终选定使用哪种方法。

从整体考虑，顺序表要预分配存储空间，如果预先分配过大，将造成浪费，若分配的过小，又会发生上溢；单链表不需要预先分配空间，只要内存空间没有耗尽，单链表的节点数就没有限制。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70]: /images/20220405/44be7596b811444593a2f42b40273572.png
[20181213202551327.png]: /images/20220405/0c3d6d9716ef4ce5aad7a74fd186049c.png
[201812132028109.png]: /images/20220405/72e5fa766b6f44cc80b1cb82b42876f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70 1]: /images/20220405/2cc0a2df358f4df5b9a519d826a8822f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70 2]: /images/20220405/0f9eee51fa724d3e80b18612aaab19ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlamluZ2ZhbmcxMjM_size_16_color_FFFFFF_t_70 3]: /images/20220405/9576ad4e6e7042b2acef2be18c490791.png