华中科技大学 数据结构 实验报告.doc

课课 程程 实实 验验 报报 告告 课程名称：课程名称： 数数 据据 结结 构构 专业班级：专业班级：华中科技大学材控华中科技大学材控 1402 班班 学学 号：号： U201411219 姓姓 名：名： 张煌张煌 指导教师：指导教师： 袁凌袁凌 报告日期：报告日期： 2016 年年 5 月月 20 日日 计算机科学与技术学院计算机科学与技术学院 目录目录 实验报告要求说明.1 1 基于顺序存储结构实现线性表的基本运算.1 1.1 问题描述.1 1.2 顺序表演示系统设计.1 1.2.1 系统总体设计.1 1.2.2 有关常量和类型定义.1 1.2.3 算法设计.1 1.3 顺序表演示系统实现与测试.1 1.3.1 系统实现.1 1.3.2 系统测试.1 1.4 实验小结.2 2 基于链式存储结构实现线性表的基本运算.3 2.1 问题描述.3 2.2 单链表演示系统设计.3 2.2.1 系统总体设计.3 2.2.2 有关常量和类型定义.3 2.2.3 算法设计.3 2.3 单链表演示系统实现与测试.3 2.3.1 系统实现.3 2.3.2 系统测试.3 2.4 实验小结.3 参考文献.5 1 课程实验概述课程实验概述 本次课程实验旨在加强学生课堂理论学习之后增强上机能力，熟练掌握并 应用数据结构中的两种逻辑结构的典型代表线性表和树。线性表的顺序存 储具有随机存取的功能，而链式存储能有效的利用动态存储空间，学会合理的 选择这两种存储方式，看似简单，但在实际应用具有很大的用处。而树（二叉 树）是非线性逻辑结构的代表，树模型的建立可以说完全建立在递归思想之上， 树的几乎所有操作都涉及到递归调用，当然我们也可以用栈来实现非递归调用， 但是其思想也是相近的。因此树的实验旨在帮助我们递归思想的建立和成熟。 2 实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现 2.1 实验内容与要求实验内容与要求 实验内容：基于顺序存储结构，实现线性表 ADT，具有 10 种基本运算。 具体要求：1.提供一个实现功能的演示系统。 2.具体物理结构和数据元素类型自定。 3.线性表数据可以使用磁盘文件永久保存。 2.2 程序概要设计程序概要设计 1.明确基本功能 程序需要实现的 12 个基本功能分别是：IntiaList（初始化）， DestroyList（摧毁线性表），ClearList（清空线性表），ListEmpty（判断表空） ，ListLength（求表长），GetElem（取表中元素），LocatElem（获得元素地址） ，PriorElem（取前继），NextElem（取后继）。ListInsert（插入）， ListDelete（删除），ListTrabverse（遍历显示），此外还有辅助功能： Load（载入），Save（保存） 2.确定各功能实现的函数参数 status IntiaList(SqList * L); status DestroyList(SqList * L); status ClearList(SqList L); status ListEmpty(SqList L); int ListLength(SqList L); status GetElem(SqList L,int i,Elemtype *e); int LocatElem(SqList L,Elemtype *e); status PriorElem(SqList *L,Elemtype cur,Elemtype * pre_e); status NextElem(SqList L,Elemtype cur,Elemtype * next_e); status ListInsert(SqList *L, Elemtype e,int i); status ListDelete(SqList * L,Elemtype * e,int i); status ListTrabverse(SqList L,void (* visit)(Elemtype e); void Save(SqList L); status Load(SqList*L); 2.3 数据结构与算法设计数据结构与算法设计 为了满足概述中的功能，结合线性表结构，给出以下结构的定义： typedef int status; typedef struct int item1; Elemtype; typedef struct Elemtype * elem; int length; int listsize; SqList,*L; 算法设计： 1.IntiaList： 初始化线性表，传入的是头结点地址。申请一个大小为 LIST_INT_SIZE、 类型为 Elemtype 的线性存储空间，并用头结点中的首结点指针指向该空间首地 址。 2.DestroyList： 销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。 3.ClearList： 与 Destroy 类似但是又有不同，ClearList 并不销毁物理空间，而是修改逻 辑关系值。 4.ListEmpty： 判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需 要对头结点进行修改。若长度为 0，表空，否则不空。 5.ListLength： 求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接 调用并显示即可。 6.GetElem： 获取第 i 号元素，传入的是头结点值、元素编号 i、以及出口表结点地址。 7.LocatElem： 取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结点 值、equal 函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号 i。 8.PriorElem： 求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一 个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用 LocatElem 确定指定元素的位置，如果不是首结点则可直接取到 PriorElem 的地 址。 9.NextElem： 与 PriorElem 功能类似，不再赘述。 10.ListInset： 插入一个数据元素，传入头结点地址、插入位置 i、临时表结点值。在调用 插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数， 插入前先判断插入位置是否合理，再判断是否“满载”。如果满载则重新申请 更大的存储空间。接下来正式插入数据元素，“先空位置再插入”。 11.ListDelete: 删除一个数据元素，传入头结点地址、删除位置 i。删除前先判断位置是否 合理，先删除元素，然后将所有删除元素之后的元素前移一个位置。 12.ListTrabverse: 传入头结点，循环访问各个元素，直至到表尾停止。 2.4 输入输出设计输入输出设计 1.输入： 在输入方面，我采用了用户自定义输入的方式，既可以采用用户自行输入， 又可以载入之前保存的数据。在每次操作之后，会提示是否保存刚才的数据， 以便下次再次使用，以下是用户自行输入的功能实现： void creat(SqList *L) int a=0; printf("Input the number of your datas?n"); scanf("%d", L->elem=(Elemtype*)malloc(a*sizeof(Elemtype); L->length=a; int i; printf("Please input your datan"); for (i=1;ielemi.item1); L->listsize=LIST_INIT_SIZE; printf("You have to save your data"); getchar(); Save(*L); 2.输出： 采用遍历输出，即功能 10 的输出。 2.5 源程序及注释源程序及注释 /* Linear Table On Sequence Structure */ #include #include #include #include #define LIST_INIT_SIZE 10 #define OK 1 #define FALSE 0 #define TRUE 1 #define ERROR -1 #define OVERFLOW -2 #define LISTINCREMENT 1 /*-*/ typedef int status; typedef struct int item1; Elemtype; typedef struct Elemtype * elem; int length; int listsize; SqList,*L; int changed=0; /*-*/ status IntiaList(SqList * L); status DestroyList(SqList * L); status ClearList(SqList L); status ListEmpty(SqList L); int ListLength(SqList L); status GetElem(SqList L,int i,Elemtype *e); int LocatElem(SqList L,Elemtype *e); status PriorElem(SqList *L,Elemtype cur,Elemtype * pre_e); status NextElem(SqList L,Elemtype cur,Elemtype * next_e); status ListInsert(SqList *L, Elemtype e,int i); status ListDelete(SqList * L,Elemtype * e,int i); status ListTrabverse(SqList L,void (* visit)(Elemtype e); /*-*/ status compare(Elemtype e1,Elemtype e2); status equal(Elemtype x, Elemtype y); void display(Elemtype e); void Save(SqList L); status Load(SqList*L); void creat(SqList *L); /*-*/ void menu(void); /*-*/ char file020; int main(void) SqList L; L.listsize=LIST_INIT_SIZE; int op=0; char req; do system("cls"); menu(); printf("Do you want to input new liear table?Y/N"); req=getchar();getchar(); if (req=Y |req=y) creat( else printf("Do you want to load saved data?Y/N"); req=getchar(); if (req=Y |req=y) while (!Load( else printf("You still use the data use before!n"); getchar(); getchar(); system("cls"); menu(); printf(" Then please input your option0-12:"); scanf("%d", switch(op) case 0: break; case 1: printf("n here is IntiaList(),which being realizedn");getchar();getchar(); if (IntiaList(getchar();getchar(); /printf("Dou you want to save?Y/N") else printf("Not realised!n"); getchar();getchar(); break; case 2: printf("n here is DestroyList(),which being realizedn"); getchar();getchar(); if (DestroyList( getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 3: printf("n here is ClearList(),which being realizedn"); getchar();getchar(); if (ClearList(L) printf("Successfully realized!n"); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 4: printf("n here is ListEmpty(),which being realizedn"); getchar();getchar(); if (ListEmpty(L) printf("It is an empty listn"); getchar();getchar(); else printf("It is not an empty listn"); getchar();getchar(); break; case 5: printf("n here is ListLength() ,which being realizedn"); if ( printf("Successfully realized!The length of L is %dn",ListLength(L); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 6: printf("n here is GetElem(),which being realizedn"); getchar();getchar(); int i; Elemtype e; printf("which elem do you want to pick?i=?"); scanf("%d", if (GetElem(L,i, printf("And the %dth elem data is %d",i,e.item1); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 7: printf("n here is LocatElem(),which being realizedn"); getchar();getchar(); int t,i,a; Elemtype e; printf("What do you want to locate?item="); scanf("%d", for (i=1;i<=L.length;i+) if (L.elemi.item1=t) break; if (i=L.length+1) printf("There is no such item in this list!n"); e=L.elemi; if (a=LocatElem(L, printf("e is in the %dth locationn",a); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 8: printf("n here is PriorElem(),which being realizedn"); getchar();getchar(); Elemtype e,cur; int i; printf("To find the prio of who?i="); scanf("%d", cur=L.elemi; if (PriorElem( printf("And the prio of elem%d is %dn",i,e.item1); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 9: printf("n here is NextElem(),which being realizedn"); getchar();getchar(); Elemtype e,cur; int i; printf("To find the next of who?i="); scanf("%d", cur=L.elemi; if (NextElem(L,cur, printf("And the nextelem of elem%d is %dn",i,e.item1); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 10: printf("n here is ListInsert(),which being realizedn"); getchar();getchar(); int i,j; Elemtype e; printf("choose where to insert?i="); scanf("%d", printf("nInsert new data="); scanf("%d", if (ListInsert( printf("the list data is now:n"); for (j=1;j<=L.length;j+) printf("%d ",L.elemj.item1); getchar();getchar(); else printf("Not realised!n"); getchar();getchar(); break; case 11: printf("n here is ListDelete(),which being realizedn"); getchar();getchar(); int i,j; Elemtype *e; printf("choose where to delete?i="); scanf("%d", if (ListDelete( printf("The deleted data is %dn",(*e).item1);getchar();getchar(); printf("the list data is now:n"); for (j=1;jelem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype); if (!L) exit(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; status DestroyList(SqList * L) free(L); L=NULL; char req; printf("Are you sure to destroy the file?Y/N"); req=getchar(); if (req=y|req=Y) remove(file0); printf("The file has been destroyed!n"); return OK; status ClearList(SqList L) L.length=0; return OK; status ListEmpty(SqList L) if (L.length=0) return TRUE; else return FALSE; int ListLength(SqList L) return L.length; status GetElem(SqList L,int i, Elemtype * e) if (!(L.length=0|iL.length) *e=L.elemi; return OK; else return ERROR; int LocatElem(SqList L,Elemtype *e) int i; for(i=1;ielem) return ERROR; else for(i=1;ilength;i+) if (compare(L->elemi,cur) break; if(i=1) return FALSE; else *pre_e=(L->elemi-1); return OK; status NextElem(SqList L,Elemtype cur,Elemtype * next_e) int i; if(!L.elem) return ERROR; else for(i=1;ilength=0) L->length+; L->elem1=e; return OK; if(iL->length) return FALSE; if(L->length>=L->listsize) newbase=(Elemtype*)realloc(L->elem,(L- >listsize+LISTINCREMENT)*sizeof(Elemtype); if(!newbase) return(OVERFLOW); L->elem=newbase; L->listsize+=LISTINCREMENT; q= for(p=p>=q;p-) *(p+1)= *p; *q=e; +L->length; return OK; status ListDelete(SqList * L,Elemtype * e, int i) Elemtype *q,*p; if(!L->elem) return ERROR; if(iL->length) return FALSE; q= for(p=p>=q;p-) *p= *(p+1); (*e)=L->elemi; -L->length; return OK; status ListTrabverse(SqList L, void (* visit)(Elemtype e) int i; if(!L.length) return(0); printf("n-all elements of liear table-n"); for(i=1;i<=L.length;i+) visit(L.elemi); return(1); status compare(Elemtype e1 ,Elemtype e2 ) if (e1.item1=e2.item1) return OK; else return FALSE; /*-*/ void menu(void) printf("nn"); printf(" Menu for Linear Table On Sequence Structure n"); printf("-n"); printf(" 1. IntiaList 7. LocatElemn"); printf(" 2. DestroyList 8. PriorElemn"); printf(" 3. ClearList 9. NextElem n"); printf(" 4. ListEmpty 10. ListInsertn"); printf(" 5. ListLength 11. ListDeleten"); printf(" 6. GetElem 12. ListTrabversen"); printf(" 0. Exitn"); printf("-n"); /*-*/ status equal(Elemtype x, Elemtype y) return (x.item1=y.item1); void display(Elemtype e) printf("%d ",e.item1); void Save(SqList L) FILE* fp=NULL; int i; char file120; do puts("nt creating data file."); puts("n please input the file name:"); gets(file1); if (fp=fopen(file1, "wb")=NULL) puts("nfile cannot open!"); printf("press ENTER to continue."); getchar(); while (fp=NULL); for (i=1;ielem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype); if (changed) char req; puts("nYou have not saved,save nowY/N?"); req=getchar(); getchar(); if (req=Y | req=y) Save(*L); do puts("nLoading data now."); puts("nPlease input the file name:"); getchar(); gets(file1); if (fp=fopen(file1,"rb")=NULL) puts("nThe file cannot open!"); printf("press ENTER to continue."); getchar(); while (fp=NULL); int i=1; L->length=0; while (!feof(fp) if (ilistsize) fread( else printf("Loading overflown"); getchar(); fclose(fp); return ERROR; L->length=i+; L->length-; printf("Loading a %d lenth List",L->length); getchar(); puts("nSuccessf