数据结构相关实验资

C语言与算法设计技能培训1、用c语言实现下列各种排序：冒泡排序、选择排序、快速排序冒泡排序函数如下:/*n表示待排序的数据的个数*/#definen10voidmaopao(inta[])(inti,j,temp;for(i=0;i<n-1;++i)(for(j=0;j<n-i;++j)if(a[j]>a[j+1])(temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}/*选择排序*/voidxuanze(inta[n])(inti,j,temp,k;for(i=0;i<n-1;++i)(k=i;for(j=i+1;j<n;++j)if(a[k]<a[j])k=j;if(k!=i)(temp=a[i];a[i]=a[k];a[k]=temp;}}}/*快速排序*/intpart(inta[n],intlow,inthigh)(intx;x=a[low];while(low<high)(while(low<high&&a[high]>=x)--high;a[low]=a[high];while(lowvhigh&&a[low]v=x)++low;a[high]=a[low];}a[low]=x;returnlow;}voidQsort(inta[n],intlow,inthigh)(intpivotloc;if(low<high)(pivotloc=part(a,low,high);Qsort(a,low,pivotloc-1);Qsort(a,pivotloc+1,high);}}main(){inta[n],j;for(j=0;j<n;++j)scanf("%d",&a[j]);maopao(a);for(j=0;j<n;++j)printf("%5d”,a[j]);printf("\n");for(j=0;j<n;++j)scanf("%d”,&a[j]);xuanze(a);for(j=0;j<n;++j)printf(”％5d”,a[j]);printf(”\n”)；for(j=0;j<n;++j)scanf("%d”,&a[j]);Qsort(a,0,n-1);for(j=0;j<n;++j)printf(”％5d”,a[j]);printf(”\n”)；getch();}2、用C语言实现下列各种操作单链表的建立在第i个结点之前插入一个结点删除第i个结点#defineNULL0typedefstructnode{intdata;structnode*next;}node,*link;/*单链表建立voidcrealink(link*L,intn){linkp,q;inti;*L=(link)malloc(sizeof(node));q=*L;q->next=NULL;for(i=1;i<=n;++i){p=(link)malloc(sizeof(node));printf("inputp->data=");scanf("%d”,&p->data);p->next=NULL;q->next=p;q=p;}}/*单链表的输出*/voidprint(linkL){linkp;p=L->next;while(p){printf("%5d”,p->data);p=p->next;}printf("\n");}/*在单链表的第I个位置上插入元素值为e的函数*/voidinsert(link*L,inti,inte){linkp,s;intj=0;p=*L;/*找被插入位置，p指向i-1位置*/while(p&&j<i-1){p=p->next;++j;}if(!pllj>i)printf("error");else{/*申请结点*/s=(link)malloc(sizeof(node));s->data=e;/*插入*/s->next=p->next;p->next=s;}}/*删除单链表的第I个位置上的元素值*/voiddelink(link*L,inti){linkp,s;intj=0;p=*L;/*查找被删位置，p指向i-1位置*/while(p&&j<i-1){p=p->next;++j;}if(!pllj>i)printf("error");else(s=p->next;/S指向被删结点*/p->next=s->next;free(s);}}main(){linkL;intn,i,e;/*链表结点的个数*/printf("inputlinkn=");scanf("%d”,&n);crealink(&L,n);print(L);/*i表示被插位置*/printf("inputi=");scanf("%d”,&i);/*i表示被插值*/printf("inpute=");scanf("%d”,&e);insert(&L,i,e);print(L);/*i表示被删位置*/printf("inputi");scanf("%d”,&i);delink(&L,i);print(L);getch();}3、用C语言实现下列各种操作二叉树的建立用递归法用递归方法对二叉树进行全序、中序、后序遍历及用非递归方法对树进行层次遍历#defineNULL0/*定义二叉树中的结点*/typedefstructnode{chardata;structnode*lch,*rch;}node,*link;/*用先序遍历的思想建立二叉树*/voidcreat(link*t){charch;scanf("%c”,&ch);if(ch=='0')*t=null;else{*t=(link)malloc(sizeof(node));(*t)->data=ch;creat(&(*t)->lch);creat(&(*t)->rch);}}/*先序遍历函数*/voidpreorder(linkt){if(t!=null){printf("%c”,t->data);/*访问根结点*/inorder(t->lch);/*先序遍历左子树*/inorder(t->rch);/*先序遍历右子树*/}}/*中序遍历函数*/voidinorder(linkt){if(t!=null){inorder(t->lch);/*中序遍历左子树*/printf("%c”,t->data);/*访问根结点*/inorder(t->rch);/*中序遍历右子树*/}}/*后序遍历函数*/voidpostorder(linkt){if(t!=null){postorder(t->lch);/*后序遍历左子树*/postorder(t->rch);/*访问根结点*/printf("%c”,t->data);/*后序遍历右子树*/}}/*二叉树的层次遍历*/voidlever(linkt){linkp;/*定义空队列*/bitreeQ[100];intfront=0,rear=0;/*初始化队列为空队列*/Q[rear++]=t;/*当队列为非空时*/while(front!=rear){p=Q[front++];/*对头元素出队列*/printf("%5d”,p->data);/*对头元素左孩子不空，将左孩子入队列*/if(p->lch!=NULL)Q[rear++]=p->lch;/*对头元素左孩子不空，将左孩子入队列*/if(p->rch!=NULL)Q[rear++]=p->rch;}}main(){linkt;creat(&t);prorder(t);printf("\n");inorder(t);printf("\n");postorder(t);printf("\n");lever(t);printf("\n");getch();}4、用C语言实现下列各种操作1）用邻接表法建立有向图的邻接表2）用深度优先和广度优先法来遍历该有向图#defineNULL0/*定义访问数组*/intvisited[100];/*邻接点及顶点的定义*/typedefstructnode{intadjvex;structnode*next;}node;/*顶点的定义*/typedefstruct(intvex;node*firstadj;}vertex;/*邻接表的定义*/typedefstruct(vertexdata[100];intm;/*m表示图中顶点的个数*/}adjlist;/*voidcreategraph(adjlist*g)功能：建立有向图的邻接表，图中的边由键盘给出。voiddfs(adjlistg)功能：完成有向连通图的深度优先遍历。voidbfs(adjlistg)功能：完成有向连通图的广度优先遍历。有向图的邻接表的建立程序*/voidcreategraph(adjlist*g)(intn,e;/*n表示图中的顶点个数,e表示边的条数*/intj,i,k;node*p,*q;/*由键盘输入图的顶点个数及边的条数*/printf("inputn=");scanf("%d”,&n);printf("inpute=");scanf("%d”,&e);/*初始化邻接表*/g->m=n;for(j=0;j<=n-1;++j)(g->data[j].firstadj=NULL;g->data[j].vex=j;for(j=0;j<e;++j){/*由键盘输入一对边*/printf("inputi,k:");scanf("%d%d”,&i,&k);/*申请一个邻结点*/p=(node*)malloc(sizeof(node));p->adjvex=k;p->next=NULL;if(g->data[i].firstadj==NULL)g->data[i].firstadj=p;else{q=g->data[i].firstadj;while(q->next)q=q->next;q->next=p;}}}/*有向图的深度优先遍历*/voiddfs(adjlistg,intv){node*p;printf("%3d”,v);visited[v]=1;p=g.data[v].firstadj;while(p){if(visited[p->adjvex]==0)dfs(g,p->adjvex);p=p->next;}}/*有向图的广度优先遍历程序*/voidbfs(adjlistg,intv){/*定义空队列*/intQ[100];intfront=0,rear=0;node*p;visited[v]=1;printf("%3d”,v);Q[rear++]=v;while(front!=rear){v=Q[front++];p=g.data[v].firstadj;while(p){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%3d”,p->adjvex);Q[rear++]=p->adjvex;}p=p->next;}}}/*主函数如下：*/main(){adjlistg;inti;creategraph(&g);/*初始化访问数组*/for(i=0;i<g.m;++i)visited[i]=0;dfs(g,0);printf("\n");/*初始化访问数组*/for(i=0;i<g.m;++i)visited[i]=0;bfs(g,0);getch();5、迷宫程序#definem6#definen9voidpath(){/*定义迷宫并初始化迷宫*/intmaze[8][11]={1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,1,1,0,0,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1};intmove[9][2];/*定义栈*/ints[54][3];inttop=0;inti,j,k,p,f=0,g,h;/*初始化增量矩阵*/move[1][0]=-1;move[1][1]=0;move[2][0]=-1;move[2][1]=1;move[3][0]=0;move[3][1]=1;move[4][0]=1;move[4][1]=1;move[5][0]=1;move[5][1]=0;move[6][0]=1;move[6][1]=-1;move[7][0]=0;move[7][1]=-1;move[8][0]=-1;move[8][1]=-1;maze[1][1]=2;/*初始化栈非空*/s[top][0]=1;s[top][1]=1;s[top]⑵=3;++top;while(top!=0&&f==0){/*退栈*/--top;i=s[top][0];j=s[top][1];k=s[top][2];/*当方向数小于8时*/while(k<=8){/*试老鼠的下一位置*/g=i+move[k][0];h=j+move[k][1];if(g==m&&h==n&&maze[g][h]==0){for(p=0;p<top;++p){printf("%d,%d,%d\n”,s[p][0],s[p][1],s[p]⑵);}printf("%d,%d,%d\n”,i,j,k);printf("%d,%d,%d\n”,m,n,k);f=1;}if(maze[g][h]==0){maze[g][h]=2;/*下一位置可通，将上一位置入栈*/s[top][0]=i;s[top][1]=j;s[top][2]=k;++top;/*改变老鼠的当前位置*/i=g;j=h;k=0;}/*方向数增1*/k=k+1;}}if(f==0)printf("nopath\n");}main(){path();getch();}6、约瑟夫问题程序#defineNULL0typedefstructQNode{intdata;structQNode*next;}QNode,*linklist;/*建立循环链表*/voidcreate(linklist*L,intn)(inti;linklistp,q;*L=(QNode*)malloc(sizeof(QNode));(*L)->next=NULL;q=*L;for(i=1;i<=n;++i)(p=(QNode*)malloc(sizeof(QNode));p->data=i;q->next=p;q=p;}q->next=(*L)->next;*L=(*L)->next;}/*输出循环链表*/voidprint(linklistL)(linklistp;p=L;while(p->next!=L)(printf("%5d",p->data);p=p->next;}printf("%5d”,p->data);printf("\n");}/*报数到第m号出圈*/voidjone(linklistL,intm)(linklistp,q;inti,j;p=L;/*将指针定位到k-1号位*/for(i=1;i<k;++i)p=p->next;/*从第k号位置开始报数，k报1号，k+1报2号，依次类推，将指针指向最后一个报数的人*/while(p->next!=p)(jT;while(p->next!=p&&j<m-1)(p=p->next;++j;}q=p->next;printf("%5d”,q->data);/*删除第m号*/p->next=q->next;p=p->next;free(q);}printf("\nzuihouyigeshi:%5d",p->data);}main()(linklistL;create(&L,100);print(L);jone(L,10);getch();}7、Kruskal算法的设计［实验目的］根据算法设计需要，掌握连通网的灵活表示方法；2.掌握最小生成树的Kruskal算法；基本掌握贪心算法的一般设计方法；进一步掌握集合的表示与操作算法的应用.［预习要求］认真阅读算法设计教材和数据结构教材内容，熟习连通网的不同表示方法和最小生成树算法；2.设计Kruskal算法实验程序.［参考数据类型或变量］typedefNodeNumberint;/*节点编号*/typedefCostTypeint;/*成本值类型*/typedefElemTypeNodeNumber/*实型或任意其它元素类型*/typedefstruct(intElemType;inttag;}NODE;typedefstruct(CostTypecost;NodeNumbernodel,node2;}EDGE;NODEset［］=({1,-1},...,(n,-1}};/*节点集，n为连通网的节点数*/EDGEes［］=((valuesofej,...」valuesofem}};/*边集，m为连通网的边数*/EDGEst［n-1］;/*最小生成树的边集*/［参考子程序接口与功能描述］intFind(NODE*set,ElemTypeelem)功能：在数组set中顺序查找元素elem,如果不成功，返回-1;否则，使用带压缩规则的查找算法，返回所在子集的根节点索引.intUnion(NODE*set,ElemTypeelem1,ElemTypeelem2)功能：应用Find算法首先找到elem1和elem2所在的子集，然后应用带加权规则的并运算算法合并两个子集.不成功时，返回-1;否则，返回并集的根节点索引.voidSort(EDGE*es,intn)功能：用任意分类算法将连通图的边集按成本值的非降次序分类.voidKruskal(EDGE*es,intm,NODE*set,intn,EDGE*st)功能：对有n个节点,m条边的连通网，应用Kruskal算法生成最小生成树，最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)功能：输出最小生成树的各条边.［实验步骤］设计测试问题，修改并调试程序，输出最小生成树的各条边，直至正确为止；待各功能子程序调试完毕，去掉测试程序，将你的程序整理成功能模块存盘备用.［实验报告要求］阐述实验目的和实验内容；阐述Kruskal算法的原理方法；提交实验程序的功能模块；提供测试数据和相应的最小生成树.［思考与练习］设计由连通网初始边集数组生成最小堆的算法；设计输出堆顶元素，并将剩余元素调整成最小堆的算法；