数据结构与算法综合设计实验1实验报告

1、电 子 科 技 大 学实 验 报 告学生姓名：苏魏明 学 号：指导教师： 实验地点： 实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法线性表三、实验学时：4四、实验原理：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可以用于表示线性结构，也可用于表示非线性结构。一般来说，在线性表的链式存储结构中，各数据结点的存储符号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。线性表

2、的链接存储中，为了方便在表头插入和删除结点的操作，经常在表头结点（存储第一个元素的结点）的前面增加一个结点，称之为头结点或表头附加结点。这样原来的表头指针由指向第一个元素的结点改为指向头结点，头结点的数据域为空，头结点的指针域指向第一个元素的结点。五、实验目的：本实验通过定义单向链表的数据结构，设计创建链表、插入结点、遍历结点等基本算法，使学生掌握线性链表的基本特征和算法，并能熟练编写c程序，培养理论联系实际和自主学习的能力，提高程序设计水平。六、实验内容：使用数据结构typedef struct node elemtype data； struct node *next； listnode,

3、 *listptr； typedef struct stuinfo char stuname10; /*学生姓名*/ int age /*年龄*/ elemtype实现带头结点的单向链表的创建、删除链表、插入结点等操作，并能实现年龄递增的两个单向链表合并一个链表，合并后的链表按年龄递减，可认为同名同年龄是同一个学生，每个学生在合并后的链表中仅出现一次。最后打印输出合并后的链表元素，验证结果的正确性。七、实验器材（设备、元器件）：pc机一台，装有c语言集成开发环境。八、数据结构与程序：#include stdafx.h#include #include #include #definemaxcn

4、t 50typedef struct stuinfo char stuname10; _int64 age; elemtype;typedef struct node elemtype data; struct node *next; listnode, *listnodeptr;typedef listnodeptr list, *listptr;/ 创建单链表: 设线性表n个元素已存放在数组elem中，动态创建一个单链表l/ 函数返回值为整型：0表示创建成功，1表示创建失败int list_create(listptr l, elemtype elem, int n)int result

