链表、双向链表、循环链表

计算机软件技术基础长春理工大学计算机科学技术学院基础部孙爽滋顺序表优点和缺点优点：逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。缺点：插入和删除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；容易造成存储空间的“碎片”思路(链式存储）：元素可以散落在任何位置，不必相邻让每个元素知道它的下一个元素在哪里我们只需要知道第一个元素的位置插入删除不再需要移动元素而是需要修改元素间的关系123456234561顺序存储结构不足的解决办法链式存储结构特点:1.2.3线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存储：线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。

1.2.3线性表的链式存储结构2.线性链表:定义：线性表的链式存储结构称为线性链表数据域:一部分存放数据元素值

指针域:

存放指针,用于指向该结点的前一个结点或后一个结点线性链表中结点组成：1.2.3线性表的链式存储结构结合C语言：链表就是一组组的数据用链将它连起来，如下图所示。数据1数据2数据5数据3数据4数据链问题是用什么来存放数据，用什么来作为链。解决办法?数据1指针◎数据2指针◎数据3指针◎数据域指针域从上图知，可以定义一个结构，其中一部分存放数据，另一部分存放指向下一数据的指针。这就构成了单链表。…节点每组数据和指针称为链表的一个节点。101.分配内存函数：malloc()——原型在stdlib.h中

1)调用方式

void*malloc(unsignedsize)2)功能在内存中分配size个字节的存储空间，并返回指向分配存储区起始地址的指针；如果不能获得需要的存储空间，将返回空指针。

注：在把返回值赋给具有一定数据类型的指针变量时，应对返回值作强制类型转换。结合C语言：跟链表相关的函数11例：为1000个字符动态分配内存

char*base_ptr;base_ptr=(char*)malloc(1000);结合C语言：12structdata{intno;charname[10];intscore;};structdata*p;p=(structdata*)malloc(sizeof(structdata));

if(p==NULL){puts(“outofmemory\n”);exit(1);}结合C语言：13①(structdata*)返回结构指针②sizeof(structdata)通知malloc分配足够的内存给structdata的每一个结构成员③p接受返回的指针④如果内存heap区已满，则返回NULL⑤exit()函数被定义在process.h或者stdlib.h中

0:程序正常终止非0：程序非正常终止结合C语言：142.calloc()函数原型在stdlib.h中

1)调用方式

void*calloc(unsignedn,unsignedsize)2)功能分配n个具有size个字节的存储空间，并返回一个指向被分配内存起始地址的指针；如果没有足够的内存满足要求，则返回一个空指针结合C语言：153.free()函数原型在stdlib.h中

1)调用方式

voidfree(void*ptr)2)功能释放由ptr指向的内存空间，并将它返回给堆注：free()只能由前面动态内存分配函数中所分配地址的那个指针来调用结合C语言：头结点是在链表的起始结点之前附加的一个结点.带头结点的单链表123∧head123∧head头结点单链表带头结点的单链表∧head空表∧head空表head->next==Null头结点有两个优点：⑴由于起始结点的位置被存放在头结点的指针域中，故在链表的第一个位置上的操作与表中其他位置上操作一致，无须进行特殊处理。⑵无论链表是否为空，其头指针都是指向头结点的非空指针，故此空表和非空表的处理也统一了。起始结点structNode{intdata;structNode*next;};structNode*head;head->next(head->next)->data起始结点的地址6链表的访问structNode*p;p=head->next;head63120pp=p->next;pp=p->next;pp->next==NULL表明p到达表尾结点p=p->next;p=0空指针对于线性链表，可以从头指针(head)开始，沿各结点的指针扫描到链表中的所有结点。*将当前结点的元素值赋给xx=p->data;ListNode*p;intx;x6pListNode*p;intx;p*将x赋给当前结点，修改当前结点的元素值x=10;p->data=x;1021建立带头节点的单链表

尾插法建立单链表（n个节点）特点：头指针固定不变，新产生的结点总是链接到链表的尾部。操作步骤：（1）进行定义：head为头指针，tail为尾指针，p为结点。（2）建立头节点head=(structnode*)malloc(sizeof(structnode));

head->next==NULL;tail=head;（3）生成新结点（p），输入数据

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

scanf(“%d”,&p->data);p->next=NULL;（4）链接到表尾tail->next=p;tail=p;（5）重复（3）~（4），继续建立新结点，直到n个节点为止。当表空时，头指针和尾指针同时指向头节点22structnode{charname[10];intwage;structnode*next;};23定义头指针、尾指针、新节点指针初始化（带头节点）开辟新节点节点个数<nYN数据赋给新节点新节点链接到表尾重新置表尾建立带头结点链表的代码(后插法)//建立n个结点单链表,返回头指针//定义头、

