《数据结构》实验指导书(C语言版)

《数据结构》课程实验指导

《数据结构》实验教学大纲

课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统 总学时/实验学时：64/16 总学分/实验学分：3.5/0.5

一、课程简介

数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的

数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。

三、实验方式与基本要求

实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。具体实验要求如下：

1. 问题分析

充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。

2. 数据结构设计

针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。

3. 算法设计

算法设计分概要和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干程序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出。

4. 测试用例设计

准备典型测试数据和测试方案。测试数据要有代表性、敏感性。测试方案包括模块测试

1

和模块集成测试。

5. 上机调试

对程序进行编译，纠正程序中可能出现的语法错误。调试前，先运行一遍程序看看究竟将会发生什么。如果情况很糟，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。

6. 程序性能分析

在运行结果正确的前提下再分析程序中主要算法是否具有较好的时间复杂度和空间复杂度。如果没有，则通过改变数据结构或操作方法使编写的程序性能达到最佳。

7. 实验总结

每个实验完成后要认真书写实验报告，对程序运行的结构，要认真分析，总结每次实验项目的体会与收获。

四、报告与考核

每个实验都要求学生根据上机内容写出实验报告，报告要求包括以下七个方面的内容： 1．实验目的； 2．实验内容； 3．实验要求； 4．算法设计； 5．详细程序清单； 6．程序运行结果；

7．实验心得体会。 考核方式：

每个实验项目根据以下两个方面进行考核：

1．指导教师随堂抽查学生的实验过程（包括实验预习、实验出勤、实验结果的测试），并根据抽查结果评定学生成绩，此成绩占此实验总成绩的70%；

2．学生编写课程设计实验报告，每位学生按照实验报告的内容和要求编写详细的实验报告并打印上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占实验总成绩的30%。

五、设备及器材材料配置

硬件：奔腾以上PC机 软件：TURBO C、C++或Java

六、实验指导书及主要参考书

[1]朱蓉.数据结构实验指导书

[2]张铭.数据结构与算法. 高教出版社.2008.6

[3]张铭.数据结构与算法－－学习指导与习题解析. 高教出版社.2009 [4]耿国华等 数据结构-C语言描述. 高教出版社.2005.7 [5]刘怀亮. 数据结构(C语言描述) .冶金出版社.2005.2

[6]刘怀亮. 数据结构(C语言描述)习题与实验指导导.冶金出版社.2005.2 [7]蔡子经，施伯乐.数据结构教程.上海:复旦大学出版社.1994 [8]严蔚敏,吴伟民.数据结构(C语言版).北京：清华大学出版社.1999；

2

[9]严蔚敏,吴伟民.数据结构题集(C语言版).北京：清华大学出版社.1999； [10]徐孝凯.数据结构课程实验.北京：清华大学出版社.2002；

[11]孟佳娜,胡潇琨.算法与数据结构实验与习题.北京：机械工业出版社.2004.

七、实验项目与内容提要 序号 1 实验名称 顺序表的基本操作 2 3 链表的基本操作 栈的基本操作 目的要求、内容提要 （限20字） 熟悉并完成顺序表上基本操作的算法及其应用问题的编程实现。 熟悉并完成单链表和双向链表基本操作算法的编程实现。 熟悉并完成顺序栈和链栈基本操作算法及其应用问题的编程实现 4 队列的基本操作 5 6 二叉树的操作 静态查找表的查找操作 7 二叉排序树的查找操作 8 9 10 哈希表上的查找操作 排序操作 图的遍历 熟悉并完成循环顺序队列和循环链队列基本操作算法及其应用问题的编程实现。 熟悉并完成二叉树遍历算法及其应用问题的编程实现。。 熟悉并完成静态查找表上的顺序查找、二分查找和索引查找算法的编程实现 熟悉并完成在二叉排序树上进行查找、插入和删除操作的编程实现。 熟悉并完成哈希表的建立、查找和插入操作的编程实现 熟悉并完成几种主要排序操作的编程实现。 熟悉并完成图的遍历、最小生成树及其应用问题的编程实现 1个班 1个班 1个班 2 设计 选做 2 设计 必做 2 设计 选做 1个班 2 设计 选做 1个班 1个班 2 设计 必做 2 设计 必做 1个班 2 设计 必做 1个班 1个班 2 设计 必做 2 设计 必做 每组人数 1个班 实验学时 2 实验类型 设计 必做 选做 必做 所在实验分室

