《实验二链表操作实现2418.pdf》由会员分享，可在线阅读，更多相关《实验二链表操作实现2418.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验二 链表操作实现 实验日期：2017 年 3 月 16 日 实验目的及要求 1.熟练掌握线性表的基本操作在链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的链式存储结构的定义和基本操作的实现；4.通过本实验加深对 C 语言的使用（特别是函数的参数调用、指针类型的应用）。实验内容 已知程序文件已给出学生身高信息链表的类型定义和基本运算函数定义。（1）链表类型定义 typedef struct int xh;/*学号*/float sg;/*身高*/int sex;/*性别，0 为男生，1 为女生*/datatype;typedef struct
2、 node datatype data;/*数据域*/struct node *next;/*指针域*/LinkNode,*LinkList;（2）带头结点的单链表的基本运算函数原型 LinkList initList();/*置一个空表（带头结点）*/void createList_1(LinkList head);/*创建单链表*/void createList_2(LinkList head);/*创建单链表*/void sort_xh(LinkList head);/*单链表排序*/void reverse(LinkList head);/*对单链表进行结点倒置*/void Error
3、(char*s);/*自定义错误处理函数*/void pntList(LinkList head);/*打印单链表*/void save(LinkList head,char strname);/*保存单链表到文件*/任务一 创建程序文件，其代码如下所示，理解 LinkList 类型和基本运算函数后回答下列问题。#include#include /*单链表结点类型*/typedef struct int xh;/*学号*/float sg;/*身高*/int sex;/*性别，0 为男生，1 为女生*/datatype;typedef struct node datatype data;/*数
4、据域*/struct node *next;/*指针域*/LinkNode,*LinkList;/*带表头的单链表的基本运算函数*/LinkList initList();/*置一个空表（带头结点）*/void createList_1(LinkList head);/*创建单链表*/void createList_2(LinkList head);/*创建单链表*/void sort_xh(LinkList head);/*单链表排序*/void reverse(LinkList head);/*单链表倒置*/void Error(char*s);/*自定义错误处理函数*/void pntL
5、ist(LinkList head);/*打印单链表*/void save(LinkList head,char strname);/*保存单链表到文件*/*置一个空表*/LinkList initList()LinkList p;p=(LinkList)malloc(sizeof(LinkNode);p-next=NULL;return p;/*创建单链表*/void createList_1(LinkList head)FILE*fp;int xh;float sg;int sex;LinkList p;if(fp=fopen(,r)=NULL)Error(can not open fil
6、e!);return;while(!feof(fp)fscanf(fp,%d%f%d,&xh,&sg,&sex);p=(LinkList)malloc(sizeof(LinkNode);p-=xh;p-=sg;p-=sex;p-next=head-next;head-next=p;fclose(fp);/*创建单链表*/void createList_2(LinkList head)FILE*fp;int xh;float sg;int sex;LinkList p,rear;if(fp=fopen(,r)=NULL)Error(can not open file!);return;rear=
7、head;while(!feof(fp)fscanf(fp,%d%f%d,&xh,&sg,&sex);p=(LinkList)malloc(sizeof(LinkNode);p-=xh;p-=sg;p-=sex;p-next=NULL;rear-next=p;rear=p;fclose(fp);/*单链表排序*/void sort_xh(LinkList head)LinkList q,p,u;p=head-next;head-next=NULL;/*利用原表头结点建新的空表*/while(p)q=p;/*q 为被插入的结点*/p=p-next;/*用 p 记录后继结点*/*遍历新链表查找插入
8、位置*/u=head;while(u-next!=NULL)/*查找插入位置*/if(u-next-q-break;u=u-next;/*插入在 u 结点的后面*/q-next=u-next;u-next=q;/*单链表倒置*/void reverse(LinkList head)LinkList p,r;p=head-next;head-next=NULL;while(p)r=p;p=p-next;/*r 指向结点头插到链表*/r-next=head-next;head-next=r;/*输出单链表*/void pntList(LinkList head)LinkList p;p=head-
9、next;while(p!=NULL)printf(%2d:%.2f%dn,p-,p-,p-data.sex);p=p-next;/*自定义错误处理函数*/void Error(char*s)printf(n%s,s);exit(1);/*返回 OS,该函数定义在中*/*保存单链表到文件*/void save(LinkList head,char strname)FILE*fp;LinkList p;if(fp=fopen(strname,w)=NULL)printf(can not open file!);return;p=head-next;while(p!=NULL)fprintf(fp
10、,%2d%5.2f%2dn,p-,p-,p-;p=p-next;fclose(fp);请回答下列问题：（1）由单链表结点类型定义可知，该链表结点类型名为 LinkNode，结点的指针类型为 LinkList ，向系统申请一个学生结点空间并把起始地址存于上述结点指针变量 new 中的语句是：p=(LinkList)malloc(sizeof(LinkNode);。（2）回答问题：a）已知：LinkList head;画出执行 head=initList();语句后的链表结构示意图 head *顺序：p b）在 a)操作的基础上，根据中的数据，画出执行 createList_1(head);语句后
11、的链表结构示意图 head c）在 b)操作的基础上，画出执行 sort_xh(head);语句后的链表结构示意图 head d）在 c)操作的基础上，画出执行 reverse(head);语句后的链表结构示意图 2 15 7 13 1 1 2 7 13 15 head e）在 d)操作的基础上，写出执行 pntList(head);语句后屏幕输出结果 （3）写出下列操作对应的执行语句（以下的指针变量的类型都是上述定义的结点指针类型）a）把一个 new 指针指向的结点头插到以 h 为头指针带表头结点的单链表中的语句 new-next=h-next;h-next=new;b）把一个 new 指针
12、指向的结点头插到以 h 为头指针不带表头结点的单链表中的语句 new-next=h;h=new;c）在单链表中删除 r 所指结点的后继结点（假设存在）的语句 r-next=r-next-next d）分别写出循环及非循环单链表中判断 r 所指结点是尾结点（假设存在）的条件 循环：r-next=NULL 15 13 7 2 1 非循环：r-next!=NULL 任务二 1题目要求 创建一个新的程序文件，请调用提供的功能函数（以#include“”方式导入函数库）及自定义的函数完成以下操作：从数据文件中读取学生信息，建立与源数据同序的学生链表并打印在屏幕上；统计学生链表中身高达标人数（男女生的身高
13、达标值由键盘输入），并打印结果；从键盘输入一位学生的相关信息插入到已排序的学生身高链表中后仍然保持学号的有序性；对上述操作后的学生链表进行倒置，结果输出到数据文件中；删除链表中身高为指定值的所有学生结点并打印；在程序文件需再定义以下三个功能函数：（1）int count(LinkList head,float sg_fm,float sg_m)功能：已知女生达标身高为 sg_fm，男生达标身高为 sg_m，统计 head 为头指针的学生链表中身高达标人数并返回；（2）void insertX(LinkList head,datatype x)功能：在学号从小到大排序的学生链表中插入值为 x 的
14、学生仍保持学号的有序性（3）int delete(LinkList head,float sg)功能：删除 head 为头指针的学生链表中指定身高的所有学生结点，删除成功返回 1，否则返回 0；2请根据题目功能要求或程序中的注释完整代码#include int count(LinkList head,float sg_fm,float sg_m);/*统计 head 为头指针的学生链表中身高达标人数并返回*/void insertX(LinkList head,datatype x);/*在学号从小到大排序的学生链表中插入值为 x 的学生仍保持学号的有序性*/int delete(LinkLi
15、st head,float sg);/*删除 head 为头指针的学生链表中指定身高的所有学生结点，删除成功返回 1，否则返回 0*/void main()LinkList head;int c,flag;float sg,sg_fm,sg_m;datatype x;/*建立与源数据文件同序的学生链表并输出；*/head=initList();/*建空链表*/createList_2(head);/*调用建链表函数建立所需链表*/printf(n 与数据文件同序的学生链表：n);pntList(head);/*调用函数打印输出链表中信息*/getchar();/*统计学生链表中身高达标人数（男
16、女生的身高达标值由键盘输入）并打印结果；*/printf(n 输入达标的女生、男生身高值：);scanf(%f%f,&sg_fm,&sg_m);c=count(head,sg_fm,sg_m);printf(n 达标学生人数为：%d,c);getchar();/*对学生链表按学号进行排序*/sort_xh(head);/*在学生链表中插入指定的学生元素后使链表仍按学号有序*/=3;=;=0;insertX(head,x);printf(n new list after insert:n);pntList(head);getchar();/*对学生链表进行倒置，结果输出到文件中；*/revers
17、e(head);save(head,);getchar();/*删除链表中身高为指定值的所有学生结点;*/sg=;flag=dele(head,sg);if(flag)printf(ndelete succeed!n);else printf(ndelete failedn);printf(n new list after delete:n);pntList(head);getchar();/统计学生链表中身高达标人数并返回(sg_fm 女生身高达标值、sg_m 男生身高达标值)int count(LinkList head,float sg_fm,float sg_m)int n=0;Lin
18、kList p;p=head-next;while(p!=NULL)if(p-=1)/*sex：1 女生*/if(p-=sg_fm)n+;else if(p-=sg_m)n+;p=p-next;return n;/在学号从小到大排序的学生链表中插入值为x 的学生仍保持学号的有序性 void insertX(LinkList head,datatype x)LinkList p,u;p=(LinkList)malloc(sizeof(LinkNode);p-=;p-=;p-=;u=head;while(u-next!=NULL)if(u-next-break;u=u-next;p-next=u-next;u-next=p;/删除学生链表中指定身高(存于 sg 中)的所有学生结点，删除成功返回 1，否则返回 0 int delete(LinkList head,float sg)LinkList p,q,v;int flag=0;q=head;p=head-next;while(p!=NULL)if(p-=sg)/*删除 p 所指结点*/v=p;p=p-next;q-next=p;free(v);flag=1;else q=p;p=p-next;return flag;/*删除成功返回 1,否则返回 0*/实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）