数据结构2013

1、第一章绪论第一章绪论 1.1什么是数据结构 随着计算机已深入到人类社会的各个领域，计算机的应用已不再局限于科学计算，而更多的应用于控制、管理以及数据处理等非数值计算的处理工作。与之相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像，甚至于声音等各种具有一定结构的数据。这也就给程序设计带来一些新的问题。为了编写一个“好”程序，必须分析待处理的对象的特征以及各处理对象之间存在的关系。这就是“数据结构”这门课形成和发展的背景。 我们从前面学过和处理过的问题中了解到，用计算机解决一个具体问题，大致需要经过下列几个步骤：首先从具体问题中抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法

2、，最后编出程序，进行调试、调整直至最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言如线性方程组或微分方程加以描述。然而，更多的非数值计算问题无法用数学方程加以描述，如书中例子1.5（p5）中的图、表、树等数据结构（或数学模型），不再是数学方程。因而，简单的来说，数据结构是一门研究非数值计算的程序设计问题、计算机操作对象以及它们之间的关系和操作等等的学科。 1.2基本概念和术语 本节对一些基本概念和术语赋予确定的含义，以便以后章节中的使用。1数据（data）：是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程

3、序处理的符号的总称。它是计算机程序加工的“源料”，如：数字中的数（实数、整数），过去用过的字符串、以及更广泛的图像、声音等都是可以通过编码而归之于数据的范畴。2数据元素（data element）：是数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。如：“表”中的一行或记录，“树”中的一个叶子都被称为一个数据元素。有时一个数据元素可由若干个数据项（data item）组成。数据项是具有独立含义的最小标识单位。3数据类型（data type）：是性质相同的数据元素的集合，是一个数据的子集。如字母字符数据对象是集合C=A,B,C,Z。4.数据结构（data structure）：是相互

4、之间存在一种或几种特定关系的数据元素的集合。如在前面例子中的图、表、树中看到，在任何问题中，数据元素都不是孤立存在的，它们之间存在着某种关系，这种数据元素之间的关系称为结构（structure）。根据数据元素之间关系的不同特征，通常有下列四类基本结构：（p4）（1）集合：结构中数据元素除了同属于一个集合的关系外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一个对一个的关系。（3）树形结构：结构中的数据元素之间存在一个对多个的关系。 （4）图状结构（或网状结构）：结构中的数据元素之间存在多个对多个的关系。 例如，书中p4的关系图。Data_structure=(D,S)。其中，D是数据

5、元素的有限集；S是D上关系的有限集。这只是对操作对象的一种数学描述，换句话说，是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。然而，讨论数据结构的目的是为了在计算机中实现对它的操作。因此，还需要研究如何在计算机中表示它。 数据结构在计算机中的表示（又称为映象）称为数据的物理结构，又称为存储结构。它包含数据元素和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位（bit）。在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素（如用8位二进制数表示一个字符等）。通常称这个位串为元素（element）或结

6、点（node）。当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为数据域（data filed）。因此，元素或结点可看成数据元素在计算机中的映象。 数据元素之间的关系在计算机中有两种不同的表示方法。顺序映象和非顺序映象。并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映象的特征是借助于元素在其中存储的相对位置来表示数据元素之间的逻辑关系。而非顺序映象的特点是借助于指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。举例略。 数据的逻辑结构和物理结构是密切相关的两个方面。任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。

7、如何描述存储结构呢？虽然存储结构涉及数据与那速及其关系在存储其中的物理位置。但本书是在高级程序语言的层次上讨论数据结构的操作。因此，不能直接以内存地址来存储结构，而是借助于高级程序语言中提供的“数据结构”或“存储类型”来描述它。如：用C中的“二维数组”类型来描述顺序存储结构；用C中的“指针”类型来描述链式存储结构。 假如把PASCAL（或C）语言看成是一个执行PASCAL指令和PASCAL数据类型的虚拟处理器，那么本书中讨论的存储结构是数据结构在PASCAL虚拟处理器中的表示，不妨称它为虚拟存储结构。 5.数据类型（data type）：是和数据结构密切相关的一个概念。 它最早出现在高级语言中

8、，用以刻画程序操作对象的特征。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型明显或隐含的规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值集上的一组操作的总称。例如，PASCAL语言中的整数类型，其值集为区间-maxint,maxint上的整数，定义在其上的一组操作为：加、减、乘、除和取模等。 按“值”的不同特征，高级语言的数据类型可分成两类：一类是非结构的原子类型，原子类型的值是不可分解的，如：整型、实型、字符型、布尔型和指针型等；另一类是结构类型，结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可

