《数据结构与算法综合设计实验1实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构与算法综合设计实验1实验报告.doc（16页珍藏版）》请在三一办公上搜索。
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(&L
21、a, &Lb);printf(打印合并后的线性表如下：n);show_list(La);system(pause);return 0;break;default:printf(谢谢您的使用。n);system(pause);return 0;break;system(pause);return 0;九、程序运行结果：1.主界面：2.单线性表的操作（以A为例）： （1）打印线性表A中的信息（2） 删除线性表A删除前（注意第二个学生）删除后（3）删除线性表A3，合并A,B线性表。打印A表打印B表合并后线性表十、实验结论：1.本实验通过定义单向链表的数据结构，设计创建链表、插入结点、遍历结点等基本算
22、法，使我们掌握线性链表的基本特征和算法，并能熟练编写C程序，培养理论联系实际和自主学习的能力，提高程序设计水平。2.可以从中了解线性表的优缺点。优点，当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。缺点，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。顺序存储插入与删除一个元素，必须移动大了的数据元素，以此对大的线性表，特别是在元素的插入和删除很频繁的情况下，采取顺序存储很是不方便，效率低；顺序存储空间容易满，出现上溢，程序访问容易出问题，顺序存储结构下，存储空间不便扩充；顺序存储空间的分配问题，分多了浪费，分少了空间不足上溢。十一、总结及心得体会：
