数据结构（陈仲民）数据结构2.pptVIP

数 据 结 构 计算机系 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 第一章 绪 论 计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。  第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 例3、学生健康情况登记表如下： 的单链表示意图如下： …… 110 …… 130 135 …… 160 头指针 head 165 170 …… 200 205 …… 第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值  第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 数组 4.4 数组的定义 4.5 数组的顺序表示和实现 4.6 矩阵的压缩存储 4.6.1 特殊矩阵 4.6.2 稀疏矩阵 k=I*(I+1)/2+J=2*(2+1)/2+1=4 b[q][1]=a[p][0]; b[q][2]=a[p][2]; q++; } } } } 5.5 广义表的定义 广义表（Lists，又称列表）是线性表的推广。在第2章中，我们把线性表定义为n=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是n(n=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。 通常用圆括号将广义表括起来，用逗号分隔其中的 元素。为了区别原子和广义表，书写时用大写字母 表示广义表，用小写字母表示原子。若广义表 LS（n=1)非空，则a1是LS的表头，其余元素组成 的表(a1,a2,…an)称为LS的表尾。 显然广义表是递归定义的，这是因为在定义广 义表时又用到了广义表的概念。广义表的例子如下： （1）A=（）——A是一个空表，其长度为零。 （2）B=（e）——表B只有一个原子e，B的长度为1。 （3）C=（a,(b,c,d))——表C的长度为2，两个元素分别 为原子a和子表(b,c,d)。