数据结构课程试验报告

课 程 实 验 报 告课程名称： 数据结构 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 计算机科学与技术学院目 录1 课程实验概述12 实验一 基于顺序结构的线性表实现2.1 问题描述22.2 系统设计22.3 系统实现22.4 效率分析23 实验二 基于链式结构的线性表实现3.1 问题描述33.2 系统设计33.3 系统实现33.4 效率分析34 实验三 基于二叉链表的二叉树实现4.1 问题描述44.2 系统设计44.3 系统实现44.4 效率分析45 实验总结与评价51、 课程试验概述数据结构是计算机程序设计的重要理论技术基础，本课程的学习对于理论学习和实验动手都有较高的要求。通过实验，旨在：1、 加深对数据结构和各种算法设计的理解。2、 培养学生的综合动手能力，把课本知识与实际操作相联系。3、 学会撰写规范的实验报告。2、 实验一 基于顺序结构的线性表实现2.1问题描述线性表的数据元素为整型，以顺序存储的结构，主要实现以下功能：初始化线性表，对表赋值，构造线性表查找指定位置的元素在指定位置插入元素删除指定位置的元素2.2系统设计顺序储存结构，定义一个结构类型的数据项：typedef struct int *elem; int length; int listsize;SqList创建一个新的顺序表InitList_Sq(SqList *pL)插入元素ListInsert (SqList *,int i,int e pL);函数在顺序表中插入元素，其中Sqlist*L为需要插入元素的顺序表，int i 为插入位置，int e为需要插入的元素。查找元素LocateElem_Sq(SqList *pL,int e)其中SqList*L为操作的顺序表,int e为要查找的元素位置。删除元素ListDelete_Sq(SqList *pL,int i,int *e)其中Sqlist*L为操作的顺序表，int i为元素在顺序表中的位置。2.3系统实现主菜单1、 构造新的线性表2、 加载数据3、 插入元素 在表尾插入元素64、 删除元素删除表头元素15、 查找元素查找元素1 查找元素22.4效率分析创建顺序表，时间复杂度O(1)插入元素，需要遍历顺序表，并将出入位置后的元素都后移动一位，时间复杂度O(n),空间复杂度O(n)查找元素，需要遍历顺序表，时间复杂度0(n),空间复杂度为O(n)删除元素，需要遍历顺序表，并将删除元素位置后的元素都前移一位，时间复杂度为O(n),空间复杂度为O(n)。3实验二 基于链式结构的线性表实现3.1问题描述：基于链式存储结构，实现线性表的基本的，常见的运算。主要实现以下功能提供一个实现各种功能的演示系统，包括插入，查找，删除，交换等功能。具体的物理结构和数据元素类型自行选定线性表数据可以使用磁盘文件永久保存。 3.2系统设计：链式表的创建，定义一个结构类型的数据项，存放链式表的基本信息：typedef struct LNode int data; struct LNode *next;LNode;插入元素ListInsert (SqList *,int i,int e pL);函数在顺序表中插入元素，其中Sqlist*L为需要插入元素的顺序表，int i 为插入位置，int e为需要插入的元素。查找元素LocateElem_Sq(SqList *pL,int e)其中SqList*L为操作的顺序表,int e为要查找的元素位置。删除元素ListDelete_Sq(SqList *pL,int i,int *e)其中Sqlist*L为操作的顺序表，int i为元素在顺序表中的位置。3.3系统实现：主界面1、 构造线性表2、 加载数据3、 插入元素表头插入1表位插入84、 删除元素删除表尾元素8继续删除表尾元素7删除表头元素15、 查找元素查找元素1查找元素53.4效率分析创建空链表，时间复杂度为O(1),空间复杂度为O(1)插入元素，在插入数据时，需要遍历链式表，时间复杂度为O（n）,空间复杂度为O(n)查找元素，需要遍历链式表，时间复杂度为O（n）,空间复杂度为O(n)删除元素，删除元素需要遍历链式表以找出所需要删除的位置，时间复杂度为O（n）,空间复杂度为O(n)。4 实验三 基于二叉链表的二叉树实现4.1问题描述基于二叉链表，实现二叉树的下列运算。二叉树的生成前序，中序和后序的遍历计算叶子数目按层次遍历求二叉树的高度4.2系统设计基于二叉链表实现二叉树的基本操作，元素数据类型为char.根据实验要求，先创建一个二叉树，然后进行各种操作，实现程序设计所需要的功能。1.创建二叉树typedef struct BiTreeNode char data; struct BiTreeNode *lchild; struct BiTreeNode *rchild; BiTreeNode;2.遍历void PreOrderTree(BiTreeNode *pBiTreeNode ); 前序递归遍历二叉树void InOrderTree(BiTreeNode *pBiTreeNode); 中序递归遍历二叉树void PostOrderTree(BiTreeNode *pBiTreeNode ); 后序递归遍历二叉树void PreOrderTree1(BiTreeNode *pBiTreeNode); 先序非递归遍历二叉树void InOrderTree1(BiTreeNode *pBiTreeNode); 中序非递归遍历二叉树void PostOrderTree1(BiTreeNode *pBiTreeNode ); 后序非递归遍历二叉树3.计算叶子数目int LeafCount(BiTreeNode *pBiTreeNode); 求二叉树的叶子个数int LeafCount1(BiTreeNode *pBiTreeNode);非递归求二叉树的叶子个数4.求二叉树的高度int Depth(BiTreeNode *pBiTreeNode);计算二叉树的深度int Depth1(BiTreeNode *pBiTreeNode); 非递归计算二叉树的深度4.3系统实现主界面二叉树为：ad#ef#g#b#c# 前序遍历中序遍历后序遍历：层次遍历：计算叶子数目：二叉树高度：4.4效率分析：1.二叉树的建立采用递归的方法建立二叉树设节点数位N时，函数的平均运行时间为F（n）设M为左子树的节点个数且f(0)=f(1)=1解递归式得：T（n）=0(n)递归栈的平均空间需求为：S(n)=(log nn)遍历二叉树2.前序遍历首先访问当前的根节点，然后递归的访问左儿子的节点和右儿子的节点设节点数为N时，函数的平均运行时间为f（n）设M为左子树的节点个数且f(0)=f(1)解递归式得T（n）=0（n）3.叶子数目计算递归调用该函数求得左子树叶子数目和右子树叶子数目，设节点数为n时，函数的平均运行时间为f(n)设m为左子树的节点个数且f(o)=f（1）=1解递归式有：T（n）=O(n)4求二叉树的高度若为空树，返回0，否则递归返回，左右子树中较高的高度+1，设节点数位N时，函数的平均运行时间为f(n)，设m为左子树的节点个数，且f(o)=f（1）=1解递归式得：T(n)=O(n)5实验总结与评价通过三次实验，增强动手能力，加强了对课本知识的理解，将理论知识与实际操作相结合，这是当前我们最需要锻炼的，很多人往往掌握了许多理论知识，却无法应用到实际中去。而在实际操作，编写程序，算法设计会遇到许多意向不到的问题，这些往往是课本上没有的。比如线性表创建时的返回地址，指针变量定义的局域。这些都必须在实验进行更深入的理解与体会。而实验设计虽然达到了基本要求，但是仍有许多东西直接改进，许多功能可以加以改进。这些希望在以后得到改进。源代码：实验一：#include #include #include#include menu.h#define End_e 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct int *elem; int length; int listsize;SqList;void InitList_Sq(SqList *pL);void Input_Data(SqList *pL);void Save_Data(SqList *pL);void Load_Data(SqList *pL);void Traverse_cross_L(SqList *pL);void ListInsert_Sq(SqList *pL,int i, int e);void ListDelete_Sq(SqList *pL,int i,int *e);void LocateElem_Sq(SqList *pL,int e);void ChangeList_Sq(SqList *pL,int i, int e);int main() SetConsoleTitle(gp_sys_name); int a,c;L1: L_menu(); SqList L,*pL=&L;L2: printf(请在菜单中选择操作功能：); scanf(%d,&c); switch(c) case 1: InitList_Sq(pL); printf(n线性表已经构造好n是否录入数据？ (输入 0 则不录入数据，否则录入数据)n); scanf(%d,&a); if(a) Input_Data(pL); scanf(%d,&a); if(a) Save_Data(pL); scanf(%d,&a); if(a) system(cls); goto L1; else printf(n数据未保存！nn按任意键退出！n); else printf(n未执行数据录入函数nn按任意键退出！n); break; case 2: InitList_Sq(pL); Load_Data(pL); printf(n数据加载成功！是否显示？(输入 0 则不显示，否则显示)nn); scanf(%d,&a); if(a) printf(n已存储的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(是否继续？(输入 0 则不继续，否则继续)n); scanf(%d,&a); if(a) goto L2; break; case 3: InitList_Sq(pL); Load_Data(pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(请输入要在原来线性表的第 i 个元素之前插入元素 e:n); int i,e; scanf(%d%d,&i,&e); ListInsert_Sq(pL, i, e); printf(n插入新元素之后线性表中的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(是否保存修改？(输入 0 则不保存，否则保存数据)n); scanf(%d,&a); if(a) Save_Data(pL); scanf(%d,&a); if(a) system(cls); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; case 4: InitList_Sq(pL); Load_Data(pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(请输入要删除第 i 个元素 ti=); int i2,e2; scanf(%d,&i2); ListDelete_Sq(pL,i2,&e2); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(被删除的是第 %d 个元素 e=%dn,i2,e2); printf(是否保存修改？(输入 0 则不保存，否则保存数据)n); scanf(%d,&a); if(a) Save_Data(pL); scanf(%d,&a); if(a) system(cls); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; case 5: InitList_Sq(pL); Load_Data(pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(请输入所要查找的元素 te=); int e3; scanf(%d,&e3); LocateElem_Sq(pL,e3); printf(n是否继续？(输入 0 则不继续，否则继续)n); scanf(%d,&a); if(a) system(cls); goto L1; else printf(n按任意键退出！n); break; case 6: InitList_Sq(pL); Load_Data(pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(请输入所要用 e 来替换 第 i 个元素 te，i=); int e4,i4; scanf(%d%d,&e4,&i4); ChangeList_Sq(pL,i4,e4); printf(n替换成功！替换之后线性表的数据是：n); Traverse_cross_L(pL); printf(表长 L.length= %dnn,pL-length); printf(是否保存修改？(输入 0 则不保存，否则保存数据)n); scanf(%d,&a); if(a) Save_Data(pL); scanf(%d,&a); if(a) system(cls); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; default:printf(n选择错误！请重新再选！nn); goto L2; return 0;void InitList_Sq(SqList *pL) pL-elem=(int *)malloc(LIST_INIT_SIZE * sizeof(int); if(!pL-elem) printf(线性表构造失败！n); exit(-1); pL-length=0; pL-listsize=LIST_INIT_SIZE;void Input_Data(SqList *pL) int i=0; printf(请输入数据，以0结束：n); do scanf(%d,&(pL-elemi); i+; pL-length+; while(pL-elemi-1!=End_e); printf(表长L.length=%dnn,pL-length-1); printf(数据录入完毕，是否保存？ (输入 0 则不保存，否则保存数据)n);void Save_Data(SqList *pL) FILE *out; int i=0; if(out=fopen(data.dat,wb)=NULL) exit(-1); while(ilength) fwrite(pL-elem,sizeof(int),1,out); i+; (pL-elem)+; fclose(out); printf(n数据已存盘成功！是否继续？(输入 0 则不继续，否则继续)n);void Load_Data(SqList *pL) FILE *in; int *p=pL-elem; if(in=fopen(data.dat,rb)=NULL) exit(-1); while(!feof(in) fread(pL-elem,sizeof(int),1,in); pL-elem+; fclose(in); pL-elem=p;void Traverse_cross_L(SqList *pL) int i=0; pL-length=0; while (pL-elemi!=End_e) printf(%dt,pL-elemi); i+; pL-length+; printf(nn);void ListInsert_Sq(SqList *pL,int i, int e) int *newbase,j; j=pL-length; if(ipL-length+1) printf(n位置不存在n); exit(-1); if(pL-length=pL-listsize) newbase=(int *)realloc(pL-elem,(pL-listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(-1); pL-elem=newbase; pL-listsize += LISTINCREMENT; while(j=i-1) pL-elemj+1=pL-elemj; j-; pL-elemi-1=e; printf(插入成功！n);void ListDelete_Sq(SqList *pL,int i,int *e) if(ipL-length) printf(元素不存在n); exit(-1); *e=pL-elemi-1; for(i=i;ilength;i+) pL-elemi-1=pL-elemi; -pL-length; printf(元素删除成功,删除后的数据是：n);void LocateElem_Sq(SqList *pL,int e) int i=0; while (pL-elemi!=e & ilength) i+; if(pL-elemi=e ) printf(n元素找到，%d是线性表中第 %d 个元素n,e,i+1); else printf(n没有所要查找的元素！n);void ChangeList_Sq(SqList *pL,int i, int e) if(ipL-length) printf(n元素不存在n); exit(-1); pL-elemi-1=e;实验二：#include #include #include#include menu.h#define End_e 0typedef struct LNode int data; struct LNode *next;LNode;void Create_L(LNode *pL);void Save_Data( LNode*pL);void Load_Data(LNode *pL);void Traverse_cross_L(LNode *pL);void ListInsert_L(LNode *pL,int i, int e);void ListDelete_L(LNode *pL,int i,int *e);void LocateElem_L(LNode *pL,int e);void ChangeList_L(LNode *pL,int i, int e);int main() SetConsoleTitle(gp_sys_name); int a,c;L1: L_menu(); LNode *pL=NULL;L2: printf(请在菜单中选择操作功能：); scanf(%d,&c); switch(c) case 1: Create_L(&pL); scanf(%d,&a); if(a) Save_Data(pL); printf(n数据已存盘成功！是否继续？n); scanf(%d,&a); if(a) system(cls); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; case 2: /*数据加载*/ Load_Data(&pL); printf(n数据加载成功！是否显示？(nn); scanf(%d,&a); if(a) printf(n已存储的数据是：n); Traverse_cross_L(pL); printf(n是否继续？n); scanf(%d,&a); if(a) goto L2;/*继续执行其他功能*/ break; case 3: /*插入新元素*/ Load_Data(&pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(在原来线性表的第 i 个元素之前插入元素 e:n); int i,e; scanf(%d%d,&i,&e); ListInsert_L(&pL, i, e); printf(插入新元素之后线性表中的数据是：n); Traverse_cross_L(pL); printf(是否保存修改？(n); scanf(%d,&a); /*判断是否保存数据*/ if(a) Save_Data(pL); Load_Data(&pL);/*因为链表是后进先出的，所以经过保存一次再加载*/ Save_Data(pL); /*再保存，这样元素的顺序就和原来保持一致了*/ printf(n数据已存盘成功！是否继续？n); scanf(%d,&a); /*判断是否继续*/ if(a) system(cls); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; case 4:/*删除指定的元素*/ Load_Data(&pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(请输入要删除第 i 个元素 ti=); int i2,e2; scanf(%d,&i2); ListDelete_L(&pL,i2,&e2); Traverse_cross_L(pL); printf(被删除的是第 %d 个元素 e=%dn,i2,e2); printf(是否保存修改？n); scanf(%d,&a); /*判断是否保存数据*/ if(a) Save_Data(pL); Load_Data(&pL);/*因为链表是后进先出的，所以经过保存一次再加载*/ Save_Data(pL); /*再保存，这样元素的顺序就和原来保持一致了*/ printf(n数据已存盘成功！是否继续？n); scanf(%d,&a); /*判断是否继续*/ if(a) system(cls); free(pL); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; case 5:/*查找元素*/ Load_Data(&pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(请输入所要查找的元素 te=); int e3; scanf(%d,&e3); LocateElem_L(pL,e3); printf(n是否继续？)n); scanf(%d,&a); /*判断是否继续*/ if(a) system(cls); free(pL); goto L1; else printf(n按任意键退出！n); break; case 6:/*元素的替换*/ Load_Data(&pL); printf(n原来线性表中已存储的数据是：n); Traverse_cross_L(pL); printf(请输入所要用 e 来替换 第 i 个元素 te，i=); int e4,i4; scanf(%d%d,&e4,&i4); ChangeList_L(pL,i4,e4); Traverse_cross_L(pL); printf(是否保存修改？n); scanf(%d,&a); /*判断是否保存数据*/ if(a) Save_Data(pL); Load_Data(&pL);/*因为链表是后进先出的，所以经过保存一次再加载*/ Save_Data(pL); /*再保存，这样元素的顺序就和原来保持一致了*/ printf(n数据已存盘成功！是否继续？n); scanf(%d,&a); /*判断是否继续*/ if(a) system(cls); free(pL); goto L1; else printf(n数据未保存！nn按任意键退出！n); break; default:printf(n选择错误！请重新再选！