数据结构期末复习总结

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单击此处添加文本致京元792女女2526乔 d-_d吕数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的

3、集合和定义在此集合上的若干四种逻辑结构：集合、线性结构、树型结构、图状结构。 数据结构的形式定义是一个二元组：Data-Structure=(D , S)其中：D是数据元素的有限集，S是D上关系的有限集。例1:设数据逻辑结构B= (K, R)K=k1, k2,k9R= <k1, k3>, <k1, k8>, <k2, k3>, <k2, k4>, <k2, k5>, <k3, k9>, <ks,血>,<k8, 3, <k9, k7>, <k4, k7>, <k4, k6>

4、;数据结构（Data Structure）:是指相互之间具有（存在）一 定联系（关系）的数据元素的集合口V 数据结构包括三个方面厂1,数据的逻辑结构2.数据的存储结构集合线性结构 树结构图 顺序存储 链式存储 素引存储 散列存储查找、插入、删壊、修改、排序例2：有_种数据D=1, 5, 8, 12, 20, 26, 34R-rr=«1, 8>, <8S 34人 <34 , 20>, <20, 12>,<12, 26>f <26t 5>有时候关系图不唯一（一般是无向图）数据结构在计算机内存中的存储包括数据元素的存储和元素之间的

5、关系的表示。 两种不同的存储结构：顺序存储结构和链式存储结构。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元素之间的逻辑结构（关系）。顺序存储一使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储 次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。iTKlci敌捱元素存储地址【处仗）l.ocKab>+cLoe城申j It 5；编艸MZoq(口J 二 Loc(a -Fr xc? 链式存储一使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在 物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系

6、来体现。通 常使用指针记载直接前驱元素或直接后继元素的存储地址。数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。? 初始化。? 判断是否空状态。? 统计元素的个数。? 遍历：按某种次序访问所有元素，每个元素只被访问一次。? 取值：获取指定元素值。? 置值：设置指定元素值。? 插入：增加指定元素。? 删除：移去指定元素。? 查找：在数据结构中寻找满足给定条件的数据元素。? 排序：将数据元素? .数据操作定义在数据的逻辑结构上； 数据操作的实现依赖于数据的存储结构。?数据结构三方面的关系：数据的逻辑结构、数据的存储结构及操作这三方面是一个整体例6 :线性表是一

7、种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存 储，则可称其为链表；若采用散列存储，则可称为散列表。? 在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同,也可能导致完全不同的数据结构。? 类型（type）是具有相同逻辑意义的一组值的集合。? 数据类型是指一个类型和定义在这个类型上的操作集合。 数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作例7： Java中整型类型int的值集是3131-2 , 一2,-1,0,1,2,-1这个值集上的操作集合+,-,*,/,%,=,=,!=,<,<=,>,>=逻辑结构物理结构 j 主线性

8、表顺序存储结构树二链式存储结构图 复合存储结构逻辑结构与所采用的存储结构数据逻辑結构层次关系圏抽象数据类型(Abstract Data Type，简称ADT):是指一个数学模型以及定 义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。 因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：ADT=(D, S, P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的一般定义形式是：ADT 抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT 抽象数

9、据类型名例& 复数抽象数据类型描述如下：ADT Complexdouble real,imag;Complex(double real, double imag);Complex add(Complex c);Complex sub(Complex c);1、算法定义：一个算法(algorithm )是一个有穷规则的集合，其规则确定一个解决某一特 定类型问题的操作序列(D.K nuth )。算法的规则必须满足以下5个特性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

10、可行性： 一个算法是能行的。 即算法描述的操作都可以通过已经实现的基本运算执行有 限次来实现。 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。2、算法设计目标- 正确性-健壮性-高时间效率-高空间效率-可读性3、算法描述自然语言描述 伪码描述 传统流程图描述 程序设计语言描述(本课程选Java)4、算法与数据结构? 算法建立在数据结构之上，对数据的操作需用算法来描述。? 算法设计依赖数据的逻辑结构，算法实现依赖数据的存储结构。? 实现一种抽象数据类型，需要选择合适的存储结构。 求解同一问题可能有许多

11、不同的算法，如何去评价这些算法的优劣？主要考虑如下三点：A. 执行算法所耗费的时间；B. 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；C. 算法应易于理解，易于编码，易于调试等等。1、时间代价分析算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势， 通常采用时间复杂度来 度量算法的时间效率 ,用大 O 表示法来记 :T(n)=O(f(n)例 1 void fun()+x;s=0 ;将x自增看成是基本操作，则语句频度为1,即时间复杂度为O(1)。如果将s=0也看成是基本操作，则语句频度为2,其时间复杂度仍为O(1),即常量阶。一个简单语句的时间复杂度为O(1)。例 2 for(i

12、=1; i<=n; +i)+x;s+=x ;语句频度为：2n,其时间复杂度为：O (n)，即为线性阶。 一个循环的时间复杂度为O(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-i n m-1 + +an+ao 是一个 m 次多项式，则 A(n)=0(n m) 例 4 两个 n 阶方阵的乘法for(i=1 ， i<=n; +i) for(j=1; j<=n; +j) cij=0 ; f

13、or(k=1; k<=n; +k) cij+=aik*bkj ; 由于是一个三重循环，每个循环从1到n,则总次数为： nxnxn=n3时间复杂度为3T(n)=0 (n)例 5for(i=2;i<=n;+i)for(j=2;j<=i-1;+j)+x;ai,j=x; 语句频度为：1+2+3+n-2=(1+ n-2) x (n-2)/22=(n-1)(n-2)/2 =n2-3n+22时间复杂度为 0(n),即此算法的时间复杂度为平方阶。 例 6： int n=8, count=0;for (int i=1; i<=n; i*=2) for (int j=1; j<=n;

14、 j+) count+;循环次数为。时间复杂度为 0(nlog2n)。例 7： int n=8, count=0;for (int i=1; i<=n; i*=2) for (int j=1; j<=i; j+) count+;总的循环次数为。时间复杂度为 0(n)。以下六种计算算法时间的多项式是最常用的。其关系为：230(1)<0(log n)<0(n)<0(n log n)<0(n )<0(n )指数时间的关系为：0(2n)<0(n!)<0(nn)当n取得很大时，指数时间算法运算时间远远超过多项式时间算法。2、空间代价分析算法的空间效率

15、(空间复杂度)指算法在执行时为解决问题所需要的额外存储空 间，不包括输入数据和程序指令所占用的存储空间，用大0表示法来记：S(n)=o(f(n)该存储空间一般包括三个方面:指令常数变量所占用的存储空间；输入数据所占用的存储空间； 辅助(存储)空间。?一般地，算法的空间复杂度指的是辅助空间。?变量i :空间复杂度 0(1)?一维数组an:空间复杂度O(n)?二维数组anm:空间复杂度O(n*m)第2章线性表线性结构是最常用、 最简单的一种数据结构。 而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：i. 存在一个唯一的被称为“第一个”的数据元素；ii.

16、存在一个唯一的被称为“最后一个”的数据元素；iii. 除第一个元素外，每个元素均有唯一一个直接前驱；iv. 除最后一个元素外，每个元素均有唯一一个直接后继。线性表(Linear List):是由n(n±O)个数据元素(结点)a0, al,an-1组成的有限序列。该序 列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。b) 当n=0时，称为空表。c) 当n>0时，将非空的线性表记作：(ao,印，an-i)线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。 用顺序存储实现的线性表称之为顺序表。线性表的逻辑顺序与物理顺序一致。? 顺序表是一种

17、随机存取结构。通常采用数组存储数据元素。? 设线性表的每个元素需占用c个存储单元。index数菇冗索Z dc (or) = Zo c (a0) + f x c存储腔址亦血)I OCI rtf >+cLocfurHi l>XcLot(心片f"L«Xm)-HUXcL曲角)+n-1 )Xcpublic boolean isEmpty() / 时间复杂度 0(1) return this.len = 0;public int length() / 时间复杂度 O(1)return this.len;public T get(int i)/ 时间复杂度 O(1)if(i&

18、gt;=0 && i < this.len)return (T)this.elementi;return null;public void set (int i, T x)/ 时间复杂度 O(1)if (x=null)return;if (i>=0 && ivthis.len) this.elementi = x;else throw newlndexOutOfBoundsException(i+ ;"”)public String toString() 时间复杂度 O(n) Stringstr =“ (”；if(this.len>0

19、)str += this.elementO.toString();for(int i = 1; i v this.len; i +)str += , ” + thieJementi.toString();return str +“)”；? 两个线性表相等是指，它们长度相同并且各对应元素相等。? 链式存储：用一组任意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的 任意位置上的。? 链表中结点的逻辑顺序和物理顺序不一定相同。?链表中的结点结构：数据域和地址域n个结点构成的链表表示为（ao, ai,，an-i）? 链表中每

20、个结点只含一个地址域，又称为线性链表或单链表。? 每个结点有两个地址域的线性链表称为双链表。? 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 q=p; q=p.next:P-丄 操作前p一|詁一 b|卜.操作前q i提作后 P = p next;.T 6| 卜E-操件前1-”-kh操作后 q.next=p;q raTHbFH. pxIHy> - 操作前q-HalHSP.- pfcTF-.操柞前qp.bHix|-|-|y|-| ,q 接件前pBQ- . HxTHyTF.操作后'5. q.next=p.next;(a)q 操作前p操作后头结点的作用是，使所有链表（包括

21、空表）的头指针非空，则对单链表的插入、删除操作不 需要区分操作位置。头结点中不存储数据。head指针头插入和头删除操作不会改变 总结-顺序表和链表的比较（1）直接访问元素的性能顺序表能够直接访问数据元素，即只要给出顺序表底层数组element的下标就可以访问数组中的任何一个数据元素。（随机存取）而链表中不能随机地直接访问大多数元素，只能从链表的第一个结点开始，沿着链 的方向，依次查找后续结点，直至到达所需访问的结点。（顺序存取）（2 ）存储空间的利用由于需要估计顺序表底层数组 element的大小（顺序表的容量），因此顺序表存在存 储空间的浪费问题。顺序表在进行插入操作时，要判断顺序表是否为满

22、。如果满，则需要扩充容量。 而链表每插入一个结点，就向系统申请一个存储单元，只要系统资源足够，系统就 会为该结点分配存储空间。（3 ）存储密度存储密度（Storage Density是指结点数据本身所占的存储量和整个结点结构所占的 存储量之比，即：（结点数据本身所占的存储量） （整个结点所占的存储总量）顺序表的全部空间都用来存放数据元素，因此存储密度=1；而链表中每个结点都要包含其后继结点或者前驱结点的链，因此存储密度< 1。（4 ）插入和删除操作顺序表的插入、删除操作很不方便，插入和删除操作有时需要移动大量元素； 而链表的插入、删除操作很容易进行，只要简单地改动相关结点的链即可，不需要

23、 移动数据元素。public Singly Li 含 t(Sing lyList<Tlist；深拷贝this();"创建只有头结点的空链表Node<T> ip = list.head.next;Node<T> rear = th is.head; II打算使用屋插入法while(p!=nullXrear.next = new Node<T>(p.data, null)；rear= reamext; /向队尾结点p = p,next:* | | A|#-1"” »| 1 | A|（b）瞬拷Pb無制单琏衣l时屮的所有结点I寻致

24、两亍魅点引划同一个元素科星头结点<a）空循环单鮭表头指针构造空表:如图（呂）创建头结点"构成坏形判空第4章栈和队列I 11循环单链表public class CirSinglvLinkedList<T>public Node<T> head;Public Cir§ingyLinkedList() this.head = new Node<T>f)； 览區贞空n空垃=th 目Q；public booleanisEmotvO (return ihis.head.next = this.head:-wtmwwvwwwvwwwvwwvwwm

25、wwr-wvwvwwhrwwwww*public String toSWngf) 遍历，循环条件改变了 for(Node<T> o=this.head.next: p!=this.head: o=p.nxt)System,out.printlnfp.data,taStrinqO + a 77 ); ? 栈的定义：-栈（Stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进 行。通常称允许插入、删除操作的这一端为栈顶 （Top），不允许操作的一端称 为栈底（Bottom）。当表中没有元素时称为空栈。-假设栈S=（so, ai, a2, a3,缶一“，贝y ao称为栈底

26、元素，an-i为栈顶元素，标 识栈顶位置的指针称为栈顶指针。栈中元素按ao, ai, a2, a3,an-i的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先 出的原则进行的。因此，栈称为后进先出表（LIFO）。? 栈的操作：-习惯上将每次删除（也称为退栈）操作又称为出栈或弹出（POP）操作。删除的元素总是当前栈中“最新”的元素（栈顶元素）。-每次插入（称为进栈）操作称为入栈或压入（PUSH）操作，入栈的元素总是当前栈中“最新”的元素。-在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。? 栈的数据元素：-栈的数据元素和线性表的数据元素完全相同，即

27、栈的数据元素是n （n>=0）个相同类型的数据元素 a。，a1,°°°an-1组成的有限序列，记为：a。®,时。-其中，n为数据元素的个数，称为栈的长度。n=0时，为空栈。? 栈的溢出：-当栈满时进栈运算称为“上溢”。-当栈空时退栈运算称为“下溢”。-栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常 下溢用来作为程序控制转移的条件。? 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。因此,?栈的顺序存储结构简称为顺序栈(Sequential Stack),它是运算受限的线性表。可用数组来实现顺序栈。? 因为栈底位置是固定

28、不变的,所以可以将栈底位置设置在数组的两端的任何一个端 点；栈顶位置是随着进栈和退栈操作而变化的,一般需用一个整型变量top栈的顺序存储结构及操作实现public class SeqStack<T> implements Stack<T>/ 顺序栈类,实现栈接口Object element; / 存储栈数据元素的数组int top;/ 栈顶元素下标注意： element 数组存储栈的数据元素； top 表示当前栈顶元素的下标。 经典实现：(1)栈的初始化public SeqStack(int size) / 构造容量为 size 的空栈this.element = ne

29、w ObjectMath.abs(size);this.top= -1;public SeqStack()/ 构造默认容量的空栈this(64);( 2)判读栈是否为空public boolean isEmpty() / 判断栈是否空,若空返回 truereturn this.top=-1;? 判读栈是否为满？ 本实现采用与顺序表同样的处理：当容量不够时,则将数组容量扩充一倍。( 3 )入栈public void push(T x) / 元素 x 入栈,空对象不能入栈if (x=null) return;/ 空对象不能入栈if (this.top=element.length-1) / 若栈满

30、,则扩充栈容量Object temp = this.element;/ 重新申请一个容量更大的数组this.element = new Objecttemp.length*2;for (int i=0; i<temp.length; i+)/ 复制数组元素, O(n)this.elementi = tempi;this.top+;this.elementthis.top = x;（4）出栈栈不空时，取走 top 位置处栈顶元素， top 减 1，下一位置数据元素作为新的栈顶元素public T pop（） / 出栈，返回栈顶元素，若栈空返回 nullreturn this.top= -1

31、 ? null : （T） this.elementthis.top -;（5）获得栈顶数据元素栈不空时，获取 top 位置处栈顶元素，此时数据元素未出栈，top 值不变public T get（） / 取栈顶元素，未出栈，若栈空返回nullreturn this.top=-1 ? null : （T）this.elementthis.top;/ 顺序栈类，最终类，实现栈接口， T 表示元素类型 public final class SeqStack<T> implements Stack<T>private SeqList<T> list; / 顺序表 p

32、ublic SeqStack(int capacity) / 构造栈public SeqStack() public boolean isEmpty() public void push(T x) public T peek()public T pop()? 栈的链式存储，称为链栈。/ 构造空栈/ 判空/x 入栈/ 返回栈顶（未出栈）/ 出栈，返回栈顶元素? 链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）? 可用单链表实现链栈。? 它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（head）,因为其中惟一的已知条件

33、是栈顶指针top，它是指向链式栈的第一个结点（相当于头指针） 。? 栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各 种运算只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）? 而线性表除此之外 （不限定一端插入删除） ，还需要考虑另外一端结点以及中间的结 点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算当作线性表的 一端进行插入删除的特例即可。链式栈实现（经典实现）栈的链式存储结构及操作实现public class LinkedStack<T> implements Stack<T&

34、gt; private Node<T> top;(1)栈的初始化public LinkedStack() / 构造空栈 this.top=null;2) 判读栈是否为空public boolean isEmpty()/ 判断栈是否空，若空返回 truereturn this.top=null;3) 入栈public void push(T x)/ 元素 x 入栈，空对象不能入栈if (x!=null)this.top = new Node(x, this.top); / 头插入， x 结点作为新的栈顶结点4) 出栈public T pop() / 出栈，返回栈顶元素，若栈空返回nu

