数据结构教程.pdf

数据结构教程数据结构教程第一课：数据结构的基本概念和术语 第二课：抽象数据类型的表示与实现 第三课：算法及算法设计要求 第四课：算法效率的度量和存储空间需求 第五课：线性表的类型定义 第六课：线性表的顺序表示和实现 第七课：实验一 线性表的顺序存储实验 第八课：线性表的链式表示与实现 第九课：循环链表与双向链表 第十课：栈的表示与实现 第十一课：栈的应用 第十二课：实验二 循环链表实验 第十三课：队列 第十四课：串的定义 第十五课：串的表示和实现 第十六课：串操作应用举例 第十七课：实验三：栈的表示与实现及栈的应用 第十八课：数组的顺序表示与实现 第十九课：实验四 串的实现实验 第二十课：广义表 第二十一课：树、二叉树定义及术语 第二十二课：实验五 数组实验 第二十三课：二叉树的存储结构 第二十四课：遍历二叉树 第二十五课：单元测验 第二十六课：图的定义与术语 第二十七课：实验六 二叉树实验 第二十八课：图的存储结构 第二十九课：静态查找表（一）顺序表的查找 第三十课：静态查找表（二）有序表的查找 第三十一课：动态查找表 第三十二课：哈希表（一） 第三十三课：哈希表（二） 第三十四课：插入排序，快速排序 第三十五课：实验七 查找 第三十六课：选择排序，归并排序 第三十七课：实验八 排序实验 第三十八课：文件概念，顺序文件 第三十九课：索引文件 第四十课：总复习第一课第一课本课主题：本课主题：数据结构的基本概念和术语教学目的：教学目的：了解数据结构的基本概念，理解常用术语教学重点：教学重点：基本概念：数据与数据元素教学难点：教学难点：数据元素间的四种结构关系。

授课内容：授课内容：一、数据、数据元素、数据对象、数据结构的定义一、数据、数据元素、数据对象、数据结构的定义1、数据的定义定义一：数据是客观事物的符号表示学号姓名语文数学C 语言6201001张三8554926201002李四9284646201003王五8774736201004...例：张三的 C 语言考试成绩为 92 分，92 就是该同学的成绩数据定义二：能输入到计算机中并被计算机程序处理的符号的总称例：图像、声音等总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据2、数据元素、数据项数据元素是数据的基本单位，它也可以再由不可分割的数据项组成如图示：3、数据对象是性质相同的数据元素的集合如上例：一个班级的成绩表可以看作一个数据对象4、数据结构定义一、数据元素集合（也可称数据对象）中各元素的关系定义二、相互之间存在特定关系的数据元素集合数据结构的种类：特征示例集合元素间为松散的关系线性结构元素间为严格的一对一关系如上面的成绩表中各元素树形结构元素间为严格的一对多关系图状结构 （或网状结构）元素间为多对多关系数据结构的形式定义：数据结构名称=（D，S）其中 D 为数据元素的有限集，S 是 D 上关系的有限集逻辑结构“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。

存储结构数据结构在计算机中的表示称为物理结构又称 存储结构顺序存储结构链式存储结构 存储结构详解：计算机中存储信息的最小单位：位位，8 位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串在逻辑描述中，把位串称为元素或结点结点当数据元素由若干数据项组成时， 位串中对应于各个数据项的子位串称为数据域数据域(Data Field)例：上述成绩表数据用 C 语言的结构体数组 classonestu[50]来存储：struct stu {int stuno;/*数据项，也称 stu 位串中的一个子位串，或叫做数据域*/char name[20];int maths;int language;int c_language;} classonestu[50];二、数据类型二、数据类型1、定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称例：C 语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、 比较大小操作 而实型则无取模操作 当然整型也不需四舍五入2、数据类型的种类：特征例原子类型 值在逻辑上不可分解int float结构类型 值由若干成分按某种结构组成struct stu数据类型封装了数据存储与操作的具体细节。

三、总结三、总结数据->数据元素具有特定关系的数据元素集合->数据结构数据结构的逻辑表示与物理存储->逻辑结构与存储结构人们不仅关心数据的逻辑结构、存储结构，还关心数据的处理方法（算法）与处理结果->数据类型数据类型->分类第二课第二课本课主题：本课主题：抽象数据类型的表示与实现教学目的：教学目的：了解抽象数据类型的定义、表示和实现方法教学重点：教学重点：抽象数据类型表示法、类 C 语言语法教学难点：教学难点：抽象数据类型表示法授课内容：授课内容：一、抽象数据类型定义（一、抽象数据类型定义（ADTADT））作用：抽象数据类型可以使我们更容易描述现实世界例：用线性表描述学生成绩表，用树或图描述遗传关系定义：一个数学模型以及定义在该模型上的一组操作关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式定义它的人同样不必要关心它如何存储例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继可以有这样一些操作：插入一个元素、删除一个元素等抽象数据类型分类原子类型值不可分解，如 int固定聚合类型值由确定数目的成分按某种结构组成，如复数可变聚合类型值的成分数目不确定如学生基本情况抽象数据类型表示法：一、三元组表示：（三元组表示：（D D，，S S，，P P））其中其中 D D 是数据对象，是数据对象，S S 是是 D D 上的关系集，上的关系集，P P 是对是对 D D 的基本操作集。

