南阳理工学院_软件学院数据结构上机实验指导书全部答案.doc

《南阳理工学院_软件学院数据结构上机实验指导书全部答案.doc》由会员分享，可在线阅读，更多相关《南阳理工学院_软件学院数据结构上机实验指导书全部答案.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、南阳理工学院数据结构上机实验指导书（2011版） 答案（仅内供）软件学院软件工程教研室2011.3目 录实验1 线性表应用2实验2 栈和队列的应用14实验3 线性表应用27实验4 图论及其应用46实验5 查找59实验6 排序64实验1 线性表应用一、实验目的1. 了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。2. 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。二、实验内容及步骤 1. 利用程序设计语言分别实现顺序表和链表的抽象数据类型。2. 掌握程序分文件（头文件和实

2、现文件）书写的方式。3. 分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。l 顺序表的非递减数列合并实验2 栈和队列的应用一、实验目的1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法。3. 熟练掌握循环队列和链队列的基本操作实现算法。二、实验内容及步骤 1. 用程序设计语言实现栈和队列的抽象数据类型。2. 在第一题的基础上完成以下选择：选择一：1) 设计并实现括号匹配算法。2) 用队列实现在屏幕上打印杨辉三角。选择二：分别用栈和队列实现迷宫问题求解。选择三：分别用栈和队列实现一个列车调度系统

3、。l 括号匹配算法。#include#include#include#include string.h return 0;int PushStack(LinkStack top, DataType e)/*进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回1*/LStackNode *p;/*定义指向第i个元素的前驱结点指针pre，指针p指向新生成的结点*/if(p=(LStackNode*)malloc(sizeof(LStackNode)=NULL)printf(内存分配失败!);exit(-1);p-data=e;/*指针p指向头结点*/p-next=top-next;top

