数据结构教程

数据结构教程第一课：数据结构的基本概念和术语第二课：抽象数据类型的表示与实现第三课：算法及算法设计要求第四课：算法效率的度量和存储空间需求第五课：线性表的类型定义第六课：线性表的顺序表示和实现第七课：实验一线性表的顺序存储实验第八课：线性表的链式表示与实现第九课：循环链表与双向链表第十课：栈的表示与实现第十一课：栈的应用第十二课：实验二循环链表实验第十三课：队列第十四课：串的定义第十五课：串的表示和实现第十六课：串操作应用举例第十七课：实验三：栈的表示与实现及栈的应用第十八课：数组的顺序表示与实现第十九课：实验四串的实现实验第二十课：广义表第二十一课：树、二叉树定义及术语第二十二课：实验五数组实验第二十三课：二叉树的存储结构第二十四课：遍历二叉树第二十五课：单元测验第二十六课：图的定义与术语第二十七课：实验六二叉树实验第二十八课：图的存储结构第二十九课：静态查找表（一）顺序表的查找第三十课：静态查找表（二）有序表的查找第三十一课：动态查找表第三十二课：哈希表（一）第三十三课：哈希表（二）第三十四课：插入排序，快速排序第三十五课：实验七查找第三十六课：选择排序，归并排序第三十七课：实验八排序实验第三十八课：文件概念，顺序文件第三十九课：索引文件第四十课：总复习第一课本课主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常用术语教学重点：基本概念：数据与数据元素教学难点：数据元素间的四种结构关系。授课内容：一、数据、数据元素、数据对象、数据结构的定义1、数据的定义定义一：数据是客观事物的符号表示。学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。定义二：能输入到计算机中并被计算机程序处理的符号的总称。例：图像、声音等。总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。2、数据元素、数据项数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：3、数据对象是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。4、数据结构定义一、数据元素集合（也可称数据对象）中各元素的关系。定义二、相互之间存在特定关系的数据元素集合。数据结构的种类：特征示例集合元素间为松散的关系线性结构元素间为严格的一对一关系如上面的成绩表中各元素树形结构元素间为严格的一对多关系图状结构（或网状结构）元素间为多对多关系数据结构的形式定义：数据结构名称=（D，S）其中D为数据元素的有限集，S是D上关系的有限集逻辑结构“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。存储结构数据结构在计算机中的表示称为物理结构。又称存储结构。顺序存储结构链式存储结构存储结构详解：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(DataField)。例：上述成绩表数据用C语言的结构体数组classonestu[50]来存储：structstu{intstuno;/*数据项，也称stu位串中的一个子位串，或叫做数据域*/charname[20];intmaths;intlanguage;intc_language;}classonestu[50];二、数据类型1、定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。2、数据类型的种类：特征例原子类型值在逻辑上不可分解intfloat结构类型值由若干成分按某种结构组成structstu数据类型封装了数据存储与操作的具体细节。三、总结数据-数据元素具有特定关系的数据元素集合-数据结构数据结构的逻辑表示与物理存储-逻辑结构与存储结构人们不仅关心数据的逻辑结构、存储结构，还关心数据的处理方法（算法）与处理结果-数据类型数据类型-分类第二课本课主题：抽象数据类型的表示与实现教学目的：了解抽象数据类型的定义、表示和实现方法教学重点：抽象数据类型表示法、类C语言语法教学难点：抽象数据类型表示法授课内容：一、抽象数据类型定义（ADT）作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。抽象数据类型分类原子类型值不可分解，如int固定聚合类型值由确定数目的成分按某种结构组成，如复数可变聚合类型值的成分数目不确定如学生基本情况抽象数据类型表示法：一、三元组表示：（D，S，P）其中D是数据对象，S是D上的关系集，P是对D的基本操作集。二、书中的定义格式：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名例：线性表的表示名称线性表数据对象D={ai|ai(-ElemSet,i=1,2,...,n,n=0}任意数据元素的集合数据关系R1={ai-1,ai|ai-1,ai(-D,i=2,...,n}除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(&L,i,e)L为线性表，i为位置，e为数据元素。ListDelete(&L,i,e)...二、类C语言语法类C语言语法示例1、预定义常量和类型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefinStatus;//Status是函数的类型，其值是函数结果状态代码。2、数据结构的存储结构typedefElemTypefirst;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、逻辑运算&&与运算；||或运算例：线性表的实现：ADTList{数据对象:D={ai|ai(-ElemSet,i=1,2,...,n,n=0}数据关系:R1={ai-1,ai|ai-1,ai(-D,i=2,...,n}基本操作：InitList(&L)DestroyList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)}ADTListListInsert(List&L,inti,ElemTypee){if(i1||iL.length+)returnERROR;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}下面是C语言编译通过的示例：#defineERROR0#defineOK1structSTU{charname[20];charstuno[10];intage;intscore;}stu[50];structLIST{structSTUstu[50];intlength;}L;intprintlist(structLISTL){inti;printf(namestunoagescore\n);for(i=0;iL.length;i++)printf(%s%s\t%d\t%d\n,L.stu[i].name,L.stu[i].stuno,L.stu[i].age,L.stu[i].score);printf(\n);}intlistinsert(structLIST*L,inti,structSTUe){structSTU*p,*q;if(i1||iL-length+1)returnERROR;q=&(L-stu[i-1]);for(p=&L-stu[L-length-1];p=q;--p)*(p+1)=*p;*q=e;++L-length;returnOK;}/*ListInsertBeforei*/main(){structSTUe;L.length=0;strcpy(e.name,zmofun);strcpy(e.stuno,100001);e.age=80;e.score=1000;listinsert(&L,1,e);printlist(L);printf(Listlengthnowis%d.\n\n,L.length);strcpy(e.name,bobjin);strcpy(e.stuno,100002);e.age=80;e.score=1000;listinsert(&L,1,e);printlist(L);printf(Listlengthnowis%d.\n\n,L.length);}E:\ZM\Zmdoc\datastru\class02listdemonamestunoagescorezmofun100001801000Listlengthnowis1.namestunoagescorebobjin100002801000zmofun100001801000Listlengthnowis2.三、总结抽象数据类型定义；抽象数据类型实现方法：一、类C语言实现二、C语言实现回目录上一课下一课第三课本课主题：算法及算法设计要求教学目的：掌握算法的定义及特性，算法设计的要求教学重点：算法的特性，算法设计要求教学难点：算法设计的要求授课内容：一、算法的定义及特性1、定义：ispass(intnum[4][4]){inti,j;for(i=0;i4;i++)for(j=0;j4;j++)if(num[i][j]!=i*4+j+1)/*一条指令，多个操作*/return0;return1;}/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/算法是对特定问题求解步骤的一种描述，它是指令的有限序