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

C语言综合实验 结构体与链表 利用结构体和指针处理动态链表 若用户使用引用自身的结构体，就可以形成一个动态链，真正做到摘去一个节点。 动态结构体中的每一个节点由两部分构成：数据项和指针项。 数据项存放有关节点自身的数据，指针项存放与该节点有关的其他节点的地址。 通过指针将若干个同类结构体连接起来。 链表的表示和实现 （1） 链表的表示 例：请画出26 个英文字母表的链式存储结构。 头指针、头结点和首元结点的区别 （3）举例 例1： sizeof(x)——计算x的长度 malloc(m) —开m字节空间 free(p) ——删除一个变量 附2： 补充结构数据类型的C表示法 链表的实现 （1） 单链表的建立和输出 （2） 单链表的修改 （3） 单链表的插入 （4） 单链表的删除 （1） 单链表的建立和输出 例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。 （2） 单链表的修改(或读取） 思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行p-data=new_value 。 （3） 单链表的插入 （4） 单链表的删除 指针结构体文件操作示例 课后习题 struct node *insertnode(struct node *head,struct node *insert) { struct node *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; //插到原链表表中或尾部 else head=insert; //插到原链表表头之前，成为新表头 return(head); } struct add_person /* 通讯录记录结构 */ { char name[10]; /* 姓名 */ char addr[30]; /* 地址 */ char offphnum[15]; /* 办公电话 */ char hmphnum[15]; /* 家庭电话 */ char mbphnum[15]; /* 移动电话 */ }; typedef struct person /*通讯录结构中结点的定义*/ { char name[10]; /* 姓名 */ char addr[30]; /* 地址 */ char offphnum[15]; /* 办公电话 */ char hmphnum[15]; /* 家庭电话 */ char mbphnum[15]; /* 移动电话 */ struct person *next; } listnode,*listlink; * 结构体应用举例 N个孩子围成一圈，并给他们依次编号，老师指定从第start个孩子开始报数，报到第m个孩子出列；然后从下一个孩子再开始报数，依次重复下去，直到所有的孩子都出列。试求孩子出列的顺序，即约瑟夫（Josephus）问题。 分析：由于问题本身的数据构成一个闭合的环，用结构体数组来构成一个静态环行链来表示此闭合环。 struct children { int num; char next; }link[MAX]; 孩子自身的号码 下一个孩子的号码 解题方法：只需沿着next连接成的环行链不带重复计数到m，使对应的num所在的节点从环行链中摘下（出列）；当环中的num成员的值为0时，表示该节点摘下，以后不再参加计数，直至节点全部摘完为止。 数据结构：Num和next一起构成一个整体，成为环行链中的一个节点（即结构体数组link中的一个元素） #include stdio.h #define MAX 100 void main( ) { int count, i,k,m,n,start; struct children{ in