[计算机软件及应用]数据结构课程设计.doc

数据结构课程设计报告学 号姓 名赵立兵班 级软1042班指导教师安徽工业大学计算机学院2012年6月目 录设计一矩阵的运算································02设计二迷宫求解··································11设计三学生成绩查询系统··························21设计四构造n个城市连接的最小生成树············28设计一矩阵的运算一、问题描述采用十字链表表示稀疏矩阵，并实现矩阵的加法运算, 要求：要检查有关运算的条件，并对错误的条件产生报警。二、 设计思路 本程序需要实现两稀疏矩阵的相加，如果用一般的数组存储矩阵，然后进行相加会很简单，但是当用十字链表表示稀疏矩阵并进行相加时，这时无疑就增加了难度。本程序通过手动输入两个任意大小的矩阵（两矩阵的大小需要一样）并输入相应位置的数值，当输入的两个矩阵的行数和列数不一样时，给出提醒输入错误。 当两矩阵一样时，分别通过调用十字链表函数，建立十字链表分别存储两矩阵中数值的相关信息。在进行矩阵相加时，先比较两矩阵在相应的同一行或列是否同时有数值。要是都有数值时，再进行比较此行或列中的同一位置是否有数，有数则进行计算并将结果插入矩阵C的十字链表中，无数时则分别插入矩阵C的十字链表的相应位置。要是两矩阵在同一行或列不是同时有值，则将相应有数值的行或列直接插入C矩阵。三、 数据结构定义本程序中考虑的内容就是矩阵中的数的十字链表相加，通过十字链表节省存储空间，并且也减少了计算量。在该方法中稀疏矩阵的每个非零元素可用一个包含5个域的结点表示结点结构信息如下图所示：除了表示非零元素所在行、列和值的三元组问题外，还增加了两个链域：指向本行中下一个非零元素行指针域cptr和指向本列的下一个非零元素列指针域rptr。 vjirptrcptrtypedef struct lnodeint i,j;/行坐标i，列坐标jstruct lnode *cptr,*rptr;/ *cptr指向本行下一个元素，*rptr指向本列下一个元素union struct lnode *next;/指向下一行datatype v;/存储稀疏矩阵该位置的数值 uval;link;4、 系统功能模块介绍开始输入矩阵A模和元素数ni<n ?yes输入A的值信息，建链表no输入矩阵B模和元素数m输入A的值信息，建链表yesi<m ?no矩阵A和矩阵B相加并输出矩阵结束五、 程序清单#include<stdio.h>#include<malloc.h>#define smax 45typedef int datatype;typedef struct lnodeint i,j;struct lnode *cptr,*rptr;union struct lnode *next;datatype v; uval;link;int flag=0;link *creatlinkmat()/*建立稀疏矩阵的函数，返回十字链表头指针*/link *p,*q,*head,*cpsmax;int i,j,k,m,n,t,s;datatype v;printf("行、列、非零元素个数(空格分隔)：");scanf("%d %d %d",&m,&n,&t);/*输入行、列，非零元素个数*/if(m>n)s=m; else s=n; head=(link *)malloc(sizeof(link);/*建立十字链表头结点*/head->i=m;head->j=n;cp0=head;/*cp是指针数组，分别指向头结点和行、列表头结点*/for(i=1;i<=s;i+)/*建立头结点循环链表*/p=(link *)malloc(sizeof(link);p->i=0;p->j=0;p->rptr=p;p->cptr=p;cpi=p; cpi-1->uval.next=p; cps->uval.next=head; printf("请输各个元素的行号、列号、值(空格分隔):n");for(k=1;k<=t;k+)printf(" 第%d个元素：",k);scanf("%d %d %d",&i,&j,&v);p=(link *)malloc(sizeof(link);p->i=i;p->j=j;p->uval.v=v;q=cpi;while(q->rptr!=cpi)&&(q->rptr->j<j)q=q->rptr;p->rptr=q->rptr;q->rptr=p;q=cpj;while(q->cptr!=cpj)&&(q->cptr->i<i)q=q->cptr;p->cptr=q->cptr;q->cptr=p;return head;void insert(int i,int j,int v,link *cp)/*插入结点函数*/link *p,*q;p=(link *)malloc(sizeof(link);p->i=i;p->j=j;p->uval.v=v;/*以下是经*p结点插入第i行链表中 */ q=cpi;while(q->rptr!=cpi)&&(q->rptr->j<j)q=q->rptr;/*在第i行中找第一个列号大于j的结点*(q->rptr)*/*找不到时，*q是该行表上的尾结点*/p->rptr=q->rptr;q->rptr=p;/* *p插入在*q之后 */*以下是将结点插入第j列链表中*/q=cpj;/取第j列表头结点while(q->cptr!=cpj)&&(q->cptr->i<i)q=q->cptr ;/*在第j行中找第一个列号大于i的结点*(q->cptr)*/*找不到时，*q是该行表上的尾结点*/p->cptr=q->cptr;q->cptr=p;/* *p插入在*q之后 */void print(link *a)/*输出十字链表的函数*/link *p,*q,*r;/p是控制行q是控制列r是控制输出的格式int k,col,t,row; col=a->j;/矩阵a的列数p=a->uval.next;/p指向第一个结点（非头结点）while(p!=a)q=p->rptr;/p指向这以一行的一个值if(q=a->cptr)break;/*处理完毕时，跳出*/ r=p;/r指向这一行的头结点while(q!=p)for(k=1;k<q->j-(r->j);k+)/输出同一行上两非零数据间的零printf(" 0");printf("%3d",q->uval.v);/输出那个非零值q=q->rptr;/q指向这一行的下一个元素r=r->rptr;/r指向q前面的一个非零元素 k=r->j;/k的值是某一行的最后一个非零元的列数for(t=k;t<col;t+)/输出一行上最后一个非零元后面的零printf(" 0");printf("n");p=p->uval.next;/p指向下一行link *add(link *a,link *b)/*p,q控制十字链a的行列,u,v控制十字链b的行列*/link *p,*q,*u,*v,*r,*cpsmax,*c;int s,i;if(a->i!=b->i|a->j!=b->j) flag=1;return NULL; /建立c的表头环链c=(link *)malloc(sizeof(link);c->i=a->i;c->j=a->j;if(c->i>c->j)s=c->i; else s=c->j;cp0=c;for(i=1;i<=s;i+)r=(link *)malloc(sizeof(link);r->i=0;r->j=0;r->rptr=r;r->cptr=r;cpi=r;cpi-1->uval.next=r;cps->uval.next =c; p=a->uval.next;u=b->uval.next;while(p!=a&&u!=b)/矩阵相加q=p->rptr;v=u->rptr;if(q=p&&v!=u)/矩阵a中第p行为空，矩阵b的第u行不为空while(v!=u)/将b的行的都复制到和矩阵中insert(v->i,v->j,v->uval.v,cp);v=v->rptr;else if(v=u&&q!=p)/矩阵a中第p行不为空，矩阵b的第u行为空while(q!=p)insert(q->i,q->j,q->uval.v,cp);q=q->rptr;else if(q!=p&&v!=u)/矩阵b的第u行和矩阵a的第p行都不为空while(q!=p&&v!=u)if(q->j<v->j)insert(q->i,q->j,q->uval.v,cp);q=q->rptr;else if(q->j>v->j)insert(v->i,v->j,v->uval.v,cp);v=v->rptr;elseif(q->uval.v+v->uval.v!=0)insert(q->i,q->j,(q->uval.v+v->uval.v),cp);q=q->rptr;v=v->rptr;if(q=p&&v!=u)/如果b未处理完，将b中未处理的值都插入到和矩阵中while(v!=u)insert(v->i,v->j,v->uval.v,cp);v=v->rptr;else if(v=u&&q!=p)/如果a未处理完，将a中未处理的值都插入到和矩阵中while(q!=p)insert(q->i,q->j,q->uval.v,cp);q=q->rptr;else; /处理完毕，不执行任何操作 else ; /矩阵b的第u行和矩阵a的第p行都为空，不执行任何操作 p=p->uval.next;u=u->uval.next;/a、b都指向下一行return c;int main()link *a,*b,*c;printf("nt课程设计一t矩阵的运算n");printf("n下面开始输入a矩阵的信息：n");a=creatlinkmat();printf(" a矩阵信息输入完毕，矩阵如下：n"); print(a);printf("n下面开始输入b矩阵的信息：n");b=creatlinkmat();printf(" b矩阵信息输入完毕，矩阵如下：n"); print(b);c=add(a,b);if(flag=1)printf("矩阵a、b不能相加!");else printf("n矩阵a与矩阵b的和为：n");print(c);printf("n"); 6、 运行及调试分析程序运行时依次输入：4 4 81 2 31 4 22 1 62 4 53 1 33 3 43 4 54 1 34 4 71 2 31 3 51 4 62 2 33 4 24 2 74 3 4运行结果截屏：七、 课程设计总结 通过本次对矩阵的运算的课程设计，让我了解到十字链表的实现方法，更加熟练的掌握了对十字链表的操作技巧，以及如何用十字链表实现矩阵之间的加法。对于十字链表的指针用法也进一步的熟练了。 在编程的过程中，曾遇到编程上的细节错误，在排查错误时发现在编程时应做到书写规范，还有适当的增加一些注释说明，这样有助于自己对程序整体架构的把握，以及出现问题时更快的找出错误的原因。遇到一些不懂得和无法实现操作的程序部分可通过书本资料查询以及向同学请教。 在程序的调试过程中，往往会发现在你编程正确的地方，系统提示你有编程错误，或者会出现整个程序全部无法运行，导致自己无法知道具体编程错误的地方在何处。此时可以通过排除法，就是将一些暂时不必要的程序部分隔离，或者加入一些代码标记，运行时观察程序运行到何处时会停止，然后就这样逐渐排除错误，最后实现整个程序的全部功能。设计二迷宫求解一、 问题描述 输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。二、 设计思路 这个程序的关键是实现在一个用“1”表示墙，“0”表示通路的迷宫里，找出一条能走出迷宫的路。在程序中通过定义一个数组maze来表示迷宫和一个数组move来试探各个方向是否有路可走，同时还定义一个栈来存储可走的路径。 由于需要用递归和非递归两种方法来实现迷宫的求解，而在递归的方法中不需要用栈来存储可走路径，替代的是，直接在迷宫中打印出走出迷宫的路线。同时因为递归操作和非递归操作都会影响到迷宫里的数值，因此不能放到同一个程序中实现，本程序通过两个程序来分别实现递归与非递归的迷宫求解。3、 数据结构定义 本程序考虑的内容就是在一个迷宫里如何定义一个move数组实现在迷宫中各个方向的试探，以及如何定义一个栈来存储可走路径。而在递归中不需用到栈，其他部分的定义和非递归的定义是一样的，所以此处数据结构的结构体做统一说明。(x-1,y)ymove数组的图像示意如右下图所示：x10010(x,y+1)(x,y-1)(x,y)10-120-13(x+1,y)增量数组move与点(x,y)相邻的四个点及坐标typedef structint xmax,ymax,dmax;/存储可走路径的坐标（x,y）,步数dint top;/栈的顶点指针seqstack,*pseqstack;typedef structint x,y;/move数组的4个试探方向item;item move4;typedef structint x,y,d;/临时迷宫路径的相关信息datatype;四、 系统功能模块介绍程序开始建立迷宫数组调用迷宫求解函数yes到达目标？no该结点出栈，指针指向前一可走方向。no剩余路径可走？yes该结点入栈，指针指向可走方向弹出栈中数值，打印可走路径结束程序开始建立迷宫数组调用迷宫求解函数yes到达目标？nono该结点值置0，指针指向上一可走方向。剩余路径可走？yes该结点值换成步骤数，指针指向可走方向。打印处理后的迷宫结束五、 程序清单；程序：非递归求解迷宫：#include<stdio.h>#include<stdlib.h>#define max 100#define m 6#define n 6typedef structint xmax,ymax,dmax;int top;seqstack,*pseqstack;typedef structint x,y;item;item move4;typedef structint x,y,d;datatype;pseqstack init_seqstack(void) /*创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败*/ pseqstack s; s=(pseqstack)malloc(sizeof(seqstack); if (s) s->top= -1; return s;int empty_seqstack(pseqstack s) /*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/ if (s->top=-1)return 1; elsereturn 0;int push_seqstack (pseqstack s, datatype temp) /*在栈顶插入一新元素x， 入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/ if (s->top=max-1) return 0; /*栈满不能入栈*/ else s->top+; s->xs->top=temp.x; s->ys->top=temp.y; s->ds->top=temp.d; return 1; int pop_seqstack(pseqstack s ,datatype *temp) /*删除栈顶元素并保存在*x， 入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/ if (empty_seqstack(s) return 0; /*栈空不能出栈 */ else temp->x=s->xs->top; temp->y=s->ys->top; temp->d=s->ds->top; s->top-;return 1; void destroy_seqstack(pseqstack *s)if(*s)free(*s);*s=NULL;return;int mazepath(int mazem+2n+2,item move,int x0,int y0)pseqstack s;datatype temp;int x,y,d,i,j,count=0;temp.x=x0;temp.y=y0;temp.d= -1;s=init_seqstack();if(!s)printf("栈初始化失败");return(0);push_seqstack(s,temp);while(!empty_seqstack(s)pop_seqstack(s,&temp);x=temp.x;y=temp.y;d=temp.d+1;push_seqstack(s,temp);while(d<4)i=x+moved.x;j=y+moved.y;if(mazeij=0)x=i;y=j;temp.x=x;temp.y=y;temp.d=d;push_seqstack(s,temp);mazexy=-1;if(x=m&&y=n)printf("走出迷宫的步骤如下：n"); while(!empty_seqstack(s)count+;pop_seqstack(s,&temp);printf(" (%d,%d) ",temp.x,temp.y);if(count%6=0)printf("n");destroy_seqstack(&s);return 1;else d=0;else d+;destroy_seqstack(&s);return 0;int main()item move4;int mazem+2n+2;int i,j;printf("nt设计二t迷宫问题(非递归求解)nn");printf("请输入%d*%d的迷宫('1'表示墙、'0'表示通路):n",m+2,m+2); for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)scanf("%d",&mazeij);printf("n");move0.x=0;move0.y=1;move1.x=1;move1.y=0;move2.x=0;move2.y=-1;move3.x=-1;move3.y=0;mazepath(maze,move,1,1);printf("nn");程序：递归求解迷宫：#include<stdio.h>#include<stdlib.h>#define m 6#define n 6typedef structint x,y;item;item move4;int path(int mazem+2,item move,int x,int y,int step)int i;step+;mazexy=step;if(x=m&&y=n)return 1;for(i=0;i<4;i+)if(mazex+movei.xy+movei.y=0)if(path(maze,move,x+movei.x,y+movei.y,step)return 1;step-;mazexy=0; return 0;int main()item move4;int mazem+2n+2;int i,j,t=0;printf("nt设计二t迷宫问题(递归求解)nn");printf("请输入%d*%d的迷宫('1'表示墙、'0'表示通路):n",m+2,m+2); for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)scanf("%d",&mazeij);printf("n");move0.x=0;move0.y=1;move1.x=1;move1.y=0;move2.x=0;move2.y=-1;move3.x=-1;move3.y=0;path(&maze,move,1,1,t);printf("n走出迷宫的步骤路线如下迷宫所示:nn");for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)printf("%dt",mazeij);printf("nn");六、 运行及调试分析两个程序运行时都依次输入：1 1 1 1 1 1 1 11 0 1 0 0 0 0 11 0 0 0 0 1 0 11 1 1 1 0 1 0 11 0 0 0 0 1 0 11 0 1 1 1 0 1 11 0 0 0 0 0 0 11 1 1 1 1 1 1 1程序运行结果截屏（非递归求解）：程序运行结果截屏（递归求解）：七、 课程设计总结 通过本次对迷宫的求解的程序设计，让我学会了在迷宫的求解问题上如何用递归和非递归的两种方法实现，以及两种方法在整个程序上数据结构定义的区别。学会了在迷宫求解过程中对迷宫的四个方向的试探方法，对于数据结构的栈的使用也有了进一步的认识。 在设计程序时，对于递归与非递归两种实现方法，一开始很模糊，然后通过参考资料和看老师上课时的课件最终实现了这两个程序。因为两个程序的输入是一样的，本来打算把两个程序合并在一起，但是在合并以后发现，在非递归的方法操作以后，会影响到递归操作，从而使迷宫求解在递归方法上无法实现。最终放弃了合并，采取分开处理。 在编程过程中，对于程序中的一些错误，我采用部分程序隔离和加入代码标记，排除了许多错误，这是一个很好的方法。同时对于无法实现的程序部分，可通过查阅资料和请教同学，从而实现自己程序想要实现的功能。设计三学生成绩查询系统一、 问题描述编写程序完成学生成绩记录的查询。学生基本情况学 号姓 名成绩99070101李小军9899070102王颜霞8699070103孙小涛5699070104单晓宏9699070105张小华8399070106李晓明7299070107陈晓婷98990701018詹外三95 若按学号进行顺序查找，例如：输入99070103，则输出 56 。 按学号排序后对学号进行折半查找。 随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。2、 设计思路 这个程序主要是实现按学号对8名学生的信息进行查找，其中查找方式分为三种：顺序查找、折半查找、二叉排序树查找。由于顺序查找、折半查找很容易实现，而二叉排序树查找需要构建二叉排序树，再进行二叉排序树查找，所以在这一步骤上有点难度。 学生信息包括序号、姓名、成绩，其中学号和姓名都是由字符实现，成绩由整形实现。在输入学生信息时直接按学号顺序输入，这样便省去了在程序中对学生的学号从新进行排序，在二叉排序树的查找过程中，只能查找那些参与构建二叉排序树的学号，二叉排序树是以第一个输入的学生学号为根结点构造二叉排序树的。三、 数据结构定义 本程序的结构体分为两部分，第一部分student实现对学生成绩的存储，第二部分BinSTreeNode实现对学生信息进行构建二叉树，其中二叉树里的学生信息不需要手动输入，可直接由函数调用复制第一部分结构体里的学生信息。typedef structchar sno11;/学号char name16;/姓名 int score;/成绩 student;typedef struct BinSTreeNodechar hao11;/二叉排序树学生学号char ming16;/二叉排序树学生姓名int fen; /二叉排序树学生成绩struct BinSTreeNode *lchild;/左子树struct BinSTreeNode *rchild;/右子树*BTree;四、 系统功能模块介绍开始输入8名学生的相关信息输入需要查找的学生号调用shun_search函数，输出查找结果（顺序查找）输入构建二叉树的的学生号调用折_search函数，输出查找结果（折半查找）调用BSTree构建二叉排序树调用BSTreeSearch函数输出查找结果（二叉排序树查找）输入需要查找的学生号结束五、 程序清单#include<stdio.h>#include<string.h>#include<stdlib.h>typedef structchar sno11;/学号char name16;/姓名 int score;/成绩 student;typedef struct BinSTreeNodechar hao11;char ming16;int fen; struct BinSTreeNode *lchild;struct BinSTreeNode *rchild;*BTree;int shun_search(student stu,int n,char x)int i,j;for(i=0;i<n;i+)if(strcmp(stui.sno,x)=0)printf("所查找的学生信息如下：n 学号t 姓名t成绩n");printf("%s %s %d",stui.sno,stui.name,stui.score);return 0;int zhe_search(student stu,int n,char x)int low,mid,high;low=0;high=n-1;while(low<=high)mid=(low+high)/2;if(strcmp(stumid.sno,x)=0)printf("所查找的学生信息如下：n 学号t 姓名t成绩n");printf("%s %s %d",stumid.sno,stumid.name,stumid.score);return 0;else if(strcmp(stumid.sno,x)>0) high=mid-1;else low=mid+1;return 0;void BSTree(BTree *t,student k) BTree r;if(*t=NULL)r=(BTree)malloc(sizeof(struct BinSTreeNode);strcpy(r->hao,k.sno);strcpy(r->ming,k.name);r->fen=k.score;r->lchild=r->rchild=NULL;*t=r;return; elseif(strcmp(k.sno,(*t)->ming)<=0)BSTree(&(*t)->lchild),k);elseBSTree(&(*t)->rchild),k);BTree BSTreeSearch(BTree t,char x)if(t=NULL) return NULL;if(strcmp(t->hao,x)=0) return t;if(strcmp(t->hao,x)>=0) return BSTreeSearch(t->lchild,x);elsereturn BSTreeSearch(t->rchild,x);main()student stu40;int i,j,k,n,b;char x12;printf("nt设计四t学生成绩查询系统nn");printf("请输入本次统计的学生数："); scanf("%d",&n);printf("n请输入这些学生的信息：n");printf("t学号t姓名 成绩n");for(i=0;i<n;i+)printf("学生%d ",i+1);scanf("%s %s %d",&stui.sno,&stui.name,&stui.score);printf("信息输入完毕.nn");printf("请输入你需要查找的学生号：");scanf("%s",x);printf("n下面进行顺序查找:n");shun_search(stu,n,x);printf("nn下面进行折半查找:n");zhe_search(stu,n,x);printf("nn下面进行二叉排序树的查找");printf("n输入构造二叉树学号的个数：");scanf("%d",&b);BTree T;T=(BTree)malloc(sizeof(struct BinSTreeNode);T=NULL;for(