数据结构实验系统源代码(期末作业)

/*树子系统 */#include<stdio.h>#include<malloc.h>#defineMAX100intcount=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;",t->data);",t->data);printf("请输入％c结点的左孩子结点:",t->data);",t->data);printf("请输入％c结点的右孩子结点:t->rchild=CreateBTree();}returnt;}/*用广义表表示法显示二叉树 /*用广义表表示法显示二叉树 *//*当二叉树非空时 *//*输入该结点数据域 *//*若其左子树非空 *//*输入左括号 *//*递归调用该函数输出其左子树各结点 *//*若其右子树非空 *//*输出逗号 *//*递归调用该函数输出其右子树各结点 */{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){/*输入左括号 /*输入左括号 *//*递归调用该函数输出其左子树各结点 *//*若其右子树非空 *//*输出逗号 *//*递归调用该函数输出其右子树各结点 */ShowBTree(T->lchild);if(T->rchild!=NULL){printf(",");ShowBTree(T->rchild);}printf(")");}}}/*先序遍历二叉树 /*先序遍历二叉树 T*//* 递归调用的结束条件 *//*输出结点的数据域 *//* 先序递归遍历左子树 *//* 先序递归遍历右子树 */{if(T==NULL)return;else{printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}/*中序遍历二叉树 /*中序遍历二叉树 T*//*递归调用的结束条件 *//*中序递归遍历左子树 *//*输出结点的数据域 *//*中序递归遍历右子树 */{if(T==NULL)return;else{InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}/*后序遍历二叉树 /*后序遍历二叉树 T*//*递归调用的结束条件 *//*后序递归遍历左子树 *//*后序递归遍历右子树 *//*输出结点的数据域 */{if(T==NULL)return;else{PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->data);}}/*按层次遍历二叉树 /*按层次遍历二叉树 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;}}TOC\o"1-5"\h\z/*若二叉树非空，则根结点地址入队 *//*队列不空时 *//*访问队首结点的数据域 *//*将队首结点的左孩子入队 *//*将队首结点的右孩子入队 */voidLeafnum(BT*T) /*求二叉树叶子结点数 */{if(T) /*若树不为空 */{if(T->lchild==NULL&&T->rchild==NULL)count++;Leafnum(T->lchild);Leafnum(T->rchild);}}TOC\o"1-5"\h\z/*全局变量 count为计数值， 其初值为 0*//*递归统计 T的左子树叶子结点数 *//*递归统计 T的右子树叶子结点数 */voidNodenum(BT*T){if(T){count++;Nodenum(T->lchild);Nodenum(T->rchild);}}intTreeDepth(BT*T){intldep=0,rdep=0;的深度*/if(T==NULL)return0;else{ldep=TreeDepth(T->lchild);rdep=TreeDepth(T->rchild);if(ldep>rdep)returnldep+1;else/*若树不为空 *//*全局变量 count为计数值， 其初值为 0*//*递归统计 T的左子树结点数 *//*递归统计 T的右子树结点数 *//*求二叉树深度 *//*定义两个整型变量， 用以存放左、 右子树/*递归统计 T的左子树深度 *//*递归统计 T的右子树深度 */returnrdep+1;void（MenuTree（）/*显示菜单子函数*/printf（"\n二叉树子系统");printf（"\nprintf（"\n================================================="）;TOC\o"1-5"\h\zprintf（"\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':TOC\o"1-5"\h\zprintf("二叉树的中序遍历序列为： ");InOrder(T);break;case'5':printf("二叉树的后序遍历序列为： ");PostOrder(T);break;case'6':printf("二叉树的层次遍历序列为： ");LevelOrder(T);break;case'7':count=0;Leafnum(T);printf("该二叉树有％~个叶子。",count);break;case'8':count=0;Nodenum(T);printf("该二叉机挡^有％~个结点。”,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"#defineMAX100typedefcharVertexType;intvisited[MAX];typedefstructnode{intadjvex;structnode*next;}EdgeNode;typedefstructvexnode{VertexTypedata;EdgeNode*firstedge;}VHeadNode;/*顶点域*//*指向第一条边结点 *//*定义顶点表结点 */typedefstruct{VHeadNodeadjlist[MAX];intn,e;}AdjList;TOC\o"1-5"\h\z/*邻接表头结点数组 *//*顶点数，边数 *//*图的邻接表类型 */voidCreateAGraph(AdjList*g,intflag){/*生成无向图的邻接表函数 */inti,j,k;EdgeNode*p;if(flag==0)printf("\n=========== 将建立一个无向图 ===========\n");elseprintf("\n=========== 将建立一个有向图 ===========\n");TOC\o"1-5"\h\zprintf（"请输入图的顶点数： "）;scanf（"%d",&g->n）;printf（"请输入图的边数： "）;scanf("%d",&g->e);printf("\n请输入图的各顶点信息： \n"/*生成有/*生成有n个顶点的顶点表 *//*接受上次输入的换行符 *//*读入顶点信息 *//*点的边表头指针设为空 */{//getchar();printf("第％~个顶点信息：",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<g->e;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<g->n;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)TOC\o"1-5"\h\z{/*用邻接表存储的图以顶点 vi开始广度优先遍历函数 */inti,v,visited[MAX];intqu[MAX],front=0,rear=0;EdgeNode*p;for(i=0;i<g->n;i++)visited[i]=0;intqu[MAX],front=0,rear=0;EdgeNode*p;for(i=0;i<g->n;i++)visited[i]=0;printf("(%d,",vi);/*辅助的访问数组赋初值 *//*输出起始访问顶点 */printf("%c)",g->adjlist[vi].data);visited[vi]=1;rear=(rear+1)%MAX;visited[vi]=1;rear=(rear+1)%MAX;qu[rear]=vi;while(front!=rear)/*队尾指针后移 *//*将vi入队*//*当队不空时 */{{front=(front+1)%MAX;v=qu[front];p=g->adjlist[v].firstedge;while(p!=NULL)TOC\o"1-5"\h\z/*将队头元素出队，赋给顶点 v*//*将顶点v的下一条邻接边顶点指针赋给 p*/{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=================================================");TOC\o"1-5"\h\zprintf("\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从顶点％~开始的深度优先遍历序列为： ",f);for(i=0;i<g.n;i++)visited[i]=0;DFS(&g,f);break;case'3':printf("请输入开始进行广度遍历的顶点序号(序号从 0开始)：");scanf("%d",&i);printf("\n从顶点％~开始的广度优先遍历序列为： ”,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';}}}}TOC\o"1-5"\h\z/*线性表子系统 */#include<stdio.h>#include<malloc.h>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("请输入％~个整数：",n);for(i=0;i<n;i++)/*生成新结点 /*生成新结点 *//*读入新结点的数据域 *//*将新结点的指针域存放头结点的指针域 *//*将新结点插入头结点之后 */scanf("%d",&s->data);s->next=head->next;head->next=s;

}printf（"建立链表操作成功！ "）;}voidCreateListL(LinkList *head,intn){/*尾插法建立链表函数 */LinkList*s,*last;inti;*/last=head; /*last始终指向尾结点，开始时指向头结点*/printf（"请输入％~个整数：",n）;for(i=0;i<n;i++){TOC\o"1-5"\h\zs=(LinkList*)malloc(sizeof(LinkList));/*生成新结点 */scanf("%d",&s->data);s->next=NULL;last->next=s;last=s;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位找到值为％~的结点！",j,x);elseprintf（"未找到值为％~的结点！",x）;voidSearchList(LinkList*head,inti)TOC\o"1-5"\h\z{/*在链表中按位置查找元素 */LinkList*p;intj=0;p=head; /*p指向链表的头结点 */if(i>LengthList(head))printf("位置错误，链表中没有该位置！ ");while(p->next!=NULL&&j<i){p=p->next;j++;}TOC\o"1-5"\h\zif(j==i) /*判断与给定的序号是否相等 */printf("在第％~位上的元素值为％d!”,i,p->data);}voidInsList(LinkList *head,inti,DataTypex){/*按位置插入元素函数 */intj=0;LinkList*p,*s;p=head;while(p->next!=NULL&&j<i-1) /*定位插入点 */{p=p->next;j++;}if(p!=NULL) /*p不为空则将新结点插到 p后*/{TOC\o"1-5"\h\zs=(LinkList*)malloc(sizeof(LinkList));/*生成新结点 s*/s->data=x; /*将数据x放入新结点的数据域*/s->next=p->next; /*将新结点s的指针域与p结点后面元素相连*/p->next=s; /*将p与新结点 s链接*/printf("插入元素成功！ ");}elseprintf("插入元素失败 ");}voidDelList(LinkList *head,inti){/*按位置删除链表中元素函数 */intj=0;

DataTypex;LinkList*p=head,*s;/*定位插入点*//*定位插入点*//*q为要删除结点*//*将要删除的数据放入指针变量 x中*//*将p结点的指针域与q结点后面元素相连*/p=p->next;j++;}if(p->next!=NULL&&j==i-1)(s=p->next;x=s->data;p->next=s->next;free(s);printf("删除第％d位上的元素％d成功！",i,x);}elseprintf（"删除结点位置错误，删除失败！ "）;}voidDispList(LinkList*head){/*显示输出链表函数*/LinkList*p;p=head->next;while(p!=NULL){printf("%5d",p->data);p=p->next;}}voidMenuLine(){ /*显示菜单子函数*/printf("\n 线性表子系统");printf("\n=================================================");TOC\o"1-5"\h\zprintf("\n| 1 建立 |");printf("\n| 2 插入 |");printf("\n| 3 删除 |");printf("\n| 4 按位置查找 |");printf("\n| 5——按元素值查找 |”);printf("\n| 6——求表长 |");printf("\n| 0 返回 |");printf("\n=================================================");printf("\n请输入菜单号(0-6):");linklist(){LinkList*head;DataTypex;inti,n;charch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){MenuLine();scanf("%c",&ch2);getchar();switch(ch2){case'1':head=InitList();TOC\o"1-5"\h\zprintf("请输入要建立线性表的长度： ");scanf("%d",&n);CreateListL(head,n); /*如改为CreateListH(L);则用头插法建立链表 */printf("建立后的线性表为： \n");DispList(head);break;case'2':printf("请输入要插入的元素位置： ");scanf("%d",&i);getchar();printf("请输入要插入的元素值： ");scanf("%d",&x);InsList(head,i,x);printf("插入元素%~后的线性表为：\n",x);DispList(head);break;case'3':printf("请输入要删除的元素位置： ");scanf("%d",&i);DelList(head,i);printf("删除第％d位的元素后的线性表为：\n",i);DispList(head);break;case'4':printf("请输入查找的元素位置(大于等于 1的整数)：");scanf("%d",&i);SearchList(head,i);break;

case'5':printf("请输入查找的整数： ");scanf("%d",&x);Locate(head,x);break;case'6':printf("该线性表的长度为 %d！",LengthList(head));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"typedefintDataType;#include"stdio.h"#include"malloc.h"typedefintDataType;typedefstructqnode{DataTypedata;structqnode*next;}LinkListQ;typedefstruct{LinkListQ*front,*rear;}LinkQueue;/*定义DataType为int类型*//*链队列存储类型 *//*定义结点的数据域 *//*定义结点的指针域 *//*定义队列的队头指针和队尾指针 *//*链队列的头指针类型 */LinkQueue*InitQueue()TOC\o"1-5"\h\z{ /*初始化链队列函数 */LinkQueue*Q;LinkListQ*p;Q=(LinkQueue*)malloc(sizeof(LinkQueue));/*建立链队列头指针所指结点 */p=(LinkListQ*)malloc(sizeof(LinkListQ));/*建立链队列的头结点 */

Q->front=p;/*Q指针所指的 front指针指向 p*/Q->rear=p;/*Q指针所指的 rear指针指向 p*/returnQ;}intEmptyQueue(LinkQueue*Q){ /*判断队空函数 */if(Q->front==Q->rear) /*链队为空 */return1;elsereturn0;}voidInQueue(LinkQueue*Q,DataTypex)TOC\o"1-5"\h\z{ /*入队函数 */LinkListQ*p;p=(LinkListQ*)malloc(sizeof(LinkListQ)); /*生成新结点 */p->data=x; /*将x存入新结点的数据域 */p->next=NULL;Q->rear->next=p; /*将新结点插入链队之后 */Q->rear=p; /*队尾指针指向队尾元素 */}intDeQueue(LinkQueue*Q,DataType*x){ /*出队函数 */LinkListQ*p;if(EmptyQueue(Q))/*调用判空函数 EmptyQueue(Q)，判断队列是否为空 */{printf("队空，不能出队元素 !");else{p=Q->front->next;else{p=Q->front->next;*x=p->data;Q->front->next=p->next;if(p->next==NULL)Q->rear=Q->front;free(p);/*队不为空 *//*p指向队头元素 *//*队头元素取出赋给 x*/*/*//**/*//*队列中只含有一个元素出队 *//*出队后队尾指针指向队头指针，此时队空/*释放原队头结点空间 */return1;intGetFront(LinkQueue*Q,DataType*x){ /*获取队头元素函数 */if(EmptyQueue(Q))/*调用判空函数EmptyQueue(Q),判断队列是否为空*/(printf("队空，无队头元素!");return0;)else /*队不为空*/(*x=Q->front->next->data;/*队头元素赋给变量 x*/return1;))voidShowQueue(LinkQueue*Q){ /*显示队中元素函数*/LinkListQ*p=Q->front->next;if(p==NULL)printf("队列为空，无元素！")；else{printf("从队列元素起栈中各元素为： ");while(p!=NULL){printf("%5d",p->data);p=p->next;)))voidMenuQueue(){ /*显示菜单子函数*/printf("\n 队列子系统");printf("\n=================================================");TOC\o"1-5"\h\zprintf("\n| 1 初始化队列 |");printf("\n| 2 入队操作 |");printf("\n| 3 出队操作 |");printf("\n| 4 求队头元素 |");printf("\n| 5 显示队中所有元素 |");printf("\n| 0 返回 |");printf("\n=================================================");printf("\n请输入菜单号(0-5):");linkqueue(){inti,n,flag;LinkQueue*Q;DataTypex;charch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){MenuQueue();scanf("%c",&ch2);getchar();switch(ch2){case'1':Q=InitQueue();printf("队列的初始化完成！ ");break;case'2':printf("请输入要入队的元素个数： ");scanf("%d",&n);printf("请输入％d个整数进行入队：",n);for(i=0;i<n;i++){scanf("%d",&x);InQueue(Q,x);}TOC\o"1-5"\h\zprintf("入队操作完成 ");break;case'3':printf("请输入要出队的元素个数： ");scanf("%d",&n);printf("出队的元素顺序依次为： ");for(i=0;i<n;i++){flag=DeQueue(Q,&x);printf("%5d",x);}if(flag==1)printf("\n出队操作成功 !");elseprintf("\n出队操作失败！ ");break;case'4':if(flag=GetFront(Q,&x))printf("当前的队头元素值为： %d",x);break;

case'5':ShowQueue(Q);break;case'0':ch1='n';break;default:printf("输入有误，请输入 0-4进行选择！ ");}if(ch2!='0'){printf("\n按回车键继续，按任意键返回主菜单！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';}}}}intEmptyStack(LinkStack*S)/*栈子系统 /*栈子系统 */#include<stdio.h>#include<malloc.h>#defineMAXSIZE1000typedefintDataType;typedefstructstacknode{DataType data;structstacknode*next;}LinkStack;LinkStack*InitStack(){/*初始化链栈函数 */LinkStack*S;S=NULL;returnS;/*初始化栈为空 */}/*数组最大长度为 100*//*定义DataType为int类型*//*链栈存储类型 *//*定义结点的数据域 *//*定义结点的指针域 */{/*判断栈空函数 */if(S==NULL) /*栈为空*/return1;elsereturn0;}LinkStack*Push(LinkStack*S,DataTypex)TOC\o"1-5"\h\z{/*入栈函数 */LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));/*生成新结点 */p->data=x; /*将x放入新结点的数据域*/p->next=S; /*将新结点插入链表表头之前 */S=p; /*新结点作为栈顶 */returnS;/*返回栈顶 S*/}LinkStack*Pop(LinkStack*S,DataType*x){/*出栈函数 */LinkStack*p;if(EmptyStack(S))/*调用判空函数EmptyStack(S),判断栈是否为空*/{printf("\t栈空，不能出栈 !");returnNULL; /*栈空不能出栈 */}else /*栈不为空 */{*x=S->data; /*栈顶元素取出赋给 x*/p=S; /*p结点指向原栈顶 S*/S=S->next; /*原栈顶S指向其下一个结点*/free(p); /*释放原栈顶空间 */returnS; /*返回栈顶 S*/}}intGetTop(LinkStack*S,DataType*x){/*获取栈顶元素函数 */if(EmptyStack(S))/*调用判空函数EmptyStack(S),判断栈是否为空*/{printf("栈空!");return0;}else /*栈不为空 */{/*栈顶元素赋给变量 /*栈顶元素赋给变量 x*/return1;voidShowStack(LinkStack*S){LinkStack*p=S;if(p==NULL)printf("\t栈空！");else{printf("从栈顶元素起栈中各元素为： ");while(p!=NULL){printf("%d",p->data);p=p->next;}}}voidD_B(LinkStack*S,DataTypex){while(x){TOC\o"1-5"\h\zS=Push(S,x%2);/*余数入栈 */x/=2; /*被除数data整除以 2，得到新的被除数 */}printf("转换后的二进制为： ");while(!EmptyStack(S)){S=Pop(S,&x);/*依次从栈中弹出每一个余数并输出 */printf("%d",x);}}voidtrans(char*exp,char*postexp){ /*将中缀表达式转换成后缀表达式函数 */struct{chardata[MAXSIZE];inttop;}op;/*运算符栈 */inti=0;op.top=-1;while(*exp!='#')/*当表达式没结束时 */{TOC\o"1-5"\h\zswitch(*exp)/*判断表达式的每个字符 */{case'(': /*当字符为 '('时*/op.top++;op.data[op.top]=*exp;/*栈顶指针增 1，运算符入栈 */exp++;/*中缀表达式指针增 1*/break;case')': /*当字符为 ')'时*/while(op.data[op.top]!='(')/*只要运算符栈顶元素不是 '('时*/{postexp[i++]=op.data[op.top];/*将栈顶运算符写入后缀表达式数组中*/op.top--; /*栈顶指针减 1*/}op.top--;exp++;/* 栈顶指针减 1，表达式指针加 1*/break;case'+':case'-':while(op.top!=-1&&op.data[op.top]!='(')/*运算符栈不为空且栈顶元素不为 '('时*/{postexp[i++]=op.data[op.top];/*将栈顶运算符写入后缀表达式数组中*/op.top--; /*运算符栈顶指针减 1*/TOC\o"1-5"\h\z}op.top++;/*运算符栈顶指针加 1*/op.data[op.top]=*exp;/*将中缀表达式元素入符号栈 */exp++;/*中缀表达式指针加 1*/break;case'*':case'/':while(op.data[op.top]=='*'||op.data[op.top]=='/')/*当栈顶元素不是 '*'和'/'时*/{postexp[i++]=op.data[op.top];/*栈顶运算符写到后缀表达式数组中*/op.top--; /*栈顶指针减 1*/TOC\o"1-5"\h\z}op.top++;/*栈顶指针加 1*/op.data[op.top]=*exp;/*中缀表达式的元素入栈 */exp++;/*表达式指针加 1*/break;case'':break;default:while(*exp>='0'&&*exp<='9')/*当表达式对象是数字 */postexp[i++]=*exp;/*将数字写到后缀表达式数组中 */exp++;/*中缀指针加 1*/}postexp[i++]='#'; /*将每个操作数之间增加分隔符 '#'*/}}while(op.top!=-1)/*当运算符栈不为空时 */{postexp[i++]=op.data[op.top];/*将栈顶运算符写入后缀表达式数组中*/op.toppostexp[i++]=op.data[op.top];/*将栈顶运算符写入后缀表达式数组中*/op.top--;/*栈顶指针减 1*/}/*为后缀表达式加一个结束标志 /*为后缀表达式加一个结束标志 */}floatcompvalue(char*postexp){ /*根据后缀表达式求值函数 */struct{floatdata[MAXSIZE];inttop;TOC\o"1-5"\h\z}st;/*数栈结点类型 */floata,b,c,d;st.top=-1;/*栈顶指针赋初值 -1*/while(*postexp!='\0')/*当后缀表达式没结束时 */{switch(*postexp){a=st.data[st.top];/*st.topa=st.data[st.top];/*st.top--;b=st.data[st.top];/*st.top--;c=b+a;st.top++;st.data[st.top]=c;/*break;TOC\o"1-5"\h\z数栈顶元素赋给变量 a*//*栈顶指针减 1*/数栈顶元素赋给变量 b*//*栈顶指针减 1*//*将a加b的结果存入变量 c*//*栈顶指针加 1*/将变量c入栈*/case'-':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b-a;st.top++;}}st.data[st.top]=c;break;casea=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b*a;st.top++;st.data[st.top]=c;break;case'/':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;if(a!=0){c=b/a;st.top++;st.data[st.top]=c;}else{printf("\n\t除零错误 !\n");//exit(0);}break;default:/*后缀表达式的字符是数字字符时，将其转换为整数 */d=0;while(*postexp>='0'&&*postexp<='9'){d=10*d+*postexp-'0';postexp++;}st.top++;st.data[st.top]=d;/*将转换之后的整数入栈 */break;}postexp++;}returnst.data[st.top];/*返回数栈的栈顶元素即为所求的结果 */voidMenuStack(){ /*显示菜单子函数*/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|0一返回|");printf("\n=================================================");printf("\n请输入菜单号(0-7):");}linkstack(){inti,n,flag;LinkStack*S;DataTypex;charch1,ch2,a;charexp[MAXSIZE],postexp[MAXSIZE];/*求表达式值的两个数组*/ch1='y';while(ch1=='y'||ch1=='Y'){MenuStack();scanf("%c",&ch2);getchar();switch(ch2){case'1':S=InitStack();printf("栈的初始化完成！")；break;case'2':printf("请输入要入栈的元素个数：");scanf("%d",&n);printf("请输入％d个整数进行入栈：",n);for(i=0;i<n;i++){scanf("%d",&x);S=Push(S,x);}printf("入栈成功！");break;case'3':printf("请输入要出栈的元素个数： ");scanf("%d",&n);printf("出栈的元素为： ");for(i=0;i<n;i++){S=Pop(S,&x);if(S!=NULL)printf("%5d",x);}break;case'4':if(flag=GetTop(S,&x))printf("当前的栈顶元素值为： %d",x);break;case'5':ShowStack(S);break;case'6':S=InitStack();TOC\o"1-5"\h\zprintf("请输入十进制正整数为 :");scanf("%d",&x); /*输入十进制正整数 */D_B(S,x); /*调用进制转换函数 */break;case'7':printf("请输入一个算术表达式(只有 +、-、*、/四种运算符) ，以'#'结束：");scanf("%s",&exp);trans(exp,postexp);printf("则该表达式的中缀表达式为： %s\n",exp);printf("转换之后的后缀表达式为(每个操作数用“ #”分隔) ：%s\n",postexp);printf("表达式的值为 :%.2f\n",compvalue(postexp));break;case'0':ch1='n';break;default:printf("输入有误，请输入 0-5进行选择！ ");}if(ch2!='0'){printf("\n按回车键继续，按任意键返回主菜单！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';/*数据结构实验系统主函数 */#include"linklist.h"#include"linkstack.h"#include"linkqueue.h#include"string.h"#include"btree.h"#include"graph.h"#include"search.h"#include"sort.h"main(){intchoice;charch;ch='y';while(ch=='y'||ch=='Y'){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|0退出|");printf("\n==================================================");printf("\n请选择菜单号(0-8):");scanf("%d",&choice);getchar();switch(choice){case1:linklist();break;case2:linkstack();break;case3:linkqueue();break;case4:string();break;case5:btree();break;case6:graph();break;case7:search();break;case8:sort();break;case0:ch='n';break;default:printf("菜单选择错误！请重新选择 ");}}}#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefintKeyType;typedefstruct{KeyTypekey;}SearchL;/*顺序表的表长 *//*关键字类型为 int型*//*存放关键字， KeyType为关键字类型 */intSeqSearch(SearchLr[],intn,KeyTypek){/*顺序查找算法函数，表中元素下标为 1到n*/inti=n;r[0].key=k; /*设元素r[o]为要查找的关键字 k(即监视哨)*/while(r[i].key!=k) /*从后向前顺序比较 */i--;return(i); /*返回查找元素下标，当为 0时表示查找失败 */}intBinSearch(SearchLr[],intn,KeyTypek){/*折半查找算法函数，表中元素下标为 1到n*/intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(k==r[mid].key)return(mid);elseif(k<r[mid].key)/*置区间初值 *//*查找区间不为空时 *//*找到待查元素 */high=mid-1;/*未找到，继续在前半区间进行查找 */elseTOC\o"1-5"\h\zlow=mid+1; /*未找到，继续在后半区间进行查找 */}return(0);}typedefstruct /*分块查找的索引表类型 */{KeyTypekey; /*关键字*/intlow,high; /*每块的低、高地址 */}IdxType;voidCreatIdx(SearchLr[],IdxTypeidx[],intm,intn){ /*分块查找的建立索引表算法函数 */inti,j,k=0; /*k为索引表下标 */KeyTypemax;for(i=0;i<m;i+=n) /*在顺序表中进行分块 */{max=r[i].key;/*将最大值设为第 i个元素关键字 */for(j=i+1;j<i+n&&j<m;j++)/*在每块中确定该块的最大值 */if(r[j].key>max)max=r[j].key;idx[k].key=max; /*将该块最大值赋给索引表第 k个元素的关键字*/idx[k].low=i; /*将该块起始下标 i赋给索引表第 k个元素的低地址 */if(i+n-1<=m-1) /*若该块长度为 m时*/idx[k].high=i+n-1;/*将该块终止下标值赋给索引表第 k个元素的高地址 */else /*若该块长度为小于 m值(最后一块)时 */idx[k].high=m-1;/*将顺序表最大元素下标值赋给该索引表第 k个元素的高地址*/k++; /*索引表下票值加 1*/}}intBlkSearch(SearchLr[],IdxTypeidx[],intm,KeyTypek){/*分块查找算法函数 */intlow,high,mid,i,j,find=0;i=0;while(idx[i].key<k)/*当索引表的关键字小于查找关键字 k时，在索引表中定位 */i++;low=idx[i].low;high=idx[i].high;while(low<=high&&!find)/*当在索引表中找到该元素所在块时 */{/*在该索引表内进行折半查找 */mid=(low+high)/2;if(k<idx[mid].key)high=mid-1;elseif(k>idx[mid].key)low=mid+1;else{high=mid-1;find=1;}}TOC\o"1-5"\h\zif(low<m)/*当在索引表中有该元素所在块时 */{i=idx[low].low; /*i赋为索引表该块的低地址 */j=idx[low].high; /*j赋为索引表该块的高地址 */}*/while(i<j&&r[i].key!=k)/*在顺序表的这个块内进行顺序查找*/i++;if(i>=j)return(-1);/*当没找到时返回 -1*/elsereturn(i);/*当找到时返回下标值 i*/}typedefstructtreenode/*二叉排序树的结点类型 */{KeyTypekey; /*关键字*/structtreenode*lchild,*rchild;/*左、右孩子指针 */}BTNode;voidDispBStree(BTNode*bt){/*用广义表显示二叉排序树函数 */if(bt!=NULL){printf("%d",bt->key);/*输出根结点的关键字 */if(bt->lchild!=NULL||bt->rchild!=NULL){/*当根结点的左、右孩子指针不为空时 */printf("(");/*输出左括号 */DispBStree(bt->lchild);/*输出该结点的左孩子 */if(bt->rchild!=NULL)/*若其右指针不为空时 */printf(",");/*输出逗号 */DispBStree(bt->rchild);/*输出该结点的右孩子 */printf(")"); /*输出右括号 */}}}BTNode*BSTInsert(BTNode*bt,KeyTypek){/*二叉排序树的元素插入函数 */TOC\o"1-5"\h\zBTNode*f,*p=bt; /*p指针指向二叉排序树的根结点 */*/while(p!=NULL) /*当p指针不为空时，由指针f确定插入位置的双亲结点*/{f=p； /*指针f指向指针p所指结点*/if(p->key>k)/*当p所指结点的关键字大于插入值时 */p=p->lchild;/*p 移到它的左孩子结点上 */elsep=p->rchild;/*p 移到它的右孩子结点上 */}p=(BTNode*)malloc(sizeof(BTNode));/*建立新结点 */p->key=k; /*将关键字 k存入新结点的数据域 */p->lchild=p->rchild=NULL;/*左、右孩子指针设为空 */if(bt==NULL)/*二叉树为空树时 */bt=p; /*新建结点作为二叉排序树的根结点 */elseif(k<f->key)/*若插入关键字 k小于其双亲结点关键字 */f->lchild=p; /*则插入为双亲结点的左孩子 */elsef->rchild=p; /*则插入为双亲结点的右孩子 */return(bt);}BTNode*CreateBST(KeyTypestr[],intn){/*建立二叉排序树函数 */inti=0;BTNode*bt=NULL;/*初始化根结点为空 */while(i<n) /*当建立没结束时 */{bt=BSTInsert(bt,str[i]);/*将第i个元素插入到二叉排序树中 */i++;}return(bt); /*返回根结点指针 */}BTNode*BSTDelete(BTNode*bt,KeyTypek){ /*在二叉排序树 t中删除关键字为 k的节点函数 */BTNode*p,*f,*s,*q;p=bt;f=NULL;while(p)/*查找关键字为 k的待删结点 p*/{if(p->key==k)break; /*找到，则跳出查找循环 */f=p; /*f指向p结点的双亲结点 */if(p->key>k)p=p->lchild;elsep=p->rchild;

if(p==NULL)returnbt;if(p->lchild==NULL){if(f==NULL)bt=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;else/*p是if(p==NULL)returnbt;if(p->lchild==NULL){if(f==NULL)bt=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;else/*p是f的右孩子 */f->rchild=p->rchild;/*free(p);}else/*p有左子树 */{q=p;s=p->lchild;while(s->rchild)/*p无左子树 *//*p是原二叉排序树的根 *//*p是f的左孩子 *//*将p的右子树链到 f的左链上 */将p的右子树链到 f的右链上 *//*释放被删除的节点 p*//*在p/*在p的左子树中查找最右下结点 */if(q==p)q->lchild=s->lchild;/*将s的左子树链到 q左孩子指针*/elseq->rchild=s->lchild;p->key=s->key; /*将s的值赋给 p*/free(s);}returnbt;BTNode*BSTSearch(BTNode*bt,KeyTypek)TOC\o"1-5"\h\z{/*二叉排序树的元素查找函数 */if(bt==NULL)return(NULL);/*空树则返回空指针 */else{if(k==bt->key)/*关键字k等于根结点关键字*/return(bt);/*返回根结点指针 */elseif(k<bt->key)/*关键字k小于根结点关键字 */return(BSTSearch(bt->lchild,k));/*到根结点的左子树查找 */elsereturn(BSTSearch(bt->rchild,k));/*到根结点的右子树查找 */}}voidMenuBTree(){ /*显示二叉排序树子菜单函数 */printf("\n 二叉排序树 ");printf("\n==================================================");printf("\n| 1 建立二叉排序树 |");printf("\n| 2 插入一个元素 |");printf("\n| 3 删除一个元素 |");printf("\n| 4 查找一个元素 |");

printf("\n|返回|");printf("\n|返回|");printf("\n==================================================");printf("\n请输入序号( 0-4)选择要进行的操作 :");}voidBTFun(){/*二叉排序树子函数 */KeyTypestr[100];BTNode*bt;inti,n,x,menux;MenuBTree();scanf("%d",&menux);do{TOC\o"1-5"\h\zswitch(menux) /*判断进行何种操作 */{/*建立二叉排序树 */printf("请输入要生成二叉排序树的关键字的个数 :");scanf("%d",&n);printf("请输入二叉排序树的各个关键字 :");for(i=0;i<n;i++)scanf("%d",&str[i]);bt=CreateBST(str,n);printf("建立的二叉排序树广义表表示法为 :");DispBStree(bt);break;/*在二叉排序树中插入一个元素 */printf("请输入要插入的元素值 :");scanf("%d",&x);bt=BSTInsert(bt,x);printf("插入后的二叉排序树为 :");DispBStree(bt);break;/*在二叉排序树中删除一个元素 */printf("请输入要删除的元素 :");scanf("%d",&x);bt=BSTDelete(bt,x);printf("删除元素％d后的二叉排序树为：”,x);DispBStree(bt);break;case4： /*在二叉排序树中查找某元素 */printf("请输入查找的元素值 ：");scanf("%d",&x);if((BSTSearch(bt,x))!=NULL)printf("在二叉排序树中存在元素 %d!",x);elseprintf("在二叉排序树中不存在元素 %d!",x);break;case0:return;break;default:printf("输入选项错误，请重新输入(0-4)!");}MenuBTree();scanf("%d",&menux);}while(1);}voidMenu(){ /*显示菜单子函数*/printf("\n 查找子系统");printf("\n==================================================");printf("\n|1—一顺序查找|");printf("\n|2—一折半查找|");printf("\n|3一分块查找|");printf("\n|4—一二叉树排序树查找|");printf("\n|0一返回|");printf("\n==================================================");printf("\n请输入菜单号(0-4):");}voidsearch(){SearchLr[MAXSIZE];IdxTypeidx[MAXSIZE];inti,m,n,x,k,address;charch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){Menu();scanf("%c",&ch2);getchar();switch(ch2){

case'1':printf("请输入表的元素个数 (0-%d):",MAXSIZE-1);scanf("%d",&n);printf("请输入％dj表中的关键字(整数):",n);for(i=1;i<=n;i++)scanf("%d",&r[i].key);printf("请输入要查找的关键字 :");scanf("%d",&x);if((address=SeqSearch(r,n,x))!=0)printf("