《数据结构》c语言版.docx

《《数据结构》c语言版.docx》由会员分享，可在线阅读，更多相关《《数据结构》c语言版.docx（183页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构概念与基本类型61.1.1 数据结构反用对象61.1.2 学习数据结构的基础71.1.2.1 C语言中的结构体71. 1.2.2 C语言的指针在数据结构中的关联作用81. 1.2.3 C语言的共用体(union)数据类型121.2线性表171.2.1 顺序表181.2.2 链表201. 2. 2. 1链表的基本结构及概念201.2. 2.2单链表设计221.2. 2. 4双链表设计301. 2. 2. 6稀疏矩阵的三元组与十字链表361.2.3 堆栈411. 2. 3. 1堆栈结构411.2. 3. 3堆栈与递归441.3.

2、3. 4递归与分治算法451.4. 3. 5递归与递推491.2.4 队列571.2. 3. 2队列应用591.5. 线性数据结构树641.5.1 概念与术语641.5.1.1 引入非线性数据结构的目的641.3. 1.2树的定义与术语651. 3. 1. 3树的内部节点与叶子节点存储结构问题661.3.2 二叉树661.3. 2.2完全叉树的顺序存储结构681.3. 3. 1基本概念721.4. 3. 2程序设计731.3.4穿线二叉树791. 3. 4. 1叉树的中序线索化802. 3. 4. 2中序遍历线索化的二叉树813. 3. 5. 2在堆中插入节点851.3.6哈夫曼树861. 3

3、. 6. 1 最佳检索树861. 3. 6. 2哈夫曼树结构与算法881. 3. 6. 3哈夫曼树应用901.3. 6. 4哈夫曼树程序设计921.3.7冋数据结构叉树深入学习导读951. 3. 7. 2k-d树程序设计初步971-4非线性数据结构图1001.4.2图形结构的物理存储方式1031.4. 2.1相邻矩阵1031. 4. 2. 2 图的邻接表不1041. 4. 2. 3图的多重邻接表示1061.4.3 图形结构的遍历1071.4.4 无向连通图的最小生成树(minimum-cost spanning tree:MST) 1101.4.5 有 向 图的取短路径1131. 4. 5.

4、1 单源最短路径(single-source shortest paths) 1131. 4. 5. 2 每对顶点间最短路经(all-pairs shortest paths) 1161.4.6拓扑排序117第二章检索1232. 1顺序检索1232.2 对半检索1242.2.1 对半检索与叉平衡树1242.2.2 对半检索思想在链式存储结构中的应用一跳跃表1272.3 分块检索1332.4 哈希检索1342. 4. 2. 1线性探测法和基本聚集问题1363. 4. 2. 2删除操作造成检索链的中断问题1384. 4. 2. 3随机探测法1395. 4. 2. 4平方探测法1406. 4. 2.

5、 5二次聚集问题与双散列探测方法1412.4.3开地址散列142第三章排序1457. 1 交换排序方法1457.1.1 直接插入排序1457.1.2 冒泡排序1477.1.3 选择排序1487.1.4 树型选择排序1493.4 堆排序1543.6 数据结构小结1593.6.1 数据结构的基本概念1593.6.2 数据结构分类1593. 6. 2. 1数据结构中的指针问题1603. 6. 2. 2线性表的效率问题1613.6.3排序与检索1613.7.1 基本概念1623.7.2 上限分析1643.7.3 下限分析1643.7.4 空间代价与时间代价转换165第6章 高级数据结构内容一一索引技术

6、1676. !基本概念1677. 2线性索引1687.1.1 线性索引1687.1.2 倒排表1696.3 2-3 树1706.3.1 2-3 树定义1726.3.2 23树节点插入1736.4 B+树1786.4.1 B+树定义1786.4.2 B+树插入与删除1806.4.3 B+树实验设计182第一章数据结构概念与基本类型1.1 概述1.1.1 数据结构应用对象计算机应用可以分为两大类,类是科学计算和工业控制,另类是商业数据处理。相 应的计算机语言也是如此,比如FORTRAN语言、C、汇编语言主要适应于前者,比如JAVA、 Powerbuilder （关系数据库平台开发工具）、Visua

