计算机软件技术基础-课件 03ch2(2)-DS 线性表的链式存储及运算

2.1.3线性表的链式存储及运算1.

单链表2.

双向链表线性表要点回顾线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或1:1存储结构：顺序、链式运算：修改、插入、删除3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找快O(1)缺点：插入、删除慢O(n)1.单链表(1)链式存储结构的特点链表(LinkedList)是指用一组任意的存储单元来存储线性表中的数据元素。这组存储单元即可以是连续的，也可以是不连续的。逻辑上相邻的数据元素在物理上不一定相邻，只能顺序(依次)访问。如何实现？ 在存储每个结点值的同时，还必须存储指示其后继或前驱结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。(1)链式存储结构的特点链表中的结点结构：数据域+指针域。链表的样式：指针数据指针数据指针或样式：数据域：存储数据元素信息指针域：存储直接后继或者直接前驱的存储位置链表存放示意图如下：a1heada2/\an……说明：链表中的每一个结点只有一个指向后继的指针，这种链表称为单链表（SingleLinkedList)。单链表中每个结点的存储地址是存放在其前驱结点的指针域中。起始结点（表头结点）无前驱，故应设表头指针（头指针）HEAD指向起始结点。终点元素无后继，它的指针域为空，即NULL（图示中也可用^表示)。链表存放示意图datanext结点示意图例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）讨论1：每个存储结点包含两部分：数据域和

。讨论2：在单链表中，除了首结点外，任一结点的存储位置由

指示。其前驱结点的指针域的值指针域(2)与链式存储有关的术语：1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：

结点只有一个指针域的链表，称为单链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……head循环链表示意图：4）头指针、头结点和首元结点

示意图如下：头指针头结点首结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点或为首结点）（即线性表的第一个元素）的特殊指针；首结点是指链表中存储线性表第一个数据元素a1的结点；头结点是在链表的首结点之前附设的一个结点，其数据域内可以不存储任何信息（也可存放线性表的长度等附加信息）。（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：一个线性表的逻辑结构为：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①

无头结点②

有头结点上例链表的逻辑结构示意图有以下两种形式：答：讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点讨论1.在链表中设置头结点有什么好处？讨论3.头结点的数据域内装的是什么？头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。答：讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数据类型。答：什么是结构类型？如何书写表达？——补充C语言内容

头结点的数据域H①类型定义和变量说明可以合写为：typedefstruct

node

//structnode是自定义结构类型名称{char

data;//定义数据域的变量名及其类型struct

node

*next;//定义指针域的变量名及其类型}SLNODE;

//SLNODE等价于structnodeSLNODE

test，*head;//test变量是structnode结构类型,*head是node结构类型的头指针//以26个字母的链表为例，每个结点都有两个分量：字符型指针型假设某个结点用变量test表示，其中两个分量分别用data和*next表示，则：*nextdatatest补充：结构类型的C语言表示法补充：结构类型的C语言表示法②对于指向结构变量test首地址的指针，还可说明为：

SLNODE

test

,*p,*q;

③每个结点的分量如何表示？*nextdatatestp方式1：直接用

test.data＝'a'；

test.next=q方式2：先让指针变量p指向该结点的首地址，然后用：

p->data='a';p->next=q;方式3：先让指针变量p指向该结点的首地址，然后用：

(*p).data='a'；(*p).next＝q‘a’‘b’qp设p为指向链表的第i个元素的指针,则第i个元素的数据域写为

，指针域写为

。p->dataai的值p->nextai+1的地址练习：对于单链表结点结构的抽象描述:typedefstructnode{ElemTypedata;//数据域

structnode*next;//指针域}SLNODE;数据元素之间的相对关系是由指针域所指示的，由链建立的顺序必须与数据元素的逻辑次序一致，而结点在存储器中的物理位置可以是任意的。对比：关于顺序表的抽象定义：typedefstructSqnode{ElemTypedata[MAXNUM];//表长（特指元素个数）intLast;//表当前存储容量（字节数）}SqList;补充：结构类型的C语言表示法④三个有用的库函数（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度；malloc(m)

—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)

