《C语言综合实验》3链表.ppt

C语言综合实验,结构体与链表,结构体应用举例,N个孩子围成一圈，并给他们依次编号，老师指定从第start个孩子开始报数，报到第m个孩子出列；然后从下一个孩子再开始报数，依次重复下去，直到所有的孩子都出列。试求孩子出列的顺序，即约瑟夫（Josephus）问题。,分析：由于问题本身的数据构成一个闭合的环，用结构体数组来构成一个静态环行链来表示此闭合环。,structchildrenintnum;charnext;linkMAX;,孩子自身的号码,下一个孩子的号码,解题方法：只需沿着next连接成的环行链不带重复计数到m，使对应的num所在的节点从环行链中摘下（出列）；当环中的num成员的值为0时，表示该节点摘下，以后不再参加计数，直至节点全部摘完为止。,数据结构：Num和next一起构成一个整体，成为环行链中的一个节点（即结构体数组link中的一个元素）,#include#defineMAX100voidmain()intcount,i,k,m,n,start;structchildrenintnum;charnext;linkMAX;printf(n请输入参加游戏孩子的人数(1%d)：n,MAX-1);scanf(%d,/*标明其已出列*/,利用结构体和指针处理动态链表,若用户使用引用自身的结构体，就可以形成一个动态链，真正做到摘去一个节点。动态结构体中的每一个节点由两部分构成：数据项和指针项。数据项存放有关节点自身的数据，指针项存放与该节点有关的其他节点的地址。通过指针将若干个同类结构体连接起来。,structchildrenintnum;structchildren*next;,链表的表示和实现,（1）链表的表示（2）链表的实现,1)链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。,如何实现？,通过指针来实现！,让每个存储结点都包含两部分：数据域和指针域,数据域：存储元素数值数据,指针域：存储直接后继或者直接前驱的存储位置,设计思想：牺牲空间效率换取时间效率,（1）链表的表示,例：请画出26个英文字母表的链式存储结构。,该字母表在内存中链式存放的样式举例如下：,解：该字母表的逻辑结构为：（a,b,y,z）,链表存放示意图如下：,结点：数据元素的存储映像。由数据域和指针域两部分组成；链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。,循环链表示意图：,head,2)与链式存储有关的术语：,头指针、头结点和首元结点的区别,头指针,头结点,首元结点,头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。,示意图如下：,答：,讨论.如何表示空表？,无头结点时，当头指针的值为空时表示空表；,有头结点时，当头结点的指针域为空时表示空表。,头结点不计入链表长度！,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,称：头指针H的值是31,（3）举例例1：,上例链表的逻辑结构示意图有以下两种形式：,区别：无头结点有头结点,头结点不计入链表长度！,讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？,因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构体数据类型。,答：,以26个字母的链表为例，每个结点都有两个分量：,设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？,方式1：直接表示为node.dataa；node.next=q方式2：p指向结点首地址，然后p-data=a;p-next=q;方式3：p指向结点首地址，然后(*p).data=a；(*p).nextq,附1：介绍C的三个有用的库函数/算符（都在中）：sizeof(x)计算变量x的长度（字节数）；malloc(m)开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)释放指针p所指变量的存储空间，即彻底删除一个变量。,sizeof(x)计算x的长度malloc(m)开m字节空间free(p)删除一个变量,1：自定义结构类型node的长度m是多少？,2：结构变量node的首地址(指针p）是多少？,3：怎样删除结构变量node？,msizeof(node)/单位是字节,p(node*)malloc(m),free(p)/只能借助node的指针删除！,p-data=a;p-next=q,对于指向结构类型的指针变量，可说明为：node*p,*q;/或用structxie*p,*q;/注：上面已经定义了node为用户自定义的xie类型。,类型定义和变量说明可以合写为：typedefstructxie/xie是自定义结构类型名称chardata;/定义数据域的变量名及其类型structxie*next;/定义指针域的变量名及其类型node，*pointer;/node是xie结构类型的类型替代,*pointer是指针型的xie结构类型的替代，也是数据类型*/,附2：补充结构数据类型的C表示法,单链表的数据类型描述如下：,typedefstructnodechardata;/数据域structnode*next;/指针域node,*LinkList;/*LinkList为node类型的指针,如何具体编程来建立和访问链表？链表的实现,请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。,结构名,类型名,链表的实现,（1）单链表的建立和输出（2）单链表的修改（3）单链表的插入（4）单链表的删除,（1）单链表的建立和输出,例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,先挖“坑”,后种“萝卜”！,#include#includetypedefstructnodechardata;structnode*next;node;node*p,*q,*head;/一般需要3个指针变量intn;/数据元素的个数intm=sizeof(node);/*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/,将全局变量及函数提前说明：,新手特别容易忘记！,node*build()/字母链表的生成。要一个个慢慢链入inti;head=(node*)malloc(m);/m=sizeof(node)前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符ap-next=(node*)malloc(m);/为后继结点“挖坑”！p=p-next；/让指针变量P指向后一个结点p-data=i+a-1;/最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！return(head);,voiddisplay(node*head)/*字母链表的输出*/p=head;while(p)/当指针不空时循环，仅限于无头结点的情况printf(%c,p-data);p=p-next;/让指针不断“顺藤摸瓜”,讨论：要统计链表中数据元素的个数，该如何改写？,sum+;,sum=0;,（2）单链表的修改(或读取）,思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行p-data=new_value。,修改第i个数据元素的操作函数可写为：,node*modifynode(node*head,inti,char,缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取。,在链表中插入一个元素X的示意图如下：,链表插入的核心语句：,Step1：s-next=p-next;Step2：p-next=s；,p-next,s-next,思考：Step1和Step2能互换么？,X结点的生成方式：s=(node*)malloc(m);s-data=X;s-next=?,（3）单链表的插入,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q=p-next;/首先保存b的指针，靠它才能找到c；p-next=q-next;/将a、c两结点相连，淘汰b结点；free(q)；/彻底释放b结点空间,p-next,(p-next)-next,q,（4）单链表的删除,结构体floatgrade;structnode*next;,/建立链表structnode*creatlink()intk;longn;structnode*head,*news,*tail;head=NULL;k=0;/初始为空表，节点个数为0printf(请输入一学生的学号(0表示结束):n);scanf(%ld,/返回链头指针,/链表遍历voidoutputlink(structnode*head)structnode*p;if(head=NULL)/若为空表，则退出printf(空表，无数据输出n);return;printf(学号tt成绩ttn);p=head;/p指向头节点while(p!=NULL)printf(%ldtt%fttn,p-num,p-grade);p=p-next;/p后移一个节点,structnode*deletenode(structnode*head,longnumkey)structnode*check,*last;check=last=head;while(check!=NULL)/在链表中对各节点进行搜索if(check-num=numkey)break;/若找到，则停止last=check;check=check-next;/未找到，后移一个节点if(check-num=numkey)if(check=head)head=check-next;/若是头节点，删除elselast-next=check-next;/若是其他节点，删除free(check);/释放已删除节点的存储空间printf(n已删除学号为%d的节点.,numkey);elseprintf(n表中无学号为%d的节点.,numkey);/表中无删除节点return(head);,#include#includevoidmain()structnode*head,*stu;longkey;printf(输入记录:n);head=creatlink();/建链表outputlink(head);/输出链表printf(输入要插入的记录（学号成绩）:n);stu=(structnode*)malloc(sizeof(structnode);/新节点scanf(%ld%f,structnode*insertnode(structnode*head,structnode*insert)structnode*check,*last;if(head=NULL)/若原链表为空表，则将待插入的节点构成一新链表insert-next=NULL;return(insert);check=last=head;while(check!=NULL)/在原链表中搜索if(check-num=insert-num)break;/找到插入点，则停止搜索last=check;check=check-next;/往后找一下节点/插入insert-next=check;/将insert所指节点插到check所指节点之前if(check!=head)last-next=insert;/插到原链表表中或尾部elsehead=insert;/插到原链表表头之前，成为新表头return(head);,structadd_person/*通讯录记录结构*/charname10;/*姓名*/charaddr30;/*地址*/charoffphnum15;/*办公电话*/charhmphnum15;/*家庭电话*/charmbphnum15;/*移动电话*/;typedefstructperson/*通讯录结构中结点的定义*/charname10;/*姓名*/charaddr30;/*地址*/charoffphnum15;/*办公电话*/charhmphnum15;/*家庭电话*/charmbphnum15;/*移动电话*/structperson*next;listnode,*listlink;,指针/*定义文件指针*/structadd_personpersons;listnode*s;listlinkhead=NULL,end=NULL;fp=fopen(people.txt,rb);/*打开文件*/if(fp=NULL)printf(cannotopenfilen);returnhead;fread(,voidSave(listlinkhead)/*保存信息*/FILE*fp;structadd_personpersons;listlinkp1;fp=fopen(people.txt,wb);for(p1=head;p1!=NULL;p1=p1-next)/*将链表中的信息存入文件*/strcpy(persons.name,p1-name);strcpy(persons.addr,p1-addr);strcpy(persons.offphnum,p1-offphnum);strcpy(persons.hmphnum,p1-hmphnum);strcpy(persons.mbphnum,p1-mbphnum);fwrite(,习题1、有若干节列车车厢，每节车厢都有固定的编号，车厢逐个进入站台编组成一列列车（车厢进入站台顺序与车厢编号无关），请你用链表模拟组成的列车，并分别完成以下功能。1）在主函数中读入数据并创建列车链表。2)用函数实现，按输入顺序打印出所有的车厢号（各号之间有一位空格分隔）。3）用函数实现，统计出组成列车中共有多少节车厢。4)用函数实现，按输入顺序的逆序打印出所有车厢号。,课后习题,