《《数据结构课程设计》课程设计报告》由会员分享，可在线阅读，更多相关《《数据结构课程设计》课程设计报告（41页珍藏版）》请在金锄头文库上搜索。
1、上海应用技术学院课程设计报告课程名称设计题目数据结构课程设计(多道)院系计算机科学与信息学院专业 网络工程 班级姓名学号指导教师 廿苹 FI期 2014772014711一.目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力二.课程设计内容说明1项目一：有序表合并(1) 对设计任务内容的概述要求输入有序表的数据，利用顺序表和链表结构分别完成两个有序表合并功能，并 输出合并后的信息。(2) 需求分析或功能描述分别设计顺
2、序表和链表的合并功能，主界面供选择有序表的类型，选择后对两个有 序表进行合并。函数是静态数据读取，顺序表读取有序的数组数据肓接合并输出，单链 表是对无序的集合排序后合并输出。(3) 概要设计或程序流程图开始图1.1有序表合并流程图(4) 程丿芋的输入与输出描述函数是静态数据读取，顺序表书有序表直接合并输出，单链表是对集合排序后合并 输岀。(5) 数据结构#define datatype int/*定义数据结构*/顺序存储类型typedef struct datatype dataMAXSIZE;int length; SqList;/*定义数据结构*/单链表存储结构typedef struct
3、 Lnodedatatype data;struct Lnode *next;JLinkList;(6) 程序模块及其接口描述程序包括以下几个模块：建立排序输出合并Main函数顺序表CreateListDispListlsqunion单链表CreateListRSortDispList2linkunion(7) 详细设计或源代码说明/listl:有序表合并1) 预处理与头文件#include# include#include #include 建立顺序表void CreateList(SqList *&L,datatype a,int n) int i;L=(SqList*)malloc(si
4、zeof(SqList);for(i=0;idatai=ai;L-length=n;2) 建立单链表void CreateListR(LinkList 启&L,datatype a|5int n) LinkList * s,*r;int i;L=(LinkList*)malloc(sizeof(LinkList);L-next=NULL;r=L;for(i=0;idata=ai;r-next=s;r=s;r-next=NULL;3) 单链表递增排序void Sort(LinkList *&L) 单链表元素递增排序LinkList *p,*pre,*q;p=L-next-next;/p指向L的第
5、2个数据节点L-next-next=NULL;构造只含一个数据结点的有序表while (p!=NULL)q=p-next;/q保存*p结点后继结点的指针pre=L;从有序表开头进行比较，pre指向插入*卩的前驱结点while (pre-next! =NULL& pre-next-datadata)在有序表中找插入*p 的前驱结点*prepre=pre next;p-next=pre-next;将插入到*p 之后next 二 p;p=q；扫描原链表余下的节点4) 输出顺序表void DispListl(SqList *L) /输出线性表int i;/if (Listdatatype(L) ret
6、urn;for (i=O;ilength;i+)printf(n%d H,L-datai);printf(HnH);5) 输出单链表void DispList2(LinkList *L) 输出线性表LinkList *p=L-next;while (p!=NULL)printf(%d n,p-data);p=p-next;printf(,nH);6) 顺序表合并函数采用顺序表存放有序表void squnion(SqList *LA,SqList *LB,SqList *&LC) /printf(uaaann);printf(”顺序表的合并)；int i=O,j=O,k=O;LC=(SqList
7、*)malloc(sizeof(SqList);while(ilength&jlength) if(LA-dataidataj) LC-datak=LA-datai;i+;k+;else LC-datak=LB-dataj;j+；k+;while(ilength)LC-data| k=LA-data i|;i+;k+;while(ilength)LC-data k=LB-dataj ;i+;k+;LC-length=k;7) 链表合并函数采用单链表存放有序表时void linkunion(LinkList *LA,LinkList *LB,LinkList *&LC) LinkList *pa
8、=LAnext,*pb=LAnext,*r,*s;LC=(LinkList *)malloc(sizeof(LinkList);r=LC;while(pa!=NULL&pb!=NULL) if(pa-datadata)s=(LinkList *)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;else s=(LinkList *)malloc(sizeof(LinkList); s-data=pb-data;r-next=s;r=s;pb=pb-next;pa=pa-next;while(pa!=NULL)s=(Li
9、nkList *)malloc(sizeof(LinkList); s-data=pa-data;r-next=s;r=s;pa=pa-next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList); s-data=pb-data;r-next=s;r=s; pb=pb-next;r-next=NULL;8) 主函数void listl()int i,flag=l;SqList *HA,*HB,*HC;LinkList *LA,*LB,*LC;datatype a= 1,2,3,5,7,8;datatype b=0,4,6,9,;dataty
10、pe c= 2,1，&5,3,7;datatype d= 6,9,4,0,;z后是界面的设计和对各函数的调用和输出。(8) 调试分析或程序测试祢 5八数据结构课设程序listl.exe12 0的合 愛回择 顺链返选合幷87654、幷3合并2的宀-S丄需:0 J回择 如丄0并顺链返选 幷合Hcl:2:0:请 合HAHB的并 表合合務口 1顺原原顺集875 93 6图1.2顺序表合并运行结果“顺庄奏的合并2：链条鬲合并0：返回请选择：合合合集番 WfWW 口链原下1 9口 2 6 A B C 女 L L L 并A:B:合合并8 54 012 30 4 60 12图1.3链表表合并运行结果(9) 尚
11、未解决的问题或改进方向有序表数据的输入函数没有设计，本程序的数据是静态直接读取，希望下次继续改 进。(10) 对软件的使用说明主界面选择之后进入此项目的界面:输入“1”进行顺序表的合并输入“2”进行顺序表的合并输入“0”返回上一级2项目二：joseph环(1) 对设计任务内容的概述编号是1, 2,小的n个人按照顺时针方向围坐一圈，每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值叫从第一个人开始顺时针方向 自1开始顺序报数，报到ni时停止报数。报ni的人出列，将他的密码作为新的m值, 从他在顺吋针方向的下一个人开始重新从1报数，如此下去，直到所有人全部岀列 为止。设计一个程序来求
12、出出列顺序。(2) 需求分析或功能描述利用单向循环链表存储结构，输入每人的密码，按照报数上限值m查找到岀列 的人并把查到的节点数据作为第二个上限值赋给m,将此节点数据输出Z后删除此 节点，再次循环此过程，直到所有数已出列。(3) 概要设计或程序流程图开始图2.1 joseph环流程图(4) 程序的输入与输出描述提供用户从键盘输入，Joseph约瑟夫环的必要数据，并从屏幕显示岀列顺序。要求：输入数据：建立输入处理输入数据，输入ni的初值，n ,输入每个人的密码, 建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列(5) 数据结构以单向循环链表实现该结构。typedef struct N
13、odeint key;/每个人持有的密码int num;/这个人的编号struct Node *next;指向下一个节点Node,*Link;(6) 程序模块及其接口描述程序包括以下几个模块：void InitList(Link &L) /创建一个空的链表void Creater(int n,Link &L) /初始化链表主要功能模块设计如下：给每人编号if(!p) exit(l);p-num=i; /利用q指针给链表每个单元编号L-next=p;L=p;L next=qnext;free(q);出列功能P=L;for(int i=l;i next;q=p-next;x=q-key;printf(%d H,q-num);p-next=q-next;free(q);(7) 详细设计或源代码说明1) 创建一个空的链表void InitList(Link &L)
