【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所指的相同 //的结点。如果单链表上