哈工程数据结构实验报告八系

1、实 验 报 告课程名称数据结构实验项目名称1单链表的实现与应用2堆栈的实现与应用3排序、查找算法的实现与应用实验类型基本型 / 基本型 / 综合型实验学时2 / 2 / 4班级学号姓名指导教师实验室名称实验时间20171127 / 1127 / 1204实验成绩编号过程表现预习部分实验报告小计总成绩123教师签字日期哈尔滨工程大学本科生院制实验1 单链表的实现与应用-【预习部分】一、实验目的通过编程实验，进一步增强对单链表的理解和掌握。二、实验要求编写程序实现单链表的基本操作（初始化、撤销、插入、删除、取数据元素、求数据元素个数），并设计测试数据，能全面地测试所设计程序的功能。三、实验原理1.

2、单链表结构线性表是一种可以在任意位置插入和删除数据元素操作、由n(n0)个相同类型数据元素a0, a1, an-1组成的线性结构。单链表是线性表的一种。而单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点是逻辑上相邻的数据元素在物理上不一定相邻。2.单链表数据插入原理要在带头结点的单链表第i（0 i size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q->data = x），最后修改新结点的指针域指向ai结点（即q->next =

3、 p->next），并修改ai-1结点的指针域指向新结点q（即p->next = q）。循环条件由两个子条件逻辑与组成，其中子条件p->next != NULL保证指针所指结点存在，子条件j < i - 1保证最终让指针p指向ai-1结点。3.单链表数据删除原理要在带头结点的单链表中删除第i（0 i size - 1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s = p->next），并把数据元素ai的值赋予x（即*x = s->data），最后把ai结点脱链（即p->next = p->next-&

4、gt;next），并动态释放ai结点的存储空间（即free(s)）。删除过程如图2-14所示。图中的对应算法中的删除语句。四、实验环境Visual Studio 2010-五、实验步骤（程序代码）/ 5555.cpp : 定义控制台应用程序的入口点/#include "stdafx.h"int _tmain(int argc, _TCHAR* argv)return 0;#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef int DataType;typedef

