数据结构期末复习总结.pdf

《数据结构期末复习总结.pdf》由会员分享，可在线阅读，更多相关《数据结构期末复习总结.pdf（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 绪论1.数据(D ata)：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据(字符串、图形、图像、音频、视频)。2.数据元素(D ata E lement)：表示一个事物的一组数据称为一个数据元素(结点顶点、记录)；数据元素是数据的基本单位。3.数据项(D ata Item)：是数据元素中有独立含义的、不可分割的最小标识单位(字段、域、属性)。一个数据元素可由若干个数据项组成。4.数据对象(D ata Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C=A,B,C,。数据(D ata)：是描述客观事

2、物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据(字符串、图形、图像、音频、视频)。数据元素(D ata E lement):表示一个事物的一组数据称为一个数据元素(结点、顶点、记录)；数据元素是数据的基本单位。数 据 项(D ata Item)：是数据元素中有独立含义的、不可分割的最小标识单位(字段、域、属性)。一个数据元素可由若干个数据项组成。数据对象(D ata Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合 C=A,B,C,。单击此处添加文本f数据数 据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合

3、和定义在此集合上的若干关系来表示。四种逻辑结构：集合、线性结构、树型结构、图状结构。数据结构的形式定义是一个二元组：D ata-Structure=(D,S)其中：D 是数据元素的有限集，S 是 D 上关系的有限集。例1：设数据逻辑结构B=(K,R)K=kiz k2z/k9R=,数据结构（D ata S tructure）:是指相互之间具有（存在）一定联系（关系）的数据元素的集合。数据结构包括三个方面/1.数据的逻辑结构2.数据的存储结构 3.数据的操作 集合 线性结构 树结构H3）图 顺 序存储 链式存储 索引存储 散列存储查找、插入、删除、修改、排序例2：有一种数据结构B 1 =(D,R)

4、,其中：D=1,5,8,1 2,20,26,3 4)R=rr=,)有时候关系图不唯一（一般是无向图）数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。两种不同的存储结构：顺序存储结构和链式存储结构。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元素之间的逻辑结构（关系）。顺序存储一使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。i n d e x数据元素0IMn-存储地址lQ C(q)L oclaol+cL ocS ohH.I )XcL o c

5、Q A i X cL oc(oo)+(，+1)XcL oc(a()+(w-l)Xcoc(q)=Loc(aQ)+zxc链式存储一使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系来体现。通常使用指针记载直接前驱元素或直接后继元素的存储地址。数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。初始化。判断是否空状态。统计元素的个数。遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入：增加指定元素。删除：移去指定元素。查找：在数据结构中寻找满足

6、给定条件的数据元素。排序：将数据元素数据操作定义在数据的逻辑结构上；数据操作的实现依赖于数据的存储结构。数据结构三方面的关系：数据的逻辑结构、数据的存储结构及操作这三方面是一个整体例6：线性表是一种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存储，则可称其为链表；若采用散列存储，则可称为散列表。在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同,也可能导致完全不同的数据结构。类 型(t y p e)是具有相同逻辑意义的一组值的集合。数据类型是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作例7：J a v a中

7、整型类型i n t的值集是-23 1，,-2,-1,0,1,2，,2 3 1-1 这个值集上的操作集合逻 辑 结 构线性表V物 理 结 构学 顺序存储结构树 -口 链式存储结构图-复合存储结构逻辑结构与所采用的存储结构数据逻辑结构层次关系图 抽 象数据类型(A bstract D ata Type，简称A D T)：是指一个数学模型以及定义在该模型上的一组操作。A D T的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论A D T的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。A D T的形式化定义是三元组：A D T=(D,S,P)其中：D 是数据对象，S 是

8、 D 上的关系集，P 是对D 的基本操作集。A D T的一般定义形式是：A D T 抽象数据类型名 数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义A D T 抽象数据类型名例 8：复数抽象数据类型描述如下：A D T C omplexdouble realjmag;C omplex(double real,double imag);C omplex add(C omplex c);C omplex sub(C omplex c);)2、算法定义：一个算法(algorithm)是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列(D.Knuth)。算法的规

