《数据结构》实验报告
专业计算机科学与技术
班级
姓名
学号
学期
指导老师
成绩：
教师评语：
数据结构上机实验报告
学号：姓名：所在系：计算机科学与技术班级：
实验名称：线性结构基本算法的实现（2）实验日期2018.09.28
实验指导教师实验机房
------------------------------------------------------------------------------------------------------
1. 实验目的：
(1) 掌握线性表顺序存储结构的基本操作：插入、删除、查找；
(2) 掌握线性表链式结构的基本操作：插入、删除、合并等运算；
(3)掌握栈和队列基本运算的算法；
2. 实验内容：
（1）实现顺序表的创建、插入、删除和查找的操作；
（2）实现单链表插入、删除、合并的操作；
（3）实现2个有序线性表的合并；
（4）利用顺序栈实现数制转换的算法；
（5）实现顺序队列各种基本运算的算法；
（6）实现链栈各种基本运算的算法；（选做）
（7）实现链队列各种基本运算的算法；（选做）
3．算法设计（编程思路或流程图或源代码）
内容：
4）顺序队列的入队、出队和取队头元素的操作
设计思路：
1、定义结构体SqQueue来表示顺序队列，其中front和rear分别指向队列的头和尾。
2、实现函数int initSqQueue(SqQueue* s)、int appendQueue(SqQueue* s, Elemtype e)、
int isEmpty(SqQueue* s)、int deleteQueue(SqQueue* s, Elemtype &e)、Elemtype getHead(SqQueue* s)、void displayQueue(SqQueue* s)、void createQueue(SqQueue* s)分别实现队列的初始化、创建、入队、出队、判断队列是否为空、取头元素、遍历队列等操作。
3、在main函数中用while（）循环对不同的操作进行判断，以测试不同的函数
源代码：
1.#include
2.#include
3.#define MAXNUM 100
4.#define Elemtype int
5.#define TRUE 1
6.#define FALSE 0
7.typedef struct {
8. Elemtype* base;
9.int front;
10.int rear;
11.}SqQueue;
12.//初始化一个空队列
13.int initSqQueue(SqQueue* s) {
14. s->base = (Elemtype*)malloc(sizeof(Elemtype)*MAXNUM);
15.if (!s->base) {
16.return FALSE;
17. }
18. s->front = s->rear = 0;
19.return TRUE;
20.}
21.//入队列操作
22.int appendQueue(SqQueue* s, Elemtype e) {
23.if ((s->rear + 1) % MAXNUM == s->front) {
24.return FALSE;
25. }
26. s->base[s->rear] = e;
27. s->rear=(s->rear + 1) % MAXNUM;
28.return TRUE;
29.}
30.//判断队列是否为空
31.int isEmpty(SqQueue* s) {
32.if (s->rear == s->front) {
33.return TRUE;
34. }
35.else {
36.return FALSE;
37. }
38.}
39.//出队列操作
40.int deleteQueue(SqQueue* s, Elemtype &e) {
41.if (isEmpty(s)) {
42.return FALSE;
43. }
44. e = s->base[s->front];
45. s->front = (s->front + 1) % MAXNUM;
46.return TRUE;
47.}
48.//获取头元素
49.Elemtype getHead(SqQueue* s) {
50.if (isEmpty(s)) {
51. printf("队列空，没有头元素！\n");
52.return 0;
53. }
54.return s->base[s->front];
55.}
56.//遍历队列
57.void displayQueue(SqQueue* s) {
58.int i = s->front;
59.if (isEmpty(s)) {
60. printf("队列空！\n");
61.return;
62. }
63.else {
64. printf("队列的元素为：");
65.while (i!=s->rear) {
66. printf("%d ", s->base[i]);
67. i = (i + 1) % MAXNUM;
68. }
69. printf("\n");
70. }
71.}
72.//创建队列
73.void createQueue(SqQueue* s) {
74.int num,i,temp;
75. printf("请输入要输入的元素数目：");
76. scanf_s("%d", &num);
77.for (i = 0; i 78. printf("请输入元第%d个元素：",i+1); 79. scanf_s("%d", &temp); 80. appendQueue(s, temp); 81. } 82.} 83.int main() { 84. SqQueue* s=(SqQueue*)malloc(sizeof(SqQueue)); 85.int e, selected=0; 86. printf("\n=====================================\n"); 87. printf("0.退出\n"); 88. printf("1.初始化\n"); 89. printf("2.建立顺序队列\n"); 90. printf("3.入队\n"); 91. printf("4.出队\n"); 92. printf("5.判断队列是否为空\n"); 93. printf("6.取队头元素\n"); 94. printf("7.遍历队列\n"); 95. printf("=====================================\n"); 96. printf("请选择要进行的操作（1-7）："); 97.while (scanf("%d", &selected)&&selected!=0) { 98.switch (selected) 99. { 100.case 1: 101. initSqQueue(s); 102.break; 103.case 2: 104. createQueue(s); 105.break; 106.case 3: 107. printf("请输入要入队列的元素："); 108. scanf_s("%d", &e); 109. appendQueue(s,e); 110.break; 111.case 4: 112. deleteQueue(s,e); 113. printf("出队列的元素为：%d\n",e); 114.break; 115.case 5: 116.if (isEmpty(s)) { 117. printf("队列为空！\n"); 118. } 119.else { 120. printf("队列不空！\n"); 121. } 122.break; 123.case 6: 124. e = getHead(s); 125. printf("队头元素为：%d\n", e); 126.break; 127.case 7: 128. displayQueue(s); 129.break; 130.default: 131. printf("操作有误！\n"); 132.break; 133. } 134. printf("请选择要进行的操作（1-7）："); 135. } 136.return 0; 137.} 5）利用顺序队列和顺序栈判断一个字符串是否是回文 设计思路： 1、先初始化一个栈和一个队列 2、用户输入一个字符串，储存在数组中 3、用for循环遍历数组，分别将里面的字符储存在栈中和队列中 4、用while循环做出栈和出队列的操作，同时比较出来的元素是否相等，如 果有一个不相等，就直接返回“不是回文” 5、在判断队列和栈是否为空，如果都为空则是回文。 QueueAndStack.h头文件中内容： 1.#include 2.#include 3.#define MAXNUM 100 4.#define Elemtype char 5.#define TRUE 1 6.#define FALSE 0 7.typedef struct { 8. Elemtype* base; 9.int front; 10.int rear; 11.}SqQueue; 12.typedef struct stacknode { 13. Elemtype data; 14. stacknode* next; 15.}StackNode; 16.typedef struct { 17. stacknode* top;//栈顶指针 18.}LinkStack; 19. 20. 21.//初始化一个空队列 22.int initSqQueue(SqQueue* s) { 23. s->base = (Elemtype*)malloc(sizeof(Elemtype)*MAXNUM); 24.if (!s->base) { 25.return FALSE; 26. } 27. s->front = s->rear = 0; 28.return TRUE; 29.} 30.//入队列操作 31.int appendQueue(SqQueue* s, Elemtype e) { 32.if ((s->rear + 1) % MAXNUM == s->front) { 33.return FALSE; 34. } 35. s->base[s->rear] = e; 36. s->rear = (s->rear + 1) % MAXNUM; 37.return TRUE; 38.} 39.//判断队列是否为空 40.int isEmpty(SqQueue* s) { 41.if (s->rear == s->front) { 42.return TRUE; 43. } 44.else { 45.return FALSE; 46. } 47.} 48.//出队列操作 49.int deleteQueue(SqQueue* s, Elemtype &e) { 50.if (isEmpty(s)) { 51.return FALSE; 52. } 53. e = s->base[s->front]; 54. s->front = (s->front + 1) % MAXNUM; 55.return TRUE; 56.} 57.//获取头元素 58.Elemtype getHead(SqQueue* s) { 59.if (isEmpty(s)) { 60. printf("队列空，没有头元素！\n"); 61.return 0; 62. } 63.return s->base[s->front]; 64.} 65.//遍历队列 66.void displayQueue(SqQueue* s) { 67.int i = s->front; 68.if (isEmpty(s)) { 69. printf("队列空！\n"); 70.return; 71. } 72.else { 73. printf("队列的元素为："); 74.while (i != s->rear) { 75. printf("%d ", s->base[i]); 76. i = (i + 1) % MAXNUM; 77. } 78. printf("\n"); 79. } 80.} 81.//创建队列 82.void createQueue(SqQueue* s) { 83.int num, i, temp; 84. printf("请输入要输入的元素数目："); 85. scanf_s("%d", &num); 86.for (i = 0; i < num; i++) { 87. printf("请输入元第%d个元素：", i + 1); 88. scanf_s("%d", &temp); 89. appendQueue(s, temp); 90. } 91.} 92. 93./*初始化栈*/ 94.void InitStack(LinkStack* s) { 95. s->top = NULL; 96. printf("\n已初始化链栈！\n"); 97.} 98./*链栈置空*/ 99.void setEmpty(LinkStack* s) { 100. s->top = NULL; 101. printf("\n链栈被置空！\n"); 102.} 103./*入栈*/ 104.void pushLstack(LinkStack* s, Elemtype e) { 105. StackNode* p = (StackNode*)malloc(sizeof(StackNode)); 106. p->data = e; 107. p->next = s->top; 108. s->top = p; 109.} 110./*出栈*/ 111.Elemtype popLstack(LinkStack* s) { 112. Elemtype e; 113. StackNode* p; 114. p = s->top; 115.if (s->top == NULL) { 116. printf("\n栈空，不能出栈！\n"); 117.return -1; 118. } 119. e = p->data; 120. s->top = p->next; 121. free(p); 122.return e; 123.} 124./*取栈顶元素*/ 125.Elemtype StackTop(LinkStack* s) { 126.if (s->top == NULL) { 127. printf("\n链栈空！\n"); 128.return -1; 129. } 130.return s->top->data; 131.} 132./*遍历链栈*/ 133.void displayLstack(LinkStack* s) { 134.if (s->top == NULL) { 135. printf("连栈空！\n"); 136.return; 137. } 138. printf("\n链栈中的数据为：\n"); 139. printf("==========================================\n"); 140. StackNode* p; 141. p = s->top; 142.while (p != NULL) { 143. printf("%d\n", p->data); 144. p = p->next; 145. } 146. printf("==========================================\n"); 147.} 148./*判断栈是否为空*/ 149.int isEmpty(LinkStack* s) { 150.if (s->top == NULL) { 151.return 1; 152. } 153.else { 154.return 0; 155. } 156.} main.cpp中的内容： 1.#include "QueueAndStack.h" 2.#include 3. 4.int isPalindrome(char* str); 5. 6.int main() { 7.char* str = (char*)malloc(sizeof(char)*200); 8. printf("请输入要判断的字符串："); 9. scanf("%s", str); 10.if (isPalindrome(str)) { 11. printf("这串字符串是回文。\n"); 12. } 13.else { 14. printf("这串字符串不是回文。\n"); 15. } 16.return 0; 17.} 18.int isPalindrome(char* str) { 19. SqQueue* s1 = (SqQueue*)malloc(sizeof(SqQueue)); 20. initSqQueue(s1); 21. LinkStack* s2 = (LinkStack*)malloc(sizeof(LinkStack)); 22. InitStack(s2); 23.int len = strlen(str); 24.for (int i = 0; i < len; i++) { 25. appendQueue(s1, str[i]); 26. pushLstack(s2, str[i]); 27. } 28.while (！isEmpty(s1) && ！isEmpty(s2)) { 29.char x, y; 30. deleteQueue(s1, x); 31. y=popLstack(s2); 32.if (x != y) { 33.return 0; 34. } 35. } 36.if (!isEmpty(s1) || !isEmpty(s2)) { 37.return 0; 38. } 39.else { 40.return 1; 41. } 42.} 4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写） 4）顺序队列的入队、出队和取队头元素的操作 存在问题：一开始报了以下错误： 原因：SqQueue* s忘记初始化。 修改： 5）利用顺序队列和顺序栈判断一个字符串是否是回文两种运行结果： 1）、不是回文的字符串： 2）、是回文的字符串： 问题：在调试程序的过程中出现无论是否是回文，都出现不是回文的现象 原因：用while语句进行判断的时候条件出现问题while (isEmpty(s1) && isEmpty(s2)) 解决方法：改为while (!isEmpty(s1) && !isEmpty(s2))即可。 5．讨论（通过实验的一些体会、学会的知识和技能等） 4）顺序队列的入队、出队和取队头元素的操作 此实验主要练习队列的基本操作，主要包括初始化、创建、入队、出队、判断队列是否为空、取头元素、遍历队列等操作。其中队列可以用链式结构或者顺序结构来储存，以上采用顺序结构并采用循环队列来创建队列。起到了充分利用空间，克服"假溢出"现象的作用。同时也应该注意，循环队列中队列为空的判断条件是q.front==q.rear而队列满的条件是（q.rear+1）%MAXQSIZE==q.front 5）利用顺序队列和顺序栈判断一个字符串是否是回文 上面的实验主要练习队列和栈的基本操作，并没有涉及到栈和队列的应用，此实验练习了栈与队列的简单应用，充分体现了栈先进后出和队列先进先出的特点。利用两者的特点，巧妙地将while循环结合，来判断字符串正反是否相同，以判断字符串是否是回文。需要注意的是要使用strlen（）函数时需要引入头文件string.h。 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求： 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 数据结构实验报告 二．程序设计相关信息 （1）实验题目：编写一个程序algo2-3.cpp，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： 1.初始化双链表h； 2.依次采用尾插法插入a，b，c，d，e元素； 3.输出双链表h； 4.输出双链表h长度； 5.输出双链表h是否为空； 6.判断双链表h的第3个元素； 7.输出元素‘a’的位置； 8.在第4个元素位置上插入‘f’元素； 9.输出双链表h； 10.删除L的第3个元素； 11.输出双链表h； 12.释放双链表h。 （2）实验目的：熟悉双链表的基本操作并掌握尾插法建表。 （3）算法描述或流程图 (4)源代码 #include typedef struct DNode { char data; struct DNode *next; struct DNode *prior; }DNode,DLinkList; void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ; h->next=NULL; h->prior=NULL; } void destroylist(DLinkList *&h) { DLinkList *p=h,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next; } free(p); } int getelem(DLinkList *h,int i,char &e) {int j=0; DLinkList *p=h; while(j 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 精品文档数据结构 实 验 报 告 目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include 数据结构实验十一：图实验
数据结构实验报告格式
数据结构实验一题目一线性表实验报告
(完整版)数据结构实验报告全集
数据结构实验报告图实验
数据结构实验报告
数据结构实验报告图实验
数据结构线性表实验报告
数据结构实验
数据结构实验报告模板
数据结构实验报告2
数据结构实验报告(图)
数据结构线性表的应用实验报告
数据结构图实验报告
数据结构实验报告及心得体会
数据结构实验一 实验报告
《数据结构》实验报告
数据结构实验—图实验报告
相关主题
文本预览