华中科技大学 数据结构 实验报告.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 data\n"); for (i=1;ielem[i].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 file0[20]; 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 option[0-12]:"); scanf("%d", switch(op){ case 0: break; case 1: {printf("\n here is IntiaList(),which being realized\n");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 realized\n"); getchar();getchar(); if (DestroyList( getchar();getchar();} else { printf("Not realised!!\n"); getchar();getchar();} break;} case 3: {printf("\n here is ClearList(),which being realized\n"); 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 realized\n"); getchar();getchar(); if (ListEmpty(L)){ printf("It is an empty list\n"); getchar();getchar();} else { printf("It is not an empty list\n"); getchar();getchar();} break;} case 5: {printf("\n here is ListLength() ,which being realized\n"); if ( printf("Successfully realized!The length of L is %d\n",ListLength(L)); getchar();getchar();} ^` else { printf("Not realised!!\n"); getchar();getchar();} break;} case 6: {printf("\n here is GetElem(),which being realized\n"); 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 realized\n"); 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.elem[i].item1==t) break; } if (i==L.length+1) printf("There is no such item in this list!\n"); e=L.elem[i]; if (a=LocatElem(L, printf("e is in the %dth location\n",a); getchar();getchar();} ^` else { printf("Not realised!!\n"); getchar();getchar();} break;} case 8: {printf("\n here is PriorElem(),which being realized\n"); getchar();getchar(); Elemtype e,cur; int i; printf("To find the prio of who?i="); scanf("%d", cur=L.elem[i]; if (PriorElem( printf("And the prio of elem[%d] is %d\n",i,e.item1); getchar();getchar();} else { printf("Not realised!!\n"); getchar();getchar();} break;} case 9: {printf("\n here is NextElem(),which being realized\n"); getchar();getchar(); Elemtype e,cur; int i; printf("To find the next of who?i="); scanf("%d", cur=L.elem[i]; if (NextElem(L,cur, printf("And the nextelem of elem[%d] is %d\n",i,e.item1); getchar();getchar();} else { printf("Not realised!!\n"); getchar();getchar();} break;} ^` case 10: {printf("\n here is ListInsert(),which being realized\n"); 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.elem[j].item1); getchar();getchar();} else { printf("Not realised!!\n"); getchar();getchar();} break;} case 11: {printf("\n here is ListDelete(),which being realized\n"); getchar();getchar(); int i,j; Elemtype *e; printf("choose where to delete?i="); scanf("%d", if (ListDelete( printf("The deleted data is %d\n",(*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.elem[i]; 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->elem[i],cur))) break; } if(i==1) return FALSE; else{ *pre_e=(L->elem[i-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->elem[1]=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->elem[i]; ^` --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.elem[i]); return(1); } status compare(Elemtype e1 ,Elemtype e2 ){ if (e1.item1==e2.item1) return OK; else return FALSE; } /*------------------------------------------------------*/ void menu(void){ printf("\n\n"); printf(" Menu for Linear Table On Sequence Structure \n"); printf("------------------------------------------------------\n"); printf(" 1. IntiaList 7. LocatElem\n"); printf(" 2. DestroyList 8. PriorElem\n"); printf(" 3. ClearList 9. NextElem \n"); printf(" 4. ListEmpty 10. ListInsert\n"); printf(" 5. ListLength 11. ListDelete\n"); printf(" 6. GetElem 12. ListTrabverse\n"); printf(" 0. Exit\n"); 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 file1[20]; do { puts("\n\t 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 overflow\n"); getchar(); fclose(fp); return ERROR; } L->length=i++; L->length--; } printf("Loading a %d lenth List",L->length); getchar(); ^` puts("\nSuccessf