4、-next=p;return 1;int PopStack(LinkStack top,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/LStackNode *p; p=top-next; if(!p)/*判断链栈是否为空*/ printf(栈已空); q=p; p=p-next; free(q); int GetTop(LinkStack top,DataType *e)LStackNode *p; p=top-next; if(!p)/*判断链栈是否为空*/ printf(栈已空); return 0; *e=p-data;/*将出栈元素赋值给e*

5、/ return 1;void main() case :case :PushStack(S,*p+);break;case ):case :case :if(StackEmpty(S)elseGetTop(S,&e);printf(缺少右括号.n);int Match(DataType e,DataType ch)if(e=(&ch=)return 1;else if(e=&ch=)return 1;else if(e=&ch=)return 1;elsereturn 0;typedef struct QNodeDataType data;struct QNode* next;LQNode,

6、*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;void InitQueue(LinkQueue *LQ) /*将返回1，否则返回0*/ return 1; else return 0;int EnterQueue(LinkQueue *LQ,DataType e)/*将元素e插入到链式队列LQ中，插入成功返回1*/ LQNode *s;LQ-rear=s;/*将队尾指针指向p*/ return 1;/int DeleteQueue(LinkQueue *LQ,DataType *e)/*删除链式队列中的队头元素，并

7、将该元素赋值给e，删除成功返回1，否则返回0*/ LQNode空*/return 0;elses=LQ.front-next;/*将指针p指向队列的第一个元素即队头元素*/*e=s-data;/*将队头元素赋值给e，取出队头元素*/return 1;/*出队操作。*/int DeleteQueue(LinkQueue *Q,DataType *x) /* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */LQNode * p;if(Q-front=Q-rear)retu/*产生第中间n-2行的元素*/for(n=2;n=N;n+)/*产生第i行元素并入队，同时将第i-1行的元素保存在临时

8、数组中*/k=0;EnterQueue(&Q,1);/*第i行的第一个元素入队*/for(i=1;i=n-2;i+)/*利用队列中第i-1行元素产生第i行的中间i-2个元素并入队列*/DeleteQueue(&Q,&t);tempk+=t;/*将第i-1行的元素存入临时数组*/while(!QueueEmpty(Q)/*将最后一行元素存入临时数组*/DeleteQueue(&Q,&t);tempk+=t;if(QueueEmpty(Q)PrintArray(temp,k,N);void main()int n;printf(请输入要打印的行数：n=:);scanf(%d,&n);YangHui

9、Triangle(n);用栈实现迷宫问题求解#include #include #define OVERFLOW -1 #define MAX 100typedef struct int x; int y; int d; Data; typedef struct int pos; Data dataMAX; SNode,*Stack; Stack InitStack() Stack pStack; pStack=(Stack)malloc(sizeof(SNode); if(!pStack) if(pStack-pos=-1) exit(OVERFLOW); else pStack-pos-;

10、 Data GetTop(Stack pStack) revoid DisplayPath(Stack pStack) Data element; printf(The path is:n); while(!IsEmpty(pStack) element=GetTop(pStack); Pop(pStack); printf(The node is:(%d,%d)n,element.x,element.y); void MazePa int i,j,k,g,h; Stack pStack; Data element; pStack=InitStack(); mazex1y1=2; h=j+di

11、rectionk1; if(g=x2 & h=y2 & mazegh=0) Push(pStack,SetStackElem(i,j,k);Push(pStack,SetStackElem(x2,y2,k); DisplayPath(pStack); return; int i,j; printf(The maze is:n); for(i=0;i8;i+) for(j=0;j11;j+) printf(%2d,mazeij); printf(n);MazePath(maze,direction,1,1,6,9); 用队列实现迷宫问题求解#include#define r 64#define

12、m2 8#define n2 10int m=m2-2,n=n2-2;typedef structint x,y; /行列坐标int i,j,k,v,front,rear,x,y;int markm2n2;for(i=0;im2;i+)for(j=0;jn2;j+)marki j=0;printf(Please Input move arrayn);for(i=0;i8;i+)scanf(%d,%d,&movei .x,&movei .y);sq1.x=1;sq1.y=1;sq1.pre=0;front=1;rear=1;mark11=1; /标记入口以到达过while(front=rear)

13、x=sqfront.x;y=sqfront.y; /(x,y)为出发点for(v=0;v8;v+) /搜索(x,y)的8个相邻(i,j)是否可以到达for(i=1;i19;i+)printf(%3d,i);printf(n);for(i=1;i19;i+)printf(%3d,sqi .x);printf(n);for(i=1;i19;i+)printf(%3d,sqi .y);printf(n);for(i=1;i19;i+)printf(%3d,sqi .pre);printf(n);return(1); /成功返回front+; /出队，front 指向新的出发点 /队空，循环结束pri

14、ntf(There is no path! n);return(0); /迷宫没有路径返回main()int i,j;for(i=0;i10;i+)maze0i =1;maze7i =1;for(i=0;i8;i+)mazei 0=1;mazei 9=1;/*for(i=1;i7;i+)for(j=1;j9;j+)printf(%d %d,i,j);scanf(%d,&mazei j);*/maze11=0;maze12=1;maze13=0;maze14=1;maze15=1;mazprintf(n);for(i=0;i8;i+)for(j=0;j10;j+)printf(%d,mazei

15、j);printf(n);PATH(maze);分别用队列实现一个列车调度系统。实验3 树的应用一、实验目的1. 领会并理解二叉树的类型定义。2. 熟练掌握二叉树的主要特性，。3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4. 熟练掌握二叉树和树的各种存储结构及其建立的算法。5. 了递归算法的实现过程。二、实验内容及步骤 1. 实现二叉树的抽象数据类型。2. 构造一棵二叉树并用递归实现其先序、中序、后序遍历算法并验证。3. 用非递归算法实现二叉树的中序遍历。4. 给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。l 二叉树递归实现其先序、中序、后序遍历

16、算法并验证。#include#include#define MaxSize 50typedef int KeyType;typedef struct /*数据元素类型定义*/if(lowhigh)/*如果元素序列的长度大于1*/ pivot=Partition(L,low,high);/*将待排序序列L.rlow.high划分为两部分*/DispList2(*L,pivot,count);/*输出每次划分的结果*/count+;QSort(L,low,pivot-1);/*对左边的子表进行递归排序，pivot是枢轴位置*/QSort(L,pivot+1,high);/*对右边的子表进行递归排序

17、 */void QuickSort(SqList *L)/* 对顺序表L作快速排序*/ QSort(L,1,(*L).length);int i,n=10;SqList L;/*冒泡排序*/InitSeqList(&L,a,n);printf(冒泡排序前：);DispList(L);BubbleSort(&L,n);printf(冒泡排序结果：);DispList(L,n);/*快速排序*/InitSeqList(&L,a,n);printf(快速排序前：);DispList(L,n);QuickSort(&L,n);printf(快速排序结果：);DispList(L);void InitS

18、eqList(SqList *L,DataType a,int n)/*DataType t;/*将第i个元素的关键字与后面i+1.n个元素的关键字比较，将关键字最小的的元素放在第i个位置*/for(i=1;i=n-1;i+)j=i;for(k=i+1;kdatak.keydataj.key)j=k;if(j!=i)/*如果序号i不等于j，则需要将序号i和序号j的元素交换*/t=L-datai;L-datai=L-dataj;L-dataj=t;void CreateHeap(SqList *H,int n)/*建立大顶堆*/int i;for(i=n/2;i=1;i-)/*从序号n/2开始建

19、立大顶堆*/AdjustHeap(H,i,n);void AdjustHeap(SqList *H,int s,int m)/*调整H.datas.m的关键字，使其成为一个大顶堆*/ DataType t;int j;t=(*H).datas;/*将根结点暂时保存在t中*/for(j=2*s;j=m;j*=2) if(jm&(*H).dataj.keydatai=ai-1;L-length=n;void DispList(SqList L,int n)/*输出表中的元素*/int i;for(i=1;i=n;i+)printf(%4d,L.datai.key);printf(n);实验4 图论

20、及其应用一、实验目的1. 了解图的基本概念及术语,并能够熟练掌握图的两种存储结构(邻接矩阵和邻接表)。2. 理解最小生成树的概念，能按Prim算法构造最小生成树。3. 掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)、拓扑排序、关键路径、最短路径的算法思想。二、实验内容及步骤 1. 实现网（有权图）的存储结构。2. 利用prim算法构造它的最小生成树。3. 选择一个源点，寻找从原点出发到达其它顶点的最短路径。l 实现网（有权图）的存储结构。v 邻接矩阵存储结构#include/*包含输入输出头文件*/#define ListSize 100/*合并顺序表A和B的元素到C中，并保持元素非递

21、减排序*/int i,j,k;DataType e1,e2;i=1;j=1;k=1;while(i=A.length&j=B.length)GetElem(A,i,&e1);/*取出顺序表A中的元素*/GeInsertList(C,k,e2);/*将较小的一个插入到C中*/j+;/*往后移动一个位置，准备比较下一个元素*/k+;GetElem(A,i,&e1);InsertList(C,k,e1);/*将A中剩余元素插入到C中*/i+;k+;while(jlength=A.length+B.length;/*C的表长等于A和B的表长的和*/l 链式表的非递减数列合并/*包含头文件*/ Data

22、Type data; struct Node *next;ListNode,*LinkList;void MergeList(LinkList A,LinkList B,LinkList *C);/*将单链表A和B的元素合并到C中的函数声明*/void InitList(LinkList *head)/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/if(*head=(LinkList)malloc(sizeof(ListNode) return 0;ListNode *Get(LinkList head,int i) /*查找单链表中第i个结点。查找成功返回该结点的指

23、针表示成功；否则返回NULL表示失败。*/ListNode *p;int j;if(ListEmpty(head)/*在查找第i个元素之前，判断链表是否为空*/return NULL;if(inext;j+;if(j=i)return p;/*找到第i个结点，返回指针p*/elsereturn NULL;/*如果没有找到第i个元素，返回NULL*/ListNode *LocateElem(LinkList head,DataType e) /*查找线性表中元素值为e的元素，查找成功将对应元素的结点指针返回，否则返回NULL表示失败。*/L应元素的序号返回，否则返回0表示失败。*/ListNod

24、e *p;int i;if(ListEmpty(head)/*在查找第i个元素之前，判断链表是否为空*/return 0;p=head-next;/*指针p指向第一个结点*/i=1;while(p)if(p-data=e)/*找到与e相等的元素，返回该序号*/return i;elsep=p-next;i+;成功返回1，失败返回0*/ListNode *p,*pre;/*定义指向第i个元素的前驱结点指针pre，指针p指向新生成的结点*/int j;pre=head;/*指针p指向头结点*/j=0;while(pre-next!=NULL&jnext;j+;int DeleteList(Link

25、List head,int i,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ListNode *pre,*p;int j; pre=head; j=0; while(pre-next!=NULL&pre-next-next!=NULL&jnext; j+; pre-next=p-next; free(p);/*释放p指向的结点*/ return 1;int ListLength(LinkList head) ListNode *p; int count=0; p=head; while(p-next!=NULL) p=p-next; count+;

26、 return count;void DestroyList(LinkList head) ListNode *p,*q; p=head; while(p!=NULL)q=p; p=p-next; free(q); void main()for(i=1;i=sizeof(b)/sizeof(b0);i+)/*将数组b中元素插入单链表B中*/if(InsertList(B,i,bi-1)=0)printf(位置不合法);return;的元素合并到C中*/printf(将单链表A和B的元素合并到C中后，C中的元素有%d个：n,ListLength(C);for(i=1;idata);/*显示输出C

27、中所有元素*/printf(n);getch()中*/while(pa&pb)elsepc-next=pb;/*如果A中的元素大于B中的元素，将B中的元素的结点作为C的结点*/pc-next=pa?pa:pb;/*将剩余的结点插入C中*/free(B);/*释放B的头结点*/实验5 查找一、实验目的1. 理解查找表的结构特点以及各种表示方法的适用性。2. 熟练掌握顺序查找和折半查找，并对其性能做出分析。3. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。二、 实验内容及步骤 1. 实现查找表的顺序查找和折半查找算法。2. 试为下列关键字建立一个装载因子不小于0.75的哈

28、希表，并计算你所构造的哈希表的平均查找长度。（ZHAO, QIAN, SUN, LI, ZHOU, WU, CHEN, WANG, CHANG, CHAO, YANG, JIN）l 顺序查找算法及折半查找算法实验6 排序一、实验目的1. 了解内部排序的定义和基本方法2. 理解排序的基本思想和基本概念3. 掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析二、实验内容及步骤 1. 实现排序表的抽象数据类型，可以随机生成n(5000=n=50000)个待排序数据。2. 分别对每一个排序表多次运行插入排序、冒泡排序、快速排序、直接选择排序、

29、堆排序，计算其平均运行时间。3. 以横轴为数据规模，纵轴表示时间对实验结果进行描点并绘制每一个排序算法的时间轨迹。l 插入排序n 以横轴为数据规模，纵轴表示时间对实验结果进行描点并绘制每一个排序算法的时间轨迹#include/*包含输入输出头文件*/#define ListSize 100/*合并顺序表A和B的元素到C中，并保持元素非递减排序*/GetElem(A,i,&e1);/*取出顺序表A中的元素*/GeInsertList(C,k,e2);/*将较小的一个插入到C中*/j+;/*往后移动一个位置，准备比较下一个元素*/k+;GetElem(A,i,&e1);InsertList(C,k

30、,e1);/*将A中剩余元素插入到C中*/i+;k+;while(jlength=A.length+B.length;/*C的表长等于A和B的表长的和*/l 链式表的非递减数列合并/*包含头文件*/ DataType data; struct Node *next;ListNode,*LinkList;void MergeList(LinkList A,LinkList B,LinkList *C);/*将单链表A和B的元素合并到C中的函数声明*/void InitList(LinkList *head)/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/if(*head

31、=(LinkList)malloc(sizeof(ListNode) return 0;ListNode *Get(LinkList head,int i) /*查找单链表中第i个结点。查找成功返回该结点的指针表示成功；否则返回NULL表示失败。*/ListNode *p;int j;if(ListEmpty(head)/*在查找第i个元素之前，判断链表是否为空*/return NULL;if(inext;j+;if(j=i)return p;/*找到第i个结点，返回指针p*/elsereturn NULL;/*如果没有找到第i个元素，返回NULL*/ListNode *LocateElem(

32、LinkList head,DataType e) /*查找线性表中元素值为e的元素，查找成功将对应元素的结点指针返回，否则返回NULL表示失败。*/L应元素的序号返回，否则返回0表示失败。*/ListNode *p;int i;if(ListEmpty(head)/*在查找第i个元素之前，判断链表是否为空*/return 0;p=head-next;/*指针p指向第一个结点*/i=1;while(p)if(p-data=e)/*找到与e相等的元素，返回该序号*/return i;elsep=p-next;i+;成功返回1，失败返回0*/ListNode *p,*pre;/*定义指向第i个元素

33、的前驱结点指针pre，指针p指向新生成的结点*/int j;pre=head;/*指针p指向头结点*/j=0;while(pre-next!=NULL&jnext;j+;int DeleteList(LinkList head,int i,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ListNode *pre,*p;int j; pre=head; j=0; while(pre-next!=NULL&pre-next-next!=NULL&jnext; j+; pre-next=p-next; free(p);/*释放p指向的结点*/ return

34、 1;int ListLength(LinkList head) ListNode *p; int count=0; p=head; while(p-next!=NULL) p=p-next; count+; return count;void DestroyList(LinkList head) ListNode *p,*q; p=head; while(p!=NULL)q=p; p=p-next; free(q); void main()for(i=1;i=sizeof(b)/sizeof(b0);i+)/*将数组b中元素插入单链表B中*/if(InsertList(B,i,bi-1)=0)printf(位置不合法);return;的元素合并到C中*/printf(将单链表A和B的元素合并到C中后，C中的元素有%d个：n,ListLength(C);for(i=1;i=ListLength(C);i+)