7、l C等主要适应于后者。面向工业控制与 科学计算的内容主要涉及它的计算方法、效率与速度等因素，某特定的测控对象有特定的 算法，在这里我们主要侧重于解决问题的方法研究，比如高次方程的叠代算法，快速富氏变 换的蝶型算法等。面向商业管理是要解决海量数据的管理与关联分析，即使是一个特定的对 象也有通用的数据管理形式,比如商业数据库系统,无论何种具体应用,它都是大量的表格 类的数据处理形式，在海量数据中检索与査询是类至关重要的操作工具，于是，数据的 逻辑结构与物理组织形式是我们要解决的主要问题，比如表数据的存储形式，索引结构等, 也就是数据结构问题。什么是数据结构?数据结构的研究对象是数据元素，目的是建

8、立数据元素在计算机中的 表达方法，简单的说，在一群有限的数据元素集合里，元素与元素之间相互关系的描述，称 为它的数据结构。比如，例L1描述了有限个数据元素集合的字典的数据结构关系。例1. 1字典的数据结构D=（able,能干的），（apple,苹果），（bug,虫），（code,代码），（cool,酷），,（x-ray, X 光），（year,年），（zoo,动物园）这里，单词是数据元素检索关键字,单词与注释构成数据元素（节点），元素节点之间 所表达的关系是按字母的顺序排列,这就是我们给字典这特定对象选定的数据结构。另一 个例子1. 2描述了事务处理中经常见到表格的数据结构形式。例1. 2线性

9、表数据结构表1. 1设备统计清单序号设备名称型号单价（元）数量1车床A64550052台钻C73200293铳床X-24000144铳床X-3467001如表!. 1所示设备统计表是种线性结构，为了把个线性表转换成可以用计算机处理 的形式,或者说选择表在计算机中的数据结构形式，需要采取如下步骤:首先，水平方向看 表的每一行是一条记录，我们称之为向量a” &=（序号,设备名称，型号，单价，数量）， a,的各分量是设备这客观实体的属性,属性的取值就是实体记录,所以,从纵向看,表是 成由一组记录所组成的,记录是表的数据结构元素，定义如:struct BILLcharFacility20；charTy

10、pe10；intCost；intNumber；）;表结构表达的记录（节点元素）之间的关系是a：, ai“,所以我们称表结构是线性的， 可以用C语言的数组变量定义相应的数据关系为:struct BILLa4；同所有的数组变量样,结构数组的下标也是从。开始的。因此，在计算机中可以用 BILL结构变量型数组A口来描述表1. 1所表达的关系,也就是线性表的数据结构形式:ao= （1,车床，A64, 5500, 5）a尸（2,台钻，C7, 3200, 29）a2= （3,铳床，X-2, 4000, 14）a3= （4,铳，X-34, 6700, 1）1.1. 2学习数据结构的基础数据结构建立在计算机语言

11、之上。学习计算机语言是学习编程方法,我们应该如何用 种具体的计算机语言实现个算法。学习数据结构，是学习如何描述个应用对象的数据元 素（属性构成），如何根据应用对象的特点构造数据元素之间的逻辑关系以及内存中的存储 实现,这是二者的区别。设计数据结构的时候要有相应的计算机语言工具支持，在BASIC、FORTRAN、C语言中， 只有C是面向数据结构应用的工具语言。比较一下C和其它语言的区别就可以知道原因，因 为它有定义数据结构基本单元的能力,并有地址的运算能力,这两点是非常重要的。通过定 义数据结构的基本单元,我们可以把不同数据类型的变量聚集在个节点内;通过地址运算， 我们可以把数据结构的逻辑关系在

12、计算机内存中用不同存储方式实现。在C语言中定义数据 结构元素是通过结构体实现的。1. 1.2. 1 C语言中的结构体在学习C语言的时候，同学对数组很熟悉，比如一个整型量的数组定义如下;int array100：它表达了一组整型量的集合，在C语言中基本变量的类型有整型量，浮点变量，字符变 量等,将所有基本变量聚合在起的方法是定义结构体,用结构体作为基本元素描述事物的 属性信息，比如表1.1那样，我们称之为数据结构元素，或者节点。关于数据结构元素在C 语言中给出了明确定义:结构元素是种被命名为个标识符的各种变量的集合,是提供将各种基本数据类型汇 集到块的手段，它提供了结构变量的格式。比如一个电话簿