3

实验B01: 顺序表的操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 顺序表的操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的

1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。 三、实验内容 1．建立顺序表。

2．在顺序表上实现插入、删除和查找操作（验证性内容）。 3．删除有序顺序表中的重复元素（设计性内容）。

4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++等 。 使用的软件名称、版本号以及模块： 五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。

（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。

（4）在顺序表中查找第i个元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。 2. 实验相关原理：

线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：

#define MAXLEN 30 /*线性表的最大长度*/ typedef struct

4

{ Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/

int length; /*顺序表的长度，即元素个数*/

}Sqlist; /*顺序表的类型*/

【核心算法提示】

1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。

2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0值。 【核心算法描述】

status Sqlist_insert(Sqlist &L,int i,Elemtype x)

/*在顺序表L中第i个元素前插入新元素x*/

{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN) return OVERFLOW;

/*顺序表L中已放满元素，再做插入操作则溢出*/

for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; }

status Sqlist_delete(Sqlist &L,int i,Elemtype &e)

/*在顺序表L中删除第i个元素*/

{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/ L.length--; /*顺序表L的长度减1*/ return OK；

}

int Sqlist_search(Sqlist L,Elemtype x)

/* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/

5

{ for (i=0;i

/*从第一个元素开始依次将每个元素值与给定值x比较*/