5、= 0, / 记录程序运行结果 0表示成功 1表示失败i = n;listnodeptr p,q;q = (listnodeptr)malloc(sizeof(listnode);q-next = null;while(i = 1)p = (listnodeptr)malloc(sizeof(listnode);if(!p) result = 1; break;p-data.age = elemi.age;strcpy(p-data.stuname, elemi.stuname);p-next = q-next;q-next = p;i = i - 1;(*l) = q;return resu

6、lt;void list_destroy(listptr l)/ 销毁单链表：释放单链表所占存储单元listnodeptr p;while(*l)p = (*l)-next;free(*l);*l = p;void list_clear(listptr l) / 初始化：将单链表l重置为空表listnodeptr p=(*l)-next; / p指向第一个节点(*l)-next=null; / 头结点指针域为空list_destroy(&p); / 销毁p所指的单链表/ 单链表中结点插入算法: 在单链表l中的第pos个结点前插入值为elem的数据元素/ 插入结果是新结点占据第pos个位置，原p

7、os位置结点变为第pos+1个结点/ 函数返回值为整型：0表示插入成功，1表示插入失败int list_insert(listptr l, int pos, elemtype elem)int result = 1;listnodeptr p = (*l)-next, s;int i = 1;while(p & inext;if(p & i = pos-1)s = (listnodeptr)malloc(sizeof(listnode);if(s)p-data.age = elem.age;strcpy(p-data.stuname, elem.stuname);s-next = p-next

8、;p-next = s;result = 0;return result;/ 删除单链表中结点: 删除单链表l中的第pos个结点数据元素/ 函数返回值为整型：0表示删除成功，1表示删除失败int list_remove(listptr l, int pos)int result = 1;listnodeptr p = (*l)-next, q;int i = 1;while(p & inext;if(p & i = pos-1)q = p-next;p-next = q-next;free(q);result = 0;return result;/ 合并单链表操作,合并后的链表储存在链表la中

9、；/ 合并之后按年龄递减也就是年月日递增的顺序，排列学生信息；void list_merge(listptr la, listptr lb)listnodeptr p, pa=(*la)-next, pb=(*lb)-next;if(!pa & !pb)printf(对不起，由于两张线性表均为空,合并失败。n);exit(0);if(pa & pb) if(pa-data.age = pb-data.age)(*la)-next = pa;pa = pa-next;(*la)-next-next = null;else(*la)-next = pb;pb = pb-next;(*la)-nex

10、t-next = null;while(pa & pb)if(pa-data.age = pb-data.age)p = pa-next;pa-next = (*la)-next;(*la)-next = pa;pa = p;else p = pb-next;pb-next = (*la)-next;(*la)-next = pb;pb = p;while(pb) / b表中还有元素p = pb-next;pb-next = (*la)-next;(*la)-next = pb;pb = p;while(pa) / a表中还有元素p = pa-next;pa-next = (*la)-next

11、;(*la)-next = pa;pa = p;printf(合并成功！n);void show_list(listnodeptr l)/ 输出单链表中元素listnodeptr p = l-next;if(!p) printf(对不起，由于单链表为空，打印失败！n); return;while(p)printf(%i64dt%sn, p-data.age, p-data.stuname);p = p-next;int read_file(char * fname, char namemaxcnt11, _int64* age)int scount = 0;char charage13 + 1

12、;file * pfile = null;pfile = fopen(fname, r);if(!pfile)printf(read_file(): file open failed!n);exit(0);elseprintf(read_file(): file open succeeded!n);memset(age, 0, maxcnt *8);memset(name, 0, maxcnt * (10 + 1);while(!feof(pfile)fscanf(pfile,%s,charage);fscanf(pfile,t%sn,namescount);agescount = _atoi

13、64(charage);scount+;fclose(pfile);return scount;void bubble_sort(elemtype elem, int n)/ 冒泡排序 将学生信息以年龄递增的顺序 也就是按出生年月降序排列int i, j, swap;for(i=1; in; i+)swap = 0; for(j=1; j=n-1; j+)if(elemj.ageelemj+1.age)elem0.age = elemj+1.age; elemj+1.age = elemj.age; elemj.age = elem0.age;strcpy(elem0.stuname, ele

14、mj+1.stuname); strcpy(elemj+1.stuname, elemj.stuname);strcpy(elemj.stuname, elem0.stuname);swap = 1; if(swap = 0) break; int main()charnamemaxcnt10+1; /存放姓名，名字最长为10个字符； _int64agemaxcnt; /采用64位整型；char * fnamea = d:filestuinfoa.txt, * fnameb = d:filestuinfob.txt;/ 定义文本信息存储路径char main_command, case_com

15、mand;int i, num, pos, temp;listnodeptr la=null ,lb=null;elemtype elemmaxcnt+1;/ 读入学生信息，并分别存入单链表表la，lb中num = read_file(fnamea, name, age);for(i=1; i=num; +i)elemi.age = agei-1;strcpy(elemi.stuname, namei-1);bubble_sort(elem, num);list_create(&la, elem, num);num = read_file(fnameb, name, age);for(i=1;

16、 i=num; +i)elemi.age = agei-1;strcpy(elemi.stuname, namei-1);bubble_sort(elem, num);list_create(&lb, elem, num);for(;)printf(n*% 请选择将要进行的操作 ooooooo*nn);printf(*% a.对线性表a进行操作 ooooooo*n);printf(*% b.对线性表b进行操作 ooooooo*n);printf(*% c.对线性表a,b进行合并 ooooooo*n);printf(*% 输入其他字符退出程序 ooooooo*nn);fflush(stdin);

17、printf(请输入您要进行的操作（a，b或c）：);scanf(%c, &main_command);switch(main_command)case a: case a:if(la=null) printf(您好，线性表b已被删除！n); break;printf(n* 请选择将要进行的操作 *nn);printf(* a.删除线性表a中的信息*n);printf(* b.打印线性表a中的信息*n);printf(* c.销毁线性表a *nn);fflush(stdin);printf(请输入您要进行的操作（a，b或c）：);scanf(%c, &case_command);switch(

18、case_command)case a: case a:printf(请输入要删学生信息的序号：);scanf(%d, &pos);temp = list_remove(&la, pos);if(temp=1) printf(对不起，学生信息删除失败！n);else printf(您好，学生信息删除成功！n);printf(打印删除学生信息后的线性表如下：n);show_list(la);break;case b:case b:show_list(la);break;case c:case c:list_destroy(&la);printf(您好，线性表a删除成功！n); break;def

19、ault: printf(对不起，您的输入有误！n); break;break;case b: caseb :if(lb=null) printf(对不起，线性表b已被删除！n); break;printf(n* 请选择将要进行的操作 *nn);printf(* a.删除线性表b中的信息*n);printf(* b.打印线性表b中的信息*n);printf(* c.销毁线性表b *nn);fflush(stdin);printf(请输入您要进行的操作（a，b或c）：);scanf(%c, &case_command);switch(case_command)case a: case a:pri

20、ntf(请输入待删学生信息的序号：);scanf(%d, &pos);temp = list_remove(&lb, pos);if(temp=1) printf(对不起，学生信息删除失败！n);else printf(您好，学生信息已成功删除！n);break;case b:case b:show_list(lb);break;case c:case c:list_destroy(&lb);printf(您好，线性表b已成功删除！n); break; default: printf(对不起，您的输入有误！n); break;break;case c: case c:list_merge(&la, &lb);printf(打印合并后的线性表如下：n);show_list(la);system(pause);return 0;break;default:pr