13、的结构元素如下定义:struct ADDERcharName20；charStreet40；charCity20；charSTATE2；unisgnedlongZip； );通过结构体定义,ADDER结构变量代表了一组基本数据类型的聚合结构,它就是所谓数 据结构的基本单元，我们定义,数据结构就是描述这样组结构变量之间关系的形式,例如:struct ADDER adder_info100；给出了结构变量ADDER的数组结合形式，是种线性关系数据结构。1.1. 2. 2 C语言的指针在数据结构中的关联作用结构化的程序模块和指针的应用是C语言程序设计的基本风格，随着BC和VC的出现, 面向对象的程序

14、设计方法以及多线程技术给我们提供了在Windows平台上开发应用软件的 多样化风格,但是,指针的应用依然是我们程序设计最基本的特征。指针是地址，它指向数据变量在内存中的地址，请同学牢牢记住这个概念，我们之所以 对指针理解的非常容易混淆,是因为我们没有把指针的概念与变量的存储位置关联在起进 行考虑。请同学清楚下面儿点: 指针的值是地址; 任何一个变量都有一个地址，变量类型不同占用的地址单元数量不同; 指针也是个变量，所以它也有地址: 给指针赋值是让指针变量指向与其同类的个数据变量的地址； 没有赋值的空指针其指向不确定，所以绝对不能在程序中使用;程序中定义任何个名称的变量都对应着个物理地址,因为需

15、要保存变量值在内存该 地址单元内,比如;char name20J编译程序分配地址单元scanf (*%s“，name);给变量 name 赋值个变量在内存占用的地址单元多少由变量的类型决定,比如,字符型变量占用个字 节，整型量占用2个字节，浮点型占用4个字节等,而个结构元素占用的内存字节数由它 所聚集的基本变量类型及数量决定。指针是程序中定义的,因而指针也是个变量，为了区别数据与地址的关系,我们将元 素变量称之为数据变量,称指针为地址变量,所以指针也需要保存,指针本身也有地址:char *cp, name 20: 编译程序给指针变最cp分配地址单元cp=name!给指针变量cp赋值,让它指向数

16、据变量name C程序中指针的用法指针变量的基本概念是地址,它用地址运算符取得某数据变量在内存的地址,从而指 向了该变量。指针存储着个数据变量的地址,既然不同类型的数据变量占用的存储单元数 不同，所以，指针变量的类型应该与其所指向的数据变量同类，也就是有整型量指针，字符 型指针，浮点数指针和结构体指针，这样，在变量集合内,指针加操作时所跨过的地址单 元数，是该类数据变量占用的内存单元长度，从而能正确的指向下个变量位置。指针如下 操作得以指向个数据变量:int val=10, y, *p;p=&val;y=*P；*p=20;20000A?1 20000Aval 200014Hval2001002

17、00100200100.1300000/ 300000p 3000003001203001203001203100y 31000Ay 31000Ay3101310100310100n=&val取得val地卅Y=*P取得P指向的P=20,给p指向的数据变量val内容变量赋值图1.1指针应用一指针p指向变量,操作指针等于操作变量我们首先定义了整型数据变量val、y和整型指针变量p,第二条语句让指针p取得了 val的地址,即指针p指向了变量val,第三条语句将指针所指向的变量val的值赋给了变 量y,第四条语句将指针p指向的变量val的值修改为20,见图1.1(a)。于是，对指针的 操作等价于对变量

18、的操作,程序变得非常简洁,比如下面程序对数组进行线性赋值：int array100,*p, i;p=&array0;for(i=0;i100;i+)*(p+i)=i;切记,一定不能给个没有值的指针,也就是空指针赋值,也不能给指针任意赋个值,比如零,图1.2显示了给个空指针置数的结果,一般0000H是计算机操作系统保留区域, 比如是软中断引导程序的入口地址,假设你给指针指向的地址单元赋值,那就是说你破坏了 系统程序入口地址，如果编译系统没有检査功能，你的程序运行时候将破坏整个计算机系统 运行状态。如果指针的值是任意个随机数,它可能指向任何可能的应用程序正在使用的数 据区或者栈区域,你的赋值操作就

19、破坏了该应用程序,比如说它的返回地址。赋值，破坏了其丄作状态图1. 2对空指针赋值20000Aval V20000AvalV 卜200014Hval200100200100200100 J:1 1 300000p300000P300000丿 p3001203001203001203100q310000q310000q3101310120310120 p=&val取得val地址芝P,把P指向的数据 量val地址赋给了 q*q=20,给q指向的 变量赋值图L 3地址传递指针的另种用法是地址的传递,数据结构中经常将一个指针的值(某节点元素的地址)传递给另个指针，比如，图1.3表示了如下程序段的执行结

