powerpoint 演示文稿 - 链表的基本概念

9.4链表9.4.1链表的基本概念例：在铁路的中转站，有10个集装箱待运。每个集装箱上有如下五项说明：①箱号 （比如AZ81920）②货物名称 （比如苹果）③重量 （比如10吨）④发货地点 （比如山东）⑤到货地点 （比如广东）12如何在程序中来描述该列火车？如何来描述火车头？如何来描述每一个集装箱？如何来描述各节车厢之间的链接关系？3DX11089玩具5吨从上海到深圳

CY20011电饭锅8吨从上海到湖南

AZ81920花生10吨从山东到广东

…head结点2需要引入一种新的数据结构：链表。链表中的每一个元素称为一个“结点”，每个结点都应该包括两部分：一为用户需要使用的实际数据；二为下一个结点的起始地址。另外，链表还有一个头指针head，指向链表的首结点。结点1结点34如何来实现链表结构？显然要用到结构体数据类型。定义如下的结构体类型：structTrain_tagstructTrain_tag*next;charNum[8];charName[10];intWeight;charFrom[20];charTo[20];数据域指针域59.4.2对链表的操作1.创建静态链表在程序中定义一组结构体变量或一个结构体数组，然后用它们来作为链表的结点，把它们链接成一个链表的形式。优点：不必去关心内存的分配与释放。缺点：需要事先知道链表结点的个数。6DX11089玩具5吨从上海到深圳

CY20011电饭锅8吨从上海到湖南

AZ81920花生10吨从山东到广东NULL…head结点2结点1结点10structTrain_tag{char Num[8]; /*集装箱编号*/

char Name[10]; /*货物名称*/

int Weight; /*货物重量*/

char From[20]; /*发货地点*/

char To[20]; /*到货地点*/

structTrain_tag*next; /*指向下一结点*/}array[10],*head;7voidCreate(){inti;head=&array[0]; /*链表的头指针*/

for(i=0;i<10;i++){

输入array[i]的各个成员变量的值；

if(i<9)array[i].next=&array[i+1];elsearray[i].next=NULL;}}思路：用第i(0-9)个数组元素来描述第i+1个链表结点8DX11089玩具5吨从上海到深圳

CY20011电饭锅8吨从上海到湖南

AZ81920花生10吨从山东到广东NULL…head结点2结点1结点10array[0]array[1]array[9]92.创建动态链表在程序当中为链表的每一个结点动态地分配相应的存储空间，并把它们链接成一个链表的形式。优点：按需分配，链表的长度可动态增长。缺点：由程序员来进行内存的分配与释放。10【例】创建一个链表，并输入每一个结点的各种描述信息（集装箱编号、货物名称、货物重量、发货地点、到货地点等），直到用户输入的货物重量等于0，表示链表结束。11structTrain_tag{char Num[8]; /*集装箱编号*/

char Name[10]; /*货物名称*/

int Weight; /*货物重量*/

char From[20]; /*发货地点*/

char To[20]; /*到货地点*/

structTrain_tag*next; /*指向下一结点*/};structTrain_tag

