数据结构实验指导书(国教).doc

南昌工程学院数据结构实验指导书 10计算机应用技术（中韩）（专）徐晨光编2012 年 2月目 录实验一：C语言相关知识复习实验3实验二：线性表实验4实验三：栈和队列实验6实验四：数组、串8实验五：二叉树实验9实验六：图12实验七：查找实验13实验八：排序14实验一 C语言相关知识复习实验一、实验目的 巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。二、实验内容1.学生信息的显示，具体要求如下：1）定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址)；2）设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型；3）设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。提示：可用结构体数组保存学生信息。2. 输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如输入：10 2 30 4 5，逆置后显示为：5 4 302 10。提示：1.逆置的方法：设有n个数据元素a(0),a(1),a(2).,a(n-1)，将第i个元素与第n-i-1个元素调换位置即可。2.采用动态内存分配方法可参考如下代码int *a; int i; a=(int *)malloc(N*sizeof(int);/动态分配起始地址 for(i=0;iN;i+) scanf(%d,&ai);/给内存空间赋值三、实验源代码此处写程序源代码，请在程序中适当注释，便于老师更快地看懂你的程序。四、实验结果此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。实验二 线性表实验一、实验目的1、掌握建立顺序表的基本方法。2、理解和掌握顺序表元素查找算法。3、掌握顺序表的插入、删除算法的思想和实现。二、实验内容1、 建立一个顺序表，要求从键盘输入10个整数，并将该顺序表的元素从屏幕显示出来2、编写查找函数，在上面的顺序表中查找其中一个元素，如果找到，返回该元素在顺序表中的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。3、编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的顺序表输出；由用户输入删除第几个元素，将完成删除后的顺序表输出。以下是程序部分代码，请调试并补充使之正确运行：#include#include#define MAXSIZE 10typedef structint *elem;int length;SqList;main()int i,x,y;int LocateElem_Sq(SqList L,int e);printf(请输入顺序表的长度);scanf(%d,&ST.length);ST.elem=(int*)malloc(sizeof(int)*ST.length);for(i=0;i=ST.length-1;i+)ST.elemi=rand()%100;printf(%d ,ST.elemi);printf(请输入你要查找的数);scanf(%d,&x);y=LocateElem_Sq(x);printf(%d,y);printf(请输入你要插入的位置及元素值);scanf(%d,%d,&i,&x);y=ListInsert_Sq(&ST,i,x);for(i=0;iST.length;i+)printf(%d ,ST.elemi);int LocateElem_Sq(SqList L,int e)int i,*p;i=1;p=L.elem;while(i=L.length & *p+!=e) +i;if(ilength;j=i;j-)L-elemj+1=L-elemj;L-elemi=e;+L-length;return 1;上述代码提供参考，其中有的地方有错误，需要修改。请读懂以上代码，体会顺序表操作的C语言实现，注意函数调用过程中参数的值传递和地址传递。在此基础上完成顺序表的删除操作。删除操作函数定义为：int ListDelete_Sq(SqList *L,int i)。注意：其中顺序表的数据是随机产生，请考虑如何设计从键盘输入。三、实验源代码四、实验结果实验三 栈和队列实验一、实验目的 1掌握堆栈特殊线性表和队列的存储方式的基本操作方法。2掌握堆栈后进先出运算原则在解决实际问题中的应用。3掌握使用队列先进先出运算原则。二、实验内容1.假设一个算术表达式中包含圆括弧、方括弧三种类型的括弧，编写一个程序用于判别表达式中括弧是否正确配对。说明：检验表达式中的括号匹配情况：假设在一个算术表达式中，可以包含三种括号：圆括号（和），方括号和，并且这两种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。提示：算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。算法步骤：扫描表达式，1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空。 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余 栈的类型定义及基本操作代码可参考教材相关定义和程序。2.仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。以下是队列操作函数的定义：(1)QueueInitiate(Q) 初始化队列Q (2)QueueNotEmpty(Q) 队列Q非空否 (3)QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。 (4)QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。三、实验源代码 四、实验结果（测试数据）实验四 数组、串一、实验目的1理解动态数组与静态数组的区别2掌握动态数组的实现方法和基本应用3掌握串存储结构4掌握串的匹配算法，并能进行相关应用二、实验内容 1.设矩阵A,B,C都是3*3矩阵，矩阵元素为整数类型，要求： (1).3个矩阵都采用动态数组进行存储； (2).编写实现C=A+B的函数； (3).编写实现C=A*B的函数。 提示：整个程序流程可参考如下： 开始动态内存分配函数申请空间，输入矩阵A和B调用两个矩阵求和函数，输出和值调用两个矩阵乘积函数，输出乘积值 结束 2.设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中从位置start开始查找是否存在子串T。若存在，则用子串V去替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。要求设计主函数进行测试 。提示：算法的主要思想是在主串S中，利用Brute-Force函数从位置start开始定位子串T的位置，如果有T存在则删除T，插入子串V，直到S中不存在子串T。三、实验源代码四、实验结果（测试数据）实验五 二叉树实验一、实验目的1、掌握二叉树的建立方法2、掌握二叉树遍历的基本方法（前序、中序、后序）3、掌握递归二叉树遍历算法的应用二、实验内容1.构造一棵二叉树,树的形态如下图所示，打印出前序遍历、中序遍历、后序遍历的遍历序列。 A B FC E G D提示：1.前序遍历二叉树的递归算法为：若二叉树为空，则算法结束；否则：（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。2.中序遍历二叉树的递归算法为：若二叉树为空，则算法结束；否则： (1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。3.后序遍历二叉树的递归算法为：若二叉树为空，则算法结束；否则： (1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。2.选择一种遍历方式计算该树中叶子结点的个数，并打印出叶子结点。提示：前序遍历、中序遍历、后序遍历都可以用来求出叶子结点数。在遍历过程中，如果判断为叶子结点，则访问该结点，计数器加1。二叉树的定义可参考以下代码定义头文件为BiTree.htypedef struct Node ElemType data; /*数据域*/ struct Node *leftChild; /*左子树指针*/ struct Node *rightChild; /*右子树指针*/BiTreeNode; /*结点的结构体定义*/*初始化创建二叉树的头结点*/void Initiate(BiTreeNode *root) *root = (BiTreeNode *)malloc(sizeof(BiTreeNode); (*root)-leftChild = NULL; (*root)-rightChild = NULL;void Destroy(BiTreeNode *root) if(*root) != NULL & (*root)-leftChild != NULL) Destroy(&(*root)-leftChild); if(*root) != NULL & (*root)-rightChild != NULL) Destroy(&(*root)-rightChild); free(*root);/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/*原curr所指结点的左子树成为新插入结点的左子树*/*若插入成功返回新插入结点的指针，否则返回空指针*/BiTreeNode *InsertLeftNode(BiTreeNode *curr, ElemType x) BiTreeNode *s, *t; if(curr = NULL) return NULL; t = curr-leftChild; /*保存原curr所指结点的左子树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-leftChild = t; /*新插入结点的左子树为原curr的左子树*/ s-rightChild = NULL; curr-leftChild = s; /*新结点成为curr的左子树*/ return curr-leftChild; /*返回新插入结点的指针*/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/*原curr所指结点的右子树成为新插入结点的右子树*/*若插入成功返回新插入结点的指针，否则返回空指针*/BiTreeNode *InsertRightNode(BiTreeNode *curr, ElemType x) BiTreeNode *s, *t; if(curr = NULL) return NULL; t = curr-rightChild; /*保存原curr所指结点的右子树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-rightChild = t; /*新插入结点的右子树为原curr的右子树*/ s-leftChild = NULL; curr-rightChild = s; /*新结点成为curr的右子树*/ return curr-rightChild; /*返回新插入结点的指针*/*若curr非空，删除curr所指结点的左子树*/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/BiTreeNode *DeleteLeftTree(BiTreeNode *curr) if(curr = NULL | curr-leftChild = NULL) return NULL; Destroy(&curr-leftChild); curr-leftChild = NULL; return curr;/*若curr非空，删除curr所指结点的右子树*/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/BiTreeNode *DeleteRightTree(BiTreeNode *curr) if(curr = NULL | curr-rightChild = NULL) return NULL; Destroy(&curr-rightChild); curr-rightChild = NULL; return curr;三、实验源代码四、实验结果实验六 图一、实验目的1、 掌握图的遍历过程；2、 理解图的存储结构与基本操作；2、熟悉图的广度优先遍历的实现二、实验内容1 采用邻接矩阵的存储结构保存下图；2 编程实现该图的创建与广度优先遍历。提示：连通图的广度优先遍历算法为： （1）访问初始顶点v并标记顶点v为已访问；（2）顶点v入队列；（3）当队列非空时则继续执行，否则算法结束；（4）出队列取得队头顶点u；（5）查找顶点u的第一个邻接顶点w；（6）若顶点u的邻接顶点w不存在，则转到步骤（3），否则循环执行， （6.1）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问； （6.2）顶点w入队列； （6.3）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。 三、实验源代码四、实验结果（打印遍历的顺序）实验七 查找实验一、实验目的1、理解动态查找表的动态生成过程；2、任意给出一组