数据结构1（清华大学）ppt.ppt

数据结构（用面向对象方法与C+语言描述）第二版1,清华大学计算机系,殷人昆,数据结构,清华大学计算机系,殷人昆 王 宏,学习数据结构的背景,计算机是一门研究用计算机进行信息表示和处理的科学。 信息的表示和组织直接关系到信息处理程序的效率。随着计算机的普及，信息范围的拓宽，信息量的增加，使许多系统程序和应用程序的规模和复杂性增加。 为了编写出一个“好”的程序，必须分析待处理对象的特征及各对象间存在的关系，这就是数据结构这门课所要研究的问题。,数据结构课程的形成和发展,形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。,数据结构课程的地位,是介于数学、计算机硬件和计算机软件三者之间的一门核心课程数据结构课程的地位。,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科。是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，属于计算机学科中的一门综合性专业基础课程。 它不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。 该课程于1968年开始在国外作为一门独立课程设立，由美国唐欧克努特教授开创其最初体系。,必修课课程设置与数据结构的关系,选修课课程设置与数据结构的关系,数值计算解决问题的一般步骤：,数学模型选择计算机语言编出程序测试最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 典型问题： 电路分析与模拟 大坝（应力与应变）结构分析 弹道仿真程序 等,非数值计算问题,数据元素之间的相互关系一般无法用数学方程加以描述。 例如，电话号码查询问题 按顺序存储方式：遍历表 按姓氏索引方式：索引表 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。,求解非数值计算的问题的步骤：,主要考虑的是设计出合适的数据结构及相应的算法。即首先要考虑对相关的各种信息如何表示、组织和存储？ 可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,数据结构课程的特点,数据结构课程是计算机专业基础课，主要训练学生在系统开发中的数据设计、算法设计与分析及数据组织的能力，它是后续多门课程，如数据库、操作系统、编译原理、网络系统基础等的基础，对于从事计算机系统开发的人员，是必修课程之一。 需要有关“程序设计语言”和“离散数学”的知识作为课程的基础。 实践性较强。,教材和教学参考书,主教材 数据结构（用面向对象方法和C+描述）， 第二版，殷人昆，邓俊辉等，清华大学出版社 辅助教材 J. R. Hubbard, Data Structures with C+, 机械工业出版社影印, 中译名数据结构 习题与解答 C+版，￥40（七折￥ 28） 数据结构习题解析（用面向对象方法与C+语言描述），殷人昆等，清华大学出版社。,集体购买, 出版社七折优惠, 各班课代表统计需要数目用Email告诉我,实验上机,在微机上使用Borland C+ 或 Visual C+ 都可以。前者的系统体积小些。但同一个源程序在这两个编译器上可能会出现不同的编译信息。 本着教学相长的精神，希望经常对教学效果作出反馈，以便及时改进教学方法。 学好一门课程，教师的引导固然十分重要，但主要靠学生的自身努力。课堂教学可以起到画龙点睛的作用，但只有不断练习，才能巩固、掌握课程的内容。因此，本课程要求同学积极独立完成所布置的习题。,课程学习要求,自觉预习、遵守纪律、认真听课、及时复习； 按时、独立、认真地完成每次作业； 完成作业方式： 第5周、第9周、第13周和第17周提交作业； 作业分两部分： 第1部分是纸面作业，要求用笔写并不得复印和打印,课程学习要求,第2部分是上机作业，要求用C+语言编程实现，并通过网络学堂提交其源程序及可执行文件； 成绩评定标准： 纸面作业，占10%； 上机作业，占22%； 平时 4 次随堂测验（随机进行）取 3 次成绩好者，占18%； 期末考试，占50%。,教师信息,殷人昆，主讲教师 62795589, 王 宏，主讲教师 62783860, 王晓东，博士助教（负责1，2，3班） 李智超，博士助教（负责4，5班及外系） ,Thanks for Coming! 谢谢,2006年2月20日,THU,第一章 数据结构概念,数据结构电子教案,殷人昆 王 宏,什么是数据结构 抽象数据类型及面向对象概念 算法定义 模板 算法简单性能分析与度量,第一章 数据结构概念,“学生”表格,“课程”表格,学生 (学号,姓名,性别,籍贯),课程 (课程号,课程名,学分),选课 (学号,课程号,成绩),“选课单”包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的网状关系,UNIX文件系统的系统结构图,数据（data）,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数据的分类： 数值性数据 非数值性数据,数据元素 (data element),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项 (Data Item)组成。数据项是具有独立含义的最小标识单位。 数据元素又称为元素、结点、记录。,什么是数据结构,定义: 由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为： Data_Structure = D, R 其中，D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系的有限集合。,例：N 个网点之间的连通关系,树形关系,网状关系,数据结构是数据的组织形式,包括三个方面： 数据元素间的逻辑关系，即数据的逻辑结构； 数据元素及其关系在计算机存储内的表示，即数据的存储表示； 数据的运算，即对数据元素施加的操作。,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关； 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型； 数据的逻辑结构与数据元素本身的形式、内容无关； 数据的逻辑结构与数据元素的相对存储位置无关。,数据的逻辑结构分类,线性结构 线性表 非线性结构 树 图（或网络）,线性结构,树形结构,树 二叉树 二叉搜索树,堆结构,“最大”堆 “最小”堆,图结构 网络结构,数据的存储结构,数据的存储结构是逻辑结构用计算机语言的实现； 数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示,主要用于内存的存储表示,主要用于外存 (文件) 的存储表示,抽象数据类型及面向对象概念,数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,构造数据类型由基本数据类型或构造数据类型组成。 构造数据类型由不同成分类型构成。 基本数据类型可以看作是计算机中已实现的数据结构。 数据类型就是数据结构，不过它是从编程者的角度来使用的。 数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。,抽象数据类型 (ADTs: Abstract Data Types),抽象数据类型是由用户定义，用以表示应用问题的数据模型。 特点是：信息隐蔽和数据封装，使用与实现相分离。 抽象数据类型可用（D, S, P）三元组表示，其中，D 是数据元素的集合（简称数据对象），S 是 D上的关系集合，P 是对 D 的基本操作集合。,抽象数据类型,抽象数据类型的描述,其中数据对象、数据之间的关系用伪码描述；基本操作定义格式为,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,基本操作名（参数表） 前置条件：先决条件描述 后置条件：操作结果描述,基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。 “前置条件”描述了操作执行之前数据结构和参数应满足的先决条件，若不满足，则操作失败，并返回相应出错信息。 “后置条件”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若前置条件为空，则省略之。,自然数的抽象数据类型定义,ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是可用的服务。 Zero( ) : NaturalNumber /前置条件：无 /后置条件：返回自然数0,IsZero(x) : Boolean /前置条件：x为NaturalNumber /后置条件：if (x = 0) then 返回True else 返回False Add (x, y) : NaturalNumber /前置条件：x, y为NaturalNumber且x+yMaxInt /后置条件：返回 x+y Subtract (x, y) : NaturalNumber /前置条件： x, y为NaturalNumber且xy /后置条件：返回 x- y,Equal (x, y) : Boolean /前置条件： x, y为NaturalNumber /后置条件： if (x = y) 返回True else 返回 False Successor (x) : NaturalNumber /前置条件： x为NaturalNumber /后置条件： if (x = MaxInt) 返回 x else 返回 x+1 end NaturalNumber,面向对象的概念,面向对象 = 对象类继承通信 对象 在应用问题中出现的各种实体、事件、规格说明等。 由一组属性值和在这组值上的一组服务（或称操作）构成。 与C中构造数据类型不同在于：C中的构造数据类型的变量仅涉及属性值，与操作分离，而C+中的对象则不然。,类 (class)，实例 (instance) 具有相同属性和服务的对象归于同一类，形成类。 类中的对象为该类的实例。 同一类的实例 共享类的属性和类的操作； 通过继承共享其父类的公共的和保护性的属性和操作； 同一类的不同实例有不同的属性值。,四边形类及其对象,继承 派生类（子类）：四边形，三角形， 基类（父类）：多边形,通信 消息传递 C+中消息传递的方式： 定义：Point p; void move(int x, inty); 使用：p.move(x, y); C中则不同，需使用函数调用方式： 定义：Point p; void move(Point q, int x, inty); 使用：move(p, x, y);,Draw( ) move(x, y) contains(aPoint),Polygon,referencePoint Vertices,Polygon 类,referencePoint Vertices,Draw( ) move(x, y) contains(aPoint),Polygon的子类 Quadrilateral类,Quadrilateral,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本,事例学习：选择排序问题 明确问题：递增排序 解决方案：逐个选择最小数据 算法框架： for (int i = 0; i n-1; i+) /n-1趟 从ai检查到an-1; 若最小整数在ak, 交换ai与ak; 细化程序：程序 SelectSort,算法设计 自顶向下，逐步求精,void selectSort ( int a , const int n ) /对n个整数a0,a1,an-1按递增顺序排序 for (int i = 0; i n-1; i+) int k = i; /从ai查到an-1, 找最小整数, 在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; ,模板 (template),定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法。,用模板定义用于排序的数据表类 #ifndef DATALIST_H #define DATALIST_H #include /K是表项关键码类型 template / /E是表项类型 class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);,public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream #endif,类中所有操作作为模板函数的实现 template void dataList : swap (int m1, int m2) /交换由m1, m2为下标的数组元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;,template int dataList:minKey (int low, int high) /查找数组Elementlow到Elementhigh中具 /有最小关键码值的表项，函数返回其位置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min; ;,定义的重载操作,template ostream ,template istream ,template void dataList : sort ( ) /按非递减顺序对listSize个关键码element0到 /elementArraySize-1排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i); #endif,使用模板的选择排序算法的主函数 #include #include “dataList.h” const int SZ = 10; int main ( ) struct sick /患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ;,dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; ,定义对象时，代入实际数据类型,重载友元操作,标准IO操作,消息通信,算法简单性能分析与度量,算法的性能标准 算法的后期测试 算法的事前估计,算法的性能标准,正确性 (Correctness ) 算法应满足具体问题的需求。 可读性(Readability) 算法应该容易阅读。以有利于阅读者对程序的理解。 效率 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。 健壮性 (Robustness) 算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。,算法的后期测试,对一个算法要作出全面的分析可分成两个阶段进行，即事前分析和事后测试 事前分析要求事前求出该算法的一个时间界限函数。 事后测试则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。 事后分析要求在算法中的某些部位插装时间函数 time ( )，测定算法完成某一功能所花费时间。,例如，给出顺序搜索 (Sequenial Search)算法 int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索与给定值 x 相等的元 /素，函数返回其位置，失败返回-1。 int i = 0; while ( i n ,插装 time( ) 的计时程序 double start, stop; time( 事实上，算法运行时间要受输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。,算法的事前估计,算法的事前估计主要包括时间复杂性和空间复杂性的分析： 问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。 时间复杂性：算法所需时间和问题规模的函数，记为 T(n)。当 n 时的时间复杂性，称为渐进时间复杂性。 空间复杂性：算法所需空间和问题规模的函数。记为 S(n)。当 n 时的时间复杂性，称为渐进空间复杂性。,空间复杂度度量,存储空间的固定部分 程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,时间复杂度度量,编译时间 运行时间 程序步 语法上或语义上有意义的一段指令序列； 执行时间与问题规模无关； 例如：声明语句：程序步数为0; 表达式：程序步数为1,程序步确定方法 插入计数全局变量count 建表，列出个语句的程序步,例 以迭代方式求累加和的函数 float sum (float a , int n) float s = 0.0; for (int i = 0; i n; i+) s = s + ai; return s; ,在求累加和程序中加入 count 语句 float sum (float a , int n) float s = 0.0; count+; /count 统计执行语句条数 for (int i = 0; i n; i+) count += 2; /针对 for 语句 s += ai; count+; /针对赋值语句 count += 2; /针对 for 的最后一次 count+; /针对 return 语句 return s; 执行结束得 程序步数 count = 3*n+4,程序的简化形式 void sum (float a , int n) for (int i = 0; i n; i+) count += 3; count += 4; ,注意： 一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。 例如： 赋值语句x = sum (R, n) 本身程序步数为 1； 一次执行对函数 sum (R, n) 的调用需要的程序步数为 3*n+4； 一次执行的程序步数为 1+3*n+4 = 3*n+5,计算累加和程序 程序步数计算工作表格,时间复杂度的渐进表示法,例 求两个n阶方阵的乘积C = AB,void MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2n+2) Cij = 0; n2 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 ,3n3 + 5n2 + 4n +2,时间复杂度的渐进表示法,算法中所有语句的频度之和是矩阵阶数n的函数 T(n) = 3n3 + 5n2 + 4n +2 一般地，称 n 是问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数。 当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度 T(n) = O(n3) 大O表示法,加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) 各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n n!,T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2),乘法规则 针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 渐进的空间复杂度 S (n) = O(f (n) 两个并列循环的例子,void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行 sumi = 0.0; /数据累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行数据和 cout i “ : ” sum i endl; 渐进时间复杂度为 O(max (m*n, m),起泡排序 void bubbleSort (int a , int n ) /对表 a 逐趟比较, n 是表当前长度 for (int i = 1; i = i; j-) /n-i次比较 if (aj-1 aj) int tmp = aj-1; aj-1 = aj; aj = tmp; /一趟比较 ,渐进时间复杂度 O(f (n)*g (n) = O(n2),有时, 算法的时间复杂度不仅依赖于问题规模 n，还与输入实例的初始排列有关。 在数组 An 中查找给定值 k 的算法： int i = n-1; while (i = 0 算法的语句 i- 的频度不仅与 n 有关，还与 A 中各元素的取值以及 k 的取值有关。,例：设有两个算法在同一机器上运行，其执行时间分别为 100n2 和 2n，问：要使前者快于后者，n 至少要取多大？ 解答： 问题是找出满足 100n2 2n = 8192 n = 14时，100n2 = 19600 2n = 16384 n = 15时，100n2 = 22500 2n = 32764 取 n = 15 满足要求。,出错处理问题举例,试编写一个函数计算 n!*2n 的值，结果存放于数组 An 的第 i 个数组元素中 (0 i n) 若设计算机中允许的整数的最大值为 maxInt，则当 i arraySize 或者对于某一个 k ( 0 k n )，使得k!*2k maxInt 时，应按出错处理。,可有如下几种不同的出错处理方式：,用 cerr 及 exit (1) 语句来终止执行并报告错误； 用返回整数函数值 0, 1 来实现算法，以区别是正常返回还是错误返回； 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某中错误返回。 抛出异常。,#include #define n 100 #define maxInt 0x7fffffff bool calc (int T , int n) int i, value = 1; if ( n != 0 ) for (i = 1; i maxInt / n / 2) return false; /直接判断 i!*2i MaxInt 是危险的 value *= n * 2; ,Tn = value; /n!*2n Tn return true; void main ( ) int An, i; for (i = 0; i n; i+) if (!calc (A, i) cout “failed at “ i endl; break; ,第二章 线性表,数据结构电子教案,殷人昆 王 宏,第二章 线性表,线性表 顺序表 单链表 多项式 循环链表 双向链表,线性表 (Linear List),线性表的定义 线性表是 n (0) 个数据元素的有限序列，记作 （a1, a2, , an） ai 是表中数据元素，n 是表长度。 原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制。 为简单起见，假定各元素类型相同。,线性表的特点 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）。,线性表的抽象基类,template class LinearList public: LinearList(); /构造函数 LinearList(); /析构函数 virtual int Size() const = 0; /求表最大体积 virtual int Length() const = 0; /求表长度 virtual int Search(T x) const = 0; /搜索 virtual int Locate(int i) const = 0; /定位 virtual E* getData(int i) const = 0; /取值 virtual void setData(int i, E x) = 0; /赋值,virtual bool Insert(int i, E x) = 0; /插入 virtual bool Remove(int i, E 线性表的存储表示有两种：顺序存储方式和链表存储方式。,顺序表 (Sequential List),顺序表的定义 将线性表中的元素相继存放在一个连续的存储空间中。 可利用一维数组描述存储结构 顺序表的特点 所有元素的逻辑先后顺序与其物理存放顺序一致,顺序表的静态存储和动态存储,#define maxSize 100 typedef int T; typedef struct T datamaxSize; /顺序表的静态存储表示 int n; SeqList; typedef int T; typedef struct T *data; /顺序表的动态存储表示 int maxSize, n; SeqList;,结点的变体（异质数据）,若想在线性表中存放不同类型的数据，可采用等价定义union： typedef union int val; /按data.val引用 char ch; /按data.ch引用 float dir; /按data.dir引用 union data *link; /按data.link引用 data; /整体上是同一类型data,顺序表(SeqList)类的定义,#include /定义在“seqList.h”中 #include #include “LinearList.h“ const int defaultSize = 100; template class SeqList: public LinearList protected: E *data; /存放数组 int maxSize; /最大可容纳表项的项数 int n; /当前已存表项数 void reSize(int newSize); /改变数组空间大小,public: SeqList(int sz = defaultSize); /构造函数 SeqList(SeqList,顺序表的构造函数,#include /操作“exit”存放在此 #include “seqList.h” /操作实现放在“seqList.cpp” template SeqList:SeqList(int sz) if (sz 0) maxSize = sz; n = 0; data = new EmaxSize; /创建表存储数组 if (data = NULL) /动态分配失败 cerr “存储分配错误！“ endl; exit(1); ;,template SeqList:SeqList ( SeqList,复制构造函数,顺序表的搜索算法,template int SeqList:search(T,顺序搜索图示,搜索成功的平均比较次数 pi 是搜索第 i 项的概率 ci 是找到时的比较次数 若搜索概率相等，则 搜索不成功 数据比较 n 次,搜索性能分析,表项的插入,表项的插入算法,template bool SeqList:Insert (int i, E x) /将新元素x插入到表中第i (1in+1) 个表项位 /置。函数返回插入成功的信息 if (n = maxSize) return false; /表满 if (i n+1) return false; /参数i不合理 for (int j = n; j = i; j-) /依次后移 dataj = dataj-1; datai-1 = x; /插入(第 i 表项在datai-1处) n+; return true; /插入成功 ;,插入算法的性能分析,在表中第 i 个位置插入，从datai-1 到data n-1 成块后移，移动n-1-(i-1)+1 = n-i+1项。 考虑所有插入位置，相等插入概率时，从 1 到 n+1，平均移动元素个数为:,表项的删除,表项的删除算法,template bool SeqList:Remove (int i, E,删除算法的性能分析,删除第 i 个表项，需将第 i+1 项到第 n 项全部前移，需前移的项数为 n-(i+1)+1 = n-i 考虑表中所有可能删除位置（1in-1）,相等删除概率时，平均移动元素个数为：,顺序表的应用：集合的“并”运算,void Union ( SeqList /插入到第n个表项位置 ,void Intersection ( SeqList /未找到在A中删除它 ,顺序表的应用：集合的“交”运算,特点 每个元素(表项)由结点(Node)构成。 线性结构 结点之间可以连续，可以不连续存储 结点的逻辑顺序与物理顺序可以不一致 表可扩充,单链表 (Singly Linked List),单链表的存储映像,free,(a) 可利用存储空间,a0,a2,a1,a3,free,first,(b) 经过一段运行后的单链表结构,单链表的结构定义,在C中定义单链表的结构十分简单： typedef int T; /结点数据的类型 typedef struct node /结点结构定义 T data; /结点数据域 struct node *link; /结点链接指针域 LinkNode; /结点命名 这是一个递归的定义。 在结构定义时不考虑操作，以后在定义和实现链表操作时直接使用结构的成分。,单链表的类定义,使用面向对象方法，要把数据与操作一起定义和封装，用多个类表达一个单链表。 链表结点(ListNode)类 链表(List)类 定义方式 复合方式 嵌套方式 继承方式 结构方式,class List; /复合方式 class ListNode /链表结点类 friend class List; /链表类为其友元类 private: int data; /结点数据, 整型 ListNode * link; /结点指针 ; class List /链表类 private: ListNode *first ; /表头指针 ;,class List /嵌套方式 private: class ListNode /嵌套链表结点类 public: int data; ListNode *link; ; ListNode *first; /表头指针 public: /链表操作 ;,/链表类和链表结点类定义(继承方式) class ListNode /链表结点类 protected: int data; ListNode * link; ; class List : public class ListNode /链表类, 继承链表结点类的数据和操作 private: ListNode *first; /表头指针 ;,在复合方式中，链表结点类中声明链表类是它的友元类，这样可以“奉献”它的私有成员给链表类。这种方式灵活。 在嵌套方式中，链表结点类是链表类的私有成员，这样限制了链表结点类的应用范围。 在继承方式中，链表类声明为链表结点类的派生类，这在实现上是可行的。但在逻辑上是有问题的，如 三角形 is 多边形（继承关系） 链表 is 链表结点（显然概念不准确）,/链表类和链表结点类定义(结构方式) struct ListNode /链表结点类 int data; ListNode * link; ; class List /链表类, 直接使用链表结点类的数据和操作 private: ListNode *first; /表头指针 ; /链表中的结点属于链表私有，别人无法访问,单链表中的插入与删除操作,插入 第一种情况：在链表最前端插入 newnode-link = first ; first = newnode;,（插入前） （插入后）,(插入前) (插入后),第二种情况：在链表中间插入 newnode-link = current-link; current-link = newnode；,第三种情况：在链表末尾插入 newnode-link = current-link; current-link = newnode；,(插入前) (插入后),单链表的插入算法,bool List:Insert(int i, int x) /将新元素 x 插入到第 i 个结点之后。i 从1开始， /i = 0 表示插入到首元结点之前。 if (first = NULL | i = 0) /空表或首元结点前 LinkNode *newNode = new LinkNode(x); /建立一个新结点 newNode-link = first; first = newNode; /新结点成为首元结点 else /否则，寻找插入位置 LinkNode *current = first; int k = 1;,while (k link; k+; if (current = NULL ,删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素,在单链表中删除含ai的结点,ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,删除前,删除后,单链表的删除算法,bool List:Remove (int i, int ,del = current-link; /删中间/尾结点 current-link = del-link; x = del-data; delete del; /取出被删结点数据 return true; ; 实现单链表的插入和删除算法，不需要移动元素，只需修改结点指针，比顺序表方便。 情况复杂，要专门讨论空表和在表头插入的特殊情形。 寻找插入或删除位置只能沿着链顺序检测。,带表头结点的单链表,表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。,非空表 空表,在带表头结点的单链表最前端插入新结点,newnode-link = p-link; p-link = newnode;,q = p-link; p-link = q-link; delete q;,从带表头结点的单链表中删除最前端的结点,(非空表）,(空表）,单链表的模板类,类模板将类的数据成员和成员函数设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中，增加了表头结点。,用模板定义的单链表类,template /定义在“LinkedList.h” struct LinkNode /链表结点类的定义 E data; /数据域 LinkNode *link; /链指针域 LinkNode() link = NULL; /构造函数 LinkNode(E item, LinkNode *ptr = NULL) data = item; link = ptr; /构造函数 bool operator= (T x) return data.key = x; /重载函数，判相等 bool operator != (T x) return data.key != x; ;,template class List : public LinearList /单链表类定义, 不用继承也可实现 protected: LinkNode *first; /表头指针 public: List() first = new LinkNode; /构造函数 List(E x) first = new LinkNode(x); List( List /计算链表的长度,LinkNode *Search(T x); /搜索含x元素 LinkNode *Locate(int i); /定位第i个元素 E *getData(int i); /取出第i元素值 void setData(int i, E x); /更新第i元素值 bool Insert (int i, E x); /在第i元素后插入 bool Remove(int i, E,template void List:makeEmpty() LinkNode *q; while (first-link != NULL) q = first-link; /保存被删结点 first-link = q-link; /从链上摘下该结点 delete q; /删除 ；,链表置空算法（保留表头结点）,template int List : Length ( ) const ListNode *p = first-link; /检测指针 p 指示第一号结点 int count = 0; while ( p != NULL ) /逐个结点检测 p = p-link; count+; return count; ,求单链表的长度的算法,first,p,a0,a1,a2,c = 0,first,p,a0,a1,a2,c = 1,first,p,a0,a1,a2,c = 2,first,p,a0,a1,a2,c = 3,单链表的搜索算法,template LinkNode *List:Search(T x) /在表中搜索含数据x的结点, 搜索成功时函数返 /该结点地址; 否则返回NULL。 LinkNode *current = first-link; while ( current != NULL ,单链表的定位算法,template LinkNode *List:Locate ( int i ) /函数返回表中第 i 个元素的地址。若i *current = first; int k = 0; while ( current != NULL ,单链表的插入算法,template bool List:Insert (int i, E x