35、llif (this.top=null)return null;/ 取栈顶结点元素/ 删除栈顶结点T temp = this.top.data; this.top = this.top.next; return temp;5) 获得栈顶元素public T get()/ 取栈顶元素，未出栈，若栈空返回 nullreturn this.top=null ? null : this.top.data;链式栈实现(基于单链表)/ 链式栈类，最终类，实现栈接口， T 表示数据元素的数据类型 public final class LinkedStack<T> implements Stack

36、<T>private SinglyList<T> list;/使用单链表(第 2 章)存储栈元素public LinkedStack() / 构造空栈 this.list = new SinglyList<T>();/ 构造空单链表public boolean isEmpty() / 判断栈是否空，若空返回 true return this.list.isEmpty();public void push(T x) / 元素 x 入栈，空对象不能入栈this.list.insert(0, x); / 单链表头插入元素 xpublic T peek() / 返回

37、栈顶元素(未出栈) ；若栈空返回 nullreturn this.list.get(0);public T pop() / 出栈，返回栈顶元素；若栈空返回 nullreturn this.list.remove(0);/ 若栈不空，单链表头删除，返回删除元素public String toString()/ 返回栈所有元素的描述字符串，形式为“(,) ”return this.getClass().getName()+" "+this.list.toString();顺序栈和链式栈的比较? 实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为O( 1)。主要两者从空间