9、以是结构的。 6.抽象数据类型（abstruct data type 简称ADT）：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特征，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特征不变，都不影响其外部的使用，也就是说，它比数据类型的范畴更广，不再局限于前述各处理器中已定义的并实现的数据类型（固有数据类型），还包括用户在设计软件系统时自己定义的数据类型。 一个含有抽象数据类型的软件模块通常包含定义、表示和实现三个部分。抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。按其值的不同特征也可分为原子类型和结构类型，后

10、者又可细分为固定聚合类型（其值由确定数目的成分按某种结构组成）和可变聚合类型（数目固定）。 抽象数据类型定义的操作中，除了和该类型相应的一组操作外，一般情况下，还应有结构的创建和销毁。 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，利用已经实现的操作来进行新的操作。举例如课本p7例1-6中抽象数据类型复数的定义。 7.多型数据类型（polymonphic data type）：是指其值的成分不确定的数据类型（略）。 从以上对数据类型的讨论可见，与数据结构密切相关的是定义在数据结构上的一组操作。操作的种类和数目不同，即使逻辑结构相同，这个数据结构的用途

11、也会大为不同。 操作的种类是没有限制的，可以根据需要而定义，基本的操作主要有以下几种：（1）插入：在数据结构中的指定位置上增添新的数据元素。（2）删除：删除数据结构中的某个指定位置上的数据元素。（3）更新：改变数据结构中的某个指定位置上数据元素的值。（4）查找：在数据结构中寻找满足某个特定要求的数据元素的值和位置。（5）排序：在线性结构中，重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或由大到小的次序排列。 从操作的特征来分，所有操作可以归结为两类：一类是加工型操作austructor，操作改变了（操作之前的）结构的值，如前边（1）、（2）、（3）、（5）四种操作。另一类是引用型操作se

12、lector，即此操作不改变结构的值，只要查询或求得结构的值，如前述“查找”操作。 8算法（algorithm）：是对特定问题求解步骤的一种描述，它是指令的有序序列，其中一条指令表示一个或多个操作。一个算法还具有下列五个重要特征：（1）有穷性：一个算法必须总是（对任何可能的输入值）在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。（2）确定性：算法中每一条指令必须有确定的含义。读者理解是不会产生二义性，且在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。（3）可行性：一个算法是可执行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。（4）输入：

13、一个算法有零个或多个的输入，这些输入取自于特定的对象的集合。（5）输出：一个算法由一个或多个的输出。这些输出是同输入有某种特定关系的量。 自学1.3节（略）抽象数据类型的表示和实现。 1.4算法的描述和算法分析 1.4.1算法的描述算法如前所述，数据结构总是与定义其上的一系列操作联系在一起，而操作可以根据某些规则写成算法。算法的描述一般可以归为三种：（1）文字说明：抓住算法的要点，进行定性的文字描述。优点是直观易懂。缺点是不严格，不全面。（2）框图表示：将算法的执行过程用一个流程图表示出来，各种操作更加具体，执行过程清楚，便于用各种语言编写程序。而且不受某种语言的限制。但框图表示不规范，形式不

14、统一，繁简因人而异。 （3）语言程序描述：任何算法必须写成程序才能最后在计算机上实现，因为高级语言有丰富的数据类型，所以通常使用高级语言。但是，因为任何一种具体的高级语言都有一些繁琐的细节规定，所以一般为了集中精力在算法实质上进行描述，常常采用某种简化了的高级语言，它具备了具体语言的基本功能，又取消了一些书写和形式的规定，使读者读后也易于改写为具体的高级语言程序，最后在计算机上实现。课本中采用的是PASCAL，讲课中我将采用如今最流行的C语言，它不仅数据类型丰富，而且结构严谨，特别适合于教学。书中有详例，此处略。 1.4.2算法设计要求 通常设计一个“好”算法应考虑达到以下几个目的，即其正确性

15、、可读性、健壮性、效率与低存储量的要求等。不详讲。1.4.3算法效率的度量 算法的执行时间需要通过按照该算法编制的程序在计算机上运行时所消耗的时间来度量，而度量一个程序的执行时间通常有两种方法：（1）一种是最后统计的方法：执行后利用计算机嫩不及时功能统计的数据分辨算法的优劣。（2）一种是事前分析估算的方法：执行前根据算法选用的策略、问题的规模、书写程序语言的种类、编译程序产生的机器码的质量、机器执行指令的速度等因素来分析估算在计算机上运行时所消耗的时间。具体例子除课本上的外，第二章线性表中也有详细分析。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，它表示随问题规模n的增大，算

