试验二链表操作实现

1、实验二 链表操作实现实验日期：2021年3月16日实验目的及要求1.熟练掌握线性表的根本操作在链式存储上的实现；2.以线性表的各种操作建立、插入、删除、遍历等的实现为重点；3.掌握线性表的链式存储结构的定义和根本操作的实现；4.通过本实验加深对C语言的使用特别是函数的参数调用、指针类型的应用实验内容程序文件linklist.cpp已给出学生身高信息链表的类型定义和根本运算函数定义(1)链表类型定义typedef struct (int xh;/*学号*/float sg; /*身高*/int sex; /*性别，0为男生，1为女生*/ datatype;typedef struct node(

2、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(char

3、 *s);/*自定义错误处理函数*/void pntList(LinkList head);/*打印单链表*/void save(LinkList head,char strname);/*保存单链表到文件*/任务一创立程序文件linklist.cpp，其代码如下所示，理解LinkList类型和根本运算函数 后答复以下问题。#include #include /*单链表结点类型*/typedef struct (int xh; /*学号*/float sg; /*身高*/int sex; /*性别，0为男生，1为女生*/ datatype;typedef struct node(datatyp

4、e data;/*数据域*/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);/*自定义错误处理

5、函数*/void pntList(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(records.txt,r

6、)=NULL)( Error(can not open file !);return ;while(!feof(fp)( fscanf(fp,%d%f%d,&xh,&sg,&sex);p=(LinkList)malloc(sizeof(LinkNode);p-data.xh=xh;p-data.sg=sg;p-data.sex=sex;p-next=head-next;head-next=p;fclose(fp);/*创立单链表*/void createList_2(LinkList head)( FILE *fp;int xh;float sg;int sex;Lin

7、kList p,rear;if(fp=fopen(records.txt,r)=NULL)( Error(can not open file !);return ;rear=head;while(!feof(fp)( fscanf(fp,%d%f%d,&xh,&sg,&sex);p=(LinkList)malloc(sizeof(LinkNode);p-data.xh=xh;p-data.sg=sg;p-data.sex=sex;p-next=NULL;rear-next=p;rear=p;fclose(fp);/*单链表排序*/void sort_xh(LinkLis

8、t head)LinkList q,p,u;p=head-next;head-next=NULL;/*利用原表头结点建新的空表*/while(p)( q=p; /*q为被插入的结点*/p=p-next;/*用p记录后继结点*/*遍历新链表查找插入位置*/u=head;while(u-next!=NULL)/*查找插入位置*/( if(u-next-data.xhq-data.xh) break;u=u-next;/*插入在u结点的后面*/q-next=u-next;u-next=q;/*单链表倒置*/void reverse(LinkList head)( LinkList p, r;p=he

9、ad-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-next;while(p!=NULL)printf(%2d: %.2f %dn,p-data.xh,p-data.sg,p-data .sex); p=p-next;/*自定义错误处理函数*/void Error(char *s) printf(n %s, s);exit(1); /*返回OS,该函数定义在s

10、tdlib.h中*/head/*保存单链表到文件*/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,%2d %5.2f %2dn,p-data.xh,p-data.sg,p-data.sex); p=p-next;fclose(fp);请答复以下问题：(1)由单链表结点类型定义可知，该链表结点类型名为LinkNode,

11、结点的指针类型为LinkList,向系统申请一个学生结点空间并把起始地址存丁上述结点指针变量new中的语句是:p=(LinkList)malloc(sizeof(LinkNode);。(2)答复以下问题：a)：LinkList head ;图*顺序：1-13-7-15-2b)在a)操作的根底上，根据records.txt中的数据，画出执行createList_1(head);语句后的链表结构示意图headc)在b)操作的根底上，画出执行sort_xh(head)语句后的链表结构示意图画出执行head=initList();语句后的链表结构示意headd在c操作的根底上，画出执行reverseh

12、ead语句后的链表结构示意图heade在d操作的根底上，写出执行pntListhead;语句后屏幕输出结果3写出以下操作对应的执行语句以下的指针变量的类型都是上述定义的结点指 针类型a把一个new指针指向的结点头插到以h为头指针带表头结点的单链表中 的语句new-next=h-next;h-next=new;b把一个new指针指向的结点头插到以h为头指针不带表头结点的单链表 中的语句new-next=h;h=new;c在单链表中删除r所指结点的后继结点假设存在的语句r-next=r-next-nextd分别写出循环及非循环单链表中判断r所指结点是尾结点假设存在 的条件循环：r-next= =N

13、ULL非循环：r-next!=NULL任务二1.1.题目要求创立一个新的程序文件sy12.cpp,请调用linklist.cpp提供的功能函数(以#include#include“linklist.cpplinklist.cpp 方式导入函数库)及自定义的函数完成以下操作：从数据文件records.txt中读取学生信息， 建立与源数据同序的学生链表并打 印在屏帚上；统计学生链表中身高达标人数(男女生的身高达标值由键盘输入)，并打印结果；从键盘输入一位学生的相关信息插入到已排序的学生身高链表中后仍然保持学号的有序性；对上述操作后的学生链表进行倒置，结果输出到数据文件result.txt中；删除链

14、表中身高为指定值的所有学生结点并打印；在程序文件sy12.cpp需再定义以下三个功能函数：(1)int count(LinkList head,float sg_fm,float sg_m)功能：女生达标身高为sg_fm,男生达标身高为sg_m,统计head为头指针 的学生链表中身高达标人数并返回；(2)void insertX(LinkList head, datatype x)功能：在学号从小到大排序的学生链表中插入值为x的学生仍保持学号的有序性(3)int delete(LinkList head,float sg)功能：删除head为头指针的学生链表中指定身高的所有学生结点，删除成功返

15、 回1,否那么返回0;2 2 .请根据题目功能要求或程序中的注释完整sy12.cppsy12.cpp 代码#include linklist.cppint count(LinkList head,float sg_fm,float sg_m);/*统计head为头指针的学生链表中身高达标人数并返回*/void insertX(LinkList head, datatype x);/*在学号从小到大排序的学生链表中插入值为x的学生仍保持学号的有序性*/int delete(LinkList head,float sg);/*删除head为头指针的学生链表中指定身高的所有学生结点，删除成功返回1,

16、否那么返回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();/*统计学生链表中身高达标人数(男女生的身高达标值由键盘输入)并打印结果；*/printf(n输入达标的女生、男生身高值：);scanf(%

17、f%f,&sg_fm,&sg_m);c=count( head, sg fm, sg m );printf(n达标学生人数为：%d,c);getchar();/*对学生链表按学号进行排序*/sort_xh(head);/*在学生链表中插入指定的学生元素后使链表仍按学号有序*/x.xh=3;x.sg=1.67;x.sex=0;insertX( head, x );printf(n new list after insert:n);pntList(head);getchar();/*对学生链表进行倒置，结果输出到文件result.txt中；*/reverse(head);save(

18、head,result.txt);getchar();/*删除链表中身高为指定值的所有学生结点;*/sg=1.67;flag= dele(head, sg);if(flag)printf(ndelete succeed!n);elseprintf(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;LinkList p;p = head-next;while (p != NULL)(if (p-data.sex = 1)/*sex： 1女生*/(if (p-data.sg = sg_fm) n+;else(if