《华中科技大学《数据结构》课程设计报告》由会员分享，可在线阅读，更多相关《华中科技大学《数据结构》课程设计报告（23页珍藏版）》请在金锄头文库上搜索。
1、课课 程程 设设 计计 报报 告告 课程名称课程名称： 数据结构数据结构 专业班级：专业班级： 学学 号：号： 姓姓 名：名： 指导教师：指导教师： 报告日期：报告日期： 2015-4-17 计算机科学与技术计算机科学与技术 目录目录 实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现1 1.1 问题描述1 1.2 系统设计1 1.3.系统实现1 1.4 效率分析10 实验二实验二 基于链式结构的线性表实现基于链式结构的线性表实现11 2.1 问题描述6 2.2 系统设计6 2.3 系统实现6 2.4 效率分析10 实验三实验三 基于二叉链表的二叉树实现基于二叉链表的二叉树实现11
2、 3.1 问题描述11 3.2 系统设计11 3.3 系统实现11 3.4 效率分析20 四四 实验总结与评价实验总结与评价20 1 实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现 1.1 问题描述问题描述 基于顺序存储结构，实现线性表的基本的、常见的运算。 1.2 系统设计系统设计 1.2.1 提供 14 个功能，分别是： 1. IntiaList 8. PriorElem 2. DestroyList 9. NextElem 3. ClearList 10. ListInsert 4. ListEmpty 11. ListDelete 5. ListLength 12. L
3、istTrabverse 6. GetElem 13. SwitchList 7. LocatElem 0. Exit 1.2.2 物理结构为顺序存储结构，数据元素为包含一个整型变量 item1 的结 构体： typedef struct int item1; Elemtype; typedef struct Elemtype * elem; int length; int listsize; SqList; 1.2.3 构建线性表之前先声明一个头结点，用于存储该表的基本信息和首结 点地址： SqList L1, L2; 1.2.4 本系统使用了如下预定义常量： #define TRUE 1
4、#define FALSE 0 #define OK 2 #define ERROR -1 #define OVERFLOW -2 typedef int status; / Status 是函数的类型，其值是函数结果状态代码 /*-*/ #define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量 #define FILE_SAVE_PATH “.SqList.txt“ /表示数据文件在同级目录下的 SqList.txt 中 1.3.系统实现系统实现 2 1.3.0 ResetSqList
5、 功能 SqList 的方法，将顺序表初始化。 void ResetSqList(SqList * L) /重置顺序表 L-elem = NULL; L-length = 0; L-listsize = 0; 1.3.1InitialList 功能 初始化线性表，传入的是头结点地址。申请一个大小为 LIST_INT_SIZE、类 型为 Elemtype 的线性存储空间，并用头结点中的首结点指针指向该空间首地址。 如果头结点地址已存在则寻问是否进行覆盖操作，若输入“666”则用新地址覆 写原地址。具体实现如下： status IntiaList(SqList * L) /构建一个新的线性表 L
6、if(L-elem!=NULL) int op; printf(“-%40s-n“,“Warning: 当前顺序表已存在，确定覆盖？“); printf(“-%40s-n“,“ps: 输入666确定覆盖，否则退出“); scanf(“%d“, if(666=op) DestroyList(L); else return ERROR; L-elem = (Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype); if(!L-elem) exit(OVERFLOW); /存储分配失败 L-length = 0; /空表长度为 0 L-listsize =
7、 LIST_INIT_SIZE; /初始存储容量 return OK; / IntiaList 1.3.2DestroyList 功能 销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具 体实现如下： status DestroyList(SqList * L) /初始条件：线性表 L 已存在 /操作结果：销毁线性表 L if(L-elem != NULL) free(L-elem); /释放 L-elem 的内存空间 3 ResetSqList(L); /重置 L 中参数 else return ERROR; return OK; / DestroyList 1.3.3Clea
8、rList 功能 与 DestroyList 不同，ClearList 并不直接对物理结构进行操作，而是修改其 逻辑长度值： status ClearList(SqList * L) /初始条件：线性表 L 已存在 /操作结果：将 L 重置为空表 if(L-elem = NULL) return ERROR; L-length = 0; return OK; 1.3.4ListEmpty 功能 判空功能，判断表是否为空表。通过判断顺序表的逻辑长度可轻松判断顺 序表是否为空。实现如下： status ListEmpty(SqList L) /初始条件：线性表 L 已存在 /操作结果：若 L 为空
9、表，则返回 TRUE，否则返回 FALSE if(L.elem = NULL) return ERROR; if(0 = L.length) return TRUE; /L 已经是空表 else return FALSE; 1.3.5ListLenth 功能 求表长。由于表长信息是 SqList 结构的成员之一，其值可以直接获得。 int ListLength(SqList L) /初始条件：线性表 L 已存在 /操作结果：返回 L 中数据元素个数 if(L.elem = NULL) return ERROR; return L.length; 1.3.6GetElem 功能 获取第 i 号元
10、素，传入的是头结点值、元素编号 i、以及用于传递得到的元 素的值的变量的地址。 status GetElem(SqList L,int i,Elemtype * e) /初始条件：线性表 L 已存在，1i | L.length0 ; i-) if(compare(e,L.elemi-1) return i; return -i; /不存在则返回 0 1.3.8PriorElem 功能 求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一 个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用 LocatElem 确定指定元素的位置，如果不是首结点则可直接取到 PriorEle
11、m 的地址。时间复 杂度为 O(n)。具体实现如下： status PriorElem(SqList L,Elemtype cur,Elemtype * pre_e) /初始条件：线性表 L 已存在 /操作结果：若 cur 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱， 否则操作失败，pre_e 无定义 if(L.elem=NULL) return ERROR; int i=LocatElem(L, cur, equal); /查询 cur 的位序 if(iL-length+1) return ERROR; /i 值不合法 if(L-length = L-listsize)
12、 Elemtype *newbase = (Elemtype *)realloc(L-elem, (L- listsize+LISTINCREMENT)*sizeof(Elemtype); if(!newbase) exit(OVERFLOW); L-elem = newbase; L-listsize += LISTINCREMENT; /考虑当前存储空间已满，则增加分配 Elemtype *insert = Elemtype *cur= for( ; cur=insert ; cur-) *(cur+1) = *cur; /插入位置之后的元素依次后移 *insert = e; +L-len
13、gth; return OK; 1.3.11 ListDelete 功能 删除指定编号的数据元素，传入头结点地址、编号 i、表结点类型结构体地 址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执 行删除操作之后，进行“移位”运算。时间复杂度仍为 O(n)。如下： status ListDelete(SqList * L,int i,Elemtype * e) /初始条件：线性表 L 已存在且非空,1length /操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 if(iL-length) return ERROR; /i 值不合法 6 assi
14、gnEle(e, L-elemi-1); for(;ilength;i+) L-elemi-1=L-elemi; -L-length; return OK; 1.3.12 ListTraverse 功能 顺序遍历顺序表元素，传入头结点值、display 函数地址。时间复杂度为 O(n) status ListTrabverse(SqList L, void (* visit)(Elemtype e) /初始条件：线性表 L 已存在 /操作结果：依次对 L 的每个数据元素调用函数 visit()。一旦 visit()失败，则操作失 败 int i; if(!L.length) return ER
15、ROR; for(i=0 ; ielem=NULL) printf(“-%40s-n“,“warning:信息存储失败“); printf(“-%40s-n“,“SqList 不存在“); printf(“-%40s-n“,“返回选择菜单“); fputc(#, pfile); /存储#表示存储失败 return ERROR; fputc(, pfile); fprintf(pfile, “%d“, L-listsize); fputc(, pfile); fprintf(pfile, “%d“, L-length); fputc(, pfile); fwrite(L-elem, sizeof(Elemtype), L-listsize, pfile); printf(“-%40s-n“,“数据存储成功“); printf(“-%40s-n“, FILE_SAVE_PATH); return OK; 8 1.3.16 Boost
