数据结构课程设计报告
学生姓名
学 号
班 级 地信10901
长江大学
20XX.6
目 录
1.需求分析..................................................................................................................3
1.1课程设计目的….…………………………………………………………………………3
1.2课程设计内容…………………………………………………………………………….3
1.3课程设计步骤…………………………………………………………………………….4
1.4课程设计要求…………………………………………………………………………….4
2.逻辑设计……………………………………………………………………………5
2.1运行环境………………………………………………………………………………….5
2.2系统流程图……………………………………………………………………………….5
3.详细设计……………………………………………………………………………………………11
4.调试过程………………………………………………………………………….22
4.1调试过程中出现的问题和处理方式…………………………………………………..22
4.2调试分析………………………………………………………………………………..23
4.3调试结果………………………………………………………………………………..23
4.总结………………………………………………………………………………………………………………………………………26
5.附录(源代码)…………………………………………………………………………………27
1. 需求分析:
1.1 课程设计目的
《数据结构》主要介绍一些常用的数据结构,阐明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛的应用于信息学、系统工程等各种领域。
数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识,加强学生的实际动手能力和提高学生综合素质是十分必要的。
课程设计的目的:
1. 要求学生达到熟练掌握C语言的基本知识和技能。
2. 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力。
3. 提高程序设计和调试能力。通过上级机实习,验证自己设计的算法的正确性。学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。
4. 培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平。
5. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
1.2课程设计内容
(1)线性链表基本操作的实现
问题描述:线性链表的插入、删除、遍历等操作的实现。
基本要求:要求生成线性表时,可以键盘上读取元素
输出形式:有中文提示,链表元素为整形。
界面要求:有合理的提示,每个功能可以设立菜单,根据提示,完成相关的功能要求。
(2)表达式求解问题
问题描述:设计一个程序,求解算术表达式。
基本要求:以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式,实现对算术四则混合运算表达式的求值。
输入形式:表达式,例如3*(8-1)
包含的算术运算符只能有‘+’、‘-’、‘*’、‘/’、‘(’、‘)’;
输出形式:运算结果,例如3*(8-1)=21.
(3)二叉排序树的操作
问题描述:二叉排序树的建立、插入、遍历、查询等操作的实现。
基本要求:从键盘读取元素建立二叉排序树,输出它的前序、中序、后序、层序遍历后的序列。
(4)二叉树的遍历、线索及应用(用递归或非递归的方法都可以)
问题描述:建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。
基本要求:要求根据读取的元素建立二叉树,能输出各种遍历。
实现提示:可通过输入带空格的前序序列建立二叉链表。
(5)图的建立与输出
问题描述:建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。
基本要求:给出图的深度优先和广度优先遍历算法,并给出遍历过程的动态演示效果
(6)拓扑排序
问题描述:建立图的存储结构,能够输入图的顶点和边的信息,并存储到相应存储结构中,再编写函数实现图的拓扑排序。
基本要求:选择邻接表作为有向图的存储结构模拟整个过程,并输出拓扑排序的顶点序列。
1.3课程设计步骤
课程设计就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际的问题,其主要需要进行 以下几个方面的工作:首先要采用一种简明、严格的问题描述,然后设计求解方法,用计算机来实现这种求解方法,在经过测试定型后制作必要的文档。
1. 建立模型
用形式模型来刻画问题,将有益于问题的解决。对于形式化的问题,我们容易知道是否有现成的算法或程序可以利用。如涉及到多个对象及相互关系的问题时所用的模型可以为图论;在符号与文本处理问题时常用字符串来做模型。这里《数据结构》课程中所介绍的各种数据结构均可作为一种模型。
2. 构造算法
建立了适当的数学模型后,问题就可以转换为一些经典问题的综合或变异形式的求解。如模型为图,则可借助于图的深度遍历、广度遍历、求最小生成树、求最短路径、拓扑排序、关键路径、二分图的匹配、图的着色等。
3. 选择数据结构
不同的存储结构对算法的时间、空间、性能方面可能有不同的影响,选择数据结构时,除了要能将所需的数据元素极其关系存储起来外,还需要考虑所选择的结构是否便于问题的求解,时间和空间复杂度是否符合要求。
4. 编程
将问题的描述算法和数据结构,用计算机语言来表示并将其转换为完整的上机程序。
5. 总结
对设计进行总结和讨论,包括本设计的优、缺点,时、空间性能,与其他可能存在的求解方法之间的比较等。
1.4课程设计要求
1. 做好上机准备:要充分认识课程设计对自己的重要性,认真做好设计前的各项准备工作。每次上机前,要事先编制好准备调试的程序,认真想好调试步骤和有关环境的设置方法,准备好有关的文件。
2. 既要虚心接受老师的指导,又要充分发挥主观能动性。结合课题,独立思考,努力钻研,勤于实践,勇于创新。充分利用时间,安排好课程设计的时间计划,并在课程设计过程中不断检测自己的计划完成情况,及时向教师汇报。
3. 独立思考,独立完成:课程设计中各项任务的设计和调试要求独立完成,遇到问题可以讨论,但不可以拷贝。在设计过程中,要严格要求自己,树立严肃,严密,严谨的科学态度,必须按时,按质,按量完成课程设计。不得弄虚作假,不准抄袭他人内容。
4. 设计的题目要求达到一定工作量(1000行以上代码),并具有一定的深度和难度。 编写出课程设计说明书,说明书不少于2000字(代码不算)。
5. 课程设计按照教学要求需要两周时间完成,两周中每天(按每周5天)至少要上3-4小时的机来调试C语言设计的程序,总共至少要上机调试程序30小时。课程设计期间,无故缺席按旷课处理。
6. 按照任意性(用户任意给定输入,系统能够完成正确的计算),友好性(界面要友好,输入有提示,尽量展示人性化),可读性(源程序代码清晰、有层次),健壮性(用户输入非法数据时,系统要及时给出警告信息),结构性(应用程序具有良好的程序结构)要求分析设计实现。
7. 整个系统只能有一个执行程序,各项内容分别以不同文件存放,功能尽量模块化。
2. 逻辑设计
2.1运行环境
Microsoft Visual C++6.0 。Visual C++(简称VC)是Microsoft公司推出的目前使用极为广泛的基于Windows平台的C++可视化开发环境。Visual C++6.0提供的控制台应用程序对学习和掌握标准C++内容非常有利。“可视“的资源编辑器与MFC类似以及应用程序向导,为快速高效地开发出功能强大的Windows应用程序提供了极大的方便。利用Visual C++6.0进行Internet、数据库及多媒体等多方面的程序开发也容易。
2.2系统流程图
1.链表的基本操作
2.表达式求值
3.二叉排序树
4.图的建立及输出
5.拓扑排序
6.二叉树
3. 详细设计:
3.1链表的基本操作
typedef struct LNode //单链表的结点类型
{
ElemType data;
struct LNode *next;
} LNode,*LinkedList;
LinkedList LinkedListInit() //初始化单链表
{
LinkedList L;
L=(LinkedList)malloc(sizeof(LNode)); //开辟头结点
L->next=NULL;
return L;
}
LinkedList LinkedListCreat( ) //建立
{ LinkedList L=LinkedListInit(),p,r;
ElemType x;
r=L;
printf("请依次输入链表中的元素,输入-1结束\n");
scanf("%d",&x);
while (x!=flag)
{p=(LinkedList)malloc(sizeof(LNode));
p->data=x;
r->next=p;
r=p;
scanf("%d",&x);
}
r->next=NULL;
return L;
LinkedList LinkedListGet(LinkedList L,int i) //查找
{LinkedList p;int j;
p=L->next; j=1;
while (p!=NULL && j
{p=p->next; j++; }
if (j==i) return p;
else return NULL;
}
void LinkedListInsert(LinkedList L, int i, ElemType x) //插入
{LinkedList p,s; int j;
j=1; p=L;
while(p&&j
{p=p->next;j++;}
if(p==NULL||j>i)
printf("插入位置不正确\n");
else {s=(LNode *)malloc(sizeof(LNode));
s->data=x;
s->next=p->next;
p->next=s;
printf("%d已插入到链表中\n",x);
}
}
void LinkedListDel(LinkedList L,int i) //删除
{ LinkedList p,q;
int j;
j=1;p=L;
while(p->next&&j
{p=p->next;j++;}
if(p->next==NULL)
printf("删除位置不正确\n");
else {q=p->next;p->next=q->next;free(q);
printf("第%d个元素已从链表中删除\n",i);
}
3.2表达式求值
//定义算符栈结构体
typedef struct
{
char fun;
int grade;
}Functor;
//将表示数据的字符串转化成数值
float Char_To_Num()
{
int flag=0, i=-1;
float value=0.0;
while((ch[sub]>=48 && ch[sub]<=57) || ch[sub]=='.')
{
if(ch[sub]=='.')
flag=1;
else
{
if(flag==0) value=value*10+ch[sub]-48;
else
{
value=value+( ch[sub]-48 )*pow(10,i);
i--;
}
}
sub++;
}
return value;
}
//算符在栈内时的级别
int In_Grade(char c)
{
int g;
switch(c)
{
case '^': g=3;break;
case '*':
case '/':
case '%': g=2;break;
case '+':
case '-': g=1;break;
case '(': g=0;break;
case ')': g=-1;break;
}
return g;
}
//算符在栈外时的级别
int Out_Grade()
{
int g;
switch(ch[tub])
{
case '^': g=4;break;
case '*':
case '/':
case '%': g=2;break;
case '+':
case '-': g=1;break;
case '(': g=4;break;
case ')': g=-1;break;
}
return g;
}
3.3二叉排序树
//定义二叉树数据结构
typedef struct TNode
{
int num;
struct TNode *lchild, *rchild;
}TNode;
//定义插入新节点的初始函数
void Insert_Node(int n)
{
if(root==NULL) //如果根结点不存在则创建
{
root=(TNode *)malloc(sizeof(TNode));
root->num=n;
root->lchild=NULL;
root->rchild=NULL;
}
else
{
myInsert_Node(root, n);//非根结点的插入操作
}
}
//前序递归遍历二叉树
void Pre_travel(TNode *p)
{
if(p)
{
printf(" %d ",p->num);
Pre_travel(p->lchild);
Pre_travel(p->rchild);
}
}
//中序递归遍历二叉树
void Mid_travel(TNode *p)
{
if(p)
{
Mid_travel(p->lchild);
printf(" %d ",p->num);
Mid_travel(p->rchild);
}
}
//后序递归遍历二叉树
void Suf_travel(TNode *p)
{
if(p)
{
Suf_travel(p->lchild);
Suf_travel(p->rchild);
printf(" %d ", p->num);
}
}
//查找
int Node_search(int key) {
if(root==NULL)
return 0;
else
{
if(key==root->num)
return 1;
else
{
return myNode_search(root, key);
}
}
}
3.4图的建立及输出
//定义表结点
typedef struct st_arc
{
int adjvex; //该弧所指向的顶点的位置
int weight; //弧的权值
struct st_arc *nextarc; //指向下一弧的指针
}arcnode;
//定义头结点
typedef struct
{
int vertex; //顶点信息
struct st_arc *firstarc; //指向第一条依附该顶点的弧的指针
}vernode,adjlist[maxnode];
//从顶点K出发深度优先搜索
void dfs(adjlist g,int k,int visited[])
{
arcnode *p;
int w;
visited[k]=1;
printf("%d ",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{
w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}
//从顶点K出发广度优先搜索
void bfs(adjlist g,int k,int visited[])
{
int front=0,rear=1,w;
arcnode *p;
visited[k]=1;/*访问初始顶点*/
printf("%d ",k);
queue[rear]=k;/*初始顶点入队列*/
while(front!=rear)
{
front=(front+1)%M;
w=queue[front];/*按访问次序依次出队列*/
p=g[w].firstarc;
while(p!=null)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
printf("%d ",p->adjvex);
rear=(rear+1)%M;
queue[rear]=p->adjvex;;
}
p=p->nextarc;
}
}
}
3.5拓扑排序
typedef struct biaoNode
{
int xiabiao;//数据域
struct biaoNode *nextbiao;//指针域
}biaoNode;//表结点的定义
typedef struct touNode //头结点
{
int data;//数据域
int indegree;//度数
biaoNode *firstarc;//指针
}touNode,AdjList[MAX];//AdjList[MAX]邻接表存储方式
typedef struct
{
AdjList shuzu;//数组邻接表
int dingdianshu,bianshu;//dingdianshu顶点数,bianshu边数
}tu;//图的定义
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;//栈
void creattu(tu *G)//创建图
{
int m, n, i;
biaoNode *p;//表结点指针
printf(" input dingdianshu and bianshu:");
scanf("%d %d",&G->dingdianshu,&G->bianshu);//输入节点数和边数
for (i = 1; i <= G->dingdianshu; i++)//for循环是初始化一个图,数据域为i,度数为0,第一个相邻的弧为空
{
G->shuzu[i].data = i;
G->shuzu[i].indegree=0;
G->shuzu[i].firstarc =NULL;
}
for(i=1 ; i <= G->dingdianshu;i++)//若下标或者第一个相邻的点不符合要求泽输出错误,要求重新输入
{
printf(" 输出各条边的起点和终点:\n ");
scanf("%d%d",&n,&m);
p = (biaoNode*)malloc(sizeof(biaoNode));//分配一个节点用来存储刚才下标为m信息
if (p == NULL)//没有分配成功,则输出错误
{
printf("error");
exit(0);
}
p->xiabiao = m;//p下标m
p->nextbiao = G->shuzu[n].firstarc;//p的nextbiao指针指向n
G->shuzu[n].firstarc = p;//同理n的第一个邻接点是m也就是p
G->shuzu[m].indegree++;//m的入度+1,因为相邻n,因为是有向图,
}
}
//在有向图中查找一个没有前驱的顶点并添加到顶点表中。(2)从图中删除该顶点和所有以该顶点为尾的弧。重复上述两步,当图为空时,顶点表将以拓扑次序出现。
void paixu(tu G)
{
int count=0;
int i;
biaoNode *p;
SqStack S;
InitStack(&S);
for(i=1;i<=G.dingdianshu;++i)//找出入度为0的节点,入栈
{
if(G.shuzu[i].indegree==0)
Push(&S,i);
}
printf(" G input:");
while(!StackEmpty(&S))//如果栈不空,也就是有入度为0的节点
{
i=Pop(&S);//弹出
printf("%d ",i);
++count;//计数器+1
for(p=G.shuzu[i].firstarc;p!=NULL;p=p->nextbiao)//与i相邻的节点度数减1
{
G.shuzu[p->xiabiao].indegree--;
if(G.shuzu[p->xiabiao].indegree==0)
Push(&S,p->xiabiao);//如果减1后,其入度为0,则入栈
}
}
printf("\n");
if(count!=G.dingdianshu)//排序后技术器的度数不是这个图的节点数,那么,就是出现错误了,否则排序成功。
printf(" 出现错误\n");
else
printf(" 排序成功\n");
}
3.6二叉树的操作
typedef struct node
{ //结点定义
TreeData data;
struct node *lchild, *rchild;
} BinTreeNode;
typedef BinTreeNode * BinTree; //根指针
BinTreeNode *CreateBT() // 建立二叉树
{ BinTreeNode *t;
char x;
scanf("%c",&x);
getchar();
if(x=='0')
t=NULL;
else
{ t=new BinTreeNode;
t->data=x;
printf("\n\t\t请输入%c结点的左子结点:",t->data);
t->lchild=CreateBT();
printf("\n\t\t请输入%c结点的右子结点:",t->data);
t->rchild=CreateBT();
}
return t;
}
Preorder(BinTreeNode *T) // 先序遍历
{
if(T)
{ printf("%3c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
Inorder(BinTreeNode *T) // 中序遍历
{ if(T)
{ Inorder(T->lchild);
printf("%3c",T->data);
Inorder(T->rchild);
}
}
Postorder(BinTreeNode *T) // 后序遍历
{ if(T)
{ Postorder(T->lchild);
Postorder(T->rchild);
printf("%3c",T->data);
}
}
Count ( BinTreeNode *T )
{
if ( T == NULL ) return 0;
else return 1 + Count ( T->lchild )+ Count ( T->rchild );
}
4.调试过程
4.1调试过程中出现的问题和处理方式:
为了使系统具有一定的容错性,当输入错误信息时应给出相应提示以正确输入数据。如:在switch语句中,需要用到default语句,用来表明不存在的case,并提示出错。
在每次功能结束时想返回主菜单进行其他项时,可以在子菜单switch语句中多写一条case语句,退出该子菜单。
程序出现语法错误:用scanf语句输入信息总是忘带地址符&;程序不完整,括号不匹配,如s=(Lnode *)malloc(sizeof(Lnode),少写了一个反括号;忘了定义变量名,在编译时常出现无法识别该变量的错误,其他的很多细节错误,像语句结尾漏了分号等,就不一一赘述了。
程序出现逻辑错误:参数传递不过去,调用函数不成功,以致得不到想要的结果。
指针问题:在使用指针之前没有对它初始化,这样很不安全。如:char *name;再将name做为一个指针传到函数中,你的本意可能是想通过函数改变你的字符串,但这里你忽略了一个问题,你没有初始化你的指针却用了它,虽然你有时可以运行,却有了不安定的因素。你可以这样定义:char name[20];这里的name是一个常量地址,也是一个数组名,因此不用担心它没有被初始化。字符数组与字符串的区别是前者不用在最末位加一个’\0’,但你如果把它当做字符串用时系统会自动给你加上的,因此在定义字符数组时尽量多定义一位)
4.2调试分析
(1)函数调用。函数调用是语言中一块十分重要部分,它可以把一个程序分成若干部分,然后进行配置。
(2)对结构体的不熟练。结构体的嵌套让我费尽脑汁,通过长时间的运用,终于可以得心应手。
(3)循环的问题。大量的循环语句的应用、分析,使我感到头疼,循环是计算机语言中很重要的部分,绝大部分程序都离不开循环。
4.3调试结果
主菜单
数 据 结 构 课 程 设 计
地 信 10901 李 娜 序 号:10
************************************
* 请按以下提示进行操作: *
* 1.链表 *
* 2.表达式求值 *
* 3.二叉排序树 *
* 4.图的建立与输出 *
* 5.拓扑排序 *
* 6.二叉树 *
************************************
##############################
请选择:
链表
- - - - - - - - - - - - - 链 表 的 基 本 操 作 - - - - - - - - - - - -
建立有表头结点的单链表,以-1作为创建链表完成的标志:
2 3 6 8 4 -1
输 出: 2 3 6 8 4
表长(头结点不计算在内):5
**********************************************
按序号查找,请输入你要查找的结点的序号:
2
找到了,该结点存放的数据:3
***********************************************
按值查找,请输入你要查找的数据:
3
找到了
***********************************************
插入结点,请输入你要插入的位置和数值
3 8
插入成功
输 出: 2 3 8 6 8 4
表长(头结点不计算在内):6
***********************************************
按序号删除,请输入你要删除的结点的序号:
4
删除成功
输 出: 2 3 8 8 4
表长(头结点不计算在内):5
***********************************************
按值删除,请输入你要删除的数据:
1
你要删除的结点不存在
你要删除的结点无前驱结点
输 出: 2 3 8 8 4
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
表达式求值
- - - - - - - - - - - - - 表 达 式 求 值 - - - - - - - - - - - - - - - - - - - - -
请输入要求解的表达式,并以等号“=”结束:
(4+7)*2+9/5=
(4+7)*2+9/5=23.80
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
二叉排序
- - - - - - - - - - - - - 二 叉 排 序 树 - - - - - - - - - - - - - - - - - - - - - -
请输入二叉树结点总数: 5
请依次输入结点数值大小(以空格或者回车隔开):7 1 3 9 5
*****************************************
先序递归遍历后的结果为:
7 1 3 5 9
中序递归遍历后的结果为:
1 3 5 7 9
后序递归遍历后的结果为:
5 3 1 9 7
层次遍历后的结果为:
7 1 9 3 5
*****************************************
请输入要查找的关键字(数字,非数字时终止):
3
该关键字存在!
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
图的建立及输出
- - - - - - - - - - - - - 图 的 建 立 与 输 出 - - - - - - - - - - - - - - - - - -
Input Vertex and Edge numbers of Graph:4,4
The info of 1 Vertex:1
The info of 2 Vertex:2
The info of 3 Vertex:3
The info of 4 Vertex:4
The Initial node,Terminal node and Weight of 1 Edge:1,2,0
The Initial node,Terminal node and Weight of 2 Edge:1,3,0
The Initial node,Terminal node and Weight of 3 Edge:1,4,0
The Initial node,Terminal node and Weight of 4 Edge:2,3,0
Output Undigraph Adjacency List:
1 1->4,0->3,0->2,0->Null
2 2->3,0->1,0->Null
3 3->2,0->1,0->Null
4 4->1,0->Null
The Depth_First Search of Graph:1 4 3 2
The Breadth_First Search:1 4 3 2
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
拓扑排序
- - - - - - - - - - - - - - -拓 扑 排 序 - - - - - - - - - - - - - - -
input dingdianshu and bianshu:4 4
输入各条边的起点和终点: 1 2
输入各条边的起点和终点:1 3
输入各条边的起点和终点:1 4
输入各条边的起点和终点:2 3
G input:1 2 3 4
排序成功
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
二叉树
二 叉 树 子 系 统
*****************************************
* 1---------建 二 叉 树 *
* 2---------先 序 遍 历 *
* 3---------中 序 遍 历 *
* 4---------后 序 遍 历 *
* 5---------结 点 总 数 *
* 6---------返 回 *
*****************************************
请选择菜单号(1--6):
4. 总结
经过两个星期的上机实践学习,使我对数据结构及C语言有了更进一步的认识和了解,要想学好它重在实践,要通过不断的上机操作才能更好地学习它,通过实践,我也发现我的好多不足之处,首先是自己在指法上还不行,经常按错字母,通过学习也有所改进;再有对C语言函数参数的传递掌握不熟,这可让我吃了好大苦,就那一个错误死活调不出来。通过本次课程设计,我对数据结构的认识有了个突破性的改进,因为这让我认识到了数据结构的实际应用,不再觉得自己所学的东西一无用处了。懂得了结合实际来考虑和思考,更懂得了怎样把所学知识应用到实际当中,激发我的学习积极性。
当然,在程序设计的过程中出现了不少的问题。由于程序是多人分块写的,所以在程序结合的时候,出现了参数传递的错误,条件设定不全,变量类型定义错误等问题。但是,通过自己不断努力这些问题最终还是被解决了,这也使我认识到不懂就问的道理。
两周的数据结构上机实习已经结束了,留给我们的路却漫长而幽远。本次上机实习,对我来说可以算是一个挑战,因为在理论学习中没有好好掌握,现在要独立完成一个复杂程序的编写,确实有一点困难。但我们对于难度一向是以积极迎战的态度来面对,认真努力完成上机任务。相信这次上机实习对今后程序编写方面会有很大的帮助,今后我们必须认真思考,而且要践行我们的承诺,一步一个脚印的走下去,才可以到达我们预期的彼岸。
5.附录
源代码
main.cpp
#include
#include
#include
#include"lianbiao.h"
#include"biaodashi.h"
#include"erchapaixu.h"
#include"tu.h"
#include"tuopupaixu.h"
#include"erchashu.h"
extern char ch[100];
extern TNode *root=NULL;
void main()
{
int opt;
printf("\n");
printf(" 数 据 结 构 课 程 设 计\n");
printf("\n");
printf(" 地 信 10901 李 娜 序 号:10 \n");
printf("\n");
do
{
printf("\n");
printf("\t\t************************************\n");
printf("\t\t*\t请按以下提示进行操作: *\n");
printf("\t\t*\t1.链表 *\n");
printf("\t\t*\t2.表达式求值 *\n");
printf("\t\t*\t3.二叉排序树 *\n");
printf("\t\t*\t4.图的建立与输出 *\n");
printf("\t\t*\t5.拓扑排序 *\n");
printf("\t\t*\t6.二叉树 *\n");
printf("\t\t************************************\n");
printf("\n");
printf("\t\t ##############################\n");
printf("\t\t 请选择: ");
scanf("%d*",&opt);
printf("\t\t ##############################\n");
printf("\n");
switch(opt)
{
case 1:
{
Lnode *L,*p;
int n,m,k;
printf("- - - - - - - - - - - - - 链 表 的 基 本 操 作 - - - - - - - - - - - - - \n");
L=Creat_LinkList();
Print_LinkList(L);
printf(" 表长(头结点不计算在内):%d\n",Length_LinkList(L));
printf(" **********************************************\n");
printf(" 按序号查找,请输入你要查找的结点的序号:\n ");
scanf("%d",&n);
p=Get_LinkList(L,n);
if(NULL==p)
printf(" 未找到\n");
else
printf(" 找到了,该结点存放的数据:%d\n",p->data);
printf(" ***********************************************\n");
printf(" 按值查找,请输入你要查找的数据:\n ");
scanf("%d",&n);
p=Locate_LinkList(L,n);
if(NULL==p)
printf(" 未找到\n");
else
printf(" 找到了\n");
printf(" ***********************************************\n");
printf(" 插入结点,请输入你要插入的位置和数值\n ");
scanf("%d%d",&k,&n);
m=Insert_LinkList(L,k,n);
if(0==m)
printf(" 前驱结点不存在不能插入\n");
else if(1==m)
printf(" 插入成功\n");
Print_LinkList(L);
printf(" 表长(头结点不计算在内):%d\n",Length_LinkList(L));
printf(" ***********************************************\n");
printf(" 按序号删除,请输入你要删除的结点的序号:\n ");
scanf("%d",&n);
m=Del_LinkList(L,n);
if(-1==m)
printf(" 你要删除的结点无前驱结点\n");
else if(0==m)
printf(" 你要删除的结点不存在\n");
else if(1==m)
printf(" 删除成功\n");
Print_LinkList(L);
printf(" 表长(头结点不计算在内):%d\n",Length_LinkList(L));
printf(" ***********************************************\n");
printf(" 按值删除,请输入你要删除的数据:\n ");
scanf("%d",&n);
m=Remove_LinkList(L,n);
if(-1==m)
printf(" 你要删除的结点无前驱结点\n");
else if(0==m)
printf(" 你要删除的结点不存在\n");
else if(1==m)
printf(" 删除成功\n");
Print_LinkList(L);
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
}
break;
case 2:
{
float result;
printf("- - - - - - - - - - - - - 表 达 式 求 值 - - - - - - - - - - - - - - - \n");
printf(" 请输入要求解的表达式,并以等号“=”结束:\n ");
scanf("%s",ch);
result=Char_Transform();
printf(" %s%.2f\n", ch, result);
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
}
break;
case 3:
{
int sum, i, key;
int data[MaxLength];
printf("- - - - - - - - - - - - - 二 叉 排 序 树 - - - - - - - - - - - - - - - \n");
printf(" 请输入二叉树结点总数:\n ");
scanf("%d",&sum);
printf(" 请依次输入结点数值大小(以空格或者回车隔开):\n ");
for(i=0;i
scanf("%d", &data[i]);
for(i=0;i
Insert_Node(data[i]);
printf(" *****************************************\n");
printf(" 先序递归遍历后的结果为:\n");
Pre_travel(root);
printf("\n 中序递归遍历后的结果为:\n");
Mid_travel(root);
printf("\n 后序递归遍历后的结果为:\n");
Suf_travel(root);
printf("\n 层次遍历后的结果为:\n");
Level_travel(root);
printf("\n");
printf(" *****************************************\n");
printf("\n 请输入要查找的关键字(数字,非数字时终止):\n ");
scanf("%d", &key);
if(Node_search(key))
printf(" 该关键字存在!\n");
else
printf(" 该关键字不存在!\n");
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n");
}
break;
case 4:
{
arcnode *p,*q;
adjlist g;
int i,j,n,k,w,e;
printf("- - - - - - - - - - - - - 图 的 建 立 与 输 出 - - - - - - - - - - - - - - \n");
printf(" Input Vertex and Edge numbers of Graph:");
scanf("%d,%d",&n,&e);
for(k=1;k<=n;k++)
{
getchar();
printf(" The info of %d Vertex:",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null; //对顺序存储部分初始化
}
for(k=1;k<=e;k++)
{
printf(" The Initial node,Terminal node and Weight of %d Edge:",k);
scanf("%d,%d,%d",&i,&j,&w);
q=(arcnode *)malloc(sizeof(arcnode));
q->adjvex=j;
q->weight=w;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=i;
p->weight=w;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
print(g,n);
printf("\n");
printf("The Depth_First Search of Graph:");
trave_dfs(g,n);
printf("\n");
printf("The Breadth_First Search:");
trave_bfs(g,n);
printf("\n");
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
}
break;
case 5:
{
tu G;
printf("- - - - - - - - - - - - - - -拓 扑 排 序 - - - - - - - - - - - - - - - - - \n");
void creattu(tu *G);
int Pop(SqStack *S);
void Push(SqStack *S,int e);
int StackEmpty(SqStack *S);
void InitStack(SqStack *S);
creattu(&G);
paixu(G);
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
}
break;
case 6:
{
manu6();
}
break;
case 0:
exit(0);
break;
default:
printf("输入有误!\n");
}
}while(opt!=0);
}
下面挑出几个功能模块:
Erchapaixu.cpp
#include
#include
# include"erchapaixu.h"
//声明插入新结点的函数(根非空)
int myInsert_Node(TNode *p, int n);
//声明全局变量root
TNode *root=NULL;
//定义插入新节点的初始函数,拆开写的目的是递归时避免不必要的判断
void Insert_Node(int n)
{
if(root==NULL) //如果根结点不存在则创建
{
root=(TNode *)malloc(sizeof(TNode));
root->num=n;
root->lchild=NULL;
root->rchild=NULL;
}
else
{
myInsert_Node(root, n);//非根结点的插入操作
}
}
int myInsert_Node(TNode *p, int n)
{
TNode *temp;
if(nnum) //比当前结点小,则访问左子树
{
if(p->lchild==NULL) //左子树为空,则插入该结点
{
temp=(TNode *)malloc(sizeof(TNode));
temp->num=n;
temp->lchild=NULL;
temp->rchild=NULL;
p->lchild=temp;
return 0;
}
else //左子树不为空,则与左子树进行比较
{
myInsert_Node(p->lchild,n);
}
}
else //右子树同理
{
if(p->rchild==NULL)
{
temp=(TNode *)malloc(sizeof(TNode));
temp->num=n;
temp->lchild=NULL;
temp->rchild=NULL;
p->rchild=temp;
return 0;
}
else
{
myInsert_Node(p->rchild,n);
}
}
return 1;
}
//前序递归遍历二叉树
void Pre_travel(TNode *p)
{
if(p)
{
printf(" %d ",p->num);
Pre_travel(p->lchild);
Pre_travel(p->rchild);
}
}
//中序递归遍历二叉树
void Mid_travel(TNode *p)
{
if(p)
{
Mid_travel(p->lchild);
printf(" %d ",p->num);
Mid_travel(p->rchild);
}
}
//后序递归遍历二叉树
void Suf_travel(TNode *p)
{
if(p)
{
Suf_travel(p->lchild);
Suf_travel(p->rchild);
printf(" %d ", p->num);
}
}
//释放分配的空间,防止内存泄露。
//此处的root为静态区root的拷贝,root需要单独赋空值。
void Free_node(TNode *p)
{
if(p)
{
Free_node(p->lchild);
Free_node(p->rchild);
free(p);
p=NULL;
}
}
//层次遍历二叉树
void Level_travel(TNode *bitree)
{
int i,j;
TNode *array[MaxLength], *temp;//建立一个先入先出的队列array,j标识队列增长,i控制输出
temp=bitree;
if(temp!=NULL)//初始化变量
{
i=0;
array[i]=temp;
j=1;
}
while(i!=j)
{
temp=array[i];//控制层次遍历顺序
printf(" %d ", temp->num);
if(temp->lchild!=NULL)
{
array[j]=temp->lchild;//左子树存在,入队列
j++;
}
if(temp->rchild!=NULL)
{
array[j]=temp->rchild;//右子树存在,入队列
j++;
}
i++;
}
}
//声明核心查找函数
int myNode_search(TNode *p, int key);
//二叉树的查找,拆开写的目的是递归时避免不必要的判断
int Node_search(int key)
{
if(root==NULL)
return 0;
else
{
if(key==root->num)
return 1;
else
{
return myNode_search(root, key);
}
}
}
int myNode_search(TNode *p, int key)
{
//printf("p.num:%d key:%d\n",p->num,key);
if(key==p->num)
return 1;
else
{
if(keynum)
{
if(p->lchild!=NULL)
return myNode_search(p->lchild, key);
else
return 0;
}
else
{
if(p->rchild!=NULL)
return myNode_search(p->rchild, key);
else
return 0;
}
}
}
tu.cpp
#include
#include
#define maxnode 30
#define null 0
#define M 20
//定义表结点
typedef struct st_arc
{
int adjvex; //该弧所指向的顶点的位置
int weight; //弧的权值
struct st_arc *nextarc; //指向下一弧的指针
}arcnode;
//定义头结点
typedef struct
{
int vertex; //顶点信息
struct st_arc *firstarc; //指向第一条依附该顶点的弧的指针
}vernode,adjlist[maxnode];
//typedef vernode adjlist[maxnode];
int queue[maxnode];
//从顶点K出发深度优先搜索
void dfs(adjlist g,int k,int visited[])
{
arcnode *p;
int w;
visited[k]=1;
printf("%d ",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{
w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}
//从顶点K出发广度优先搜索
void bfs(adjlist g,int k,int visited[])
{
int front=0,rear=1,w;
arcnode *p;
visited[k]=1;/*访问初始顶点*/
printf("%d ",k);
queue[rear]=k;/*初始顶点入队列*/
while(front!=rear)
{
front=(front+1)%M;
w=queue[front];/*按访问次序依次出队列*/
p=g[w].firstarc;
while(p!=null)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
printf("%d ",p->adjvex);
rear=(rear+1)%M;
queue[rear]=p->adjvex;;
}
p=p->nextarc;
}
}
}
//数组visited标志图中的顶点是否已被访问<广度>
void trave_bfs(adjlist g,int n)
{
int i,visited[maxnode];
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
bfs(g,i,visited);
}
//数组visited标志图中的顶点是否已被访问<深度>
void trave_dfs(adjlist g,int n)
{
int i,visited[maxnode];
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}
//输出
void print(adjlist g,int n)
{
arcnode *q;
int i;
printf(" Output Undigraph Adjacency List:\n");
for(i=1;i<=n;i++)
{
printf("\t%d\t",i);
printf("%d->",g[i].vertex);
q=g[i].firstarc;
while(q!=null)
{
printf("%d,",q->adjvex);
printf("%d->",q->weight);
q=q->nextarc;
}
printf("Null");
printf("\n");
}
}