数据结构实验报告-物联网工程.docx
《数据结构实验报告-物联网工程.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告-物联网工程.docx(64页珍藏版)》请在沃文网上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 联网 工程