的基本操作集二、书中的定义格式：ADTADT 抽象数据类型名抽象数据类型名{ { { {数据对象：数据对象： >数据关系：数据关系： >基本操作：基本操作： >} } } }ADTADT 抽象数据类型名抽象数据类型名例：线性表的表示名称线性表数据对象 D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 任意数据元素的集合数据关系 R1={| ai-1,ai(- D,i=2,...,n}除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert( //Status 是函数的类型，其值是函数结果状态代码2、数据结构的存储结构typedef ElemType first;3、基本操作的算法函数类型 函数名（函数参数表）{//算法说明语句序列}//函数名4、赋值语句简单赋值：变量名=表达式；串联赋值：变量名 1=变量名2=...=变量名 k=表达式；成组赋值:（变量名 1，...,变量名 k） = （表达式 1， ...,表达式 k);结构名=结构名；结构名=（值 1，...，值 k);变量名[]=表达式；变量名[起始下标..终止下标]=变量名[起始下标..终止下标]；交换赋 值：变量名变量名；条件赋变量名=条件表达式？表达式？表值：达式 T：表达式 F5、 选择语句1、if（表达式） 语句；2、if（表达式） 语句；else 语句；3、switch(表达式）{case 值 1：语句序列 1；break;...case 值 n：语句序列 n；break;default:语句序列 n+1；break;}4、switch{case 条件 1：语句序列 1；break;...case 条件 n：语句序列 n；break;default:语句序列 n+1；break;}6、 循环语句for （赋初值表达式； 条件； 修改表达式序列）语句；while（条件）语句；do{ 语句序列}while（条件）；7、 结束语句return [表达式]；return; //函数结束语句break; //case 结束语句exit(异常代码); //异常结束语句8、 输入和输出语句scanf（[格式串]，变量 1，...,变量 n）；9、 注释//文字序列10、基本函数max（表达式 1，...，表达式 n）min,abs,floor,ceil,eof,eoln11、逻辑运算q=for(p=p>=q;--p) *(p+1)=*p;*q=e;++L.length;return OK;}下面是 C 语言编译通过的示例：#define#define#define#defineERRORERRORERRORERROR 0 0 0 0#define#define#define#defineOKOKOKOK 1 1 1 1structstructstructstruct STUSTUSTUSTU{ { { { charcharcharchar name[20];name[20];name[20];name[20];charcharcharchar stuno[10];stuno[10];stuno[10];stuno[10];intintintint age;age;age;age; intintintint score;score;score;score;}stu[50];}stu[50];}stu[50];}stu[50];structstructstructstruct LISTLISTLISTLIST{ { { { structstructstructstruct STUSTUSTUSTU stu[50];stu[50];stu[50];stu[50];intintintint length;length;length;length;}L;}L;}L;}L;intintintint printlist(structprintlist(structprintlist(structprintlist(struct LISTLISTLISTLIST L)L)L)L){ { { { intintintint i; i; i; i;printf(“nameprintf(“nameprintf(“nameprintf(“name stunostunostunostunoageageageage score\n“);score\n“);score\n“);score\n“);for(i=0;iL->length+1)(iL->length+1)(iL->length+1)(iL->length+1)returnreturnreturnreturnERROR;ERROR;ERROR;ERROR;q=q=q=q=for(p=p>=q;--p)for(p=p>=q;--p)for(p=p>=q;--p)for(p=p>=q;--p)*(p+1)=*p;*(p+1)=*p;*(p+1)=*p;*(p+1)=*p;*q=e;*q=e;*q=e;*q=e; ++L->length;++L->length;++L->length;++L->length;returnreturnreturnreturnOK;OK;OK;OK;}/*ListInsert}/*ListInsert}/*ListInsert}/*ListInsertBeforeBeforeBeforeBefore i i i i */ */ */ */main()main()main()main(){ { { { structstructstructstruct STUSTUSTUSTU e;e;e;e;L.length=0;L.length=0;L.length=0;L.length=0;strcpy(e.name,“zmofun“);strcpy(e.name,“zmofun“);strcpy(e.name,“。