数据结构实验指导书

数据结构实验指导书太原理工大学2011年3月-PAGE19-实验一线性表一、目的与要求熟悉线性表的基本操作在顺序存储和链式存储结构上的实现，基本操作在实际问题中的应用。仔细分析并调试运行下面给出的程序。二、实验内容某省福利彩票的单注号码由1～35中的任意7个数组成，中奖号码由7个基本号码和1个特别号码组成。用计算机模拟摇奖过程随机产生8个号码，前7个号码为基本号码，最后1个号码为特别号码。分析：参考电视中的摇奖过程，使用线性表sq1存储35个号码，sq2存储抽奖结果。线性表sq2中，前7个元素是基本号码，第8个元素是特别号码。使用函数randomize()初始化随机发生器，使用random(n)产生范围在0～n-1之间的随机数，模拟抽奖过程的随机性。抽奖过程是：用random()产生一个随机数k，将线性表sq1中的第k个元素删除，插入线性表sq2的最后。如此重复8次，产生8个号码。最后输出抽奖结果。如：在线性表sq2中保存的抽奖号码依次是：2613521227316则输出结果是：2613052102270316C语言源程序如下：#defineN35#defineM8#defineSUCCESS1#defineFAILED-1#defineINIT_SIZE50#defineADDNODE10#include<stdlib.h>typedefintELEMENT;/*定义元素类型*/typedefstructslist_st/*定义顺序表类型*/{ELEMENT*element;intsize;intlength;}SLIST;intInitSList(SLIST*list);/*函数声明*/intGetSListLength(SLIST*list);intInsertElement(SLIST*list,intposition,ELEMENTelem);intDeleteElement(SLIST*list,intposition,ELEMENT*elem);intPrintSList(SLIST*list);main()/*主函数*/{inti,j,k;ELEMENTtmpelem;SLISTsq1,sq2;/*定义顺序表*/InitSList(&sq1);/*初始化顺序表sq1*/InitSList(&sq2);/*初始化顺序表sq1*/for(i=1;i<=N;i++)/*将N()=35个号码存储在顺序表sq1中*/InsertElement(&sq1,i,i);randomize();for(i=1;i<=M;i++){j=GetSListLength(&sq1);/*求顺序表的长度*/k=random(j)+1;/*产生一个随机数*/DeleteElement(&sq1,k,&tmpelem);/*删除顺序表sq1的第k个元素*/InsertElement(&sq2,i,tmpelem);/*插入到顺序表sq2的最后*/}PrintSList(&sq2);/*输出抽奖结果*/}intInitSList(SLIST*list)/*初始化顺序表*/{if((list->element=(ELEMENT*)malloc(INIT_SIZE*sizeof(ELEMENT)))==NULL)returnFAILED;else{list->size=INIT_SIZE;list->length=0;returnSUCCESS;}}intGetSListLength(SLIST*list)/*求表长*/{if(list!=NULL)returnlist->length;elsereturnFAILED;}intInsertElement(SLIST*list,intposition,ELEMENTelem)/*插入*/{inti;ELEMENT*tmplist;if(position<1||position>list->length+1)returnFAILED;if(list->length==list->size){tmplist=(ELEMENT*)realloc(list->element,(list->size+ADDNODE)*sizeof(ELEMENT));if(tmplist==NULL)returnFAILED;list->element=tmplist;list->size+=ADDNODE;}for(i=list->length-1;i>=position-1;i--)list->element[i+1]=list->element[i];list->element[position-1]=elem;list->length++;returnSUCCESS;}intDeleteElement(SLIST*list,intposition,ELEMENT*elem)/*删除*/{inti;if(position<1||position>list->length)returnFAILED;*elem=list->element[position-1];for(i=position;i<list->length;i++)list->element[i-1]=list->element[i];list->length--;returnSUCCESS;}intPrintSList(SLIST*list)/*输出顺序表中的元素*/{inti;if(list==NULL)returnFAILED;printf("\n");for(i=0;i<list->length;i++)printf("%02d",list->element[i]);printf("\n");}三、思考题1．设有n个人围坐在一个圆桌周围，现从第s个人从1开始报数，数到第m的人离开圆桌，然后从下一个人重新开始报数，数到m的人又离开圆桌，如此重复，直到所有的人离开圆桌。对任意给定的n,s,m，求n个人离开圆桌的次序。提示：用循环链表存储n个人的信息（可以是姓名，也可以是编号），从链表的首结点开始计数，到s时，删除该结点，插入到出列链表的(第二个链表)最后，接着删除结点的下一个结点重新计数，直到该链表为空。第二个链表的结点数据就是离开圆桌的次序。2．多项式相加。用单链表ha存储多项式A(x)=a0+a1x1+a2x2+…+anxn(其中ai是非0系数)，用单链表hb存储多项式B(x)=b0+b1x1+b2x2+…+bmxm(其中bj是非0系数)，要求计算C(x)=A(x)+B(x)，结果存储在单链表hc中。设：A(x)=9+7x1-5x2+3x3+x5B(x)=10+8x1-6x3+4x4+2x5

