《c语言程序设计项目教程教学课件作者宋海燕项目十通信录》由会员分享，可在线阅读，更多相关《c语言程序设计项目教程教学课件作者宋海燕项目十通信录（39页珍藏版）》请在金锄头文库上搜索。
1、项目十 通 信 录,任务10.1 初识单链表 任务10.2 建立动态链表 任务10.3 链表插入运算 任务10.4 链表查找 任务10.5 链表删除运算,返回,任务10.1 初识单链表,【实例10.1】用单链表实现通信录中联系人的存储。 （1）用逻辑状态图表示通信录中的联系人名单，如图10-3 所示。 （2）在内存中的链式结构存储如图10-4 所示。 知识链接 （1）对图10-3 说明：首先将第一个结点的地址160 放到一个指针变量 head 中，最后一个结点没有后继，其指针域设置为空（NULL），表明此表到此结束。查找时从第一个结点的地址开始“顺藤摸瓜”找到每个结点。通常用“头指针”来标识一
2、个单链表，如单链表L、单链表H、单链表head 等，这是指某链表的第一个结点的地址放在了指针变量 L、H、head 中。头指针为“NULL”则表示一个空的单链表。,下一页,返回,任务10.1 初识单链表,（2）单链表。 为建立起数据元素之间的线性（一对一）关系，对每个数据元素，除了存放数据元素的自身的信息之外，还需要存放其后继数据元素在内存中的地址，这两部分信息组成一个结点，结点的结构如图10-5 所示，每个元素都如此。存放数据元素信息的地方称为数据域，存放其后继地址的地方称为指针域。因此n 个元素的线性表通过每个结点的指针域拉成了一个“链子”，称为链表。因为每个结点中只有一个指向后继的指针，
3、所以称其为单链表。 链式存储结构的结点（数据项）最少有两个域：数据域和指针域。采用不连续空间存储线性表，使用指针指向下一元素的位置。,上一页,下一页,返回,任务10.1 初识单链表,（3）链表中结点的定义。 链表是由一个个结点构成的，结点的定义如下： typedef struct node datatype data; struct node *next; LNode，*LinkList； 定义头指针变量： LinkList H； 结点的结构如图10-6 所示。,上一页,下一页,返回,任务10.1 初识单链表,（4）通信录链表中结点的定义。 typedef struct /通信录结点类型 ch
4、ar num5; /编号 char name9; /姓名 char sex3; /性别 char phone13; /电话 char addr31; /地址,上一页,下一页,返回,任务10.1 初识单链表, DataType; typedef struct node /结点类型定义 DataType data; /结点数据域 struct node *next; /结点指针域 ListNode; typedef ListNode *LinkList; LinkList head; ListNode *p;,上一页,返回,任务10.2 建立动态链表,【实例10.2】建立通信录单链表和输出通信录。
5、 /此处需包含头文件声明及结构体定义部分的代码 LinkList CreateList(void) /尾插法建立带头结点的通信录链表 LinkList head=(ListNode *)malloc(sizeof(ListNode); /申请头结点 ListNode *p,*rear; char flag=y; /此处也可用int flag=0 语句; /结束标志置0 rear=head; /尾指针初始指向头结点 while (flag=y) ,下一页,返回,任务10.2 建立动态链表,p=(ListNode *)malloc(sizeof(ListNode); /申新结点 printf(“编
6、号(4)姓名(8)性别 电话(11) 地址(31)n“); printf(“-n“); printf(“n 添加的编号:n“); scanf(“%s“,p-data.num); printf(“n 添加的姓名:n“); scanf(“%s“,p-data.name); printf(“n 性别:n“); scanf(“%s“,p-data.sex); printf(“n 电话:n“); scanf(“%s“,p-data.phone);,上一页,下一页,返回,任务10.2 建立动态链表,printf(“n 地址:n“); scanf(“%s“,p-data.addr); rear-next=p
7、; /新结点连接到尾结点之后 rear=p; /尾指针指向新结点 printf(“继续建表?(y/n):“); scanf(“%c“, /返回链表头指针 ,上一页,下一页,返回,任务10.2 建立动态链表,void PrintList(LinkList head) /通信录链表的输出函数 / ListNode *p; p=head-next; printf(“编号 姓 名 性别 联系电话 地址 n“); printf(“-n“); while (p!=NULL) printf(“%s,%s,%s,%s,%sn“,p-data.num,p-data.name,p-data.sex,p-data.
8、phone,p-data.addr); printf(“-n“); p=p-next; /后移一个结点,上一页,下一页,返回,任务10.2 建立动态链表, main() ListNode *p; head=CreateList( ); PrintList(head); （1）运行结果。 实例10.2 的运行结果如图10-7 所示。 （2）知识链接。,上一页,下一页,返回,任务10.2 建立动态链表, malloc 函数： a. 原型为void *malloc（unsigned int size）; b. 作用是在内存的动态存储区中分配一个长度为size 的连续空间; c. 函数的返回值是一个指
9、向分配域起始地址的指针（类型为void）; d. 当内存空间不足时，返回空指针（NULL）。 free 函数： a. 原型为void free（void *p）； b. 作用是释放由指向的内存区，使这部分内存区能被其他变量使用。 建立动态链表： 所谓建立动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相链的关系，如图10-8 所示。,上一页,返回,任务10.3 链表插入运算,【实例10.3】在通信录链表中插入结点。 /此处需包含实例10.2 中的代码 void InsertNode(LinkList head,ListNode *p)
10、 /在通信录链表head 中插入结点 ListNode *p1,*p2; p1=head; p2=p1-next; while(p2!=NULL /p2 指向表的下一个结点,下一页,返回,任务10.3 链表插入运算, p1-next=p; /插入p 所指向的结点 p-next=p2; /连接表中剩余的结点 main() ListNode *p; head=CreateList( ); InsertNode(head,p); PrintList(head); ,上一页,下一页,返回,任务10.3 链表插入运算,（1）运行结果。 实例10.3 的运行结果如图10-9 所示。 （2）知识链接。 链表
11、的插入操作。 链表的插入是指将一个结点插入到一个已有的链表中。 为了能做到正确插入，必须解决两个问题： a. 怎样找到插入的位置； b. 怎样实现插入。 插入运算 InsertNode（）的算法思路。 a. 找到第i-1 个结点；若存在则继续步骤b，否则结束； b. 申请、添加新结点； c. 将新结点插入，返回主程序。,上一页,下一页,返回,任务10.3 链表插入运算, 插入运算InsertNode（）算法实现 后插结点：设p 指向单链表中的某结点，s 指向待插入的值为x 的新结点，将*s 插入到*p 的后面，插入示意如图10-10所示。 操作如下： a. s-next=p-next; b.
12、p-next=s; 注意：两个指针的操作顺序不能交换。 在通信录链表中插入结点的流程如图10-11 所示。,上一页,返回,任务10.4 链表查找,【实例10.4】通信录链表中信息的查询。 /此处需包含实例10.3 中的代码 ListNode *ListFind(LinkList head) /通信录链表中信息的查找 ListNode *p; char num5; char name9; char pp; printf(“=n“); printf(“ a. 按编号查询 n“); printf(“ b. 按姓名查询 n“);,下一页,返回,任务10.4 链表查找,printf(“=n“); pri
13、ntf(“ 请 选 择： “); p=head-next; scanf(“%c“, /没有查到要查找的通信信息 ,上一页,下一页,返回,任务10.4 链表查找,else if (pp=b|pp=B) printf(“ 请输入要查找者的姓名：“); scanf(“%s“,name); while(p main() ,上一页,下一页,返回,任务10.4 链表查找,ListNode *p; head=CreateList( ); InsertNode(head,p); p=ListFind(head); PrintList(head); （1）运行结果。 实例10.4 的运行结果如图10-12 所示
14、。,上一页,下一页,返回,任务10.4 链表查找,（2）知识链接。 链表的查询操作如下。 按编号查询ListFind（）。 算法思路：从链表的第一个结点开始，逐个判断链表中的结点是否是第i 个，若是，则返回该结点的指针，否则继续后一个，直至结束。没有第个结点时返回空。 按值查询ListFind（）。 算法思路：从链表的第一个结点开始，判断当前结点的值是否等于x，若是，返回该结点的指针，否则继续后一个，直至结束。找不到时返回空。 通信录信息查询的流程如图10-13 所示。,上一页,返回,任务10.5 链表删除运算,【实例10.5】通信录链表中结点的删除。 /此处需包含实例10.4 中的代码 vo
15、id DelNode(LinkList head) /删除通信录链表上的结点 char cho; ListNode *p,*q; p=ListFind(head); /调用查找函数 if (p=NULL) printf(“没有查到要删除的通信者!n“); return;,下一页,返回,任务10.5 链表删除运算, main() ListNode *p; head=CreateList( ); InsertNode(head,p); p=ListFind(head); DelNode(head); PrintList(head); ,上一页,下一页,返回,任务10.5 链表删除运算,（1）运行结果。 实例10.5 的运行结果如图10-14 所示。 （2）知识链接。 链表的删除操作。 链表的删除是指将链表中已有的结点删掉。 与插入操作一样，删除操作同样需要解决两个问题： a. 怎样找到删除的位置； b. 怎样实现删除。 删除运算DelNode（）的算法思路。 a. 找
