数据结构实验指导书(2013)

数据结构实验指导书

仲志平 编写

安徽师范大学物理与电子信息学院

自动化教研室 二0一三年八月

前言

《数据结构》是自动化、电子信息工程以及通信工程等专业的专业基础课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价．通过本课程的学习，使学生深入透彻地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为自动化专业、电子信息工程专业以及通信工程专业学生今后学习其它相关专业课程奠定基础．

本实验指导书是为了配合“实用数据结构”课程的教学而编写的．指导书包括4个实验，每个实验均由实验目的、基本概念和实验内容三个部分构成．其中实验内容包括“验证性内容”和“设计性内容”两部分．“验证性内容”提供了参考程序，主要是加深对基本概念的理解、增加感性认识．“设计性内容”则是考察学生对所学知识灵活运用的能力．为了帮助同学们对所学知识的理解，在基本概念中提供了各种数据结构所对应的操作的算法．在附录中提供了一些结构较复杂的操作算法及相应的实例．

实验操作是本课程教学内容的一个重要方面．因此，要求同学在每次实验操作之前，仔细阅读实验指导书和教材中的相关内容，复习和掌握好算法工具（C语言），实验前，要求同学们读懂“验证性内容”，准备好“设计性内容”的方案．操作过程中细心观察各种现象和结果，做好记录，最终完成实验报告．

目 录

实验一 线性表 ......................................................................................................... 1

一、实验目的 ...................................................................................................... 1 二、基本概念 ...................................................................................................... 1 三、实验内容 ...................................................................................................... 6 实验二 栈与队列 ................................................................................................... 13

一、实验目的 .................................................................................................... 13 二、基本概念 .................................................................................................... 13 三、实验内容 .................................................................................................... 19 实验三 二叉树 ..................................................................................................... 28

一、实验目的 .................................................................................................... 28 二、基本概念 .................................................................................................... 28 三、实验内容 .................................................................................................... 31 实验四 查找与排序 ............................................................................................... 39

一、实验目的 .................................................................................................... 39 二、基本概念 .................................................................................................... 39 三、实验内容 .................................................................................................... 49 附 录 ..................................................................................................................... 56

实验一 线性表

一、实验目的

１．理解顺序表、链表的概念和存储方式． ２．掌握顺序表、链表的相关运算和算法．

二、基本概念

1．线性表

线性表是一组有限的数据元素的集合，它是一种最简单、最常见的数据结构．线性表的一般表示形式为：

L = (a1, a2, …, an)

其中L为线性表，ai (i=1, 2, …, n)是属于某数据对象的元素，n(n≥0)为元素个数，又称为表长，n=0时为空表．

data

1 i-1 i n-1 MAXSIZE-1

顺序表中的数据元素存储在一组地址连续的存储单元中，其存储结构具有以下特点：

①线性表中所有元素所占的存储空间是连续的；

②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的．如图1.1所示.

顺序表的定义： typedef struct

{

datatype data[MAXSIZE]; int last;

}SeqList;

顺序表的初始化： SeqList *init_SeqList()

顺序表的的主要运算有插入、删除、查找和排序． (1) 顺序表的插入运算算法（算法1.1） int Insert_SeqList(SeqList *L,int i,int x) {

int j;

if(L->last==MAXSIZE-1)

{

printf("the list is full!"); return -1; }

if(i<1 || i>L->last+2)

{

printf("the location is wrong"); return 0; }

for(j=L->last;j>=i-1;j--)

L->data[j+1]=L->data[j]; L->data[i-1]=x;

/*结点移动*/

/*新元素插入*/

/*检查插入位臵的正确性*/

/*表空间已满，不能插入*/

/*在线性表L的第i个位臵插入一个数据元素x*/

{

SeqList *L;

L=(SeqList *)malloc(sizeof(SeqList)); L->last=-1; return L; }

L->last++; /*last仍指向最后元素*/

return 1; }

/*插入成功*/

(2) 顺序表的删除运算算法（ …… 此处隐藏：5509字，全部文档内容请下载后查看。喜欢就下载吧 ……