数据结构实验报告-物联网工程.docx

1、中南大学数据结构实 验 报 告目录实验一 线性表的操作算法3一、需求分析3二、概要设计3三、详细设计6四、调试分析26五、测试结果27六、附录29实验二 二叉树的操作算法30一、需求分析30二、概要设计30三、详细设计34四、调试分析42五、测试结果42六、附录44实验三 图的操作算法45一、需求分析45二、概要设计45三、详细设计45四、调试分析45五、测试结果45六、附录45实验四 排序算法的实现46一、需求分析46二、概要设计46三、详细设计46四、调试分析46五、测试结果46六、附录46实验一 线性表的操作算法一、需求分析1.实验要求：分别用数组和链表作为存储结构，实现线性表的插入、删

2、除、查找、排序、合并等操作。2.实验分析：1）构成线性表，且能进行排序的合法字符：大写或者小写字母、整形（包括但不限于int、long、unsigned等数据类型）数据，浮点型（包括但不限于float、double等数据类型）数据。2）程序以用户和计算机的对话方式进行，用户通过程序中的提示语句进入相关子程序完成相关任务。用户可以选择顺序表和链表两种形式来进行相关操作。另外，应要求先创建好线性表（包括顺序表和链表），再完成插入，删除，查找，二路归并，排序等功能。3）程序执行的命令：A. 创建线性表（线性表均表示顺序表和链表两种形式的顺序表，下同），提示用户输入线性表中的数据；注：以下B、C、D、

3、E、F五个步骤并无先后顺序，用户可以根据自己的需要进行相关操作。B. 进行线性表的插入操作：提醒用户输入数据的位置信息和内容信息，并且显示线性表插入以后的结果，以检验是否正确进行了操作（之后每一步也都应有此验证步骤）；C. 进行线性表的删除操作：用户可以选择通过数据的位置信息还是内容信息进行删除；D. 进行线性表的查找操作：用户在自己选定的线性表类型中均可以进行按值返址和按址返值两个操作；E. 进行线性表的排序操作：这里的排序是指外部排序，而且对排序的有效性和可靠性均无较高要求，可以使用冒泡排序、简单选择排序、二路归并排序，希尔排序等各种方法。F. 进行线性表的归并操作：进行归并合作之前应该提

4、前进行好排序的操作，这里可以在归并操作中帮助用户再次进行排序，之后完成归并操作。4）输入过程中能自动滤去合法字符以外的其他字符，并能在输入不当时输入相应的提示信息。5）测试数据：见“测试结果”二、概要设计1.抽象数据类型：typedef struct DySqListint *elem;int len;int cursize;*DySqPtr;typedef struct LNodeint data;struct LNode *next;*LinkList,LNode;ADT List数据对象：D=ei | i=1,2,3,n; n=0; ei AtomSet/AtomSet为某个数据对象数据

5、关系：R=| ei-1,ei D,2=i=n基本操作：Init_List(ListPtr L);操作结果：创建空的顺序表，初始化DySqList中的成员。Creat_List(ListPtr L);初始条件：L是已经进行了初始化的空顺序表。操作结果：创建一个顺序表，输入表中数据。Display_List(ListPtr L);初始条件：顺序表L存在，且非空表。操作结果：把表中元素依次输出。GetLct_List(ListPtr L, int i);初始条件：顺序表L存在，且非空表。操作结果：获取一个元素的内容信息在表中的位置，并返回该位置，若未找到，则返回-1。GetElem_List(Lis

6、tPtr L, int e);初始条件：顺序表L存在，且非空表。操作结果：获取一个元素的内位置信息在表中的内容，并返回该内容，若未找到，则返回-1。GetLen_List(ListPtr L);初始条件：顺序表L存在。操作结果：返回该线性表的长度。Delete_List_Ord(ListPtr L, int i);初始条件: 顺序表L存在，且非空表。操作结果：按照元素的位置信息删除该元素。Delete_List_Val(ListPtr L,int i);初始条件：顺序表L存在，且非空表。操作结果: 按照元素的内容信息删除该元素。Insert_List(ListPtr L, int x, int

7、 i);初始条件：顺序表L存在，且非空表。操作结果: 按照元素的内容和位置信息插入该元素，这里插入的元素是在指定位置前。Sort_List(ListPtr L):初始条件：顺序表L存在，且非空表。操作结果: 对顺序表L进行排序。Merge_List(ListPtr La, ListPtr Lb, ListPtr Lc);初始条件：La，Lb，Lc存在，且La,Lb非空表。操作结果：将La和Lb合并到Lc中。2.主程序：void main()Cover();/用户欢迎界面TypeSelection();/用户选择界面void TypeSelection()初始化；选择界面；while (1)sc

