《数据结构》实验报告doc.doc

《《数据结构》实验报告doc.doc》由会员分享，可在线阅读，更多相关《《数据结构》实验报告doc.doc（32页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构 实验报告 20 20 学年第一学期 班 级 姓 名学 号指导教师实验一 单链表的建立、删除和插入一、实验学时2学时。二、实验类型验证类型。三、实验目的了解单链表的结构特点，描述方法及有关概念，掌握单链表建立、插入、删除的基础操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备1、复习有关单链表的有关概念及结点结构定义；2、复习在单链表的建立算法、删除结点和插入结点的算法。六、实验内容建立一个包括头结点和5个结点(5,4,3,2,1)的单链表，实现单链表建立的基础操作。在链表的第2个元素之前插入一个结点，实现单链

2、表插入的基础操作。删除链表中的第3个元素的结点，实现单链表删除的基础操作。七、实验方法及步骤 单链表的结点结构定义（见课本P28）： typedef struct LNode int data; struct LNode *next;LNode,*LinkList;（1）本实验采用从表尾到表头逆向建立单链表的算法(见课本P30)。步骤：先建立头结点，然后建立an结点，再在an结点之前建立an-1结点，再在an-1结点之前建立an-2结点，依次类推，最后建立a1结点。LNode *CreateList(int n) /* 算法2.11 */ /* 逆位序(插在表头)输入n个元素的值，建立带表头结

3、构的单链线性表L */ int i; LinkList p; L=(LinkList)malloc(sizeof(struct LNode); L-next=NULL; /* 先建立一个带头结点的单链表 */ printf(请输入%d个数据n,n); for(i=n;i0;-i) p=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */ scanf(%d,&p-data); /* 输入元素值 */ p-next=(*L)-next; /* 插入到表头 */ L-next=p; return L; （2）在带头结点的单链线性表L中第i个位置之前插入

4、元素e步骤：首先要找到第i个结点，然后修改指针的指向才能实现插入。关键的语句：s-next=p-next; p-next=s;LNode *Insert(LinkList L,int i,int e)/*在带头结点的单链线性表L中第i个位置之前插入元素e*/ LinkList p=L,q,s; int j=0; while(p&jnext; +j; if(!p|ji-1) return L; /*假如i小于1或者大于表长，则不插入结点，返回原链表*/ s=(LinkList)malloc(sizeof(struct LNode); s-data=e; s-next=p-next; p-next

5、=s;return L;（3）在带头结点的单链线性表L中，删除第i个元素，并由e返回其值。步骤：首先要找到插入位置，然后修改指针，才能插入到链表中去。关键语句： q=p-next; p-next=q-next;LNode *Del(LinkList L,int i,int *e)/*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/LinkList p=L,q; int j=0; while(p-next&jnext; +j; if(!(p-next)|ji-1) return L; /* 删除位置不合理,则不删除链表中的元素，直接返回原链表 */ q=p-next; p-next

6、=q-next; *e1=q-data; free(q); return L;八、程序及实验结果 （1）程序（2）实验结果成绩 指导教师签名 实验二 栈的建立、插入和删除一、实验学时2学时。二、实验类型验证类型。三、实验目的了解顺序栈的结构特点，描述方法及有关概念，掌握顺序栈的建立、插入、删除的基础操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备1、复习栈的有关概念；2、复习栈的建立、插入和删除的有关算法。六、实验内容建立一个顺序栈，实现顺序栈建立的基础操作。在顺序栈的栈顶插入一个元素，实现顺序栈插入的基础操作。删除

7、顺序栈中的栈顶的一个元素，实现顺序栈删除的基础操作。七、实验方法及步骤顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。对于顺序栈，为了方便操作，需要设定两个常量：STACK_INIT_SIZE(存储空间初始分配量)和STACKINCREMENT(存储空间分配增量)，并以下述类型说明作为顺序栈的定义(见课本P46)。typedef structchar *base; char *top; int stacksize;SqStack；步骤：（1）函数Initstack()实现顺序栈的初始化，即构造一个空栈。（2）

8、函数Push()实现在顺序栈中，插入一个元素e成为新的栈顶元素。（3）函数Pop()实现在顺序中，删除栈中栈顶元素，并用返回其值。（4）在主函数中分别调用这几个函数，即可完成要求。八、程序及实验结果 （1）程序（2）实验结果成绩 指导教师签名 实验三 队列的建立、插入和删除一、实验学时2学时。二、实验类型验证类型。三、实验目的了解队列的结构特点，描述方法及有关概念，掌握队列建立、插入、删除的基本操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备1、复习链队列的有关概念；2、复习链队列的建立、插入和删除算法。六、实验内容

9、建立一个由五个元素（a,b,c,d,e）组成的链队列,实现队列建立的基本操作。在队列中再插入一个元素f，实现队列插入的基本操作。在队列删除一个元素，实现队列删除的基本操作。七、实验方法及步骤队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。/*单链队列-队列的链式存储结构*/(见课本P61)typedef struct QNode char data; struct Qnode *next;Qnode,*QueuePtr;typedef struct QueuePtr front;/*队头指针*/ Queue

10、Ptr rear; /*队尾指针*/LinkQueue;步骤：（1）函数InitQueue()是构造一个空队列。（2）函数EnQueue()是在插入元素e为Q的新的队尾元素。（3）函数DeQueue()的作用是若队列不空时，则删除Q的队头元素，用e返回。（4）在主函数中分别调用这几个函数，即可完成要求。八、程序及实验结果 （1）程序（2）实验结果 成绩 指导教师签名 实验四 模式串的匹配一、实验学时3学时。二、实验类型验证类型。三、实验目的了解串的特点，描述方法及有关概念，掌握串的模式匹配算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.

11、0。五、实验准备1、模式匹配子串的定位操作通常称为串的模式匹配。它是各种串处理系统中最重要的操作之一。 2、模式匹配的算法基本思想从主串S的第pos 个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为零。 改进的模式匹配算法：每一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能的一段距离后，继续进行比较

12、。在改进的模式匹配算法(KMP算法)中，当匹配过程中产生“失配”时，指针i不变，指针j退回到nextj所指示的位置上重新进行比较，并且当指针j退至零时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1字符重新进行匹配。六、实验内容已知主串s1为aaabaaaab，子串s2为aaaab，求子串s2在主串s1中的位置。七、实验方法及步骤在改进的模式匹配算法(KMP算法)中，需要用next和nextval数组存放课本中的next和nextval的值。步骤：（1）函数StrAssign(SString T,char *chars)是生成一个其值等于chars的主

13、串T。（2）函数StrLength(SString S) EnQueue()是返回子串S的元素个数。（3）函数get_next(SString T,int next)的作用是求模式串T的next函数修正值并存入数组nextval。（4）函数void get_nextval(SString T,int nextval)的作用是求模式串T的next函数修正值并存入数组nextval。（5）Index_KMP(SString S,SString T,int pos,int next)的函数据作用是利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。（4）在主函数中分别调用这

14、几个函数，即可完成要求。八、程序及实验结果 （1）程序（2）实验结果 成绩 指导教师签名 实验五 稀疏矩阵的转置 一、实验学时2学时。二、实验类型验证类型。三、实验目的了解称疏矩阵的结构特点，描述方法及有关概念，掌握稀疏矩阵转置的操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备稀疏矩阵可由表示非零元的三元组及其行列数惟一确定。假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式，称之为三元组顺序表。/-称疏矩阵的三元组顺序表存储表示-/#define MAX_SIZE 100 /* 非零元个数的最大值

15、*/ typedef struct int i,j; /* 行下标,列下标 */ ElemType e; /* 非零元素值 */ Triple; typedef struct Triple dataMAX_SIZE+1; /* 非零元三元组表，data0未用 */ int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */ TSMatrix;在此，data域中表示非零元的三元组是以行序为主序顺序排列的，这样做的目的是将有利于进行某些矩阵运算。按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。如果能预先确定矩阵M中每一列(即T中每一行)的第一个非零元在b.d

16、ata中应有的位置，那么对对a.data中的三元组依次作转置时，便可直接放到b.data中恰当的位置上去。为了确定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。在此，需要附设num和cpot两个向量。numcol表示矩阵M中第col列中非零元的个数，cpotcol指示M中第col列的第一个非零元在b.data中的恰当位置。显然有根据上面的思想，可以实现稀疏矩阵的快速转置的算法。六、实验内容已知稀疏矩阵A给出了非零元素，要求将稀疏矩阵A快速转置成稀疏矩阵B。稀疏矩阵A的内容见课本P98页。七、程序及实验结果（1）程序（2）实验结果

17、成绩 指导教师签名 实验六 二叉树的操作一、实验学时2学时。二、实验类型验证类型。三、实验目的了解二叉树的链式存储结构特点，描述方法及有关概念，掌握二叉树的建立和遍历操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备遍历二叉树是按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1) 访问根结点；(2) 先序遍历左子树；(3) 先序遍历右子树。六、实验内容按照一个先序序列建立二叉树的二叉链表(ABC DE G F ,见课本P131页)，然

18、后再先序遍历这棵二叉树，请编程实验。七、程序及实验结果（1）程序（2）实验结果 成绩 指导教师签名 实验七 图的最小生成树一、实验学时4学时。二、实验类型验证类型。三、实验目的了解图的存储结构特点，描述方法及有关概念，掌握图的最小生成树操作的算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备图的最小生成树就是此图构造的生成树的权值之和最小。构造最小生成树可以有两种方法：普里姆算法和克鲁斯卡尔算法。本程序是采用普里姆算法来实现求最小生成树。在主程序中，首先构造无向网，然后调用MiniSpanTree_PRIM(),由顶点V1

19、开始，求该网的最小生成树。这样，最小生成树顶点集最初只有V1，其中用到了辅助数组closedge。closedgei.lowcost是最小生成树顶点集中的顶点到i点的最小权值。若i点属于最小生成树，则closedgei.lowcost=0。closedgei.adjvex是最小生成树顶点集中到i点为最小权值的那个顶点。六、实验内容利用普里姆算法，构造课本P174页的图的最小生成树。在程序运行的过程中，要输入的内容很多(下划线表示的内容)。请输入无向网G的顶点数，边数，边是否含其它信息(是：1，否：0)：6,10,0请输入6个顶点的值(3个字符)：v1 v2 v3 v4 v5 v6请输入10条边

20、的顶点1 顶点2 权值(以空格作为间隔)：v1 v2 6v1 v3 1v1 v4 5v2 v3 5v2 v5 3v3 v4 5v3 v5 6v3 v6 4v4 v6 2v5 v6 6此程序可用Turbo C或VC进行调试。用VC进行调试可以看到它的中文文字效果。七、程序及实验结果（1）程序（2）实验结果成绩 指导教师签名 实验八 有序表的查找一、实验学时2学时。二、实验类型验证类型。三、实验目的了解静态查找表的顺序存储结构特点，描述方法及有关概念，掌握有序表的查找的操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备了解

21、静态查找表的顺序存储结构和折半查找的特点，并能独立写出折半查找算法。六、实验内容定义一个结构体数组ElemType rN=5,13,19,21,37,56,64,75,80,88,92，然后输入一个要查找的整数，对这个数组进行折半查找来查询这个元素是否在这个数组中。为了能利用课本的某些函数，仍定义ElemType为结构体，其中只有一个成员，就是其关键字key。typedef int KeyType; /* 设关键字域为整型 */ typedef struct KeyType key; /* 仅有关键字域 */ ElemType; /* 数据元素类型 */七、程序及实验结果（1）程序（2）实验结

22、果成绩 指导教师签名 实验九 直接插入排序一、实验学时2学时。二、实验类型验证类型。三、实验目的了解内部排序结构特点，描述方法及有关概念，掌握直接插入排序操作算法。四、需用仪器、设备奔腾及以上微机；安装了Windows 2000/xp操作系统和VC6.0或TC2.0。五、实验准备直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r1.i-1中插入一个记录ri后，变成含有i个记录的有序子序列r1.i；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r0处设置监

23、视哨。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。为待排记录建立如下的结构体(见课本P264)： typedef struct KeyType key; /* 关键字项 */ InfoType otherinfo; /* 其它数据项，具体类型在主程中定义 */ RedType; /* 记录类型 */ typedef struct RedType rMAX_SIZE+1; /* r0闲置或用作哨兵单元 */ int length; /* 顺序表长度 */ SqList; /* 顺序表类型 */六、实验内容定义一个结构体数组：RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8，然后再对这个结构体数组中的元素进行直接插入排序，请编程实现。七、程序及实验结果（1）程序（2）实验结果成绩 指导教师签名 - 32 -