38、和时间两个方面考虑：-初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的 浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间， 但是在每个结点中，设置了一个指针域，从而产生了结构开销。-当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈， 使每个栈从各自的端点向中间延伸， 这样浪费的 空间就会减少。 但这种情况只有当两个栈的空间需求有相反的需求时， 这种 方法才有效。也就是说，最好一个栈增长，一个栈缩短。反之，如果两个栈 同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可 能需要大量的数据移动， 造成时间的开销

39、增大。 而链式栈由于存储的不连续 性，一般不存在栈满的问题，所以一般不需要栈的共享。? 【例 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*? 队列的定义：-队列(Q

40、ueue)也是一种运算受限的特殊线性表。其插入和删除操作分别在线 性表的两端进行(只允许在表的一端进行插入，而在另一端进行删除)。允许删除的一端称为队头(front)，允许插入的一端称为队尾 (rear)。-当队列中没有元素时称为空队列。在空队列中依次加入元素印向2,an之后， a1是队头元素，an是队尾元素。显然退出队列的次序也只能是內月2,an ,也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。-先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In FirstOut)的线性表，简称 FIFO表。队列的操作：-一般情况下，入队(e nqueue)操作又称为队列

41、的插入。-出队(dequeue)操作又称为队列的删除。队列的数据元素：-队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是 n(n >=0)个相同类型的数据元素a。，a1,°°°an-1组成的有限序列，记为：a。®,an-讣。-其中，n为数据元素的个数，称为队列的长度。n=0时，为空队列 。-队列的溢出：-队列在顺序存储时，经常出现“假溢出”现象，解决“假溢出”现象的方法有很多种，但通常采用循环队列方式存储。-使用顺序表，出队效率低。因此不使用顺序表作为队列的成员变量。使用数组，存在假溢出:10203：i0124front01234204

