数据结构指导书(第三版).doc

实验一实验名称线性表的顺序存储实验日期实验目的1.掌握线性表的顺序存储结构。2.能熟练利用顺序存储结构实现线性表的基本操作。3.能熟练掌握线性表创建、插入、删除、查找和显示线性表中元素等基本操作。实验内容1建立含有不少于3个元素的顺序表，并将结果在屏幕上输出。2. 对刚建立的顺序表实现插入、删除、查找，并将结果在屏幕上输出。3设计一个选择式菜单。算法描述：#include stdio.h#include malloc.h#define MAXSIZE 200 /线性表允许的最大长度#define datatype inttypedef struct /定义线性表的结构 datatype dataMAXSIZE; /表示线性表（a1，a2，.,an） int last; /last表示线性表的实际长度 SeqList;/* 线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表 */SeqList *init_SeqList( ) SeqList *L; L=new SeqList; / L=malloc(sizeof(SeqList); L-last=-1; return L;/* 插入操作：Insert_List(L,i,x)初始条件：线性表L存在，插入位置正确 (1=i=n+1,为插入前的表长)。操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, . , n 的数据元素的序号变为 i+1,i+2, . , n+1，插入后表长=原表长+1。 */int Insert_SeqList(SeqList *L,int i,datatype x)/*删除操作：Delete_List(L,i)初始条件：线性表L存在，1=i=n。操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,., n 的元素变为序号为 i, i+1,.,n-1，删除后新表长原表长。 */int Delete_SeqList(SeqList *L,int i) /*按值查找：Locate_List(L,x)，是给定的一个数据元素。初始条件：线性表L存在操作结果：在表L中查找值为的数据元素，其结果返回在L中首次出现的值为的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为的数据元素，返回一特殊值表示查找失败。 */int Location_SeqList(SeqList *L, datatype x) void print(SeqList *L) /打印线性表 int i; for (i=0;ilast;i+) printf(%d,L-datai); printf(n);void main() SeqList *L; int i,j,k; datatype x; do printf(nnnn); printf(ttt 线性表子系统n);printf(tt*n);printf(tt* 1-初始化表 *n);printf(tt* 2-插 入*n);printf(tt* 3-删除*n);printf(tt* 4-查找*n);printf(tt* 5-显示*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(05)：);scanf(%d,&k);getchar();switch(k) case 1: L=init_SeqList( ); /初始化线性表 break; case 2: /在线性表第i位置处插入值为X的元素printf(n 请输入插入的位置i和数据X(输入格式：i,X):);scanf(%d,%d,&i,&x); j=Insert_SeqList(L,i,x);break; case 3: /删除线性表中值为X的元素 printf(n 请输入要删除元素的位置i:);scanf(%d,&i); j=Delete_SeqList(L,i);if (j = 1) printf(删除成功!);else printf(删除失败!);break; case 4: /查找线性表中元素值为x的位置printf(n 请输入要查找的数值X:);scanf(%d,&x); j=Location_SeqList(L,x);if (j != -1 ) print(L);printf(中值为X所在的位置是 %d ,j);elseprintf(线性表中无此元素!n);break; case 5: /输出线性表 printf(n线性表的顺序存储为：); print(L); while(k!=0);运行结果实验人员实验地点教师评语优良中及格不及格批改日期实验二实验名称线性表的链式存储实验日期实验目的1.掌握线性表的链式存储结构。2.能熟练利用链式存储结构实现线性表的基本操作。3.能熟练掌握链式存储结构中算法的实现。实验内容1.用头插法或尾插法建立带头结点的单链表，并在屏幕上输出显示此链表。2.实现单链表上的插入、删除、修改、查找、计数等操作，并将结果在屏幕上输出。3设计一个选择式菜单。算法描述：#include stdio.h#include malloc.h#define datatype inttypedef struct node datatype data; /链表的数据域 struct node *next; /链表的指针域 LNode,*LinkList;LinkList Creat_LinkList1( ) /头插入法建立单链表算法 /*按序号查找 Get_Linklist(L,i)在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/LNode *Get_LinkList(LinkList L,int i) /*插入运算 Insert_LinkList(L,i,x)在单链表L的第i个位置上插入值为x的元素*/int Insert_LinkList(LinkList L, int i, datatype x) /*删除运算：Del_LinkList(L,i)删除单链表L上的第i个数据结点*/int Del_LinkList(LinkList L,int i) void print(LinkList L) /输出单链表 LNode *p=L; while(p-next!=NULL) printf(%d-,p-data); /输出表中非最后一个元素 p=p-next; printf(%dn,p-data); /输出表中最后一个元素 void main() LinkList H; int i,j,k;datatype x;do printf(nnnn); printf(ttt 链表子系统n);printf(tt*n);printf(tt* 1-建 表 *n);printf(tt* 2-插 入*n);printf(tt* 3-删除*n);printf(tt* 4-查找*n);printf(tt* 5-显示*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(05)：);scanf(%d,&k);getchar();if (k=1) H=Creat_LinkList1( ); /用头插入法建立单链表else if (k=2) /在线性表第i位置处插入值为X的元素printf(n 请输入插入的位置i和数据X(输入格式：i,X):);scanf(%d,%d,&i,&x);j=Insert_LinkList(H,i,x);else if (k=3)printf(n 请输入要删除元素的位置i:);scanf(%d,&i);j=Del_LinkList(H,i);if (j = 1) printf(删除成功!);else printf(删除失败!);else if (k=4) /查找线性表中元素值为x的位置printf(n 请输入要查找的序号i:);scanf(%d,&i);LNode *p;p=Get_LinkList(H,i);if (p!=NULL) print(H);printf(中序号为i的地址是 %d ,p);elseprintf(链表中无此序号!n); else if (k=5) /输出链表 printf(n表的存储顺序为：); print(H); while(k!=0);运行结果实验人员实验地点教师评语优良中及格不及格批改日期实验三实验名称栈的应用实验日期实验目的1.掌握栈的数据类型描述及栈的特点。2.掌握栈的顺序和链式两种存储结构的特点及算法描述。3.掌握栈的5种基本运算及算法在两种不同存储结构上的实现。实验内容1编写链式栈进栈、出栈、显示栈中全部元素的程序。2将一个正整数n转换成R进制，要求用顺序栈的来实现。3用switch语句设计一个选择式菜单，以菜单方式执行上述操作。算法描述：#include stdio.h#include malloc.htypedef int datatype; typedef struct node /定义链式栈结构datatype data;struct node *next;StackNode,*LinkStack;/置空栈 LinkStack Init_LinkStack() /入栈 LinkStack Push_LinkStack(LinkStack top, datatype x) /出栈LinkStack Pop_LinkStack (LinkStack top, datatype *x)void print(LinkStack top)StackNode *p=top;while(p != NULL) printf(%d-,p-data);p=p-next;/顺序栈#define MAXSIZE 1024 typedef structdatatype dataMAXSIZE;int top;SeqStack;/顺序栈置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack *Init_SeqStack()SeqStack *s;s=new SeqStack;s-top= -1; return s;/顺序栈判空栈int Empty_SeqStack(SeqStack *s)if (s-top = -1) return 1; else return 0;/顺序栈入栈int Push_SeqStack (SeqStack *s, datatype x)if (s-top = MAXSIZE-1) return 0; /栈满不能入栈else s-top+; s-datas-top=x; return 1;/顺序栈出栈int Pop_SeqStack(SeqStack *s, datatype *x) if (Empty_SeqStack(s) return 0; /栈空不能出栈 else *x=s-datas-top;s-top-; return 1; /栈顶元素存入*x，返回 void conversion(int N,int r)SeqStack *s;datatype x; s=Init_SeqStack();/初始化栈printf(n %d 的十进制数转换成 %d 进制为: ,N,r);while ( N ) Push_SeqStack (s,N%r); /余数入栈 N=N/r ;/商作为被除数继续 while ( !Empty_SeqStack(s) Pop_SeqStack (s,&x) ; printf( %d ,x) ; void main() LinkStack top;top=Init_LinkStack(); int i,j,k; datatype x; do printf(nnnn); printf(ttt 栈的应用子系统n);printf(tt*n);printf(tt* 1-链式进栈 *n);printf(tt* 2-链式出栈*n);printf(tt* 3-链栈显示*n);printf(tt* 4-进制转换*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(04)：);scanf(%d,&k);getchar();switch(k) case 1: /进栈printf(n 请输入要进栈的数据X:);scanf(%d,&x); case 2: /出栈 case 3: /打印链式栈中的元素 printf(n 链式栈的元素有：); case 4: /进制转换int N,r;printf(n 请输入一个整数N=); printf(n 请输入一个要转换的进制数r=); 运行结果实验人员实验地点教师评语优良中及格不及格批改日期实验四实验名称队列的应用实验日期实验目的1.掌握队列的数据类型描述及队列的特点。2.掌握队列的顺序和链式两种存储结构的特点及算法描述。3.掌握队列的5种基本运算及算法在两种不同存储结构上的实现。实验内容1 实现顺序循环或链式队列的进队列、出队列、判断队列空否、显示队列中全部元素的运算。2 设计一个选择式菜单，以菜单方式选择队列的各种操作。算法描述：#include stdio.h#include malloc.htypedef int datatype; #define MAXSIZE 50 /队列的最大容量/定义队列的结构体typedef struct ; /置空队/入队/出队/判队空/显示队列void main()c_SeQueue *sq;LQueue *Lq;int j,k;datatype x;sq=Init_SeQueue(); Lq=Init_LQueue();do printf(nnnn); printf(ttt 队列子系统n);printf(tt*n);printf(tt* 1-进 队 列 *n);printf(tt* 2-出 队 列*n);printf(tt* 3-队列空否*n);printf(tt* 4-显示队列*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(04)：);scanf(%d,&k);getchar();switch(k) case 1: /进队列printf(n 请输入要进队列的数据:); ; ; break; case 2: /出队列 ;break; case 3: /判断队列空否 ;if (j=1) printf(此队列为空!);else printf(此队列不空。);break; case 4: /显示队列printf(n 此队列有数据：); ;while(k!=0);运行结果实验人员实验地点教师评语优良中及格不及格批改日期实验五实验名称二叉树的遍历和应用实验日期实验目的1.掌握二叉树的数据类型描述及二叉树的特性。2.掌握二叉树的链式存储结构的建立算法。3.掌握二叉链表上二叉树的基本运算的实现。实验内容1.用递归或非递归的方法建立一棵二叉树。2.用递归实现二叉树的先序、中序、后序三种遍历。3.求二叉树的深度、叶子结点的个数。4.设计一个选择式菜单，以菜单方式实现各种操作。算法描述：#include stdio.h#include malloc.htypedef char TelernType; typedef struct BTreeNode TelernType data ; /树的数据域为字符型struct BTreeNode *LChild ; /*左孩子指针struct BTreeNode *RChild ; /*右孩子指针BTree ; BTree *CreatBTree()BTree *T;char x;scanf(%c,&x);getchar();if (x=0) T=NULL;else T=new BTree;T-data=x;printf( 请输入 %c 结点的左孩子：,T-data);T-LChild=CreatBTree();printf( 请输入 %c 结点的右孩子：,T-data);T-RChild=CreatBTree();return T;/前序递归遍历二叉树void PreOrder(BTree *T) void InOrder(BTree *T)void postOrder(BTree *T)int TreeHeight(BTree *T)int lh,rh;if (T=NULL) return 0;elselh=TreeHeight(T-LChild );rh=TreeHeight(T-RChild );if (lhrh) return lh+1;else return rh+1;int count=0;void leafnum(BTree *T)if(T) /树不空if (T-LChild=NULL & T-RChild =NULL)count+;leafnum(T-LChild );leafnum(T-RChild ) ;void main()BTree *T;int k;do printf(nnnn); printf(ttt 树 子系统n);printf(tt*n);printf(tt* 1-建二叉树 *n);printf(tt* 2-前序遍历 *n);printf(tt* 3-中序遍历 *n);printf(tt* 4-后序遍历 *n);printf(tt* 5-求树高度 *n);printf(tt* 6-叶子个数 *n);printf(tt* 0-返回 *n);printf(tt*n);printf(tt 请选择菜单项(05)：);scanf(%d,&k);getchar();if (k=1)printf(n 请输入此树的根结点:); /建立二叉树else if (k=2) printf(n 此树前序遍历的顺序:); else if (k=3)printf(n 此树中序遍历的顺序:); else if (k=4) /查找线性表中元素值为x的位置printf(n 此树后序遍历的顺序:); else if (k=5) /输出链表 printf(n此树的高度是：%d, ); else if (k=6) /输出链表 printf(n此树叶子结点个数是：%d, ); while(k!=0);运行结果实验人员实验地点教师评语优良中及格不及格批改日期实验六实验名称图的邻接矩阵和遍历实验日期实验目的1.掌握图的基本概念和邻接矩阵的存储结构。2.掌握图的邻接矩阵存储结构的算法实现。3.掌握图在邻接矩阵存储结构上遍历算法的实现。实验内容1.对给定的图，建立图的邻接矩阵。2.实现该图的深度优先搜索遍历。3.实现该图的广度优先搜索遍历。4.设计一个选择式菜单，以菜单方式实现各种操作。算法描述：#include stdio.h#define MaxVertexNum 20 /定义图的最大顶点数#define MaxEdgeNum 50 /定义图的最大边数#define MaxValue 1000 /定义MaxValue为全局整型常量，作为无穷大typedef int VertexType; /定义图中顶点数据的类型VertexType为整型typedef VertexType vexlistMaxVertexNum; /为存储顶点信息的数组类型typedef int adjmatrixMaxVertexNumMaxVertexNum; /为存储邻接矩阵的数组类型int n; /实际的顶点个数int e; /实际的边个数int visited MaxVertexNum ; /全局数组标记置1表示已经访问，0为未访问/* 建立图的邻接矩阵通过从键盘上输入n个顶点信息和e条无向带权边的信息，建立邻接矩阵GA*/void Create(vexlist GV,adjmatrix GA,int n,int e)int i , j, k, w; printf (n 请输入 %d 个顶点数据, n); /建立顶点数组 for (i=1; i=n; i+) GVi=i; for (i=1; i=n; i+) /*初始化邻接矩阵数组*/for (j=1; j=n; j+) GA i j =MaxValue;printf (输入 %d 条无向带权边n, e); /*建立邻接矩阵数组*/for (k=1; k=e; k+) printf(输入第 %d 条边的两端序号及权值(i j W): ,k); scanf (%d%d%d, &i, &j, &w); GAij=GAji=w; /置数组中相应对称元素的值为w/邻接矩阵的深度遍历void dfs(vexlist GV,adjmatrix GA,int i) / 从顶点i出发的深度遍历 int j; printf(%d,GVi); /输出访问顶点 visitedi=1; /全局数组访问标记置1表示已经访问 for(j=1; j=n; j+) if (GAij!=MaxValue)&(!visitedj)dfs(GV,GA,j);/邻接矩阵的广度遍历void bfs(vexlist GV,adjmatrix GA,int i) /从顶点i出发广度遍历 int qMaxVertexNum ; /Q为队列 int f,r,j ; / f,r分别为队列头，尾指针 f=r=0 ; /设置空队列 printf(%d,GVi); / 输出访问顶点 visitedi=1; /全局数组标记置1表示已经访问 r+; qr=i ; /入队列 while (fr) f+; i=qf ; /出队列for (j=1; j=n; j+)if (GAij!=MaxValue)&(!visitedj) printf(%d,GVj);visitedj=1 ; r+; qr=j; void print(adjmatrix GA)void main()vexlist GV;adjmatrix GA;int i,k;do printf(nnnn);printf(tt 图的邻接矩阵子系统n);printf(tt*n);printf(tt* 1-更 新 图 *n);printf(tt* 2-深度遍历 *n);printf(tt* 3-广度遍历 *n);printf(tt* 0-返回 *n);printf(tt*n);printf(tt 请选择菜单项(03)：);scanf(%d,&k);switch(k)case 1:printf (n请输入图的顶点的个数n= ); ;printf (请输入图的边个数e= ); ; ;printf(图的邻接矩阵如下n);print(GA);break;case 2:for (i=0; i MaxVertexNum; i+) /*标志向量初始化*/visited i=0; printf (n请输入从图的哪个顶点(1-%d)开始深度遍历:,n); ;printf(深度遍历的结果为：); ;break;case 3:for (i=0; i MaxVertexNum; i+) /*标志向量初始化*/ ; printf (n请输入从图的哪个顶点(1-%d)开始广度遍历:,n); ;printf(广度遍历的结果为：); ;break; while (k!=0);运行结果实验人员实验地点教师评语优良中及格不及格批改日期实验七实验名称图的邻接表和遍历实验日期实验目的1.掌握图的基本概念和邻接表的存储结构。2.掌握图的邻接表存储结构的算法实现。3.掌握图在邻接表存储结构上遍历算法的实现。实验内容1.对给定的图，建立图的邻接表。2.实现该图的深度优先搜索遍历。3.实现该图的广度优先搜索遍历。4.设计一个选择式菜单，以菜单方式实现各种操作。算法描述：#include stdio.h#define MaxVertexNum 20 /定义图的最大顶点数#define MaxEdgeNum 50 /定义图的最大边数typedef int VertexType; /定义图中顶点数据的类型VertexType为整型typedef VertexType vexlistMaxVertexNum; /定义存储顶点信息的数组类型struct edgenode /定义邻接表中边结点类型 int adjvex; /邻接点域int weight; /权值域，对无权图可省略struct edgenode* next; /指向下一个边结点的链域;int n; /图中实际顶点的个数int e; /图中实际边的个数int visited MaxVertexNum ; /全局数组标记置1表示已经访问，0为未访问/定义adjlist 为存储n个表头指针的数组类型typedef struct edgenode* adjlistMaxVertexNum;/通过从键盘上输入e条有向无权边的信息，建立顶点数组GV和邻接表GLvoid Create(vexlist GV, adjlist GL, int n, int e)int i , j, k; for (i=1; i=n; i+) GVi=i; /建立顶点数组for (i=1; i=n; i+) /初始化邻接表，即将表头向量中的每个域置空GL i =NULL;printf (n输入 %d 条有向无权边nn, e); /建立邻接表for (k=1; kadjvex = j; /将j的值赋给新结点的邻接点域 p-next = GL i ; /将新结点插入到vi邻接表的表头 GL i = p; void print(adjlist GL) struct edgenode *p; for(int i=1;i,p-adjvex);p=p-next;printf(n); /邻接表的深度遍历，从初始点vi出发深度优先搜索由邻接表GL表示的图void DFS(adjlist GL, int i) struct edgenode *p;printf (%d , i); /假定访问顶点vi以输出该顶点的序号代之 visite