【2017年整理】数据结构实验指导书.doc
文本预览下载声明
《数 据 结 构》
实 验 指 导 书
白云飞 倪素虹 郑广 编著
河北科技大学信息科学与工程学院
2004年2月
简 介
《数据结构》是高等教育计算机及应用专业考试计划中的专业课程，主要研究数据的逻辑结构、存储结构以及相应的算法。数据的逻辑结构包括线性结构、树型结构、图状结构和集合四大类。线性结构较简单数据元素之间是一对一的关系；树型结构较复杂，数据元素之间的关系是一对多的关系；图状结构则更复杂，数据元素之间是多对多的关系；集合中的数据元素除同属于一个集合外，数据元素之间是完全松散的关系，也就是无关系。数据的存储结构概括为顺序结构、链式结构、索引结构和散列结构四大类，各有优缺点，适应于不同的应用场合。对数据的基本运算概括为查找、插入、删除、排序和遍历等，当数据的逻辑结构、存储结构及程序设计方法不同时，相应的算法也就不同。
本书共包含五个实验，其中第三个（图的遍历操作）实验选作，以Borland C++ 3.1语言为开发环境，大部分程序也可以在Turbo C 2.0下运行。主要对线性链表、二叉树、图、查找和排序五个方面的概念和算法进行了详细的分析和讨论。每个实验包括需求分析、概要设计、详细设计、测试分析、用户使用说明和测试结果六个部分。
目 录
实验一 单链表的操作 4
实验二 二叉树操作 10
实验三 图的遍历操作 15
实验四 数据查找 20
实验五 排序 26
附1 32
实验一 单链表的操作
需求分析
本实验完成对单链表的插入和删除，单链表的数据域为字符串，插入时不允许重复的字符串插入表中；删除时是根据输入的字符串，先找到相应的结点，后删除之。
输入的形式和输入值的范围
输入的字符串可以含有空格，以回车键结束。如果直接按回车键表示建立链表结束。
输入的字符串最大长度默认为10，用户可以修改头文件改变此长度。
输出的形式
单链表的输出是每个字符串占一行。当插入重复的字符串到表中时，有信息提示，否则输出插入后的单链表；当根据输入的字符串删除时，如果没有找到相应的结点，有信息提示，否则输出删除后的单链表。
程序所能达到的功能
能够根据要求正确的实现插入和删除功能。
测试数据
见六、测试结果
概要设计
本实验用到的数据结构定义在linklist.h的头文件中，如下：
//以下是linklist.h的头文件内容。
#define STRLEN 10 //定义字符串的默认长度
typedef struct Node{ //定义单链表结点类型
char string[STRLEN] ;
struct Node *next ;
} ListNode ;//定义结点别名
typedef ListNode *LinkList ; //定义结点指针类型
typedef enum bool{FALSE, TRUE} Boolean ; //定义布尔类型
主程序流程：
详细设计
//以下是linklist.cpp的程序文件内容。
#include stdio.h
#include stdlib.h
#include string.h
#include linklist.h //定义数据结构的头文件
//初始化操作，本操作创建一个只含有头结点的空链表。
void IniList(LinkList *head)
{
*head = (LinkList)malloc(sizeof(ListNode)) ;
(*head)-next = NULL ;
}
//插入操作，本操作在头指针为head的单链表上，插入字符串为
//str所指的结点；如果单链表存在此串，返回假值；否则插入并
//返回真值
Boolean InsertList( LinkList head , char *str )
{
ListNode *p = head-next ;
//判断是否存在与待插入的字符串相同的字符串
while (p strcmp(p-string, str))
p = p-next ;
if (p) return FALSE ; //存在相同的字符串，返回假值
//以下几步完成插入
p = (ListNode *)malloc(sizeof(ListNode)) ; //开辟结点空间
strcpy(p-string, str) ; //给数据域赋值
p-next = head-next ; //该结点插入到头结点之后
head-next = p ;
return TRUE ; //插入成功，返回真值
}
//删除操作，在单链表head上，删除字符串与str所指的相同
//的结点。如果单链表上
显示全部