尾、p指针structnode*CreatList(intn){inti;stuctnode*head,tail,p;head=(structnode*)malloc(sizeof(structnode));head->next=NULL;tail=head;for(i=0;i<n;i++){p=(structnode*)malloc(sizeof(structnode));scanf(“%d”,&p->data);p->next=NULL;tail->next=p;tail=p;}returnL;}//建立头结点//用tail标记链表尾部//生成新结点//输入结点的数据域//链接到表尾//更新尾指针//返回链表的头指针structnode{charname[20];structnode*next;};structnode*head;typedefstructnode{charname[20];structnode*next;}LinkList;LinkList*head;新的类型名代换旧的类型名，也就是说：LinkList等价与structnode3.单链表:

定义：由n个结点链接，且每个结点中只包含一个指针域的链表。例：线性单链表(A,B,C,D,E,F)ABCDEhead

F1.2.3线性表的链式存储结构逻辑结构存储结构3.单链表:

(1)单链表插入：增加新结点,修改链接指针后插结点在指针p所指结点之后插入一个指针s所指的结点修改p和s所指结点的指针域的指针即可1.2.3线性表的链式存储结构插入步骤修改s指针域,使其指向p结点的后继结点:snext=pnextp

B

C

Xs

A修改p指针域,使其指向新结点s:pnext＝s考虑上述两步骤若颠倒会怎样？插入步骤修改s指针域,使其指向p结点的后继结点:snext=pnextp

B

C

Xs

A修改p指针域,使其指向新结点s:pnext＝s后面的结点都将从链表中脱离它们占用着内存空间，程序却找不到它们了3.单链表:

(2)单链表删除：不需要移动元素,仅修改指针链接删除结点删除p指向的结点只修改p(被删除结点)的前驱结点的指针域即可1.2.3线性表的链式存储结构删除步骤修改q结点指针域qnext＝pnextCpBA删除前删除后qpCBAfree(p);先找到p的前驱结点qqnext＝qnextnext存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素时间性能查找顺序存储结构O(1)单链表O(n)插入和删除顺序存储结构需要平均移动表长一半的元素，时间为O(n)单链表在找出某位置的指针后，插入和删除的时间仅为O(1)空间性能顺序存储结构需要预分配存储空间，分大了，浪费，分小了，易发生溢出单链表不需要预分配一整块存储空间，只要有就可以分配，元素个数也不受限制单链表结构和顺序存储结构的比对：假设我们的校园只有单行道保安沿这条路线巡逻，需要查遍所有地点。有一天，保安先从主教出发，想把以上地点走一遍，此时主管告诉他，不行，你必须从主校门开始走。。。主校门办公楼图书馆体育馆机电楼主教逸夫楼北门事实上，把主校门和北门连接起来，形成一个环路，就解决了这个问题。单链表的尴尬4.循环链表特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。

带头结点的循环链表1.2.3线性表的链式存储结构优点：从表中任一结点出发均可找到表中其它结点。对带头结点的单循环链表head为空的判定条件是

head->next=head带头结点的空循环链表例：假设长度大于1的循环单链表中，既无头结点也无头指针，p指向该链表中某一结点，编写一个算法删除该结点的前驱结点。单链表只能从头结点开始遍历整个链表，而循环单链表则可以从表中任意结点开始遍历整个链表。...a1a2an-1a0ps=p;while(s.next.next!=p)s=s.next;如何寻找前驱结点？s指向该结点的前驱结点的前驱结点ss.next=p;删除该结点的前驱结点思考：对于单链表而言，连接两个单链表应该如何实现？...a0head1a1an-1^...b0head2b1bn-1^currentcurrent.next=head2.next对于循环单链表呢？...a0head1a1an-1...b0head2b1bn-1pp=head1.next;head1.next=head2.next.next;head2.next=p;...a0head1a1an-1...b0head2b1bn-1p主校门办公楼图书馆体育馆机电楼主教逸夫楼北门终于有一天，保安在感叹：如果我们有双行道该多好啊！双向链表（doublelinkedlist）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。01/02/2023395.双向链表定义：在双向链表中，每个结点有两个指针域，next指向后继结点，prior指向前趋结点。

datapriornext结点构成：1.2.3线性表的链式存储结构作用：可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找的不足。head......ana2a1nextprior对指向双向链表任一结点的指针p，有下面的关系：p->next->priou=p->priou->next=ppnextpriouspriousnext

设对象引用p表示双向链表中的第i个结点，则p.next表示第

个结点，p.next.prior表示第

个结点，即p.next.prior==p；同样地，p.prior表示第

个结点，p.prior.next仍表示第