42、050ffrontrear入队：新元義按氏打指示位置加入,再将队尾指针加一。即 rear 二 jcat 十 1出队：将fkmt指示的元素取出,再将队头指针加一鼻即 Front front 1数组已经到了最右端，此时T我们无法再往数组中加入数据了， 但前面显热有空间我们没有使用。番们称这种情况为假上溢。顺序循环队列：? 现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中 的队列称为循环队列(Circular Que ne )。? 将顺序队列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。? 循环队列的操作：? 假设数组的空间是 m ，只要在入、出队列时，将队

43、首和队尾的指针对m 做求模运算即可实现队首和队为指针的循环， 即队首和队尾指针的取值范围是 0 到 m-1 之间。队空： front = rear队满： front = （rear + 1） % maxSize 或另外设一个标志以区别队空、队满 入队 : rear = （rear + 1） % maxSize 出队 : front = （front + 1） % maxSize;求队长 : （rear - front + maxSize）%maxSize 链式队列的基本概念：-定义链队列的存储结构基本和线性表的定义相同，它是对链表实现的简单化。-队列的各种运算比链式存储的普通线性表运算实现时要

44、方便得多，主要原因是队列的各种运算只能在队列的两端操作。? 队列是特殊的线性表，我们只要考虑对线性表的两端操作的情况， 并且只能一端插入（队首） ，另一端删除（队尾） 。? 而线性表除此之外（不限定一端插入、一端删除） ，还需要考虑中间 的结点的插入、删除、查询等操作。? 理解时，我们可以把队列的入、出队运算当作线性表两端进行插入 删除的特例即可。? 于是，一个链队列由头指针和尾指针唯一确定。? 使用单链表，入队效率低。? 单链表设计，增加尾指针。? 以不带头结点的单链表实现链式队列。? 队列的应用-（一）合并两个队列? 假设有两个队列，要求将两个队列合并到一起，合并时交替使用两 个队列中的元