20、果。int val=10, *p, *q;p=&val;q=p;*q=20;另外,为数据节点申请内存空间时,用指针指向调用函数返回的节点地址: p= (struct node *)mal loc (sizeof (node) ； /p 是指针变量 指针在数据结构中的关联作用指针在数据结构起到关联节点的作用，让指针从个节点元素指向另一个节点元素,换 句话说，通过指针连接节点元素之间的存储位置,从而让它们之间关联在起，进而表达了 它们之间的逻辑关系。让指针从个节点指向另(或者是多个)节点，需要在节点定义中加入指针变量，指 针在节点内，它指向下个节点，如果你能找到当前节点位置，就能根据指针找到后续节

21、点 所在，这就是节点关联。现在讨论如何用指针关联两个节点元素，我们看例1.3。例L3用节点内部指针关联两个节点。如下个学生数据节点的定义:struct student_nodeint number;char name40;char gender;struct node *student_next;在这个结构体内,我们不但提供了描述学生个体属性的基本变量聚合,而且还有该节点 类型的指针变量next,用next可以指向学生集合中的其它个体或者说是节点,从而表达了 集合中节点之间的关系,使它们关联在起。比如,设指针head已指向内存里的个节点 ai,当再申请个节点比如a2时,通过对ai的next赋值

22、使其指向a2,从而让ai与a2关联起 来,如图1.4所示。方法实例如程序1.1。ala2厂 DATA next DATA nullhead 图L4节点关联程序1.1#include#include #define nul1 0 int main (void)struct student_nodechar number20;char name40;char gender;struct student_node *next;*q, *head;q= (struct student_node *)malloc(sizeof (student_node);节点 alhead=q;/head 指向 al

23、q= (struct student_node *)malloc(sizeof (student_node) ;/节点 a2printf (请输入名字、n);scanf (%s”, q-name); 给 naem 赋值,输入名字printf (请输入学号、n);scanf (%s”, q-number) ;/给 number 赋值,输入学号q-next=null;head-next二q;给al的指针赋值,al的指针指向a2printf (节点a2记录内容是:);printf (如 sn”, head-next-number, headnext-name);打印节点 a2 输入的名字 retur

24、n(0);程序运行结果:请输入名字张三请输入学号2003wl234节点a2记录内容是:2003W1234张三1.1. 2. 3 C语言的共用体(union)数据类型在链表和树结构中往往要求内部节点与外部(比如树杈是内部节点而叶子是外部节点) 同构,处理的方法是c语言中的共用体(union)数据类型,这里简要的回顾共用体的概念。 共用体说明和共用体变量定义共用体是种数据类型,它是一种特殊形式的变量。共用体说明和共用体变量定义与结 构十分相似。其形式为:union共用体名数据类型成员名;数据类型成员名;共用体变量名;共用体表示几个变量共用一个内存位置,在不同的时间保存不同的数据类型和不同长度 的变

25、量。下例表示说明一个共用体a_bc:union data int i;char ch;float f;);再用已说明的共用体可定义共用体变量。例如用上面说明的共用体定义个名为Ige 的共用体变量可写成:union data Ige;共用体变量Ige中整型量i、字符ch以及浮点变量f共用同一内存区域,如图1.5所 示。因此,对三个变量中任何个变量的赋值操作,都会影响其余变量的值。chf图1.5共用体内变量共用内存的同一个区域当个共用体被说明时,编译程序自动地产生一个变量,其长度为共用体中最大的变量 长度。共用体访问其成员的方法与结构相同。同样共用体变量也可以定义成数组或指针,但 定义为指针时也要

26、用”符号,此时共用体访问成员可表示成:共用体名成员名共用体也可以出现在结构内，图1.6描述了下述结构定义的变量之间关系:struct int age;char sex;union int i;char *ch;y;内存长度图1.6结构与共用体关系若要访问结构变量y中共用体x的成员i,可以写成:y. x. i;若要访问结构变量y中共用体x的字符指针ch所指向的内容,可写成:*y. x. ch;若写成y. X. *ch;”是错误的。 结构和共用体的区别1 .结构和共用体都是由多个不同的数据类型成员组成,但在任何同一时刻,共用体中只 存放了一个被选中的成员,而结构的所有成员都存在。2 .对于共用体的

27、不同成员赋值,将会对其它成员重写,原来成员的值就不存在了,而对 于结构的不同成员赋值是互不影响的。因此,共用体中的指针操作需要特别小心，它很容易 被误操作。作为加深对共用体理解的例子,请读者参见程序1.2。程序1.2共用体的应用#include int main(void)Ichar a;union 注意和图L 6的区别int age;char sex;struct (int i;char *ch;x;y;y.age=10;y. x. i=20;覆盖了 y.age,注意高位是。y. sex二b;覆盖了 y. x. i 的低位,，b=98y. x. ch=&a;/y. x. ch在地址上与共用体

28、内其它变量无关*(y. x. ch)=a;printf ,如例1.2的表格数据结构,就使用了数组形式。因 为数组提供的数据元素之间的关系只能是线性相邻的，往往不能满足现实中具有非线性关系 的对象需要，因此，必须借助指针来表达复杂逻辑结构的数据关系。比如,现实中还可以举 出含有多种关系存在的数据结构,设批数据元素的逻辑结构是:K= Ki, K2,K髙组元素R=ri, r2组关系r尸ki, kz, , kz, k3, ,ks, ki, , , , r2-kio, k, 图1. 7 2元关系的逻辑结构图示法图1.8基本的数据逻辑结构类型这是有两元数据关系的逻辑结构,分别用实、虚线表示如图L7所示。关

29、系n表示了 种树形逻辑关系,n表示了 (k10, k. k2)的顺序相邻关系。树形结构是非线性的,当然不 能用线性的数组关系描述,所以必须借助指针。指针既能表达线性相邻也能表达非线性分支, 这是数据结构使用指针的原因所在。现在我们给出数据结构的定义:定义1.1:数据结构是个二元组集合S= (D, R),其中D是结构变量的非空有限集 合,R是描述在D上的有限个关系的集合。所以，我们说数据结构研究的是客观事物个体属性在计算机中表达及描述的方法。在节 点元素中，用计算机语言的基本变量的聚合，刻画了事物的客观属性，指针或数组的地址连 接，则描述了节点之间的关联关系。学习数据结构的内容主要是3点:数据结

30、构的逻辑结构。根据应用对象设计有限元素集合中节点之间的逻辑关系,如, 线性表、树、图等;逻辑结构在计算机中的物理实现。如顺序表、链表、二义树等;数据结构中节点的操作运算。如，插入、删除、检索等。图L8给出了几种基本的数据结构形式。要设计应用于计算机处理的数据结构形式,上 述的定义必须联系于计算机的物理实现有实际意义。数据结构在计算机内存中的表示方法，我们称为数据结构的物理结构，以区别于前者的 逻辑结构形式。物理结构有四种基本的形式,见图1.9所示，其中,索引结构用于文件操作, 散列结构是对数据检索时采用的种形式。顺序存储结构(数组、队列、栈)物理纱松二链式存储结构(链表、树),物理“向二索引存

31、储结构一散列存储结构 数据结构.线性表.逻辑结构 -树、图图1.9基本的数据物理结构类型所谓顺序存储结构,是指将数据元素顺序的存放于计算机内存中一个连续的存储区域 里，借助元素在存储器中的相对位置来表示元素之间的逻辑关系,也就是用数组描述的一群 有限数据元素集合。链式存储结构的特点,是在每个元素中加入一个指针域，它指向逻辑上相邻接的元素的 存放地址。而数据元素在内存中的存放顺序与逻辑关系无关。即链式存储结构是用指针的指 向来表达节点的逻辑关系，这也就是C、Pascal适用于数据结构设计的原因。图1.10给出 顺序、链式存储结构示意。它们都是描述，或者说存储了线性关系a, a“A但方式不同。数据

32、域指针域起始地址S S+L S+2Laj起始地址s川S+Laga3S+L32S+(i-l)*LS+2LajS+ (n-l)*LS+(i-l)*L3i-lS+(i-l)*La3S+i*LS+i*La.S+i*LAS+2LS+(n-l)*I.S+(n-l)*L为指向ai+i(a)顺序存储结构(L是结构元素长度)(b)链式存储结构图!.10向量的顺序存储结构与链式存储结构数据结构有线性与非线性之分。个数据结构的关系里,除去端点外,每个节点有冃 仅有个前趋和后继时,这个数据结构它是线性的。如数组、链表。如果数据结构关系中, 其节点有一个以上的前驱或后继，则称为非线性的数据结构。如树、图。一般情况下,我

33、们 讨论非空有限集合D上只有单关系r的数据结构。但是,在关系数据库设计时，讨论的则 是非空有限集合D上的一组关系R的数据结构设计问题。数据结构的物理表达问题，在有关参考书已经明确给出,读者可以仔细阅读理解,对C 语言不熟悉的读者要尤其注意指针和链式存储结构。在我们的课程中,线性表、树是学习的 重点，而线性表中链表设计是重点内容。它应用了指针的概念，在C语言设计中，掌握了指 针的应用就掌握了 C语言的设计风格，对有关指针和指针型函数还有不清楚地方的需要复 习。图的内容不在本教材讨论范围。排序、检索在数据结构之后学习。在结束有关数据结构的概念讨论之前,我们再次明确的给出数据结构内容的三要素是: 数

34、据结构=数据逻辑结构+物理结构+数据运算数据运算是指对数据结构的检索、插入、排序、删除、更新等操作。此外,不同数据结 构之间的运算效率也是我们要重点考虑的内容。1.2线性表线性表是我们接触的最基本、最普通的种数据结构，我们给出它的定义:定义1.2： 个线性表是数据元素的有限序列心, az, as,aj,其中aaz, as,指是结构元素,下标 是元素序号，它的数据结构表示是:Linear_list=(D, R), R =, ,*。“ aM g D 0 = 1,2这里,关系R给出了元素的种先后次序：ai为表起点,a.为表终点，除第一元素之外, 表中每一元素只有一个前趋,除最后个元素之外,表中每一元

35、素仅有一个后继。根据线性表在内存中的存储方式不同，我们分为顺序存储结构的顺序表和链式存储结构 的链表。顺序表由元素在内存中顺序存储的相对关系来表达逻辑上的线性有序相邻关系。链表则是用指针的指向来表达这种逻辑上的相邻关系,它在物理上是非顺序排列的。从图1.10 中可以看出它们的共性与特性,即用不同的物理存储结构表达同一种线性逻辑关系。1. 2. 1顺序表顺序表是顺序存储结构的线性表，其结构已在图1.10中描述过，就是用数组定义的数 据元素集合、以及元素之间顺序相邻的关系。顺序表内相邻数据元素的物理地址也相邻，因 而物理存储关系表达了逻辑顺序相邻的关系。顺序表结构主要方便实现些简单的数据操作，比如

36、对半检索等。顺序表的特点是简单, 它的主要缺点是需要程序预先定义线性表结构，占用固定的内存空间。这在大多数应用中非 常不方便。比如，个学校的学生关系数据库，有关学生信息的数据纪录条目随着年代的增 加而增加，你不可能预先设定一个最大存储记录的上限,那样非常不便。一般说，顺序存储结构和链式存储结构的区别主要体现在数据结构的操作效率上。现在 讨论顺序表在插入与删除运算方面与链表的区别点。设有长度为n的顺序表:a, a2, as, , aj在第i个元素前插入数据小,如图1.11所示，即:ai, a2, as, ,ab, ai, a为此，我们需要移动数组中的元素以腾出个空位插入加元素。显然，在包含a1元

37、素 块移动时，移动元素个数j是:j=n-i+l i=l, 1, 2,，n如果在表中任一位置插入元素的概率相等，则有P,=丄,其平均移动次数是: + 1屋-十n2图1.11顺序存储的插入操作同样,在删除i节点上元素时,需要顺序移动其后面的元素序列补充这个位置,在顺序 表中元素的移动个数是j=n-i,所以,其平均移动次数是: =丄七(-n-一因此，当n很大时，顺序表插入与删除运算所占用的时间很多，为0(n)时间复杂度 (所花费的时间与规模n成线性关系)。一般说顺序表在读取元素时效率高(是随机存储结 构)，而在插入与删除时效率比较低。顺序存储结构可以描述线性表，但并不是说顺序存储结构只能描述线性表。

38、在个特定 应用对象时,如果考虑节省存储空间的目的，我们往往也用顺序存储结构描述一棵树形结构, 如果读者认为顺序存储结构很简单，没有什么概念可做的话,请看下面例子。问如何用顺序存储结构以最小空间例1.4.树的顺序存储结构。设棵树如图1.12所示,存储在内存中?图!.12 一棵树结构解:首先分析题意,它的实质是如何在顺序存储结构中描述出个元素所具有的多个后继节 点的关系,换句话说,我们要用个序列来表达这棵树的每层元素、以及各层元素之间的 关系，最简单的想法是按层次结构写出这个序列:AB1B2B3C1C2C3C4C5C6C7C8C9C10显然,这样只能限定在这颗特定的树结构卜.，不具有存储树形结构的

39、普遍意义,因为除 非事先指定，否则你不能在程序中区分每层元素的边界。我们仔细分析一下可以发现，树 是一个递归的结构，根有分叉节点,分叉节点与它的后继仍然形成一棵子树，直到叶子,所 以，我们如果能表达出第一层根和后继节点的关系，就可以递归的用这个形式结构表达下去, 设用“(”边界符表示一层边界的起点，“)”表示终点，于是树形结构的元素展开序列为:A (B, (ClC2C3C0B2(C5C6)B3 (CzGCgC.o) 因此,树节点的顺序存储结构是：A ( Bl ( Cl C2 C3 C4 ) B2 ( C5 c6 ) B3 ( C7 c8C9 CIO ) | )程序中，每遇到一个左括弧表示层节点

40、的开始,每遇到一个右括弧表示最近与其相配 的左括弧代表的那层节点结束。(题毕)在数据结构中，用顺序存储结构实现的还有队列、栈等，因为它们都是线性表的种, 所以也可以称为顺序表,但是操作上有其特殊性,它们将在后面内容中继续予以讨论。1. 2. 2链表链表相对来说是个新的内容,也是学习数据结构的入门。我们首先给出它的基本概念, 然后帀点讨论链表设计问题。1. 2. 2. 1链表的基本结构及概念在线性数据结构中为什么使用链式存储结构?前面说过,如果事先知道一个文件占用内 存空间的大小，那么用数组描述(顺序存储结构)是最简洁的。但是,大多数应用例子表明 无法预先给定一个文件记录数的上限,那样非常不经济

41、。最适宜的处理方法是仅在输入一条 文件记录时，向计算机内存管理系统申请个记录节点所需的空间。系统根据内存当前占用 情况进行动态地址分配。然后程序根据所得到的地址，输入这条纪录的数据到这个地址単元 区域内,并把这条记录的地址连接到文件当前纪录的末端，使所有纪录串起来形成一个链。只要内存未满(一般情况下可以假设计算机硬盘足够的大),并且程序能正确的连接文 件所有记录的地址，则文件记录长度可以动态生长，当然也可以动态删除，而连接所有纪录 地址的方法就是指针。如何用指针链接各个数据节点?让我们回顾例1.3描述的指针关联作用,定义在节点内 部有一个指针域，只要初始有一个头指针head,并让它指向头节点小

42、,那么,通过把每次输 入纪录ai的地址赋值给其前驱节点ai所含的指针next,就可以让ai指向a,：a； i-next=ai；它描述了a” am的逻辑关系。线性表的链式存储结构特点是用内存中随机分布的存储单元来存储线性表的数据元素， 而关系ai,a,Q,是用节点a,指针域所含的后继节点a川地址信息来表达的。即,节点分为 数据域与指针域两部分，如图1.13 (a)所示。head 头指针数据域指针域I(a)节点结构head头指针第一个节点 直接后继节点(b)单链表结构I I 1叩瓯卜尾指针为空尾指针指向首节点直接后继节点(C)循环单链表结构图1.13单链表结构所有节点指针的指向形成了一条数据链。图1.14给出了链表的基本类型，图!.15是双 链表结构0单链表:只有一个指针域指向直接后继节点链表类型 一A双链表:有两个指针域指向直接前趋与后继节点循环链表：头尾相连的单、双链表图L 14基本的链表数据结构分类I后继指针域数据域前驳指针最!(a)节点结构头指表头节点(b)双链表图1.15双链表结构我们要注意头指针的作用,空表时指针亦为空。此外,单、双链表的循环结构和非循环 结构没有本质的区别。程序设计时，有时也用尾指针来取代头指针，详细见后述例题。有的 参考书设置有专门的头节点，在它数据域设置个特定的赋