5、struct Node DataType data; struct Node *next; SLNode;void ListInitiate(SLNode *head) *head = (SLNode *)malloc(sizeof(SLNode);(*head)->next = NULL;void Destroy(SLNode *head) SLNode *p, *p1;p = *head; while(p != NULL) p1 = p; p = p->next;free(p1); *head = NULL;int ListInsert(SLNode *head, int i,

6、 DataType x) SLNode *p, *q; int j;p = head; j = -1; while(p->next != NULL && j < i - 1) p = p->next; j+; if(j != i - 1) printf("插入位置参数错！");return 0; q = (SLNode *)malloc(sizeof(SLNode); q->data = x; q->next = p->next; p->next = q; return 1;int ListDelete(SLNode

7、 *head, int i, DataType *x) SLNode *p, *s; int j;p = head; j = -1; while(p->next != NULL && p->next->next!= NULL && j < i - 1) p = p->next;j+; if(j != i - 1)printf("插入位置参数错！");return 0;s = p->next; *x = s->data; p->next = p->next->next; free(s)

8、; return 1;int ListGet(SLNode *head, int i, DataType *x) SLNode *p; int j;p = head; j = -1; while(p->next != NULL && j < i) p = p->next;j+; if(j != i) printf("取元素位置参数错！");return 0; *x = p->data; return 1; int ListLength(SLNode *head)SLNode *p = head;int size = 0;while(p

9、->next != NULL)p = p->next;size +;return size; void main(void) SLNode *head; int i , x;ListInitiate(&head); for(i = 0; i < 10; i+) ListInsert(head, i, i+1) ; for(i = 0; i < ListLength(head); i+) ListGet(head, i, &x); printf("%d ", x); printf("n", x); ListDelet

10、e(head, 6, &x) ; for(i = 0; i < ListLength(head); i+) ListGet(head, i, &x); printf("%d ", x); Destroy(&head); 六、实验结果实验结果如下：主程序实现的功能为：建立一个线性表，首先依次输入数据元素1，2，3，10，然后删除数据元素7，最后依次显示当前线性表中的数据元素。由实验结果可知，实验程序正确执行了功能。七、分析与总结单链表和顺序表相比，主要优点是不需要预先确定数据元素的最大个数，插入和删除操作不需要移动数据元素；主要缺点是查找数据元素

11、时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。经过本次实验，我掌握了单链表的基本操作初始化、撤销、插入、删除、取数据元素、求数据元素个数等，提高了自己的编程能力。实验2 堆栈的实现与应用-【预习部分】一、实验目的通过编程实验，进一步增强对堆栈的理解和掌握。二、实验要求编写程序实现顺序堆栈的基本操作（初始化、非空否、入栈、出栈、取栈顶数据元素），并设计测试数据，能全面地测试所设计程序的功能。三、实验原理1.顺序堆栈结构堆栈定义为限定只能在固定一端进行插入和删除操作的线性表。其特点是后进先出。允许进行

12、插入和删除操作的一端称为栈顶，另一端称为栈底。它的作用是可以完成从输入数据序列到某些输出数据序列的转换。顺序堆栈是顺序存储结构的堆栈。顺序栈的存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。2.数据集合a0,a1,an-1ai的数据类型为DataType。3操作集合 (1) StackInitiate(S) ：初始化堆栈 (2) StackNotEmpty(S)：堆栈S非空否 (3) StackPush(S, x) ：入栈 (4) StackPop(S, d)：出栈 (5) StackTop(S, d)：取栈顶数据元素四、实验环境Visual Studio 2010-五、实

13、验步骤（程序代码）/ 5555.cpp : 定义控制台应用程序的入口点/#include "stdafx.h" int _tmain(int argc, _TCHAR* argv)return 0;#include <stdio.h>#include <stdlib.h>#define MaxStackSize 100typedef int DataType;typedef struct DataType stackMaxStackSize; int top; SeqStack;void StackInitiate(SeqStack *S)S->

14、;top = 0;int StackNotEmpty(SeqStack S) if(S.top <= 0)return 0; else return 1;int StackPush(SeqStack *S, DataType x) if(S->top >= MaxStackSize) printf("堆栈已满无法插入！n"); return 0; else S->stackS->top = x; S->top +; return 1; int StackPop(SeqStack *S, DataType *d) if(S->top

15、<= 0) printf("堆栈已空无数据元素出栈!n"); return 0; else S->top -;*d = S->stackS->top; return 1; int StackTop(SeqStack S, DataType *d) if(S.top <= 0) printf("堆栈已空!n"); return 0; else *d = S.stackS.top - 1; return 1; void main(void) SeqStack myStack; int i , x; StackInitiate(&

16、amp;myStack); for(i = 0; i < 10; i+) StackPush(&myStack, i+1); StackTop(myStack, &x); printf("当前栈顶数据元素为:%dn,x"); printf("依次出栈的数据元素序列如下:n"); while(StackNotEmpty(myStack) StackPop(&myStack, &x); printf("%d ", x); 六、实验结果主程序实现的功能为：建立一个顺序堆栈，首先依次输入数据元素1, 2,

17、 3,.,10，然后依次出栈堆栈中的数据元素并显示。实验结果如下：由实验结果可知，实验程序正确执行了功能。七、分析与总结顺序堆栈与链式堆栈的主要区别在于，顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用光而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用；而对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间开始，另外当某个项不使用时也可将内存返还给系统。经过本次实验，我掌握

18、了顺序堆栈的基本操作始化、非空否、入栈、出栈、取栈顶数据元素等，进一步提高了自己的编程能力。实验3 排序、查找算法的实现与应用-【预习部分】一、实验目的通过编程实验，进一步增强对排序、查找算法的理解和掌握。二、实验要求（1）在 0,999 区间内，随机生成N个整数（N >= 20）；（2）编程实现一种排序算法，对这N个数据进行递增排序；（3）编程实现一种查找算法，在已排序的数据序列中查找指定数据。 三、实验原理1.排序原理排序是对数据元素序列建立某种有序排列的过程,是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。主要有以下几种排序方法：交换排序的基本思想是利用交换数据元素的位

19、置进行排序的方法。插入排序的基本思想是每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适当位置上，直到数据元素全部插入为止。选择排序的基本思想是是每次从待排序的数据元素集合中选取关键字最小（或最大）的数据元素放到数据元素集合的最前（或最后），数据元素集合不断缩小，当数据元素集合为空时选择排序结束。归并排序主要是二路归并排序,基本思想是可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 én / 2ù 个长度为 2 的有序子序列 ；再做两两归并，如此重复，直到最后得到一个长度为 n 的有序序列。2.查找

20、原理查找是查询某个关键字是否在(数据元素集合）表中的过程，也称作检索。常用的一种算法为二分查找（又称折半查找）。算法的基本思想是先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素值相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。四、实验环境Visual Studio 2010-五、实验步骤（程序代码）/ paixu.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#include <stdlib.h>#include

21、<time.h>int b20;int SelectSort(int b, int n)int i, j, small;int temp;for(i = 0; i < n-1; i+) small = i; /设第i个数据元素关键字最小 for(j = i+1; j < n; j+)/寻找关键字最小的数据元素 if(bj < bsmall) small=j; /记住最小元素的下标 if(small != i)/当最小元素的下标不为i时交换位置 temp = bi; bi = bsmall; bsmall = temp; for(i=0;i<n;i+)prin

22、tf("%d",bi);printf(" ");return 1;int BiSearch(int b, int n, int key) int low = 0, high = n - 1;/确定初始查找区间上下界 int mid;while(low <= high) mid = (low + high)/2;/确定查找区间中心下标 if(bmid = key) return 1;/查找成功 else if(bmid < key) low = mid + 1; else high = mid - 1; return 0;/查找失败int random(int n)int i,a;srand(unsigned int)time(NULL); /当前时间作种子，每次都不同for(i=0;i<n-1;i+)a = rand(); /生成032767之间的一个数值a=a/200;bi=a;printf("%d",bi);printf(&