数据结构-实验指导书(自编简).doc

数据结构（C语言版）实验指导书（非计算机专业适用）广州大学2013.1目 录实验一 线性表的顺序存储及其操作1实验二 线性表的链式存储及其操作3实验三 栈和队列的应用7实验四 串及其操作9实验五 树及其操作11实验六 图及其操作16实验七 查找和排序22实验一 线性表的顺序存储及其操作预习题：1、 线性表是如何定义的？有什么特点？2、 线性表有哪些实现方法？3、 线性表的顺序存储和链式存储各有什么优缺点？4、 在线性表的顺序存储中，插入和删除都需要进行数据元素的迁移，问：两者迁移的方法有何异同？（从迁移的内容、迁移的顺序来分析）5、 顺序存储的线性表进行内容的翻转时，和数据元素的奇偶性有关吗？实验项目：线性表的顺序实现：查找、插入、删除、翻转实验类型: 基础性指导思想：用数组存储线性表，实现线性表的基本操作。实验目的及要求：1、 复习C语言的数组的定义；2、 理解线性表的属性；3、 实践线性表的顺序实现方法以及相关的操作；4、 要求：提交实验报告，附源程序、打印运行结果。涉及的知识点：线性表的逻辑属性、运算单数组的操作：定义、输入、输出、数组内容的翻转元素/数组的操作：元素的检索、插入、删除实验内容：实现数组的输入、输出、查找、插入、删除、翻转等功能，每个功能用一个函数实现，在主程序中按以下要求把这些函数组织起来。实验步骤：编写具有以下功能的程序：1、 从键盘读入10个整数（或字符）； 2、 显示当前数组内容；3、 输入一个数组元素，显示该元素在线性表中的位置；重复本过程，元素在表头、表中、表尾的各一次；4、 输入一个不在数组中的数据，程序要检测出该元素不在线性表内；5、 输入一个新的数组元素和要插入的位置，把该元素插入后显示数组内容；重复本过程，插入的位置在表头、表中、表尾的各一次；6、 输入一个合理的元素位置，删除该位置上的元素，显示数组内容；重复本过程，插入的位置在表头、表中、表尾的各一次；7、 把数组的内容翻转后输出；8、 删除一个数组元素，使得数组元素个数的奇偶性改变，再翻转一次、输出，以确认翻转过程适合于奇数和偶数长度的数组。- 22 -实验二 线性表的链式存储及其操作预习题：1、 线性表的链式存储在哪些方面比顺序存储要好？2、 在线性表的链式存储中，插入和删除都需要进行数据元素的迁移吗？3、 为什么链表的插入和删除操作都需要记住被操作的结点的前一个结点？4、 链式存储的线性表进行内容的翻转时，和数据元素的奇偶性有关吗？实验项目：线性表的链表实现：遍历、插入、删除、翻转实验类型: 基础性指导思想：用链表存储线性表，实现线性表的基本操作。实验目的及要求：1、 复习C语言的指针的定义、链表的使用；2、 理解线性表的属性；3、 实践线性表的链式实现方法以及相关的操作。4、 要求：提交实验报告，附源程序中填空的内容（10处）、打印运行结果涉及的知识点：线性表的逻辑属性、运算带表头的单链表的操作：定义、输入、输出、链表内容的翻转元素/链表的操作：元素的插入、删除实验内容：实现链表的输入、输出、插入、删除、翻转等功能，教师提供主要源代码，其中有10处标出需要学生填空，使得整个程序能正确运行。问题描述：用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。实验步骤：读懂后面附带的源代码，在标注“填空”的位置填写适当的表达式或语句，使得程序完成指定功能。测试要求：1、 连续插入5个实数；要求：插入的元素要分别位于表头、表中、表尾，以确保该插入函数适合于各种情况；2、 翻转链表，确认成功后再翻转一次，恢复元素的升序序列；3、 删除3个数组元素，删除的元素要分别要位于表头、表中、表尾，以确保该删除函数适合于各种情况；4、 删除一个不存在的元素，确认链表的内容没被改变。以下是待填空的源代码，请同学们粘贴到系统中填空、运行、测试：/* 链表操作：插入、删除、输出、翻转用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。 */#include #include malloc.h#define null 0struct node float data;struct node *next;void insert(float aa,struct node *vq)struct node *newnode,*p;newnode=(struct node *)malloc(sizeof(struct node);newnode-data=aa;p=vq;while (p-next!=null)&(p-next-datanext=p-next;/* 填空2 */;vq-data=vq-data+1;void dele(float aa,struct node *vq) struct node *p,*q;p=vq;while (p-next!=null)&(p-next-datanext=null)|(p-next-data!=aa)printf(n%5.1f is not in the link !,aa);else if (p-next-data=aa) q=p-next;p-next=/* 填空4 */;free(/* 填空5 */);vq-data=vq-data-1;void print(struct node *vq)struct node *p;printf(nthe length of link is %4.0f,vq-data);p=vq-next;printf(nthe link is:);while (/* 填空6 */) printf(%5.1f,p-data);/* 填空7 */;void reverse(struct node *vq) struct node *q,*p;p=(*vq)-next;(*vq)-next=/* 填空8 */;while (p!=null) q=p; p=/* 填空9 */; q-next=/* 填空10 */; (*vq)-next=q; main() int mark=1,op;float aa;struct node *vq;vq=(struct node *)malloc(sizeof(struct node);vq-data=0;vq-next=null;while (mark=1) printf(nWhich kind of operation will you select ? );printf(ninsert-1, delete-2, print-3, reverse-4, exit-0 : );scanf(%d,&op);switch (op) case 0: mark=0; break;case 1: printf(nPlease input the new element:);scanf(%f,&aa);insert(aa,vq);print(vq);break;case 2: if (vq-data=0)printf(n the link is null !,aa);elseprintf(nPlease input the deleted element:);scanf(%f,&aa);dele(aa,vq); print(vq);break;case 3: print(vq); break;case 4: reverse(&vq); print(vq);break;default:printf( input error!n);/*程序结束*/实验三 栈和队列的应用预习题：1、 栈和队列是如何定义的？各有什么特点？2、 栈和队列有哪些实现方法？3、 栈和队列的顺序存储和链式存储各有什么优缺点？实验项目：栈和队列及其操作的实现；栈和队列的应用实验类型：设计性指导思想：栈和队列是两种常用的和重要的数据结构。利用顺序存储或链式存储实现栈和队列及其基本操作，在此基础上，应用栈和队列解决实际问题。培养学生解决问题的能力。实验目的及要求：1、 熟悉栈和队列的定义和特点；2、 实践栈和队列的顺序和链式实现方法以及相关的操作；3、 根据实际问题的要求，合理使用栈和队列，设计相关程序；4、 要求：提交实验报告，附源程序、打印运行结果。涉及的知识点：栈和队列的存储方法栈的常用操作（构造、销毁、入栈、出栈、读栈、判断栈空或满）队列的常用操作（构造、销毁、入队列、出队列、判断队列空或满）实验内容：根据以下两个问题的要求，合理使用栈和队列，设计相关程序：项目一：字符串回文的判断“回文”英语叫做Palindrome，是指一个单字或名词或句子，顺读倒读都可成立的，英语单字中顺读倒读仍是同一字的有：civic，deed，did，gag，level，madam，noon，peep，refer，rotator。亚当同学刚刚碰到夏娃小姐时说的是什么？“Madam, Im Adam.”Napoleon被关的时候因为过度无聊也写过这玩意儿: Able Was I Ere I Saw Elba还有一些palindrome：No lemons，no melon.Dogs sass GodSilly ram ate wet amaryllis!Now, evil, Ive won!Was it a cat I saw? 这个的高级版本是Was it a car or a cat I saw？通过程序自动判断用户输入的字符串是否回文。提示：首先构造一个栈和队列，将用户输入的字符串同时入栈和入队列。然后当栈或队列不为空时，将出栈和出队列的元素进行比较，若全部一致，则为回文。显示效果如下图所示：项目二：判别表达式中的括号（“ 、()” ）是否匹配表达式运算是计算机重要应用之一，而判断表达式是表达式运算的基础。通过程序自动判断用户输入的表达式中的括号是否匹配。显示效果如下图所示：实验四 串及其操作预习题：1、 C语言是如何存储字符串的？与普通的字符型数组有何区别？2、 C语言的标准库函数提供了哪些串的函数？你自己能编写实现其相同功能的函数吗？3、 多个字符串合并时，如何处理结束符？4、 串的模式匹配算法是怎样的？5、 若主串中有多个地方匹配子串，要返回首次匹配的位置、返回最后匹配的位置、返回所有匹配的位置，各如何处理？实验项目：串的操作：单个字符串的长度统计、翻转、多个字符串的合并、子串判别实验类型：基础性指导思想：熟练掌握C语言的字符串操作方法，理解字符串与字符型数组的差异。实验目的及要求：1、 复习C语言的字符串的使用；2、 理解串的操作；3、 实现串的模式匹配算法；4、 要求：提交实验报告，附源程序、打印运行结果。涉及的知识点：串的存储方法常见的串的函数（求长度、两个字符串的连接）串的模式匹配BF算法（又称古典的、经典的、朴素的、穷举的）实验内容：读入两个字符串，输出其长度、连接之后的结果，再判断第一个字符串是否第二个串的子串。实验步骤：编写具有以下功能的程序：1. 读入两个字符串S1、S22. 分别显示这S1、S2的及长度3. 自己编写函数，把S1的内容翻转，即把S1逆序，生成S3，显示S3的内容、长度。提示：字符串结束符要单独处理。4. 分别显示S1+S2、S2+S1的结果5. 判断S1是否S2的子串6. 测试要求：a) S1、S2要带字母、数字、空格b) S1是S2的子串、S1不是S2的子串的各试一次实验五 树及其操作预习题：1、 二叉树是如何递归定义的？有什么特点？2、 满二叉树和完全二叉树有何区别？3、 为什么要进行树的遍历？4、 树的遍历方法有几种？对于每一种来说，遍历的结果是惟一的吗？5、 根据哪两种遍历结果，能够还原二叉树的结构？6、 树的层次遍历要用到我们前面学的什么结构？实验项目：二叉树的存储及先序、中序、后序、层次遍历实验类型：设计性指导思想：掌握把非线性结构的树数据转换为线性结构的多种方法实验目的及要求：1、 理解树的逻辑结构以及实现方法，尤其是在程序中的表达；2、 掌握树的多种遍历方法，先序、中序、后序的递归方法以及层次遍历的思想和实现方法；3、 设计统计二叉树的结点个数、叶片个数的算法；4、 要求：提交实验报告，附自己编写中序、后序递归函数、层次遍历函数、统计二叉树的结点个数、叶片个数函数的代码，并打印运行结果。涉及的知识点：树的三种递归遍历方法、递归程序设计树的层次遍历算法、队列实验内容：自己编写或粘贴后面附录的源程序，完成树的输入、先序、中序、后序、层次遍历等功能。实验步骤：1. 设计二叉树的表达方法；2. 输入一棵二叉树：要求该树至少包含五个结点，带有一个儿子、两个儿子的结点；3. 编写树的先序、中序、后序遍历的函数，看输出结果，确认树的结构和自己输入的一致；4. 在上一步正确的基础上，运用队列结构，对树进行层次遍历；5. 统计并输出树的结点个数、叶片个数；附录：树的操作的部分源代码：#include #include #define null 0typedef char nodedatatype;typedef struct node nodedatatype data; struct node *lchild,*rchild;bintnode;/* 定义二叉链表结点结构 */typedef bintnode *bintree;/* 定义二叉链表指针类型 */ABCDEF/* 使用已经定义的循环队列*/typedef bintree DataType;typedef int Status;#include SQueue.hcreatebintree(bintree *t) /* 输入二叉树的先序遍历序列*/*（例如上图所示二叉树的先序遍历序列输入为：ABDECF，其中表示空格）*/* 创建二叉链表 */ char ch; if (ch=getchar()= )/* 如果读入空格字符，创建空树 */ *t=null; else *t=(bintnode*)malloc(sizeof(bintnode);/* 申请根结点*t空间 */ (*t)-data=ch;/* 将结点数据ch放入根结点的数据域 */ createbintree(&(*t)-lchild);/* 建左子树 */ createbintree(&(*t)-rchild);/* 建右子树 */ /* end of if */ /* end of creatbintree */preorder(bintree t) /* 对二叉树进行先序遍历 */ if (t) printf(%c,t-data); preorder(t-lchild); preorder(t-rchild); /* end of if */ /* end of preorder */ inorder(bintree t) /* 对二叉树进行中序遍历 */ /* end of inorder */postorder(bintree t) /* 对二叉树进行后序遍历 */ /* end of postorder */error(char *message) /* 出错时，调用的返回出错信息，终止程序运行的函数 */ fprintf(stderr,error:%sn,message); exit(1); leverorder(bintree t) /* 对二叉树进行层次遍历，用到队列 */ SQInit(&myQueue);/*创建队列*/ SQAppend(&myQueue,t);/* 将根结点入队 */ while (!SQIsEmpty(myQueue) /* end of while */ /* end of leverorder */int leave(bintree t) /* 求以t为树根的二叉树的叶子总数 */ leavelist(bintree t) /* 输出以t为树根的二叉树的叶子信息 */ if (t) leavelist(t-lchild);/* 输出左子树中的所有叶子 */ if (t-lchild=null)&(t-rchild=null) /* 若根结点为叶子，则输出叶子的数据域信息 */ printf(%c,t-data); leavelist(t-rchild);/* 输出右子树中的所有叶子 */ /* end of if */ /* end of inorder */int nodes(bintree t) /* 求以t为树根的二叉树的结点总数 */ /* end of node */main()/* 主函数 */ /* 建立二叉树的二叉链表表示，并进行先序遍历、中序遍历、后序遍历和按层次遍历， */ /* 求出所有叶子和结点总数。 */ bintree t=null; int n; printf(please input nodes of bintree:n); createbintree(&t);/* 建立二叉链表 */ printf(the preorder is:); preorder(t);/* 对二叉树t进行先序遍历 */ printf(n); printf(the inorder is:); inorder(t);/* 对二叉树t进行中序遍历 */ printf(nthe postorder is:); postorder(t);/* 对二叉树t进行后序遍历 */ printf(nthe leverorder is:); leverorder(t);/*对二叉树t进行按层次遍历 */ n=leave(t);/* 求出二叉树的叶子数n */ printf(nthe leave of bintree is: %d,n);/* 打印二叉树的叶子总数 */ if (n)/* 当叶子数不为0 */ printf(nthe list of leave is:); leavelist(t);/* 输出所有的叶子 */ else printf(nno leave!);/* 输出无叶子（即空树）信息 */ printf(nthe nodes of bintree is: %dn,nodes(t);/* 输出二叉树的总结点数 */ getchar();/*暂停，任意键继续*/ getchar(); 显示结果如右图所示。实验六 图及其操作预习题：1、 为什么要进行图的遍历？2、 图有几种遍历方法？遍历的结果是惟一的吗？3、 任何一个无向连通图都有生成树吗？4、 一个无向连通图的生成树是惟一的吗？5、 从指定的结点出发，一个无向连通图的深度（广度）优先树是惟一的吗？6、 对于某个图来说，广度优先生成树和深度优先生成树有可能相同吗？实验项目：修改已有的先深、先广遍历程序，求先深、先广遍历生成树实验类型：基础性指导思想：掌握非线性结构的图在程序中的存储方法以及相应的操作实验目的及要求：1、 学会把图转化为程序能识别的邻接矩阵；2、 透彻理解图的两种遍历方法及对应的生成树。涉及的知识点：图的表示法生成树的概念图的深度优先遍历算法图的广度优先遍历算法ABCDEFGH实验内容：自己编写或粘贴后面附录的源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。实验步骤：1问题的描述该程序是对图进行先深、先广遍历，请在此基础上，改为处理指定图，求该图从指定结点出发的先深、先广遍历生成树。实验步骤：1、读懂教师给定的程序或课本的程序；2、输入指定的图；3、把显示遍历序列改为显示先深、先广遍历生成树，要求输出结果是：ABCDEFGH先广遍历生成树ABCDEFGH先深遍历生成树2实验报告的书写：二、实验原理：填写程序改动的方法、依据五、实验过程原始记录：打印与自己改写的源代码相关的程序段，附加注解。六、实验结果及分析：打印屏幕输入、输出结果。注意：除了从顶点1出发之外，再选择另一个结点，即打印两组测试数据（均使用上面指定输入的图）附录：图的深度优先、广度优先遍历/*用邻接矩阵表示的图的深度优先搜索和广度优先搜索*/#include #define maxvertexnum 100/* 设置邻接矩阵的最大阶数 */* 设置图的顶点信息为字符型 */typedef char vertextype;/* 设置边上权值和循环队列数据元素为整型 */typedef int edgetype,DataType,Status;/*用已定义的循环队列头文件SQueue.h */#include SQueue.htypedef struct vertextype vexsmaxvertexnum;/* 图的顶点信息表 */ edgetype edgesmaxvertexnummaxvertexnum;/* 图的邻接矩阵 */ int n,e;/* 图的顶点数和边数 */ mgraph;/* 图的邻接矩阵表示结构定义 */typedef enumFALSE,TRUEboolean;boolean visitedmaxvertexnum;/* 顶点访问标记向量 */main()/* 主函数 */ /* 建立用邻接矩阵表示的图，并进行深度优先搜索和广度优先搜索 */ mgraph *g;char anychar; g=(mgraph*)malloc(sizeof(mgraph);/* 申请图g的邻接矩阵表示空间 */ createmgraph(g);/* 建立图g */ printf(the dfs is:);/* 对图g进行深度优先搜索 */ dfstraverse(g); printf(the bfs is:);/* 对图g进行广度优先搜索 */ bfstraverse(g); printf(Press any key to continue.); scanf( %c,&anychar); createmgraph(mgraph *g) /* 建立图g的邻接矩阵表示 */ int i,j,k,w; int flag; printf(nPlease select which graphic that you want to creat:n); printf(digragh-0n); printf(undigragh-1n); scanf(%d,&flag); printf(Please input Number of Vertex,Edge:n); scanf(%d,%d,&g-n,&g-e);/* 输入图*g的顶点数和边数 */ printf(input the infomation of Vertexs:n); for(i=0;in;i+) /* 输入n个顶点的信息 */ /* %c前添加空格，在接收单字符时可清除缓冲区中的空格和回车 */ scanf( %c,&(g-vexsi); for(i=0;in;i+)/* 将邻接矩阵数组初始化 */ for(j=0;jn;j+) g-edgesij=0; for(k=0;ke;k+) /* 读入n有向边对应的三元组(i,j,w),若构造有向图， */ /* i为有向边的弧尾，j是有向边的弧头， */ /* w是有向边的权值（建立一般的有向图时，可输入1） */ printf(input i,j,w:n); scanf(%d,%d,%d,&i,&j,&w); g-edgesij=w; if (flag)/* 构造无向图，即为对称矩阵 */ g-edgesji=w; dfsm(mgraph *g,int i) /* 对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索 */ int j; printf(visit vertex:%c ,g-vexsi);/* 访问序号为i的顶点 */ visitedi=TRUE;/* 将序号为i的顶点设置访问过标记 */ for(j=0;jn;j+)/* 扫描邻接矩阵的第i行，做以下操作 */ if (g-edgesij!=0)&(!visitedj) /* 寻找序号为i的顶点的未访问过的邻接点(设序号为k), */ dfsm(g,j);/* 以序号为k的顶点为出发点进行深度优先搜索 */ /* end of dfsm */dfstraverse(mgraph *g) /* 对以邻接矩阵表示的图，进行深度优先搜索 */ int i; for(i=0;in;i+)/* 将图的所有顶点设置为未访问过 */ visitedi=FALSE; for(i=0;in;i+)/* 对图*g进行深度优先搜索 */ if(!visitedi) dfsm(g,i); printf(n); /* end of dfstraverse */bfsm(mgraph *g,int k) /* 对以邻接矩阵表示的图，以序号为k的顶点作为出发点进行广度优先搜索 */ int i,j; SQueue myQueue; SQInit(&myQueue);/* 创建循环队列myQueue */ printf(visit vertex:%c ,g-vexsk);/* 访问序号为k的顶点 */ visitedk=TRUE;/* 将序号为k是结点设置为已访问过 */ SQAppend(&myQueue, k);/* 将序号为k的顶点入队 */ while(!SQIsEmpty(myQueue)/* 若队列不为空，则做以下操作 */ SQDelete(&myQueue, &i); /* 将队首元素(序号为i的顶点)出队 */ for(j=0;jn;j+)/* 寻找序号为i顶点的邻接点，并做如下处理 */ if(g-edgesij!=0)&(!visitedj)/* 若序号为i的顶点有未访问过邻接点 */ printf(visit vertex:%c ,g-vexsj);/* 访问序号为j的顶点 */ visitedj=TRUE;/* 设置序号为j的顶点访问过标记 */ SQAppend(&myQueue, j); /* 将序号为j的顶点入队 */ /* end of if */ /* end of for */ /* end of bfsm */bfstraverse(mgraph *g) /* 对以邻接矩阵表示的图，进行广度优先搜索 */ int i; for(i=0;in;i+)/* 将所有顶点设置为未访问过 */ visitedi=FALSE; for(i=0;in;i+)/* 对邻接矩阵表示的图进行广度优先搜索 */ if(!visitedi) bfsm(g,i); pr