45、素，并把剩余的队列中的元素添加在最后，将产生的 新队列返回。-（二）模拟客户服务系统-（三）主机与外部设备之间速度不匹配的问题? 以主机和打印机为例来说明，主机输出数据给打印机打印，主机输 出数据的速度比打印机打印的速度要快得多，若直接把输出的数据 送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方 法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如 到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印 机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完 后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据， 这样利用队列既保证了打印数据的正确，又使主机提高了

46、效率。第 5 章 数组和广义表? 数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数 据的数据结构。? 数组是顺序存储的随机存取结构，数组是其他数据结构实现顺序存储的基础。? 使用数组时需要定义数组的大小和存储数据的数据类型。? 数组分为一维数组和多维数组。数组的维数是由数组下标的个数确定的：?一个下标称为一维数组?一个下标以上的数组称为多维数组?从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列? 数组是二元组 下标，值 的一个集合。? 一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定

47、义给 定下标读取元素和修改元素的操作。? 声明的格式一般是：数据类型 变量名称 =new 数据类型 数组大小;女口： int element = new int5;一维数组的存储一维数组的数据存储按照顺序存储，逻辑地址和物理地址都是连续 的。如果已知第一个数据元素的地址loc(ao),则第i个元素的地址loc(ai)为：Loc(ai)= Loc(ao)+ i x c? 数组分配内存空间的方式有2种：-静态数组：声明时给出数组元素个数。当程序开始运行时，数组即获得系统 分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。in t 3 = 1,2,3;-动态数组：声明时不指定数组