实验二栈和队列一、目的与要求通过栈应用的一个典型实例——迷宫求解，熟悉栈的操作特点和栈的使用方法。仔细分析并调试运行下面给出的程序。二、实验内容所谓迷宫求解就是要在迷宫中寻找一条从入口到出口的路径。采用试探法——从入口出发，沿着某一方向向前搜索，如果有路就继续前进，否则沿原路退回一步，重新选择新的方向，在继续搜索。如此重复，直到到达出口或退回到入口(表明迷宫中无路径)。为了保证在搜索路径过程中能沿原路回退，需用一个后进先出的数据结构——栈，保存搜索过程中走过的路径。000000000000000000000000000001101101000010100100001111110000100100000010111100001110011000000000000000000000在迷宫中，搜索从入口到出口路径的算法思想是这样的：从迷宫的入口出发，先将迷宫的入口位置入栈。取栈顶位置作为当前位置，如果当前位置就是出口位置，那么至此已经找到一条路径，算法结束。如果当前位置还未被搜索过，则在当前位置上置路径标志(ROAD_ID)，表示已经位于搜索路径上，并将其入栈。接着查看其它相邻的位置(上下左右4个相邻位置)，将所有的候选通路(具有PATH_ID标志的位置)依次入栈，如此重复，直到找到出口。如果当前位置为死路(上下左右4个相邻位置要么都已搜索，要么都是墙)，则表明当前位置必不在路径上，需回退。如果栈中的前一位置尚未被搜索过，则从此位置开始搜索其它路径。如果栈中的前一位置已经搜索过，则说明该位置也是死路，需继续回退。如果最后栈为空，则说明迷宫中没有从入口到达出口的路径。C语言源程序如下：#defineSUCCESS1#defineFAILED-1#defineTRUE1#defineFALSE0#defineROW_NUM8+2#defineCOL_NUM8+2#defineSTACK_SIZE50typedefstructposition_st{intx;inty;}POSITION;typedefstructstack_st{POSITIONdata[STACK_SIZE];inttop;}STACK;STACKmystack;#defineWALL_ID0#definePATH_ID1#defineROAD_ID2#defineDEAD_ID3intSearchMazePath(intmaze[][COL_NUM],POSITION*start,POSITION*end);voidInitStack(STACK*stack);intPushStack(STACK*stack,POSITION*elem);intPopStack(STACK*stack,POSITION*elem);intIsStackEmpty(STACK*stack);main(){inti,j;intmaze[ROW_NUM][COL_NUM]={{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,1,1,0,1,1,0,1,0,0},{0,0,1,0,1,0,0,1,0,0},{0,0,1,1,1,1,1,1,0,0},{0,0,1,0,0,1,0,0,0,0},{0,0,1,0,1,1,1,1,0,0},{0,0,1,1,1,0,0,1,1,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0}};POSITIONstart={2,1},end={7,8},pos;SearchMazePath(maze,&start,&end);for(i=0;i<ROW_NUM;i++){for(j=0;j<COL_NUM;j++)printf("%d",maze[i][j]);printf("\n");}printf("\n");}intSearchMazePath(intmaze[][COL_NUM],POSITION*start,POSITION*end){POSITIONposition,tmppos;InitStack(&mystack);PushStack(&mystack,start);while(IsStackEmpty(&mystack)!=TRUE){PopStack(&mystack,&position);if(maze[position.x][position.y]==WALL_ID){maze[position.x][position.y]=DEAD_ID;continue;}elseif(maze[position.x][position.y]==PATH_ID){PushStack(&mystack,&position);maze[position.x][position.y]=ROAD_ID;}if(position.x==end->x&&position.y==end->y)returnSUCCESS;if(maze[position.x+1][position.y]!=PATH_ID&&maze[position.x][position.y+1]!=PATH_ID&&maze[position.x-1][position.y]!=PATH_ID&&maze[position.x][position.y-1]!=PATH_ID)maze[position.x][position.y]=DEAD_ID;else{if(maze[position.x][position.y-1]==PATH_ID){tmppos.x=position.x;tmppos.y=position.y-1;PushStack(&mystack,&tmppos);}if(maze[position.x-1][position.y]==PATH_ID){tmppos.x=position.x-1;tmppos.y=position.y;PushStack(&mystack,&tmppos);}if(maze[position.x][position.y+1]==PATH_ID){tmppos.x=position.x;tmppos.y=position.y+1;PushStack(&mystack,&tmppos);}if(maze[position.x+1][position.y]==PATH_ID){tmppos.x=position.x+1;tmppos.y=position.y;PushStack(&mystack,&tmppos);}}}}voidInitStack(STACK*stack){stack->top=-1;}intPushStack(STACK*stack,POSITION*elem){if(stack->top>=STACK_SIZE)returnFAILED;stack->top++;stack->data[stack->top].x=elem->x;stack->data[stack->top].y=elem->y;returnSUCCESS;}intPopStack(STACK*stack,POSITION*elem){if(stack->top<0)returnFAILED;elem->x=stack->data[stack->top].x;elem->y=stack->data[stack->top].y;stack->top--;returnSUCCESS;}intIsStackEmpty(STACK*stack){if(stack->top<0)returnTRUE;elsereturnFALSE;}三、思考题1．请列举日常生活中栈的应用。2．请列举日常生活中队列的应用。

