还剩34页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
仲恺农业工程学院课程设计报告课程名称数据结构院(系)专业班级学号姓名指导老师目录TOC\o1-3\h\z\u1顺序表12链表63栈和队列124树和二叉树185图246查找和排序29课程设计总结33参考文献331顺序表2题设线性表存于A[
1..size]的前num各分量中,且递增有序请设计一个算法,将x插入到线性表的适当位置上,以保持线性表的有序性
一、数据结构说明
1、线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素假设线性表的每个元素需占用L个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置则线性表中第i+1个数据元素的存储位置LOCai+1和第i个数据元素的存储位置LOCai之间满足下列关系LOCai+1=LOCai+L一般来说,线性表的第i个数据元素ai的存储位置为LOCai=LOCa1+i-1*L式中LOCa1是线性表的第一个数据元素a1的存储位置,通常称做线性表的起始位置或基地址线性表的这种机内表示称做线性表的顺序存储结构或顺序映象SequentialMapping,反之,称这种存储结构的线性表为顺序表它的特点是,为表中相邻的元素ai和ai+1赋以相邻的存储位置LOCai和LOCai+1换句话说,以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系
2、顺序表存储结构用一段地址连续的存储单元依次存储线性表中的数据元素图1顺序表存续结构示意图
二、顺序表的存储结构设计typedefstruct{ElemType*data;//存储空间基址intlength;//当前长度intsize;//当前分配的存储容量以sizeofElemType为单位}SqList;
三、算法设计(程序流程图)图2顺序表课程设计流程图
四、详细设计#includestdio.h#includestdlib.h#includeprocess.h/*exit*/#includemalloc.h#defineLIST_INIT_SIZE100/*线性表存储空间的初始分配量*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedefintElemType;typedefstruct{ElemType*data;//存储空间基址intlength;//当前长度intsize;//当前分配的存储容量以sizeofElemType为单位}SqList;/*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2/*因为在math.h中已定义OVERFLOW的值为3故去掉此行*/typedefintStatus;/*Status是函数的类型其值是函数结果状态代码,如OK等*/typedefintBoolean;/*Boolean是布尔类型其值是TRUE或FALSE*/StatusInitListSqListL{/*操作结果构造一个空的顺序线性表*/L.data=ElemType*mallocLIST_INIT_SIZE*sizeofElemType;if!L.dataexitOVERFLOW;/*存储分配失败*/L.length=0;/*空表长度为0*/L.size=LIST_INIT_SIZE;/*初始存储容量*/returnOK;}StatusInsertOrderListSqListLElemTypex{//顺序表L中的元素依值递增有序,本算法将x插入其中适当位置//以保持其有序性入口断言0=L.length=L.sizeintij;ifL.length==L.sizereturnOVERFLOW;else{i=L.length-1;whilei=0xL.data[i]i--;forj=L.length-1;j=i+1;j--L.data[j+1]=L.data[j];L.data[i+1]=x;L.length++;returnOK;}}StatusListTraverseSqListL{/*初始条件顺序线性表L已存在*//*操作结果依次对L的每个数据元素访问并输出*/ElemType*p;inti;p=L.data;fori=1;i=L.length;i++printf%d*p++;printf\n;returnOK;}voidmain{SqListL1;ElemTypee1e2;intin;printf顺序表第2题\n;InitListL1;//初始化顺序表printf给顺序表长度赋值n=;scanf%dn;//通过键盘输入为顺序表长度赋值printf输入元素:\n;fori=1;i=n;i++{scanf%de1;//通过键盘输入为e赋值InsertOrderListL1e1;//调用InsertOrderList函数,在L中递增插入新的数据元素e1}printf有序递增顺序表为:;ListTraverseL1;//依次对L的每个数据元素访问并输出printf输入一个元素并把它插入表中\n;scanf%de2;InsertOrderListL1e2;//调用InsertOrderList函数,在有序递增顺序表L中有序插入新的数据元素e2printf新有序递增顺序表为:;ListTraverseL1;//依次对L的每个数据元素访问并输出}
五、调试分析
1、调试结果图3顺序表课程设计调试结果
2、时间复杂度StatusInsertOrderListSqListLElemTypex函数的时间复杂度为On
3、程序存在问题和解决办法在调试程序的时候发现自己编程序的时候考虑不周,忽略了顺序表的最大容量的问题,程序运行的结果跟预想的结果不吻合解决办法是在编写程序的时候要把顺序表的最大容量这个问题考虑进去2链表5题试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法
一、数据结构说明
1、线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的,也可以是不连续的因此,为了表示每个数据元素ai与其直接后继数据元素ai+1,之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储—个指示其直接后继的信息即直接后继的存储位置这两部分信息组成数据元素ai的存储映象,称为结点Node它包括两个域其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域指针域中存储的信息称做指针或链n个结点ai(1≤i≤n的存储映象链结成一个链表,即为线性表a1,a2,…,an的链式存储结构又由于此链表的每个结点中只包含一个指针域,故又称线性链表或单链表
2、链表存储结构用一组任意的存储单元存放线性表的元素P结点(*p)图4链表存储结构示意图
二、链表的存储结构设计structLNode;typedefstructLNode*PtrToNode;typedefPtrToNodeList;typedefPtrToNodePosition;typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}*LinkList;LinkListL;//L为单链表的头指针
三、算法设计(程序流程图)图5链表课程设计流程图
四、详细设计#includestdio.h/*EOF=^Z或F6NULL*/#includeprocess.h/*exit*/#includemalloc.htypedefintElemType;/*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3故去掉此行*/typedefintStatus;/*Status是函数的类型其值是函数结果状态代码,如OK等*/typedefintBoolean;/*Boolean是布尔类型其值是TRUE或FALSE*/structLNode;typedefstructLNode*PtrToNode;typedefPtrToNodeList;typedefPtrToNodePosition;typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}*LinkList;LinkListL;//L为单链表的头指针voidInsertElemTypeXPositionP{PositionTmpCell;/*1*/TmpCell=PositionmallocsizeofstructLNode;/*2*/ifTmpCell==NULL/*3*/printfOutofspace!!!;/*4*/TmpCell-data=X;/*5*/TmpCell-next=P-next;/*6*/P-next=TmpCell;}intIsLastPositionPListL{returnP-next==NULL;}PositionFindPreviousElemTypeXListL{PositionP;/*1*/P=L;/*2*/whileP-next!=NULLP-next-data!=X/*3*/P=P-next;/*4*/returnP;}voidDeleteElemTypeXListL{PositionPTmpCell;P=FindPreviousXL;if!IsLastPL/*Assumptionofheaderuse*/{TmpCell=P-next;/*Xisfound;deleteit*/TmpCell-data=X;//给指针TmpCell赋值P-next=P-next-next;//更改P-Next的值freeTmpCell;//释放TmpCell所指向的结点}}StatusListTraverseListL{/*初始条件线性表L已存在*/ListP=L-next;whileP{printf%dP-data;/*输出元素*/P=P-next;/*指针指向下一个元素*/}printf\n;returnOK;}voidmainvoid{ListL1;PositionP1;intMin;intjxn;printf链表第5题\n;L1=ListmallocsizeofstructLNode;/*产生头结点并使L指向此头结点*/if!L1/*存储分配失败*/exit0;L1-next=NULL;/*头结点的指针域的值为NULL*/printf给链表长度赋值n=;scanf%dn;//通过键盘为n赋值printf输入元素\n;forj=1;j=n;j++{scanf%dx;//通过键盘为x赋值InsertxL1;//将元素x插入链表中}printf链表为:;ListTraverseL1;P1=L1-next;Min=P1-data;P1=P1-next;for;P1!=NULL;P1=P1-next{ifP1-data=MinMin=P1-data;}printf删除最小值为Min=%d\nMin;DeleteMinL1;//删除链表中的最小值printf删除最小值后,新的链表为:;ListTraverseL1;}
五、调试分析
1、调试结果图6链表课程设计调试结果
2、时间复杂度P1=L1-next;Min=P1-data;P1=P1-next;for;P1!=NULL;P1=P1-next{ifP1-data=MinMin=P1-data;}本段程序的时间复杂度为On,而voidDeleteElemTypeXListL函数的时间复杂度为O1,所以在链表中删除最小值的时间复杂度为On
3、程序存在问题和解决办法调用指针的时候出现数据混乱,解决办法是调用指针的时候要注意指针所指向的数据,避免发生数据混乱3栈和队列11题如果允许在循环队列的两端都可以进行插入和删除操作要求
(1)写出循环队列的类型定义;
(2)写出“从队尾删除”和“从队头插入”的算法
一、数据结构说明
1、栈Stack是限定仅在表尾进行插入或删除操作的线性表因此,对栈来说,表尾端有其特殊含义,称为栈顶top,相应地,表头端称为栈底bottom不含元素的空表称为空栈队列Queue是一种先进先出FirstinFirstOut,缩写为FIFO的线性表它只允许在表的一端进行插入,而在另一端删除元素这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开在队列中,允许插入的一端叫做队尾rear,允许删除的一端则称为队头front
2、栈存储结构图7栈的示意图
3、队列存储结构图8队列的示意图
二、队列的存储结构设计structQueueRecord{intCapacity;//队列最大容量intFront;//队头intRear;//队尾intSize;//队列大小ElementType*Array;//数组};
三、算法设计(程序流程图)图9栈和队列课程设计流程图
四、详细设计#includemalloc.h/*malloc等*/#includestdio.h/*EOF=^Z或F6NULL*/#includestdlib.h/*atoi*/#includeprocess.h/*exit*/structQueueRecord;typedefstructQueueRecord*Queue;#defineMinQueueSize5typedefcharElementType;structQueueRecord{intCapacity;//队列最大容量intFront;//队头intRear;//队尾intSize;//队列大小ElementType*Array;//数组};voidMakeEmptyQueueQ{Q-Size=0;Q-Front=1;Q-Rear=0;}intIsEmptyQueueQ{returnQ-Size==0;}intIsFullQueueQ{returnQ-Size==Q-Capacity;}staticintSuccintValueQueueQ{if--Value==-1Value=Q-Capacity-1;returnValue;}QueueCreateQueueintMaxElements{QueueQ;/*1*/ifMaxElementsMinQueueSize{/*2*/printfQueuesizeistoosmall;exit0;}/*3*/Q=QueuemallocsizeofstructQueueRecord;/*4*/ifQ==NULL{/*5*/printfOutofspace!!!;exit0;}/*6*/Q-Array=ElementType*mallocsizeofElementType*MaxElements;/*7*/ifQ-Array==NULL{/*8*/printfOutofspaace!!!;exit0;}/*9*/Q-Capacity=MaxElements;/*10*/MakeEmptyQ;/*11*/returnQ;}voidEnqueueElementTypeXQueueQ{ifIsFullQprintfFullqueue;else{Q-Size++;//队列大小加1Q-Front=SuccQ-FrontQ;Q-Array[Q-Front]=X;//将元素X插入队列中}}ElementTypeDequeueQueueQ{ElementTypec2;ifIsEmptyQ{printfEmpty;exit0;}Q-Size--;//队列大小减1Q-Front=SuccQ-FrontQ;c2=Q-Array[Q-Front];returnc2;}voidmainvoid{charc1c2;QueueQ;intiMAX;printf栈和队列第11题\n;printf输入数据赋给MAXMAX=5\n;scanf%dMAX;getchar;Q=CreateQueueMAX;//建立一个大小MAX的队列printf依次输入元素abcde\n;fori=1;i=5;i++{scanf%cc1;getchar;Enqueuec1Q;//将元素c1插入队列中}/*以下程序语句(可以有一条或多条)的功能输出出队序列*/printf输出出队序列为;fori=1;i=5;i++{c2=DequeueQ;printf%cc2;}printf\n;}
五、调试分析
1、调试结果图10栈和队列课程设计调试结果
2、时间复杂度入队函数的时间复杂度为On出队函数的时间复杂度为On
3、程序存在问题和解决办法程序刚开始运行的时候输出的结果跟自己预想的预想的结果不吻合,原因是输入数据的时候按Enter键,Enter键被当做元素了,解决办法是添加getchar()语句,运行结果正确4树和二叉树13题二叉树排序方法如下
(1)将第一个数据放在树根
(2)将随后读入的数据与树根中的数据相比较,若比树根大,则置于右子树,反之则置于左子树,建成一棵二叉树;
(3)利用中序遍历打印排序结果
一、数据结构说明
1、在现实的生活中,描述一个单位的组织结构以及一个家族的族谱都可用树形结构来形象地表示出,在计算机的领域中,数据库系统中信息的组织形式也可用它来描述,因此它是一种应用非常广泛的非线性结构,其中以二叉树最为常用本次实验以二叉树的操作为主
2、二叉树是另一种树形结构它的特点是每个结点最多有两棵子树(二叉树中不存在度大于2的结点),而且二叉树的子树有左右之分,其次序不能颠倒树的一般形态如下图11树
3、树存储结构双亲表示法,孩子链表表示法,孩子兄弟法本次算法树主要采用孩子链表表示法进行存储,如下序号datafirstchildABCD∧EF∧G∧H∧I∧图12树的孩子链表表示法示意图
二、二叉排序树的存储结构设计typedefstructSearchTNode{TElemTypeElement;//数据域structSearchTNode*lchild*rchild;/*左右孩子指针*/}SearchTNode*SearchTree;
三、算法设计(程序流程图)图13二叉树课程设计流程图
四、详细设计#includestdio.h/*EOF=^Z或F6NULL*/#includeprocess.h/*exit*/#includemalloc.h#includestdlib.htypedefintElementType;/*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;/*Status是函数的类型其值是函数结果状态代码,如OK等*/typedefintBoolean;/*Boolean是布尔类型其值是TRUE或FALSE*/typedefintTElemType;/*二叉树的二叉链表存储表示*/typedefstructSearchTNode{TElemTypeElement;//数据域structSearchTNode*lchild*rchild;/*左右孩子指针*/}SearchTNode*SearchTree;/*二叉树的二叉链表存储的基本操作*/StatusInitBiTreeSearchTree*T{/*操作结果:构造空二叉树T*/*T=NULL;returnOK;}voidCreatSearchTreeSearchTree*TTElemTypeX{if*T==NULL/*如果是空树*/{*T=SearchTreemallocsizeofstructSearchTNode;if*T==NULLexitOVERFLOW;else{*T-Element=X;*T-lchild=*T-rchild=NULL;}}/*最后建立一个结点的树*/else/*如果是树*/ifX*T-ElementCreatSearchTree*T-lchildX;elseifX*T-ElementCreatSearchTree*T-rchildX;}voidInOrderTraverseSearchTreeT{/*初始条件:二叉树T存在Visit是对结点操作的应用函数*//*操作结果:中序递归遍历T对每个结点调用函数Visit一次且仅一次*/ifT{InOrderTraverseT-lchild;/*先中序遍历左子树*/printf%dT-Element;/*再访问根结点*/InOrderTraverseT-rchild;/*最后中序遍历右子树*/}}voidmain{SearchTreeT;TElemTypeX;intin;printf树和二叉树第13题\n;InitBiTreeT;//构造空树printf输入结点的个数n=;scanf%dn;printf请输入结点\n;fori=1;i=n;i++{scanf%dX;//通过键盘给X赋值CreatSearchTreeTX;//建立二叉排序树}printf中序递归遍历二叉排序树:;InOrderTraverseT;//调用中序遍历函数printf\n;}
五、调试分析
1、调试结果图15二叉树课程设计调试结果
2、时间复杂度voidCreatSearchTreeSearchTree*TTElemTypeX函数的时间复杂度为On
3、程序存在问题和解决办法程序刚开始运行的结果和自己预想的结果十分的不吻合,经检查发现voidCreatSearchTreeSearchTree*TTElemTypeX函数中出现的问题,经过把此函数修改调整后,运行结果正确5图14题编写函数实现用Prim算法构造最小生成树的算法
一、数据结构说明
1、图(GRAPH)是一种复杂的数据结构,结点之间的关系可以是任意的,由此图的应用极为广泛,已经渗透到如物理、化学、电讯工程、计算机科学等领域
2、图存储结构邻接矩阵表示法和邻接表表示法,本次实验图主要以邻接表进行存储用邻接矩阵表示法表示图如下图所示0101A=101101001001图16一个无向图的邻接矩阵表示无向图对应的邻接表表示如下图所示序号vertexfirstedge13∧023∧01∧图17一个无向图的的邻接表表示
二、图(prim算法辅助数组)的存储结构设计struct{intadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];
三、算法设计(程序流程图)图18图课程设计流程图
四、详细设计#includestdio.h#defineMAX_VERTEX_NUM100#defineINFINITY99999intmap[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intne;struct{intadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];//构造连通图voidLoadMap{intijvuc;fori=1;i=n;i++forj=1;j=n;j++map[i][j]=INFINITY;fori=1;i=e;i++{scanf%d%d%duvc;map[u][v]=c;map[v][u]=c;}}//输出生成树的每条边voidMiniSpanTree_PRIM{intijkminu;u=1;forj=1;j=n;++jifj!=u{closedge[j].adjvex=u;closedge[j].lowcost=map[u][j];}closedge[u].lowcost=0;fori=1;in;++i{min=INFINITY;forj=1;j=n;j++{ifclosedge[j].lowcost0closedge[j].lowcostmin{k=j;min=closedge[j].lowcost;}}printf%d-%d\nclosedge[k].adjvexk;closedge[k].lowcost=0;forj=1;j=n;j++ifmap[k][j]closedge[j].lowcost{closedge[j].adjvex=k;closedge[j].lowcost=map[k][j];}}}voidmain{printf图第14题\n;printf请输入连通图的顶点数目:;scanf%dn;printf请输入连通图的边的数目:;scanf%de;printf请依次输入每条边的两个顶点名和权值顶点_顶点_权值如125:\n;LoadMap;printf最小生成树所包括的边如下:\n;MiniSpanTree_PRIM;}
五、调试分析
1、调试结果图19图课程设计调试结果
2、时间复杂度普里姆算法的时间复杂度为O6查找和排序7题编写函数实现直接插入算法、希尔排序算法
一、数据结构说明
1、插入排序的主要操作是插入,其基本思想是每次将一个待排序的元素按其大小插入到一个已经排好序的有序序列中,直到全部记录排好序为止
2、希尔排序基本思想是将整个待排序记录分割成若干个子序列,在子序列内分别进行直接插入排序,待整个序列中的记录基本有序时,对全体记录进行直接插入排序
二、数组存储结构设计A[length]B[length]
三、算法设计(程序流程图)图20直接插入排序流程图图21希尔排序流程图
四、详细设计#includestdio.h#includestdlib.h#definelength100voidInsertSortinta[]intn{intijtemp;fori=0;in-1;i++{temp=a[i+1];j=i;whilej-1tempa[j]{a[j+1]=a[j];j--;}a[j+1]=temp;}}voidShellsortintA[]intN{intijIncrement;intTmp;forIncrement=N/2;Increment0;Increment/=2/*hsequence*/fori=Increment;iN;i++{/*insertionsort*/Tmp=A[i];forj=i;j=Increment;j-=IncrementifTmpA[j-Increment]A[j]=A[j-Increment];elsebreak;A[j]=Tmp;}/*endfor-Iandfor-Incrementloops*/}voidmain{intA[length]B[length];intijnm;printf排序和查找第7题\n;printf元素个数n=;scanf%dn;printf输入元素\n;fori=0;in;i++{scanf%dA[i];}InsertSortAn;printf通过直接插入排序后序列为;fori=0;in;i++printf%dA[i];printf\n;printf元素个数m=;scanf%dm;printf输入元素\n;fori=0;im;i++{scanf%dB[i];}ShellsortBm;printf通过希尔排序后序列为;fori=0;im;i++printf%dB[i];printf\n;}
五、调试分析
1、调试结果图23排序和查找课程设计调试结果
2、时间复杂度直接插入排序的时间复杂度为O希尔排序的时间复杂度为O课程设计总结数据结构是计算机专业的专业基础课,它在教学计划中的地位是承上启下的核心课程,属于武术中的“练功”科目通过本次的数据结构课程设计让我对本课程有了更深刻的认识,掌握了基本的数据结构,对线性表、队列和栈、二叉树、图等基本数据结构的基本操作有了更加深入的了解,提高了算法设计能力、程序设计能力和算法分析能力等,同时,我也发现了自己的一些不足,如指针的操作还不熟练,对一些问题的考虑还不周全等,在往后的学习中加以改进和弥补自己的不足之处参考文献
[1]严蔚敏吴伟民编.数据结构[M].北京:清华大学出版社
2004.…………空闲开始有序顺序表L1元素e2输入数据赋给e2把e2插入有序顺序表L1的适当位置输出有序顺序表L1结束datanext开始链表L1对链表L1作有序递减排序删除最小值,并把它赋给MIN输出链表L1结束出栈进栈栈顶栈底...开始初始化队列Q输入一串元素从队头插入元素从队尾删除元素结束ABCDEFGIH10∧21∧5432∧643∧875768开始初始化二叉树Ti=1,n====T=NULL?输入元素Xroot=X输入元素YX(Y)rootlchild=XYrchild=XYi++in中序遍历输出二叉树T结束V3V03V1V201123开始辅助数据数组初始化一个节点初始化i=1选择第i个顶点的最小相连边;将另个顶点并入将另个顶点并入;i++ig.arcnum?j=0jg.arcnum?输出最小树结束j++新顶点并入后重新选择最小边开始输入数组A[n]通过直接插入排序输出有序数组A[n]结束开始输入数组B[m]通过希尔排序输出有序数组B[m]结束。