if (i

3．源程序代码参考 #define MAXLEN 50

typedef struct{int elem[MAXLEN]; int length;}Sqlist;

Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ {int j;

if(i<1||i>L.length+1) printf(\ else if(L.length>=MAXLEN) printf(\

else { for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

L.elem[i-1]=x; L.length++;

} return L; }

Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/ {int j;

if(i<1||i>L.length) printf(\ else { for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];

L.length--;

} return L; }

int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ { int i;

for (i=0;i

6

else

return 0; }

void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ { int j;

for(j=0;j<=L.length-1;j++) printf(\ printf(\}

main() /*主函数 */ { Sqlist L; int i,x,j;

printf(\请求输入顺序表中元素个数*/ scanf(\

printf(\请求输入顺序表中各个元素*/ for(j=0;j<=L.length-1;j++)

scanf(\

printf(\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的新元素*/ scanf(\

L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=Sqlist_delete(L,i);/*调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(\ scanf(\

if (Sqlist_search(L,x)) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查

找不成功*/

printf(\ else

printf(\ }

7

4．运行结果参考如图1-1所示：

图1-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。 ⑴ 实验要求

① 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。

② 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。 ⑵ 核心算法提示

要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。

⑶ 核心算法描述 Sqlist delSqlist(Sqlist L)

{int i=0,j;

while(i

if (L.elem[i]==L.elem[i+1]) /*如果第i个及第i+1个相邻元素值相等*/

{ for (j=i+1;j

除第i个元素的目的*/

L.elem[j-1]=L.elem[j];

L.length--; /*有序顺序表的表长减1*/ } else i++; return L; }

2．编程实现一个简单学生成绩表的操作。

8

实验要求

此系统的功能包括：

① 查询：按特定的条件查找学生

② 修改：按学号对某个学生的某门课程成绩进行修改 ③ 插入：增加新学生的信息

④ 删除：按学号删除已退学的学生的信息。 学生成绩表的数据如下：

学号 2008001 2008002 2008003 2008004 2008006 2008006 姓名 Alan Danie Helen Bill Peter Amy 性别 F M M F M F 大学英语 高等数学 93 75 56 87 79 68 88 69 77 90 86 75 要求采用顺序存储结构来实现对上述成绩表的相关操作。

9

实验B02: 链表的操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 链表的操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的

1．掌握线性表的链式存储结构的表示和实现方法。 2．掌握链表基本操作的算法实现。 三、实验内容

1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。 2．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。 3．计算已知一个单链表中数据域值为一个指定值x的结点个数（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++ 等。 使用的软件名称、版本号以及模块： 五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。

（3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。

（4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。 2. 实验相关原理：

线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含

10

一个指针的链表，则称单链表。单链表的存储结构描述如下：

typedef struct Lnode {

Elemtype data;/*数据域*/ struct Lnode *next;/*指针域*/

}LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/

【核心算法提示】

1． 链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入” 的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。

2． 链表查找操作的基本步骤：因链表是一种\顺序存取\的结构，则要在带头结点的链表中查找到第 i个 元素，必须从头结点开始沿着后继指针依次\点数\，直到点到第 i 个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。

3． 链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。

4． 链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。 【核心算法描述】

void creat1(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用头

插法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/ L->next=NULL;/*头结点的指针域初始为空*/ scanf(\

while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/ p->data=node; /*为新结点数据域赋值*/ p->next=L->next;/*新结点指针域指向开始结点*/

L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/

scanf(\} }

void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插

法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/ L->next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/

scanf(\while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/ p->data=node; /*新结点数据域赋值*/ p->next=NULL; /*新结点指针域为空*/ r->next=p;/*尾结点指针域指向新结点*/

11

r=p; /*尾指针指向新结点，即新结点成为尾结点*/

scanf(\ } }

status list_search(Linklist L, int i;Elemtype &e)

/*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/

{ p=L->next; /*使指针p指向第1个元素结点*/

j=1; /*计数器赋初值为1*/

while (p&& jnext; j++; }

if (!p&& j>i)

return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK;

}

status list_insert(Linklist &L,int i;Elemtype x)

/*在带头结点的单链表L中第i个位置之前插入新元素x*/

{ p=L; j=0;

while(p!=NULL&&j

个位置*/

{ p=p->next;

++j;

}

if(p==NULL||j>i-1)

return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE)); /*分配一个新结点的空间*/ s->data=x; /*为新结点数据域赋值*/

/*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/

s->next=p->next; /*新结点指针域指向p的后继结点*/

p->next=s; /*新结点成为p的后继结点*/ return OK;

}

status list_delete(Linklist &L,int i,Elemtype &x)

/*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/

{ p=L;j=0;

while(p->next!=NULL&&jnext;

++j; }

if (p->next==NULL||j>i-1)

return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p->next; /* q指向p的后继结点*/

12

p->next=q->next; /*q的后继结点成为p的后继结点*/ x=q->data; /*用x返回第i个位置的元素*/

free(q); /*释放q所指的被删结点的空间*/ return OK; }

3．源程序代码参考

#include #include typedef struct Lnode { int data;

struct Lnode *next; } LNODE,*Linklist;

Linklist creat(Linklist L) /*单链表建立函数 */ {int node; Linklist p;

L=(Linklist)malloc(sizeof(LNODE)); L->next=NULL;

printf(\ \ /*请求输入线性表中各个元素，以0结束*/ scanf(\ while(node!=0)

{p=(Linklist)malloc(sizeof(LNODE)); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf(\ } return L; }

Linklist insert(Linklist L,int i,int x) /*单链表插入函数*/ { int j;Linklist p,s; p=L; j=0;

while (p!=NULL&&jnext; ++j; }

if (p==NULL||j>i-1)

printf(\ else

13

{ s=(Linklist)malloc(sizeof(LNODE)); s->data=x; s->next=p->next; p->next=s; } return L; }

Linklist delete(Linklist L,int i) /*单链表删除函数*/ { int j,x; Linklist p,q; p=L; j=0;

while(p->next!=NULL&&jnext; ++j; }

if(p->next==NULL||j>i-1) printf(\ else

{ q=p->next; p->next=q->next; x=q->data;

printf(\ free(q); } return L; }

int search(Linklist L, int i) /*单链上的查找函数*/ { Linklist p; int j; p=L->next; j=1;

while (p&& jnext; j++; }

if (!p&& j>i)

return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else

return(p->data); /*否则函数返回第i个元素的值*/ }

14

void display(Linklist L) /*单链表元素输出函数*/ { Linklist p; p=L->next; while(p!=NULL) { printf(\ p=p->next; } printf(\}

main()/*主函数*/

{Linklist L=NULL; int i,x;

L=creat(L);/*调用单链表建立函数*/ printf(\

display(L); /*调用单链表元素输出(遍历)函数*/

printf(\ you want to insert:\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的元素*/ scanf(\

L=insert(L,i,x);/*调用单链表插入函数*/ printf(\ display(L);/*调用单链表元素输出(遍历)函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=delete(L,i); /*调用单链表删除函数*/ printf(\

display(L); /*调用单链表元素输出(遍历)函数*/

printf(\请求输入待查找元素的位置*/ scanf(\

x=search(L,i); /*调用单链表查找函数*/

if (x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(\ the %dth elem is %d\\n\ else

printf(\ the %dth elem is not exsit\\n\}

15

4．运行结果参考如图2-1所示：

图2-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1. 编程实现在双向循环链表上的插入、删除和查找操作

⑴ 实验要求

（1）输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在双向循环链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。

（3）删除双向循环链表中第i个元素，并输出删除后的链表中各元素值。

（4）在双向循环链表中查找值为x元素，如果查找成功，则显示该元素在链表中的位置，否则显示该元素不存在。

⑵ 核心算法提示

双向循环链表采用的存储结构描述如下：

typedef struct DULNODE

{ Elemtype data; /*数据域*/

struct DULNODE *prior; /*指向前驱结点的指针域*/ struct DULNODE *next;/*指向后继结点的指针域*/

}DULNODE,*DuLinklist; typedef int Elemtype;

不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点：

（1）凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。 （2）单链表操作算法中的判断条件：p= =NULL 或p!=NULL ,在循环链表的操作算法中则需改为：p!= L,其中L为链表的头指针。

⑶ 核心算法描述

void DuList_creat (DuLinklist &L,int n) /*输入n个整数（其中n为表长），将这些整数作为data

域并用尾插法建立一个带头结点的双向循环链表的函数*/

{ L=( DuLinklist)malloc(sizeof(DULNODE));/*为头结点分配空间*/

16

L->next=L->prior=L;

/*使头结点的后继指针和前驱指针都指向自身，形成空的双向循环链表*/

r=L; /*尾指针初始指向头结点*/

for (i=0;i

{ p=(DuLinklist)malloc(sizeof(DULNODE));/*为一个新结点分配空间*/ scanf(\从键盘输入值，并保存在新结点数据域中*/ p->next=r->next; /*新结点后继指针指向尾结点r的后继结点*/ p->prior=r; /*新结点的前驱指针指向尾结点r*/

r->next=p; /*尾结点的后继指针指向新结点*/

r=p; /*尾指针指向新结点，即新结点成为尾结点*/

}

L->prior=r; /*使尾结点成为头结点的前驱结点*/ }

status DuList_search(DuLinklist L, int i;Elemtype &e)

/*在带头结点的双向循环链表L中查找第i个元素，如果查找成功则用e返回其值*/

{ p=L->next; /*使指针p指向第1个元素结点*/ j=1; /*计数器赋初值为1*/

while (p!=L && jnext; j++;

} if (j!=i)

return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK; }

status DuList_insert(DuLinklist &L,int i;Elemtype x)

/*在带头结点的双向循环链表L中第i个位置之前插入新元素x*/

{ p=L->next; j=1;

while(p!=L &&j

{ p=p->next;

++j; }

if(j!=i)

return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(DuLinklist)malloc(sizeof(DULNODE)); /*为一个新结点s分配空间*/ s->data=x; /*为新结点数据域赋值*/

/*下面四条语句就是完成修改链，将新结点s插入到p结点之前*/ s->next=p;

p->prior->next=s;

s->prior=p->prior;

p->prior=s;

return OK;

}

17

status DuList_delete(DuLinklist &L,int i,Elemtype &x)

/*在带头结点的双向循环链表L中，删除第i个元素结点，并用x返回其值*/ { p=L->next;j=1;

while(p!=L&&jnext;

++j; }

if (j!=i)

return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/

q=p; /*记下被删结点*/

p->prior->next=p->next; /*修改链使得p结点从链中脱离*/ p->next->prior=p->prior; x=q->data;

printf(\ free(q); //释放被删结点空间 return OK; }

提醒: 请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。

2．编写一个程序，计算出一个单链表中数据域值为一个指定值x的结点个数。

实验要求：

⑴ 从键盘输入若干个整数，以此序列为顺序建立一个不带头结点的单链表； ⑵ 输出此单链表中的各个数据元素值；

⑶ 给定一个x的具体整数值，计算并返回此单链表中数据域值为x的结点个数值。

18

实验B03: 栈的操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 栈的操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的

1．掌握栈的存储结构的表示和实现方法。 2．掌握栈的入栈和出栈等基本操作算法实现。 3．了解栈在解决实际问题中的简单应用。 三、实验内容

1．建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。 2．建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。 3．实现汉诺（Hanoi）塔求解问题（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++等。 使用的软件名称、版本号以及模块： 五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序栈、链栈的基本操作算法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。 （2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。

（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。 2. 实验相关原理：

栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：

#define MAXSIZE 100; /*顺序栈的最大长度*/ typedef struct

{ Selemtype base[MAXSIZE]; /*存储栈中数据元素的数组*/

int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ }Sqstack;

【核心算法提示】

19

1．顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。

2． 顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e返回其值，并使函数返回OK。 【核心算法描述】

status Push(Sqstack &S,Selemtype e)

/*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ { if (S.top >=MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR;

S.base[S.top++]=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; }

status Pop(Sqstack &S,Selemtype &e)

/*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ { if (S.top==0) /*如果栈空，则函数返回ERROR*/ Return ERROR;

e=S.base[--S.top];/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; }

3．源程序代码参考

#define MAXSIZE 100 typedef struct

{ int base[MAXSIZE];

int top; /*top指示存储栈顶元素的下一存储单元*/ }Sqstack; /*顺序栈的类型定义*/

Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ { if (S.top>=MAXSIZE)

printf(\

else

S.base[S.top++]=e;

return S; }

Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ { if (S.top==0)

printf(\

else

20

T->data=Pre[Pre_start]; /*取先序序列中的第一个字符作为根结点的数据域值*/ for(i=Mid_start;Mid[i]!=T->data;i++); /*在中序序列中查找根结点*/ ltreelen=i-Mid_start; /*计算左子树中结点个数*/ rtreelen=Mid_end-i; /*计算右子树中结点个数*/ if(ltreelen)

T->lchild=creat_sub(T,Pre_start+1,Pre_start+ltreelen,Mid_start,Mid_start+ltreelen-1) ; else

T->lchild=NULL;

if(rtreelen)

T->rchild=creat_sub(T,Pre_end-rtreelen+1,Pre_end,Mid_end-rtreelen+1,Mid_end); else

T->rchild=NULL;

return T; }

int precmp(Bitree T1,Bitree T2)

/*用先序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)

if (T1->data==T2->data)

if (precmp(T1->lchild,T2->lchild)) if(precmp(T1->rchild,T2->rchild))

return 1; return 0; }

int midcmp(Bitree T1,Bitree T2)

/*用中序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)

if (precmp(T1->lchild,T2->lchild)) if (T1->data==T2->data)

if(precmp(T1->rchild,T2->rchild)) return 1; return 0; }

int backcmp(Bitree T1,Bitree T2)

/*用后序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)

if (precmp(T1->lchild,T2->lchild))

if(precmp(T1->rchild,T2->rchild))

if (T1->data==T2->data) return 1;

return 0; }

36

2． 编程求从二叉树根结点到到指定结点p之间的路径。

⑴ 实验要求

① 假设二叉树的结点值是字符，请根据输入的二叉树后序遍历序列和中序遍历序列来建立二叉链表表示的二叉树,并对其进行某种遍历,输出遍历序列以验证建立的二叉树是否正确。

② 任意给定一结点p,输出从二叉树的根结点到该结点p的路径。 ⑵ 核心算法提示

要求出从根结点到指定结点p之间的路径，可利用后序遍历的非递归算法来实现。由于

后序遍历当访问到p所指结点时，栈中所有结点均为p所指结点的祖先，由这些祖先便构成了一条从根结点到p结点之间的路径。

37

实验B06: 静态表的查找操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 静态表的查找操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的

1．掌握顺序查找操作的算法实现。

2．掌握二分查找操作的算法实现及实现该查找的前提。 3．掌握索引查找操作的算法实现。 三、实验内容

1．建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。 2．建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。 3．建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++ 使用的软件名称、版本号以及模块： 五、知识准备

前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。

（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。

（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。 2. 实验相关原理：

查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。

静态查找表采用顺序存储结构的数据描述为：

#define MAXSIZE 100 /*顺序查找表的最大长度*/ typedef int keytype; typedef struct {keytype key;

38

}redtype; typedef struct

{redtype elem[MAXSIZE]; int length; }Sstable;

【核心算法提示】

查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素 或记录的过程。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针”。

（1）顺序查找操作的基本步骤：从表中最后一个记录开始，逆序扫描查找表，依次将扫描到的结点关键字值与给定值key进行比较，若当前扫描到的结点关键字值与key相等，则查找成功；若扫描到第一个记录，仍未找到关键字值等于key的记录，则查找失败。在程序设计中为了减少执行的循环次数使用了监视哨。监视哨可设置在表头，也可设置在表尾。在此设置在表头。

（2）二分查找也叫折半查找，这种查找要求查找表必须是有序顺序表。其查找操作的基本步骤：首先取出表中的中间元素，若其关键字值等于给定值key，则查找成功，操作结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。 【核心算法描述】

int sxsearch(Sstable ST, keytype key)

/*在顺序查找表ST中，用顺序查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */

{ ST.elem[0].key=key; /*在表头设置监视哨*/

for(i=ST.length;ST.elem[i].key!=key;--i); /*从后往前顺序查找*/ return i; }

int binsearch(Sstable ST,keytype key)

/*在按关键字从小到大的有序顺序表ST中，用二分查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */ { low=1;high=ST.length; /*置查找区间的初值*/ while(low<=high) { mid=(low+high)/2;

if (key==ST.elem[mid].key)

return mid;/*找到匹配记录*/ else if (key

high=mid-1;/*继续对左半部分进行二分查找*/

else low=mid+1；/*继续对右半部分进行二分查找*/ }

return 0; /*找不到匹配记录*/ }

39

3．源程序代码参考

#define MAXSIZE 100 typedef int keytype; typedef struct { keytype key; }redtype; typedef struct

{ redtype elem[MAXSIZE]; int length; }Sstable;

int sxsearch(Sstable ST,keytype Key)/*顺序查找函数*/ { int i;

ST.elem[0].key=Key;

for(i=ST.length;ST.elem[i].key!=Key;--i); return i; }

int binsearch(Sstable ST,keytype Key)/*二分法查找函数*/ { int low,mid,high; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if (Key==ST.elem[mid].key) return mid;

else if (Key

main()/*主函数*/ {Sstable ST; int i,pos,x,key; pos=0; while(1)

{ printf(\ 1---Sxserach\\n\ printf(\ 2---Binserach\\n\ printf(\ 3---Exit\\n\

40

本文来源：https://www.bwwdw.com/article/g3sg.html