8、anf_s(%d, &Selection);switch (Selection)case 1:SqList_Selection(); break;case 2:LkList_Selection(); break;default:printf(Sorry,wrong number,please input again:);continue;if (Selection = 1 | 2)break;3.调用关系：本程序中的模块包括：其中：def.h:提供本程序所需要用到的宏定义。LkList.h:完成对链表的基本定义和操作，其中调用了def.h中的宏定义。SqList.h:完成对顺序表的基本定义和操

9、作，其中调用了def.h中的宏定义。Bkgrd.cpp:该系统的各种界面设计和对LkList.h以及SqList.h中的函数的调用，以实现各种功能，是整个函数的入口，其中调用了LkList.h，SqList.h和def.h。三、详细设计1.def.h中的基本函数以及源码：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LIST_INCREMENT 102.LkList.h中的基本函数以

10、及源码：#include#include#includedef.htypedef struct LNodeint data;struct LNode *next;*LinkList,LNode;void Display_LkLs(LinkList H)LinkList p=NULL;for (p = H-next; p; p = p-next)printf(%8d, p-data);void Init_LkLs(LinkList H)H-data=0;H-next = NULL;void Create_LkLs(LinkList H)int i,n;LinkList p = H, q = NU

11、LL;printf(请输入您要输入的元素的个数：);scanf_s(%d, &n);printf(请输入您要输入的数据，用回车隔开);for (i = 0; i data);q-next = p-next;p-next = q;p = q; /插表头生成一个单项链表int GetElem_LkLs(LinkList H, int i)int count;LinkList p = NULL;for (p = H-next, count = 1; p&count next, count+);if (!p | counti)return ERROR;return p-data;int GetLct_

12、LkLs(LinkList H,int e)int count;LinkList p = H-next;for (count = 0; p&p-data != e; count+)p = p-next;if (!p)return ERROR;return count+1;int GetLen_LkLs(LinkList H)int count;LinkList p= H-next;for (count = 0; p; count+)p=p-next;return count;int Insert_LkLs(LinkList H, int i,int e)int count;LinkList p

