自考《数据结构》实验指导.docx

计算机及应用专业数据结构实验指导书int j=0;listnode * p, *r;p=head;while (p&jnext; +j;if (!p-next | | jiT)return;r=p-next; p-next=r-next; free (r);void insertnode(linklist head, int x, int i) /在单链表中第i号位置处插入值为X的结点 (int j二0;listnode * p, *s;p=head;while(p&jnext; +j;if(!p|ji-l) exit (1);s=(linklist)malloc (sizeof (listnode); s-data=x;s-next=p-next; p-next=s;int _tmain(int argc, _TCHAR* argv)( linklist newlist=createlist;int i, x=20, y=25;doprintf (5d, newlist-data); newlist=newlist-next;while(newlist!=NULL); i=l； deletelist (newlist, i);i=3; deletelist(newlist, i); doprintf(5d，newlistdata); newlist=newlistnext;while(newlist!=NULL);i=4; insertnode(newlist, x, i);i=8; insertnode(newlist, y, i); printf(n);doprintf(5d，newlist-data); newlist=newlistnext;while(newlist!二NULL); getchar;return 0;实验2二叉树的建立与遍历一、目的掌握二叉树的相关概念,能熟练完成二叉树的递归法建立、先序、中序和后 序遍历方法.二、题目二叉树的创建与遍历算法的设计三、实验内容及步骤要求要求：以下3个题中，任意选作一题.1、问题描述一一从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法. 基本要求：(1) 从键盘输入二叉树的元素,建立二叉树.(2) 实现二叉树的先序遍历算法.2、问题描述一一从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法. 基本要求：(1) 从键盘输入二叉树的元素,建立二叉树.(2) 实现二叉树的中序遍历算法.3、问题描述一一从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法. 基本要求：(1) 从键盘输入二叉树的元素,建立二叉树.(2) 实现二叉树的后序遍历算法.四、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.五、范例参考include 甘include typedef struct Nodeint data;struct Node *LChild;struct Node *RChild;BitNode, *BitTree;void CreatBiTree(BitTree *bt)/用先序遍历序列创建二叉树，如果是首当 前树根置为空，否则申请一个新节点/scanf (%d, &t);if(t二二0)*bt二NULL;else*bt二(BitTree)malloc(sizeof(BitNode); (*bt)-data=t:CreatBiTree(&(*bt)-LChild);CreatBiTree(&(*bt)-RChiId);void Visit (int data)/访问根节点printf(%4d ，data);)void PreOrder(BitTree root)/*先序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ if (root!=NULL)Visit (root -data) ; /*访问根结点*/PreOrder (root -LChild) ; /*先序遍历左子树*/PreOrder (root -RChild) ; /*先序遍历右子树*/void InOrder(BitTree root)/*中序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if (root!二NULL)(InOrder (root -LChild) ;/*中序遍历左子树*/Visit (root -data) ;/*访问根结点*/InOrder (root -RChild) ;/*中序遍历右子树*/)void PostOrder(BitTree root)/*后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/if (root!二NULL)PostOrder (root -LChild) ; /*后序遍历左子树*/ PostOrder (root -RChild) ; /*后序遍历右子树*/ Visit (root -data) ;/*访问根结点*/void PrintTree(BitTree Boot, int nLayer) /按竖向树状打印的二叉树 /int i;if (Boot=NULL) return;PrintTree(Boot-RChild, nLayer+1);for (i=0;iLChiId, nLayer+1);int _tmain(int argc, _TCHAR* argv) BitTree T;int h;int layer;int treeleaf;layer=0;printf (请输入二叉树中的元素(以先序遍历序列输入，其中0代表空子 树)：n)；CreatBiTree (&T); printf (先序遍历序列为：);PreOrder (T);printf CAn中序遍历序列为:);InOrder (T);printf (n后序遍历序列为:);PostOrder (T);getch;return 0;实验3图的建立与遍历一、目的掌握图的定义，能熟练地运用邻接表和矩阵实现图的存储与深度优先和广度 优先的遍历方法.二、题目请以图1中给出的加权有向图完成实验内容与实验步骤要求中给出的2题.三、实验内容及步骤要求1、输出该图的邻解表和矩阵2种存放形式的存放结果；图1加权有向图2、编程输出该图的深度优先遍历和广度优先遍历的结果.（注意遍历得的结果不唯一，如下 的输出结果仅供参照）004000800009005006000500300010004000800009005006000500300010050700004000800009005006000500300010这是图的邻接表的形式0：311:22：503:524:35:40四、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.五、范例参考#include#includedefine max 100typedef struct(int number;int info;)VertexType;typedef struct(int edgesmaxmax: int n, e;VertexType vexsmax;define max 100typedef struct(int number;int info;)VertexType;typedef struct(int edgesmaxmax: int n, e;VertexType vexsmax;/最大顶点个数/以下定义临接矩阵类型顶点编号/顶点其他信息，边的权值顶点类型/图的定义邻接矩阵/顶点数和弧数/存放定点信息)MGraph;typedef struct ANodeint adjvex; /弧的重点位置，就是放值的 struct ANode nextarc;int info;)ArcNode;图的邻接矩阵类型/定义邻接表类型弧的结点结构类型/指向下一条弧的指针/存放弧的信息（权值）typedef struct Vnodeint data;ArcNode *firstarc;/邻接表/图中顶点数和和边数图的邻接表类型全局数组用于判断后面/输出邻接矩阵/将邻接矩阵g转换为邻邻接表头结点的的类型/指向第一条弧)VNode;typedef VNode AdjListmax; /AdjList是邻接表类型，把大表变成几个小的连接到一起typedef structAdjList adjlist:int n, e;ALGraph;int visitedmax: 节点是否被访问过 void DispMat(MGraph g)int i, j;for (i=0;ig. n;i+)for (j=0;jadjlisti. firstarc=NULL;for (i=0; in; i+)/检查邻接矩阵的每个元素for (j=0;jadjvex=j: p-info=g. edges i j ;/存放边的权值p-nextarc=G-adjlisti. firstarc; 将*?连接到表后 G-adjlisti. firstarc=p;Ge=g. e;G-n=g. n;/输出邻接表弧的类型/这是那个大链表的头/顺着那个头向下查看/输出邻接表弧的类型/这是那个大链表的头/顺着那个头向下查看void DispAdj(ALGraph *G)(int i; ArcNode *p;for (i=0;in;i+)p=G-adjlisti. firstarc; if (p!=NULL)printf ( %d: ，i);while(p!=NULL)printf ( %d ，p-adjvex) ;/输出弧的终点p=p-nextarc; printf(n)；)void change (int visited, ALGraph *G) /给全局变量 visited 赋初值for (i=0;in;i+) visitedi=O;)void ListToMat (ALGraph *G, MGraph g)/将邻接表转换为邻接矩阵的形式(int i, j;int n=Gn:ArcNode *p;for (i=0;in;i+)for (j=0;jn;j+)g. edgesi j=0;for(i=0;iadjlisti. firstarc;while (p!=NULL)g.edgesip-adjvex=p-info; p=p-nextarc;g. n=n;g. e=G-e;void DFS (ALGraph *G, int v)/递归深度优先遍历ArcNode *p;/change(visited, G):visitedv=l;/第一个点设为已被访问并输出，接着以他为主进行遍历 printf ( d, v);p=G-adjlistv. firstarc;while(p!=NULL)if (visitedp-adjvex=0)DFS (G, p-adjvex); p=p-nextarc;)void BFS(ALGraph *G, int v) 广度优先遍历，一个点先找和其有关的所有节点，在 接着按步骤继续预备实验编制简单C+程序本部分主要介绍在Visual C+中编译和运行单个C程序的方法.1、打开VC,出现如图2. 1所示界面：图2.1 VC初始界面（新建）对话2、打开“file”（文件）菜单，选择“new”（新建），会出现“new” 框,如图2. 2所示：ArcNode *p;/定义循环队列并初始化int queuemax, front=0, rear=0; int visitedmax;int w, i;for (i=0;in;i+) visitedi=O;printfC %d ”, v);把输入的第v个作为第一个广度遍历的节点，一直这样进行下 去visitedv=l;rear=(rear+l)%max;queuerear=v;while(front!=rear)front= (front+l)%max;w=queuefront;p=Gadjlistw. firstarc:一个顶点了while(p!=NULL)rear=(rear+l)%max;queuerear=v;while(front!=rear)front= (front+l)%max;w=queuefront;p=Gadjlistw. firstarc:一个顶点了while(p!=NULL)要入队了把V入队队列不为空的时候要出队了/跟前面差不多开始查找与顶点W邻接的第if (visitedp-adjvex=O)/就是当前节点未被访问printf (/z%d ，z, p-adjvex); visitedp-adjvex=l;rear= (rear+1) %max; 又要入队了，马上要重复之前的操作了 queuerear=p-adjvex;p=p-nextarc;void mainint i, j;MGraph g;/没有定义过的邻接表类型加上*ALGraph *G; int Amax6;printf (请输入邻接矩阵:n);for (i=0;i6;i+)for(j=0;j6;j+) scanf (d，&Ai j);)g. n=6;g e = 10;for(i=0;ig. n;i+)for (j=0;jg. n;j+)g. edgesi j=Ai j ; /这是给邻接矩阵赋值 printf (这是图的邻接矩阵的形式:)； printf (n)；DispMat (g) ;/输出邻接矩阵的函数G= (ALGraph *)malloc(sizeof(ALGraph);MatToList(g, G);printf r这是图的邻接表的形式:)；printf (n)；DispAdj(G);printf (从顶点0开始的深度优先遍历：n); DFS (G, 0);printf (n)；printf (从顶点0开始的广度优先遍历：n); BFS (G, 0);printf (n)；实验4最小生成树与最短路径的算法一、目的掌握求解图最小生成树的Prim算法和求解单源最短路径的Di jstra算法.二、实验内容及步骤要求要求：以下2个题中，任意选作一题.1、问题描述一一运用Prim算法求出下图给出的无向图（边权为正数）中构成最小生成 树的边权之和.2、问题描述一一运用Dijstra算法求出下图给出的有向图（边权为正数）中从0号顶 点到其他顶点间的最短路径值.三、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.!1!I、范例参考1.源程序ttinclude ttinclude #define Maxint 9999999define N 110/创建map二维数组储存图表，low数组记录每2个点间最小权值,visited数组标记 某点是否已访问mapNN, lowN, visitedN;n;intintint prim(int i, j, pos, min, result=0; memset(visited, 0, sizeof(visited);/从某点开始,分别标记和记录该点 visitedl=l;pos=l;第一次给low数组赋值 for(i=l;i=n;i+) if(i!=pos) lowi=mapposi;/再运行n-1次for(i=l;in;i+)/找出最小权值并记录位置min=MaxInt;for(j=l;jlowj) min=lowj;pos=j;/最小权值累加result+=min;标记该点visitedpos=l;更新权值for(j=l;jmapposj) lowj=mapposj；return result;int mainint i, v, j, ans; while(scanf&n)!=EOF) /所有权值初始化为最大 memset(map, Maxint, sizeof(map); for(i=l;i=n;i+)for(j=l;j=n;j+)scanf (d，&v); mapij=mapij=v; ans=prim;printf (dn, ans);return 0;源程序ttinclude ttinclude #define MaxVertexNum 100 typedef int VertexType ; /由用户定义顶点类型 typedef int EdgeType;/由用户定义边上的权值类型typedef struct VertexType vexsMaxVertexNum;EdgeType edgesMaxVertexNumMaxVertexNum; int n, e;MGrap;bool visitedMaxVertexNum: void createMGrap(MGrap*): void DFSTraverse(MGrap* ):void DFS(MGrap* , int );void Dijkstra(MGrap* , int, int);void main MGrap *G =(MGrap*)malloc(sizeof(MGrap);int D5; createMGrap(G);for (int i=0;in;i+) for(int j=0;jn;j+) printf(-8d，G-edgesij); printf (n);)DFSTraverse(G);Di jkstra(G, 0, D);void createMGrap(MGrap* G)( int i, j, k, w=0, p;/ printf (输入顶点数和边数n”); scanf(d, %d，&Gn, &Ge);for ( p=0;pn;p+)(/ printf (，z输入顶点信息)；scanf(%d, &Gvexsp);/ printf (邻接矩阵初始化n); for ( i=0;in;i+)for ( j=0;jn;j+)G-edgesij=1000;for ( k=0;ke;k+)/printf (读入两个顶点(i, j)之间边的值wn);scanf (d, %d, %d，&i, &j, &w);G-edgesij=w;/ G-edgesji=w;/ printfC 读入的数 i=%d, j=%d, w=%dn i, j, w); void DFSTraverse(MGrap* G) int i;for (i=0;in;i+) visitedi二false;printf (深度优先遍历序列：n);for (i=0; in; i+) 确保每一个顶点都遍历过，如果有孤立的也可以 if (!visitedi)DFS(G, i)；printf (n);)void DFS(MGrap* G, int i) printf (d-，Gvexsi);visitedi二true;for (int j=0;jn;j+) if (G-edges i visitedj)DFS(G, j);void Dijkstra(MGrap* G , int s, int D) int k=0;Ds=0;for (int i=0;in;i+) visitedi=false;visiteds=true;/初始化最短距离一维数组for (int i=0;in;i+)if (!visitedi) Di=G-edgessi;/修改最短距离一维数组for (int i=0;inl;i+)(/找出最小的值，下次找的时候不包括已经找到的int min =1000;for (int j=0;jG-n;j+) if (!visitedj&Djmin) min=Dj;k=j；visitedk=true;printf (最小值的下标%dn, k);/修改剩余点的距离值for (int j二0;j n;j+)if (!visitedj& DjDk+G-edgeskj)Dj= Dk+G-edgeskj:for (int i=0;iG-n;i+)printf (s 到顶点d 的最短距离dn，i, Di);实验5内排序一、目的掌握以简单选择法、快速排序、归并排序和箱式排序这4类经典的内排序 算法.二、实验内容及步骤要求要求：任选2题完成;对1和2小题封装一个记录结构(含一个记录值成员和一个排序 键值成员)1. 编写一个简单的程序实践箱式排序算法,要求在main中分别输入排序前后的记录 值以便比较.2. 编写一个简单的程序实践2路归并排序算法,要求在main中分别输入排序前后的记 录值以便比较.3. 编写一个简单的程序实践简单选择排序算法,要求在main中分别输入排序前后的 记录值以便比较.4. 自定义整型数组，对放入其中的若干个元素进行快速排序的实现，要求在main中分 别输入排序前后的数组内容以便比较.三、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.四、范例参考源程序：(箱式排序)甘include stdio. h甘define num_arr 5typedef struct attrint key;char name10;ArrType ;void sort (ArrType A)int i;ArrType Bnum_arr;for (i=0; inum_arr ; i+) BAi. key二 Ai;for (i=0; i Bi. name);void mainArrTypecnum_arr=4, John, l,Jane, 0, Alice, 2,Peter, 3, To nTsort (c);)源程序：(归并排序)#include甘define N 7#def ine LQ (a, b) (a) = (b)甘define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度*/ typedef int KeyType; /*定义关键字类型为整型*/ typedef int InfoType; /*定义其它数据项的类型*/ typedef structKeyType key; /* 关键字项 */InfoType otherinfo; /*其它数据项，具体类型在主程中定义*/ )RedType; /* 记录类型 */ typedef struct(RedType r MAXSIZE+1; /* r0闲置或用作哨兵单元 */ int length; /*顺序表长度*/)SqList; /*顺序表类型*/void Merge(RedType SR, RedType TR, int i,int m, int n) /*将有序的SRi.m和SRm+l.n归并为有序的TRi.n */ int j, k, 1;for (j=m+l, k=i ; i=m&j=n;+k) /* 将 SR 中记录由小到大地并入 TR */ if LQ(SRi. key, SRj. key)TRk二SRi+;else TRk=SRj+;if(i=m) for (1=0;l=m-i;1+)TRk+l=SRi+l; /* 将剩余的 SRi.m复制到 TR */ if(j=n)for (1=0: K=n-j ; 1+)TRk+l=SRj+l; /* 将剩余的 SRj.n复制到 TR */图2. 2 “new”对话框3、在“new”（新建）对话框中选择Files” （文件）选项卡，选择“C+Source File，如图2. 3所示：程序编写窗口13回区）File Edit View Insert Project Build Tools Window Help渗圜岛！副则 | Build / Debug Find in Files 1 Find in | |ReadyLn 1, Col 1OVRREAD Z图 2. 3 选择 “C+ Source File”按钮，即可在出现的程序编写窗口中编写源程序了,4、单击“注意:此时程序文件名和存放位置由系统默认，如图2. 4所示:图2.4程序编写窗口5、若要确定程序文件名为“TESTI. CPP” （VC中编写的源程序扩展名为.CPP）,void MSort(RedType SR, RedType TRI,int s, int t) /* 将 SRs. t归并排序为 TRls. . t.*/int m;RedType TR2MAXSIZE+1;if(s=t)TRls=SRs;else(m 二(s+t)/2; /* 将 SRs. . t平分为 SRs. . m和 SRm+l.t */ MSort (SR, TR2, s, m) : /* 递归地将 SRs. .m归并为有序的 TR2s. .m */MSort (SR, TR2,m+l,t); /* 递归地将 SRm+l. t归并为有序的 TR2m+l.t */Merge (TR2, TRI, s, m, t) ; /* 将 TR2 s. m和 TR2m+l. t归并到 TRls. t */ void MergeSort(SqList *L) /*对顺序表L作归并排序.*/MSort (*L). r, (*L). r, 1, (*L). length);)void print(SqList L)(int i;for(i=l:i=L. length;i+)printf ( (%d, %d) , L. r i. key, L. r i. otherinfo);printf(n)；)void mainRedTypedN = (49, 1, (38, 2), (65, 3, 97,4, 76,5, 13,6, (27, 7;SqList 1;int i;for (i=0:iN;i+)1. r i+l=di;1.length=N;printf (z，排序前：n); print (1);MergeSort(&1);printf r排序后：n)； print (1);)源程序：(快速排序)include stdio. hint Partion(int A, int p,int q)int x=Ap;int i=p, t;int j;for(j=i+l;j=q;j+)( if(Aj=x) (i+；t=Ai ;Ai=Aj ;Aj=t;)t=Ap ;Ap二Ai ;Ai=t;return i;void Quicksort(int A, int p, int q)(int r;if(pq)r=Partion (A, p, q);Quicksort (A, p, rl);Quicksort (A, r+1, q);int main(int argc, char* argv)inta = (10, 22, 56, 789, 100, 38, 6, 45, 66, 19, 17, 26, 76, 749, 1000, 388, 5666, 405, 6060, 1900, i;Quicksort (a, 0, 19);for(i=0;i=19;)printf (5d，ai+);if (i%10=0)printf(n);return 0:源程序：(简单选择排序)main( void sort(char *name, int n), print (char *name, int n); char *name=Follow me, BASIC”,Great Wall”, FORTRAN”, Computer ;int n=5;sort (name, n);print (name, n);)void sort (char *name, int n)( char *temp;int i, j, k;for(i=0;i0)k=j;if (k!=i)( temp=naniei ; namei=namek ; namek=temp;实验6查找一、目的掌握顺序查找和二分查找算法.二、实验内容及步骤要求1. 自定义一个字符串数组，通过键盘给全部元素赋初值,用直接顺序查找方法搜索该 数组中指定的元素是否存在，如果存在报告其位置，否则报告该元素不存在.2. 自定义一个数值型数组，通过键盘给数组元素赋予初值，用你学过的任意一种方法 对该数组进行排序,然后编程实践运用二分法在该数组中查找指定的元素是否存在，如果 存在报告其位置，否则报告该元素不存在.三、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.四、范例参考1.源程序(顺序查找)main( char book10020;int i;for (i=0;i100;i+)gets(booki);printf( input book name:” );gets(bname);for(i=0;i100:i+)if ( strcmp(bname, booki)=0)( printf( found!); break;)if (i=4)printf(not found!” );2 .源程序(二