实验三树一、目的与要求熟悉树和二叉树的表示方法和遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。仔细分析并调试运行下面给出的程序。二、实验内容1．任意给定一棵二叉树。试设计一个程序，建立二叉树并对其进行遍历。假设有如下的二叉树：二叉树的结点若无子树，则将其子树看作“.”，按照前序序列的顺序输入二叉树的结点内容。对上图所示的二叉树，其输入序列为：ABD..EH...CF.I..G..对建立的二叉树进行后序遍历，若为空二叉树，则输出：Thisisaemptybinarytree。若二叉树不空，则输出遍历序列。对上图所示的二叉树，输出结果为：DHEBIFGCA二叉树采用二叉链表存储。采用递归方法建立和遍历二叉树。二叉树的建立过程是：首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。C语言源程序如下：#include<stdio.h>typedefstructnode{chardata;structnode*left,*right;}NODE;/*建立二叉树*/voidcreatbit(NODE**tree){charx;x=getchar();if(x!='.'){(*tree)=(NODE*)malloc(sizeof(NODE));(*tree)->data=x;creatbit(&((*tree)->left));creatbit(&((*tree)->right));}else(*tree)=NULL;}/*后根遍历二叉树*/voidPostOrderTraverse(NODE*t){if(t!=NULL){PostOrderTraverse(t->left);PostOrderTraverse(t->right);printf("%c",t->data);}}main(){NODE*tree;printf("Pleaseinputtree:");creatbit(&tree);printf("\n");if(tree==NULL)printf("Thisisaemptybinarytree.\n");PostOrderTraverse(tree);printf("\n");}2．假设通讯中电文由a,b,c,d,e,f,g,h等8个字符组成，其出现的频率分别为：12，23，9，2，27，6，15，5。请设计程序，给出这8个字符的赫夫曼编码。分析：m个权值的赫夫曼树由2m-1个结点，采用数组存储赫夫曼树中的结点，树中的每个结点结构为：wparentleftright其中：w为结点的权，parent是结点的双亲在数组中的下标，left和right分别是结点的左右孩子在结点数组中的下标。另外，与每个叶子结点对应字符的编码被存放在一个字符数组中，因为编码是不等长的，即每个编码所占用的空间不等，应此存储编码串的空间需动态分配。C语言源程序如下：#defineSUCCESS1#defineFAILED-1#defineCODE_NUM8#defineMAX_WEIGHT32767#include<stdio.h>#include<string.h>typedefstructnode_st{/*定义树结点类型*/intw;intparent,left,right;}NODE;typedefstructchar_code_st{/*定义字符、编码类型*/charch;intweight;char*huffmancode;}HCODE;char*tmpcode;intCreatHuffmanCode(HCODE*node,intnodenum);intGetTwoNode(NODE*huffmantree,intn,int*s1,int*s2);main(){inti,nodenum;/*字符个数*/HCODEnode[CODE_NUM]={{'a',12},{'b',23},{'c',9},{'d',2},{'e',27},{'f',6},{'g',15},{'h',5}};nodenum=CODE_NUM;CreatHuffmanCode(node,nodenum);/*求赫夫曼编码*/for(i=0;i<nodenum;i++)/*输出字符及其编码*/printf("%c%s\n",node[i].ch,node[i].huffmancode);}/*定义求赫夫曼编码函数*/intCreatHuffmanCode(HCODE*node,intnodenum){inti,m,s1,s2;intcurrent,preid,tmpid;NODE*huffmantree;if(nodenum<1)returnFAILED;/*字符数不对,返回失败标志*/if(nodenum==1)returnSUCCESS;/*只有一个字符，无需编码*/m=2*nodenum-1;/*赫夫曼树的结点数*/huffmantree=(NODE*)malloc(m*sizeof(NODE));for(i=0;i<nodenum;i++){/*初始化叶子结点*/huffmantree[i].w=node[i].weight;huffmantree[i].parent=0;huffmantree[i].left=0;huffmantree[i].right=0;}for(i=nodenum;i<m;i++){/*初始化非叶子结点*/huffmantree[i].w=0;huffmantree[i].parent=0;huffmantree[i].left=0;huffmantree[i].right=0;}for(i=nodenum;i<m;i++){/*构造赫夫曼树*/GetTwoNode(huffmantree,i,&s1,&s2);huffmantree[s1].parent=i;huffmantree[s2].parent=i;huffmantree[i].left=s1;huffmantree[i].right=s2;huffmantree[i].w=huffmantree[s1].w+huffmantree[s2].w;}tmpcode=(char*)malloc(nodenum*sizeof(char));tmpcode[nodenum-1]='\0';for(i=0;i<nodenum;i++){/*求赫夫曼编码*/current=nodenum-1;/*存放当前编码的位置*/for(preid=i,tmpid=huffmantree[i].parent;tmpid!=0;preid=tmpid,tmpid=huffmantree[tmpid].parent)if(huffmantree[tmpid].left==preid)tmpcode[--current]='0';elsetmpcode[--current]='1';node[i].huffmancode=(char*)malloc((nodenum-current)*sizeof(char));strcpy(node[i].huffmancode,&tmpcode[current]);}returnSUCCESS;}/*找权值最小的两棵子树*/intGetTwoNode(NODE*huffmantree,intn,int*t1,int*t2){inttmp1,tmp2,i;tmp1=tmp2=MAX_WEIGHT;*t1=*t2=0;for(i=0;i<n;i++)if(huffmantree[i].parent==0)if(huffmantree[i].w<tmp1){*t2=*t1;tmp2=tmp1;*t1=i;tmp1=huffmantree[i].w;}elseif(huffmantree[i].w<tmp2){*t2=i;tmp2=huffmantree[i].w;}}