13、 = H,q=NULL;if (iGetLen_LkLs(H)printf(插入位置错误！);return ERROR;for (count = 0; count next;q = (LinkList)malloc(sizeof(LNode);q-data = e;q-next = p-next;p-next = q;return OK;int Delete_LkLs_Ord(LinkList H, int i)int count = 0;LinkList p = H, q = NULL;for (count = 0; count next; count+)p = p-next;if (!(p

14、-next) | counti - 1)return ERROR;q = p-next;p-next = q-next;free(q);return OK;int Delete_LkLs_Val(LinkList H, int e)LinkList p = H,q = NULL;if (!H)printf(链表已空，无法操作！n);return INFEASIBLE;while (p)if (e = p-data)break;elseq = p;p = p-next;if (!p)printf(找不到该元素！n);return ERROR;elseq-next = p-next;free(p)

15、;if (!H)printf(链表已空n);return INFEASIBLE;return OK;void Sort_LkLs(LinkList H)int temp=0;LinkList p = NULL, q=NULL; /工作指针for (p = H; p;p = p-next)for (q = H;q-next;q=q-next)if (q-data) (q-next-data)temp = q-data;q-data = q-next-data;q-next-data = temp;printf(排序完毕！n);LinkList Merge_LkLs(LinkList La,Lin

16、kList Lb)LinkList pa =La-next, pb = Lb-next,pc=La;LinkList pam = La,pbm = Lb;while (pa&pb)if (pa-data data)pc-next = pa; pc = pa; pa = pa-next;elsepc-next = pb;pc = pb;pb = pb-next;pc-next = pa ? pa : pb;free(Lb);return La;3.SqList.h中的基本函数以及源码：#include#include#includedef.htypedef struct DySqListint

17、*elem;int len;int cursize;*DySqPtr;void Display_DySq(DySqPtr L)int j;printf(nThe result is:ntt);for (j = 0; j len; j+)printf(%8d, L-elemj);int Init_DySq(DySqPtr L)L-elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int);if (!L-elem)printf(内存分配失败！n);return OVERFLOW; /分配内存失败L-len = 0;L-cursize = LIST_INIT_SI

18、ZE;return OK;int Create_DySq(DySqPtr L)int i;int *newbase=NULL;Init_DySq(L);printf(请输入您要输入的元素的个数：);scanf_s(%d, &L-len);if (L-len L-cursize)newbase = (int *)realloc(L-elem,(LIST_INIT_SIZE + L-len)*sizeof(int);L-elem = newbase;L-cursize = L-len + LIST_INIT_SIZE;if (!L-elem)printf(内存分配失败！n);return ERRO

19、R;printf(请输入您要输入的数据，用回车隔开:n);for (i = 0; i len; i+)printf(nttttt);scanf_s(%d, &L-elemi);printf(nntttt 建立完毕！n);return OK;int GetLct_DySq(DySqPtr L, int i)int q;for (q = 0; q len; q+)if (L-elemq = i)return q+1;printf(表中不存在该元素！n);return ERROR;int GetElem_DySq(DySqPtr L, int e)if (eL-len)return ERROR;re

20、turn L-eleme-1;int GetLen_DySq(DySqPtr L)return L-len;int Delete_DySq_Ord(DySqPtr L, int i)int j=0;if (i-1L-len - 1)printf(删除位置不合理！n);return FALSE; /删除位置不合理if (L-len = 0)printf(顺序表已空，无法删除！n);return INFEASIBLE; /顺序表空，无法执行删除for (j = i-1; j len - 1; j+)L-elemj = L-elemj + 1;/每个元素后移一个单元格-L-len;printf(删除

21、完毕！n);return OK;int Delete_DySq_Val(DySqPtr L,int i)int j;j = GetLct_DySq(L,i);if (j != ERROR)if (Delete_DySq_Ord(L, j) = OK)return OK;elsereturn ERROR;elsereturn ERROR;int Insert_DySq(DySqPtr L, int x, int i)int j;int *newbase=NULL;if (i-1L-len + 1)printf(插入位置不合理！n);return ERROR;if (L-len = L-cursi

22、ze)newbase = (int *)realloc(L-elem, (L-cursize + LIST_INCREMENT)*sizeof(int);/增加动态分配的内存，即cursizeif (!newbase)printf(内存分配失败！n);return OVERFLOW;L-elem = newbase;L-cursize += LIST_INCREMENT;for (j = L-len - 1; j = i - 1; j-)L-elemj + 1 = L-elemj;L-elemi - 1 = x;L-len+;printf(插入完毕！n);return OK;int Sort_

23、DySq(DySqPtr L)int i, j, temp;for (j = 0; j len - 1;j+)for (i = 0; i len - 1 - j;i+)if (L-elemiL-elemi + 1)temp = L-elemi;L-elemi = L-elemi + 1;L-elemi + 1 = temp;printf(n排序完毕！n);return OK;void Merge_DySq(DySqPtr La, DySqPtr Lb,DySqPtr Lc)int i = 0, j = 0, k = 0;Lc-len = La-len + Lb-len;Lc-cursize =

24、 2*LIST_INIT_SIZE;while (i len&j len)if (La-elemi elemj)Lc-elemk+ = La-elemi+;elseLc-elemk+ = Lb-elemj+;while (i len)Lc-elemk+ = La-elemi+;while (j len)Lc-elemk+ = Lb-elemj+;printf(n归并完毕！n);4.Bkgrd.cpp中的基本函数以及源码：#include#include#includeSqList.h#includeLkList.hDySqPtr L = NULL;void TypeSelection();vo

25、id SqList_Selection();/void Create_Sq()system(cls);int tag;L = (DySqPtr)malloc(sizeof(DySqList);Init_DySq(L);printf(=nn);while (1)tag = Create_DySq(L);if (tag = ERROR)printf(SystemErrorn);printf(Please Input the lists you want to create againn);if (tag = OK)break;printf(=nn);Display_DySq(L);printf(n

26、Press any key to return to the Sequence List Menu.);getchar();getchar();SqList_Selection();void GetLct_Sq()int num, tag;system(cls);printf(=nnnnnn);printf(Please input the element you want to find:nnnttttt);while (1)scanf_s(%d, &num);tag = GetLct_DySq(L, num);if (tag = ERROR)printf(Input error,pleas

27、e input the number you want to find again:n);elseprintf(The first element you want to find in the list is located in the %d th cell.nnnnnn, tag);break;printf(=nn);printf(nPress any key to return to the Sequence List Menu.);getchar();getchar();SqList_Selection();void GetElem_Sq()int pos, tag;system(c

28、ls);printf(=nnnnnn);printf(Please input the position you want to find:nnnttttt);while (1)scanf_s(%d, &pos);tag = GetElem_DySq(L, pos);if (tag = ERROR)printf(Input error,please input the number you want to find again:n);elseprintf(The element is %d.nnnnnn, tag);break;printf(=nn);printf(nPress any key

29、 to return to the Sequence List Menu.);getchar();getchar();SqList_Selection();void GetLen_Sq()system(cls);printf(=nnnnnnnn);printf(The length of the Sequence List is:%d.nnnnnnnnn, GetLen_DySq(L);printf(=nn);printf(nPress any key to return to the Sequence List Menu.n);getchar();getchar();SqList_Selec

30、tion();void Insert_Sq()system(cls);int pos = 0, value = 0;printf(=nnnnnn);printf(Please input the position and the value you want to insert(use space to separate) into,we will insert the element right in front of the location:);scanf_s(%d%d, &pos, &value);Insert_DySq(L, pos, value);printf(nnnnnnn=nn

31、);Display_DySq(L);printf(nPress any key to return to the Sequence List Menu.);getchar();getchar();SqList_Selection();void Delete_Sq_Ord()system(cls);int pos = 0;printf(=nnnnnn);printf(Please input the position you want to delete,we will delete the element by the position:);scanf_s(%d, &pos);Delete_D

32、ySq_Ord(L, pos);printf(nnnnnnn=nn);Display_DySq(L);printf(nPress any key to return to the Sequence List Menu.);getchar();getchar();SqList_Selection();void Delete_Sq_Val()system(cls);int value = 0;printf(=nnnnnn);printf(Please input the value you want to delete,we will delete the element by the value

33、);scanf_s(%d, &value);Delete_DySq_Val(L, value);printf(nnnnnnn=nn);Display_DySq(L);printf(nPress any key to return to the Sequence List Menu.);getchar();getchar();SqList_Selection();void Delete_Sq()int Selection = 0;system(cls);printf(=nnnn);printf(ttttYou want to use:nnnnn);printf(tttt1.Delete one

34、by ordernnnnn);printf(tttt2.Delete one by valuennnnn);printf(=n);printf(Please input the number to get into the according sub-system:);while (1)scanf_s(%d, &Selection);switch (Selection)case 1:Delete_Sq_Ord();break;case 2:Delete_Sq_Val();break;default:printf(Sorry,wrong number,please input again:);continue;if (Selection = 1 | 2)break;void Sort_Sq()system(cls);printf(=nnnnnn);Sort_DySq(L);printf(nnnnnn=nn);Display_DySq(L);printf(nPress any key to return to the Sequence List Menu.n);getchar();g