数据结构上机实验题.doc

。数据结构上机实验题内容概要：对于计算机学科而言，实践非常重要，它是检验读者对理论知识的掌握程度，同时加深读者对所学知识的理解和运用，本附录为读者布置了七道上机实验题，分别对应于教材的第二章至第四章及第六章至第九章的内容。实验一 线性表实验目的：1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构单链表中的各种基本操作。实验内容：1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。实验步骤：1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L=21，23，14，5，56，17，31，然后在第i个位置插入元素68。3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。实现提示：1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素 */typedef struct elemtype vecMAXSIZE; int len; /* 顺序表的长度 */ sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：typedef int elemtype;typedef struct node elemtype data; /数据域 struct node *next; /指针域linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(linklist *)malloc(sizeof(linklist);该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。思考与提高：1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2. 在main函数里如果去掉L=&a语句，会出现什么结果？实验二 栈实验目的：掌握栈的顺序表示和实现实验内容：编写一个程序实现顺序栈的各种基本运算。实验步骤：1. 初始化顺序栈2. 插入元素3. 删除栈顶元素4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈实现提示：/*定义顺序栈的存储结构*/typedef struct Datatype stackMAXNUM; int top;SqStack; /*初始化顺序栈函数*/void InitStack(SqStack *p) q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/*入栈函数*/void Push(SqStack *p,Datatype x) if(p-toptop=p-top+1; /*栈顶+1*/ p-stackp-top=x; /*数据入栈*/ /*出栈函数*/Datatype Pop(SqStack *p)x=p-stackp-top; /*将栈顶元素赋给x*/p-top=p-top-1; /*栈顶-1*/ /*获取栈顶元素函数*/Datatype GetTop(SqStack *p) x=p-stackp-top;/*遍历顺序栈函数*/void OutStack(SqStack *p) for(i=p-top;i=0;i-)printf(第%d个数据元素是：%6dn,i,p-stacki);/*置空顺序栈函数*/void setEmpty(SqStack *p) p-top= -1;思考与提高：读栈顶元素的算法与退栈顶元素的算法有何区别？实验三 队列实验目的：掌握队列的链式表示和实现实验内容：实现队列的链式表示和实现。实验步骤：1. 初始化并建立链队列2. 入链队列3. 出链队列4. 遍历链队列实现提示：/*定义链队列*/typedef struct Qnode Datatype data; struct Qnode *next;Qnodetype;typedef struct Qnodetype *front; Qnodetype *rear;Lqueue; /*初始化并建立链队列函数*/void creat(Lqueue *q) h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申请空间*/ h-next=NULL; q-front=h; q-rear=h;for(i=1;idata=x; s-next=NULL; q-rear-next=s; q-rear=s;/*出链队列函数*/Datatype Ldelete(Lqueue *q) p=q-front-next; q-front-next=p-next; if(p-next=NULL) q-rear=q-front; x=p-data; free(p); /*释放空间*/ /*遍历链队列函数*/void display(Lqueue *q) while(p!=NULL) /*利用条件判断是否到队尾*/ printf(%d-,p-data); p=p-next; 思考与提高：链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？实验四 树及二叉树实验目的：1. 通过实验，掌握二叉树的建立与存储2. 通过实验，掌握二叉树的遍历方法实验内容：1. 练习二叉树的建立与存储2. 练习二叉树的遍历实验步骤：1. 建立自己的头文件BinTree.h，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。2. 建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。实现提示：建立二叉树的代码如下：BinTNode *CreateBinTree() /输入二叉树的先序遍历序列，创建二叉链表 BinTNode *t;char ch;ch=getchar();if (ch=0) /如果读入0，创建空树 t=NULL;elset=(BinTNode *)malloc(sizeof(BinTNode);/申请根结点*t空间t-data=ch; /将结点数据ch放入跟结点的数据域t-lchild=CreateBinTree(); /建左子树t-rchild=CreateBinTree(); /建右子树 return t;思考与提高：1. 如何用孩子兄弟表示法存储树？2. 熟悉并掌握哈夫曼树及其应用。实验五 图实验目的：1. 掌握图的基本存储方法； 2. 掌握有关图的操作算法并用高级语言实现； 3. 熟练掌握图的两种搜索路径的遍历方法。实验内容：假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个简易交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。实验步骤：1. 定义结点结构，定义图结构。2. 存储图信息；3. 定义求某顶点到其他所有顶点最短路径的函数；4. 写出主函数。实现提示：int creatcost(int costMAX_VEX) /*建立图的邻接矩阵,cost数组表示图的邻接矩阵*/ int vexnum,arcnum,i,j,k,v1,v2,w; /*输入图的顶点数和弧数(或边数)*/ printf(n请输入顶点数和边数(输入格式为:顶点数,边数): ); scanf(%d,%d,&vexnum,&arcnum); for(i=1;i=vexnum;i+) for(j=1;j=vexnum;j+) costij=9999; /*设9999代表无限大*/ for(k=1;k=arcnum;k+) printf(v1,v2,w = ); scanf(%d,%d,%d,&v1,&v2,&w); /*输入所有边或所有弧的一对顶点V1,V2 */ costv1v2=w; return(vexnum);void dijkstra(int costMAX_VEX,int vexnum) /*Dijkstra算法求从源点出发的最短路径*/ int pathMAX_VEX,sMAX_VEX,distMAX_VEX,i,j,w,v,min,v1; /*S数组用于记录顶点V是否已经确定了最短路径,SV=1,顶点V已经确定了最短路径,SV=0,顶点V尚未确定最短路径。dist数组表示当前求出的从V0 到Vi 的最短路径。path是路径数组,其中pathi表示从源点到顶点Vi之间的最短路径上Vi的前驱顶点,如有路径(v1,v3,v5),则path5=3*/ printf(输入源点 v1 : ); scanf(%d,&v1); /*输入源点V1 */ for(i=1;i=vexnum;i+) disti=costv1i; /*初始时,从源点V1到各顶点的最短路径为相应弧上的权*/ si=0; /*初始化*/ if(costv1i9999) pathi=v1; /*初始化,path记录当前最短路径,即顶点的直接前趋*/ sv1=1; /*将源点加入S集合中*/ for(i=1;i=vexnum;i+) min=9999; /*本例设各边上的权值均小于9999*/ for(j=1;j=vexnum;j+) /*从S集合外找出距离源点最近的顶点w*/ if(sj=0)&(distjmin) min=distj; w=j; sw=1; /*将w加入S集合,即w已是求出最短路径的顶点*/ for(v=1;v=vexnum;v+) /*根据w修改dist*/ if(sv=0) /*修改未加入的顶点的路径长度*/ if(distw+costwvdistv) distv=distw+costwv; /*修改V-S集合中各顶点的最短路径长度*/ pathv=w; /*修改V-S集合中各顶点的最短路径*/ printf(源点1到其他各顶点的路径与值：n,v1); for(i=2;i=vexnum;i+) /*输出从某源点到其他各顶点的最短路径*/ if(si=1) w=i; while(w!=v1) printf(%d-,w); w=pathw; /*通过找到前驱顶点,反向输出最短路径*/ printf(%d,w); printf( %dn,disti); else printf(%d key=key;s-lchild=NULL; s-rchild=NULL;*bst=s;else if(keykey) InsertBST(&(*bst)-lchild), key); /*将s插入左子树*/ else if(key(*bst)-key) InsertBST(&(*bst)-rchild), key); /*将s插入右子树*/void CreateBST(BSTNode *bst) /*从键盘输入记录的值，创建相应的二叉排序树*/ int key;*bst=NULL;scanf(%d, &key);while (key!=0) /*输入0时结束*/InsertBST(bst, key);scanf(%d, &key);BSTNode *SearchBST(BSTNode *bst, int key)/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的记录，若查找成功，返回指向该记录结点指针，否则返回空指针*/ if (!bst) return NULL;else if (bst-key = key)return bst; /*查找成功*/elseif (bst-key key)return SearchBST(bst-lchild, key);/*在左子树继续查找*/else return SearchBST(bst-rchild, key);/*在右子树继续查找*/思考与提高：1. 用其它的查找方法完成该算法。2. 比较各种算法的时间及空间复杂度。实验七 排序实验目的：1. 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2. 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3. 了解各种方法的排序过程及其时间复杂度的分析方法。实验内容：统计成绩 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： （1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；