链表的基本概念VIP免费

119.4链表9.4.1链表的基本概念例：在铁路的中转站，有10个集装箱待运。每个集装箱上有如下五项说明：①箱号（比如AZ81920）②货物名称（比如苹果）③重量（比如10吨）④发货地点（比如山东）⑤到货地点（比如广东）2233如何在程序中来描述该列火车？如何来描述火车头？如何来描述每一个集装箱？如何来描述各节车厢之间的链接关系？44DX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南AZ81920花生10吨从山东到广东…head结点2需要引入一种新的数据结构：链表。链表中的每一个元素称为一个“结点”，每个结点都应该包括两部分：一为用户需要使用的实际数据；二为下一个结点的起始地址。另外，链表还有一个头指针head，指向链表的首结点。结点1结点355如何来实现链表结构？显然要用到结构体数据类型。定义如下的结构体类型：structTrain_tagstructTrain_tag*next;charNum[8];charName[10];intWeight;charFrom[20];charTo[20];数据域指针域669.4.2对链表的操作1.创建静态链表在程序中定义一组结构体变量或一个结构体数组，然后用它们来作为链表的结点，把它们链接成一个链表的形式。优点：不必去关心内存的分配与释放。缺点：需要事先知道链表结点的个数。77DX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南AZ81920花生10吨从山东到广东NULL…head结点2结点1结点10structTrain_tag{charNum[8];/*集装箱编号*/charName[10];/*货物名称*/intWeight;/*货物重量*/charFrom[20];/*发货地点*/charTo[20];/*到货地点*/structTrain_tag*next;/*指向下一结点*/}array[10],*head;88voidCreate(){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个链表结点99DX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南AZ81920花生10吨从山东到广东NULL…head结点2结点1结点10array[0]array[1]array[9]10102.创建动态链表在程序当中为链表的每一个结点动态地分配相应的存储空间，并把它们链接成一个链表的形式。优点：按需分配，链表的长度可动态增长。缺点：由程序员来进行内存的分配与释放。1111【例】创建一个链表，并输入每一个结点的各种描述信息（集装箱编号、货物名称、货物重量、发货地点、到货地点等），直到用户输入的货物重量等于0，表示链表结束。1212structTrain_tag{charNum[8];/*集装箱编号*/charName[10];/*货物名称*/intWeight;/*货物重量*/charFrom[20];/*发货地点*/charTo[20];/*到货地点*/structTrain_tag*next;/*指向下一结点*/};structTrain_tag*head,*p,*q;1313①只要用户输入的Weight不为0，就要构建链表。基本思路是将一个一个的结点添加至链表中。首先用指针p来申请一个结构体变量的内存空间，并且装入用户输入的各种描述信息，然后将指针q和head都指向它。如下图：创建链表的过程可归纳为如下三个步骤pqheadDX11089玩具5吨从上海到深圳图链表的第一个结点建成1414②后继结点的创建：如果用户输入的Weight又不为0，就要构建链表的第二个结点。首先用指针p来申请一个结构体变量的内存空间，并且装入用户输入的各种描述信息，然后要执行q->next=p，把第一个结点的next指针去指向它，从而建立两个结点之间的链接关系。最后再把q指向新的结点。如下图：headqpDX11089玩具5吨从上海到深圳图链表的第二个结点建成CY20011电饭锅8吨从上海到湖南q1515headqDX11089玩具5吨从上海到深圳第三个结点加入链表的过程：CY20011电饭锅8吨从上海到湖南qpCZ21026苹果8吨从山东到福建1616③链表创建过程的结束：如果用户输入的Weight等于0，意味着链表创建过程的结束，此时指针q所指向的就是链表的最后一个结点，所以要把该结点的next指针赋值为NULL，即执行q->next=NULL，表示这里已是链尾，后面不会再连结点。如下图：headDX11089玩具5吨从上海到深圳CY20011电饭锅8吨从上海到湖南qNULLAZ81920花生10吨从山东到广东1717voidCreate(){intWeight;head=p=q=NULL;while(1){printf("输入货物重量：");scanf("%d",&Weight);if(We...