实验四查找一、目的与要求熟悉查找的概念和查找方法，设计相关的查找程序。本实验给出了顺序查找、二分查找和二叉排序查找的程序，请仔细阅读并调试运行。二、实验内容随机产生20个整数，组成一个顺序表（或有序表，或二叉排序树）。从键盘输入一个整数x，进行顺序查找、二分法查找和二叉排序树查找。C语言源程序如下：#include<stdlib.h>#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineMAXSIZE20#defineSUCCESS1#defineFAILED-1typedefintKeyType;typedefstruct{KeyTypekey;}RcdType;/*元素类型*/typedefstruct{RcdTyper[MAXSIZE+1];intlength;}SqList;/*顺序表类型*/typedefstructnode_st{RcdTypedata;structnode_st*left,*right;}NODE;/*二叉排序树结点类型*/intSearch(SqList*L,KeyTypekey);intBinarySearch(SqList*L,KeyTypekey);voidInitList(SqList*L);voidWriteList(SqList*L);voidInsertSort(SqList*L);NODE*FindNode(NODE*tree,KeyTypekey);NODE*FindNodeWithInsert(NODE**tree,KeyTypekey);voidCreatBinarySortTree(NODE**tree,SqList*L);main(){inti,x;SqListL;NODE*tree,*found;InitList(&L);CreatBinarySortTree(&tree,&L);printf("\n数据序列:\n");WriteList(&L);printf("输入一个整数：");scanf("%d",&x);i=Search(&L,x);printf("顺序查找结果：");if(i==FAILED)printf("查找的数%d不存在!\n",x);elseprintf("查找的数%d是第%d个数!\n",x,i);printf("\n\n有序表序列:\n");InsertSort(&L);WriteList(&L);printf("输入一个整数：");scanf("%d",&x);i=BinarySearch(&L,x);printf("二分查找结果：");if(i==FAILED)printf("查找的数%d不存在!\n",x);elseprintf("查找的数%d是第%d个数!\n",x,i);found=FindNode(tree,x);printf("\n二叉排序树查找结果：");if(found==NULL)printf("查找的数%d不存在!\n",x);elseprintf("查找的数%d存在，其地址是%x\n",x,found);getch();}intSearch(SqList*L,KeyTypekey)/*顺序查找*/{inti;for(i=1;i<=L->length;i++)if(L->r[i].key==key)returni;returnFAILED;}intBinarySearch(SqList*L,KeyTypekey)/*二分查找*/{intlow,high,mid;low=1;high=L->length;while(low<=high){mid=(low+high)/2;if(L->r[mid].key==key)returnmid;if(L->r[mid].key<key)low=mid+1;elsehigh=mid-1;}returnFAILED;}NODE*FindNode(NODE*tree,KeyTypekey){NODE*tmp=tree;while(tmp!=NULL){if(tmp->data.key==key)returntmp;if(tmp->data.key>key)tmp=tmp->left;elsetmp=tmp->right;}returnNULL;}NODE*FindNodeWithInsert(NODE**tree,KeyTypekey)/*二叉排序树查找并插入*/{NODE*tmp,*pre;tmp=pre=*tree;while(tmp!=NULL){if(tmp->data.key==key)returntmp;pre=tmp;if(tmp->data.key>key)tmp=tmp->left;elsetmp=tmp->right;}tmp=(NODE*)malloc(sizeof(NODE));tmp->data.key=key;tmp->left=tmp->right=NULL;if(*tree==NULL)*tree=tmp;elseif(pre->data.key>key)pre->left=tmp;elsepre->right=tmp;returnNULL;}voidCreatBinarySortTree(NODE**tree,SqList*L)/*建立二叉排序树*/{inti;*tree=NULL;for(i=1;i<=L->length;i++)FindNodeWithInsert(tree,L->r[i].key);}voidInitList(SqList*L)/*初始化*L*/{inti;randomize();for(i=1;i<=MAXSIZE;++i)L->r[i].key=(KeyType)random(100);L->length=MAXSIZE;}voidWriteList(SqList*L)/*输出顺序表*L*/{inti;for(i=1;i<=L->length;++i)printf("%3d",L->r[i].key);printf("\n");}voidInsertSort(SqList*L)/*直接插入排序*/{inti,j;for(i=2;i<=(*L).length;++i)if(LT((*L).r[i].key,(*L).r[i-1].key)){(*L).r[0]=(*L).r[i];for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)(*L).r[j+1]=(*L).r[j];(*L).r[j+1]=(*L).r[0];}}三、思考题1．分析二分查找的查找过程。2．画出程序运行时20个随机数组成的二叉排序树。3．设计算法，对本实验中的二叉排序树进行中序遍历。

