数据结构课程设计.ppt

《数据结构课程设计.ppt》由会员分享，可在线阅读，更多相关《数据结构课程设计.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计数据结构课程设计实验一实验一 线性表线性表实验二实验二 堆栈与队列堆栈与队列实验三实验三 二叉树的遍历二叉树的遍历实验四实验四 图遍历的演示图遍历的演示实验五实验五 查找与排序查找与排序共10学时 实验一实验一 线性表线性表 实验目的实验目的 1了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。2了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。实验内容实验内容2单链表的实践。1顺序表的实践。顺序表的实践顺序表的实践1)建立4个元素的顺序表list=2，3，4，5，实现顺序表建立的基本操作。2)在list=2，3，4，5的元素4和

2、5之间插入一个元素9，实现顺序表插入的基本操作。3)在list=2，3，4，9，5中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。单链表的实践单链表的实践1)建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。2)在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。3)在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。实验要点及说明实验要点及说明线性表（linearlist）是n（n0）个数据元素a1，a2，an组成的有限序列。其中n称为数据元素的个数或线性表的长度，当

3、n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，,an），其中的数据元素ai（1in）是一个抽象的符号，ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。可用C语言描述为:#

4、defineLIST_SIZE100/LIST-SIZE表示线性表允许的最大长度Typedefintelemtype;TypedefstructelemtypedataLIST-SIZE+1;/表示线性表intlen;/len表示线性表的实际长度sqlist；若将前面线性表的顺序存储结构类型中的数组形式改为指针形式，则得到动态分配形式如下：structsqlistelemtype*data;intlen;线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及它在内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不

5、一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问。常用的链表有单链表、循环链表和双向链表、多重链表等。单链表是线性表的链式存贮结构中每个结点只有一个指针域的链表。单链表可用描述为:typedefstructLnodeelemtypedata;/用来存放结点本身信息元素类型structLnode*next;/指针类型,存放下一个元素地址Lnode;TypedefLnode*linklist;重点：重点：单链表的建立是非常重要的一个程序，和实验二中栈的建立与队列的建立有密切的关系。实验二实验二 栈与队列栈与队列实验目的实验目的1了解顺序栈的结构特点及有关概

6、念，掌握顺序栈建立及入栈的基本操作。2了解顺序栈共用的含义及优点，掌握顺序栈的基本操作。实验内容实验内容 进行顺序栈初始化及入栈、出栈，实现顺序栈建立及入栈、出栈的基本操作。特点：特点：根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。栈的运算：栈的运算：1.初始化栈：Voidinitstack(s)将栈S置为一个空栈(不含任何元素)。2.进栈：VoidPush(&s,x)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”

7、。3.出栈：elemtypePop(&s)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：Elemtypegettop(s)取栈S中栈顶元素。5.判栈空：Intempty(s)判断栈S是否为空，若为空，返回值为1，否则返回值为0。6.置空栈：voidclearstack(&s)顺序栈的数据类型：顺序栈的数据类型：#definestacksize100Typedefintelemtype;typedefStructelemtypedatastacksize+1;inttop;/:指向栈顶位置的指针sqstack;运行界面：运行界面：队列的实现队列的实现 实验目的实验目的

8、 1了解顺序队列的结构特点及有关概念，掌握顺序队列建立及入队列的基本操作。2了解顺序队列共用的含义及优点，掌握顺序队列的基本操作。队列的定义队列的定义:队列是一种线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。链队列存储表示：链队列存储表示：typedefstructQNodeQElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;实验三实验三 二叉树

9、的遍历二叉树的遍历实验目的实验目的学习掌握二叉树各种遍历方法的基本操作算法。实验要点及说明实验要点及说明由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。二叉树的遍历按访问根结点的先后次序不同分为前序、中序和后序三种。实验要求与步骤实验要求与步骤基本要求：采用递归算法实现前序、中序和后序遍历；实现提示：二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次；测试数据：此时，数据类型可

10、描述如下：typedef struct btreenodeint data;struct btreenode*lchild;struct btreenode*rchild;bnode;实验四实验四 图遍历的演示图遍历的演示实验目的实验目的学习掌握图的两种搜索路径的遍历。实验内容实验内容 试写一个程序，演示在连通的无向图上遍历全部结点的操作。实验要点及说明实验要点及说明深度优先搜索遍历图的算法广度优先搜索遍历图的算法深度优先搜索遍历图的算法深度优先搜索遍历图的算法首先访问指定的起始顶点v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后

