数据结构实验系统源代码期末作业.docx
- 文档编号:2677965
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:81
- 大小:33.24KB
数据结构实验系统源代码期末作业.docx
《数据结构实验系统源代码期末作业.docx》由会员分享,可在线阅读,更多相关《数据结构实验系统源代码期末作业.docx(81页珍藏版)》请在冰点文库上搜索。
数据结构实验系统源代码期末作业
/*树子系统*/
#include
#include
#defineMAX100
intcount=0;/*定义计算结点个数的变量*/
typedefstructtnode
{
chardata;
structtnode*lchild,*rchild;
}BT;
BT*CreateBTree()
{
BT*t;
charch;
scanf("%c",&ch);
getchar();
if(ch=='0')
t=NULL;
else
{
t=(BT*)malloc(sizeof(BT));
t->data=ch;
printf("请输入%c结点的左孩子结点:
",t->data);
t->lchild=CreateBTree();
printf("请输入%c结点的右孩子结点:
",t->data);
t->rchild=CreateBTree();
}
returnt;
}
voidShowBTree(BT*T)/*用广义表表示法显示二叉树*/
{if(T!
=NULL)/*当二叉树非空时*/
{printf("%c",T->data);/*输入该结点数据域*/
if(T->lchild!
=NULL)/*若其左子树非空*/
{printf("(");/*输入左括号*/
ShowBTree(T->lchild);/*递归调用该函数输出其左子树各结点*/
if(T->rchild!
=NULL)/*若其右子树非空*/
{printf(",");/*输出逗号*/
ShowBTree(T->rchild);/*递归调用该函数输出其右子树各结点*/
}
printf(")");
}
else
if(T->rchild!
=NULL)/*二叉树左子树为空,右子树不为空时*/
{
printf("(");/*输入左括号*/
ShowBTree(T->lchild);/*递归调用该函数输出其左子树各结点*/
if(T->rchild!
=NULL)/*若其右子树非空*/
{printf(",");/*输出逗号*/
ShowBTree(T->rchild);/*递归调用该函数输出其右子树各结点*/
}
printf(")");
}
}
}
voidPreOrder(BT*T)/*先序遍历二叉树T*/
{if(T==NULL)return;/*递归调用的结束条件*/
else
{printf("%c",T->data);/*输出结点的数据域*/
PreOrder(T->lchild);/*先序递归遍历左子树*/
PreOrder(T->rchild);/*先序递归遍历右子树*/
}
}
voidInOrder(BT*T)/*中序遍历二叉树T*/
{if(T==NULL)return;/*递归调用的结束条件*/
else
{InOrder(T->lchild);/*中序递归遍历左子树*/
printf("%c",T->data);/*输出结点的数据域*/
InOrder(T->rchild);/*中序递归遍历右子树*/
}
}
voidPostOrder(BT*T)/*后序遍历二叉树T*/
{if(T==NULL)return;/*递归调用的结束条件*/
else
{PostOrder(T->lchild);/*后序递归遍历左子树*/
PostOrder(T->rchild);/*后序递归遍历右子树*/
printf("%c",T->data);/*输出结点的数据域*/
}
}
voidLevelOrder(BT*T)/*按层次遍历二叉树T*/
{intf,r;/*定义队头队尾指针*/
BT*p,*q[MAX];/*定义循环队列,存放结点指针*/
p=T;
if(p!
=NULL)/*若二叉树非空,则根结点地址入队*/
{f=1;q[f]=p;r=2;}
while(f!
=r)/*队列不空时*/
{p=q[f];
printf("%c",p->data);/*访问队首结点的数据域*/
if(p->lchild!
=NULL)/*将队首结点的左孩子入队*/
{q[r]=p->lchild;r=(r+1)%MAX;}
if(p->rchild!
=NULL)/*将队首结点的右孩子入队*/
{q[r]=p->rchild;r=(r+1)%MAX;}
f=(f+1)%MAX;
}
}
voidLeafnum(BT*T)/*求二叉树叶子结点数*/
{if(T)/*若树不为空*/
{if(T->lchild==NULL&&T->rchild==NULL)
count++;/*全局变量count为计数值,其初值为0*/
Leafnum(T->lchild);/*递归统计T的左子树叶子结点数*/
Leafnum(T->rchild);/*递归统计T的右子树叶子结点数*/
}
}
voidNodenum(BT*T)
{if(T)/*若树不为空*/
{
count++;/*全局变量count为计数值,其初值为0*/
Nodenum(T->lchild);/*递归统计T的左子树结点数*/
Nodenum(T->rchild);/*递归统计T的右子树结点数*/
}
}
intTreeDepth(BT*T)/*求二叉树深度*/
{intldep=0,rdep=0;/*定义两个整型变量,用以存放左、右子树的深度*/
if(T==NULL)
return0;
else
{ldep=TreeDepth(T->lchild);/*递归统计T的左子树深度*/
rdep=TreeDepth(T->rchild);/*递归统计T的右子树深度*/
if(ldep>rdep)
returnldep+1;
else
returnrdep+1;
}
}
voidMenuTree()/*显示菜单子函数*/
{
printf("\n二叉树子系统");
printf("\n=================================================");
printf("\n|1——建立一个新二叉树|");
printf("\n|2——广义表表示法显示|");
printf("\n|3——先序遍历|");
printf("\n|4——中序遍历|");
printf("\n|5——后序遍历|");
printf("\n|6——层次遍历|");
printf("\n|7——求叶子结点数目|");
printf("\n|8——求二叉树总结点数目|");
printf("\n|9——求树深度|");
printf("\n|0——返回|");
printf("\n================================================");
printf("\n请输入菜单号(0-9):
");
}
btree()
{
BT*T=NULL;
charch1,ch2,a;
ch1='y';
while(ch1=='y'||ch1=='Y')
{MenuTree();
scanf("%c",&ch2);
getchar();
switch(ch2)
{
case'1':
printf("请按先序序列输入二叉树的结点:
\n");
printf("说明:
输入结点后按回车('0'表示后继结点为空):
\n");
printf("请输入根结点:
");
T=CreateBTree();
printf("二叉树成功建立!
");break;
case'2':
printf("二叉树广义表表示法如下:
");
ShowBTree(T);break;
case'3':
printf("二叉树的先序遍历序列为:
");
PreOrder(T);break;
case'4':
printf("二叉树的中序遍历序列为:
");
InOrder(T);break;
case'5':
printf("二叉树的后序遍历序列为:
");
PostOrder(T);break;
case'6':
printf("二叉树的层次遍历序列为:
");
LevelOrder(T);break;
case'7':
count=0;Leafnum(T);
printf("该二叉树有%d个叶子。
",count);break;
case'8':
count=0;Nodenum(T);
printf("该二叉树共有%d个结点。
",count);break;
case'9':
printf("该二叉树的深度是%d。
",TreeDepth(T));break;
case'0':
ch1='n';break;
default:
printf("输入有误,请输入0-9进行选择!
");
}
if(ch2!
='0')
{printf("\n按回车键继续,按任意键返回主菜单!
\n");
a=getchar();
if(a!
='\xA')
{
getchar();ch1='n';
}
}
}
}
/*用邻接表存储的图子系统*/
#include"stdio.h"
#include"malloc.h"
#defineMAX100/*最大顶点数*/
typedefcharVertexType;
intvisited[MAX];/*全局变量,访问数组*/
typedefstructnode
{
intadjvex;/*邻接点域*/
structnode*next;/*指向下一邻接点的指针域*/
}EdgeNode;/*定义边表结点*/
typedefstructvexnode
{
VertexTypedata;/*顶点域*/
EdgeNode*firstedge;/*指向第一条边结点*/
}VHeadNode;/*定义顶点表结点*/
typedefstruct
{
VHeadNodeadjlist[MAX];/*邻接表头结点数组*/
intn,e;/*顶点数,边数*/
}AdjList;/*图的邻接表类型*/
voidCreateAGraph(AdjList*g,intflag)
{/*生成无向图的邻接表函数*/
inti,j,k;
EdgeNode*p;
if(flag==0)
printf("\n===========将建立一个无向图===========\n");
else
printf("\n===========将建立一个有向图===========\n");
printf("请输入图的顶点数:
");
scanf("%d",&g->n);
printf("请输入图的边数:
");
scanf("%d",&g->e);
printf("\n请输入图的各顶点信息:
\n");
for(i=0;i
{//getchar();/*接受上次输入的换行符*/
printf("第%d个顶点信息:
",i+1);
scanf("\n%c",&(g->adjlist[i].data));/*读入顶点信息*/
g->adjlist[i].firstedge=NULL;/*点的边表头指针设为空*/
}
printf("\n请输入边的信息,输入格式为:
序号1,序号2(序号依次为0、1、2...):
\n");
for(k=0;k
{
printf("请输入第%d条边:
",k);
scanf("\n%d,%d",&i,&j);
/*将编号为i的结点添加到邻接表中*/
p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex=j;
p->next=g->adjlist[i].firstedge;
g->adjlist[i].firstedge=p;
/*将编号为j的结点添加到邻接表中,有向图不用添加该结点,去掉下面if语句*/
if(flag==0)
{
p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex=i;/*邻接点序号为i*/
p->next=g->adjlist[j].firstedge;/*将新边表结点p插到顶点vi边表头部*/
g->adjlist[j].firstedge=p;
}
}
}
voidDispAGraph(AdjList*g)
{/*输出图的邻接表函数*/
inti;
EdgeNode*p;
printf("\n图的邻接表表示如下:
\n");
for(i=0;i
{
printf("%2d[%c]",i,g->adjlist[i].data);
p=g->adjlist[i].firstedge;
while(p!
=NULL)
{
printf("-->[%d]",p->adjvex);
p=p->next;
}
printf("\n");
}
}
voidDFS(AdjList*g,intvi)
{/*用邻接表存储的图以顶点vi开始深度优先遍历函数*/
EdgeNode*p;
printf("(%d,",vi);
printf("%c)",g->adjlist[vi].data);
visited[vi]=1;
p=g->adjlist[vi].firstedge;
while(p!
=NULL)
{
if(visited[p->adjvex]==0)
DFS(g,p->adjvex);
p=p->next;
}
}
voidBFS(AdjList*g,intvi)
{/*用邻接表存储的图以顶点vi开始广度优先遍历函数*/
inti,v,visited[MAX];
intqu[MAX],front=0,rear=0;/*定义循环队列*/
EdgeNode*p;
for(i=0;i
visited[i]=0;
printf("(%d,",vi);/*输出起始访问顶点*/
printf("%c)",g->adjlist[vi].data);
visited[vi]=1;
rear=(rear+1)%MAX;/*队尾指针后移*/
qu[rear]=vi;/*将vi入队*/
while(front!
=rear)/*当队不空时*/
{front=(front+1)%MAX;
v=qu[front];/*将队头元素出队,赋给顶点v*/
p=g->adjlist[v].firstedge;/*将顶点v的下一条邻接边顶点指针赋给p*/
while(p!
=NULL)
{if(visited[p->adjvex]==0)/*若未访问过*/
{visited[p->adjvex]=1;/*访问数组该元素置1,已访问*/
printf("(%d,",p->adjvex);/*输出该顶点编号*/
printf("%c)",g->adjlist[p->adjvex].data);/*输出该顶点信息*/
rear=(rear+1)%MAX;/*队尾指针后移*/
qu[rear]=p->adjvex;/*将p所指的顶点入队*/
}
p=p->next;/*p指针后移*/
}
}
}
voidMenuGraph()/*显示菜单子函数*/
{printf("\n图子系统");
printf("\n=================================================");
printf("\n|1——更新邻接表|");
printf("\n|2——深度优先遍历|");
printf("\n|3——广度优先遍历|");
printf("\n|0——返回|");
printf("\n=================================================");
printf("\n请输入菜单号(0-3):
");
}
graph()/*主函数*/
{
inti,f;
charch1,ch2,a;
AdjListg;
ch1='y';
while(ch1=='y'||ch1=='Y')
{MenuGraph();
scanf("%c",&ch2);
getchar();
switch(ch2)
{
case'1':
printf("要建立的是有向图
(1)还是无向图(0),请选择(输入1或0):
");
scanf("%d",&f);
CreateAGraph(&g,f);
DispAGraph(&g);
break;
case'2':
printf("请输入开始进行深度遍历的顶点序号(序号从0开始编号):
");
scanf("%d",&f);
printf("\n从顶点%d开始的深度优先遍历序列为:
",f);
for(i=0;i visited[i]=0; DFS(&g,f); break; case'3': printf("请输入开始进行广度遍历的顶点序号(序号从0开始): "); scanf("%d",&i); printf("\n从顶点%d开始的广度优先遍历序列为: ",i); BFS(&g,i); break; case'0': ch1='n';break; default: printf("输入有误,请输入0-3进行选择! "); } if(ch2! ='0') {printf("\n按回车键继续,按任意键返回主菜单! \n"); a=getchar(); if(a! ='\xA') { getchar();ch1='n'; } } } } /*线性表子系统*/ #include #include typedefintDataType;/*定义DataType为int类型*/ typedefstructlinknode/*单链表存储类型*/ { DataTypedata;/*定义结点的数据域*/ structlinknode*next;/*定义结点的指针域*/ }LinkList; LinkList*InitList() {/*初始化链表函数*/ LinkList*head; head=(LinkList*)malloc(sizeof(LinkList));/*动态分配一个结点空间*/ head->next=NULL; returnhead;/*头结点L指针域为空,表示空链表*/ } voidCreateListH(LinkList*head,intn) {/*头插法建立链表函数*/ LinkList*s; inti; printf("请输入%d个整数: ",n); for(i=0;i {s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/ scanf("%d",&s->data);/*读入新结点的数据域*/ s->next=head->next;/*将新结点的指针域存放头结点的指针域*/ head->next=s;/*将新结点插入头结点之后*/ } printf("建立链表操作成功! "); } voidCreateListL(LinkList*head,intn) {/*尾插法建立链表函数*/ LinkList*s,*last; inti; last=head;/*last始终指向尾结点,开始时指向头结点*/ printf("请输入%d个整数: ",n); for(i=0;i { s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/ scanf("%d",&s->data);/*读入新结点的数据域*/ s->next=NULL;/*将新结点的指针域为空*/ last->next=s;/*将新结点插入表尾*/ last=s;/*将last指针指向表尾结点*/ } printf("建立链表操作成功! "); } intLengthList(LinkList*head) {/*求链表长度函数*/ LinkList*p=head->next; intj=0; while(p! =NULL)/*当p不指向链表尾时*/ {p=p->next; j++; } returnj; } voidLocate(LinkList*head,DataTypex) {/*在链表中查找值为x的元素位置*/ intj=1;/*计数器*/ LinkList*p; p=head->next; while(p! =NULL&&p->data! =x)/*查找及定位*/ {p=p->next; j++; } if(p! =NULL) printf("在表的第%d位找到值为%d的结点! ",j,x); else printf("未找到值为%d的结点! ",x); } voidSearchList(LinkList*head,inti) {/*在链表中按位置查找元素*/ LinkList*p; intj=0; p=head;/*p指向链表的头结点*/ if(i>LengthList(head)) printf("位置错误,链表中没有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 系统 源代码 期末 作业