——释放指针p所指变量的存储空间，即彻底删除一个变量。问1：自定义结构类型结点的长度m是多少？问2：结构变量的首地址(指针p）是多少？问3：怎样删除结构结点？*nextdata长度为m字节pm＝sizeof(SLNODE)p＝(SLNODE*)malloc(m)free(p)只能借助其指针删除！

单链表的实现(1)单链表的定义及其初始化

(2)单链表的建立和输出(3)单链表的访问(4)单链表的插入(5)单链表的删除(1)单链表的定义及其初始化单链表的定义：n个结点由指针链组成一个链表。其结点只有一个指针域的链表，称为单链表或线性链表；链表是由一个个结点构成的，结点定义如下：typedefstructnode{

ElemTypedata;//数据域

structnode*next;//指针域

}SLNODE;定义头指针变量：

structnode*h;或者SLNODE*h这样定义一个structnode类型的指针变量之后，系统并没有为它分配内存单元。这需要通过动态申请内存单元来存放结点。C语言中提供的malloc(n)可以完成此功能。由于一个空的单链表没有一个结点，故头结点(或头指针)指向为空NULL。具体操作如下：h=(SLNODE*)malloc(sizeof(SLNODE));h->next=NULL;执行后的逻辑示意图如上图所示。

单链表的初始化^空表h(2)单链表的建立实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将其地址存放在相应结点的指针域中。假设线性表中结点的数据类型是字符型，我们逐个输入这些字符型的结点，并以特殊字符(例如“\n”)为输入结束标记。动态地建立单链表的常用方法有如下两种：头插法建表尾插法建表babaxPPs在P所指向的结点之后插入新的结点xs单链表的插入关键语句：s->next=P->next;P->next=s;∧HH∧a1Hsa2该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。关键语句：

s->next=H->next;H->next=s;头插法建表s∧a1SLNODE*createfromHead(){ SLNODE*head;SLNODE*s; ElemTypex; head=(SLNODE*)malloc(sizeof(SLNODE));x=get_data();while(x!=-1）{s=(SLNODE*)malloc(sizeof(SLNODE));s–>data=x;s–>next=head->next;

head->next=s;x=get_data();} returnhead}头插法建表head->next=NULL;头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。如何实现？该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。尾插法建表关键是要保存尾结点（最后一个结点）的位置。尾插法建表∧HrHq新结点头指针头结点a1∧增加一个结点Ha1b2∧q新结点rr（始终指向尾结点）关键语句：r->next=q;r=q;SLNODE*createfromRear(){SLNODE*head;SLNODE*r,*q; ElemTypex; head=(SLNODE*)malloc(sizeof(SLNODE)); r=head;

head->next=NULL;x=get_data();while(x!=-1） {q=(SLNODE*)malloc(sizeof(SLNODE));

q–>data=x;r–>next=q; r=q;/*r永远指向链表的最后一个结点*/x=get_data();}

r->next=NULL;

//将最后一个结点的next链域置为空returnhead;}尾插法建表特别容易忘记！！//带头结点SLNODE*createfromRear2(){SLNODE*head; SLNODE*r,*q; ElemTypex;

head=NULL; r=head;x=get_data();while(x!=-1） {q=(SLNODE*)malloc(sizeof(SLNODE));

q–>data=x;

if(head==NULL){head=q;r=head;}//新结点插入空表

else

r–>next=q; r=q;/*r永远指向链表的最后一个结点*/x=get_data();}

if(r!=NULL) r->next=NULL;

//将最后一个结点的next链域置为空returnhead;}尾插法建表不带头结点头结点的用途：对首结点进行统一的处理；对空表、非空表进行统一的处理。voiddisplay(SLNODE*head)/*字母链表的输出*/{SLNODE*p;p=head;/*只要没到最后一个元素，就不停地“顺藤摸瓜”输出*/while(p->next!=NULL)/*存在头结点*/{p=p->next;printf("%c",p->data);}

}讨论：要统计链表中数据元素的个数，该如何改写？

sum++;单链表的输出(3)单链表的访问思路：要找到第i个数据元素，关键是要先找到指向该结点的指针p即可。难点：单链表中想访问第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取。核心语句：j=0;p=head;WHILE(p->next!=NULL&&j<i){p=p->next;j++;}if(p!=NULL&&j==i)

return

(p->data);eslereturn(-1);}在链表中插入一个元素的示意图如下：(4)单链表的插入babax∧anaia1a2ppai-1xLs∧anaia1a2pai-1LInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/

s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/s->data=x;s->next=p->next;p->next=s;returnOK;}s(4)单链表的插入∧anaia1a2pai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/

s->data=x;

s->next=p->next;p->next=s;returnOK;}s(4)单链表的插入∧anaia1a2pai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/s->data=x;

s->next=p->next;p->next=s;returnOK;}s(4)单链表的插入∧anaia1a2ai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/s->data=x;s->next=p->next;