11、从w2出发，访问w2的一个未被访问过的邻接顶点w3，依次类推，直到一个所有邻接点都被访问过为止。广度优先搜索遍历图的算法广度优先搜索遍历图的算法首先访问指定的起始顶点v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，wk，然后再依次从w1，w2，wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。实验要求与步骤实验要求与步骤基本要求：基本要求：采用邻接表或邻接矩阵作存储结构，实现连通无向图的深度优先搜索遍历和广度优先搜索遍历。测试数据：测试数据：要求画出该图的邻接表或邻接矩阵。实现提示：实现提示：采用邻接表或邻接矩阵作存储结构。

12、constintn=maxn；/图中顶点数constinte=maxe；/图中边数structgraphelemtypeVn+1;/存放顶点信息v1,v2,.vn，不使用v0存储空间intarcsn+1n+1/邻接矩阵;图的邻接矩阵数据类型描述如下图的邻接矩阵数据类型描述如下:constintn=maxn；/maxn表示图中最大顶点数constinte=maxe；/maxe图中最大边数structlink/定义链表类型elemtypedata;link*next;structnode/定义邻接表的表头类型elemtypev;/顶点信息link*next;an+1;图的邻接表数据类型描述如下：图

13、的邻接表数据类型描述如下：算法：算法：深度优先搜索遍历图的算法：p169广度优先搜索遍历图的算法：p170从键盘输入图：inputnode:6node0=1node1=2node2=3node3=4node4=5node5=6Insertedgei-j:02Insertedgei-j:01Insertedgei-j:14Insertedgei-j:13Insertedgei-j:34Insertedgei-j:45Insertedgei-j:52Insertedgei-j:-11结果：dfs:124563实验五实验五 查找与排序查找与排序实验目的实验目的学习掌握查找的过程及方法。学习掌握各种排

14、序方法的排序过程及其实现算法。实验内容实验内容1、实现顺序查找，在输入的数组纪录中顺序查找所需的纪录。2、用二分查找，也称折半查找方法，对已知的有序序列进行查找。实验要点及说明实验要点及说明 顺顺序序查查找找是一种简单的查找方法。从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。二二分分查查找找是一种高效率的查找方法。但二分查找有条件限

15、制：要求表必须用向量作存贮结构，且表中元素必须按关键字有序(升序或降序均可)。基本思想是：首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较，若相等，则查找成功；否则，若Rmid.keyk，则在R1到Rmid-1中继续查找，若有Rmid.keyk，则在Rmid+1到Rn中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。顺序查找算法实现顺序查找算法实现constintn=maxn/n为表的最大长度structnodeelemtype key;/key为关键字

16、，类型设定为elemtype;intseqsearch(nodeRn+1,elemtypek)/在表中查找关键字值为的元素R0.key=k;inti=n;/从表尾开始向前扫描while(Ri.key!=k)i-;returni;二分查找算法实现二分查找算法实现intbinsearch(nodeRn+1,elemtypek)intlow=1,high=n;while(lowk)high=mid-1;/在左子区间中查找elselow=mid+1;/在右子区间中查找return0;/查找失败实验内容实验内容 实现常用的内部排序算法并进行比较：起泡排序、直接插入排序、简单选择排序、快速排序。试通过随机

17、数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。实验要点及说明实验要点及说明起泡排序的基本思想是：将待排序列中第一个记录的关键字R1.Key与第二个记录的关键字R2.Key作比较，如果R1.Key大于R2.Key，则交换记录R1和R2在序列中的位置，否则不交换；然后继续对当前序列中的第二个记录和第三个记录作同样的处理，依次类推，直到序列中倒数第二个记录和最后一个记录比较完为止。直接插入排序直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序直接插入排序简单选择排序简单选择排序 简单选择排序：一趟

18、简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1in）个记录交换之。一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1in）个记录交换之。快速排序方法的基本思想是：从待排序列的n个记录中任意选取一个记录Ri（通常选取序列中的第一个记录）作标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri.Key，排在Ri后面的记录的关键字都大于Ri.Key。快速排序方法快速排序方法 实验要求与步骤实验要求与步骤基本要求：待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。4个算法至少选作2个。实验要求与步骤实验要求与步骤基本要求：基本要求：选作其中一个。实现提示：实现提示：主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如正序、逆序和不同程度的乱序。注意采用分块调试的方法；测试数据：测试数据：例如：初始序列645789624。可以由同学们自己给出。