48、长度。当程序运行中需要使用数组时，向系统 申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系 统归还所占用的内存空间。? 数组容量不够时，不能就地扩容。前面的做法是，申请一个更大容量的数组并进行 数组元素复制。? 在Java中，数组元素既可以简单数据类型，也可以是引用类型。而且Java中的数组都是动态数组。? 多维数组(Multi-Array )?多维数组是指下标的个数有两个以上，我们比较常用的是二维数组(因为三维以上的数组存储可以简化为二维数组的存储)。?多维数组是线性表的扩展。?理解：二维数组是“元素为一维数组”的一维数组。?二维数组的声明同一维数组。格式为：数据类型 数组

49、名称=new数据类型size1 size2;如: int element = new int45;例如，设A是一个有m行n列的二维数组，则 A可以表示为：在此，可以将二维数组 A看成是由m个行向量X。，治，Xm-组成，其中，X=( ai0, ai1,.,ain-i), 0w i 1n;也可以将二维数组 A看成是由n个列向量yo, yi, ,yn-i 组成，其中 yi=(aoi, aii,.,am-ii), 0w i Wnjn - 1a 0jao,n - 1a ija 1,n - 1aija i,n - 1a m - 1,ja m - 1,n - 1列前驱a i,j - 1a i jaij +1

