数据结构：链表

链表顺序表与链表的比较数据结构：链表全文共66页，当前为第1页。链表（LinkedList）链接表是线性表的链接存储表示单链表静态链表循环链表双向链表数据结构：链表全文共66页，当前为第2页。单链表(SinglyLinkedList)特点

每个元素(表项)由结点(Node)构成。线性结构

结点可以连续，可以不连续存储结点的逻辑顺序与物理顺序可以不一致表可扩充datalinka0a1a2a3a4first数据结构：链表全文共66页，当前为第3页。单链表的存储映像free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构数据结构：链表全文共66页，当前为第4页。单链表的定义typedefcharListData;typedefstructnode{

//链表结点

ListDatadata;

//结点数据域

structnode*link;

//结点链域}ListNode;typedefListNode*LinkList;//链表头指针LinkListfirst;//链表头指针数据结构：链表全文共66页，当前为第5页。单链表中的插入与删除插入

第一种情况：在第一个结点前插入

newnode->link=first;first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst数据结构：链表全文共66页，当前为第6页。

(插入前)(插入后)

第二种情况：在链表中间插入

newnode->link=p->link; p->link=newnode；newnodepnewnodep数据结构：链表全文共66页，当前为第7页。

第三种情况：在链表末尾插入

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodenewnodepp数据结构：链表全文共66页，当前为第8页。intInsert(LinkList&first,intx,inti){//在链表第

i个结点处插入新元素

x

ListNode*p=first;intk=0;while(

p!=NULL&&k<i-1)

{p=p->link;k++;

}

//找第i-1个结点

if(p==NULL&&first!=NULL){

printf(“无效的插入位置!\n”);return0;}ListNode*newnode=

//创建新结点

(ListNode*)malloc(sizeof(ListNode));

数据结构：链表全文共66页，当前为第9页。

newnode->data=x;if(first==NULL||i==1){

//插在表前

newnode->link=first;

first=newnode;}else{

//插在表中或末尾

newnode->link=p->link;p->link=newnode;}

return1;

}数据结构：链表全文共66页，当前为第10页。删除第一种情况:删除表中第一个元素第二种情况:删除表中或表尾元素在单链表中删除含ai的结点ai-1ai-1aiaiai+1ai+1pq删除前删除后数据结构：链表全文共66页，当前为第11页。intDelete(LinkList&first,inti){//在链表中删除第i个结点

ListNode*p,*q;if(i==1)

//删除表中第

1个结点

{q=first;first=first->link;}else{

p=first;intk=0;

//找第i-1个结点

while(p!=NULL&&k<i-1)

{p=p->link;

k++;

}

数据结构：链表全文共66页，当前为第12页。

if(p==NULL||p->link==NULL){

printf(“无效的删除位置!\n”);return0;

}else{

//删除表中或表尾元素

q=p->link;

//重新链接

p->link=q->link;}}free(q);

//删除q

return1;

}数据结构：链表全文共66页，当前为第13页。带头结点的单链表头结点位于表的最前端，本身不带数据，仅标志表头。设置头结点的目的是统一空表与非空表的操作简化链表操作的实现。非空表 空表0ana1firstfirst0数据结构：链表全文共66页，当前为第14页。在带头结点的单链表第一个结点前插入新结点

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp数据结构：链表全文共66页，当前为第15页。

q=p->link;p->link=q->link;deleteq;

从带头结点的单链表中删除第一个结点firstfirst(非空表）first0first(空表）0pqpq数据结构：链表全文共66页，当前为第16页。前插法建立单链表从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端直到读入结束符为止。firstnewnodefirstnewnode00数据结构：链表全文共66页，当前为第17页。LinkListcreateListF(void){charch;ListNode*s;

LinkListhead=//建立头结点(LinkList)malloc(sizeof(ListNode));head->link=NULL;while((ch=getchar())!=‘\n’){s=(listNode*)malloc(sizeof(ListNode));s->data=ch;

//建立新结点

s->link=head->link;

//插入到表前端

head->link=s;

}

returnhead;}

数据结构：链表全文共66页，当前为第18页。后插法建立单链表每次将新结点加在链表的表尾；设置一个尾指针r，总是指向表中最后一个结点，新结点插在它的后面；尾指针r初始时置为指向头结点地址。00newnodefirstnewnode00rrrr数据结构：链表全文共66页，当前为第19页。LinkListcreateListR(void){charch;

LinkListhead=//建立表头结点(LinkList)malloc(sizeof(ListNode));ListNode*s,*r=head;

//r指向表尾

while((ch=getchar())!=‘\n’){s=(listNode*)malloc(sizeof(ListNode));s->data=ch;

//建立新结点

r->link=s;r=s;

//插入到表末端

}

r->link=NULL;

//表收尾

returnhead;}

数据结构：链表全文共66页，当前为第20页。firstqfirstfirstqqfirsta0a1a1a2a2a2单链表清空数据结构：链表全文共66页，当前为第21页。单链表清空voidmakeEmpty(LinkListfirst){//删去链表中除表头结点外的所有其他结点

ListNode*q;

while(first->link!=NULL){ q=first->link;first->link=q->link;

//将表头结点后第一个结点从链中摘下

free(q);

//释放它

}

}数据结构：链表全文共66页，当前为第22页。firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3计算单链表长度数据结构：链表全文共66页，当前为第23页。intLength(LinkListfirst){

ListNode*p=first->link;

//检测指针p

指示第一个结点

intcount=0;

while(p!=NULL){

//逐个结点检测

p=p->link;count++;}

returncount;}计算单链表长度数据结构：链表全文共66页，当前为第24页。ListNode

*Find(LinkListfirst,ListData

value

){//在链表中从头搜索其数据值为value的结点

ListNode*p=first->link;

//检测指针

p

指示第一个结点

while(p!=NULL&&p->data!=value)

p=p->link;

returnp;}在单链表中按值查找数据结构：链表全文共66页，当前为第25页。ListNode*Locate(LinkListfirst,inti){//返回表中第i

个元素的地址

if(i<0)returnNULL;

//i值不合理

ListNode*p=first;intk=0;//置于表头

while(p!=NULL&&k<i)

{p

=p->link;k++;}

//找第i个结点

if(k==i)returnp;

elsereturnNULL;//返回第i个结点地址或NULL}在单链表中按序号查找（定位）数据结构：链表全文共66页，当前为第26页。在单链表中插入新结点

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入newnodenewnode插入pppp数据结构：链表全文共66页，当前为第27页。intInsert(LinkListfirst,ListDatax,inti){//将新元素x插入在链表中第i

号结点位置

ListNode*p=Locate(first,i-1);

if(p==NULL)return0; //不插入

ListNode*newnode=//创建新结点

(ListNode*)malloc(sizeof(ListNode));newnode->data=x;

newnode->link=p->link;//链入

p->link=newnode;return1;

//插入成功，函数返回1}在单链表中插入新元素数据结构：链表全文共66页，当前为第28页。在单链表中删除一个结点

q=p->link;p->link=q->link;deleteq;

first0firstpppqqq数据结构：链表全文共66页，当前为第29页。intdelete(LinkListfirst,inti){//将链表第i

号元素删去

ListNode*p=Locate(first,i-1);

//寻找被删结点的前驱结点

if(p==NULL||p->link==NULL)

return0; //不删除

ListNode*q=p->link;

//被删结点地址

p->link=q->link;

//摘下被删结点

free(q

);

//释放

returnl;}在单链表中删除一个结点数据结构：链表全文共66页，当前为第30页。【例】单链表求和函数

typedefintListData;

intsum(LinkListls){

ListNode*p=ls->link;intretvalue=0;while(p!=NULL){retvalue+=p->data;//

累加

p=p->link;}

returnretvalue; }数据结构：链表全文共66页，当前为第31页。静态链表结构数据结构：链表全文共66页，当前为第32页。静态链表定义constintMaxSize=100;//静态链表大小typedefintListData;typedefstructnode{//静态链表结点

ListDatadata;

intlink;}SNode;typedefstruct{//静态链表

SNodeNodes[MaxSize];intnewptr; //当前可分配空间首地址}SLinkList;数据结构：链表全文共66页，当前为第33页。将链表空间初始化voidInitList(SLinkListSL){SL.Nodes[0].link=-1;SL.newptr=1;//当前可分配空间从1开始

//建立带表头结点的空链表

for(inti=1;i<MaxSize-1;i++)SL.Nodes[i].link=i+1;

//构成空闲链接表

SL.Nodes[MaxSize-1].link=-1;

//链表收尾}数据结构：链表全文共66页，当前为第34页。在静态链表中查找具有给定值的结点intFind(SLinkListSL,ListDatax){

intp=SL.Nodes[0].link;

//指针p指向链表第一个结点

while(p!=-1)

if(SL.Nodes[p].data!=x)p=SL.Nodes[p].link;elsebreak;

//逐个结点检测查找具有给定值的结点

returnp;}数据结构：链表全文共66页，当前为第35页。在静态链表的表尾追加一个新结点intAppend(SLinkListSL,ListDatax){

if(SL.newptr==-1)return0;//追加失败

intq=SL.newptr;//分配结点

SL.newptr=SL.Nodes[SL.newptr].link;SL.Nodes[q].data=x;SL.Nodes[q].link=NULL;

intp=0;//查找表尾

while(SL.Nodes[p].link!=-1)p=SL.Nodes[p].link;SL.Nodes[p].link=q;//追加

return1;}数据结构：链表全文共66页，当前为第36页。在静态链表中查找第

i个结点intLocate(SLinkListSL,inti){

if(i<0)return

-1;//参数不合理

intj=0,p=SL.Nodes[0].link;while(p!=-1&&j<i){

//循链查找第i号结点

p=SL.Nodes[p].link;

j++;}

if(i==0)return0;

returnp;}数据结构：链表全文共66页，当前为第37页。在静态链表第

i个结点处插入一个新结点intInsert(SLinkListSL,inti,ListDatax){

intp=Locate(SL,i-1);if(p==-1)return0;//找不到结点

intq=SL.newptr;//分配结点

SL.newptr=SL.Nodes[SL.newptr].link;SL.Nodes[q].data=x;SL.Nodes[q].link=SL.Nodes[p].link;SL.Nodes[p].link=q;//插入

return1;}数据结构：链表全文共66页，当前为第38页。在静态链表中释放第

i个结点intRemove(SLinkListSL,inti){

intp=Locate(SL,i-1);if(p==-1)return0;//找不到结点

intq=SL.Nodes[p].link;//第i号结点

SL.Nodes[p].link=SL.Nodes[q].link;

SL.Nodes[q].link=SL.newptr;//释放

SL.newptr=q;return1;}数据结构：链表全文共66页，当前为第39页。循环链表(CircularList)循环链表是单链表的变形。循环链表最后一个结点的link

指针不为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。数据结构：链表全文共66页，当前为第40页。循环链表的示例带表头结点的循环链表

a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)数据结构：链表全文共66页，当前为第41页。查找成功查找不成功循环链表的查找firstfirst3131484815155757查找15查找25pppppppp数据结构：链表全文共66页，当前为第42页。循环链表的定义typedefcharListData;typedefstructcnode{

//链表结点

ListDatadata;

//结点数据域

structcnode*link;

//结点链域}CircListNode;typedefCircListNode*CircLinkList;//循环链表头指针CircLinkListfirst;//循环链表头指针数据结构：链表全文共66页，当前为第43页。循环链表的查找算法CircListNode

*Find(CircLinkListfirst,ListData

value

){//在链表中从头搜索其数据值为value的结点

CircListNode*p=first->link;

//检测指针

p

指示第一个结点

while(p!=first&&p->data!=value)

p=p->link;

returnp;}数据结构：链表全文共66页，当前为第44页。带尾指针的循环链表rear3148155722

如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。在表尾插入，时间复杂性O(1)

在表尾删除，时间复杂性O(n)

在表头插入，相当于在表尾插入在表头删除，时间复杂性O(1)数据结构：链表全文共66页，当前为第45页。将循环链表链入单链表链头rear1520253010first60657055rear1520253010p60657055first数据结构：链表全文共66页，当前为第46页。双向链表(DoublyLinkedList)双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。双向链表每个结点结构：

双向链表通常采用带表头结点的循环链表形式。前驱方向

后继方向priordatanext数据结构：链表全文共66页，当前为第47页。结点指向

p==p->prior->next==p->next->prior非空表

空表p->priorp->nextppriornextfirstfirst数据结构：链表全文共66页，当前为第48页。双向循环链表的定义typedefintListData;typedefstructdnode{

ListNodedata;//数据

structdnode*prior,*next;//指针}DblNode;typedefDblNode*DblList;//双向链表

数据结构：链表全文共66页，当前为第49页。建立空的双向循环链表voidCreateDblList(DblList&

first){

first=(DblNode*)malloc

(sizeof(DblNode));

if(first==NULL)

{print(“存储分配错!\n”);exit(1);}first->prior=first->next=first;

//表头结点的链指针指向自己}数据结构：链表全文共66页，当前为第50页。计算双向循环链表的长度intLength(DblListfirst){//计算带表头结点的双向循环链表的长度

DblNode*p=first->next;

intcount=0;

while(p!=first)

{p=p->next;count++;

}returncount;}数据结构：链表全文共66页，当前为第51页。查找成功查找不成功双向循环链表的查找firstfirst3131484815155757查找15查找25数据结构：链表全文共66页，当前为第52页。ListNode*Find(DblListfirst,ListDatax){//在双向循环链表中搜索含x的结点,

若找到,//则返回该结点的地址,否则返回表头地址。

DblNode*p=first->next;

while(p!=first&&p->data!=x)p=p->next; returnp;}//也可以在prior(前驱)方向查找,程序类似。数据结构：链表全文共66页，当前为第53页。DblNode*Locate(DblListfirst,inti){

if(i<0)returnfirst;

DblNode*p=first->next;intj=1;

while(p!=first&&j<i)

{p=p->next;j++;}returnp;}//也可以在prior(前驱)方向查找,程序类似。定位：查找第i个结点在链中的位置数据结构：链表全文共66页，当前为第54页。双向循环链表的插入(非空表)firstfirst314815在结点*p

后插入25pp31482515q->prior=p; q->next=p->next;p->next=q;q->next->prior=q;q数据结构：链表全文共66页，当前为第55页。双向循环链表的插入(空表)first在结点*p后插入25pq25q->prior=p; q->next=p->next;

(=first)p->next=q;q->next->prior=q;

(first->prior=q)

firstp数据结构：链表全文共66页，当前为第56页。intInsert(DblListfirst,inti,ListDatax){DblNode*p=Locate(first,i-1);

//指针定位于插入位置

if(p==first&&i!=1)return0;DblNode*q=(DblNode*)malloc(sizeof(DblNode));//分配结点

q->data=x;

q->prior=p; p->next->prior=q;

//在前驱方向链入新结点

q->next=p->next;p->next=q;

//在后继方向链入新结点

return1;}数据结构：链表全文共66页，当前为第57页。删除48双向循环链表的删除firstfirst非空表314815p3115p->next->prior=p->prior;p->prior->next=p->next;数据结构：链表全文共66页，当前为第58页。删除31双向循环