*head,*p,*q;12①只要用户输入的Weight不为0，就要构建链表。基本思路是将一个一个的结点添加至链表中。首先用指针p来申请一个结构体变量的内存空间，并且装入用户输入的各种描述信息，然后将指针q和head都指向它。如下图：创建链表的过程可归纳为如下三个步骤pqheadDX11089玩具5吨从上海到深圳图链表的第一个结点建成13②后继结点的创建：如果用户输入的Weight又不为0，就要构建链表的第二个结点。首先用指针p来申请一个结构体变量的内存空间，并且装入用户输入的各种描述信息，然后要执行q->next=p，把第一个结点的next指针去指向它，从而建立两个结点之间的链接关系。最后再把q指向新的结点。如下图：headqpDX11089玩具5吨从上海到深圳图链表的第二个结点建成CY20011电饭锅8吨从上海到湖南q14headqDX11089玩具5吨从上海到深圳第三个结点加入链表的过程：CY20011电饭锅8吨从上海到湖南qpCZ21026苹果8吨从山东到福建15③链表创建过程的结束：如果用户输入的Weight等于0，意味着链表创建过程的结束，此时指针q所指向的就是链表的最后一个结点，所以要把该结点的next指针赋值为NULL，即执行q->next=NULL，表示这里已是链尾，后面不会再连结点。如下图：headDX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南qNULLAZ81920花生10吨从山东到广东16voidCreate(){intWeight;head=p=q=NULL;while(1){printf("输入货物重量：");

scanf("%d",&Weight);if(Weight<=0)break;p=malloc(sizeof(structTrain_tag));p->Weight=Weight;

输入该结点的其他信息；

if(head==NULL)head=p;//新建的是首结点

elseq->next=p; //不是首结点

q=p; //q指向当前尾结点}

if(head!=NULL)q->next=NULL;}173.访问链表在创建好一个链表之后，可以依次地访问该链表当中的各个结点的数据。voidDisplay(){structTrain_tag*p;p=head;while(p!=NULL){printf("%s,%s,%d,%s,%s\n",p->Num, p->Name,p->Weight,p->From,p->To);p=p->next;}}184.删除链表结点假设列车现在到达长沙站，因此需要把到货地点为湖南的车厢（假设有且仅有一节），从列车上摘下来，然后列车继续向南行驶。这里就需要用到链表结点的删除技术。19headDX11089玩具5吨从上海到湖南CY20011电饭锅8吨从上海到深圳NULLAZ81920花生10吨从山东到广东情形一、待删除的是首结点phead=p->next;20DX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南AZ81920花生10吨从山东到广东情形二、待删除的不是首结点pqq->next=p->next;21voidDelete(){structTrain_tag*p,*q;if(head==NULL){printf("空链表");return;}p=head;while((p!=NULL)&&strcmp(p->To,"湖南")){

q=p;p=p->next; //把指针p往后移动一个结点}

if((p!=NULL)&&!strcmp(p->To,"湖南")){

if(p==head)head=p->next; //删除的是首结点

elseq->next=p->next; //删除的是中间结点}}225.插入链表结点原则：插入操作不应破坏原有链接关系；需要插入的这个结点应该把它放在合适的位置上，也就是说，应该有一个插入位置的查找过程。233head4710NULL86先看下面一个简单的例子： 已有一个如图所示的链表。它是按结点中的货物重量从小到大排序的。现在要插入一个新的结点，该结点的货物重量为7吨。24定义：structTrain_tag*head; //头指针structTrain_tag*p; //链表当前结点structTrain_tag*q; //链表上一结点structTrain_tag*pNode;//待插入的结点25NULLheadDX11089玩具5吨从上海到湖南pNodehead=pNode;第一种情况：链表为空，即head=NULL

待插入的pNode

结点就是链表中的第一个结点。26pNode->next=head;head=pNode;第二种情况：

pNode

结点的Weight值小于等于链表首结点的

Weight值，即 pNode->Weight<=head->Weight

这时要将pNode

结点插入到首结点的前面，即执行以下两条语句：27这种情况如下图5104NULL15NULLheadpNodepNode->next=head;head=pNode;28第三种情况： 即pNode结点的Weight要大于首结点的Weight

值，这时肯定地说pNode结点要插入到首结点之 后，但究竟插入到哪里需要先找到正确的位置。 我们设指针q和指针p分别指向相邻的两个结点，

q在前p在后（即q更靠近首结点）。 首先让q=head，让p=head->next，然后让它们 顺序往后移动，每次移动一个结点。当着满足：

q->Weight<pNode->Weight<=p->Weight

时，pNode就插在q与p之间。2951012NULL15NULLheadpNode移动指针：q=p;p=p->next;pqpq插入结点：pNode->next=p;q->next=pNode;30voidInsert(structTrain_tag*pNode){structTrain_tag*p,*q;//第一种情形，链表为空

if(head==NULL){head=pNode;return;

}

//第二种情形，新结点的Weight小于等于首结点

if(pNode->Weight<=head->Weight){pNode->next=head;head=pNode;return;

}31//第三种情形，循环地查找正确的插入位置

q=head;p=head->next;while(p!=NULL){if(pNode->Weight<=p->Weight)break;else{q=p;p=p->next;}}

//将pNode结点插入在正确的位置(q和p之间)

pNode->next=p;q->next=pNode;}32

while(p!=NULL){if(pNode->Weight<=p->Weight)break;else{q=p;p=p->next;}}如果新结点的Weight大于所有结点？在这种情形下，当循环语句结束后，指针q是指向链表的尾结点，而指针p=NULL。3351017NULL15NULLheadpNodeq插入结点：pNode->next=p;q->next=pNode;pNULLNULL346.链表的释放对于静态链表，它们所占用的内存空间是由系统自动来分配和释放的；对于动态链表，必须由程序员自己来进行内存的分配与释放。35voidDestroy(){structTrain_tag*p,*q;p=head;while(p!=NULL){q=p;p=p->next;free(q);}}headDX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南CZ21026苹果8吨从山东到福建pqpqpqhead=NULL;369.4.3环形链表环形链表：一种特殊的链表，其尾结点的next指针，又指向了链表的首结点，从而形成了一个圆环。从环形链表的任何一个结点出发，都可以遍历整个的链表。37学校给高一（三）班分配了一个名额，去参加

奥运会的开幕式。每个人都争着要去，可是名

额只有一个，怎么办？班长想出了一个办法，

让班上的所有同学围成一圈，按照顺时针方向

进行编号。然后随便选定