数据结构课程设计--- 数据结构各章算法的演示系统.doc

课程设计(论文)任务书 信息 学院计算机专业2010-02-17 班 一、课程设计(论文)题目 数据结构各章算法的演示系统 二、课程设计(论文)工作自 2011 年12月19 日起至 2011 年 12月 30 日止。三、课程设计(论文) 地点: 5-401、402 四、课程设计(论文)内容要求：1本课程设计的目的1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2课程设计的任务及要求1）基本要求：1.分析题目，查阅相关资料；2.算法设计、数据结构设计； 3.编写代码并调试；4.完成课程设计报告。 2）创新要求： 在基本要求达到后，可进行创新设计。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写毕业论文（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等（3）毕业论文装订按学校的统一要求完成4）答辩与评分标准： （1）完成问题的解决方法分析：20分； （2）算法思想（流程）：20分； （3）数据结构：20分；（4）测试数据：20分（5）回答问题：20分。5）参考文献： c程序设计（第二版） 谭浩强 著 清华大学出版社出版 c+程序设计 谭浩强 著 清华大学出版社出版 数据结构（c语言版） 严蔚敏、吴伟民 著 清华大学出版社出版 数据结构辅导与提高 徐孝凯 著 清华大学出版社出版 6）课程设计进度安排内容 天数 地点构思及收集资料 4天 图书馆编程与调试 5天 实验室 撰写论文 2天 宿舍 学生签名： 2011年 12月 19 日课程设计(论文)评审意见（1）完成问题分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）算法思想（20分）：优（）、良（）、中（）、一般（）、差（）； （3）数据结构（20分）：优（）、良（）、中（）、一般（）、差（）；（4）测试数据 （20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 职称： 2011年1月 3 日目 录第一章 课程设计的目的 41.1 课程设计的题目及简介 4第二章 课程设计的内容 42.1 课程设计的设计说明 42.2 程序截图. 52.3 部分程序清单 6第三章 测试数据 283.1 串的基本操作 283.2 队列和二叉树的基本操作 293.3 排序和顺序表 30第四章 课设心得 31第五章 参考文献 31 一、课程设计的目的1，课程设计的题目及简介：课程设计是一门锻炼学生动手操作能力的课程，在了解并掌握数据结构与算法的设计方法的过程中，培养初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。为自己以后从事软件开发事业打下基础。课设使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构，存储结构和操作实现算法，以及他们在程序中的使用方法。掌握使用各种计算机资料和有关的参考资料，提高程序设计的基本能力。同时,为了掌握,巩固本学习所学的数据结构的一些算法和获取实现大型的程序设计架构思想,也为了将整个数据结构课程各个知识点有条不紊的联系起来,因此我选择了”数据结构各章算法的演示系统”.还可以使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法,使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。二、课程设计的内容1、设计说明本次课程设计的主要是每章的adt算法演示系统，从中穿插的程序功能是所定义的数据结构类型基本应用（比如说二叉树的左右子树，字符串的链接，排序中的各种算法，图的bfs，dfs）另外，演示系统设计的理念是要更好的引导学生知道操作的基本，及合理编排程序。2、程序截图 图1 查找表的基本操作 图2 图的基本操作3、程序清单（1）线性表的主要操作/构造一个空的线性表status initlist(sqlist &l) l.elem = (elemtype *)malloc(list_init_size * sizeof(elemtype); if(!l.elem) return error;/存储空间失败 l.length = 0;/当前长度0 l.size = list_init_size;/初始容量 return ok;/销毁顺序表lstatus destroylist(sqlist &l) free(l.elem); l.elem = null; l.length = l.size = 0; return ok;/将l重置为空表status clearlist(sqlist &l) l.length = 0; return ok;/若l为空白,返回true;否则返回falsestatus listempty(sqlist l) if(0 = l.length) return true; else return false;/返回l中的元素个数status listlength(sqlist l) return l.length;/返回l中第1个与e满足关系compare()的数据元素的位序status locateelem(sqlist l,elemtype e,status(*compare)(elemtype,elemtype) elemtype *p; int i = 1;/i的初值为第i个元素的位序 p = l.elem;/p的初值为第i个元素的存储位置 while(i = l.length & !compare(*p+,e) +i; if(i = s.stacksize) s.base = (selemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(selemtype);if(!s.base) return 0;s.top = s.base+s.stacksize;s.stacksize+=stackincrement;*s.top+ = e;return 1;int pop(sqstack &s,selemtype &e)if(s.top = s.base) return 0;e = *-s.top;return 1;（3）队列的基本操作bool inqueue(queuesq &qu, int size) if(size0)coutsize的值非法!endl;return false; qu.msize=size+1; qu.queue=new elemtypequ.msize; if(!qu.queue) cout内存空间用完了!endl; return false; qu.length=0; qu.front=qu.rear=0; void clear(queuesq &qu) delete qu.queue; qu.queue=0; qu.front=qu.rear=0; qu.length=0; qu.msize=0; bool enqueue(queuesq &qu,elemtype item) if(qu.rear+1)%qu.msize)=qu.front) cout队列已满，溢出endl; return false; qu.rear=(qu.rear+1)%qu.msize; qu.queuequ.rear=item; return true; elemtype outqueue(queuesq &qu) if(qu.front=qu.rear) cout队列为空endl; return false; qu.front=(qu.front+1)%qu.msize; qu.length-; return qu.queuequ.front; elemtype peekqueue(queuesq &qu) if(qu.front=qu.rear) cout队列为空endl; return false; return qu.queue(qu.front+1)%qu.msize; int queuelength(queuesq qu) return(qu.rear+qu.msize-qu.front)%qu.msize; bool queuetraverse(queuesq qu) int k=0; for(k=qu.front+1;k=qu.rear;k+) coutqu.queuek; coutendl; if(qu.rear-qu.front)!=k) return false; else return true; void destroyqueue(queuesq &qu) free(qu.queue); (4) 串的基本操作void assign(sqstring &s,char t)int i=0;while (ti!=0) s.chi=ti; i+;s.len=i;void strcopy(sqstring &s,sqstring t)int i;for (i=0;it.len;i+)s.chi=t.chi;s.len=t.len;int strlength(sqstring s)return(s.len); int strequal(sqstring s,sqstring t)int i=0;if (s.len!=t.len)return(0);else for (i=0;is.len;i+)if (s.chi!=t.chi) return(0);return(1);sqstring concat(sqstring s,sqstring t)sqstring r;int i,j;for (i=0;is.len;i+)r.chi=s.chi;for (j=0;jt.len;j+)r.chs.len+j=t.chj;r.len=i+j;return(r); void dispstr(sqstring s)int i;for (i=0;is.len;i+)printf(%c,s.chi);printf(n);int strcompare(sqstring s,sqstring t)int i;for(i=0;istrlength(s)&istrlength(t);i+)if(s.chi!=t.chi)return s.chi-t.chi;return strlength(s)-strlength(t);(5)静态查找表int create ( linelist &l,int n)int j; l.elem = (elemtype *)malloc(list_init_size * sizeof(elemtype); if(!l.elem) return 0; l.length = 0; l.size = list_init_size; cout逐个输入元素：endl; for(j=1;jl.elemj; return 1;int destroylist(linelist &l) free(l.elem); l.elem = null; l.length = l.size = 0; return 1;int seqsearch(linelist l,int n,keytype k)int i=1;while (in) return(-1);elsereturn(i);int listtraverse(linelist l,int n) elemtype *p; int i; p=l.elem; for(i=1;i=n;i+) coutpi ; coutdata=ch;createbitree(t-lchild);createbitree(t-rchild);return ok;status preorder(bitree t)if(t)printf(%c,t-data);preorder(t-lchild);preorder(t-rchild); return ok;status inorder(bitree t)if(t)inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);return ok;status postorder(bitree t)if(t)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);return ok;void levelordertraverse(bitnode* t)const maxsize=300;bitnode* qmaxsize;int front=0,rear=0;bitnode* p;if(t!=null)rear=(rear+1)%maxsize;qrear=t;while(front!=rear)front=(front+1)%maxsize;p=qfront;printf(“%c”, p-data);if(p-lchild!=null)rear=(rear+1)%maxsize;qrear=p-lchild;if(p-rchild!=null)rear=(rear+1)%maxsize;qrear=p-rchild;if(front=(rear+1)%maxsize)coutendllchild=null&bt-rchild=null) no+; preorder(bt-lchild); preorder(bt-rchild); int depth(bitree bt) int depthval,depthleft,depthright; if (!bt) depthval=0; else depthleft=depth(bt-lchild); depthright=depth(bt-rchild); depthval=1+(depthleftdepthright ?depthleft:depthright); return depthval;int bitreeempty(bitree t)if(t)return 0;elsereturn 1;char root(bitree t)if(bitreeempty(t)return 0;elsereturn t-data;char value(bitree p)return p-data;bitree parent(bitree t,bitnode* e)if(t)if(t-data=e-data)return null;if(t-lchild!=null&t-lchild-data=e-data|t-rchild!=null&t-rchild-data=e-data)return t;elsebitnode* tempp=null;if(tempp=parent(t-lchild,e)return tempp;if(tempp=parent(t-rchild,e)return tempp;return null;bitree leftchild(bitree t,bitnode* e)if(!t) return error;if(e-lchild!=null) return e-lchild;else return null; (7)图的基本操作int creategraph(algraph *g)int i,j,k;int w;vertextype va,vb;arcnode *p;scanf(%d,&(*g).kind);scanf(%d%d, &(*g).vexnum, &(*g).arcnum);for(i = 0; i (*g).vexnum; +i)scanf(%s, (*g).verticesi.data);(*g).verticesi.firstarc = null;for(k = 0;k adjvex = j;if(*g).kind = 1 | (*g).kind = 3)p-info = (int *)malloc(sizeof(int);*(p-info) = w;elsep-info = null; p-nextarc = (*g).verticesi.firstarc; (*g).verticesi.firstarc = p;if(*g).kind = 2) p = (arcnode*)malloc(sizeof(arcnode);p-adjvex = i;if(*g).kind = 3) p-info = (int*)malloc(sizeof(int);*(p-info) = w;elsep-info = null; p-nextarc = (*g).verticesj.firstarc; (*g).verticesj.firstarc = p;return 1;void dfs(algraph g,int v)int w;vertextype v1,w1;strcpy(v1,*getvex(g,v);visitedv = 1;visitfunc(g.verticesv.data);for(w = firstadjvex(g,v1); w = 0;w = nextadjvex(g,v1,strcpy(w1,*getvex(g,w)if(!visitedw)dfs(g,w);void dfstraverse(algraph g,void(*visit)(char*)int v;visitfunc = visit; for(v = 0; v g.vexnum; v+)visitedv = 0;for(v = 0; v g.vexnum; v+)if(!visitedv)dfs(g,v);printf(n);void bfstraverse(algraph g,void(*visit)(char*)int v,u,w;vertextype u1,w1;linkqueue q;for(v = 0; v g.vexnum; +v)visitedv=0;initqueue(&q);for(v = 0; v = 0; w = nextadjvex(g, u1, strcpy(w1, *getvex(g,w)if(!visitedw)visitedw = 1;visit(g.verticesw.data);enqueue(&q,w);printf(n);(8)排序/*快速排序*/void quicksort(linelist r,int s,int t) int i=s,j=t;linelist tmp;if (si &