16、法执行时间的增长率为f(n)，算法的时间度量记作T(n)=O(f(n)，它和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。 1.4.4算法存储空间需求 一个算法的上机程序除了需要存储空间来寄存本省所用的指令、常量、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为了实现计算所需信息的辅助空间。 类似于算法的时间复杂度，算法的空间复杂度（space complexity）是算法所需存储空间的度量，记作S(n)=O(f(n)，其中n为问题的规模和大小。 第二章第二章 线性表线性表 课本中第二章到第四章讨论线性结构，即线性表、栈和队列以及串。 何谓线性结构呢？其特点是

17、：在结构中的数据元素的非空有限集中，（1）存在惟一的一个被称作“第一个”的数据元素 ；（2）存在惟一的一个被称作“最后一个”的数据元素 ；（3）除“第一个”外，集合中的每一个数据元素均只有一个前驱；（4）除“最后一个”外，集合中的每一个数据元素均只有一个后继。 2.1线性表的逻辑结构 线性表的linear_list是最常用且最简单的一种线性数据结构。线性表的定义为：含有n个数据元素的线性表示，一个数据结构 linear_list=(D,R)其中：D= R=N,N= ， 其中 为某个数据对象。 0,2 , 1,|0nniDaaiiniDaaaaiiii, 3 , 2,011D0 线性表中数据元素

18、可以是各种各样，但同一线性表中的元素必须具有相同特征，因此，属于同一数据对象。关系N是一个序偶的集合，它表示线性表中数据元素之间的相邻关系，即 领先于 ， 领先于 ，。我们称 是 的直接前驱元素， 是 的直接后继元素，而 无前驱， 无后继。 注意：这种数据结构中的逻辑关系是就数据元素而言的。而元素本身数据是具有简单结构还是复杂结构无关。我们在研究这种结构时，是把元素作为一个基本单位（整体）看待的。一个数据元素可以由若干数据项组成，在这种情况下，我们常把数据元素称为记录（record）。含有大量记录的线性表又称为文件（FILE）。如：我们在用数据库处理的多张表都是线性表，26个字母的英文字母表（

19、A,B,C,Z）等也是线性表。 线性表中数据元素的个数n(n0)定义为线性表的长度。其中n=0时称为空，n0时为：（ ）。ai 1aiaiai1ai 1aiai 1aia1anaaaan,3212.1.2线性表的基本运算 线性表的基本运算主要有：插入、删除、查找、排序等。P20（1）INITIATE(L)初始化操作，设定为空的线性表L。（2）LENGTH(L)求长度函数，值为给定线性表中数据元素个数。（3）GET(L,i)取元素函数，若1=iL(link)-plink=p-rlink (2)(p-r(link)-llink=p-llinkcledoublink(h,x)/*以H为头节点的双向循

20、环链表中，删除数据为X的节点/struct node *hp=h-klink;while (p!=h&p-data!=x)p=p-klink;if(p=h)printf(“no”);exit(1);else(p-llink)-klink=p-klink;(p-klink)-llink=p-llink;free(p);p 2在节点x后插入节点y（略），请同学们自己编程实现。 2.4 一元多项式的表示和相加（略） 第三章栈和队列第三章栈和队列 栈和队列也是线性结构，其基本操作是线性表操作的子集，是操作受限的线性表，可称为限定性的数据结构。 3.1栈 3.1.1栈的定义栈是一种经常使用且非常

21、重要的数据结构，是进行特殊操作的线性表。定义：栈是限制插入、删除操作在同一端进行的可变线性表。操作的这一端，即线性表的尾端由其特殊含义称为栈顶（struct top ）另一端（不动端）即称为栈底（struct bottom）若有栈s=(a1,a2,.an),则a1为栈底元素，an为栈顶元素。栈中元素按此顺序进栈，退栈的第一个元素为栈顶元素。即栈的修改按后进先出的原则进行，因此栈又称为后进先出表。LIFO结构（Last In First Out）如图课本Page42图3.1栈所示，栈像一个口袋，又像一个火车站的驿站栈的基本操作除了在栈顶进行插入(push(s,x)和删除pop(s)之外，还有栈的

22、初始化INISTACK(S),判空EMPTY(S),及取栈顶元素TOP(S),栈置空操作SETNULL（S）,CURRENT_SIZE(S)求当前栈中元素个数函数等。 3.1.2栈的表示和实现语言说明：#define M /*M是栈的长度*/ eltype sM; /*eltype表示栈元素的类型*/ int t; /*t称为栈顶指针，初值t=0,表示栈为空*/这里栈s采取顺序静态存储结构下面的数组元素下标从1开始使用，若t=M时意为栈满，此时若有元素再入栈则将产生“数组越界“的结论，称为栈上溢。1进栈：将某一元素x插入栈顶，算法如下push(x)int x if (t=M) /*其中over

23、flow（）表示调用一个上溢处理程序，具体情况视需要而定，上溢说明预先分配给栈的空间已用完，即栈满，不能再进栈，一般这是一个程序的出错状态，必须加以处理，但也可能是作为程序转向的判断标志*/ overflow(); exit(-1); s+t=x;2退栈：取栈顶元素，送入给定的变量y，算法如下：pop(y)int y;if(t=0) underflow(); exit(-1); y=st-; 其中underflow()表示调用一个下溢处理程序，具体情况视需要而定。下溢说明栈已恢复到初始状态（为空），再删除就易出错，需作相应处理，但也可能是程序的结束标志。 解决上溢的办法：1.单个栈的情况根据对

24、栈使用的统计规律，可先分配足够大的空间，防止上溢，因为在软件系统中一般对栈的使用相当频繁，不能每进栈一次就判断一下是否上溢，并且如果上溢了，需再申请空间，这样太耗费时间。因此，这种判断方法仅在理论上可行。2.两个栈的情况：共享空间，对头使用，如下图： s1s2b1t1t2b2这种方法在动态使用时，有时能达到相互调节余缺的作用，在一定程度上节省了空间。 #define M /*共享空间的总长度*/ #defineN /*M=M+1*/ eltype SM; int t1,t2 / *t1,t2 分别为栈S1 ，S2的栈顶指针*/注意：两个栈共享空间时不能将其说明为两个数组，这样达不到共享空间的目

25、的。初值：t1=0，t2=n，此时两个栈为空。 对S1操作：进栈 t1+ 退栈 t1-对S2操作：进栈 t2 退栈 t2+每个栈上溢的条件是t1+1= t23.多个栈的情况：共享空间平分使用，溢出平移。栈顶、栈底指针说明为数组，使用较为方便。如图所示： S1 1 2 N SM t1=b1 t2=b2 tN=bN bN+1=M 具体不再说明（略）。各式中的上溢条件为：ti=bi+1,idata=x;p-next=null;if(r=null)f=p;r=p;elser-next=p;r=p;outqueue(p); /*从队列删除一个结点指针p*/struct node * p,* f;if(f

26、=null) print (“err”);return(); p=f; f=f-next;进栈示意图 r pf X (r)出栈示意图 p f r(f) 可以看出，空队列状态是程序设计中常用的一种控制转移的条件。链栈一般不会发生上溢现象，除非是整个可用空间都被占满。在顺序存储时，可能发生假上溢现象，需进行处理（略）。3.4.3 循环队列队列的顺序存储结构循环队列比链队列节省空间。可用一维数组表示（前面已用语言说明）。入队列操作： f,r=0 初始为空队列 r+; qn=ai /*ai入队列*/出队列操作： f+;y=qf;f=r; /*队列为空* /若队列实际容量不够大时，则会产生假溢出现象。

27、解决溢出的方法之一是把队列设想为一个循环的线性表，即q1接到qm之后。循环队列的操作，可能出现下列情况：（1）队列满（标志为f=r）后,再插入元素，产生上溢，类似栈的情况，可调用overflow(q)来处理。（2）不是插入而是删除m-r元素时，队列为空（f=r=1）后再删除元素，产生下溢，类似栈的情况，可调用underflow(q)来处理。如何解决f=r,同时作为队满和队空标志的矛盾呢？两种解决办法： （1）设立标志单元，记录元素的个数。例如：设立标志单元mark,初值：mark=0。每当插入一个元素时，令mark+;每当删除一个元素时，令mark-;于是，当f=r时，如果mark=m,则队满

28、mark=0，则队空。这种方法的缺点是多用了一个标志单元，且每次对队列的操作都要对标志单元的计数值进行修改，队列一般使用频繁，所以希望减去这种计数运算，改进的方法是：（2）不设标志单元，采取留一个空位的方法。即如果删除前，队列，如图所示，则认为队列已满，不能再插入。插入时，先作r+;后判断r=f?(若r=f，则认为队满)，删除时先判断r=f?(若r=f，则认为队空)，后作f+; a) 进队：inqueue(x)int x;r+; /*先加*/if(r=m+1) r=0;if(r=f) overflow(); /*后判断*/exit();qr=x;b):出队；outqueue(y);int y

29、; if (n=f); /*先判断*/ underflow(); /*下溢处理*/ exit();f+;if (f=m+1) f=1;y=qf;3.5队列的应用 概率的模拟问题。模拟是指通过构造数学模型用计算机程序来模拟一个实际的客观世界的物理过程。这样做较之对这些物理现象本身进行试验要快，并且节省人力和物力，而且一旦做出了模拟，就可以随时改变参数，进而观察这些变化的运动状态。模拟的过程很多，例如：火箭运动，导弹攻击，十字路口上来往的车辆，电话交换台的电话呼叫等等。模拟首先不要简历模型，模拟出计算程序。模型有两种：确定模型和概率模型，我从应用队列出发举一个简化的例子，例：飞机交通流问题（air

30、plane traffic flow）.假定有一个机场，飞机在同一条跑道上着陆和起飞，每架飞机着陆需3分钟起飞需2分钟，每小时平均有8架飞机着陆，8架飞机起飞，并假定飞机是随机时刻到达，求在24小时内，空中飞机和地面飞机的平均等待时间。 可见存在两个队列：空中队列和地面队列。空中飞机需着陆优先于地面飞机起飞（因为空中飞机等待的花费）。即使每小时平均有8架飞机起飞。8架飞机着陆，那么飞机到来的概率为8/60，不来的概率为52/60，（一每分钟作为时间间隔），用一个随机数来模拟飞机的到来，若次数小于8/60表示有飞机到来，把它排在要求着陆的飞机队列里。用另一个随机数确定飞机是否要起飞。如果要起飞，

31、则排在等待起飞的飞机队列里。然后检查跑道是否为空，若空，先检查空中的队列：队列不空，允许队首飞机着陆， 队列为空，再检查地面队列，如图所示： 空中队列q1(1,m)，队首指针为f.1，队尾指针为r1，地面队列为q2(1,m)，队首指针为f2，队尾指针为r2，变量说明：t ：表示时间 （） ：跑道不能提供使用的时间test 0 ：跑道上没有飞机； 2 ：一架着陆飞机在用跑道； 3 :：一架起飞飞机在用跑道；arr：在时刻t已着陆飞机的数目 dep：在时刻t已起飞的飞机的数目 （包括跑道上的飞机） q11.mrand(0)产生0和1 之间的随机数 ； totime ：总的等待时间； avtime

32、：平均等待时间； 跑道跑道 示意图程序如下：#include#include#define QMAX 1000main() /*airplane traffic flow*/int f1, r1, f2, r2, t, arr, dep, runw, totime ; in q1QMAX, q2QMAX, test ,avtime ; f1=r1=f2=r2=0; t=arr=dep=runw=totime=0; do t+;if (rand(0)8/60） q2+r2=t;if(t=runw) test=0; if (r1f1) totime+=t-q1+f1;arr+; runw=t+3;

33、 test=1;else if(r2f2) totime+=t-q2+f2;dep+;runw=t+2;test=2; printf(“t=%d, test=%d,arr=%d,dep=%d,runw=%d”,t,test,arr,dep,runw); while(t=0)n是串中字符的个数，称为长度。串名、串的值，可以是字母、数字和其它字符。零个字符称为空串（nullstring）,长度为零。串在C语言中是一个常量，它可以存放在一个字符数组中。例如：char a=”BEI”, b=”JING”,c=”BEIJING”, d=”BEI JING”; 这里a ,b, c, d实际就是字符串变量，

34、长度为3，4，7，8，并且a和b都是c和d的子串。两串相等当且仅当两个串值相等，也就是长度和对应的字符都相等时才相等，其大小是按照编码顺序进行比较的。 值得一提的是，C语言中，编译程序还在字符串最后自动加上空终止符 0但它不计入字符串的长度，正是由于加上这一终止符，在C语言中对字符串的操作不仅可以通过字符数组操作也可以通过字符指针操作，两者效果一样。后者更方便简洁，我们已学过C语言，不再详述。二 、串的基本操作 这里仅就常用串的操作，通过C语言的一些库函数列入如下： 1 赋值操作（拷贝） # include char *strcpy(str1,str2); char *str1,str2;说明

35、：strcpy()把str2的内容拷贝到str1中，str2是必须具有空终止符的指针，函数返回指向str1的指针。 2 比较操作：#include char strcmp(str1,str2); char *str1, * str2 ; 说明：strcmp()以字典序列比较两个带空终止符的字符串，并返回一个整数（含义） 小于0 str1小于str2 等于 0 str1等于str2 大于0 str1大于str23 求串长：# include int strlen (str); char *str; 说明：stringlen()返回由str指示的带空终止符的串长，空终止符不计在内。 4 串联接 #

36、include char *strcat(str1,str2); char str1,str2;说明：strcat()在str1后面拷贝str2,并以终止符结束。str1原来的终止符被str2的第一个字符覆盖，函数返回指向str1的指针。5 求子串位置：#includeint strcspn(str1,str2).;char *str1,str2; 说明：函数strcspn()返回在str1中出现str2的字符的位置。在c语言的串操作函数库中还有一些其它的函数，共有二十九个。 4.2串的存储结构 基本上可归纳为三种存储结构4.2.1静态字符数组存储结构这在第一节中已经提及，例如我们要处理的文本

37、是一行一行的字符串，预先估计一个行长，即一行最多可能的字符数，那么用于存储每个字符串的变量可以用下面定义的字符段数组表示#define REAX-FINE-LEN 500; char liveMAX-LINE-LEN;这种存储结构中，数组的每个元素（每一个字节）存放一个字符，存储密度大，但由于预先规定了串的最大存储长度，则当串长较小时空间利用率低，另一方面由于限定了串的最大长度，使得串的某些操作，如联接，置换等受到很大的限制或因超越预定空间产生错误的结果，因此和线性表一样可以采取下述的链式存储结构。 4.2.2动态链式存储结构 采取动态链式存储结构存储串时，存在一个结点大小的问题，即每个结点可

38、以放一个字符也可以放多个字符。 当结点大小大于1时，由于串长不一定是结点大小的整数倍，则链表的最后一个结点不满时，通常补上一个不属于字符串的特殊字符来表示。 有时为了便于串的操作，当用链表存储串时，除头指针外，还附带一个尾指针指示表中最后一个结点。在一般情况下，对串的操作为从头到尾的顺序进行，不必建立双向链表。设尾指针的目的是为了便于进行联接操作，但联接需要注意处理首尾的无效字符。 在链式存储结构中，节点大小的选择很重要，它直接影响串的处理速度。在各种串的处理系统中，所处理的串往往很长很多。比如，一本书的几百万字符，情报资料的成百上万条目。这时要考虑串值的存储密度，存储密度定义为：串值所占的字

39、节数除以链表结点实际动态申请的字节数，显然存储密度越小（例如结点大小为1）运算处理越方便，但存储占用量大。如果在串处理过程中需进行内外存交换的话，则会因内外存交换过多而影响处理的总效率。另外，串字符集的大小也是一个重要因素。一般，字符集小，字符的集内编码就短，这也影响串值存储方式的选择。 4.2.3 索引式存储结构在很多的实际应用中采用的是另一种存储结构，即所有串值连续的存放在一个动态申请的最空间中，而每一个串值的实际地址（指针）存放在一个称为索引表示的静态指针数组里。例如下一节的建立关键字索引表示的实例中，采取的就是这种结构，它们的输入文件f和输出文件g示意如下： 1 输入文件f.test的

40、每一行标是一个图书馆的图书卡，有书号和书名组成。 书号 书名005 Computer data strutre010 Introduction to data strutre 023 Fundamentals of data 034 The design and analysis of computer al;gorithas050 introduction to numerical anlasis067 numerical analisis 为了便于查询，建立一个关键词为书号的索引表，如下述的输出文件g所示2输出文件g.text的每一行由关键字（除常用词to,of,anddeng 等）和相关

41、书号组成 关键词 相关书号algorithms 034anylysis 034,050,067computer 005,034data 005,010,023design 034funcdamentals 023numerical 050,067inlnuduction 010,050structures 005,010,023则输出文件的重要结构即采取索引堆结构，用C语言表示如下： /*书号结点类型*/struct nodeint no; struct node *next;/*关键词索引表类型*/struct listchar *stadr;struct node *first;idxMA

42、X_LIST_LEN; /*关键词索引表*/struct char leapMAX_LIST_LEN,*p=leap; /*堆及其指针*/ 其中方括号内是预先定义的两个最大常量，分别表示关键词索引表的最大长度（最多关键词个数）和存放关键字串值堆的最大空间长度。结构示意图如下: stadr first no next add1 034 add2 034 050 067 idx add1 algorithms0 add2 analysis0自由项指针 hp- 在这种结构中，串值的存储位置是程序执行过程中动态申请的。实际地址放在一个索引表中，因此对串值的访问是通过它的索引值（指针）和每个串的终止符进

43、行的。在堆中由于值连续存放，存储密度高，但插入、删除不太方便。要保持有序状态，整个空间需要动态调整。因此在实现过程中，串只是随机存放，而它们按大小的有顺序状态往往是在所有串值存放完了之后，通过索引排序得到的。上述问题的具体程序就是这样实现的。 第五章第五章 多维数组和广义表多维数组和广义表 前三章讨论的线性表、栈、队列和串都是线性的数据结构，它们的逻辑特征是：每一个数据元素至多有一个直接前趋和直接后继。本章介绍的多维数组和广义表是一种复杂的非线性结构。它们的逻辑特征是：一个数据元素可能有多个直接前趋和多个直接后继。 5.1多维数组 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供

44、使用的结构类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： aaaaaaaaaAmnmmnnmn212222111211 可以看成是由m个行向量组成的向量，也可以看成是由n个列向量组成的向量。 二维数组中的每一个元素 均属于两个向量：第i行的行向量和第j列的列向量。也就是说，除了边界外，每个元素 都恰好有两个直接前趋和两个直接后继结点：行向量上的直接前趋 和直接后继 ，列向量上的直接前趋 和直接后继 。并且二维数组仅有一个开始点 ，它没有前趋，仅有一个终端结点 ，它没有后继。另外边

45、界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继，即：除开始结点 外，第一行和第一列上的结点： 都只有一个直接前趋；除终端结点 外，第m行和第n列上的结点 都只有一个直接后继。 aijaijaij 1aij 1aji 1aji 1a11amna11), 2(), 2(11minjaaij和amn) 1, 1() 1, 2(minjaainmj和同样，三维数组 中和每个元素 都属于三个向量，每个元素最多可以有三个直接前趋和三个直接后继。依此类推，m维数组 的每个元素 都属于m个向量，最多可以有m个直接前趋和直接后继。由于计算机的内存结构是一维的，因此用一维内存来表示多维数

46、组，就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 通常有两种顺序存储方式： aijkAmnpannnm21aii im211）行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： 。在PASCAL、C语言中，数组就是按行优先顺序存储的。（2）列优先顺序：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量后面。以二维数组为例，按列优先

47、顺序存储的线性序列为： 。在FORTAN语言中，数组就是按列优先顺序存储的。 aaaaaaaaaamnmmnn,21312222111211aaaaaaaaaamnnnmm,21132221212111 以上规则可以推广到多维的情况：行优先顺序可规定为先排最右的下标，从右向左，最后排左下标；列优先顺序于此相反，先排最左下标，从左向右，最后排最右下标。我们可按此原则排出三维数组。 按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取

48、，即顺序存储的数组是一个随机存取结构。 例如：二维数组 按“行优先顺序”存储在内存中，假设每一个元素占d个存储单元。元素 的存储地址应是数组的基地址加上排在 前面的元素所占用的单元数。因为 位于第i行第j列，前面的i-1行一共有(i-1)*n个元素，第i行上 前面又有j-1个元素，故它前面一共有（i-1）*n+(j-1)个元素，因此， 的地址计算函数为： 。同样，三维数组 按行优先顺序存储，其地址计算函数为： 。我们不难推广到更多维的情况。Amnaijaijaijaijaijdjniloclocaaijij 1) 1()()(Amnpdkpjpniloclocaaijk)1() 1() 1()

49、()(111 上述讨论均是假设数组的下界是1，更一般的二维数组 ，这里 不一定是1。 前共有 行，一共有 列，故这 行共有 个元素，第i行 前一共有 个元素，因此， 的地址计算函数为： 。 值得注意的是，在C语言中，数组的下标的下界是0，因此在C语言中，二维数组的地址计算函数为： 。 以下讨论数组的存储结构时，我们均以C语言的数组下界表示。 ,2211dcdcAcc21、aijci1122cdci1) 1()(221cdciaijcj2aijdjiccloclocccdcaaij)() 1()()()(222121djiloclocdaaij) 1()()(2005.2矩阵的压缩存储 在科学与

50、工程的计算问题中，矩阵是一种常用的数学对象，在用高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。 5.2.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布是有一定规律的矩阵，下面我们讨论几种特殊矩

51、阵的压缩存储。1对称矩阵在一个n阶方阵A中，若元素满足下列性质： 则称A为对称矩阵，例如下面便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节省近一半的存储空间。不失一般性，我们按行优先顺序存储主对角线（包括对角线）以下的元素，其存放形式如下： 10njiaajiij， 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 在这个下三角矩阵中，第i行（ ）恰有i+1个元素，元素总数为： 。 aaaaaaaaaannnnn1, 12, 11 , 10 , 1

52、222120111000ni 02/ ) 1() 1(10nnini因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量san(n+1)/2中。为了便于访问对称矩阵A中的元素，我们必须在 和sak之间找到一个对应的关系。若 ，则 是在下三角矩阵中。 之前的i行一共有1+2+i=i(i+1)/2个元素， 是第i+1个元素，因此有：k=i(i+1)/2+j 若ij，则 是在上三角矩阵中。因为 ，所以只要交换上述对应关系中的i和j即可得到：k=j(j+1)/2+i令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为： ，因此 的地址可用下式计算：aijjiaijaija

53、ij2/ ) 1(0nnkaijaajiijJIIk2 / ) 1(aijdJIISalocdkSalockSaloclocaij2/ ) 1()0 ()0 ()()(2三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如下图（a）所示，它的下三角（不包括主对角线）中的元素均为常数c。下三角矩阵正好相反，它的主对角线上方均为常数c，如下图（b）所示。在多数情况下，三角矩阵的常数c为零。 （a） (b)aaaaaannnnccc1, 11, 1111, 00100aaaaaannnnccc1, 11 , 10, 1111000三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好

54、有 个，因此，三角矩阵可压缩存储到向量Sa 中，其中c存放在向量的最后一个分量中。上三角矩阵中，主对角线之上的第p行（ ）恰有n-p个元素。按行优先顺序存放上三角矩阵中的元素 时， 之前的i行一共有 个元素，在第i行上， 是该行的第j-i+1个元素。因此，Sak和 的对应关系是：下三角矩阵的存储和对称矩阵类似，Sa(k)和 的对应关系是：2/ ) 1( nn12/ ) 1( nnnp 0aijaij2/ ) 12()(10inipnipaijaijjinnjiijinik当当2/)1()12(2/aijjinnjjiik当当2/ ) 1(i2/ ) 1(3对角矩阵对角矩阵中，所有的非零元素都集

55、中在以主对角线为中心的带状区域中。即除了主对角线上和主对角线邻近的上、下方，所有其它的元素均为零。如下图就是一个三对角矩阵： 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每一个非零元素和向量下标的对应关系。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中元素与该向量的对应关系。通过这个关系，仍能对矩阵中的元素进行随机存取。 aaaaaaaaannnn1, 12, 122211211100100000000000005.2.2稀疏矩阵 设矩阵 中有s个非零元素，若s远远小于矩阵元素的总数（即s

56、 t-1 3 0 6 . . . SMAX-1 a - data0000600020003018005054A下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个m*n的矩阵A，它 的 转 置 矩 阵 B 是 一 个 n * m 的 矩 阵 ， 且Aij=Bji, 0=im 0=jdata置换为B的三元组表b-data。 0008000000300205601045BB的三元组表为： i j v 0 0 1 1 1 0 3 6 2 1 0 5 . 1 2 -2 . 2 1 3 b-t-1 4 0 8 . .SMAX-1 b-data 如果只是简单的交换a-data中i和j的内

57、容，那么得到的b-data将是一个按列优先顺序存储的稀疏矩阵B，要得到如上图所示的按行优先顺序存储的b-data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的，为了找到A的每一列中所有的非零元素，需要对三元组表a-data从第一行起整个扫描一遍，由于a-data是按A的行优先顺序存储的，因此得到的恰是b-data应有的次序。具体算法如下： spmatrix *TRANSMAT(a) /*返回稀疏矩阵a的转置*/spmatrix *a;/* 分别指示a-data和b-data中结点序号*/int a

58、n0,bno,col; /*col指示*a的列号（即*b的行号）*/spmatrix *b;b=malloc(sizeof(spmatrix); /*申请*b的存储空间*/b-m=a-n;b-n=a-m; /*行、列数交换*/b-t=a-t;if(b-t0) /*有非零元素，则转置*/ bn0=0; bann00和for(col=0;coln;col+) for(an0=0;an0t;an0+) if(a-dataan0.j=col) b-databn0.i=a-dataan0.j; b-databn0.j=a-dataan0.i; b-databn0.v=a-dataan0.v; bn0+;

59、 return b; /*返回转置结果指针*/ /*TRANSMAT*/ 该算法的时间主要消耗在col和ano的二重循环上，若A的列数为n，非零元素个数为t，则执行时间为o（ ），即与A的列数和非零元素个数的乘积成正比，而通常用二维数组表示矩阵时，其转置算法的执行时间是O( )，它正比于行数和列数的乘积，由于非零元素个数一般远远大于行数。因此，上述稀疏矩阵的转置算法的时间，大于非压缩存储的矩阵转置的时间。 2十字链表 三元组表是用顺序方法来存储稀疏矩阵中的非零元素，当非零元素的位置或个数经常发生变化时，三元组表就不适合做稀疏矩阵的存储结构。例如，要做矩阵相加A+B且结果存于A中，就会因为要在矩

60、阵A的三元组表中插入或删除结点而引起大量的结点移动。因此，采用链表做为存储结构更为恰当。 tnnm 稀疏矩阵的链接存储表示方法不止一种，但我们仅介绍一种称为十字链表的链接存储方法。在该方法中，每一个非零元素用一个结点表示，结点中除了表示非零元素所在的行、列和值的三元组（i，j,v）外，还增加了两个链域：行指针域（rptr），用来指向本行中下一个非零元素；列指针域（cptr），用来指向本列中下一个非零元素。 行指针域将稀疏矩阵中同一行的非零元素链接在一起，列指针域将同一列上的非零元素链接在一起。因此，每一个非零元素aij既是第i行链表上的一个结点；又是第j列链表上的一个结点。它好像处在一个十字交叉路口上，故称这样的链表为十字链表（亦称正交