第一篇：数据结构讲稿-第一次课-DS绪论
《数据结构》教案
课程性质和任务
本课程是计算机专业的主要专业基础课程之一。本课程的参考教学时数为54学时，实际讲课学时为35，实验学时为16。其主要内容包括顺序表、链表、栈、队、串、树和图的结构，以及查找和排序技术。通过本课程的教学，使学生理解计算机软件系统所必须的数据结构及算法的内部逻辑，掌握在软件工程中大量存在的查找和排序技术，并通过大量的上机实习，实现各种数据结构的算法，以便为后续课程的学习提供专业基础知识，同时增强学生编制程序的能力。
课程教学目标
通过本课程的学习，应达到以下目标：
深刻理解数据结构中线性表、栈、队和链的概念、算法及其基本应用。
理解树的基本概念，学会建立二叉树，并在二叉树上进行查找、插入和删除等各种运算。
理解图的基本结构和算法，了解图的路径问题。
熟练掌握几种重要的内部排序和查找技术，了解外部排序的一般过程。
能熟练地运用C语言，准确、清晰地编制与本课程有关的算法，并能上机调试通过。
新疆农业大学数据结构课程教案
第一讲 绪论(对应教材p1—p17)
一、教学目的和要求
要求掌握数据结构中基本概念的定义，理解数据结构研究的主要内容，了解抽象数据类型的表示和实现，理解算法评价的两个指标。
二、授课主要内容
1.数据结构研究的主要内容 2.数据结构中涉及的基本概念
3.算法的概念、描述方法以及评价标准
三、教学重点难点
数据结构中的基本概念、算法的概念、描述方法以及评价标准
四、授课内容和方法
【口述】当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。
一、什么是数据结构
我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。
1、举例说明
图书馆的书目检索自动化问题----计算机处理的对象之间存在着线性关系，称为线性的数据结构。
人机对奕问题----计算机处理的对象是一个个格局。所有可能出现的格局是一棵倒置的树。
多岔路口交通灯的管理问题----数学模型是图的数学结构。
【由以上举例引出下列结论：】
非数值计算问题的数学模型是表、树和图之类的数据结构。【总结出定义】 数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。（三个要素：对象、关系及操作（运算））
2、《数据结构》课程的介绍
1968年美国克努特教授开创了数据结构的最初体系： 数据的逻辑结构和存储结构及其操作。
数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。
二、基本概念和术语
1、数据 数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机
加工的“原料”。
数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。
2、数据对象、数据结构
数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构的形式定义：数据结构是一个二元组
Data_Structure=(D,S)其中，D 是数据元素的有限集，S 是D上关系的有限集。
例：复数 Complex=(C,R)例：课题小组 Group=(P,R)P={T,G1,„,Gn,S11,„,Snm}1≤n≤3，1≤m≤2，R={R1,R2} R1={
① 逻辑结构：数据元素之间的逻辑关系。
② 存储结构(物理结构)：数据元素及其关系在计算机存储器的表示。用于表示数据元素的位串称之为元素或结点。用于表示数据项的位串称之为数据域。
③ 数据的运算：对数据施加的操作。
算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。
3、数据的两种存储结构： 顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。
链式存储结构：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，通常要借助于语言的指针类型来描述。
*
4、数据类型、抽象数据类型
数据类型:是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。
原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。
抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。
抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型： ① 原子类型:变量的值是不可分解的。
② 固定聚合类型:变量的值由确定数目的成分按某种结构组成。③ 可变聚合类型:其值的成分数目不确定。
抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。
（D，S，P）
D是数据对象，S是D上的关系集，P是对D的基本操作。
格式：
ADT 抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 }ADT 抽象数据类型名。
数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：
基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉 例：
ADT Triplet{ 数据对象：D={e1，e2,e3 |e1,e2,e3∈Elemset(定义了关系运算的某个集合)} 数据关系：R1={〈e1,e2>,
InitTriplet(&T,v1,v2,v3)DestroyTriplet（&T）Get（T,i,&e）Put(&T,i,e)IsAscending(T)IsDescending(T)Max(T,&e)
Min(T,&e)
}ADT Triplet 多形数据类型:是其值的成分不确定的数据类型。
三、抽象数据类型的表示与实现
抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。
1、类C语言
精选了C 的一个子集，扩充修改，增强了语言的描述功能。 预定义常量和类型
数据结构的表示：存储结构用类型（typedef）定义来描述。
数据元素类型约定为ElemType. 基本操作的算法用函数描述：
函数类型 函数名（函数参数表）{ //算法说明
语句序列
}//函数名
增加了引用调用的参数传递方式。
赋值语句、选择语句、循环语句、结束语句、输入输出语句、注释语句 基本函数 逻辑运算约定
例：Triplet的表示和实现
//采用动态分配的顺序存储结构
Typedef ElemType * Triplet://由InitTriplet分配三个元素存储空间 //基本操作的函数原型说明
Status InitTriplet(Triplet &T,ElemType v1, ElemType v2, ElemType v3)Status DestroyTriplet（&T）Status Get（T,i,&e）Status Put(&T,i,e)Status IsAscending(T)Status IsDescending(T)Status Max(T,&e)Status Min(T,&e)//基本操作的实现
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //构造三元组T，依次置T 的三个元素的处值为v1,v2和v3。
T=(ElemType)malloc(3*sizeof(ElemType));//分配三个元素的存储空间
If(!T)exit(OVERFLOW);//分配存储空间失败 T[0]=v1;T[1]=v2;T[2]=v3;return OK;}//InitTriplet Status DestroyTriplet（Triplet &T）{ //销毁三元组T。······
}//Min
四、算法和算法分析
1、算法（Algorithm）
是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五个重要特性：有穷性、确定性、可行性、输入、输出
2、算法设计的要求
正确性、可读性、健壮性和效率与低存储量要求
3、算法效率的度量
算法时间是由控制结构和原操作的决定的。做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。
时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），T（n）=O（f（n））
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长绿相同。
语句的频度：是该语句重复执行的次数。
例：求两个n阶方阵的乘积C=A×B，其算法如下： #define n 100 void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n]){ int i,j,k for(i=1;i<=n;++i)n+1
for(j=1;j<=n;++j)n*(n+1)
C[i][j]=0;n2
for(k=1;k<=n,k++)n2(n+1)
3C[i][j]=C[i][j]+a[i][k]*b[k][j];n
} } T(n)=2n3+3n2+2n+1 3limT(n)/ n=2 T(n)=O(n3)例：
（a）{++x;s=0;}（b）for(i=1;i<=n;++i){++x;s+=x;}（c）for(j=1;j<=n;++j)for(k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的语句的频度分别为1,n和n2 时间复杂度是O(1),O(n)和O(n2)。时间复杂度有时与输入有关。
4、算法的存储空间需求
空间复杂度：S（n）=O（f（n））
五、作业布置
复习回顾c语言中关于结构体和指针部分的内容，以便于后期学习。
六、教学后记
按2 学时讲完。
以前教学中反映出学生对抽象数据类型掌握不好，结构体知识基本不懂，所以要求学生课下自学，下次课抽1学时学习结构体和指针。
学生读程序能力差，循环嵌套分析不出执行次数。考虑布置了一道题目练习。
第二篇：数据结构DS复习_章节教案（模版）
《数据结构》课程授课教案
课程名称：数据结构 英文名称：Data Structure 学时数及学分：64＋32学时
4＋1学分 授课班级：2005级2班
教材名称及作者、出版社、出版时间：
《数据结构（C语言版）》，严蔚敏 吴伟民，北京：清华大学出版社，2004
一、课程的目的、要求和任务
《数据结构》是计算机专业的一门必修的核心基础课程。是计算机程序设计的重要理论技术基础，它对理论和实践的要求都相当高，具有相当的难度，且内容较多。
本课程旨在讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构在计算机中的存储结构，以及进行各种非数值运算的方法，让学生学习、分析和研究计算机加工数据对象的特性，掌握数据的组织方法，以便选择合适的数据的逻辑结构和存储结构，设计相应的操作运算。在计算机应用领域中，尤其是在系统软件和应用软件的设计和应用中都要用到各种数据结构，这对提高软件设计和程序编制水平都有很大的帮助。
二、课程主要教学内容
本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。
1.掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法；
2.掌握各种主要数据结构的特点、机内表示、处理数据的算法设计，以及算法分析、组织、处理数据的理论和方法，建立良好的编程风格；培养数据的抽象能力。
三、课程教学重点与难点
1.教学重点：线性表、栈、队列、二叉树、图典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法思想。2.教学难点：各种数据结构的应用和进行操作实现。
四、参考书
1.《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，2006年7月 2.《数据结构与算法设计》,王晓东,电子工业出版社,2002.3 3.《数据结构（C语言篇）习题与解析》,李春葆, 清华大学出版社 4.《数据结构学习指导与典型题解》，朱占立等编著，西安交通大学出版社 5.《数据结构题集（C语言版）》, 严蔚敏
吴伟民, 清华大学出版社 6.《数据结构》 殷人昆 编著, 清华大学出版社
7.《数据结构》 张选平雷永梅, 机械工业出版社，2002.1 第一章 绪论
1.教学内容(1)(2)(3)(4)2.数据结构的基本概念和术语； 数据的逻辑结构、存储结构； 抽象数据类型在软件设计中的意义；
算法的概念和算法的时间和空间复杂度分析。
教学目的及要求(1)(2)(3)(4)掌握数据结构的基本概念，理解数据结构和算法的关系； 抽象数据类型的表示和实现； 类C语言描述算法的机制； 掌握算法复杂性分析的方法和技巧。本课程的主要内容；
数据结构的基本概念和术语，抽象数据类型，算法和算法的时间复杂度分析 抽象数据类型的表示和实现 算法的时间复杂度分析；
讲授数据结构课程的主要内容以及在软件分析和设计中意义； 讲授抽象数据类型在软件设计中的意义； 讲授算法的概念和算法的时间复杂度分析方法； 例题讲解算法的时间复杂度分析方法； 作业
对于重点和难点，通过例题讨论讲解。3.教学重点(1)(2)
4.教学难点(1)(2)
5.教学思路与教学方法(1)(2)(3)(4)(5)(6)
6.习题与思考题(1)填空题
a）数据的逻辑结构可形式地用一个二元组B＝(D，S)来表示，其中D是_____，S是_____。b）存储结构可根据数据元素在机器中的位置是否连续分为_____，_____。c）算法的基本要求有_____，_____，_____，_____，_____。d）度量算法效率可通过_____，_____两方面进行。(2)简述下列术语：
a）数据、数据元素、数据对象、数据结构 b）数据的存储结构、逻辑结构； c）数据类型和抽象数据类型(3)(4)举例说明一下数据结构和算法的关系。
试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。
例如：求下列算法的时间复杂度：
i=1;
while(i<=n)
i=i*3;答：O（logn）
第二章 线性表（8学时）
1.教学内容(1)线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算；(2)线性表的顺序存储结构、a）特点；
b）基本操作的实现算法（初始化、插入、删除、查找等）；(3)线性表的链式存储结构及基本操作的实现算法；
a）线性链表的特点、类型定义，以及基本操作（初始化、插入、删除、查找等）的实现算法；
b）循环链表、双向链表的定义、特点及操作的实现。
2.教学目的及要求(1)(2)(3)掌握线性表的逻辑特点；
掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。
掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。(4)循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。(5)3.领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能 教学重点(1)(2)(3)4.(1)(2)5.线性表的定义和抽象数据类型；顺序和链式存储结构； 顺序表的设计；
链表（单链表、循环链表、双向链表）的设计。顺序表操作的算法设计，以及单链表操作的算法设计； 完整应用程序的结构 教学难点
教学思路与教学方法(1)(2)讲授本章节的基本概念，先逻辑结构，后存储结构； 讲授各存储结构下操作实现的主要思想；(3)(4)(5)6.在C++开发环境下，计算机演示完整应用程序的结构，以及编辑、编译和运行的方法；
例题讲解；对于重点和难点，通过程序演示，作业来突出。
辅助手段：多媒体演示＋板书
习题与思考题（见PPT课件，并完成实验二的实验题目）
教学内容(1)(2)(3)(4)(5)栈的基本概念、特点，与一般线性表的区别；
栈顺序表示和实现、链式表示和实现；
栈的典型应用：数制转换问题；括号匹配问题；栈与递归； 队列的基本概念、特点，与一般线性表的区别；
顺序队列、顺序循环队列、链式队列、队列应用；优先级队列。理解栈的概念；
掌握顺序栈和链式栈的设计方法；
理解队列的概念，掌握顺序循环队列和链式队列的设计方法； 了解栈和队列的应用方法，掌握栈和队列的基本应用。第三章 栈和队列（8学时）
1.2.教学目的及要求(1)(2)(3)(4)
3.教学重点(1)(2)顺序栈和链栈的设计方法、典型应用； 顺序循环队列和链式队列的设计方法。栈和队列的实现；
应用栈实现表达式的求值；
顺序队列的假溢出现象，顺序循环队列的队空和队满判断方法。
课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。(2)(3)(4)对算法的实现要求采用VC++ 开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。
每次下课前布置若干思考题，待下次上新课前进行提问，或完成课堂练习，加强互动。
根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。4.教学难点(1)(2)(3)
5.教学思路与教学方法(1)
6.1.习题与思考题（见PPT课件，并完成实验三的实验题目）教学内容 第四章 串（2学时）(1)(2)(3)2.(1)(2)(3)(4)3.(1)(2)4.5.串的基本概念、存储结构（顺序存储、链式存储）、顺序存储结构下基本操作的实现算法；
串的模式匹配：Brute-Force算法。
联系C语言中串的存储方法及串函数，并围绕两种基本存储结构进行分析。了解串类型的抽象数据类型定义； 熟悉串的有关概念，串和线性表的关系；
了解串的表示和实现（串的各种存储结构，比较它们的优、缺点，从而学会在何时选用何种存储结构为宜）；
理解串的两种模式匹配算法的思想、实现及时间复杂度的分析；
串的存储结构； 了解串的模式匹配。教学目的及要求
教学重点
教学难点
教学思路与教学方法(1)(2)(3)以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；
课后做习题，并课外上机实验，练习基本操作的实现及模式匹配的实例训练，以巩固课堂所学知识点。板书设计：
a）以文字描述为主，要点及关键词用不同颜色标注； b）涉及有关存储结构、算法时，通过示意图描述；(4)提问：
a）空串和空白串有无区别？
b）回顾：C语言中串的存储方法及有关串函数。
6.习题与思考题（见PPT课件，并完成实验四的实验题目）
第五章 数组和广义表（6学时）
1.教学内容(1)(2)(3)(4)2.数组的定义及其实现机制；
特殊矩阵（包括n阶对称矩阵、n阶三角矩阵）的压缩存储方法； 稀疏矩阵的压缩存储方法：三元组顺序表、十字链表，以及稀疏矩阵实现转置和相加运算；
广义表的结构特点、基本操作及其存储表示方法
教学目的及要求(1)(2)理解了解数组的逻辑结构和存储表示；掌握数组在以行/列为主的存储结构中的地址计算方法；
掌握特殊矩阵的压缩存储方式及下标变换公式；(3)(4)了解稀疏矩阵压缩存储方法的特点和适用范围，理解以三元组表示的稀疏矩阵进行矩阵运算采用的处理方法；
掌握广义表的结构特点极其存储表示方法，以及对非空广义表进行分解的两种分析方法；
(5)3.(1)(2)(3)(4)4.5.(1)(1)(2)(3)(4)了解广义表的递归算法设计。
稀疏矩阵的三元表存储表示及稀疏矩阵转置的两种实现方法。多维数组的表示和实现； 特殊矩阵的压缩存储； 稀疏矩阵的压缩存储。
稀疏矩阵的十字链表的定义和建立算法。
从具体的矩阵实例出发，先分析其特点，然后围绕以上知识点进行讲述。以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；
课后做习题，并上机实验，练习特殊矩阵、稀疏矩阵的压缩存储方法，以巩固课堂所学知识点。板书设计：
a）以文字描述为主，要点及关键词用不同颜色标注； b）对压缩存储方法通过示意图描述；
c）对于实例，通过链接到VC环境下实际运行。教学重点
教学难点
教学思路与教学方法
(5)(6)(7)重点突出：通过课堂强调与透彻分析，课后练习进行。
难点解决：通过实例讲解，并在VC环境下实际运行实例，使学生真实体会算法设计全过程。师生互动设计：
a）提问：数组与线性表的区别与联系？ b）回顾：线性表的两种存储结构表示方法。
6.1.习题与思考题（见PPT课件，并完成实验四的实验题目）教学内容(1)(2)(3)二叉树的定义和性质，性质的应用
二叉树的存储结构（特别是二叉链表存储结构）
二叉树的各种遍历算法（先序、中序、后序、层次）及其应用；能根据先序和中序，中序和后序确定一棵二叉树。(4)(5)线索二叉树的建立、遍历的基本思想，能画出按先序、中序、后序遍历次序建立的线索二叉树；
二叉树的应用—哈夫曼树，哈夫曼编码； 第六章 树和二叉树（10学时）(6)2.(1)(2)(3)3.(1)(2)(3)4.树和二叉树之间的转换 树与二叉树的基本概念； 二叉树的性质与存储结构；
掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现。二叉树的性质、二叉树的存储结构；
二叉树的遍历算法和二叉树遍历算法的应用； 哈夫曼树在编码方面的应用方法。教学目的及要求
教学重点
教学难点(1)(2)二叉树的性质以及利用这些性质分析问题的方法； 二叉树问题的遍历算法设计分析和实现。
讲授本章节的基本概念，先逻辑结构，后存储结构； 讲授各存储结构下的实现的主要思想； 计算机演示存储结构下的实现； 例题讲解； 作业
辅助手段：多媒体演示
对于重点和难点，通过程序演示，作业来突出。5.教学思路与教学方法(1)(2)(3)(4)(5)(6)(7)
6.习题与思考题（见PPT课件，并完成实验五的实验题目）
第七章 图（10学时）
1.教学内容(1)(2)2.(1)(2)(3)(4)(5)(6)(7)3.图的基本概念、图的存储结构；
图的程序实现、图的遍历、最小生成树、最短路径等。了解图的定义和术语
掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法； 理解图的深度和广度遍历方法和算法设计方法； 了解图的连通性问题极其判断；
理解最小生成树的概念、普里姆算法和克鲁斯卡尔算法； 有向无环图极其应用（拓扑排序和关键路径）；
了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算法。教学目的及要求
教学重点(1)(2)(3)图的邻接矩阵和图的邻接表存储结构； 图的深度和广度遍历方法； 普里姆算法和克鲁斯卡尔算法。4.5.教学难点(1)(1)(2)(3)(4)(5)(6)图操作的实现方法。
课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量；
图中的概念很多，采取先讲实例应用，再总结概念定义的方法学习效果会好些；
对重点和难点算法的核心部分通过板书进行详细讲解。
对算法的实现要求采用VC++开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。
每次下课前布置若干思考题，待下次上新课前进行提问。
根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。教学思路与教学方法
6.习题与思考题（见PPT课件，并完成实验六的实验题目）
第八章 查找（8学时）
1.教学内容(1)(2)(3)(4)顺序查找、二分查找、索引顺序查找算法；
二叉排序树的查找、插入与删除算法；了解二叉平衡树的基本概念 常用的哈希函数的设计方法：除留余数法、直接定址法、数字分析法；哈希冲突解决方法：开放地址法、链表法。
哈希表的完整设计过程，包括：哈希表的构建、元素的插入与删除、哈希表查找效率。
2.教学目的及要求(1)掌握静态查找表的四种查找方法（顺序查找、折半查找、静态树表、索引查找）的实现；(2)(3)3.掌握动态查找表（二叉排序树、二叉平衡树、B-和B+树、键树）的构造和查找方法；
掌握哈希表构造方法，哈希表的查找以及衡量查找效率的平均查找长度的讨论。教学重点(1)(2)(3)4.5.二分查找；
二叉排序树的查找； 哈希表查找。
教学难点(1)(1)哈希表中哈希函数的设计与哈希冲突解决方法。以课堂多媒体教学为主，辅助以黑板进行绘图分析； 教学思路与教学方法(2)(3)课后完成上机实验，练习二分查找、二叉排序树查找及哈希表查找的算法设计，以巩固课堂所学知识点。板书设计：
a）以文字描述为主，要点及关键词用不同颜色标注； b）对查找、插入与删除等算法通过示意图描述； c）对于实例，通过链接到VC环境下实际运行。
(4)(5)(6)重点突出：通过课堂强调与透彻分析，课后练习进行。
难点解决：通过不同类型的实例讲解，使学生理解并掌握常用的哈希函数设计方法以及哈希冲突的解决方法，并总结其优、缺点。师生互动设计：
a）实例分析中引导学生参与算法设计；
b）提问：在每一种哈希函数的设计方法及哈希冲突的解决方法讲解后，引导并提问学生此类方法的优、缺点及解决途径。
6.1.习题与思考题（见PPT课件，并完成实验七的实验题目）教学内容(1)(2)排序算法的性能指标；
插入排序、选择排序、交换排序、归并排序、基数排序的算法设计与应用。第九章 内部排序（8学时）
2.教学目的及要求(1)(2)掌握排序的基本概念和排序算法的评判标准；
掌握如下排序的算法基本思想和设计方法，以及算法分析。a）直接插入排序 b）希尔排序 c）直接选择排序 d）堆排序 e）快速排序 f）二路归并排序 g）基数排序
3.4.5.教学重点(1)希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想； 教学难点(1)(1)(2)(3)(4)堆排序、快速排序、二路归并排序和基数排序的算法设计方法。讲授本章节的基本概念，先逻辑结构，后存储结构； 讲授各存储结构下的实现的主要思想； 计算机演示存储结构下的实现； 例题讲解； 教学思路与教学方法(5)(6)(7)6.作业
辅助手段：多媒体演示
对于重点和难点，通过程序演示，作业来突出。
习题与思考题（见PPT课件，并完成实验七的实验题目）。
第三篇：湖州师范学院数据结构DS大作业
求真学院
数据结构课程设计大作业
20142832班
题
目： 专
业： 学生姓名： 学
号 指导教师 完成日期：
排序效率的比较 计算机科学与技术
邵
斌
湖州师院求真学院信息工程系
目录一、二、三、四、五、六、七、实验内容概述...............................................................................................................................1 实验目的概述...............................................................................................................................1 解题思路的描述...........................................................................................................................1 源程序清单...................................................................................................................................1 程序调试及测试结果...................................................................................................................8 结论...............................................................................................................................................9 参考文献.....................................................................................................................................10
I
此处写大作业题目（宋体三号，居中）
【内容摘要】
200至300字左右，楷体BG2312五号
【关键字】XXXX，XXXXX，XXXXX，XXXXX(3到5个)数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。
关键字：排序 逻辑运算 数据结构 时间复杂度
【Abstract】
中文摘要的翻译，五号，Times New Roman
【Key words】XXXXX，XXXXX，XXXXX，XXXXX Data structure is the way of computer storage and organization data.A data structure is a data element and a set of data elements that have one or more specific relationships between each other.Typically, carefully selected data structures can be brought to a higher running or storage efficiency, processing a variety of problems.The program is written in C language, it fully reflects the concept of data structure and algorithm charm.The program is implanted in a variety of sorting methods, these sorting algorithms have the characteristics of each algorithm, the use of a variety of algorithms to achieve the same effect, is the so-called “all roads lead to Rome”.And, the program also collects the running time of each algorithm, through the time of the comparison, for the user to pick out two kinds of optimization of the sorting method.Keywords: sorting logic operation data structure time complexity
一、实验内容概述
对于直接插入排序、选择排序、冒泡排序、Shell排序、快速排序和堆排序等几种常见的排序算法进行练习，并且比较各算法在不同长度数据下的优劣。
要求：（１）被排序的对象由计算机随机生成，长度分别取２０，１００，５００三种。
（２）程序中要有对各种排序算法的比较，具体为比较次数和移动次数的统计。
（３）对课设的结果做比较分析
二、实验目的概述
1.巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力；
2.通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作；
3.锻炼学生的动手能力与培养其独立思考的能力。
三、解题思路的描述
这是一个算法性能评价的程序，重点在于算法的性能评价上。实现排序功能可以有多种方法，判断一个算法性能好坏的标准主要有时间复杂度和空间复杂度。在当今系统资源相对充足的计算机系统中，时间复杂度便成为最主要的评价标准。
对于每一个排序算法，都应当有两个返回值：比较次数和移动次数。这里采用指针传递地址的方式，通过修改形参的地址从而可以改变实参的值。每个排序算法中除了含被排序对象指针外，还有两个整型变量指针，用于传递算法执行过程中的比较次数和移动次数。
取定一种排序对象的长度，由计算机产生一定量的伪随机数后，主函数调用各个排序子函数，但由于排序对象也是指向一维数组的指针，在调用一次一种排序算法后，通过形参对指针的改变，被排序对象已经是有序的了。当再次调用其他函数时有可能使比较和移动次数达到最大或最小，就失去了比较的意义。因此，本程序中采用了子函数另开辟空间，参数只起到一个复制值的作用，在每个子函数结束前用delete()来释放申请排序对象的指针，避免程序出现内存耗尽的情况。
四、源程序清单
主要包括： #include
void number(){ srand(time(0));int i,t;printf(“随机数长度：n”);printf(“ 1.长度为20n”);printf(“ 2.长度为100n”);printf(“ 3.长度为500n”);printf(“输入序号选择长度:”);scanf(“%d”,&t);switch(t){ case 1: n=20;for(i=1;i<=n;i++){ a[i]=rand()%1000+1;//1-1000的随机数
}break;case 2: n=100;for(i=1;i<=len;i++){ a[i]=rand()%1000+1;}break;case 3:n=500;for(i=1;i<=len;i++){ a[i]=rand()%1000+1;}break;} for(i=1;i<=len;i++)b[i]=a[i];printf(“随机生成的%d个数如下：n”,len);for(i=1;i<=len;i++){ printf(“%d ”,a[i]);} printf(“n”);} typedef struct{ int key;//关键字
}RecordNode;//排序结点类型 typedef struct{ RecordNode *record;int n;//排序对象的大小 //srand函数是初始化随机数的种子 }ElemType;//排序对象的类型 直接排序
void InsertSort(ElemType A[], int n){ int i, j;ElemType x;for(i=1;i x = A[i];//准备插入第i个元素 for(j=i-1;j>=0;j--){ //从第i-1个开始往前找插入点 if(x.stn < A[j].stn)A[j+1]=A[j];else break;} A[j+1]=x;//插入 } for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} 直接选择排序 void SelectSort(ElemType A[], int n){ int i, j, k;ElemType x;for(i=0;i<=n-2;i++){ //每一趟选择最小元素并与A[i]交换 k=i;for(j=i+1;j<=n-1;j++)//查找最小元素的下标 if(A[j].stn void BubbleSort(ElemType A[], int n){ int i, j, flag;//flag为交换标记 ElemType x;for(i=1;i<=n-1;i++){ // 最多n-1趟排序flag=0;//假设本次没有交换 for(j=n-1;j>=i;j--)//第i 趟 if(A[j].stn < A[j-1].stn){ flag=1;//出现交换 x=A[j];A[j]=A[j-1];A[j-1]=x;} if(flag==0)return;} for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } Shell排序 void ShellSort(ElemType A[ ], int n,int dk) { int i,j,temp;ElemType x; for(i=dk;i 快速排序 void QuickSort(ElemType A[ ], int s, int t){ //递归算法，对区间 A[s] ～A[t] 进行快速排序 int i=s+1, j=t;ElemType temp, x = A[s];//第一个为基准元素 while(i<=j){ while(i<=j && A[i].stn <= x.stn)i++;//从左到右 while(i<=j && A[j].stn >= x.stn)j--;//从右到左 if(i < j){ temp=A[i];A[i]=A[j];A[j]=temp;i++;j--;} for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } if(s!=j){ //交换基准元素 A[s]=A[j];A[j]=x;} if(s void CreatHeap(ElemType A[], int n){ int i;for(i =(n–2)/2;i >= 0;i--)Sift(A, n, i);//调整A[i..n-1]使之为一个堆 } void Sift(ElemType A[], int n, int i){ // 调整A[i..n-1]成为一个堆（它的左右子树已是一个堆）ElemType x=A[i];int j = 2 * i + 1;// j为i的左孩子 while(j <= n-1){ // i有左子树 if(j +1 < n && A[j].stn < A[j+1].stn)j++;// 使j指向左右孩子中排序码大的孩子 if(x.stn < A[j].stn){ //使j指向左右孩子中排序码大的孩子 A[i]=A[j];i=j;j=2*i+1;} else break;} A[i]=x;} void HeapSort(ElemType A[], int n){ //A为待排序表，n为表的长度 int i;ElemType x； CreatHeap(A, n);// 把A建成一个堆 for(i = n-1;i >= 1;i--){ x = A[0];//第0个元素与第i个元素交换 A[0] = A[i];A[i] = x;Sift(A, i, 0);//调整A[0..i-1]使之为一个堆 } for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } Void main(){ int i,j,n,N=20;cout<<“ 各排序方法选择结果：n”;ElemType A[20];for(j=0;j 算法的时间复杂度是什么？算法的空间复杂度是什么？为什么？ 插入排序：稳定，时间复杂度 O(n^2)O(n2)选择排序：不稳定，时间复杂度 O(n^2)O(n2)冒泡排序：稳定，时间复杂度 O(n^2)O(n2)希尔排序：不稳定，时间复杂度平均时间 O(nlogn)最差时间O(n^s)1 程序调试及测试结果 主要包括： 选择长度为20的随机数，六种方法排序的结果。 从比较次数和移动次数可大致看出各排序方法的效率高低，后三种明显优于前三种 六、结论 主要包括： 随机数产生方法：srand(time(0))就是给这个算法一个启动种子，也就是算法的随机种子数，有这个数以后才可以产生随机数,用1970.1.1至今的秒数，初始化随机数种子。Srand是种下随机种子数，你每回种下的种子不一样，用Rand得到的随机数就不一样。为了每回种下一个不一样的种子，所以就选用Time(0)，Time(0)是得到当前时时间值（因为每时每刻时间是不一样的了）。 进行函数的参数传递时，如果传入一个地址，比传入一个struct效率要高，因为少了一个拷贝过程。待改进的地方：很多步骤有重复用到，如把数组b赋值给a，定义Ccnt，Rcnt等，可以做个初始化的函数调用，省去重复的代码。可以增加其他排序方法进行效率比较。 七、参考文献 [1] 唐国民, 王国钧.数据结构 [M].北京:清华大学出版社, 2013: 213-238 [2] 张乃孝.算法与数据结构——C语言描述[M].北京: 高等教育出版社, 2002 [3] 唐国民，王智群.C语言程序设计[M].北京:清华大学出版社, 2009:107-115 [4] 唐国民, 王国钧.数据结构实验教程 [M].北京:清华大学出版社, 2013: 195-207 说明： 标为M的是书籍 标为D的为学位论文 标为J的为期刊 标为C的为会议论文 指导教师：邵 斌 日期：2016/6/5 实验成绩： 法律逻辑学教案 第一章 引 论 第一节 逻辑学的产生和发展 一、“逻辑”的含义 二、逻辑的产生 逻辑问题(亦即思维或论辩的正确性问题)成为人们的研究对象，几乎同时起源于三个古老的国家，即古代的希腊、印度和中国。不过，真正形成较完整的学科体系并在世界各国流传至今的，是古希腊的逻辑学，它作为一门独立的学科出现，迄今已有2000多年。 在古希腊，当时虽然是奴隶主贵族政治时期，但生产力有了很大的发展。 一方面，社会政治生活中演讲辩论的风气盛行，不仅出现了一批专门以论辩为职业的人，而且还出现了一批专门培养所谓有智能、善辩论者的教师，即智者学派。 另一方面，古希腊的自然科学尤其是数学，特别是以欧几里德为代表的“几何学”有了很大发展。这不仅表现了人们已具有较高的抽象思维能力，而且，其证明本身就包含了逻辑知识。 古希腊逻辑科学的创始人是亚里士多德(公元前384年至公元前322年)。他的《工具论》一书奠定了逻辑科学的理论基础，他被称为“逻辑之父”。 《工具论》包括《范畴篇》 (即概念)，《解释篇》(即命题与判断)，《前分析篇》、《后分析篇》(即推理与证明)，《论辩篇》(即论辩常识)，《辩谬篇》 (即揭露诡辩的方法)，这本书对后世影响很大。 亚里士多德以后，直到中世纪，欧洲的逻辑学家在逻辑学的基本理论方面虽作了一些研究，但发展不大。 在我国，先秦时期的逻辑思想异常活跃，社会上出现了“百家争鸣”的文化局面。当时的诸子百家为使世人采纳己见，便相互辩诘，其中有很多逻辑方面的知识。惠施、公孙龙、韩非和苟况等人，都提出了许多有价值的逻辑理论，特别是后期的墨家的逻辑理论就更加完整和系统。 《墨经》是一部内容非常丰富的逻辑专著，它包括《经上》、《经下》、《经说上》、《经说下》、《大取》、《小取》。在这部专著中，当今逻辑学所讲的概念、判断和推理等在《墨经》中都已有论述。比如，《小取》篇中说： “以名举实，以辞抒意，以说出故。”这里的“名”相当于概念，“辞”相当于判断，“说”相当于推理。它说明了概念是用来反映事物的，判断是用来推导事物之间因果关系的。我国古代的逻辑学先后被称做“名学”、“辩学”、“理则学”和“理论学”等。到了东汉时期，由于董仲舒倡导“罢黜百家，独尊儒术”，此后的逻辑学说便趋于衰微了。 在古代印度，同样是诸教纷纷兴起，他们之间互相论争，其中，胜论派和正理派开创了因明学。“因”指推理的依据，“明”即通常所说的“学”，“因明”就是古代印度关于推理的学说。如陈那在《因明正理门论》中提出的“三支论式”认为，每一个推理形式都是由“宗”、“因”、“喻”三部分组成。这里所谓的“宗”相当于三段论中的结论，所谓“因”相当于三段论的小前提，所谓“喻”相当于三段论的大前提。 古希腊的逻辑学、印度的因明学和中国的名辩学，犹如三颗瑰丽的明珠，在世界古代逻辑史上交相辉映。 三、逻辑学的发展 16世纪以后，资产阶级革命带来了科学的革命，这一时期的自然科学发展迅速，使逻辑逻辑学得到了极大的丰富和发展，甚至可以说是经历了伟大的转折。 例如，哥白尼的太阳中心说，笛卡尔的解析几何，牛顿和莱布尼茨的微积分，伽利略的动力学，拉普拉斯的星云说，并且电磁波的发现，蒸汽机、涡轮机、电动机的发明都在这个时期。 英国唯物主义哲学家、被马克思誉为 “整个近代实验科学的真正始祖”的弗兰西斯·培根，建立起归纳逻辑理论，主要著作《新工具》。 法国著名数学家笛卡尔则进一步完善了演绎法，并在历史上第一次提出了关于推理过程中可以运用简单的符号，建立“普遍数学’’的设想，给后继者创立符号化的数理逻辑以启迪。 17世纪法国波尔·罗亚尔修道院的阿尔诺和尼卡尔合写并出版的逻辑著作，即被后人称的“波尔·罗亚尔逻辑学”，更是大大地丰富和完善了原有逻辑学的内容，成为近代逻辑学中最早的也最具代表 性的逻辑学教科书，流传甚广，影响深远，可以说传统逻辑学的主要内容和体系，至此基本定型。 17世纪后半期，特别是18世纪以后，传统逻辑在原有基础上朝着两个根本不同的方向发展。 一方面，人们基于传统逻辑还不够形式化而带来的不精确、不系统的弊端，在传统逻辑基础上发展出了数理逻辑。 早在17世纪末期，德国数学家莱布尼茨在笛卡尔思想影响下就设想把数学方法应用于逻辑，把逻辑推理变成纯符号的逻辑演算，使逻辑成为一种证明艺术，并进行了开创性的研究工作。尽管他后来中断了这一研究，设想未能实现，却给逻辑的发展指出了新的方向，对后来数理逻辑的创建起到了重要作用，因而被公认为数理逻辑学奠基人。 此后，经过19世纪末期英国数学家乔治·布尔、德·摩根，以及后来的德国数学家弗雷格和20世纪英国数学家罗素、怀特海等许多人的努力，前后经历了200年左右的时间，终于建立起了严密、完整、崭新的逻辑体系——数理逻辑。 另一方面，在科学迅速发展的时代背景下，18世纪末期德国的一些哲学家却从另一个角度批评了传统逻辑的不足。他们基于传统逻辑只研究思维的形式，没有把思维的内容和思维的形式统一起来；基于它只立足于思维的确定性而撇开了思维的变动性、辩证性，提出了研究辩证思维的问题，从而出现了辩证逻辑。 德国哲学家康德首先对传统思维提出批评。他认为亚里士多德的 逻辑虽然完善，但它只研究思维的功能及其形式，不研究思维的内容、来源，因此他把这样的逻辑称之为“形式逻辑”、“普通逻辑”，使传统逻辑的这种称谓流传至今(不过，当代学术界更倾向于认为严格意义下的形式逻辑仅指数理逻辑，而把传统逻辑称为普通逻辑)。 继康德之后，19世纪德国的辩证逻辑的创始人黑格尔在批评传统逻辑的基础上，努力用他的辩证法观点来改造旧逻辑，建立新逻辑。他在《逻辑学》这一巨著中，系统地研究了思维的辩证或辩证思维的问题，勾画出了一种新的——即辩证逻辑学科体系的轮廓。 自此也可以说又诞生了一种与传统逻辑根本不同的、既是世界观又是方法论的另一种意义上的逻辑——辨证逻辑。 第二节 法律逻辑学的性质和研究对象 一、法律逻辑学的性质 法律逻辑学是一门介于普通逻辑学和法律科学之间的交叉学科，是一门工具性质学科。 二、法律逻辑学的研究对象 法律逻辑学的主要研究对象是法律思维形式及其规律。思维形式：是思维内容与形式的统一，思维内容是思维反映的特定对象及其本质和规律；思维形式是思维赖以存在和表达的方式，即概念、判断和推理。 思维的逻辑形式：是指思维形式的各部分之间的联系方式。 例如： 所有金属都是导电体。 所有出现尸斑的尸体都是死后２－４小时的尸体。所有哺乳动物都是用肺呼吸的动物。所有Ｓ都是Ｐ。又如： 如果死者背上有自己无法形成的致命伤，那么，死者是被人杀害的。 如果数Ｘ能被８整除，那么，数Ｘ能被４整除。如果p，那么q。 再如： 法律是有阶级性的，刑法是法律，所以，刑法是有阶级性的。 所有出现尸斑的尸体都是死亡后２－４小时的尸体，本案死者的尸体是出现尸斑的尸体，所以，死者的尸体是死亡后２－４小时的尸体。 Ｍ是Ｐ，Ｓ是Ｍ，所以，Ｓ是Ｐ。 逻辑形式是由逻辑常项和逻辑变项构成。 逻辑常项：是思维形式中不变的部分。如：所有„都是„ 如果„那么„ 逻辑变项：是逻辑形式中可变的因素，即可以表示任何具体内容的部分。 如：Ｓ、Ｐ、Ｍ、p、q Ｓ、Ｐ、Ｍ是词项变项；p、q是命题变项。 法律逻辑学是我国高等院校法学专业的一门必修课。法律逻辑学具有很强的应用性质,是结合案例分析而建立在普通逻辑原理基础上的,是和语言逻辑学、教育逻辑学、医疗逻辑学等并列的形式逻辑的分支学科.由于高校的法律专业是为社会培养法律方面的人才,法律工作者必须掌握科学的思维素质和严谨缜密的逻辑思维能力.作为训练法学专业学生逻辑思维能力的学科,法律逻辑学成为法律专业一门重要的基础课程。 云淡风清 http://gsqls.blog.163.com/ 第1章 数据结构概述 1.1概述 以下为某市部分院校的交通地图情况，要求找出从出发点到目的地之间的最短路径及其长度。 对于此问题，如果手工去做，速度慢(特别地，现实中实际地图信息要比此例复杂许多)，还容易出错，此时可借助于计算机完成。 计算机进行此类信息的处理时，涉及到两个问题：一是现实当中的信息在计算机中如何表示，二是如何对信息进行处理。 信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题不断复杂化，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 1.1.1编写解决实际问题的程序的一般流程 如何通过编写程序，以比手工更为高效精确的方式解决实际问题呢？一般流程如下： 1、由具体问题抽象出一个适当的数学模型； 2、分析问题所涉及的数据量大小及数据之间的关系； 3、确定如何在计算机中存储数据及体现数据之间的关系？ 4、确定处理问题时需要对数据作何种运算？ 5、确定算法并编写程序； 5、分析所编写的程序的性能是否良好？若性能不够好则重复以上步骤。 云淡风清 http://gsqls.blog.163.com/ 上面所列举的问题基本上由数据结构这门课程来回答。 《数据结构》是计算机科学中的一门综合性专业基础课，是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。 1.1.2数据结构的例子 1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 姓名 电话号码 陈伟海 *** 李四锋 ***。。 这是一种典型的线性结构。 2、磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推。 。。 本问题中各目录从上到小形成了一种一对多的关系，是一种典型的树形结构。 云淡风清 http://gsqls.blog.163.com/ 3、交通网络图 下图表明了若干个城市之间的联系： 从图中可看出，一个地方到另外一个地方可以有多条路径，是一种典型的网状结构，数据与数据成多对多的关系。 4、排序问题 对100000个整数进行降序排序。冒泡法程序： #include a[i]=rand();printf(“n按原序输出：n”);for(i=1;i<=N;i++) printf(“%8d”,a[i]);system(“pause”);for(j=1;j for(i=N;i>j;i--) if(a[i]>a[i-1]) { a[0]=a[i]; a[i]=a[i-1]; a[i-1]=a[0]; } printf(“n按新次序输出：n”); 云淡风清 http://gsqls.blog.163.com/ for(i=1;i<=N;i++) printf(“%8d”,a[i]);printf(“n”);} 快速排序程序： #include void quick_sort(int a[N+1],int left,int right){ int j,last,temp;if(left { //将划分子集的元素(此处选中间元素)移动到最左边 temp=a[left]; a[left]=a[(left+right)/2]; a[(left+right)/2]=a[left]; last=left;//用last记录比关键字小的元素的最右位置 for(j=left+1;j<=right;j++)//划分子集 if(a[j]>a[left]) { temp=a[last]; a[last]=a[j]; a[j]=temp; last++; } //对形成的新子集递归进行快速排序 quick_sort(a,left,last-1); quick_sort(a,last+1,right);} } void main(){ int i;int a[N+1];srand(time(NULL));for(i=1;i<=N;i++) a[i]=rand();printf(“n按原序输出：n”);for(i=1;i<=N;i++) printf(“%8d”,a[i]);system(“pause”); 云淡风清 http://gsqls.blog.163.com/ quick_sort(a,1,N);printf(“n按新次序输出：n”);for(i=1;i<=N;i++) printf(“%8d”,a[i]);printf(“n”);} 运行可知，两者速度差异非常明显，主要是排序所花的时间差别很大。可看出，同样的问题，采用不同方法进行处理，有可能呈现出非常大的性能方面的差异。 还可以找到许多其它例子，如图书馆的书目检索系统自动化问题，教师资料档案管理系统，多叉路口交通灯的管理问题等。 1.2基本概念和术语 1.2.1数据(Data)： 是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 1.2.2数据元素(Data Element)： 是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。 1.2.3数据对象(Data Object)： 是性质相同的数据元素的集合，是数据的一个子集，其中的数据元素可以是有限的，也可以是无限的。如整数集合：N={0，±1，±2，…}，是无限集，而字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}则为有限集。 1.2.4数据的逻辑结构： 指对数据元素之间逻辑关系的描述。 数据元素之间的关系可以是一种或多种。 数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。其要点有两个方面：一是元素本身，二是元素之间的关系。数据元素之间的逻辑结构有四种基本类型，如下： 云淡风清 http://gsqls.blog.163.com/ ①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中相邻的数据元素之间存在一对一的关系。③树型结构：结构中相邻的数据元素之间存在一对多的关系。 ④图状结构或网状结构：结构中相邻的数据元素之间存在多对多的关系。数据结构数学形式的定义是一个二元组： DataStructure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例：设数据逻辑结构B=(K，R)，其中： K={k1, k2, …, k9} R={ 1.2.5数据的物理结构： 又称存储结构，指数据结构在计算机内存中的存储方式。 数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的存储。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。 顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。 例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0}，两种不同的存储结构。顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；通过结构体类型实现的链表来表示链式存储结构。 1.2.6数据结构(Data Structure)： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。 1.2.7数据结构的三个组成部分： 逻辑结构：数据元素之间逻辑关系的描述：D_S=(D，S)。 存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储结构如下图所示。 云淡风清 http://gsqls.blog.163.com/ 逻辑结构与所采用的存储结构 数据逻辑结构层次关系图 1.2.8数据类型(Data Type)： 指的是一个值的集合和定义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型(如int，float，double，char等)和构造类型(如数组，结构体，共用体等)。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 1.3数据结构的运算 数据结构的主要运算包括： ⑴建立(Create)一个数据结构； ⑵消除(Destroy)一个数据结构； ⑶从一个数据结构中删除(Delete)一个数据元素； ⑷把一个数据元素插入(Insert)到一个数据结构中； ⑸对一个数据结构进行访问(Access)； ⑹对一个数据结构(中的数据元素)进行修改(Modify)； ⑺对一个数据结构进行排序(Sort)； ⑻对一个数据结构进行查找(Search)。 以上只列举了一些常见运算，实际应用当中可能会遇到许多其它运算。 云淡风清 http://gsqls.blog.163.com/ 1.4抽象数据类型(Abstract Data Type)1.4.1抽象数据类型简介： 简称ADT，是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。说明： ⑴ADT和数据类型实质上是一个概念，其区别是：ADT的范畴更广,它不再局限于系统已定义并实现的数据类型，还包括用户自己定义的数据类型。 ⑵ADT的定义是由一个值域和定义在该值域上的一组操作组成。包括定义，表示和实现三个部分。⑶ADT的最重要的特点是抽象和信息隐蔽。抽象的本质就是抽取反映问题本质的东西，忽略非本质的细节，使所设计的结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐藏数据存储和操作实现的细节，使用者了解抽象操作或界面服务，通过界面中的服务来访问这些数据。 ADT不考虑物理结构以及算法的具体实现。 例：整数的数学概念和对整数所能进行的运算构成一个ADT，C语言中的变量类型int就是对这个抽象数据类型的一种物理实现。 1.4.2ADT的一般定义形式： ADT的一般定义形式是： ADT<抽象数据类型名> { 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT<抽象数据类型名> 其中数据对象和数据关系的定义用伪码描述。基本操作的定义是： <基本操作名>(<参数表>)初始条件：<初始条件描述> 操作结果：<操作结果描述> 说明： 初始条件：描述操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息。 操作结果：描述操作正常完成之后，数据结构的变化状况和应返回的结果。 1.5算法(Algorithm)1.5.1算法基本概念： 算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或 云淡风清 http://gsqls.blog.163.com/ 多个操作。 1.5.2算法的基本特征： 算法具有以下五个特性 ①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 ③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。 ④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 ⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 1.5.3算法的基本描述方法： 一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述等。 1.5.4算法与程序的异同比较： 算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。 1.5.5评价算法好坏的几个标准： 评价一个好的算法有以下几个标准 ①正确性(Correctness)：算法应满足具体问题的需求。 ②可读性(Readability)：算法应易于供人阅读和交流。可读性好的算法有助于对算法的理解和修改。 ③健壮性(Robustness)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 ④通用性(Generality)：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。⑤效率与存储容量需求：效率指的是算法执行的时间；存储容量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。 1.6算法效率的度量 解决同一个问题的算法可能有多种，如何选择一个效率高的算法呢？应该来讲，与算法效率相关的因素有很多，如下： 云淡风清 http://gsqls.blog.163.com/ 1、算法选用何种策略； 2、问题的规模； 3、程序设计的语言； 4、编译程序所产生的机器代码的质量； 5、内存的大小； 6、外存的大小； 7、机器执行指令的速度； 8、其它。 而确定算法效率的方法通常有两种： 1.6.1事后统计： 先实现算法，然后运行程序，测算其时间和空间的消耗。缺点： 1、必须先依据算法编制程序并运行程序，耗费人力物力； 2、依赖软硬件环境，容易掩盖算法本身的优劣。由于算法的运行与计算机的软硬件等环境因素有关，不容易发现算法本身的优劣。同样的算法用不同的编译器编译出的目标代码数量不同，完成算法所需的时间也不同；若计算机的存储空间较小，算法运行时间也就会延长； 3、没有实际价值。测试花费不少时间但并没有解决现实中的实际问题。 1.6.2事前分析： 仅仅通过比较算法本身的复杂性来评价算法的优劣，不考虑其它的软硬件因素，通常考查算法所用的时间和所需的存储空间。 算法复杂性的度量可以分为时间复杂度和空间复杂度。 1.6.3算法的时间复杂度(Time complexity) 1、算法的时间复杂度 算法的时间复杂度用于度量一个算法所用的时间。 算法所用的时间主要包括程序编译时间和运行时间。由于一个算法一旦编译成功可以多次运行，因此可以忽略编译时间，只讨论算法的运行时间。 算法的运行时间依赖于加、减、乘、除、等基本的运算以及参加运算的数据量的大小，另外，与计算机硬件和操作环境等也有关系。要想准确地估算时间是不可行的，而影响算法时间最为主要的因素是问题的规模，即输入量的多少。同等条件下，问题的规模越大，算法所花费的时间也就越长。例如，求1+2+3+„+n的算法，即n个整数的累加求和，这个问题的规模为n。因此，运行算法所需的时间T是问题规模n的函数，记作T(n)。 同等条件下，相同或类似的基本操作在真正程序运行过程中所花费的时间也差不多，这样，如果两个不同算法中一个所含基本操作多而另一个所含基本操作少，则包含基本操作少的算法其花费时间也就较少。因此，通常用算法中基本语句的执行次数来作为度量算法速度快慢的依据，而这种度量时间复杂度的方法得出的不是时间量，而是一种增长趋势的度量，即当问题规模n增大时，T(n)也随之变大。换言之，当问题规模充分大时，算法中基本语句的执行次数为在渐进意义下的阶，称为算法的渐进时间复杂度，简称时间复杂度，通常用大O记号表示。用数学语言通常描述为：若当且仅当存在正整数n和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称该算法的渐进时间复杂度为T(n)=O(f(n))。 一般地，常用最内层循环内的语句中的原操作的执行频度(重复执行的次数)来表示时间复杂度。 2、时间复杂度分析举例： 例：两个n阶方阵的乘法。 云淡风清 http://gsqls.blog.163.com/ for(i=1;i<=n;++i)for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];} 分析：由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3，时间复杂度为T(n)=O(n3)。 例： { ++x;s=0;} 分析：将x自增看成是基本操作，则语句频度为1，即时间复杂度为O(1)。 如果将s=0也看成是基本操作，则语句频度为2，其时间复杂度仍为O(1)，即常量阶。只要T(n)不是问题规模n的函数，而是一个常数，它的时间复杂度则均为O(1)。例：以下程序段： for(i=1;i<=n;++i){ ++x;s+=x;} 分析：基本语句的语句频度为：n，其时间复杂度为：O(n)，即为线性阶。例：以下程序段： for(i=1;i<=n;++i)for(j=1;j<=n;++j){ ++x; s+=x;} 分析：基本语句的语句频度为：n2，其时间复杂度为：O(n2)，即为平方阶。 定理：若T(n)=amnm+am-1nm-1+„+a1n+a0是一个m次多项式，则T(n)=O(nm)，即复杂度表达式只取一个n趋向于无穷大时的同阶无穷小表达式即可。 通过对算法复杂度的分析，总结出这样一条结论，在计算任何算法的复杂度时，可以忽略所有低次幂和最高次幂的系数，这样可以简化算法分析，并使注意力集中在增长率上。 从本质上来讲，此种策略也就是只考虑对算法复杂度影响最大的因素而忽略次要因素。例：以下程序段： for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i,j]=x; } 云淡风清 http://gsqls.blog.163.com/ 分析：基本语句的语句频度为： 1+2+3+„+n-2 =(1+n-2)×(n-2)/2 =(n-1)×(n-2)/2 =(n2-3n+2)/2 按上述定理，时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 一个算法时间复杂度为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数(即零次多项式)来界定。而一个时间为O(n2)的算法则由一个二次多项式来界定。 3、常见表示时间复杂度的阶： O(1)：常量时间阶 O(n)：线性时间阶 O(㏒n)：对数时间阶 O(n㏒n)：线性对数时间阶 O(nk)：k≥2，k次方时间阶 4、常见时间复杂度大小关系分析： 以下六种计算算法时间复杂度的多项式是最常用的，其大小关系通常为： O(1) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随输入数据集的不同而不同。例：素数的判断算法。 void prime(int n)//n是一个正整数 { int i=2;while((n%i)!=0 && i*1.0 i++;if(i*1.0>sqrt(n)) printf(“&d 是一个素数n”,n);else printf(“&d 不是一个素数n”,n);} 此例中执行频率最高的语句为i++;，此语句最少执行0次，最多执行sqrt(n)次，对于不同的n，执行次数不确定。 对于此类算法，如果输入数据不同，则算法运行时间也不同，因此要全面分析一个算法，需要考虑算法在最好、最坏、平均情况下的时间消耗。由于最好情况出现的概率太小，因此不具代表性，但是，当最好情况出现的概率大时，应该分析最好情况；虽然最坏情况出现的概率也太小，不具代表性，但是分析最坏情况能够让人们知道算法的运行时间最坏能到什么程度，这一点在实时系统中很重要；分析平均情况是比较普遍的，特别是同一个算法要处理不同的输入时，通常假定输入的数据是等概率分布的。 例：冒泡排序法。 void bubble_sort(int a[],int n) 云淡风清 http://gsqls.blog.163.com/ { int temp;change=false;for(i=n-1;change=TURE;i>1 && change;--i) for(j=0;j if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; change=TURE; } } 最好情况：0次 最坏情况：1+2+3+⋯+n-1=n(n-1)/2平均时间复杂度为：O(n2)1.6.4算法的空间复杂度(Space complexity) 1、算法的空间复杂度 算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间数量指的不是程序指令、常数、指针等所需要的存储空间，也不是输入数据所占用的存储空间，辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。算法的空间复杂度分析方法同算法的时间复杂度相似，设S(n)是算法的空间复杂度，通常可以表示为： S(n)=O(f(n))其中：n为问题的规模(或大小)。该存储空间一般包括三个方面： 指令常数变量所占用的存储空间； 输入数据所占用的存储空间； 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。如： 一维数组a[n]：空间复杂度O(n)二维数组a[n][m]：空间复杂度O(n*m)例：数组a中有10000个数，要求将所有数据逆置(即顺序倒过来存放)。为达到逆置目的，有以下两种方案： 方案一： int a[10000],b[10000],i;for(i=0;i<10000;i++)b[10000-i-1]=a[i];for(i=0;i<10000;i++)a[i]=a[b];方案二： int a[10000],t,i;for(i=0;i<10000/2;i++) 云淡风清 http://gsqls.blog.163.com/ { t=a[i];a[i]=a[10000-i-1];a[10000-i-1]=t;} 很明显，方案二中的辅助空间数量为1，而方案一中的辅助空间数量为10000，方案二的空间复杂度优于方案一。 在算法的时间复杂度和空间复杂度中，我们更注重算法的时间性能。因此，在对算法性能的分析当中，通常均主要针对算法时间性能进行分析。 1.6.5学习算法的原因 讲述了这么多关于算法的基础知识，究竟为什么要学习算法呢？ 首先，算法无处不在。算法不仅出现在数学和计算机程序中，更普遍地出现在我们的生活中，在生活中做什么事情都要有一定的顺序，然而不同的顺序带来的效率和成果可能都会不同，只有学好了算法，才能让生活更有趣、更有效率。 其次，算法是程序的灵魂。学习计算机编程，必须要掌握好其灵魂，否则，写出来的程序就像是没有灵魂的躯体。 再次，算法是一种思想。掌握了这种思想，能够拓展思维，使思维变得清晰、更具逻辑性，在生活以及编程上的很多问题，也就更易解决。 最后，算法的乐趣。学习算法不仅仅是为了让它帮助人们更有效地解决各种问题，算法本身的趣味性很强，当通过烦琐的方法解决了一个问题后会感觉到有些疲惫，但是面对同一个问题，如若学会使用算法，更简单有效地解决了这个问题，会发现很有成就感，算法的速度、思想会让人觉得很奇妙。每一个奇妙的算法都是智慧的结晶。 学习算法的理由成千上万，不同的人可能出于不同的目的去学习算法，希望大家能够通过对课程的学习对算法有进一步的理解。 习题一 1、简要回答术语：数据，数据元素，数据结构，数据类型。 2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 3、数据结构的主要运算包括哪些？ 4、算法分析的目的是什么？算法分析的主要方面是什么？ 云淡风清 http://gsqls.blog.163.com/ 第2章 线性表 下表为某电台提供给听众的若干首英文歌曲名及相关点播情况统计信息： 由于实际的歌曲库可能很大，手工管理效率低，不方便，现请设计一个软件系统实现对此类歌曲库的管理。 分析： 此例中相邻的两首歌之间是一种一对一的关系，属于典型的线性结构，可按线性结构进行组织及管理。 2.1线性结构与线性表 2.1.1线性结构 如果一个数据元素序列满足： ⑴除第一个和最后一个数据元素外，每个数据元素只有一个直接前驱数据元素和一个直接后继数据元素； ⑵第一个数据元素没有前驱数据元素； ⑶最后一个数据元素没有后继数据元素。则称这样的数据结构为线性结构。 线性表、栈、队列、串和数组都属于线性结构。如下图： 云淡风清 http://gsqls.blog.163.com/ 2.1.2线性表 线性表(Linear List)是一种最简单、最常用的线性结构，是一种可以在任意位置进行插入和删除数据元素操作的、由n(n≥0)个相同类型数据元素a1，a2，„，an组成的线性结构。在这种结构中： ⑴存在一个唯一的被称为“第一个”的数据元素； ⑵存在一个唯一的被称为“最后一个”的数据元素； ⑶除第一个元素外，每个元素均有唯一一个直接前驱； ⑷除最后一个元素外，每个元素均有唯一一个直接后继。线性表中的数据元素的个数n称为线性表的长度。当n=0时，称为空表。空线性表用符号()表示。 当n>0时，将非空的线性表记作：(a1，a2，„an)，其中符号ai(1≤i≤n)表示第i个抽象数据元素。 a1称为线性表的第一个(头)结点，an称为线性表的最后一个(尾)结点。a1，a2，„ai-1都是ai(2≤i≤n)的前驱，其中ai-1是ai的直接前驱； ai+1，ai+2，„an都是ai(1≤i ≤n-1)的后继，其中ai+1是ai的直接后继。 线性结构是最常用、最简单的数据结构，而线性表是一种典型的线性结构，其基本特点是可以在任意位置进行插入和删除等操作，且数据元素是有限的。 线性表可以用顺序存储结构或链式存储结构实现。用顺序存储结构实现的线性表称为顺序表，用链式存储结构实现的线性表称为链表。链表主要有单链表、循环单链表和循环双链表三种。顺序表和链表各有优缺点，并且优缺点刚好相反，在实际应用中要根据情况选择对操作及性能有利的存储结构。 线性表中的数据元素ai所代表的具体含义随实际应用领域的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。 ◆线性表中的结点可以是单值元素(每个元素只有一个数据项)。例1：26个英文字母组成的字母表：(A，B，C、„、Z)例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188)例3：一副扑克的点数：(2，3，4，„，J，Q，K，A)◆线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。 例4：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’，08/12/1984)„，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)} ◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。◆线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。 ◆对线性表的基本操作如下(实际应用中要根据需要选择相应操作或者添加未列出的操作)： ⑴建立空表L ⑵返回表L的长度，即表中元素个数 ⑶取线性表L中位置i处的元素(1≤i≤n)⑷取i的直接前驱元素 ⑸取i的直接后继元素 ⑹查询元素x在L中的逻辑位置 ⑺在线性表L的位置i处插入元素x，原位置元素后移一个位置 ⑻从线性表L中删除位置i处的元素 ⑼判断线性表是否为空 ⑽清空已存在的线性表 ⑾遍历所有元素 云淡风清 http://gsqls.blog.163.com/ ⑿根据所给关键字查询元素并返回其详细信息 ⒀修改表中元素 ⒁对所有元素按条件排序 2.1.3线性表的抽象数据类型定义 ADT List { 数据对象：D = { ai | ai∈ElemSet, i=1,2,„,n, n≥0 } 数据关系：R = { 操作结果：构造一个空的线性表L； ListLength(L)初始条件：线性表L已存在； 操作结果：返回线性表中的元素个数； GetElem(L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert(L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L)+1，线性表未满； 操作结果：在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移； ListLocate(L,e)初始条件：线性表L已存在； 操作结果：返回元素e在L中的逻辑位置，不存在则返回0； ListDelete(L,i)初始条件：线性表L已存在，1≤i≤ListLength(L)； 操作结果：从表L中删除位置i处的元素； ListClear(L)初始条件：线性表L已存在； 操作结果：清空已存在的表； ListTraverse(L)初始条件：线性表L已存在； 操作结果：遍历输出所有元素； ListUpdate(L,i,e)初始条件：线性表L已存在,1≤i≤ListLength(L)； 操作结果：将线性表L中第i个位置的值置为e； ListSort(L)初始条件：线性表L已存在； 操作结果：按一定条件对所有元素重新排序； ListDestroy(L)初始条件：线性表L已存在； 操作结果：释放线性表空间； … 云淡风清 http://gsqls.blog.163.com/ } ADT List 2.2线性表的顺序存储 2.2.1线性表的顺序存储结构 顺序存储：把线性表的结点按逻辑顺序依次存入地址连续的一组存储单元里。用这种方法存储的线性表简称顺序表。 顺序存储的线性表的特点： ◆线性表的逻辑顺序与物理顺序一致； ◆数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现的。设有非空的线性表：(a1，a2，„an)。顺序存储如下图所示。 在具体的机器环境下，设线性表的每个元素需占用len个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系： Loc(ai+1)=Loc(ai)+l 线性表的第i个数据元素ai的存储位置为： Loc(ai)=Loc(a1)+(i-1)*len 高级语言中同一个数组的各个元素占用连续存储单元，具有随机存取(指存取同一数组各元素的时间开销相同，不受所处位置的限制)的特性，故而在高级语言中通常用数组来存储顺序表。除了用数组来存储线性表的元素之外，顺序表还应该表示线性表的长度属性以方便某些操作，所以用结构体类型来定义顺序表类型。 #include -1 #define MAX_SIZE 100 //最大长度 typedef int Status;//状态 typedef int ElemType;//元素类型，可根据实际需要更改 typedef struct Sqlist { ElemType *Elem_Array;//线性表存储空间地址 int Length;//线性表长度 } SqList;注意：C语言中数组的下标值是从0开始，第i个元素的下标值是i-1。 2.2.2顺序表的基本操作 顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。 以下将对几种主要的操作进行讨论。#include 云淡风清 http://gsqls.blog.163.com/ #include -1 #define MAX_SIZE 100 //最大长度 typedef int Status;//状态 typedef int ElemType;//元素类型，可根据实际需要更改 typedef struct Sqlist { ElemType Elem_Array[MAX_SIZE];//线性表存储空间地址 int Length;//线性表长度 } SqList;/* 1、初始化 构造一个空的线性表 */ Status Init_SqList(SqList *L){ L->Length=0;return OK;} /* 2、测长度 返回线性表中的元素个数 */ int Length_SqList(SqList *L){ return L->Length;} /* 3、取元素 用e返回L中第i个数据元素的值，1≤i≤ListLength(L)*/ Status Get_SqList(SqList *L,int i,ElemType *e){ if((i>=1)&&(i<=L->Length)){ *e=L->Elem_Array[i-1];//i位置对应的元素下标为i-1 return OK;} else return ERROR;} 云淡风清 http://gsqls.blog.163.com/ /* 4、顺序线性表的插入 在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移。要求1≤i≤ListLength(L)+1，线性表未满。实现步骤： (1)将线性表L中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。 (3)线性表长度加1。*/ Status Insert_SqList(Sqlist *L,int i,ElemType e){ int j;if((i<1)||(i>L->Length+1))//位置错误 return ERROR;else if(L->Length>=MAX_SIZE)//线性表上溢 //实际开发中达到空间上限时可用remalloc()函数重新分配空间，扩大空间容量 return ERROR; else { //i-1位置以后的所有结点后移 for(j=L->Length-1;j>=i-1;--j) L->Elem_Array[j+1]=L->Elem_Array[j]; L->Elem_Array[i-1]=e;//在i-1位置插入结点 L->Length++;//线性表长度增1 return OK; } } /* 时间复杂度分析： 在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中的第i个位置插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。 总的平均移动次数：Einsert=∑pi*(n-i+1)(1≤i≤n)计算得：Einsert=n/2。 即在顺序表上做插入运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。 */ /* 5、线性表元素位置查询 返回元素e在L中的逻辑位置，不存在则返回0 云淡风清 http://gsqls.blog.163.com/ */ int Locate_SqList(Sqlist *L,ElemType e){ int i,found=0;//found用于表示是否找到，0：未找到 1：找到 i=0;//从第一个开始查询 while((i if(L->Elem_Array[i]==e) found=1; else i++;if(found==1) return i+1;//返回逻辑位置编号 else return 0;//未找到，返回0 } /* 6、删除指定位置元素 在线性表： L=(a1，„ai-1，ai，ai+1，„，an)中删除结点ai(1≦i≦n)，使其成为线性表： L=(a1，„ai-1，ai+1，„，an)要求1≤i≤ListLength(L)，线性表未空。实现步骤： (1)将线性表L中的第i+1个至第n个结点依此向前移动一个位置。(2)线性表长度减1。*/ Status Delete_SqList(Sqlist *L,int i){ int k;if(L->Length==0)//线性表空 { printf(“线性表L为空!n”); return ERROR;} else if(i<1||i>L->Length)//指定位置不合适 { printf(“要删除的数据元素不存在!n”); return ERROR; } else { //i位置以后的所有结点前移 for(k=i;k L->Elem_Array[k-1]=L->Elem_Array[k]; 云淡风清 http://gsqls.blog.163.com/ L->Length--;//线性表长度减1 return(OK); } } /* 时间复杂度分析： 删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。 则总的平均移动次数：Edelete=∑Pi*(n-i) (1≤i≤n)计算得：Edelete=(n-1)/2 即在顺序表上做删除运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低，因此算法的平均时间复杂度为O(n)。 */ /* 7、清空 */ Status Clear_SqList(Sqlist *L){ L->Length=0;return OK;} /* 8、遍历 以输出为例 */ Status Traverse_SqList(Sqlist *L){ int i;printf(“共有%d个元素，以下为具体内容：n”,L->Length);for(i=0;i printf(“%8d”,L->Elem_Array[i]);printf(“n------------------END------------------n”);return OK;} /* 9、修改 将线性表L中第i个位置的值置为e。要求线性表L已存在且1≤i≤ListLength(L)。*/ Status Update_SqList(Sqlist *L,int i,ElemType e){ if((i<1)||(i>L->Length))//位置错误 云淡风清 http://gsqls.blog.163.com/ return ERROR;else { L->Elem_Array[i-1]=e;//放置新数据 return OK;} } /* 10、排序 按要求对线性表中元素排序。*/ Status Sort_SqList(Sqlist *L){ int i,j;ElemType temp;for(i=1;i<=L->Length-1;i++) for(j=0;j<=L->Length-i-1;j++) { if(L->Elem_Array[j] { temp=L->Elem_Array[j]; L->Elem_Array[j]=L->Elem_Array[j+1]; L->Elem_Array[j+1]=temp; } } return OK;} /* 主函数 */ void main(){ int xz=1,i;SqList L;ElemType e;while(xz!=0){ printf(“ 1、初始化n 2、测长度n 3、取元素n 4、插入n 5、查询n 6、删除n 7、清空n 8、遍历n 9、修改n10、排序n 0、结束n请选择：”); scanf(“%d”,&xz); switch(xz) { case 1: if(Init_SqList(&L)==OK) 云淡风清 http://gsqls.blog.163.com/ printf(“初始化成功！n”);else printf(“初始化未成功！n”);break;case 2: printf(“线性表长度为：%dn”,Length_SqList(&L));break;case 3: printf(“请输入要取元素的位置：”);scanf(“%d”,&i);if(Get_SqList(&L,i,&e)==OK) printf(“指定位置上的元素为：%dn”,e);else printf(“Error！n”);break;case 4: printf(“请输入要插入的位置：”);scanf(“%d”,&i);printf(“请输入要插入的元素内容：n”);scanf(“%d”,&e);if(Insert_SqList(&L,i,e)==OK) printf(“插入成功n”);else printf(“Error！n”);break;case 5: printf(“请输入要查询的元素内容：”);scanf(“%d”,&e);printf(“此元素逻辑位置为：%d(0表示未找到)。n”,Locate_SqList(&L,e));break;case 6: printf(“请输入要删除元素的位置：”);scanf(“%d”,&i);if(Delete_SqList(&L,i)==OK) printf(“删除成功n”);else printf(“Error！n”);break;case 7: Clear_SqList(&L);break;case 8: Traverse_SqList(&L);break; 云淡风清 http://gsqls.blog.163.com/ case 9: printf(“请输入要修改的元素位置：”); scanf(“%d”,&i); printf(“请输入元素的新内容：n”); scanf(“%d”,&e); if(Update_SqList(&L,i,e)==OK) printf(“修改成功n”); else printf(“Error！n”); break; case 10: Sort_SqList(&L); printf(“排序完成！n”); break; case 0: printf(“谢谢使用，再见！n”); break; default: printf(“输入错误！n”); break; } } } 需要说明的是，本例没有实现空间的动态分配，若要实现动态分配，可参照第三章“栈的动态顺序存储结构”的做法。 2.2.3顺序存储线性表的特点 优点：表中任意一个结点的存取很方便，可以进行随机存取，处于不同位置上的结点的存取时间从理论上来说相同，也能进行插入和删除操作。 缺点： (1)插入和删除不方便。为保持连续存放，操作中需要移动大量元素。 (2)会造成空间的浪费以及不易扩充。所占空间通常情况下大小固定，处理长度变化较大的线性表时，分配空间大小不够，会造成溢出；分配空间太大，会造成浪费。 2.3线性表的链式存储 2.3.1线性表的链式存储结构 链式存储：用一组任意(即不必要连续)的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。 链表中结点所占用的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的，链表中结点的逻辑顺序和物理顺序不一定相同。 为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的 云淡风清 http://gsqls.blog.163.com/ 地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如下图所示。 data：数据域，存放结点的值。 next：指针域，存放结点的直接后继的地址。 链表通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起。每一个结点只包含一个指针域的链表，称为单链表。 为操作方便，总是在链表的第一个结点之前附设一个头指针变量head指向第一个结点。头结点的数据域可以不存储任何信息(或存放链表长度等辅助信息)，此时通常称为带头结点的单链表。当然，也可以让头结点的数据域存放有效数据，此时称为不带头结点的单链表。相对而言，带头结点的单链表浪费了一个结点的数据域，但会给编程带来一定方便。 带头结点的单链表其基本结构如下： 说明： (1)整个链表由若干个结点组成，一个结点占用一个内存块，而每个结点又分为两大部分：数据域和指针域，其中数据域存放用户数据，指针域用于存放后一个结点的地址，通过指针域将逻辑上前后相邻的结点连接起来，这样，通过前一个结点指针域中存放的地址就可以找到后一个结点。可看出，每个结点的指针域实际上充当了指针变量的角色，只要结点数可变，则意味着指针变量数也可变，而事实上结点所对应的这些内存块完全可以多次动态分配，这也就意味着指针域(相当于指针变量)的个数可以根据需要动态调整，这就解决了前述的“程序中变量个数固定，但问题本身所需变量个数不定”的矛盾。 (2)设置一个头指针变量指向首结点，在带头结点的单链表中，此结点不存放有效数据。(3)末尾结点的指针域设置为空“NULL”表示链表的结束，相当于字符串中的' '。 (4)在没有用户数据的情况下，此链表只有一个结点，此结点既是首结点，又是末结点，结点的指针域为“NULL”，此时表示链表为逻辑“空”，也就是说，链表的初始状态应该如下图所示。 单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名。例 1、线性表L=(bat，cat，eat，fat，hat)其带头结点的单链表的逻辑状态和物理存储方式如下图所示。 云淡风清 http://gsqls.blog.163.com/ 1、结点的描述与实现 C语言中用带指针的结构体类型来描述 typedef int ElemType;typedef struct Lnode { ElemType data;//数据域，保存结点的值 struct Lnode *next;//指针域，保存后继结点地址 }LNode; //结点的类型 2、结点空间分配及回收的实现 结点存储空间是通过动态内存分配和释放来实现的，即需要时分配，不需要时释放。在C语言中可通过标准函数：malloc()，realloc()，sizeof()，free()等来实现分配。 动态分配：p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。动态释放：free(p);系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc()函数时的返回值。动态重新分配：p=(LNode*)realloc(p,newsize);先判断当前的指针是否有足够的连续空间，如果有，扩大p指向的地址，并且将p返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来p所指内存区域，同时返回新分配的内存区域的首地址，即重新分配存储器块的地址。返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 3、最常用的基本操作 ⑴ 结点的赋值 LNode *p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;讲课时板书教案上的几种常见的指针操作。效果如下图。 ⑵常见的指针操作 ①q=p; 云淡风清 http://gsqls.blog.163.com/ ②q=p->next; ③p=p->next; ④q->next=p; ⑤q->next=p->next; 云淡风清 http://gsqls.blog.163.com/ 2.3.2单链式的基本操作 以带头结点的单链表为例。#define OK #define ERROR -1 typedef int Status;//状态 #include “stdlib.h” #include “stdio.h” typedef int ElemType;typedef struct Lnode { ElemType data;//数据域，保存结点的值 struct Lnode *next;//指针域，保存后继结点地址 }LNode; //结点的类型 /* 1、链表初始化(建立空链表)*/ LNode * Init_LinkList(void){ LNode *L;L=(LNode *)malloc(sizeof(LNode));//给头结点分配空间 if(L!=NULL) L->next=NULL;//指针域置为空以作为结束标记 return L;} /* 2、头插入法建表 从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止，每次插入的结点都作为链表的第一个数据结点。 */ 云淡风清 http://gsqls.blog.163.com/ Status Create1_LinkList(LNode *L){ ElemType data;char sfjx=1;//0：结束 1：继续 LNode *p;while(sfjx!=0){ p=(LNode *)malloc(sizeof(LNode));//给新结点分配空间 if(p==NULL) return ERROR;//空间分配不成功 else { printf(“请输入元素内容：”); scanf(“%d”,&data);//读入值 p->data=data;//数据域赋值 //钩链，新创建的结点总是作为第一个数据结点 p->next=L->next; L->next=p; } printf(“是否继续(0：结束 1：继续)：”); scanf(“%d”,&sfjx);} return OK;} /* 3、尾插入法建表 头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。 该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。*/ Status Create2_LinkList(LNode *L){ ElemType data;char sfjx=1;//0：结束 1：继续 LNode *p,*q;//找到已有链表的末结点 q=L;while(q->next!=NULL) q=q->next;while(sfjx!=0){ p=(LNode *)malloc(sizeof(LNode));//给新结点分配空间 if(p==NULL) 云淡风清 http://gsqls.blog.163.com/ return ERROR;//空间分配不成功 else { printf(“请输入元素内容：”); scanf(“%d”,&data);//读入值 p->data=data;//数据域赋值 //钩链，新创建的结点总是作为最后一个结点 q->next=p; q=p;//q重新指向末结点 } printf(“是否继续(0：结束 1：继续)：”); scanf(“%d”,&sfjx);} q->next=NULL;//重设链表结束标记 return(OK);} /* 4、按序号查找，取单链表中的第i个元素。 对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。*/ Status Get_LinkList(LNode *L,int i,ElemType *e){ int j=1;LNode *p;p=L->next;//使p指向第一个结点 while((p!=NULL)&&(j p=p->next;//移动指针p j++; //j计数 } if(p==NULL)//找不到 return(ERROR);else { *e=p->data; return(OK);} } /* 云淡风清 http://gsqls.blog.163.com/ 5、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点? 若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。 */ LNode *Locate_LinkList(LNode *L,ElemType key){ LNode *p;p=L->next;while((p!=NULL)&&(p->data!=key)) p=p->next;if(p!=NULL)//找到了 return p;else//找不到 return(NULL);} /* 6、单链表的插入，插入到指定位置 在以L为头结点的单链表的第i个位置插入值为e的结点。 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。 */ Status Insert_LinkList(LNode *L,int i,ElemType e){ int j=0;LNode *p,*q;p=L;//找待插入位置的前一个结点位置 while((p!=NULL)&&(j p=p->next; j++;} if((j!=i-1)||(p==NULL))//位置不合适 { printf(“位置不合适，无法插入！n”); return ERROR;} else { q=(LNode *)malloc(sizeof(LNode));//给新结点分配空间 if(q==NULL) return ERROR; else 云淡风清 http://gsqls.blog.163.com/ { //实现插入 q->data=e; q->next=p->next; p->next=q; return OK; } } } /* 7、按序号删除 删除单链表中的第i个结点。 为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p->next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。设单链表长度为n，则删去第i个结点仅当1≤i≤n时是合法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是p->next!=NULL。显然此算法的时间复杂度也是O(n)。 */ Status Delete1_LinkList(LNode *L,int i){ int j=1;LNode *p,*q;p=L;q=L->next;//找待删除位置的前一个结点位置 while(q!=NULL && j p=q; q=q->next; j++;} if((q==NULL)||(i<=0)){ printf(“位置不合适，无法删除！n ”); return ERROR;} else { //实现删除 p->next=q->next; free(q); return OK;} } 云淡风清 http://gsqls.blog.163.com/ /* 8、按值删除 删除单链表中值为key的第一个结点。 与按值查找相类似，首先要查找值为key的结点是否存在? 若存在，则删除；否则返回NULL。*/ Status Delete2_LinkList(LNode *L,int key){ LNode *p=L,*q=L->next;//找待删除结点位置，q指向其位置，p指向其前驱结点 while(q!=NULL && q->data!=key){ p=q; q=q->next;} if(q!=NULL)//找到了 { //实现删除 p->next=q->next; free(q); return OK;} else { printf(“所要删除的结点不存在！n”); return ERROR;} } /* 9、删除单链表中值为key的所有结点 与按值查找相类似，但比前面的算法更简单。 基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下一个结点，直到所有的结点都检查。 */ void Delete3_LinkList(LNode *L,int key){ LNode *p=L,*q=L->next;//p始终指向q的前驱，以方便删除操作的实现 while(q!=NULL){ if(q->data==key) { p->next=q->next; 云淡风清 http://gsqls.blog.163.com/ free(q); q=p->next; } else { p=q; q=q->next; } } } /* 10、删除单链表中所有值重复的结点，使得所有结点的值都不相同 与按值查找相类似，但比前面的算法更复杂。 基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。 */ void Delete4_LinkList(LNode *L){ LNode *p=L->next,*q,*ptr;while(p!=NULL)//检查链表中所有结点 { q=p; ptr=p->next; while(ptr!=NULL)//检查结点p的所有后继结点ptr { if(ptr->data==p->data) { q->next=ptr->next; free(ptr); ptr=q->next; } else { q=ptr; ptr=ptr->next; } } p=p->next;} } /* 云淡风清 http://gsqls.blog.163.com/ 11、修改指定位置的数据 */ Status Modify_LinkList(LNode *L,int i,ElemType e){ int j=1;LNode *p;p=L->next;//找待修改结点位置 while(p!=NULL && j p=p->next; j++;} if((p==NULL)||(i<=0))//找不到 { printf(“位置不合适，无法修改！n ”); return ERROR;} else { p->data=e; return OK;} } /* 12、单链表遍历 以输出为例 */ void Traverse_LinkList(LNode *L){ LNode *p;p=L->next;while(p!=NULL){ printf(“%8d”,p->data); p=p->next;} printf(“n”);} /* 13、单链表的合并 设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以Lc为头指针的有序链表。算法说明：算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。 云淡风清 http://gsqls.blog.163.com/ 合并了值为-7，-2的结点后示意图如下图所示。 */ LNode *Merge_LinkList(LNode *La,LNode *Lb){ LNode *Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La;//指向新链表的末结点 pa=La->next;pb=Lb->next;while(pa!=NULL && pb!=NULL){ if(pa->data data)//将pa所指的结点合并，pa指向下一个结点 { pc->next=pa; pc=pa; pa=pa->next; } else if(pa->data>pb->data)//将pb所指的结点合并，pb指向下一个结点 { pc->next=pb; pc=pb; pb=pb->next; 云淡风清 http://gsqls.blog.163.com/ } else//将pa所指的结点合并，pb所指结点删除 { pc->next=pa; pc=pa; pa=pa->next; ptr=pb; pb=pb->next; free(ptr); } } //将剩余的结点链上 if(pa!=NULL) pc->next=pa;else pc->next=pb; free(Lb);return(Lc);} /* 14、单链表的排序 采用插入排序方法，以升序为例 */ void Sort_LinkList(LNode *L){ LNode *p,*q,*r,*s;p=L->next;L->next=NULL;while(p!=NULL){ q=L->next; r=L; while((q!=NULL)&&(p->data>q->data)) { q=q->next; r=r->next; } s=p->next; r->next=p; p->next=q; p=s;} } 云淡风清 http://gsqls.blog.163.com/ /* 15、单链表的释放 */ void Release_LinkList(LNode *L){ LNode *p,*q;p=L;//指向头结点，从此结点开始释放 while(p!=NULL){ q=p->next; free(p); p=q;} } void main(){ int xz=1,i;LNode *L,*L1,*L2;ElemType e;while(xz!=0){ printf(“ 1、链表初始化n 2、头插入法建表n 3、尾插入法建表n 4、按序号查找n 5、按值查找n 6、单链表的插入n”); printf(“ 7、按序号删除n 8、按值删除n 9、删除单链表中指定值的所有结点n10、删除单链表中所有值重复的结点n”); printf(“ 11、修改指定位置的数据n12、单链表遍历n13、单链表的合并n14、单链表的排序n15、单链表的释放n 0、结束n请选择：”); scanf(“%d”,&xz); switch(xz) { case 1: L=Init_LinkList(); if(L!=NULL) printf(“初始化成功！n”); break; case 2: if(Create1_LinkList(L)==OK) printf(“建立成功！n”); else printf(“建立不成功！n”); break; case 3: if(Create2_LinkList(L)==OK) printf(“建立成功！n”); 云淡风清 http://gsqls.blog.163.com/ else printf(“建立不成功！n”);break;case 4: printf(“请输入要查找元素的序号：”);scanf(“%d”,&i);if(Get_LinkList(L,i,&e)==OK) printf(“%dn”,e);else printf(“找不到！n”);break;case 5: printf(“请输入要查找元素的关键字：”);scanf(“%d”,&e);L1=Locate_LinkList(L,e);if(L1!=NULL) printf(“%dn”,L1->data);else printf(“找不到！n”);break;case 6: printf(“请输入要插入元素的内容：”);scanf(“%d”,&e);printf(“请输入插入位置：”);scanf(“%d”,&i);if(Insert_LinkList(L,i,e)==OK) printf(“插入成功！n”);else printf(“插入不成功！n”);break;case 7: printf(“请输入要删除元素的位置：”);scanf(“%d”,&i);if(Delete1_LinkList(L,i)==OK) printf(“成功删除！n”);else printf(“未成功删除！n”);break;case 8: printf(“请输入要元素的内容：”);scanf(“%d”,&e);if(Delete2_LinkList(L,e)==OK) printf(“成功删除！n”);else 云淡风清 http://gsqls.blog.163.com/ printf(“未成功删除！n”);break;case 9: printf(“请输入要元素的内容：”);scanf(“%d”,&e);Delete3_LinkList(L,e);printf(“成功删除！n”);break;case 10: Delete4_LinkList(L);printf(“成功删除！n”); break;case 11: printf(“请输入修改位置：”);scanf(“%d”,&i);printf(“请输入元素的新内容：”);scanf(“%d”,&e);if(Modify_LinkList(L,i,e)==OK) printf(“修改成功！n”);else printf(“修改不成功！n”);break;case 12: Traverse_LinkList(L); break;case 13: L1=Init_LinkList();L2=Init_LinkList();if((L1==NULL)||(L2==NULL)) printf(“初始化不成功！n”);else { printf(“请建立第一个链表：n”); Create2_LinkList(L1); printf(“请建立第二个链表：n”); Create2_LinkList(L2); Sort_LinkList(L1); Sort_LinkList(L2); L=Merge_LinkList(L1,L2); printf(“合并后的结果如下：n”); Traverse_LinkList(L);} break;case 14: 云淡风清 http://gsqls.blog.163.com/ } } Sort_LinkList(L);break;case 15: Release_LinkList(L); break;case 0: printf(“谢谢使用，再见！n”);break;default: printf(“输入错误！n”);break;} 2.4循环链表 循环链表(Circular Linked List)：是一种头尾相接的链表，其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环，这样，从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。 下图是带头结点的单循环链表的示意图。 循环链表的操作： 对于带头结点的单循环链表，除链表的合并外，其它操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上做以下简单修改： 1、判断是否是空链表 head->next==head; 2、判断是否是表尾结点 p->next==head;例：有m个人围成一圈，顺序排号。从第一个人开始报数，凡报到3的人退出圈子，问最后留下的那位是原来的第几号？ 根据问题描述可知，该问题中m个人围坐在一起形成首尾相接的环，比较自然的一种思路是用循环链表模拟这个环。从第3个人开始出圈，相当于从链表中删除一个结点。该程序主要由三个模块组成： 1、建立循环单链表存放初始各人编号； 2、报数并按顺序输出出圈人的编号； 3、输出剩下的人的编号。具体步骤如下： 云淡风清 http://gsqls.blog.163.com/ 第一步：输入人员总数； 第二步：创建循环链表并向单链表中填入人员编号； 第三步：找第一个开始报数的人； 第四步：数到3让此人出圈(删除对应结点)； 第五步：接着开始报数，重复第四步，直到圈中剩余一个为止； 第六步：输出剩下结点中的编号，即为最终所要求的编号。程序源代码： #include “stdio.h” #include “stdlib.h” #define MAXN 100 //最大个数 struct Node { int data;struct Node *next;};void main(){ struct Node *head, *s, *q, *t;int n, m, count=0, i;do//输入总个数 { printf(“请输入总个数(1－%d)：”,MAXN);scanf(“%d”,&m);}while((m<1)||(m>MAXN));do//输入出圈时要数到的个数 { printf(“要数到的个数(1--%d)：”,m);scanf(“%d”,&n);}while((n<1)||(n>m));for(i=0;i { s=(struct Node *)malloc(sizeof(struct Node));s->data=i+1;s->next=NULL;if(i==0){ head=s;q=head;} else { q->next=s;q=q->next;} 云淡风清 http://gsqls.blog.163.com/ } q->next=head;//形成圈 //以下代码输出原始状态 printf(“原始状态：n”);q=head;while(q->next!=head){ printf(“%4d”,q->data);q=q->next;} printf(“%4dn”,q->data);q=head;//以下代码实现出圈 printf(“出圈顺序：n”);do { count++;if(count==n-1){ t=q->next;q->next=t->next;count=0;printf(“%4d”,t->data);free(t);} q=q->next;}while(q->next!=q);printf(“n剩下的是%4dn”,q->data);} 注意：此程序采用的是不带头结点的单链表，以免在循环链表中由于不存放有效数据的头结点的存在而影响计数。 2.5双向链表 双向链表是为了克服单链表的单向性的缺陷而引入的。单链表只能从头到尾单向访问各结点，对操作的限制极大。双向链表(Double Linked List)指构成链表的每个结点中设立两个指针域，一个指向其直接前趋结点，一个指向其直接后继结点，这样形成的链表中有两个方向不同的链，故称为双向链表。 和单链表类似，双向链表一般也增加一个不存放实际有效数据的头结点，从而使某些操作更方便。下面为带头结点的双向链表示意图： 云淡风清 http://gsqls.blog.163.com/ 将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。 2.5.1双向链表的结点及其类型定义 双向链表的结点的类型定义如下。typedef struct Dulnode { ElemType data;struct Dulnode *prior,*next;}DulNode;双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：(p->prior)->next=p=(p->next)->prior;结点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p->next的直接前趋指针域中。 2.5.2双向链表的基本操作 1、双向链表结点的插入 将值为e的结点插入双向链表中。插入前后链表的变化如下图所示。 ①若插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是：“先右后左”，部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode));S->data=e;S->next=p->next;//先右 p->next->prior=S;//后左 p->next=S;//先右 S->prior=p;//后左 ②若插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序，部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode));S->data=e;p->next=S;S->next=q;S->prior=p;q->prior=S; 2、双向链表结点的删除 设要删除的结点为p，删除时可以不引入新的辅助指针变量，先直接断链，再释放结点。部分语句组如下： p->prior->next=p->next;p->next->prior=p->prior;free(p); 云淡风清 http://gsqls.blog.163.com/ 注意： 与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。 2.6一元多项式的表示和相加 2.6.1一元多项式的表示 一元多项式如下： p(x)=p0+p1x+p2x2+ „ +pnxn，由n+1个系数唯一确定。则在计算机中可用线性表(p0，p1，p2，„，pn)表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下： 1、顺序存储结构表示的类型 typedef struct { float coef; //系数部分 int expn;//指数部分 } ElemType; 2、链式存储结构表示的类型 typedef struct ploy { float coef; //系数部分 int expn; //指数部分 struct ploy *next;}Ploy;2.6.2一元多项式的相加 不失一般性，设有两个一元多项式： P(x)=p0+p1x+p2x2+ „ +pnxn，Q(x)=q0+q1x+q2x2+ … +qmxm (m 1、顺序存储表示的相加 线性表的定义： typedef struct { ElemType a[MAX_SIZE];int length;}Sqlist;用顺序表示的相加非常简单，访问第i项可直接访问：L.a[i-1].coef，L.a[i-1].expn 2、链式存储表示的相加 当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。 云淡风清 http://gsqls.blog.163.com/ 一元多项式相加的实质是： 指数不同：是链表的合并。 指数相同：系数相加，和为0，去掉结点，和不为0，修改结点的系数域。算法一： 就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表不再存在，当然就不再允许对原来两个多项式进行其它操作了。 算法描述： Ploy *add_ploy(ploy *La,ploy *Lb)//将以La，Lb为头指针表示的一元多项式相加 { ploy *Lc,*pc,*pa,*pb,*ptr;float x;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){ if(pa->expn expn)//将pa所指的结点合并，pa指向下一个结点 { pc->next=pa; pc=pa; pa=pa->next; } else if(pa->expn>pb->expn)//将pb所指的结点合并，pb指向下一个结点 { pc->next=pb; pc=pb; pb=pb->next; } else { x=pa->coef+pb->coef; if(abs(x)<=1.0e-6)//如果系数和为0，删除两个结点 { ptr=pa; pa=pa->next; free(ptr); ptr=pb; pb=pb->next; free(ptr); } else//如果系数和不为0，修改其中一个结点的系数域，删除另一个结点 { 云淡风清 http://gsqls.blog.163.com/ pc->next=pa; pa->coef=x; pc=pa; pa=pa->next; ptr=pb; pb=pb->next;free(pb); } } }//end of while if(pa==NULL) pc->next=pb;else pc->next=pa;return(Lc);} 算法之二： 对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。 算法描述： Ploy *add_ploy(ploy *La,ploy *Lb)//将以La，Lb为头指针表示的一元多项式相加，生成一个新的结果多项式 { ploy *Lc,*pc,*pa,*pb,*p;float x;Lc=pc=(ploy *)malloc(sizeof(ploy));pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){ if(pa->expn expn) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pa->coef; p->expn=pa->expn; p->next=NULL;//生成的结点插入到结果链表的最后，pa指向下一个结点 pc->next=p; pc=p; pa=pa->next; } else if(pa->expn>pb->expn) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pb->coef;p->expn=pb->expn; p->next=NULL; 云淡风清 http://gsqls.blog.163.com/ pc->next=p;//生成的结点插入到结果链表的最后，pb指向下一个结点 pc=p; pb=pb->next; } else { x=pa->coef+pb->coef; if(abs(x)<=1.0e-6)//系数和为0，pa, pb分别直接后继结点 { pa=pa->next; pb=pb->next; } else//若系数和不为0，生成的结点插入到结果链表的最后，pa, pb分别指向直接后继结点 { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=x;p->expn=pb->expn; p->next=NULL; pc->next=p; pc=p; pa=pa->next; pb=pb->next; } } }//end of while if(pb!=NULL) while(pb!=NULL) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pb->coef; p->expn=pb->expn; p->next=NULL; pc->next=p; pc=p; pb=pb->next; } if(pa!=NULL) while(pa!=NULL) { p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值 p->coef=pb->coef; p->expn=pa->expn; p->next=NULL; pc->next=p; 云淡风清 http://gsqls.blog.163.com/ } pc=p; pa=pa->next;} return(Lc);习题 二 1、简述下列术语：线性表，顺序表，链表。 2、何时选用顺序表，何时选用链表作为线性表的存储结构合适？各自的主要优缺点是什么？ 3、在顺序表中插入和删除一个结点平均需要移动多少个结点？具体的移动次数取决于哪些因素？ 4、链表所表示的元素是否有序？如有序，则有序性体现于何处？链表所表示的元素是否一定要在物理上是相邻的？有序表的有序性又如何理解？ 5、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 6、写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 7、设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。第四篇：绪论讲稿
第五篇：数据结构讲稿
点击咨询 