9、则必须满足以下5 个特性：有 穷 性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确 定 性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。可 行 性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。输 入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输 出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。2、算法设计目标-正 确性-健壮性-高时间效率-高空间效率-可读性3、算法描述 自然语言描述 伪码描述传 统流程图描述 程序设计语言描述(本课程选Java)4、算法与数据结构

10、 算法建立在数据结构之上，对数据的操作需用算法来描述。算法设计依赖数据的逻辑结构，算法实现依赖数据的存储结构。实现一种抽象数据类型，需要选择合适的存储结构。求解同一问题可能有许多不同的算法，如何去评价这些算法的优劣？主要考虑如下三点：A.执行算法所耗费的时间；B.执行算法所耗费的存储空间，其中主要考虑辅助存储空间；C.算法应易于理解，易于编码，易于调试等等。1、时间代价分析算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率，用大。表示法来记：T(n)=O(7(n)例 1 void fun()+x;s=0;)将x自增看成是基本操作，则语句频度为1,

11、即时间复杂度为0(1)。如果将s=0也看成是基本操作，则语句频度为2,其时间复杂度仍为0(1),即常量阶。一个简单语句的时间复杂度为0(1)。例 2 for(i=l;i=n;+i)+x;s+=x;语句频度为：2 n,其时间复杂度为：0(n),即为线性阶。一个循环的时间复杂度为。()。例 3 for(i=l;i=n;+i)for(j=l;j=n;+j)+x;s+=x;)语句频度为：2n2 ,其时间复杂度为：0(M),即为平方阶。定理：A(n)=a mn m+a m-i n m+.+ain+a()是一个 m 次多项式,则 A(n)=O(nm)例4两个n阶方阵的乘法for(i=l,i=n;+i)fo

12、r(j=l;j=n;+j)cij=O；for(k=l;k=n;+k)ciU+=aik*bkQ;)由于是一个三重循环，每个循环从1到n,则总次数为：nXnXn=n3时间复杂度为T(n)=O(n3)例 5 for(i=2;i=n;+i)for(j=2;j=i-l;+j)+x;ai,j=x;)语句频度为：1+2+3+n-2=(l+n-2)X(n-2)/2=(n-l)(n-2)/2=M-3n+2时间复杂度为0(M),即此算法的时间复杂度为平方阶。例 6：int n=8,count=0;for(int i=l;i=n;i*=2)for(int j=l;j=n;j+)count+;循环次数为。时间复杂度为

13、O(nlog2n)。例 7：int n=8,count=0;for(int i=l;i=n;i*=2)for(int j=l;j=i;j+)count+;总的循环次数为。时间复杂度为0(n)。以下六种计算算法时间的多项式是最常用的。其关系为：0(l)0(log n)O(n)O(n log n)O(n2)O(n3)指数时间的关系为：0(2n)0(n!)0时，将非空的线性表记作：(a0,ai，an.i)线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。用顺序存储实现的线性表称之为顺序表。线性表的逻辑顺序与物理顺序一致。顺序表是一种随机存取结构。通常采用数组存储数据元素。设线性表

14、的每个元素需占用c个存储单元。oc(q)=ocQ )+zxcin dex数据元素存储地址0的IQCQ)1aL ocS o)+c*L oc(4o)+(i7)Xc/a.L oc(4o)+iXc/+1L ocQ)+(f+l)XcIL oc(a()+0 L l)Xcpublic boolean isEmpty()时间复杂度 0(1)return this.len=0;)public int length()时间复杂度 0(1)return this.len;)public T get(int i)时间复杂度 0(1)if(i=0&i=0&kthis.len)this.elementi=x;else t

