《数据结构期末复习总结 .pdf》由会员分享，可在线阅读，更多相关《数据结构期末复习总结 .pdf（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章绪论1.数据(Data)：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。2.数据元素(Data Element)：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。3.数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。4.数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合 C=A,B,C,。数据(Data)：是描述客观事物的数字、字
2、符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。数据元素(Data Element)：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）；数据元素是数据的基本单位。数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合 C=A,B,C,。数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示。四种逻辑结构：
3、集合、线性结构、树型结构、图状结构。数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是 D上关系的有限集。例 1：设数据逻辑结构 B=（K，R）K=k1,k2,k9 R=，名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 39 页 -有时候关系图不唯一（一般是无向图）数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。两种不同的存储结构：顺序存储结构和链式存储结构。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元素之间的逻辑结构(关系)。顺序存储使用一组连
4、续的内存单元依次存放数据元素，元素在内存中的物理存储次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。?链式存储使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系来体现。通名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 39 页 -常使用指针记载直接前驱元素或直接后继元素的存储地址。数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。?初始化。?判断是否空状态。?统计元素的个数。?遍历：按某种次序访问所有元素，每个元素只被访问一次。?取值：获取指定元素值。?置值：
5、设置指定元素值。?插入：增加指定元素。?删除：移去指定元素。?查找：在数据结构中寻找满足给定条件的数据元素。?排序：将数据元素?.数据操作定义在数据的逻辑结构上；数据操作的实现依赖于数据的存储结构。?数据结构三方面的关系：数据的逻辑结构、数据的存储结构及操作这三方面是一个整体例 6：线性表是一种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存储，则可称其为链表；若采用散列存储，则可称为散列表。?在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同，也可能导致完全不同的数据结构。?类型（type）是具有相同逻辑意义的一组值的集合。?数据类型是指一个类型和定义在这个类型上
6、的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作例 7：Java 中整型类型int的值集是 -231,-2,-1,0,1,2,231-1 这个值集上的操作集合+,-,*,/,%,=,=,!=,=名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 39 页 -抽象数据类型(Abstract Data Type，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。ADT 的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论 ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：ADT=(D，S，P
7、)其中：D是数据对象，S是 D上的关系集，P是对 D的基本操作集。ADT的一般定义形式是：ADT 数据对象：数据关系：基本操作：ADT 例 8：复数抽象数据类型描述如下：ADT plex double real,imag;plex(double real,double imag);plex add(plex c);plex sub(plex c);1、算法定义：一个算法（algorithm）是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列（D.Knuth）。算法的规则必须满足以下5 个特性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法
8、中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 39 页 -输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。2、算法设计目标正确性健壮性高时间效率高空间效率可读性3、算法描述自然语言描述伪码描述传统流程图描述程序设计语言描述（本课程选Java）4、算法与数据结构?算法建立在数据结构之上，对数据的操作需用算法来描述。?算法设计依赖数据的
9、逻辑结构，算法实现依赖数据的存储结构。?实现一种抽象数据类型，需要选择合适的存储结构。求解同一问题可能有许多不同的算法，如何去评价这些算法的优劣？主要考虑如下三点：A.执行算法所耗费的时间；B.执行算法所耗费的存储空间，其中主要考虑辅助存储空间；C.算法应易于理解，易于编码，易于调试等等。1、时间代价分析算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率,用大 O表示法来记:T(n)=O(f(n)例 1 void fun()+x;s=0;将 x 自增看成是基本操作，则语句频度为，即时间复杂度为(1)。如果将 s=0 也看成是基本操作，则语句频度为
10、，其时间复杂度仍为(1)，即常量阶。一个简单语句的时间复杂度为(1)。例 2 for(i=1;i=n;+i)+x;s+=x;语句频度为：2n，其时间复杂度为：(n)，即为线性阶。一个循环的时间复杂度为(n)。例 3 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：2n2，其时间复杂度为：O(n2)，即为平方阶。定理：若 A(n)=a m n m +a m-1 n m-1+a1n+a0是一个 m次多项式，则A(n)=O(n m)例 4 两个 n 阶方阵的乘法 for(i=1，i=n;+i)for(j=1;j=n;+j)cij=0;名师资料总结-精品资料欢迎
11、下载-名师精心整理-第 5 页，共 39 页 -for(k=1;k=n;+k)cij+=aik*bkj;由于是一个三重循环，每个循环从1 到 n，则总次数为：n nn=n3时间复杂度为T(n)=(n3)例 5 for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai,j=x;语句频度为：1+2+3+n-2 =(1+n-2)(n-2)/2 =(n-1)(n-2)/2=n2-3n+2 时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。例 6：int n=8,count=0;for(int i=1;i=n;i*=2)for(int j=1;j=n;j+)count+;循环次数为
12、。时间复杂度为O(nlog2n)。例 7：int n=8,count=0;for(int i=1;i=n;i*=2)for(int j=1;j=i;j+)count+;总的循环次数为。时间复杂度为O(n)。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(n)O(n)O(n n)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)0 时，将非空的线性表记作：(a0，a1，an-1)线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。用顺序存储实现的线性表称之为顺序表。线性表的逻辑顺序与物理顺序一致。?顺序表是一种随机存取结构。通常采用数组存储数据元素。?设线
13、性表的每个元素需占用c 个存储单元。public boolean isEmpty()/时间复杂度O(1)return this.len=0;public int length()/时间复杂度O(1)return this.len;public T get(int i)/时间复杂度O(1)if(i=0&i=0&i0)str+=this.element0.toString();for(int i=1;i this.len;i+)str+=“，”+this.elementi.toString();return str+“)”;?两个线性表相等是指，它们长度相同并且各对应元素相等。?链式存储：用一组任
14、意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。?链表中结点的逻辑顺序和物理顺序不一定相同。?链表中的结点结构：数据域和地址域n 个结点构成的链表表示为 (a0,a1,.,an-1)?链表中每个结点只含一个地址域，又称为线性链表或单链表。?每个结点有两个地址域的线性链表称为双链表。?单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 39 页 -头结点的作用是，使所有链表（包括空表）的头指针非空，则对单链表的插入、删除操作不需要区分操
15、作位置。头结点中不存储数据。头插入和头删除操作不会改变head 指针总结-顺序表和链表的比较（1）直接访问元素的性能顺序表能够直接访问数据元素，即只要给出顺序表底层数组element 的下标就可以访问数组中的任何一个数据元素。（随机存取）而链表中不能随机地直接访问大多数元素，只能从链表的第一个结点开始，沿着链的方向，依次查找后续结点，直至到达所需访问的结点。（顺序存取）（2）存储空间的利用由于需要估计顺序表底层数组element的大小（顺序表的容量），因此顺序表存在存储空间的浪费问题。顺序表在进行插入操作时，要判断顺序表是否为满。如果满，则需要扩充容量。而链表每插入一个结点，就向系统申请一个存
16、储单元，只要系统资源足够，系统就会为该结点分配存储空间。（3）存储密度存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即：（结点数据本身所占的存储量）（整个结点所占的存储总量）顺序表的全部空间都用来存放数据元素，因此存储密度=1；而链表中每个结点都要包含其后继结点或者前驱结点的链，因此存储密度=0）个相同类型的数据元素a0，a1，。an-1组成的有限序列，记为：a0,a1,an-1。其中，n 为数据元素的个数，称为栈的长度。n=0 时，为空栈。?栈的溢出：当栈满时进栈运算称为“上溢”。当栈空时退栈运算称为“下溢”。栈上溢是一种出错状态，应该
17、设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转移的条件。?由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。?栈的顺序存储结构简称为顺序栈（Sequential Stack），它是运算受限的线性表。因此，可用数组来实现顺序栈。?因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，一般需用一个整型变量top。栈的顺序存储结构及操作实现public class SeqStack implements Stack /顺序栈类，实现栈接口 Object element;/存储栈数据元素的数组 int top;/栈顶元
18、素下标 注意：element 数组存储栈的数据元素；top 表示当前栈顶元素的下标。经典实现：（1）栈的初始化 public SeqStack(int size)/构造容量为size的空栈 this.element=new ObjectMath.abs(size);this.top=-1;public SeqStack()/构造默认容量的空栈 this(64);（2）判读栈是否为空 public boolean isEmpty()/判断栈是否空，若空返回true return this.top=-1;?判读栈是否为满？本实现采用与顺序表同样的处理：当容量不够时，则将数组容量扩充一倍。（3）入栈
19、 public void push(T x)/元素 x 入栈，空对象不能入栈 if(x=null)return;/空对象不能入栈 if(this.top=element.length-1)/若栈满，则扩充栈容量名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 39 页 -Object temp=this.element;/重新申请一个容量更大的数组 this.element=new Objecttemp.length*2;for(int i=0;itemp.length;i+)/复制数组元素，O(n)this.elementi=tempi;this.top+;this.eleme
20、ntthis.top=x;（4）出栈栈不空时，取走top 位置处栈顶元素，top 减 1，下一位置数据元素作为新的栈顶元素 public T pop()/出栈，返回栈顶元素，若栈空返回null return this.top=-1?null:(T)this.elementthis.top-;（5）获得栈顶数据元素栈不空时，获取top 位置处栈顶元素，此时数据元素未出栈，top 值不变 public T get()/取栈顶元素，未出栈，若栈空返回null return this.top=-1?null:(T)this.elementthis.top;/顺序栈类，最终类，实现栈接口，T 表示元素类
21、型public final class SeqStack implements Stack private SeqList list;/顺序表 public SeqStack(int capacity)/构造栈 public SeqStack()/构造空栈 public boolean isEmpty()/判空 public void push(T x)/x入栈 public T peek()/返回栈顶（未出栈）public T pop()/出栈，返回栈顶元素?栈的链式存储，称为链栈。?链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。?
22、可用单链表实现链栈。?它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（head），因为其中惟一的已知条件是栈顶指针top，它是指向链式栈的第一个结点（相当于头指针）。?栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各种运算只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）?而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算当作线性表的一端进行插入删除的特例即可。链式栈实现（经典实现）栈的链式存储结构及操作实现
23、public class LinkedStack implements Stack private Node top;名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 39 页 -（1）栈的初始化 public LinkedStack()/构造空栈 this.top=null;（2）判读栈是否为空 public boolean isEmpty()/判断栈是否空，若空返回true return this.top=null;（3）入栈 public void push(T x)/元素 x 入栈，空对象不能入栈 if(x!=null)this.top=new Node(x,this.t
24、op);/头插入，x 结点作为新的栈顶结点 （4）出栈 public T pop()/出栈，返回栈顶元素，若栈空返回null if(this.top=null)return null;T temp=this.top.data;/取栈顶结点元素 this.top=this.top.next;/删除栈顶结点 return temp;（5）获得栈顶元素 public T get()/取栈顶元素，未出栈，若栈空返回null return this.top=null?null:this.top.data;链式栈实现（基于单链表）/链式栈类，最终类，实现栈接口，T 表示数据元素的数据类型public fi
25、nal class LinkedStack implements Stack private SinglyList list;/使用单链表（第2 章）存储栈元素 public LinkedStack()/构造空栈 this.list=new SinglyList();/构造空单链表 public boolean isEmpty()/判断栈是否空，若空返回true return this.list.isEmpty();public void push(T x)/元素 x 入栈，空对象不能入栈 this.list.insert(0,x);/单链表头插入元素x 名师资料总结-精品资料欢迎下载-名师精
26、心整理-第 13 页，共 39 页 -public T peek()/返回栈顶元素（未出栈）；若栈空返回null return this.list.get(0);public T pop()/出栈，返回栈顶元素；若栈空返回null return this.list.remove(0);/若栈不空，单链表头删除，返回删除元素 public String toString()/返回栈所有元素的描述字符串，形式为“(,)”return this.getClass().getName()+this.list.toString();顺序栈和链式栈的比较?实现链式栈和顺序栈的操作，都是需要常数时间，即时间
27、复杂度为O（1）。主要两者从空间和时间两个方面考虑：初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间，但是在每个结点中，设置了一个指针域，从而产生了结构开销。当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种方法才有效。也就是说，最好一个栈增长，一个栈缩短。反之，如果两个栈同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可能需要大量的数据移动，造成时间
28、的开销增大。而链式栈由于存储的不连续性，一般不存在栈满的问题，所以一般不需要栈的共享。?【例 3】使用栈计算算术表达式值算术表达式有三种表示方法：，如 A+B，称为中缀(infix)表示；，如+AB称为前缀(prefix)表示；，如 AB+，称为后缀(postfix)表示。中缀表达式：1+2*(3-4)+5 其对应的后缀表达式为 1234-*+5+习题 中缀表达式如下，写出后缀表达式。A+B*(C-D*(E+F)/G+H)-(I+J)*K 【习题解答】ABCDEF+*G/-H+*+IJ+K*?队列的定义：队列(Queue)也是一种运算受限的特殊线性表。其插入和删除操作分别在线性表的两端进行（只
29、允许在表的一端进行插入，而在另一端进行删除）。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO 表。队列的操作：一般情况下，入队(enqueue)操作又称为队列的插入。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 39 页 -出队
30、(dequeue)操作又称为队列的删除。队列的数据元素：队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是n（n=0）个相同类型的数据元素a0，a1，。an-1组成的有限序列，记为：a0,a1,an-1。其中，n 为数据元素的个数，称为队列的长度。n=0 时，为空队列。队列的溢出：队列在顺序存储时，经常出现“假溢出”现象，解决“假溢出”现象的方法有很多种，但通常采用循环队列方式存储。使用顺序表，出队效率低。因此不使用顺序表作为队列的成员变量。顺序循环队列：?现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中的队列称为循环队列（Circular Quene）。?将顺序队
31、列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。?循环队列的操作：?假设数组的空间是m，只要在入、出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队为指针的循环，即队首和队尾指针的取值范围是 0 到 m-1 之间。队空：front=rear 队满：front=(rear+1)%maxSize或另外设一个标志以区别队空、队满入队:rear=(rear+1)%maxSize 出队:front=(front+1)%maxSize;求队长:(rear-front+maxSize)%maxSize 链式队列的基本概念：定义链队列的存储结构基本和线性表的定义相同，它是对链表
32、实现的简单化。队列的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是队列的各种运算只能在队列的两端操作。?队列是特殊的线性表，我们只要考虑对线性表的两端操作的情况，并且只能一端插入（队首），另一端删除（队尾）。?而线性表除此之外（不限定一端插入、一端删除），还需要考虑中间的结点的插入、删除、查询等操作。?理解时，我们可以把队列的入、出队运算当作线性表两端进行插入名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 39 页 -删除的特例即可。?于是，一个链队列由头指针和尾指针唯一确定。?使用单链表，入队效率低。?单链表设计，增加尾指针。?以不带头结点的单链表实现链式队列
33、。?队列的应用（一）合并两个队列?假设有两个队列，要求将两个队列合并到一起，合并时交替使用两个队列中的元素，并把剩余的队列中的元素添加在最后，将产生的新队列返回。（二）模拟客户服务系统（三）主机与外部设备之间速度不匹配的问题?以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接
34、到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。第 5 章数组和广义表?数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构。?数组是顺序存储的随机存取结构，数组是其他数据结构实现顺序存储的基础。?使用数组时需要定义数组的大小和存储数据的数据类型。?数组分为一维数组和多维数组。数组的维数是由数组下标的个数确定的：?一个下标称为一维数组?一个下标以上的数组称为多维数组?从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列?数组是二元组 的一个集合。?一维数组具有
35、线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作。?声明的格式一般是：=new ；如：int element=new int5;一维数组的存储一维数组的数据存储按照顺序存储，逻辑地址和物理地址都是连续的。如果已知第一个数据元素的地址loc(a0)，则第i个元素的地址loc(ai)为：Loc(ai)=Loc(a0)i c?数组分配内存空间的方式有2 种：静态数组：声明时给出数组元素个数。当程序开始运行时，数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。int 3=1,2,3;动态数组：声明时不指定数组长度。当程序运行中
36、需要使用数组时，向系统申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存空间。?数组容量不够时，不能就地扩容。前面的做法是，申请一个更大容量的数组并进行数组元素复制。名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 39 页 -?在 Java 中，数组元素既可以简单数据类型，也可以是引用类型。而且Java 中的数组都是动态数组。?多维数组（Multi-Array）?多维数组是指下标的个数有两个以上，我们比较常用的是二维数组（因为三维以上的数组存储可以简化为二维数组的存储）。?多维数组是线性表的扩展。?理解：二维数组是“元素为一维数组”的一维数组。
37、?二维数组的声明同一维数组。格式为：=newsize1 size2;如：int element=new int45;例如，设A是一个有 m行 n 列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由 m个行向量 X0，X1，Xm-1T组成，其中，Xi=(ai0,ai1,.,ain-1)，0 i m-1；也可以将二维数组A 看成是由n 个列向量y0,y1,yn-1 组成，其中 yi=(a0i,a1i,.,am-1i)，0 i n-1。二维数组的遍历行优先顺序（行主序）：存储时先按行从小到大的顺序存储，在每一行中按列号从小到大存储。列优先顺序（列主序）：存储时先按列从小到大的顺序存储，在每
38、一列中按行号从小到大存储。二维数组的顺序存储结构假设二维数组是m*n 的二维数组（共有m行，每行有n 列）。第一个数据元素的地址是loc(a00)，行主序列主序O(1)，随机存取结构例：数组 A869按行存放，设第一个元素的首地址是54，每个元素的长度为5，求元素 A245的存储地址。Loc(2,4,5)=54+5*（6*2*9+4*9+5）=799 但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下我们可以对这类矩阵进行压缩存储，即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。三角矩阵的压缩存储：以主对角线划分，三角矩阵有下三角和上三角两种。如图所示。在大多数
39、情况下，三角矩阵常数为零。?1.下三角矩阵?重复元素 c 可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到数组element0.n(n+1)/2中，其中 c 存放在数组的最后一个元素中。?（1）线性压缩存储三角矩阵?2.上三角矩阵?和下三角矩阵的存储类似，共需 n(n+1)/2+1个存贮单元，假设仍按行优先顺序存放，这时sk 与 aij的对应关系为：a0,ja0,n-1a1,ja1,n-1ai,jai,n-1am-1,jam-1,n-1jn-1ai,jai-1,jai+1,jai,j-1ai,j+1列前驱列后继行前驱行后继cjniaLocaLocij)()()
40、(00cimjaLocaLocij)()()(00名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 39 页 -对称矩阵如果用一维数组存储一个对称矩阵，只要将对称矩阵存储在一个最大下标为n(n+1)/2的一维数组S中即可。此时按照行优先顺序存储，数据元素aij与数组 S的下标 k 的对应关系为?稀疏矩阵（Sparse Matrix）对稀疏矩阵很难下一个确切的定义，它只是一个凭人们的直觉来理解的概念。一般认为，一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个数所占比例较大时，该矩阵就是一个稀疏矩阵。?稀疏矩阵稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则：每一个非零元素占
41、有一行，每行中包含非零元素所在的行号、列号、非零元素的数值。书（120 页）?稀疏矩阵如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如果矩阵中有整行（或整列）中没有非零元素，此时可能不能够还原成原来的矩阵所以为了完整地描述稀疏矩阵，在以上描述的情况下，如果增加一行的内容，该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个数，就可以还原为原来的矩阵描述了。/三元组顺序表类public class SeqMatrix int rows,columns;/行数、列数 SortedSeqList list;/排序顺序表 public int get(int i,int j)/
42、返回第 i 行第 j 列的元素 if(i=rows|j=columns)1,11,22,21,12,1111,02,00100000000nnnnnnnnnnnnaaaaaaaaaaAnjijiniaijinnnaaij02)12()(Loc)1(.)1()(Loc)(Loc00001,12,11,10,11,22,21,20,21,12,11,10,11,02,01,00,0.nnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaAnjiijjanijjiiaaji02)1()(Loc02)1()(Loc)(Loc0,00,0,名师资料总结-精品资料欢迎下载-名师精心整理-第
43、18 页，共 39 页 -throw new IndexOutOfBoundsException(“outofBound”);Triple item=new Triple(i,j,0);int k=0;Triple elem=this.list.get(k);while(k=0)if(item.pareTo(elem)=0)return elem.value;k+;return 0;public void set(int row,int column,int value)if(value=0)return;if(row=this.rows|column=this.columns)throw n
44、ew IllegalArgumentException(“outofBound”);Triple elem=new Triple(row,column,value);int i=0;while(i 0)i+;else break;this.list.insert(i,elem);/不存在该元素，将新元素插入 广义表的定义：广义表是线性表的扩展，具体定义为n（n0）个元素的有限集合。其中元素有以下两种类型：1）一个原子元素（指不可再分的元素）；2）一个可以再分的元素（或称为一个子表）。如果所有元素都是原子元素，则称为线性表，如果含有子表则是广义表。n 的值是广义表的长度，如果n=0，称为空表。广
45、义表定义 GList=(a0,a1,an-1)中国(北京,上海,江苏(南京,苏州),浙江(杭州),广东(广州)L(a,b)/线性表，长度为2，深度为 1 T(c,L)(c,(a,b)/L为 T的子表，T的长度为2，深度为2 矩阵三角矩阵三元组顺序表（排序）二维数组矩阵特殊矩阵（零元素分布规律、不存储分布规律的零元素）对称矩阵线性压缩存储非零元素区域稀疏矩阵（零元素分布不规律、不存储零元素）三元组行的单链表（排序）三元组十字链表（排序）三元组单链表（排序）一维数组三角形的二维数组对角矩阵名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 39 页 -G(d,L,T)(d,(a,b),
46、(c,(a,b)/L、T为 G的子表，G的长度为3，深度为 3 S()/空表，长度为0，深度为 1 S1(S)()/元素是一个空表，长度为1，深度为2 Z(e,Z)(e,(e,(e,()/递归表，Z 的长度为2，深度无穷广义表的特性（1）线性结构（3）可共享（2）多层次结构，有深度（4）可递归?广义表的三个重要结论：列表的元素可以是子表，而子表的元素还可以是子表。由此，列表是一个多层次的结构，可以用图形象地表示。广义表的存储方法有很多种，一般采用链表存储。第 6 章树和二叉树?树结构是一类重要的非线性结构。?树结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。?树定义：树
47、(Tree)是由 n(n=0)个结点组成的有限集合。n=0 的树称为空树，n0 的树由以下两个条件约定构成：1.有且仅有一个特殊的称为根(Root)的结点，它只有后继结点，没有前驱结点；2.其余的结点可分为m(nm=0)个互不相交的子集T0、T1、T2、Tm-1，其中每个子集又是一棵树，并称其为子树(Subtree)。?以上定义中：结点的双亲结点或父母结点（parent）：结点上面的相邻结点，或指结点的前驱结点结点 n 的孩子结点（child）：任何一个以n 作为双亲结点的结点，或指结点n 的后继结点树的根（root）：有且仅有的一个特定的结点，它没有双亲结点结点 n 的祖先结点（ancest
48、or）：包括 n 的双亲结点，n 的双亲结点的双亲结点，等等；即指从根结点到其父母结点所经过的所有结点?根是树中所有结点的公共祖先结点结点 n 的子孙（后代）结点（descendant）：任何一个以n 作为祖先结点的结点；即指结点的所有孩子结点，以及孩子的孩子等。兄弟结点（sibling）：如果结点m和 n共有一个双亲结点，则称m和 n为兄弟结点叶子结点（终端结点）（leaf）：没有孩子结点的结点分支结点（非终端结点）：叶子结点之外的结点称为分支结点或者非终端结点子树（subtree）：在树 T 中，n 的子孙结点组成了以n 作为根的T 的子树名师资料总结-精品资料欢迎下载-名师精心整理-第
49、20 页，共 39 页 -结点 n 的度（degree of node）：n 的孩子结点的数量树的度（degree of a tree）：树中所有结点的最大度数结点 n 的层次（level）：结点 n 所处的树中的层次位置。可以假设根的层次是 0 或 1，本书中所有都假设根的层次为1，其他结点的层次是其父母结点的层次加 1 树的高度（heigh）或深度（depth）：树中结点的最大层次数边（edge）：设树中X 结点是 Y结点的父母结点，有序对（X，Y）称为连接这两个结点的分支，也称为边。路径（path）:从一个结点n 到另一个结点的边序列。路径长度（length）：路径中涉及到边的数量。若把
50、树中每个结点的各子树看成从左到右有次序的（即不能互换），则称该树为有序树（Ordered Tree）；否则称为无序树（Unordered Tree）森林（forest）：m棵互不相交的树的集合（如：T0,T1,T2 Tm-1），但可能为空?二叉树定义：二叉树是n 个结点的有限集合：n=0 时，为空二叉树；n0 时，由一个根结点、两棵互不相交的左子树和右子树的子二叉树组成。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。?二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这