实验五排序一、目的与要求熟悉排序的概念和常用排序方法，设计相关的排序程序。本实验给出了直接插入排序、希尔排序、快速排序、堆排序、归并排序程序，请仔细阅读并调试运行。二、实验内容随机产生20个整数，组成一个顺序表，对其进行直接插入排序、希尔排序、快速排序、堆排序、归并排序。C语言源程序如下：#include<stdlib.h>#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineMAXINT32767#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;}RcdType;/*定义记录类型*/typedefstruct{RcdTyper[MAXSIZE+1];intlength;}SqList;/*定义顺序表类型*/voidInitList(SqList*L)/*初始化顺序表*L*/{inti;randomize();for(i=1;i<=MAXSIZE;++i)L->r[i].key=(KeyType)random(100);L->length=MAXSIZE;}voidWriteList(SqList*L)/*输出顺序表*L*/{inti;for(i=1;i<=L->length;++i)printf("%3d",L->r[i].key);printf("\n");}voidInsertSort(SqList*L)/*直接插入排序*/{inti,j;for(i=2;i<=(*L).length;++i)if(LT((*L).r[i].key,(*L).r[i-1].key)){(*L).r[0]=(*L).r[i];for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j) (*L).r[j+1]=(*L).r[j];(*L).r[j+1]=(*L).r[0];}}voidShellInsert(SqList*L,intdk)/*希尔排序*/{/*对顺序表*L作一趟希尔排序*/inti,j;for(i=dk+1;i<=(*L).length;++i)if(LT((*L).r[i].key,(*L).r[i-dk].key)){(*L).r[0]=(*L).r[i];for(j=i-dk;j>0&<((*L).r[0].key,(*L).r[j].key);j-=dk) (*L).r[j+dk]=(*L).r[j];(*L).r[j+dk]=(*L).r[0];}}voidShellSort(SqList*L,intdlta[],intt){/*按增量序列dlta[0..t-1]对*L作希尔排序*/intk;for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}intPartition(SqList*L,intlow,inthigh)/*快速排序*/{/*对*L[low..high]作一趟快速排序,返回枢轴位置*/KeyTypepivotkey;L->r[0]=L->r[low];pivotkey=L->r[low].key;while(low<high){while(low<high&&LQ(pivotkey,L->r[high].key))--high;L->r[low]=L->r[high];while(low<high&&LQ(L->r[low].key,pivotkey))++low;L->r[high]=L->r[low];}L->r[low]=L->r[0];returnlow;}voidQSort(SqList*L,intlow,inthigh){/*对*L[low..high]快速排序*/intpivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}voidQuickSort(SqList*L){/*对*L作快速排序*/QSort(L,1,L->length);}void