个结点，即p.prior.next==p。双向链表的关系i+1ii-1i5.双向链表(1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。p插入前cbax待插入的结点:q1.2.3线性表的链式存储结构cbaxqp①p结点作为q结点的前驱:q->prior=p；②p结点的后继作为q结点的后继:q->next=p->next；③q结点作为p结点的后继结点的前驱结点:p->next->prior=q④q结点作为p结点的后继:p->next=q；(p的后继指向新结点q)②③④①确定新结点q的前驱和后继5.双向链表p删除前cba(2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。1.2.3线性表的链式存储结构p①②

①

p的后继结点作为p结点前驱结点的后继(ac)

②

p的前驱结点作为p结点后继结点的前驱(ac)p->prior->next=p->next；p->next->prior=p->prior；free(p)；cba习题讲解1.线性表的顺序存储结构和线性表的链式存储结构分别是______。

A.顺序存取的存储结构、顺序存取的存储结构

B.随机存取的存储结构、顺序存取的存储结构

C.随机存取的存储结构、随机存取的存储结构

D.任意存取的存储结构、任意存取的存储结构2.在单链表中，增加头结点的目的是______。

A.方便运算的实现

B.使单链表至少有一个结点

C.标识表结点中首结点的位置

D.说明单链表是线性表的链式存储实现BA3用链表表示线性表的优点是______。

A.便于插入和删除操作

B.数据元素的物理顺序与逻辑顺序相同

C.花费的存储空间较顺序存储少

D.便于随机存取4.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为200,则第12个元素的存储地址是_______.

A.248B.247C.246D.244AD5.下列对于线性链表的描述中正确的是______。(05.4月）A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的A6.线性表是（）

A.一个有限序列，可以为空B.一个有限序列，不能为空

C.一个无限序列，可以为空D.一个无限序列，不能为空7．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）

A.（n+1）/2B.n/2C.nD.n+18.一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)

位置插入一个新元素时，需要从后面向前依次后移（）个元素。A.n-iB.n-i+1C.n-i-1D.iACB9.设单链表中指针p指向结点ai,若要删除ai之后的结点（若存在），则需修改指针的操作为（）。

A.p->next=p->next->next B.p=p->next C.p=p->next->next D.next=p10.设单链表中指针p指向结点ai,指针q指向将要插入的新结点

x，则当x插在链表中两个数据元素ai和ai+1之间时，只要先修改q->next=p->next，后修改（）即可。

A.p->next=q B.p->next=p->next->next C.p->next=q->nextD.q->next=null11.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。

A.1 B.2 C.3 D.4AAB12.不带头结点的单链表L为空的判定条件是（）。

A.L==NULL B.L->next==NULL C.L->next==L D.L!=NULL13．带头结点的单链表L为空的判定条件是（）。

A.L==NULL B.L->next==NULL C.L->next==L D.L!=NULL14.在一个带有头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A.2 B.3 C.4 D.6ABC15.在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（）

A.p->prior B.p->next C.p->next->next D.p->prior->prior16.线性表采用链式存储时，其地址（）

A.必须是连续的 B.一定是不连续的

C.部分地址必须是连续的 D.连续与否均可以BD17.下列叙述中正确的是：(2010年9月国二）

A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的

B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

D）上述三种说法都不对

B1.在一个单链表中删除指针p所指向结点时，应执行一下操作：

q=p->next;p->data=p->next->data;p->next=_____；

free(q);p->next->nextpqABBC2.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把_____的值赋给q->next，然后把_____的值赋给p->next。p->nextq3.假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针p所指向的新结点时，首先执行_____赋值操作，然后执行__

___赋值操作。p->next=headhead=pheadp4.在一个单链表中删除指针p所指向结点的后继结点时，需要把_____的值赋给p->next指针域。p->next->next5.在_____链表中，既可以通过设定一个头指针也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。循环6.在一个带有头结点的双向循环链表中的p所指向的结点之前插入一个指针s所指向结点时,可执行如下操作：

(1)s->prior=_____；

(2)p->prior->next=s; (3)s->next=_____; (4)p->prior=_____;p->priorpsps7.线性表的长度是指_______。线性表中包含数据元素的个数8.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_______和_______。单链表、双链表9.循环单链表与非循环单链表的主要不同是循环单链表的尾结点指针______，而非循环单链表的尾结点指针______。指向链表头节点指向空10.访问单链表中的结点，必须沿着______依次进行。指针域11.在双向链表中，每个结点有两个指针域，一个指向______，另一个指向______。前驱节点后续节点12.在一个双向链表中删除指针p所指向的结点时，需要对

p->next->prior指针域赋值为______。p->prior13.设head为单循环链表L的头结点，则L为空表的条件是______。head->next=head14.在一个长度为n的顺序表中的删除第i个元素（0≤i≤n-1），需要向前移动______个元素。n-i15.线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是

。(n-1)/216.一含N个元素的顺序表，若在第i个元素之前插入一个元素，需移动

个元素。n-i+117.从链表种删除q结点之后的p结点，语句为：q->next=

。

p->next18.链表中每个结点包含两部分内容，一部分为