图形结构论文-刘天毅

小白就是拽

贡献于2018-07-11

字数:7842 关键词:

 学年论文 (课程论文、课程设计) 题  目: 数据结构课程设计 作  者: 刘天毅  所在学院: 信息科学与工程学院 专业年级: 计算机14-3 指导教师: 阿孜古丽·牙会甫 职  称:  副教授   2016年06月24日 目录 1.绪论 1 2、 《学生匹配算法的设计与实现》 1 2.1 《学生匹配算法》需求分析 8 2.2 《学生匹配算法》概要设计 8 2.2.1 数据结构的设计 8 2.2.2存储方式 8 2.2.3 基本操作的设计 8 2.3 详细设计 8 2.4关键代码 8 2.5 测试及结果分析 8 2.6 小结 8 3.《表达式的设计与计算》 9 3.1 《表达式的设计与计算》需求分析 9 3.2 《表达式的设计与计算》概要设计 9 3.2.1 数据结构的设计 9 3.2.2存储方式 9 3.2.3 基本操作的设计 9 3.3 详细设计 9 3.4关键代码 9 3.5 测试及结果分析 9 3.6 小结 9 4.《图形结构题目》 10 4.1 《》需求分析 10 4.2 《》概要设计 10 4.2.1 数据结构的设计 10 4.2.2存储方式 10 4.2.3 基本操作的设计 10 4.3 详细设计 10 4.4关键代码 10 4.5 测试及结果分析 10 4.6 小结 10 5.《检索题目》 11 6、总结 12 绪 论 在数据结构小学期课堂上,在老师的带领和指导下,我更进一步了解了有关C语言的知识,并逐渐熟练了运用Visual Stdio这个软件来编写一些具体实用的程序。 编程的目的在于加强学生对C语言更好的学习、掌握、理解从而运用。 编译软件 Visual Studio是微软公司推出的开发环境。是最流行的Windows平台应用程序开发环境。 摘 要 现今社会,人与人之间的交流要用某种能够共同理解的语言,当然,人与计算机之间也要有“语言”。程序员或操作人员是通过按某种语言规范设计程序来控制计算机的工作从而完成指定的任务。因此,程序员必须事先掌握与计算机打交道的“计算机语言”,这时我们就需要C语言,它通常用于系统软件、工程软件的设计等。C语言功能非常强大,应用广泛,一旦掌握了之后,你对计算机的认识会增加许多,以后再自学其他语言就显得轻而易举了。虽然C语言比较难学,但是只要你能理清思路,掌握它的精髓,那么学习C语言也是一件非常容易且又其乐无穷的事。 关键词:C语言程序设计 Visual Studio 2、学生匹配系统的设计与实现 2.1 《》需求分析 2.2 《》概要设计 2.2.1 数据结构的设计 2.2.2存储方式 2.2.3 基本操作的设计 2.3 详细设计 2.4关键代码 2.5 测试及结果分析 2.6 小结 3.《表达式设计与计算》 3.《表达式设计与计算》的设计与实现 3.1 《表达式设计与计算》需求分析 本次课程设计我选择的的题目是表达式设计与计算,我所了解的表达式设计与计算需要设计表达式(保存于二叉树中),中缀输出表达式(带括号),表达式的计算(运用栈操作)。 3.2 《表达式设计与计算》概要设计 我选择的题目为《表达式设计与计算》的设计与实现,本系统应完成一下几方面的功能:前缀输入表达式,中缀输出表达式,计算表达式的结果。 设计使用数据结构:二叉树,栈 3.2.1 数据结构的设计 1.二叉树的定义 typedef char datatype; typedef struct Node//二叉树 { datatype data; struct Node *Lchild; struct Node *Rchild; }BTnode,*Btree; 2.栈的定义 struct Stack1 { int data[100]; int top; }m; void pushm(int x) { m.top++; m.data[m.top]=x; } void initm() { m.top=-1; } void popm() { m.top--; } struct Stack2 { char data[10]; int top; }n; void pushn(char y) { n.top++; n.data[n.top]=y; } void initn() { n.top=-1; } void popn() { n.top--; } 3.2.2存储方式 1)二叉链表存储结构。 2)顺序栈存储结构。 3.3 基本操作的设计 1) void ReadExpr(Btree *bt)//以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 2) void WriteExPr(Btree root,char *a,int &i)//--用带括弧的中缀表示式输出表达式E。 3) int Value(char *A)//计算表达式的值 4) char Assign(char c)//实现对变量V的赋值(V=c;),变量的初值为0 5) char compare(char q1,char q2)//比较算符优先程度的函数 6)int operate(int p1,int p2,char q)//计算函数,q代表运算符,p1为运算符的左边数值,p2为运算符的右边数值 7)int isnot_oper(char oper)//判断不是运算符的函数 3.4 详细设计 主菜单 构 造 复 合 表 达 式 构 造 单 表 达 式 退 出 图3-1 流程图 3.5关键代码 1) void ReadExpr(Btree *bt)//以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 void ReadExpr(Btree *bt)//以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 { char ch; ch=getchar(); if(ch=='.') *bt=NULL; else { *bt=(Btree)malloc(sizeof(BTnode)); (*bt)->data=ch; ReadExpr(&(*bt)->Lchild); ReadExpr(&(*bt)->Rchild); } } 2) void WriteExPr(Btree root,char *a,int &i)//--用带括弧的中缀表示式输出表达式E。 void WriteExPr(Btree root,char *a,int &i)//--用带括弧的中缀表示式输出表达式E。 { if(root!=NULL) { if(root!=NULL && root->Lchild!=NULL && root->Lchild->Rchild==NULL && root->Lchild->Rchild==NULL) { printf("("); a[i]='('; i++; } WriteExPr(root->Lchild,a,i); printf("%c",root->data); a[i]=root->data; i++; WriteExPr(root->Rchild,a,i); if(root!=NULL && root->Rchild!=NULL && root->Rchild->Rchild==NULL && root->Rchild->Rchild==NULL) { printf(")"); a[i]=')'; i++; } } } 3) int Value(char *A)//计算表达式的值 int Value(char *A) { int v,x,y,sum; int i=0; char c,op; char q1,q2; initm(); initn(); c=A[i]; i++; while(c!='n') { if(isnot_oper(c)) { if(((c>='a')&&(c<='z'))||((c>='A')&&(c<='Z'))) { c=Assign(c); } if(((c-'0')>=0)&&((c-'0')<=9)) { v=c-'0'; c=A[i]; i++; } if(((c-'0')>=0)&&((c-'0')<=9)) { v=v*10+c-'0'; c=A[i]; i++; } pushm(v); } else { q1=n.data[n.top]; q2=c; switch(compare(q1,q2)) { case '<': //栈顶元素优先级低 pushn(c); c=A[i]; i++; break; case '=': //脱括号 popn(); c=A[i]; i++; break; case '>': op=n.data[n.top];//出栈并运算结果 popn(); x=m.data[m.top]; popm(); y=m.data[m.top]; popm(); pushm(operate(y,x,op)); break; } } } sum=m.data[m.top]; return sum; } 4) char Assign(char c)//实现对变量V的赋值(V=c;),变量的初值为0 char Assign(char c)//实现对变量V的赋值(V=c;),变量的初值为0 { printf("\n"); printf("请对%c赋值:",c); fflush(stdin); scanf("%c",&c); return c; } 5) char compare(char q1,char q2)//比较算符优先程度的函数 char compare(char q1,char q2) //比较算符优先程度的函数 { if(((q1=='+'||q1=='-')&&(q2=='+'||q2=='-'||q2==')'||q2=='#'))||((q1=='*'||q1=='/')&&(q2=='+'||q2=='-'||q2=='*'||q2=='/'||q2==')'||q2=='#'))) return '>'; if((q1=='('&&q2==')')||(q1=='#'&&q2=='#')) return '='; else return '<'; } 6)int operate(int p1,int p2,char q) //二元运算的函数,q代表运算符,p1为运算符的左边数值,p2为运算符的右边数值 { int p; switch(q) { case '+': p=p1+p2; break; case '-': p=p1-p2; break; case '*': p=p1*p2; break; case '/': p=p1/p2; break; } return p; } 7)int isnot_oper(char oper)//判断是否是运算符的函数 { switch(oper) { case'+': case'-': case'*': case'/': case'(': case')': case '#': return 0; default: return 1; } } 3.6 测试及结果分析 1. 结果分析:当时输入选项“1”时,清屏并提示输入表达式E0,应用前缀输入方式输入表达式,然后输出表达式会加入括号,并求出结果,图为简单表达式。 2. 结果分析:输入E0时,若输入的字符非0~9时,会提示请对非0~9的字符赋值的语句,输出表达式是,会在恰当的地方加入括号,最终求出结果,图为带未知变量的表达式。 3. 结果分析:当输入选项为“2”时,清屏并提示输入构造表达式E1,E2。构造方法与构造单表达式相同,当构造完成时,会提示输入E1,E2中间的运算符,输入后生成新的中缀表达式,在给未知变量赋值后输出表达式的结果。 3.7 小结 本次树形结构的实验的完成,使我对树形结构和栈的运用更加熟练,对前缀输入,中缀输出表达式有了更清晰的认识,对于求表达式值时,运用出栈入栈的算法分别将运算数和运算符结合,同时判断运算数和运算符,因输入数据为字符型, 需判断字符是否为0~9之间,如果是,则将字符转换为对于整形变量,否则将在下一步对其赋值,学习数据结构,对树的存储结构有很清楚的认识。 4.《谣言传播问题》 4.1 《谣言传播问题》需求分析 本次实验我选择的题目是《谣言传播问题》,这个实验所解决的问题是如何选择联系人使这个联系人传播到其他所有联系人的总时间最短,则需要运用图的存储结构—邻接矩阵,并且需要一个一维数组保存各个联系人传播到其他所有联系人的总时间。 4.2 《谣言传播问题》概要设计 本程序需要完成的操作:Floyd算法计算各点之间的最短路径, 需要运用到的数据结构为:图的邻接矩阵,一维数组 4.2.1 数据结构的设计 1.图的邻接矩阵存储结构定义 ##include #include #define MAX 100 #define Max 65535 typedef struct { int vexs[MAX]; int n,e; int edges[MAX][MAX]; }mgraph;//邻接矩阵存储 int A[MAX][MAX];//最短路径值的矩阵 int path[MAX][MAX];//最短路径矩阵 4.2.2存储方式 邻接矩阵存储结构。 4.2.3 基本操作的设计 1)void creatG(mgraph *ga)//创建图(用邻接矩阵存储) 2)int selectmin(int sum[],int n)//从数组中选取最小的值 3)int selectflag(int sum[],int n,int min)//找出最小值的下标(即为所选取联系人的编号) 4)void floyd(mgraph *G)//佛洛伊德算法求最短路径 5)void printt(mgraph g)//输出邻接矩阵 4.3 详细设计 函数名称 creatG(mgraph *ga) selectmin(int sum[],int n) selectflag(int sum[],int n,int min) floyd(mgraph *G) printt(mgraph g) 基本操作 创建图(用邻接矩阵存储) 从数组中选取最小的值(即为最短传播时间) 找出最小值的下标(即为所选取联系人的编号) 佛洛伊德算法求最短路径 打印邻接矩阵 返回值 Void Int Int Void Void 4.4关键代码 1.邻接矩阵存储联系人信息 void creatG(mgraph *ga)//创建图(用邻接矩阵存储) { int i,j,w,k; printf("请输入联系人数及联系人间的传播关系个数:"); scanf ("%d%d",&(ga->n),& (ga->e)); //输入联系人数及联系人间的传播关系个数 printf ("请输入联系人信息(顶点编号),建立联系人信息表:\n") ; for(i=1;i<=ga->n;i++) scanf("%d",&(ga->vexs[i])); //输入顶点信息 for(i=1;i<=ga->n;i++) for (j=1;j<=ga->n;j++) { if(i==j) ga->edges[i][j]=0; else ga->edges[i][j]=Max; } for (k=1;k<=ga->e;k++) /*联系人序号i,j和时间w,建立邻接矩阵*/ { printf ("请输入第%d条边的联系人序号i,j和时间w:",k); scanf ("%d%d%d",&i,&j,&w); ga->edges[i][j]=w; } } 时间复杂度:T(n)=O(n^2)。 2.选取联系人传播的最短时间 int selectmin(int sum[],int n)//从数组中选取最小的值 { int i,min=MAX; for(i=1;i<=n;i++) { if(sum[i]n;i++) for(j=1;j<=G->n;j++) { A[i][j]=G->edges[i][j]; if(G->edges[i][j]!=Max) path[i][j]=j; else path[i][j]=0; } for(k=1;k<=G->n;k++) for(i=1;i<=G->n;i++) for(j=1;j<=G->n;j++) if(A[i][k]+A[k][j]n;i++) { for(j=1;j<=G->n;j++) { if(i!=j) { if(A[i][j]==Max) { printf("谣言不能由联系人%d传到联系人%d\n",i,j); printf("\n"); continue; } printf("联系人%d到联系人%d的传播时间为:%d \t",i,j,A[i][j]); next=path[i][j]; printf("传播路径为:%d",i); while(next!=j) { printf("->%d",next); next=path[next][j]; } printf("->%d\n",j); printf("\n"); sum[i]+=A[i][j]; } } printf("-----------联系人%d到其他联系人的总时间为:%d--------\n",i,sum[i]); printf("----------------------------------------------------\n"); } min=selectmin(sum,G->n); m=selectflag(sum,G->n,min); printf("\n"); printf("*******************************************************************************\n"); printf("*选择联系人%d作为第一个传播谣言的人,可使谣言传遍所有的人的时间最短,时间为:%d *\n",m,min); printf("*******************************************************************************\n"); } 时间复杂度:T(n)=O(n^3)。 5.输出联系人的邻接矩阵 void printt(mgraph g)//输出邻接矩阵 { int i,j; printf("图的邻接矩阵表示为:\n"); for(i=1;i<=g.n;i++) { for(j=1;j<=g.n;j++) printf("%d\t",g.edges[i][j]); printf("\n"); } printf("\n"); } 时间复杂度:T(n)=O(n^2)。 4.5 测试及结果分析 1.主界面 2.输入操作 3.输出结果(邻接矩阵) 结果分析:根据输入的联系人信息输出联系人信息的邻接矩阵。 4.输出结果(各联系人到其他所有联系人的时间及路径) 结果分析:由图可看出,根据Floyd算法计算出联系人1分别到联系人2~4的时间及路径,并最终输出联系人1到其他联系人的总时间,程序会将这个值保存在sum[]数组中。 5.输出结果(最终选择的联系人) 结果分析:选择传播总时间最短的联系人作为第一个传播谣言的人,并输出最短时间。 4.6 小结 5.《检索题目》 6、总结 新疆大学课程论文(设计)、学年论文评分表 题 目 作 者 专业年级 指导教师 指导教师评语及 评分建议 指导教师: 年 月 日 院 (部) 或 教 研 室 意 见 学院或教研室主任: 年 月 日

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ]
0 人已下载

下载文档

相关文档