50、行前驱a i- ij列后继行后继a i + ij二维数组的遍历行优先顺序(行主序)：存储时先按行从小到大的顺序存储，在每一 行中按列号从小到大存储。列优先顺序(列主序)：存储时先按列从小到大的顺序存储，在每一 列中按行号从小到大存储。二维数组的顺序存储结构假设二维数组是 m*n的二维数组(共有m行，每行有n列)。第一个数据元 素的地址是loc(aoo)，行主序LocG)二 Loc(a00) (i n j) c列主序Loc(aij) = Loc(a00)(j m i) c0(1),随机存取结构例：数组A869按行存放，设第一个元素的首地址是54,每个元素的长度为 5,求元素A245的存储地址。L

51、oc(2,4,5)=54 + 5 *( 6*2*9+4*9+5)= 799但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下我们 可以对这类矩阵进行压缩存储，即为多个相同的非零元素只分配一个存储空间；对 零元素不分配空间。三角矩阵的压缩存储：以主对角线划分，三角矩阵有下三角和上三角两种。如图所示。在大多数情况下，三角矩阵常数为零。?1.下三角矩阵? 重复元素c可共享一个存储空间，其余的元素正好有n(n +1)/2个，因此，三角矩阵可压缩存储到数组 elementO.n(n +1)/2中，其中c存放在数组的最后一个元素中。?( 1 )线性压缩存储三角矩阵?2.上三角矩阵?和下三

52、角矩阵的存储类似，共需n(n +1)/2+1个存贮单元，假设仍按行优先顺序存放，这时sk与aij的对应关系为：-a000a01a11玄,2a0, n 4a1, nJ炀=00 an/,n 匸an-2,n -4-00 0an ,n -4- 一Loc(aij) = Loc(a00) n (n -1) . (n - i 1) j -i r<(< n i 1)二 Loc(a00)j 0 S：n2对称矩阵如果用一维数组存储一个对称矩阵，只要将对称矩阵存储在一个最大下标为n(n+1)/2的一维数组 S中即可。aij与数组S的下标k的对应关系为此时按照行优先顺序存储，数据元素i(i+l)/2+j

53、当 i>jk=j(j十 1)/2十i当 i<ja0,0ao,i-%n_21a,。ai,1-a，n_2ai,n±Loc(a,j)ix(i+1)Loc(a。,。)+；丿 + jj x( j +1) Loc(a°,°) + j (； %a_2,0aiai_2,1-ai J,1- a_2,n _2ai J,n _2an_2,n4丄0 _ j _ i ： nQ_i j n?稀疏矩阵(Sparse Matrix)-对稀疏矩阵很难下一个确切的定义，它只是一个凭人们的直觉来理解的概念。一般认为，一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个数 所占比例较大时，该矩阵就是一个稀疏矩阵。? 稀疏矩阵稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则：每一个非零元素占有一行，每行中包含非零元素所在的行号、列号、非零元素的数值。书(120页)? 稀疏矩阵-如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如果矩阵中有整行(或整列)中没有非零元素，此时可能不能够还原成原来的 矩阵-所以为了完整地描述稀疏矩阵，在以上描述的情况下，如果增加一行的内容，该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个数，就可 以还原为原来的矩阵描述了。/三元组顺序表类public cl