2.5 单向链表的存储结构和操作

南山隐士 2022年11月20日 20 0

            <script src="/static/js/iframeResizer.contentWindow.min.js?v=1.46.25530-lms-open-university-master-110549c7"></script>

</header>

    <!--<h1>-->

理解单向链表链式存储结构的概念,结合老师的视频讲解和视频动画重点掌握单向链表的插入、删除操作,理解并掌握其关键语句。

1.单向链表的表示

与线性表(a1,a2,…,an)相应的单向链表由n个结点链接而成。每个数据元素对应链表中一个结点,数据元素ai相应的结点在单向链表中称为结点ai。结点ai中的数据域存储数据元素ai,指针域用于存放ai的直接后继元素ai+1相应结点的存储地址。链表中第一个结点的存储位置称为头指针,程序中通常用一个指针变量存储头指针。本章命名该指针变量为head。最后一个数据元素an没有直接后继,所以链表中最后一个结点的指针域存放的是空指针(NULL)。该单向链表如图2-4所示。

图2-4 单向链表示意图

由单向链表的结构可知,只要已知头指针,就可以由前到后逐次访问到链表中任意一个结点。具体做法是由头指针出发,可以访问到第一个结点,由第一个结点的指针域可以访问到第二个结点,…,一般地,由第i个结点的指针域可以访问到第i+1个结点。

2.单向链表的存储结构

在C语言中,可以用“结构变量”存储结点的信息,用“结构指针变量”存储头指针。不失一般性,设线性表的数据元素为整数,则结构体类型定义如下:

3.静态法建立链表

设线性表为(3,5,8,2),在程序中用说明结构变量的方法建立单向链表,并输出链表中各结点的数据元素。(我们为你提供了本题的详细解析、解题步骤及带注解的完整程序,您可以根据需要选择查看。)

  详细解析:

  解题步骤:

带注释的完整程序:

#define NULL 0

void main()

{

NODE a, b, c, d, *head, *p;

a.data=3;

b.data=5;

c.data=8;

d.data=2; /* 对结点的数据域(结构变量的data成员)赋值 */

head=&a; /* a结点的起始地址赋值给头指针变量head */

a.next=&b; /* b结点的起始地址赋值给a结点的指针域(结构变量的next成员)*/

b.next=&c;

c.next=&d;

d.next=NULL; /* d是尾结点,把空指针赋值给d结点的指针域 (结构变量的next成员)*/

p=head; /* 工作指针p指向结点a */

do

{

printf("%d\n",p->data); /* 逐次输出p所指结点的数据 */

p=p->next; /* 使p指向当前所指结点的直接后继结点 */

}while(p!=NULL)

}

在某些情况下,为了操作方便,在线性链表的第一个结点前增加一个附加结点,称它为头结点。头结点的数据域可以不存储任何信息,或者只是存储一些非线性表的数据元素的附加信息。而头结点指针域用以存储第一个结点的指针(地址),如图2-5所示。

图2-5 带头结点的单向链表示意图

若没有特别说明,以下讨论的链表都设定为带头结点的链表。

以上介绍的程序是在程序一开始通过说明结构变量来为链表的结点开辟存储单元。而实际应用中链表通常是一种动态存储结构,结点所占用的存储空间是在程序的执行过程中,根据需要临时开辟的。当链表中需要增加一个结点时,要为新结点申请一个存储空间。当链表中要删除一个结点时,要将已删除的结点的存储空间释放,归还给系统。C语言编译系统的库函数提供了动态分配和释放存储空间的函数。

例如:

NODE *p; /*说明一个指向结点(结构体变量)的指针变量*/

p= (NODE *) malloc ( sizeof (NODE)); /*动态分配一个新结点,并使p指向该结点*/

free(p); /*释放p所指向的结点*/

图2-6 分配、释放存储空间

4.动态法建立链表

建立单向链表的算法是一个动态过程,即从“空表”开始,依次生成各元素的结点,并逐次插入到链表中。根据插入位置的不同,建立链表的方法可以分为尾插法和头插法。尾插法是逐次生成的新结点总是作为当前链表的尾结点插入,头插法是逐次生成的新结点总是作为当前链表的第一个结点插入,算法2-3、算法2-4分别是用尾插法和头插法建立单向链表的算法。

(1)尾插法

算法要点:程序中有3个结构指针变量,其中指针变量head存放头结点的地址,指针变量p用以在动态开辟新结点的存储单元时,存放新的结点的地址,我们称它为“生成指针”。指针q始终指向当前链表的尾结点。当p所指向的新结点被链入表尾后,由q来替代p指向表尾结点,目的是可以通过q访问尾结点,我们称它为“接应指针”。具体步骤为:用p开辟新结点,并由p指向新结点,把p链入表尾,用q指向尾结点,由p继续生成新结点。

【算法2-3】用尾插法建立带头结点且有n个结点的单向链表的算法。

NODE *create1(int n)

/* 对线性表(1,2,.....,n),建立带头结点的单向链表 */

{

   NODE *head,*p,*q;

   int i;

   p=(NODE *)malloc(sizeof(NODE));

   head=p; q=p; p->next=NULL;

   for(i=1;i<=n;i++)

   {

          p=(NODE *)malloc(sizeof(NODE));

            p->data=i;

          p->next=NULL;

          q->next=p;

          q=p;

   }

   return(head);

}

(2)头插法

算法要点:程序中有3个结构指针变量head、p、q,head和p的作用与上例相同,指针q始终指向当前链表的头结点。具体步骤为:用p开辟新结点,利用指针q把p所指向的新结点插入当前链表的头结点之后,作为第一个结点,再由p继续生成新结点。(使用指针变量q是为了与后面的插入算法一致,而就本例可以不设q,而利用head就可以完成q的功能)。

【算法2-4】用头插法建立带头结点且有n个结点的单向链表的算法。

NODE *create2(int n)

/*对线性表(n,n-1,.....,1),建立带头结点的线性链表 */

{

     NODE *head,*p,*q;

     int i;

     p=(NODE *)malloc(sizeof(NODE));

     head=p;

     p->next=NULL;

     q=p;

     for(i=1;i<=n;i++)

     {

        p=(NODE *)malloc(sizeof(NODE));

        p->data=i;

        if(i==1)  

          p->next=NULL;  

        else

        p->next=q->next;

        q->next=p;

      }

     return(head);

}

5.单向链表的插入操作

设已经有一个带头结点的单向链表,头指针为head,要求在单向链表中两个结点a和b之间(也就是在b结点前)插入一个数据元素为x的结点。已知q为指向结点a的指针,在具体实现插入操作时,首先要生成一个数据元素为x的结点,假设p为指向结点x的指针,然后使结点x的指针域指向结点b,操作语句为p->next=q->next;再使结点a的指针域指向结点x,操作语句为q->next=p;结果如图2-11所示:

图2-11 在单向链表中插入结点示意图

Last Updated: 2022/11/20 14:04:22
mysql 设置root远程登录