《C语言程序设计项目教程》-项目十 通 信 录

项目十通信录任务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），表明此表到此结束。查找时从第一个结点的地址开始“顺藤摸瓜”找到每个结点。通常用“头指针”来标识一个单链表，如单链表L、单链表H、单链表head等，这是指某链表的第一个结点的地址放在了指针变量L、H、head中。头指针为“NULL”则表示一个空的单链表。下一页返回任务10.1初识单链表（2）单链表。①为建立起数据元素之间的线性（一对一）关系，对每个数据元素，除了存放数据元素的自身的信息之外，还需要存放其后继数据元素在内存中的地址，这两部分信息组成一个结点，结点的结构如图10-5所示，每个元素都如此。存放数据元素信息的地方称为数据域，存放其后继地址的地方称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。②链式存储结构的结点（数据项）最少有两个域：数据域和指针域。采用不连续空间存储线性表，使用指针指向下一元素的位置。上一页下一页返回任务10.1初识单链表（3）链表中结点的定义。①链表是由一个个结点构成的，结点的定义如下：typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；②定义头指针变量：LinkListH；结点的结构如图10-6所示。上一页下一页返回任务10.1初识单链表（4）通信录链表中结点的定义。typedefstruct{//通信录结点类型charnum[5];//编号charname[9];//姓名charsex[3];//性别charphone[13];//电话charaddr[31];//地址上一页下一页返回任务10.1初识单链表}DataType;typedefstructnode{//结点类型定义DataTypedata;//结点数据域structnode*next;//结点指针域}ListNode;typedefListNode*LinkList;LinkListhead;ListNode*p;上一页返回任务10.2建立动态链表【实例10.2】建立通信录单链表和输出通信录。//此处需包含头文件声明及结构体定义部分的代码LinkListCreateList(void)//尾插法建立带头结点的通信录链表{LinkListhead=(ListNode*)malloc(sizeof(ListNode));//申请头结点ListNode*p,*rear;charflag='y';//此处也可用intflag=0语句;//结束标志置0rear=head;//尾指针初始指向头结点while(flag=='y'){下一页返回任务10.2建立动态链表p=(ListNode*)malloc(sizeof(ListNode));//申新结点printf("编号(4)姓名(8)性别电话(11)地址(31)\n");printf("-----------------------------------------------\n");printf("\n添加的编号:\n");scanf("%s",p->data.num);printf("\n添加的姓名:\n");scanf("%s",p->);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;//新结点连接到尾结点之后rear=p;//尾指针指向新结点printf("继续建表?(y/n):");scanf("%c",&flag);}rear->next=NULL;//终端结点指针置空returnhead;//返回链表头指针}上一页下一页返回任务10.2建立动态链表voidPrintList(LinkListhead)//通信录链表的输出函数//{ListNode*p;p=head->next;printf("编号姓名性别联系电话地址\n");printf("------------------------------------------------------------\n");while(p!=NULL){printf("%s,%s,%s,%s,%s\n",p->data.num,p->,p->data.sex,p->data.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（unsignedintsize）;b.作用是在内存的动态存储区中分配一个长度为size的连续空间;c.函数的返回值是一个指向分配域起始地址的指针（类型为void）;d.当内存空间不足时，返回空指针（NULL）。②free函数：a.原型为voidfree（void*p）；b.作用是释放由ｐ指向的内存区，使这部分内存区能被其他变量使用。③建立动态链表：所谓建立动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点的数据，并建立起前后相链的关系，如图10-8所示。上一页返回任务10.3链表插入运算【实例10.3】在通信录链表中插入结点。//此处需包含实例10.2中的代码voidInsertNode(LinkListhead,ListNode*p)//在通信录链表head中插入结点{ListNode*p1,*p2;p1=head;p2=p1->next;while(p2!=NULL&&strcmp(p2->data.num,p->data.num)<0){p1=p2;//p1指向刚访问过的结点p2=p2->next;//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）知识链接。①链表的插入操作。链表的插入是指将一个结点插入到一个已有的链表中。为了能做到正确插入，必须解决两个问题：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.p->next=s;注意：两个指针的操作顺序不能交换。在通信录链表中插入结点的流程如图10-11所示。上一页返回任务10.4链表查找【实例10.4】通信录链表中信息的查询。//此处需包含实例10.3中的代码ListNode*ListFind(LinkListhead)//通信录链表中信息的查找{ListNode*p;charnum[5];charname[9];charpp;printf("==================\n");printf("a.按编号查询\n");printf("b.按姓名查询\n");下一页返回任务10.4链表查找printf("==================\n");printf("请选择：");p=head->next;scanf("%c",&pp);if(pp=='a'||pp=='A'){printf("请输入要查找者的编号：");scanf("%s",num);while(p&&strcmp(p->data.num,num)<0)p=p->next;if((p==NULL)||strcmp(p->data.num,num)>0)p=NULL;//没有查到要查找的通信信息}上一页下一页返回任务10.4链表查找elseif(pp=='b'||pp=='B'){printf("请输入要查找者的姓名：");scanf("%s",name);while(p&&strcmp(p->,name)!=0)p=p->next;}returnp;}main(){上一页下一页返回任务10.4链表查找ListNode*p;head=CreateList();InsertNode(head,p);p=ListFind(head);PrintList(head);}（1）运行结果。实例10.4的运行结果如图10-12所示。上一页下一页返回任务10.4链表查找（2）知识链接。链表的查询操作如下。①按编号查询ListFind（）。算法思路：从链表的第一个结点开始，逐个判断链表中的结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，直至结束。没有第ｉ个结点时返回空。②按值查询ListFind（）。算法思路：从链表的第一个结点开始，判断当前结点的值是否等于x，若是，返回该结点的指针，否则继续后一个，直至结束。找不到时返回空。通信录信息查询的流程如图10-13所示。上一页返回任务10.5链表删除运算【实例10.5】通信录链表中结点的删除。//此处需包含实例10.4中的代码voidDelNode(LinkListhead)//删除通信录链表上的结点{charcho;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（）