15、hrow newlndexOutOfBoundsException(i+/#,)；)public String toString()时间复杂度 0(n)String str=if(this.len0)str+=this.element0.toString();for(int i=1;i this.len;i+)str+=,+this.elementi.toString();return str+)两个线性表相等是指，它们长度相同并且各对应元素相等。链 式 存 储：用一组任意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中

16、的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。链表中的结点结构：数据域和地址域n个结点构成的链表表示为(a,a i,an-i)链表中每个结点只含一个地址域，又称为线性链表或单链表。每个结点有两个地址域的线性链表称为双链表。单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。q=P；q=p.next;p=p.next;q.next=p;(a)(b)操作后P.q P.M ali-.操作前操作后P ran-rbn.p q.操作前操作后Pp1.操作前操作后qq.H aH n E Jp-Fcn-.P4CI3-.操作前操作后dal-hrbT.q 操作前pHal.，.q.n ext=p.

17、n ext;q qaT-HrbH-.TaFhrbH-.P-PxT H y R-.操作前 操作后q p.-I al H bl-h.|x|-H vl l.(b)q 操作前p.rar r&TF-nh7nyn-操作后头结点的作用是，使所有链表(包括空表)的头指针非空，则对单链表的插入、删除操作不需要区分操作位置。头结点中不存储数据。头插入和头删除操作不会改变head指针总结-顺序表和链表的比较(1)直接访问元素的性能 顺序表能够直接访问数据元素，即只要给出顺序表底层数组element的下标就可以访问数组中的任何一个数据元素。（随机存取）而链表中不能随机地直接访问大多数元素，只能从链表的第一个结点开始，

18、沿着链的方向，依次查找后续结点，直至到达所需访问的结点。（顺序存取）（2）存储空间的利用 由于需要估计顺序表底层数组element的大小（顺序表的容量），因此顺序表存在存储空间的浪费问题。顺序表在进行插入操作时，要判断顺序表是否为满。如果满，则需要扩充容量。而链表每插入一个结点，就向系统申请一个存储单元，只要系统资源足够，系统就会为该结点分配存储空间。（3）存储密度 存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即：（结点数据本身所占的存储量）（整个结点所占的存储总量）顺序表的全部空间都用来存放数据元素，因此存储密度=1；而链表中每个结点

19、都要包含其后继结点或者前驱结点的链，因此存储密度|ist)/深拷贝(this();创建只有头结点的空链表Node p=list.head.next;Node rear=this.head;打算使用尾插入法while(p!=nullXrear.next=new Node(p.data,null);rear=rear.next;rear指向队尾结点p=p.next;)b）深拷贝，复制单链&mt中的所有结点，没有复制元素对象，导致两个结点引用同一个元素对象1 1循环单链表public class CirSinqlvLinkedListhead头结点(a)空循环单链表public Node head;

20、头指针public CirSinalvLinkedList()构造空表.如图(a)this.head=new Node();创建头结点this.head.next=this.head;构成环形)public boolean isEmptvO(判空return this.head.next=this.head;)public String toStrinqO /遍历，循环条件改变了for(Node p=this.head.next;p!=this.head;p=p.next)System.out.Drintin(p.data.toStrinq()+“);)第4章 栈 和 队 列栈的定义：-栈(S

21、tack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。通常称允许插入、删除操作的这一端为栈顶(T o p),不允许操作的一端称为栈底(Bottom)。当表中没有元素时称为空栈。-假设栈S=(a,a i，a2,a3,.a z),则a0称为栈底元素，a i为栈顶元素，标识栈顶位置的指针称为栈顶指针。栈中元素按a。，a，a2)a3,.a a的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表(LIF。)。栈的操作：-习惯上将每次删除(也称为退栈)操作又称为出栈或弹出(P O P)操作。删除的元素总是当前栈中“最新”的元素(栈顶

22、元素)。-每次插入(称为进栈)操作称为入栈或压入(P U S H)操作，入栈的元素总是当前栈中“最新”的元素。-在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。栈的数据元素：栈的数据元素和线性表的数据元素完全相同，即栈的数据元素是n(n=0)个相同类型的数据元素a。,a i，。a组成的有限序列，记为:a。,am。-其中，n为数据元素的个数，称为栈的长度。n=0时，为空栈。栈的溢出：-当栈满时进栈运算称为“上溢”。-当栈空时退栈运算称为“下溢”。-栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转移的条件。由于栈是运算受限的线性表

23、，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈(Sequential Stack),它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，一般需用一个整型变量top。栈的顺序存储结构及操作实现public class SeqStack implements Stack 顺序栈类，实现栈接 口(Object element;存储栈数据元素的数组int top;栈顶元素下标)注意：element数组存储栈的数据元素；top表示当前栈顶元素的下标。经典实现：(1)栈的初始化p

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

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

