数据结构实验指导书C.doc

数据结构实验指导书（适用于计算机应用、软件技术专业）信息工程系目录前言1实验一、单链表的基本操作2实验二 栈和队列4实验三 串6实验四 二叉树的遍历8实验五 树的应用11实验六 图13实验七、折半查找和二叉排序树15实验八、内部排序17前言数据结构是计算机应用、软件技术等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。数据结构是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。实验一 链表的操作一、实验目的 1、通过实验，掌握链表的输入与输出2、通过实验，掌握链表的基本操作二、实验内容1、建立自己的有关链表的头文件2、练习链表的输入与输出3、练习链表的基本操作的实现4、练习链表基本操作的应用三、实验前的准备1、复习相关课程内容，理解并掌握链表基本操作算法2、准备相关的程序清单3、阅读实验指导书四、实验步骤与方法（一）、理解并运行下面的程序将用户输入的数据按头插入法建立一个带头结点的单链表。输入结点数据时以输入一串字符的方式实现，$字符为结束输入字符。#include “datastru.h”#include #include int count_head(LINKLIST *head)/*带头结点的单链表:输出单链表元素值并计数*/ int I = 0; LINKLIST *p; p = head-next; printf(“输出单链表元素值 : “); while(p != NULL) printf(“ %c”,p-data);I+;p = p-next; printf(“n”); return I;LINKLIST *creatlink_head_head(LINKLIST *head) /*用头插入法建立带头结点的单链表*/ LINKLIST *t;char ch; t = (LINKLIST *)malloc(sizeof(LINKLIST); head = t; t-next = NULL; printf(“单链表元素值为单个字符, 连续输入，$为结束字符 : “); while(ch = getchar()!= $) t = (LINKLIST *) malloc(sizeof(LINKLIST);t-data = ch;t-next = head-next;head-next = t; return(head);main() LINKLIST *head = NULL; int num; printf(“n 建立单链表nn”); head = creatlink_head_head(head); fflush(stdin); num = count_head(head); printf(“单链表元素个数 = %dn”, num);运行情况如下：输入：输出：（二）、建立自己的头文件mylinklist.h，内容包括单链表数据结构的说明，链表的建立与输出、插入与删除操作等要求：程序自己用附页附上（三）、单链表基本操作的应用1、 通过调用基本操作的功能函数，完成单链表指定位置元素的插入、删除。程序清单：运行结果：五、实验中出现的问题与解决方法实验二 栈与队列的基本操作 一、实验目的 1、通过实验，掌握输入与输出2、通过实验，掌握栈与队列的基本操作二、实验内容3、建立相关的头文件4、栈与队列的基本操作练习三、实验前的准备1、复习相关课程内容，掌握并理解栈与队列的基本操作2、准备相关的程序清单3、阅读实验指导书四、实验步骤与方法（一）、建立自己的有关栈与队列的头文件，内容包括栈与队列数据结构的说明，基本操作的实现等（二）、完成一栈的建立与输出。写出程序及运行结果（三）、完成一队列的建立与输出五、实验中出现的问题与解决方法实验三 串的操作一、实验目的 1、通过实验，掌握顺序串的数据类型描述及基本操作的实现二、实验内容1、练习顺序串的应用三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法（一）、顺序串的应用1、建立自己的头文件MYSTRING.H,内容包括顺序串的数据类型描述,串的连接、串的定位操作等2、编写算法，完成顺序串的数据生成与数据的输出，并将这两个函数加入到MYSTRING.H中3、 编写算法，通过调用相关函数验证子串的定位操作五、实验中出现的问题与解决方法实验四 二叉树一、实验目的 1、通过实验，掌握二叉树的建立与存储2、通过实验，掌握二叉树的遍历方法二、实验内容1、练习二叉树的建立与存储2、练习二叉树的遍历三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法，其中，建立二叉树的代码如下：BTCHINALR * createbt( ) BTCHINALR *q; struct node1 *s30; int j,i,x; printf(建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn); printf(i,x = ); scanf(%d,%c,&i,&x); while(i != 0 & x != $) q = (BTCHINALR*)malloc(sizeof(BTCHINALR); /*建立一个新结点q*/ q-data = x; q-lchild = NULL; q-rchild = NULL; si = q;/*q新结点地址存入s指针数组中*/ if(i != 1)/*i = 1，对应的结点是根结点*/ j = i / 2; /*求双亲结点的编号j*/ if(i % 2 = 0) sj-lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else sj-rchild = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(i,x = ); scanf(%d,%c,&i,&x); return s1; /*返回根结点地址*/2、建立教材中P77图6.9示的二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。写出有关算法五、实验中出现的问题与解决方法实验五 树的应用一、实验目的 通过实验，进一步掌握树的应用二、实验内容练习二叉树的应用三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、查找二叉链表中指定的结点的子函数如下，请编写程序验证此算法#include #include #include BTCHINALR *search_ch(BTCHINALR *cur, char x)/*先序查找*/BTCHINALR *temp; if(cur=NULL) return NULL; if(x = cur-data) return cur; temp = search_ch(cur-lchild,x); if (temp != NULL) return temp; else return search_ch(cur-rchild,x);main（） 2、编写算法，求二叉树中叶子结点的个数3、查找给定结点的双亲结点的算法，请编写程序，验证此算法#include #include #include BTCHINALR *parent(BTCHINALR *start, BTCHINALR *current)/*从start所指结点起查找当前结点current的父亲结点*/ BTCHINALR *p; if(start=NULL)return NULL; if(start-lchild=current|start-rchild=current)return start; p=parent(start-lchild,current); if(p!=NULL) return p; else return parent(start-rchild,current);main（） 五、实验中出现的问题与解决方法实验六 图的建立与存储一、实验目的 1、通过实验，掌握图的建立与存储二、实验内容1、练习用图的邻接矩阵表示法存储图2、练习用图的邻接链表表示法存储图三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、图的邻接矩阵表示法算法如下，通过如下算法，完成图的建立#include #include#includeMGRAPH create_mgraph()/*建立图的邻接矩阵*/ int i,j,k; MGRAPH mg; mg.kind=2; printf(nn输入顶点数和边数(用逗号隔开) : ); scanf(%d,%d,&i,&j);fflush(stdin); mg.vexnum=i; mg.arcnum=j; printf(nn); for(i=0;img.vexnum;i+) printf(输入顶点 %d 的值 : ,i+1); scanf(%d,&mg.vexsi); fflush(stdin); for(i=0;img.vexnum;i+) for(j=0;jmg.vexnum;j+) mg.arcsij=0; for(k=1;k=mg.arcnum;k+) printf(输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ,k); scanf(%d,%d,&i,&j); fflush(stdin); while(img.vexnum|jmg.vexnum) printf(输入错，重新输入: ); scanf(%d,%d,&i,&j); mg.arcsi-1j-1=1; mg.arcsj-1i-1=1; return mg;main（）2、图的邻接链表表示法算法如下，通过如下算法，完成图的建立#include #include#includeADJGRAPH creat_adjgraph()EDGENODE *p;int i, s, d;ADJGRAPH adjg;adjg.kind = 2;printf(nn输入顶点数和边数(用逗号隔开) : );scanf(%d,%d, &s, &d);fflush(stdin);adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/printf(nn);for(i = 0; i adjg.vexnum; i+) printf(输入顶点 %d 的值 : , i + 1); scanf(%d, &adjg.adjlisti.vertex); /*输入顶点的值*/ fflush(stdin); adjg.adjlisti.link = NULL;printf(nn);for(i = 0; i adjg.arcnum; i+) printf(输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): , i + 1); scanf(%d,%d, &s, &d); /*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s adjg.vexnum | d adjg.vexnum) printf(输入错，重新输入: ); scanf(%d,%d, &s, &d); s -; d -; p = malloc(sizeof(EDGENODE); /*建立一个和边相关的结点*/ p-adjvex = d; p-next = adjg.adjlists.link; /*挂到对应的单链表上*/ adjg.adjlists.link = p; p = malloc(sizeof(EDGENODE); /*建立另一个和边相关的结点*/ p-adjvex = s; p-next = adjg.adjlistd.link; /*挂到对应的单链表上*/ adjg.adjlistd.link = p;return adjg;main（）五、实验中出现的问题与解决方法实验七 基本查找算法一、实验目的 1、通过实验，掌握静态查找的算法2、通过实验，掌握动态查找的算法二、实验内容1、练习顺序表上查找元素2、练习二分法查找元素三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、完成顺序表上顺序查找元素的算法#include datastru.h#include int seq_search(KEYTYPE k, SSTABLE *st)/*顺序表上查找元素*/ int j; j = st-len; /*顺序表元素个数*/ st-r0.key = k; /*st-r0单元作为监视哨*/ while(st-rj.key != k) j-; /*顺序表从后向前查找*/ return j; /*j=0, 找不到；j0 找到*/main( ) 运行情况如下：2、写一算法，完成有序表上二分法查找元素五、实验中出现的问题与解决方法实验八 简单内部排序一、实验目的 通过实验，掌握简单的排序方法二、实验内容1、练习直接插入排序2、练习冒泡排序3、练习选择排序三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、完成直接插入排序的算法，理解并运行下面的程序#include datastru.h#include void insertsort(RECNODE *r, int n)main( ) RECNODE aMAXSIZE; int i, j, k, len;printf(nn输入待排序数据(整数，以空格隔开，0 结束) : ); k = 0; scanf(%d,&j);while(j != 0) k+; ak.key = j; scanf(%d,&j); len = k;printf(n排序前 : );for (i = 0; i len; i+) printf( %d,ai+1.key);printf(n);insertsort (a,len);printf(nn排序后 : );for (i = 0; i len; i+) printf( %d,ai+1.key);printf(nn);2、完成冒泡排序的算法，理解并运行下面的程序#include void bublesort(RECNODE *r, int n)main( ) RECNODE aMAXSIZE; int i,