p->next=s;returnOK;}(4)单链表的插入ps思考：如何在p所指向的结点之前插入新的结点？(5)单链表的删除思想方法

删除运算是将表的第i个结点（ai）删去。

具体步骤：（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前驱结点ai-1的指针域中）（2）令ai-1的指针域(p-＞next)指向ai的直接后继结点（即把ai从链上摘下）（3）释放结点ai的空间。单链表的删除删除步骤（即核心语句）：q=p->next;//保存b的指针，靠它才能指向cp->next=q->next;//a、c两结点相连free(q)；//删除b结点，彻底释放在链表中删除某元素的示意图如下：cabpp->next(p->next)->next××DelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}

(5)单链表的删除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;

if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}q(5)单链表的删除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}(5)单链表的删除ai-1a1aiai+1LpqDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}

(5)单链表的删除ai-1a1aiai+1LpqDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/

p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}

(5)单链表的删除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/

free(q);}/*删除并释放结点*/}(5)单链表的删除intDelete_LinkList(SLNODE*HEAD,inti){SLNODE*q,*p;int j=0;q=HEAD;while(q->next!=NULL&&j<i-1){q=q->next;j++;} //使p指向第i-1个结点if((j!=i-1)||(q->next==NULL))return0; //第i个结点不存在，不能删除else{ p=q->next; q->next=p->next; //修改指向关系free(p); //释放被删除结点空间return1;}}ai-1a1aiai+1Lq(5)单链表的删除:删除第i个结点p背景：对于单链表而言，若已知某结点的指针为p，其后继结点的指针则为p->next，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，即找后继的时间性能是O(1)，找前驱的时间性能是O(n)。问题：如何使得找前驱的时间性能达到O(1)？付出空间的代价：每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。双向链表:

在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双链表一般也是由头指针唯一确定的，增加头结点也能使双链表上的某些运算变得方便。

2.双向链表双向链表在非线性结构（如树结构）中将大量使用。2.

双向链表这种指针域包括指向该结点的直接前驱和直接后继的两个指针的存储结构－双向链表此结点结构的C语言描述为：typedefstructnode{elemtypedata;structnode*prior,*next;}DLNODEpriordatanext指向前驱结点的指针域数据域指向后继结点的指针域双向链表的逻辑示意图：ˆ

双向链表结构的对称性若P是指向表中某一结点的指针则有：(P->next)->prior=p(P->prior)->next=p即结点*p的存储位置既存放在其前驱结点*(p->prior)的直接后继指针域中，也存放在它的后继结点*(p->next)的直接前驱指针域中。ana1a2ˆhintDlinkIns(DLNODE*L,DLNODE*P,ElemTypex)如何在P指向结点之前插入新的结点SL123PSx

S->prior=P->prior;

P->prior->next=S;

S->next=P;

P->prior=S;双向链表的前插运算关键步骤∧∧注意：步骤

必须在步骤

和

后面，即确保指针域P->prior使用完之后，再赋新的值。L123intDlinkDel(DLNODE*L,DLNODE*P)//删除指定结点PPP->next->prior=P->prior;P->prior->next=P->next；Free(P)注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。双向链表的删除操作讨论：链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可(P->next=head;)。