数据结构
作业和实验指导书
数据结构课程组
广东工业大学计算机学院
20##年3月
目 录
第1章 概述
1.1 课程、教材和实验
1.2 作业和实验安排
第2章 算法设计实验和上机
2.1 数据结构习题概述
2.2 算法设计的上机作业要求
2.3 算法设计上机作业
第3章 抽象数据类型的实现
3.1 实验概要
3.2 实验目的
3.3 预习与参考
3.4 实验要求和设计指标
3.5 实验仪器设备和材料
3.6 调试及结果测试
3.7 考核形式
3.8 实验报告要求
3.9 思考题
3.10 示例
第4章 课程设计
4.1 课程设计概述
4.2 课程设计时间和内容
4.3 课程设计步骤
4.4 课程设计报告范例
4.5 课程设计考核形式和评分标准
第1章 概述
1.1 课程、教材和实验
数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。数据结构不仅是计算机专业的核心课程，而且已成为其他理工专业的热门选修课。课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯, 其重要程度决不亚于知识传授。因此，在数据结构的整个教学过程中, 完成习题作业和上机实习是两个至关重要的环节。
习题的作用在于帮助学生深入理解教材内容, 巩固基本概念, 达到培养良好程序设计能力和习惯的目的。从认知的程度划分，数据结构的习题通常可分为三类：基础知识题、算法设计题和综合实习题。基础知识题主要是检查对概念知识的识记和理解，一般可作为学生自测题。算法设计题的目的是练习对原理方法的简单应用，多数是要求在某种数据存储结构上实现某一操作，是数据结构的基础训练，构成了课外作业的主体。综合实习题则训练对知识的综合应用和软件开发能力，主要是针对具体应用问题，选择、设计、和实现抽象数据类型（ADT）的可重用模块，并以此为基础开发满足问题要求的小型应用软件，应将其看作软件工程的综合性基础训练的重要一环，给予足够的重视。
本实验指导书为采用下列教材的数据结构课程而编写：
[1] 严蔚敏，吴伟民. 《数据结构》（C语言版，含光盘）. 清华大学出版社，2002.9
[2] 严蔚敏，吴伟民. 《数据结构题集》（C语言版）. 清华大学出版社，1999.2
其中，《数据结构题集》实际上是一本较全面的学习和实验指导书。本实验指导书根据教学计划给予一些补充，与上述两本教材配合使用。
《数据结构题集》的第一篇为习题篇，含有三百余道习题，组织成十二章，分别对应教科书中各章内容，并在每章之前给出该章的内容提要和学习要求。这些习题是作者在多年教学过程中所积累资料的基础上，参考大量国外教材之后精心设计而成的。书中对特别推荐的题目作了标记，并对每道习题的难易程度按五级划分法给出了难度系数。
第二篇为实习篇，分别以抽象数据类型、线性表、栈和队列、串、数组和广义表、树和图以及查找和排序为核心，设置了七组上机实习题，每组有3至9个题目供学生自由选择。期望这些实习题能对习题起到良好的扩充作用，使学生受到涉及“从问题到程序”的应用软件设计的完整过程的综合训练，培养合作能力，成为将来进行软件开发和研究工作的“实践演习”。
数据结构是实践性很强的课程，光是“听”和“读”是绝对不够的。在努力提高课堂教学的同时，必须大力加强对作业实践环节的要求和管理。国内外先进院校一般都要求修读数据结构的学生每周应不少于4个作业机时，而且有一套严格的作业和实习规范和成绩评定标准，形成行之有效的教学质量保证体系。《数据结构题集》强调规范化在算法设计基本训练中的重要地位。在习题篇中给出了算法书写规范，在实习篇中给出了实习步骤和实习报告的规范。教学经验表明，严格实施这些貌似繁琐的规范，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将能起到显著的促进作用。
数据结构及其算法的教学难点在于它们的
抽象性和动态性。虽然在书本教材和课堂授课（板书或投影胶片）中采用图示可以在一定程度上化抽象为直观，但很难有效展现数据结构的瞬间动态特性和算法的作用过程。在随教科书配发的光盘中，“数据结构的算法动态模拟辅助教学软件DSDEMO”是为学习并掌握数据结构中各类典型算法而开发的一个辅助教学软件，可对教科书中八十余个典型算法进行动态交互式跟踪演示，在算法执行过程中实现数据结构和算法的动态同步可视化，使学生获得仅从教材文字说明中无法获得的直观知识。软件既可用于课堂讲解演示，又能供个人课外反复观察、体会和理解，对提高教学质量和效率有显著效果。在习题篇的每一章列举了与该章相关的算法清单，并在《数据结构题集》附录中提供该软件完整的使用说明。
1.2 作业和实验安排
根据教学计划，数据结构课程的实验和上机由三部分构成：
1． 算法设计实验和上机（30机时）
在“数据结构算法设计作业系统”上机完成40道必做题，学有余力的同学还可以选做另外40道选做题。
2． 抽象数据类型的实现（6学时设计性实验）
实现一个抽象数据类型，并对所采用的存储结构和相关操作的实现进行讨论。
3． 课程设计（一周综合性实验）
完成《数据结构题集》中的一至两个实习题。
第2章 算法设计实验和上机
2.1 数据结构习题概述
《数据结构题集》把数据结构的习题分为“基础知识题”和“算法设计题”两类。
“基础知识题”主要供学生进行自测和复习之用，目的是帮助学生深化理解教科书的内容，澄清基本概念、理解和掌握数据结构中分析问题的基本方法和算法要点，为完成算法设计题做准备。
“算法设计题”则侧重于基本程序设计技能的训练，相对于实习题而言，这类编程习题属于偏重于编写功能单一的“小”程序的基础训练，然而，它是进行复杂程序设计的基础，是本课程习题作业的主体和重点。
各章的题量根据教学内容的多少和重要程度而定，几乎对教科书的每一小节都安排了对应的习题。但对每个学生来说，不必去解全部习题，而只须根据自己的情况从中选择若干求解即可。为了表明题目的难易程度，便于学生选择，在每个题的题号之后注了一个难度系数，难度级别从①至⑤逐渐加深，其区别大致如下：难度系数为①和②的习题以基础知识题为主；难度系数为③的习题以程序设计基础训练为主要目的，如强化对“指针”的基本操作的训练等；习题中也收纳了不少难题，其难度系数设为④和⑤，解答这些题可以激起学习潜力较大的学生的兴趣，对广泛开拓思路很有益。但习题的难度系数也只是一个相对量，学生的水平将随学习的进展而不断提高，因此没有必要去比较不同章节的习题的难度系数，此外，该难度系数值的假设是以学生没有参照习题的解答或提示为前提的。
“循序渐进”是最基本的学习原则。学习者不应该片面追求难题。对于解难度系数为i的习题不太费力的学生，应试试难度系数为i+1的习题，但不要把太多的时间浪费在难度系数为i+2的习题上。“少而精”和“举一反三”是实践证明行之有效的。解答习题应注重于“精”，而不要求“多”。为此，在一些值得向学生推荐的“好题”题号前加注了标记◆。把握住这些“关键点”，就把握住了数据结构习题、乃至数据结构课程的总脉络。
2.2 算法设计的上机作业要求
1．使用Anyview C语言和算法书写规范写出书面作业的算法（函数），作为上机前的准备。
需要强调的是“算法的可读性”。算法是为了让人来读的，而不是供机器读的。初学者总是容易忽视这一点。算法的真正意图主要在于提供一种在程序设计者之间交流解决问题方法的手段。因此，可读性具有头等的重要性。不可读的算法是没有用的，由它得到的程序极容易产生很多隐藏很深的错误，且难以调试正确。一般地说，宁要一个可读性好、逻辑清晰简单、但篇幅较长的算法，也不要篇幅较小但晦涩难懂的算法。算法的正确性力求在设计算法的过程中得到保证，然而一开始做不到这一点也没多大关系，可以逐步做到。
算法设计的正确方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略逐一地解决子问题，最后严格按照和使用本章后面提供的算法书写规范和类C语言完成算法的最后版本。
按照规范书写算法是一个值得高度重视的问题。在基础训练中就贯彻这一规范，不但能够有助于写出“好程序”，避免形成一系列难以纠正且遗害无穷的程序设计坏习惯，而且能够培养软件工作者应有的严谨的科学工作作风。
2．对函数进行静态检查修改，形成准备上机的程序文本。
多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，查纠错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。
静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地分析理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。
3．在“Anyview C数据结构算法设计作业系统”编辑提交程序，并在系统的自动测试和提示下，调试程序，直到能通过系统的测试。
“Anyview C数据结构算法设计作业系统”提供了程序可视化运行和调试的环境，为进行数据结构教学的师生提供了算法设计作业程序的可视化自动测试环境。可在该集成环境编辑C源程序，并对其进行可视化运行、分析和调试。通过设置断点、单步或变换速度的连续运行，可在多个窗口上动态观察程序执行时的数据变量的物理和逻辑2D或3D视图，使得程序运行期间本来不可见的程序对数据的处理过程和数据之间的动态抽象关系全部可视化。在提交算法设计作业程序时，系统自动进行可视化测试，评判作业程序的正确性。通过对比“标准结果视图”和“作业结果视图”，作业者可对自己的程序进行直观的分析和排错。关于该作业系统的使用，请参阅系统的帮助文档。
在调试过程中可以不断借助系统的可视DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，这时不应“苦思冥想”，而应动手确定疑点，通过修改程序来证实它或绕过它。
4．在调试程序的过程中，做好调试笔记，记录心得体会。
调试正确后，认真整理源程序及其注释，记录带有完整注释的且格式良好的源程序清单和结果。
一道算法设计作业文档包括：
（1）上机前编写并经过静态检查的程序文本；
（2）调试笔记；
（3）最后程序文本，及通过时间。
2.3 算法设计上机作业
1．作业内容和机时
40道必做题，40道选做题。每年作适当调整更换。
6个课内实验机时，教师现场指导答疑。
24个课外训练机时，实验教师指导答疑。
学生平时可以在互联网上登录系统，做选做题。
2．算法设计题目文档
系统为每道算法设计题提供一个题目文档，包括以下内容：
（1）题目；
（2）算法的函数原型；
（3）可用的类型定义和函数原型。
做题前，必须仔细阅读题目文档，正确理解题目和做题要求。
第3章 抽象数据类型的实现
3.1 实验概要
实验项目名称: 抽象数据类型的实现
实验项目性质: 设计性实验
所属课程名称: 数据结构
实验计划学时: 6
3.2 实验目的
对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。 进而达到熟练地运用本课程中的基础知识及技术的目的。
3.3 预习与参考
1．确定要实现的抽象数据类型，并对基本操作做适当的选取和增加；
2．选择存储结构，并写出相应的类型定义；
3．设计各基本操作的实现算法，并表达为函数形式；
4．设计测试方案，编写主函数；
5．将上述4步的结果写成预习报告。
3.4 实验要求和设计指标
以教材中线性表，串，稀疏矩阵，广义表，二叉树，树，图以及查找表等抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个抽象数据类型。
可选的抽象数据类型如下表所列：
注：如果基本操作数量较多，可选择实现其中一个基本操作子集。
实验要求如下：
1．参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。
2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。
3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。
4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。
3.5 实验仪器设备和材料
软件实验室。
编程环境：Anyview C可视化编程环境、TC++、C++Builder或者VC++。
3.6 调试及结果测试
调试内容应包括：调试过程中遇到的问题是如何解决的以及对实验的讨论与分析；基本操作的时间复杂度和空间复杂度的分析和改进设想。列出对每一个基本操作的测试结果，包括输入和输出，测试数据应完整和严格。
3.7 考核形式
考核形式以实验过程和实验报告相结合的方式进行。在实验完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算实验部分的结束。实验报告作为整个设计性实验评分的书面依据。设计性实验的成绩评定以选定题目的难易度、完成情况和实验报告为依据综合评分。从总体来说，所实现的抽象数据类型应该全部符合要求，类型定义，各基本操作的算法以及存储结构清晰；各模快测试运行正确；程序的结构合理；设计报告符合规范。
3.8 实验报告要求
实验结束后要写出实验报告，以作为整个设计性实验评分的书面依据和存档材料。实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容。本设计性实验的报告要包括以下几项内容：
（1）设计任务、要求及所用软件环境或工具；
（2）抽象数据类型定义以及各基本操作的简要描述；
（3）所选择的存储结构描述及在此存储结构上各基本操作的实现；
（4）程序清单（计算机打印），输入的数据及各基本操作的测试结果；
（5）实验总结和体会。
实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。
3.9 思考题
对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。
3.10 示例
1. 题目
采用字符类型为元素类型和无头结点单链表为存储结构，实现抽象数据类型List。
ADT List{
数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }
基本操作：
SetEmpty(&L)
操作结果：构造一个空的线性表L。
Destroy(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
Length(L)
初始条件：线性表L已存在。
操作结果：返回L中元素个数。
Get(L, i, &e)
初始条件：线性表L已存在，1≤i≤LengthList(L)。
操作结果：用e返回L中第i个元素的值。
Locate(L, e, compare())
初始条件：线性表L已存在，compare()是元素判定函数。
操作结果：返回L中第1个与e满足关系compare()的元素的位序。
若这样的元素不存在，则返回值为0。
Insert(&L, i, e)
初始条件：线性表L已存在，1≤i≤LengthList(L)+1。
操作结果：在L的第i个元素之前插入新的元素e，L的长度加1。
Delete(&L, i, &e)
初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。
操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。
Display(L)
初始条件：线性表L已存在。
操作结果：依次输出L的每个元素。
} ADT List
2．存储结构定义
公用头文件DS0.h:
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <values.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define IBFEASIBLE -1
#define OVERFLOW -2
#define MAXLEN 20
#define MAXSIZE 20
typedef int Status;
typedef char ElemType; /* 元素类型为字符类型*/
（1） 顺序存储结构
#define LIST_INIT_SIZE 20 /*线性表存储空间的初始分配量*/
#define LISTINCREMENT 10 /*线性表存储空间的分配增量*/
typedef struct{
ElemType *elem; /*存储空间基址*/
int length; /*当前长度*/
int listsize; /*当前分配的存储容量*/
} SqList;
（2） 无头结点单链表存储结构
typedefstruct LNode {
ElemType data;
struct LNode *next;
} LNode, *LList; /* 不带头结点单链表类型*/
（3） 带头结点单链表存储结构
typedefstruct LNode { /* 结点类型 */
ElemType data;
struct LNode *next;
} LNode, *Link, *Position;
typedefstruct LinkList { /* 链表类型 */
Link head,tail; /* 分别指向线性链表中的头结点和最后一个结点 */
int len; /* 指示线性链表中数据元素的个数 */
} LinkList;
3. 算法设计
（1） 顺序存储结构
Status SetEmpty(SqList &L) { /*构造一个空的顺序线性表 */
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
return OVERFLOW; /* 存储分配失败 */
L.length=0; /* 空表长度为0 */
L.listsize=LIST_INIT_SIZE; /* 初始存储容量 */
return OK;
}
Status Destroy (SqList &L) { /*销毁顺序线性表L */
free(L.elem);
L.elem=NULL;
L.length=0;
L.listsize=0;
return OK;
}
int Length(SqList L) { /* 求表长*/
return L.length;
}
Status Get(SqList &L, int i, ElemType &e) { /* 获取第i元素 */
if(i<1||i>L.length)
return ERROR;
e=*(L.elem+i-1);
return OK;
}
int Locate(SqList L, ElemType x) { /* 确定x在表中的位序 */
ElemType *p;
int i=1; /* i的初值为第1个元素的位序 */
p=L.elem; /* p的初值为第1个元素的存储位置 */
while(i<=L.length && *p++!=x)
++i;
if(i<=L.length)
return i;
else
return 0;
}
Status Insert(SqList &L, int i, ElemType e) {
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
ElemType *newbase,*q,*p;
if(i<1||i>L.length+1) /* i值不合法 */
return ERROR;
if(L.length>= L.listsize) { /* 当前存储空间已满,增加分配 */
newbase=(ElemType *) realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) return OVERFLOW; /* 存储分配失败 */
L.elem=newbase; /* 新基址 */
L.listsize+=LISTINCREMENT; /* 增加存储容量 */
}
q=L.elem+i-1; /* q为插入位置 */
for(p=L.elem+L.length-1; p>=q; --p)
*(p+1)=*p; /* 插入位置及之后的元素右移 */
*q=e; /* 插入e */
++L.length; /* 表长增1 */
return OK;
}
Status Delete(SqList &L, int i, ElemType &e) {
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
ElemType *p,*q;
if(i<1||i> L.length) /* i值不合法 */
return ERROR;
p= L.elem+i-1; /* p为被删除元素的位置 */
e=*p; /* 被删除元素的值赋给e */
q= L.elem+L.length-1; /* 表尾元素的位置 */
for(++p; p<=q; ++p) /* 被删除元素之后的元素左移 */
*(p-1)=*p;
L.length--; /* 表长减1 */
return OK;
}
Status Display(SqList L) { /* 依次显示表中元素 */
ElemType *p;
int i;
p=L.elem;
printf("( ");
for(i=1; i<=L.length; i++)
printf("%c",*p++);
printf(" )\n");
return OK;
}
（2） 无头结点单链表
void SetEmpty(LList &L) { /* 置无头结点的空单链表*/
L=NULL;
}
Status Destroy (LList &L) { /* 销毁链表*/
LList q=L;
while(L) {
L=L->next;
free(q);
q=L;
}
return OK;
}
int Length(LList L) { /* 求表长*/
int n=0;
while(L!=NULL) {
n++;
L=L->next;
}
return n;
}
Status Get(LList L, int i, ElemType &e) { /* 获取第i元素 */
int j=1;
while (j<i && L!=NULL) {
L=L->next;
j++;
}
if(L!=NULL) { e=L->data; return OK; }
elsereturn ERROR; /* 位置参数i不正确 */
}
int Locate(LList L, ElemType x) { /* 确定x在表中的位序 */
int n=1;
while (L!=NULL && L->data!=x) {
L=L->next;
n++;
}
if (L==NULL) return 0;
else return n;
}
Status Insert(LList &L, int i, ElemType e) { /* 插入第i元素*/
int j=1;
LList s,q;
s=(LList)malloc(sizeof(LNode));
s->data=e;
q=L;
if (i==1) { s->next=q; L=s; return OK;}
else {
while(j<i-1 && q->next!=NULL) {
q=q->next;
j++;
}
if (j==i-1) {
s->next=q->next;
q->next=s;
return OK;
}
elsereturn ERROR; /* 位置参数i不正确 */
}
}
Status Delete(LList &L, int i, ElemType &e) { /* 删除第i元素*/
int j=1;
LList q=L,t;
if (i==1) {
e=q->data;
L=q->next;
free(q);
return OK;
}
else {
while (j<i-1 && q->next!=NULL) {
q=q->next;
j++;
}
if (q->next!=NULL && j==i-1) {
t=q->next;
q->next=t->next;
e=t->data;
free(t);
return OK;
}
else return ERROR; /* 位置参数i不正确*/
}
}
void Display(LList L) { /* 依次显示表中元素 */
printf("单链表显示: ");
if (L==NULL)
printf("链表为空!");
elseif (L->next==NULL)
printf("%c\n", L->data);
else {
while(L->next!=NULL) {
printf("%c->", L->data);
L=L->next;
}
printf("%c", L->data);
}
printf("\n");
}
（3） 带头结点单链表
Status SetEmpty(LinkList &L) { /* 置带头结点的空单链表*/
Link p;
p=(Link)malloc(sizeof(LNode)); /* 生成头结点 */
if(p) {
p->next=NULL;
L.head=L.tail=p;
L.len=0;
return OK;
}
else
return ERROR;
}
Status Destroy(LinkList &L) { /* 销毁线性链表L，L不再存在 */
Link p,q;
if(L.head!=L.tail) { /* 不是空表 */
p=q= L.head->next;
L.head->next=NULL;
while(p!=L.tail) {
p=q->next;
free(q);
q=p;
}
free(q);
}
free(L.head);
L.head=L.tail=NULL;
L.len=0;
return OK;
}
int Length(LinkList L) { /* 返回线性链表L中元素个数 */
return L.len;
}
Status Get(LinkList L, int i, ElemType &e) { /* 获取第i元素 */
/* i=0为头结点 */
Link p;
int j;
if(i<1||i>L.len)
return ERROR;
else{
p=L.head;
for(j=1;j<=i;j++)
p=p->next;
e=p->data;
return OK;
}
}
int Locate(LinkList L, ElemType x) { /* 确定x在表中的位序 */
int i=0;
Link p=L.head;
do {
p=p->next;
i++;
} while(p && p->data!=x); /* 没到表尾且没找到满足关系的元素 */
if (!p)
return 0;
else
return i;
}
Status Insert(LinkList &L, int i, ElemType e) { /* 插入第i元素*/
int j=0;
Link s,q;
s=(Link)malloc(sizeof(LNode));
s->data=e;
q=L.head;
while(j<i-1 && q->next!=NULL) {
q=q->next;
j++;
}
if (j==i-1) {
s->next=q->next;
q->next=s;
if (L.tail==q) L.tail=s;
L.len++;
return OK;
}
elsereturn ERROR; /* 位置参数i不正确 */
}
Status Delete(LinkList &L, int i, ElemType &e) {
/* 删除第i元素*/
int j=0;
Link q=L.head,t;
while (j<i-1 && q->next!=NULL) {
q=q->next;
j++;
}
if (q->next!=NULL && j==i-1) {
t=q->next;
q->next=t->next;
e=t->data;
if(L.tail==t) L.tail=q;
free(t);
L.len--;
return OK;
}
else return ERROR; /* 位置参数i不正确*/
}
void Display(LinkList L) { /* 依次显示表中元素 */
Link p;
printf("单链表显示: ");
if (L.head==L.tail)
printf("链表为空!");
else {
p=L.head->next;
while(p->next!=NULL) {
printf("%c->", p->data);
p=p->next;
}
printf("%c", p->data);
}
printf("\n");
}
4．测试
（1） 顺序存储结构
SqList head;
void main() { /* 主函数*/
char e,c;
int i,n,select,x1,x2,x3,x4,m,g;
SetEmpty(head);
n=random(8); /* 随机产生表长 */
for (i=1; i<=n; i++) { /* 将数据插入到顺序表中 */
c='A'+random(26);
Insert(head,i,c);
}
do{
Display(head);
printf("select 1 求长度 Length()\n");
printf("select 2 取结点 Get()\n");
printf("select 3 求值查找 Locate()\n");
printf("select 4 删除结点 Delete()\n");
printf("input your select: ");
scanf("%d",&select);
switch(select) {
case 1: x1=Length(head);
printf("顺序表的长度:%d ",x1);
break;
case 2: printf("请输入要取的结点序号: ");
scanf("%d",&m);
if(Get(head,m,x2)) printf("%c\n",x2);
else printf("错误\n");
break;
case 3: printf("请输入要查找的数据元素: ");
scanf("\n%c",&e);
x3=Locate(head,e);
printf("%d\n",x3);
break;
case 4: printf("请输入要删除的元素序号: ");
scanf("%d",&g);
if(Delete(head,g,x4)) printf("%c\n",x4);
else printf("错误\n");
break;
}
} while (select>0 && select <5);
}
（2） 无头结点单链表
LList head;
void main() { /* 主函数*/
char e,c;
int i,n,select,x1,x2,x3,x4,m,g;
SetEmpty(head);
n=random(8); /* 随机产生表长 */
for (i=1; i<=n; i++) { /* 将数据插入到顺序表中 */
c='A'+random(26);
Insert(head,i,c);
}
do{
Display(head);
printf("select 1 求长度 Length()\n");
printf("select 2 取结点 Get()\n");
printf("select 3 求值查找 Locate()\n");
printf("select 4 删除结点 Delete()\n");
printf("input your select: ");
scanf("%d",&select);
switch(select) {
case 1: x1=Length(head);
printf("顺序表的长度:%d ",x1);
break;
case 2: printf("请输入要取的结点序号: ");
scanf("%d",&m);
if(Get(head,m,x2)) printf("%c\n",x2);
else printf("错误\n");
break;
case 3: printf("请输入要查找的数据元素: ");
scanf("\n%c",&e);
x3=Locate(head,e);
printf("%d\n",x3);
break;
case 4: printf("请输入要删除的元素序号: ");
scanf("%d",&g);
if(Delete(head,g,x4)) printf("%c\n",x4);
else printf("错误\n");
break;
}
} while (select>0 && select <5);
}
（3） 带头结点单链表
LinkList head;
void main() { /* 主函数*/
char e,c;
int i,n,select,x1,x2,x3,x4,m,g;
SetEmpty(head);
n=random(8); /* 随机产生表长 */
for (i=1; i<=n; i++) { /* 将数据插入到顺序表中 */
c='A'+random(26);
Insert(head,i,c);
}
do {
Display(head);
printf("select 1 求长度 Length()\n");
printf("select 2 取结点 Get()\n");
printf("select 3 求值查找 Locate()\n");
printf("select 4 删除结点 Delete()\n");
printf("input your select: ");
scanf("%d",&select);
switch(select) {
case 1: x1=Length(head);
printf("顺序表的长度:%d ",x1);
break;
case 2: printf("请输入要取的结点序号: ");
scanf("%d",&m);
if(Get(head,m,x2)) printf("%c\n",x2);
else printf("错误\n");
break;
case 3: printf("请输入要查找的数据元素: ");
scanf("\n%c",&e);
x3=Locate(head,e);
printf("%d\n",x3);
break;
case 4: printf("请输入要删除的元素序号: ");
scanf("%d",&g);
if(Delete(head,g,x4)) printf("%c\n",x4);
else printf("错误\n");
break;
}
} while (select>0 && select<5);
}
5．三种存储结构的比较
6．思考与小结
（1）无头结点单链表的插入和删除操作的实现，要区分该表是否为空，并编写相应的代码。
（2）在算法设计时，要注意判断有关参数值的合法性。
（3）三种存储结构的主函数相同。设计主函数及测试运行时，要考虑测试的完备性。
7．预习报告和实验报告
（1）预习报告：包括1-4步的初稿。
（2）实验报告：在预习报告的基础上，增加在实验中，对算法修改核调试的收获体会，以及思考和小结的内容。
第4章 课程设计
4.1 课程设计概述
课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，课程设计题目中的问题比平时的习题复杂得多，也更接近实际。实习着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而课程设计是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的检查者。
为了达到上述目的，《数据结构题集》安排了六个课程设计（实习）单元。训练重点在于基本的数据结构，而不强调面面俱到。各课程设计单元与教科书的各章只具有粗略的对应关系，一个课程设计题目常常涉及几部分教学内容。在每个课程设计单元中安排了难度不等的4～9个实习题，每个题目的题号之后标有难度系数，对于特别推荐题也作了标记。与习题的情况类似，在一个单元之内比较题目难度才有意义。此外，难度系数是根据题目的基本要求而给出的。
每个课程设计题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等五个部分组成。
问题描述旨在为学生建立问题提出的背景环境，指明问题“是什么”。
基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求。
测试数据部分旨在为检查学生上机作业提供方便。在完成课程设计题目时，应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据。
在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示。
选做部分向那些尚有余力的学生提出了更严峻的挑战，同时也能开拓其他学生的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。
不难发现，这里与传统的做法不同，题目设计得非常详细。会不会限制学生的想象力，影响创造力的培养呢？回答是：软件发展的一条历史经验就是要限制程序设计者在某些方面的创造性，从而使其创造能力集中地用到特别需要创造性的环节之上。课程设计题目本身就给出了问题说明和问题分解求精的范例，使学生在无形中学会模仿，它起到把学生的思路引上正轨的作用，避免坏结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查。题目的设计策略是：一方面使其难度和工作量都较大，另一方面给学生提供的辅助和可以模仿的成分也较多。当然还应指出的是，提示的实现方法未必是最好的，学生不应拘泥于此，而应努力开发更好的方法和结构。
在每个课程设计单元中，每人可以从中选做一个实习题。经验表明，如果某题的难度略高于自己过去所对付过的最难题目的难度，则选择此题能够带来最大的收益。切忌过分追求难题。较大的题目，或是其他题目加上某些选做款项适合于多人合作。
4.2 课程设计时间和内容
数据结构课程设计通常安排在数据结构课程结束后，要求用一周时间，完成《数据结构题集》中实习一至六这六个单元中的一至两个题目。
在课程的实际教学中，可以适时启动课程设计。比如，如果要求完成两个题目，可在学习线性结构（线性表、栈、队列和串）之后，先选做实习一至三中的一个题目。然后，再在实习四至六中选做一个题目。
4.3 课程设计步骤
《数据结构题集》为实习制定了严格的规范。一种普遍存在的错误观念是，调试程序全凭运气。学生花两个小时的上机时间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实习步骤规范进行实习不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。
（一）问题分析与系统概要设计
充分地分析和理解问题，明确题目要求做什么（而不是怎样做）和限制条件是什么。按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。作为概要设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），画出模块之间的调用关系图，以及设计测试方案。这是一个不断调整的过程。基本操作的规格说明应尽可能明确具体。
（二）详细设计与编码
本步骤主要是确定数据结构的存储表示和实现抽象数据类型。详细设计就是要对数据结构和基本操作的规格说明作进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出过程或函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。
编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60各字符。每个过程（函数）体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应该分割成较小的过程（函数）。要控制if语句连续嵌套的深度。其他要求参见第一篇的算法书写规范。如何编写程序才能较快地完成调试是特别要注意的问题。
（三）上机准备和静态检查
上机准备包括以下几方面：
（1）高级语言文本（体现与编译程序用户手册）的扩充和限制。
（2）如果用C++语言，要特别注意平时惯用的类C语言与C++语言之间的细微差别。
（3）熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。
（4）掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG调试程序。
上机动态调试前应先进行静态检查，以提高调试效率。
（四）上机调试程序
上机时要带上语言教材或手册。调试最好分模块进行，自底向上，即先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。
在调试过程中可以借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，这时不应“苦思冥想”，而应动手设法确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，记录带有完整注释的且格式良好的源程序清单和结果。
（五）整理课程设计报告
课程设计报告必须采用学校统一规定的报告封面，在首页给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1. 需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：
⑴ 输入的形式和输入值的范围；
⑵ 输出的形式；
⑶ 程序所能达到的功能；
⑷ 测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2. 概要设计
说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的调用关系。
3. 详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法需要达到的详细程度为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。
4. 调试分析
内容包括：
⑴ 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；
⑵ 算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想；
⑶ 经验和体会等。
5. 用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤；
6. 测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
7. 附录
带注释的源程序。如果提交源程序软盘，可以只列出程序文件名清单。
在各课程设计单元中都提供了实习报告实例。必须注意的是，实习报告的各种文档资料要在程序开发的过程中逐渐充实形成，而不能最后补写（当然可以也应该最后用实验报告纸誊清或打印）。
4.4 课程设计报告范例
《数据结构题集》在每个实习单元提供了一个完整的示例，在起到了报告规格范例作用的同时，还隐含地显示了很多有益的东西，比如，基于数据结构的系统划分方法；递归算法设计方法和技巧；对于有天然递归属性的问题如何构造非递归算法；如何在编写程序的时候就为调试提供方便；如何支持动态的断言检测；下标增量技术；赋值形参/引用形参与全局量的设计考虑；如何恰当地在程序中加入注释和断言能获得较好的可读性；以及所提倡的程序设计风格等等。
4.5 课程设计考核形式和评分标准
1．在程序运行界面突出显示设计者的班级、学号和姓名。课程设计结束前，进行程序运行检查和答辩。
2．提交课程设计报告（打印）和光盘。各班统一制作一张光盘，每人一个目录，每题一个子目录，内含：源程序文件、可执行程序文件、测试用例和课程设计报告WORD文档。
3．成绩采用五级评分制：优，良，中，及格和不及格。
根据题目的难度、选做内容、完成的程序和报告的质量评定成绩。
只完成基本内容者，成绩至高为“良”。
鼓励完成选做内容，可获得加分到“优”。
鼓励采用Windows环境编程。
如果有下列情况，则视情节严重程度，成绩下降若干档次，直至不及格：
· 盘中文件含有病毒或者内容不能正确读出；
· 抄袭、复制别人程序或文档；
· 未能按时提交报告和光盘。