26、-1?null:(T)this.elementthis.top-;（5）获得栈顶数据元素栈不空时，获取top位置处栈顶元素，此时数据元素未出栈，top值不变publicTget（）取栈顶元素,未出栈，若栈空返回nullreturn this.top=-l?null:(T)this.element(this.top;顺序栈类，最终类，实现栈接口，T 表示元素类型public final class SeqStack implements Stackprivate SeqList list;顺序表public SeqStack(int capacity)构造栈public SeqStackf)构造

27、空栈public boolean isEmpty()public void push(T x)public T peek()public T pop()判空/x入栈返回栈顶（未出栈）出栈，返回栈顶元素 栈的链式存储，称为链栈。链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。可用单链表实现链栈。它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（head）,因为其中惟一的已知条件是栈顶指针to p,它是指向链式栈的第一个结点（相当于头指针）。栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各种运算

28、只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算当作线性表的一端进行插入删除的特例即可。链式栈实现（经典实现）栈的链式存储结构及操作实现public class LinkedStack implements Stackprivate Node top;（1）栈的初始化public LinkedStack()构造空栈this.top=null;(2)判读栈是否为空public boolean isEmpty

29、()判断栈是否空，若空返回true(return this.top=null;(3)入栈public void push(T x)元素x 入栈，空对象不能入栈(if(x!=null)this.top=new Node(x,this.top);头插入，x 结点作为新的栈顶结点(4)出栈publicT pop()出栈，返回栈顶元素，若栈空返回null(if(this.top=null)return null;T temp=this.top.data;取栈顶结点元素this.top=this.top.next;删除栈顶结点return temp;)(5)获得栈顶元素public T get()取栈顶

30、元素，未出栈，若栈空返回null(return this.top=null?null:this.top.data;)链式栈实现(基于单链表)链式栈类，最终类，实现栈接口，T 表示数据元素的数据类型public final class LinkedStack implements Stack(private SinglyList list;使用单链表(第2 章)存储栈元素public LinkedStack()构造空栈(this.list=new SinglyList();构造空单链表public boolean isEmpty()判断栈是否空，若空返回truereturn this.list.

31、isEmpty();public void push(T x)元素x 入栈，空对象不能入栈(this.list.insert(O,x);单链表头插入元素xpublic T peek()返回栈顶元素(未出栈)；若栈空返回null(return this.iist.get(O);)public T pop()出栈，返回栈顶元素；若栈空返回null(return this.list.remove(O);若栈不空，单链表头删除，返回删除元素public String toStringf)返回栈所有元素的描述字符串，形式为(return this.getC lass().getName()+this.l

32、ist.toString();)顺序栈和链式栈的比较实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为。(l)o 主要两者从空间和时间两个方面考虑：-初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间,但是在每个结点中，设置了一个指针域，从而产生了结构开销。当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种方法才有效。也就是说，最好一个栈增长，一个栈缩短 反之，

33、如果两个栈同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可能需要大量的数据移动，造成时间的开销增大。而链式栈由于存储的不连续性，一般不存在栈满的问题，所以一般不需要栈的共享。【例3 使用栈计算算术表达式值算术表达式有三种表示方法：操作数操作符 操作数，如 A+B,称为中缀(infix)表示；操作符 操作数 操作数，如+A B称为前缀(prefix)表示；操作数操作数 操作符，如 A B+,称为后缀(postfix)表示。中缀表达式：1+2*(3-4)+5其对应的后缀表达式为1234-*+5+习题中缀表达式如下，写出后缀表达式。A+B*(C-D*(E+F)/G+H)-(I+J)

34、*K【习题解答】A BC D EF+*G/-H+*+IJ+K*队列的定义：-队列(Queue)也是一种运算受限的特殊线性表。其插入和删除操作分别在线性表的两端进行(只允许在表的一端进行插入，而在另一端进行删除)。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。-当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,a。之后，a i是队头元素，a”是队尾元素。显然退出队列的次序也只能是ai,az,a”，也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。-先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In FirstOut)的线性

35、表，简称FIFO表。队列的操作：-一般情况下，入队(enqueue)操作又称为队列的插入。-出队(dequeue)操作又称为队列的删除。队列的数据元素：-队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是n(n=0)个相同类型的数据元素a0,a a”i 组成的有限序列，记为：匕。闭,a Q。-其中，n 为数据元素的个数，称为队列的长度。n=0时，为空队列。-队列的溢出：-队列在顺序存储时，经常出现“假溢出”现象，解 决“假溢出”现象的方法有很多种，但通常采用循环队列方式存储。-使用顺序表，出队效率低。因此不使用顺序表作为队列的成员变量。以 魏 且 存 储 题 素入队：新元素按rear

36、指示位置加入，再将队尾指针加一。即 rear=rear+1出队：将front指示的元素取出，再将队头指针加一。即 front=front+1数组已经到了最右端，此 时，我们无法再往数组中加入数据了，但前面显然有空间我们没有使用。我们称这种情况为假上溢。顺序循环队列：现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中的队列称为循环队列(C ircular Quene)。将顺序队列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。循环队列的操作：假设数组的空间是m,只要在入、出队列时，将队首和队尾的指针对m 做求模运算即可实现队首和队为指针的循环，即队首和队尾指

37、针的取值范围是0 到 m-1之间。队空：front=rear 队满：front=（rear+1）%maxSize或另外设一个标志以区别队空、队满 入队：rear=（rear+1）%maxSize 出队：front=（front+1）%maxSize;求队长：（rear-front+maxSize）%maxSize链式队列的基本概念：-定义链队列的存储结构基本和线性表的定义相同，它是对链表实现的简单化。-队列的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是队列的各种运算只能在队列的两端操作。队列是特殊的线性表，我们只要考虑对线性表的两端操作的情况，并且只能一端插入（队首），另一端

38、删除（队尾）。而线性表除此之外（不限定一端插入、一端删除），还需要考虑中间的结点的插入、删除、查询等操作。理解时，我们可以把队列的入、出队运算当作线性表两端进行插入删除的特例即可。于是，一个链队列由头指针和尾指针唯一确定。使用单链表，入队效率低。单链表设计，增加尾指针。以 不带头结点的单链表实现链式队列。队列的应用-（一）合并两个队列假设有两个队列，要求将两个队列合并到一起，合并时交替使用两个队列中的元素，并把剩余的队列中的元素添加在最后，将产生的新队列返回。-（二）模拟客户服务系统-（三）主机与外部设备之间速度不匹配的问题以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度

39、比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。第 5 章 数 组 和 广 义 表 数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构。数组是顺序存储的随机存取结构，数组是其他数据结构实现顺序存储的基础。使用数组时需要定义

40、数组的大小和存储数据的数据类型。数组分为一维数组和多维数组。数组的维数是由数组下标的个数确定的：一个下标称为一维数组 一个下标以上的数组称为多维数组 从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列数组是二元组 下标，值 的一个集合。一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作。声明的格式一般是：数据类型 变量名称口=new 数据类型 数组大小习；如：int elementd=new int5;一维数组的存储 一维数组的数据存储按照顺序存储，逻辑地址和物理地址都是连续的

41、。如果己知第一个数据元素的地址loc(ao),则第i个元素的地址1 同)为：Loc(a,)=Loc(ao)+/Xc 数组分配内存空间的方式有2种：-静态数组：声明时给出数组元素个数。当程序开始运行时;数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。int 3=1,2,3;动态数组：声明时不指定数组长度。当程序运行中需要使用数组时，向系统申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存空间。数组容量不够时，不能就地扩容。前面的做法是，申请一个更大容量的数组并进行数组元素复制。在Java中，数组元素既可以简单数据类型，也可以是

42、引用类型。而且Java中的数组都是动态数组。多维数组(Multi-Array)多维数组是指下标的个数有两个以上，我们比较常用的是二维数组(因为三维以上的数组存储可以简化为二维数组的存储)。多维数组是线性表的扩展。理解：二维数组是“元素为一维数组”的一维数组。二维数组的声明同一维数组。格式为：数据类型 数组名称 口 口=new数据类型sizel size2;如：int element口 口 =new int45;例如，设A是一个有m行n列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由m个行向量X。，X i,，Xm-iF组成，其中，Xi=(ai0,aii,-.,ain.i),0 i m

43、-l；也可以将二维数组A看成是由n个列向量仇,yi,.,yn.i组成，其中 yi=(aOi,a n,，am-6,0 i n-l列 前 驱列 后 继 二维数组的遍历行优先顺序(行主序)：存储时先按行从小到大的顺序存储，在每一行中按列号从小到大存储。列优先顺序(列主序)：存储时先按列从小到大的顺序存储，在每一列中按行号从小到大存储。二维数组的顺序存储结构 假设二维数组是m*n的二维数组(共有m行，每行有n列)。第一个数据元素的地址是loc(aoo),行主序=L 0 c(a0 0)+(i x +j)xc 列主序L o c(%.)=Loc(a00)+(/x，”+i)x c 0(1).随机存取结构例：数

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

45、元素中。(1)线性压缩存储三角矩阵 2.上三角矩阵 和下三角矩阵的存储类似，共 需n(n+l)/2+l个存贮单元，假设仍按行优先顺序存放，这时sk与 的 对 应 关 系 为：。00001a,n-2aQ,n-a,n-A=.00 an-2,n-2an-2,n-000L oc (%)=L oc(f l0 0)+n+(-1)+.+(-z +1)+j-i.,zx(2 x-z-l).c/./=L oc(a0 0)+-+j Qijjk=jO+l)/2+i 当 ij“0.0“0.1a,oA.=an-2.0”-2,1_an-,0“0 斤2 a0,n-aLn-2 a,n-“-2.-2LOC(%QT/、Z X(Z

46、+1).L oc 3oo)+-一 +jL oc(a0 0)H -H0 j in0 z j n,稀疏矩阵(Sparse Matrix)-对稀疏矩阵很难下一个确切的定义，它只是一个凭人们的直觉来理解的概念。一般认为，一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个数所占比例较大时，该矩阵就是一个稀疏矩阵。稀疏矩阵稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则：每一个非零元素占有一行，每行中包含非零元素所在的行号、列号、非零元素的数值。书(120页)稀疏矩阵-如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如果矩阵中有整行(或整列)中没有非零元素，此时可能不能够还原成原来的

47、矩阵-所以为了完整地描述稀疏矩阵，在以上描述的情况下，如果增加一行的内容，该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个数，就可以还原为原来的矩阵描述了。三元组顺序表类public class SeqMatrix(int rows,columns;行数、列数SortedSeqList list;排序顺序表)public int get(int i,int j)/返回第 i 行第 j 列的元素if(i=rows 11 j=columns)throw new lndexOutOfBoundsException(outofBound);Triple item=new Triple(i,j

48、,O);int k=0;Triple elem=this.list.get(k);while(k=0)if(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 1 1 column=this.columns)throw new IHegalA rgumentException(/zoutofBound/,)；Triple elem=new Triple(row,column,value);int

49、 i=0;whilefi 0)i+;else break;this.list.insert(i,elem);/不存在该元素，将新元素插入矩 阵 二维数组矩阵特殊矩阵（零元素分布规律、不存储分布规律的零元素）三角矩阵 对称矩阵对角矩阵线 性 压 缩-维数组存储非零元素区域三角形的二维数组稀疏矩阵（零元素分布不规律、不存储零元素）三元组顺序表（排序）三元组单链表（排序）三元组行的单链表（排序）I三元组十字链表（排序）广义表的定义：广义表是线性表的扩展，具体定义为n（n 2 0）个元素的有限集合 其中元素有以下两种类型：1）一个原子元素（指不可再分的元素）；2）一个可以再分的元素（或称为一个子表）。

50、如果所有元素都是原子元素，则称为线性表，如果含有子表则是广义表。n的值是广义表的长度，如 果n=0,称为空表。广义表定义G List=（a0,ai,，a*i）中国（北京，上海，江苏（南京，苏州），浙江（杭州），广东（广州）L=（a,b）线性表，长度为2,深度 为1T=(c,L)=(c,(a,b)1.为丁的子表，T的长度为2,深度为2G=(d,L,T)=(d,(a,b),(c,(a,b)L、T为G的子表，G的长度为3,深度为3S=()空表，长度为0,深度为1Sl=()元素是一个空表，长度为1,深度为2Z=(e,Z)=(e,(e,(e,(.)递归表，Z的长度为2,深度无穷广义表的特性(1)线性结构