计算机软件基础第2章线性数据结构.ppt

1、,DATA,10,65,865,姓名 学号 成绩 班级 李红 9761059 95 机97.6,数据结构,第2章 线性数据结构,2.1 基本概念 2.1.1 数据和数据结构 2.1.2 算法的描述和评价 2.2 线性表 2.2.1 线性表的定义及操作 2.2.2 线性表的 顺序存储结构 2.2.3 线性表的链式存储结构 2.2.4 循环链表和双向链表 2.3 栈和队列 2.3.1 栈 2.3.2 队列,2.1 基 本 概 念,2.1.1 数据和数据结构 现代数字计算机原是作为能快速地进行复杂、耗时计算的工具而发明的。随着计算机的发展，在计算机的绝大多数应用中，能够存取、处理大量信息的能力却被认

2、为是计算机的首要特征，而它的计算能力在许多情况下已经几乎被忽略了。有鉴于此，常常把计算机称作数据处理机。,什么是数据？数据就是信息的载体,它可以用计算机表示并加工。可以看出，数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的初期，由于计算机主要用于数值计算，数据指的就是数值。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如字符、文字、表格、图形、图像、声音等也属于数据的范畴。,数据元素是数据集合中的一个个体，它是组成数据的基本单位。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。 数据元素可以是一个数或字符串，也可以由若

3、干数据项组成(数据的最小单位)，在这种情况下，通常把数据元素称为记录。如表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。,表2-1 学生学籍登记表,什么是数据结构？在任何问题中，构成数据的数据元素并不是孤立存在的，它们之间存在着一定的关系以表达不同的事物及事物之间的联系。所以简单地说，数据结构就是研究数据及数据元素之间关系的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容： 数据的逻辑结构。 数据的存储结构

4、。 数据的运算。,1. 数据的逻辑结构,2. 数据的存储结构,3. 数据的运算： 检索、排序、插入、删除、修改等。,A . 线性结构,B . 非线性结构,A . 顺序存储,B . 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,反映数据元素之间的逻辑关系,数据元素在计算机内部的组织方式,C . 散列结构（散列表）,D . 索引结构（索引表）,1. 数据的逻辑结构 数据的逻辑结构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为 DataStructure =(D，R) 其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。 根据数据元素之间关系的不同

5、特性，数据结构又可分为两大类：线性数据结构和非线性数据结构。按照这种划分原则，本书介绍的所有数据结构如图2-1所示。,图2-1 数据结构分类,2数据的存储结构 数据的逻辑结构是从逻辑上来描述数据元素之间的关系的，是独立于计算机的。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究数据元素和数据元素之间的关系如何在计算机中表示，这就是数据的存储结构。 计算机的存储器是由很多存储单元组成的，每个存储单元有惟一的地址。数据的存储结构要讨论的就是数据结构在计算机存储器上的存储映像方法。,实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。一般来说，数据在存储器中的存储有四种基本的

6、映像方法。 (1) 顺序存储结构。这种存储方式主要用于线性数据结构，就是把数据元素按某种顺序放在一块连续的存储单元中。其特点是逻辑上相邻的数据元素存储在物理上相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。 某些非线性数据结构也可以采用顺序方式存储，例如完全二叉树、多维数组等，具体方法将在后面介绍。,(2) 链式存储结构。链式存储结构可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。即可用一组任意的存储单元来存储数据元素，这些存储单元可以是连续的，也可以是不连续的。 链式存储结构的特点就是将存放每个数据元素的结点分为两部分：一部分存放数据元素(称为数据域),另一部分存放指示

7、存储地址的指针(称为指针域)，借助指针表示数据元素之间的逻辑关系。,(3) 索引存储结构。在线性表中，数据元素可以排成一个序列：R1、R2、R3、Rn ，每个数据元素Ri在序列里都有对应的位置数据i，这就是元素的索引。索引存储结构就是通过数据元素的索引号i来确定数据元素Ri的存储地址。一般索引存储结构的实现方法是建立附加的索引表，索引表里第i项的值就是第i个元素的存储地址。,(4) 散列存储结构。这种存储方法就是在数据元素与其在存储器上的存储位置之间建立一个映像关系F。根据这个映像关系F，已知某数据元素就可以得到它的存储地址。即D=F(E)，这里E是要存放的数据元素，D是该数据元素的存储位置。

8、可见，这种存储结构的关键是设计这个函数F。但函数F不可能解决数据存储中的所有问题，还应有一套意外事件的处理方法，它们共同实现数据的散列存储结构。本书第4章中介绍的哈希表，就是散列存储结构的一个实例。,3. 数据的运算 数据的运算是定义在数据逻辑结构上的操作，每种数据结构都有一个运算的集合。常用的运算有检索、插入、删除、更新、排序等。运算的具体实现要在存储结构上进行。 数据的运算是数据结构的一个重要方面。讨论任何一种数据结构时都离不开对该结构上的数据运算及实现算法的讨论。,2.2 线 性 表,2.2.1 线性表的定义及操作 定义2-1 线性表(Linear-list)是n(n0)个数据元素的有限

9、序列。记为： (a1，a2, ., an) 其中，数据元素个数n称为表的长度，n = 0时，称此线性表为空表。,线性表的逻辑结构：若线性表是非空表，则第一个元素a1无前趋，最后一个元素an无后继，其它元素ai(1in)均只有一个直接前驱ai-1和一个直接后继ai+1。 下面给出几个线性表的例子： 例2-1 26个大写的英文字母表：(A，B，C，.，Z) 例2-2 某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出： (200，220，250，300，400，700，1200),例2-3 某单位职工政治面貌登记表如表2-2所示，每个职工的情况为一条记录，它由职工号、姓名

10、、性别、职称、工龄、政治面貌六个数据项组成。 在表2-2中，一个数据元素由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。,表2-2 职工政治面貌登记表,线性表的特点: 同一性。线性表中每个数据元素ai的具体含义，在不同情况下各不相同，它可以是一个数，或是一个符号，甚至是其它更复杂的信息。但在同一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。 有穷性。线性表中数据元素的个数是有限的。 有序性。若线性表是非空表，(a1，a2, ., an), ai-1领先于ai (1in) ，称ai-1是ai的直接前驱元素, ai是ai-1的直接后继元素。

11、除了第一个元素a1外,每个元素ai有且仅有一个被称为其直接前驱的结点ai-1,除了最后一个元素an外,每个元素ai有且仅有一个被称为其直接后继的结点ai+1。这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。,线性表是一个相当灵活的数据结构，它的长度可以根据需要增减，操作也比较灵活方便。线性表的基本操作有以下几种： (1) INITIATE(L)。初始化操作，设定一个空的线性表L。 (2) LENGTH(L)。求表长，求出线性表L中数据元素个数。 (3) GET(L，i)。取元素函数，若1iLENGTH(L)， 则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。,(4)

12、 PRIOR(L，elm)。求前趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空元素。 (5) NEXT(L，elm)。求后继函数，若elm的位序小于LENGTH(L)，则函数值为elm的后继，否则为空元素。 (6) LOCATE(L，x)。定位函数，返回元素x在线性表L中的位置。若L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。 (7) INSERT(L，i，x)。插入操作，若1iLENGTH(L)+1，则在线性表L中的第i个位置上插入元素x，运算结果使得线性表的长度增加1。否则空操作,(8) DELETE(L，i)。删除操作，若1iLENGTH(L)，删除给

13、定线性表L中的第i个数据元素，使得线性表的长度减1。否则空操作 (9) EMPTY(L)。判空表函数，若L为空表，则返回布尔值“true”，否则返回布尔值“false”。 对线性表还有一些更为复杂的操作，如将两个线性表合并成一个线性表；把一个线性表拆分成两个或两个以上的线性表；重新复制一个线性表；对线性表中的元素按值的大小重新排序等。这些运算都可以通过上述基本运算来实现。,2.2.2 线性表的顺序存储结构 在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。,线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的

14、存储单元里。 (1) 设有线性表(a1，a2，.，an)，若1个数据元素只占1个存储单元，则这种分配方式如图2-2所示。 若用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为： Loc(ai)= Loc(a1)+(i-1) 其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址或者基地址。,(2) 若1个数据元素占d个存储单元，则有 Loc(ai)= Loc(a1)+(i-1)*d Loc(ai+1)= Loc(ai)+ d 可见，线性表中每个元素的存储地址是该元素在表中序号i的线性函数。只要确定了线性表的起始地址和每个元素所占存储单元的多少，就可以计算出任

15、一数据元素的存储地址,从而实现对顺序表中任一数据元素的随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。,图2-2 线性表顺序存储结构示意图(设每个数据元素占有1个存储单元),顺序存储结构是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间相邻的逻辑关系。 在C语言中，可用一维数组Vn来描述顺序存储结构。因此,可以借助一维数组来描述顺序表。除了用来存储线性表的元素外,还应该用一个变量来表示线性表的长度属性。,注意：在C语言中数组的下标是从0开始，即： Vn的有效范围是从 V0Vn-1,线性表的顺序存储结构两种实现方法 (1)数组表示法：数组中的分量下标即为元素在线性表中的序号

16、 #define maxlen 100 datatype elemmaxlen; int last; 其中， maxlen是线性表的最大长度，它可以根据实际需要而修改。 datatype抽象数据类型，可用int, float, double, char 或结构体类型等代替如： typedef int datatype,数据域elem描述了线性表中数据元素占用的数组空间，线性表的各个元素a1，a2，an依次存放在一维数组elem的各个分量elem0，elem1，elemlast-1中。 数据域last表示线性表的当前长度。,typedef定义类型,语言不仅提供了丰富的数据类型，而且还允许由用户

17、自己定义类型说明符，也就是说允许由用户为数据类型取 “别名”。类型定义符typedef即可用来完成此功能。 例如，有整型量a,b,其说明如下： int a,b;其中int是整型变量的类型说明符。 int的完整写法为integer，为了增加程序的可读性， 可把整型说明符用typedef定义为：typedef int INTEGER 例如： INTEGER a,b;它等效于： int a,b;,例如： typedef char NAME20; 表示NAME是字符数组类型，数组长度为20。然后可用NAME 说明变量，如： NAME a1,a2,s1,s2;完全等效于： char a120,a220,

18、s120,s220,2）将last与data封装在一起，单独定义一种顺序表类型用结构体建立, last与data作为该结构体的成员项。 #define maxlen 100 typedef struct datatype elemmaxlen; int last; sqlisttp;,用变量方式定义两个顺序表L和P,sqlisttp L , P ;,L. last =2;,L.elem0=91;,L.elem1=82;,P. last =10;,P.elem0=93;,P.elem1=78;,结构体,1、结构体类型的定义 2、结构体变量的定义及引用,结构体类型的引入,问题：为了描述一个事物的不

19、同属性，需要用到各种不同类型的数据，这 些数据彼此相关，形成一个有机的整体。 例如：一个教师的基本信息由姓名、性别、年龄、职称、工资等几项组合 而成。如何描述一个教师的情况呢？ 变量之间是相互独立的，无任何联系；而数组只能用来表示一批相同类型 的数据。因此，若用单个变量分别表示教师的姓名、性别、年龄等属性， 则难以反映他们之间的内在联系；若用数组，则根本无法表示，因为姓 名、性别、年龄等不属同一种数据类型。 C语言中用“结构体”来描述由多个不同类型的数据组成的数据集合。相当于 其他高级语言中的“记录”.,表 教师信息登记表,1.结构体类型的定义,与基本数据类型不同的是，结构体是又一种构造类型，

20、是由多个类型的数据成员组合而来的。因此该类型的具体内容应根据需要先定义，后使用。 可以定义如下结构体类型来描述教师的基本情况： struct teacher /*struct 是关键字*/ char name30; /*内是该类型的各成员*/ char sex; int age; char position10; float salary; ; /*语句末尾是“;” */ 该结构体类型名为struct teacher，teacher 是该结构体的标识符；该类型包含有6个成员的数据项：name、 sex、 age、 position 和salary，其中每个成员项都有自己的类型。,可见，定义一种

21、新的结构体类型的一般形式是： struct 结构体类型名 成员类型 成员名； 成员类型 成员名； ； 其中，struct 是 关键字，结构体类型名、结构体成员名的命名规则同变量的命名规则一样。,2.结构体变量的定义及引用,经以上定义后，结构体类型struct teacher与系统定义的类型int、long、 float 等一样，可以用它来定义该类型的变量、数组、函数等。 例 定义一个结构体变量，用于存放一个教师的信息，然后将其输出。,main() struct teacher char name30; char sex; int age; char position10; float sala

22、ry; ; struct teacher person; /*定义结构体变量person*/ strcpy(,wang li); person.sex=f; /*给各成员赋值*/ person.age=30; strcpy(person.position,middle); person.salary=1600;,printf(n name sex age position salary); printf(n%10s %3c %5d %10s %8.2f,, person.sex,person.age,person.position,person.sa

23、lary); 分析： * 先定义结构体类型，后定义结构体变量。 * 对结构体变量输入输出操作、或将基本类型的数据赋给结构体变量时，需分别访问各个基本类型的成员，不能整体赋值或输入输出。 如：printf(“%s%c%d%s%f”,person); 错！ person=“li li”,f, 24, “primary”,1000; 错！,(一)所谓输入输出是以计算机主机为主体而言的 输出:从计算机向外部输出设备(显示器,打印机) 输出数据。 输入:从输入设备(键盘,鼠标,扫描仪)向计算机 输入数据。,数据输入输出的概念及在C语言中的实现,(二)C语言本身不提供输入输出语句,输入和输出操作是由C函数

24、库中的函数来实现的。 例如: 字符输入函数: getchar 字符输出函数:putchar 格式输入函数: scanf 格式输出函数: printf 字符串输入函数:gets 字数串输出函数:puts,数据输入输出的概念及在C语言中的实现,(三)在使用系统库函数时,要用预编译命令“#include”将有关的“头文件”包括到用户源文件中。 例如：在调用标准输入输出库函数时，文件开头应该有： #include “stdio.h” 或： #include ,头文件,数据输入输出的概念及在C语言中的实现,（一）字符输出函数 一般形式：putchar（c） 函数作用：向终端输出一个字符,字符型变量整型变

25、量,字符数据的输入输出,字符数据的输入输出,例4.1 输出单个字符。#includevoid main()char a,b,c;a=B;b=O;c=Y;putchar(a);putchar(b);putchar(c);putchar(n);,运行结果：BOY,putchar(a);putchar(n);putchar(b);putchar(n);putchar(c);putchar(n);,运行结果：B O Y,字符数据的输入输出,（二）字符输入函数 一般形式：getchar（） 函数作用：从终端（或系统隐含指定的输入设备）输入一个字符。 函数值： 从输入设备得到的字符。,字符数据的输入输出,

26、例4.2 输入单个字符。#includevoid main() char c; c=getchar(); putchar(c); putchar(n);,格式输入与输出,（一）格式输出函数 函数作用：向终端（或系统隐含指定的输出设备）输出若干个任意类型的数据。 一般格式：printf（格式控制，输出表列）,%d:以带符号的十进制形式输出整数 %o:以八进制无符号形式输出整数 %x:以十六进制无符号形式输出整数 To be continued,格式输入与输出,%u:以无符号十进制形式输出整数 %c:以字符形式输出，只输出一个字符 %s:输出字符串 %f:以小数形式输出单，双精度数，隐含输出六位小

27、数 %e:以指数形式输出实数 %g:选用%f或%e格式中输出宽度较短的一种格式，不输 出无意义的0,格式输入与输出,格式符。用来输出十进制整数。 几种用法： :按十进制整型数据的实际长度输出。 :为指定的输出字段的宽度。如果数据的位数小于， 则左端补以空格，若大于，则按实际位数输出。 例: （，）; 若，则输出结果为 ，,格式输入与输出,(2)格式符，用来输出一个字符。 如：d； （，d）； 输出字符.,格式输入与输出,(3)s格式符 输出字符串. 。例如： （，） 输出字符串“”（不包括双引号）。 %ms，输出的字符串占m列，若串长大于m，则全部输出，若串长 小于m，则左补空格。,格式输入与

28、输出,(4)格式符。用来以小数形式输出实数（包括单双精度） 有以下几种用法： 。不指定字段宽度，由系统自动指定字段宽度，使整数 部分全部输出，并输出位小数。应当注意，在输出的数字中 并非全部数字都是有效数字。单精度实数的有效位数一般为位。 .。指定输出的数据共占列，其中有位小数。如果 数值长度小于，则左端补空格。,格式输入与输出,（一）.格式输入函数 函数作用：按照变量在内存的地址将变量值存 进去。 一般格式：scanf（格式控制，地址表列）,同printf函数,是由若干个地址组成的表列，可以是变量的地址，或字符串的首地址,格式输入与输出,例 用scanf函数输入数据。#includevoid

29、 main()int a,b,c;scanf(“%d%d%d”,a在内存中的地址 int last; /* last=length */ sqlisttp; void insert(sqlisttp *v, int i, int x) int k; if (iv- last+1) /* 非法位置*/ printf( 插入位置不合适！n );,else if (v-last=maxlen) /* 表空间溢出*/ printf( 线性表已满！n ); else for( k = v- last-1; k = i-1; k- ) v- elemk+1 = v- elemk; v- elemi-1 =

30、 x; /* 插入x */ v- last+; ,void main( ) sqlisttp lp; int i, a, j, data; for (i=0; i maxlen; i+) scanf( %d, ,线性表中所有数据：12，23，56，21，8，10,插入的数据元素的位置、值：1，28,在上述算法中v为何设计成指针参数? C语言中参数传递是”值”传递方式,若参数设计成sqlisttp v这种类型,在调用 函数时,会把实参的值复制到系统为形参开辟的临时单元中,然后对形参进 行处理,形参是局部变量,当该函数执行完,返回主调函数后,形参即被释放, 对形参所作的任何修改都不可能反映到主调函

31、数中。而把参数设计成指向 线性表的指针后,在调用时传给形参的是指向线性表的指针即线性表的地 址,在被调函数中,可以通过这个地址直接对地址中存储的线性表的各项的 值进行修改。在主调函数中访问线性表时仍然是对相同的地址空间进行访 问,当然这样的修改就可以反映到主调函数中。,算法2-2 线性表的删除算法。 已知线性表的当前状态是(a1，a2，ai-1，ai，ai+1，an)，若要删除第i个元素ai，则线性表成为(a1，a2，ai-1，ai+1，an)。 具体实施步骤为： (1) 若i值合法，则将第i+1至第n个位置上的元素依次向前移动一个存储单位； (2) 将线性表的长度减1。,.,a2,a1,al

32、ast,.,ai+1,ai,0,1,i-1,i,last-1,删除线性表的第i个元素，后面所有元素前移。,ai-1,.,a2,a1,alast,ai+1,ai,删除 结点ai,ai+1,alast,#define maxlen 100 typedef struct int elemmaxlen; int last; sqlisttp; void delete(sqlisttp *v, int i) int k; if (iv- last) printf( 删除位置不合适！n );,else for( k = i; k last-1; k+ ) v- elemk-1 = v- elemk; v-

33、 last-; ,从上述算法中不难看出，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。,当线性表的元素很多，且每个元素的数据项较多时， 花费在移动元素上的时间会很长。 一般情况下，线性表的顺序存储结构适合于表中元素 变动较少的线性表。,2.2.3 线性表的链式存储结构 上节介绍的线性表的顺序存储结构，它的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻的。因此，可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。 然而，这种存储结构有三个缺点：第一，在作插入或删除操作时，需移动大量元素；

34、第二，在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，使存储空间不能得到充分利用；为克服线性表顺序存储结构的缺点，引进了另一种存储结构链式存储结构。,1链式存储结构 线性表的链式存储结构是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。这样，逻辑上相邻的元素在物理位置上就不一定是相邻的，为了能体现元素之间的逻辑关系，就必须在存储每个元素ai的同时，存储其直接后继元素的存储位置。这两部分信息组成一个数据元素的存储映像，称为结点。这时，结点至少包括两个域，一个域存放该元素的数据，称为数据域(data)；另一个域存放后继结点在存储器中的地址，称为指

35、针域或链域(next)。,一般情况下，链表中每个结点可以包含若干个数据域和指针域。若每个结点中只有一个指针域，则称此链表为线性链表或单链表，否则被称为多链表。,data,next,链式存储结构的特点: 存储空间不一定连续; 逻辑关系是由指针来体现的; 逻辑上相邻,物理上不一定相邻; 非随机存储取(顺序存取),例2-4 设有线性表由动物名组成：(cat, horse, monkey, elephant, pig, panda)。 它的物理状态如图2-3所示。 当链表采用图2-3来表示时，逻辑上的顺序不易观察，所以经常把链表用图2-4所示的逻辑状态来表示。,图2-4 线性链表的逻辑状态示意图,图2

36、-3 线性链表的物理状态示意图,在图2-4中，指针域的值用箭头代替了，线性链表结点的相邻关系用箭头来指示，逻辑结构的表示非常形象、清晰。整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域next找到线性表的各个元素，直到next域为空为止。 在此单链表中，head是指向单链表中第一个结点的指针，我们称之为头指针；最后一个元素panda所在结点不存在后继，因而其指针域为“空”(用NULL或 表示)。,通常，我们在单链表第一个元素所在的结点之前附设一个结点头结点，头结点的指针域存储第一个元素所在结点的存储位置；头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。若线性表为

37、空表，则头结点的指针域为“空”，如图2-5所示。 头结点指针:指向头结点的指针,图2-5 带头结点的单链表,单链式存储结构的C语言描述为： struct node int data; struct node *next; ; typedef struct node NODE;,NODE是结点类型；,typedef struct node int data; struct node *next; NODE;,定义结点类型的变量 NODE L L.data=x; L.next=NULL;,定义指向Node类型结点的指针变量 NODE *p p-data=y；p-next=NULL；,3线性链表的运

38、算 线性链表是线性表的链式存储表示，所以对线性链表的运算与前面所介绍的对线性表的运算相同，只是相应的算法与顺序存储的线性表有所不同。,对链表操作时，最基本的操作为插入、删除运算。在讨论插入、删除操作之前，首先要解决插入时的新结点从何处取出，删除后的结点又往何处送的问题。在采用链接分配时，总存在一个可利用的内存空间称为可利用空间表。这样，每当要调用新结点时就到这个可利用空间表里去取，删除时就把结点归还给这个可利用空间表。,在C语言的编程实现时，申请与释放一结点对应于C语言中两个标准函数malloc(sizeof(NODE)和free(p)。 (1) malloc 是从可利用空间表中调用一新结点，

39、并返回该结点的地址。,库函数提供动态地开辟和释放存储单元的函数： malloc函数 其函数原型为void *malloc(unsigned int size);其作用是在内存的 动态存储区中分配一个长度为size的连续空间。此函数的值（即 “返回值”）是一个指向分配域起始地址的指针（类型为 void）。如果此函数未能成功地执行（例如内存空间不足），则 返回空指针(NULL)。,struct node int data; struct node *next; ; typedef struct node NODE;,NODE *p;,p= (NODE *) malloc(sizeof(NODE),

40、(2) free(p)将p指向的结点归还给可利用空间表。,申请分配能存放一个链表结点NODE类型数据的存储空间，并返回这个存储空间的首地址，即指针型变量p指向新申请的结点，为方便起见，以后把指针型变量p所指向的结点称为p结点。,free函数 其函数原型为void free（void *p）;其作用是释放由指向 的内存区，使这部分内存区能被其他变量使用。是最近一次 调用malloc函数时返回的值。free函数无返回值。,结点的表示,100,218,165,333,p,p=? p-data=? p-next=? (p-next)-data=? (p-next)-next=?,1)带头结点单链表的初

41、始化 初始化带头结点的单链表就是建立一个只有头结点的空链表。 NODE* Initlist (NODE *head) head=(NODE *)malloc (sizeof(NODE); head-next=NULL; return (head); ,2) 单链表的查找 按序号查找 在链表中，即使知道被访问结点的序号i,也不能像顺序表中那样直接按 序号i访问结点，实现随机存取，而只能从链表的头指针出发，沿结点 的指针域逐个往后查找，直至搜索到第i个结点为止。 设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链 表的头指针head出发，从头结点开始顺着指针域扫描，用指针p指向当 前

42、扫描到的结点，初值指向第一个结点，用counter做计数器，累计当 前扫描过的结点数（初值为1，把第一个结点看做是第1个结点），当 counter=i时，指针p所指结点就是要找的第i个结点。,N ODE * get( NODE *head, int i) NODE *p; int counter = 1 ; p = head- next; /* 从第一个结点开始扫描 */ while ( p!=NULL) /* 已扫描结点计数*/,/*在带头结点的单链表中找出第i个元素所在结点，若找到，返回该结点的存储位置p，否则返回 NULL */, if ( p!= NULL) /* 找不到, in或i=

43、0 */ ,注意需事先定义NULL的具体数值，比如： #define NULL 0,按值查找 按值查找是指在单链表中查找是否有结点的值等于给定 值x的结点，若有的话，则返回首次找到其值为x的结点 的存储位置，否则返回NULL。查找过程从第一个节点开 始，顺着指针域将结点的值和给定值x作比较。算法如 下： int FoundList (NODE *head, int x ) /*在带头结点的单链表中查找其值为x的结点，若找到，返回该结点在单链表中的序号，即是第几个结点，否则返回0*/, NODE *p; int pos=1; p=head-next; while (p!=NULL) ,3) 单链

44、表的插入 设有线性表(a1，a2，.，ai-1，ai，.，an)，用带头结 点的单链表存储，头指针为head，要求将值为x的元 素插入到第i(1in+1)个位置上，即插入到ai-1与ai 之间，线性表变为(a1，a2，ai-1，x，ai，an) 插入前单链表的逻辑状态如图2-6所示。,图2-6 带头结点单链表的逻辑状态,为插入数据元素x， (1) 首先要生成一个数据域为x的新结点s； (2) 然后确定插入位置，即找到ai之前的元素 ai-1，并使指针p指向之； (3) 最后改变链接，将x插在ai-1与ai之间，修改结点p和结点s的指针域。即 s-next = p-next；p-next = s

45、。 插入结点s后单链表的逻辑状态如图2-7所示。,图2-7 在单链表中插入结点S,算法2-4 void insert(NODE *head, int i, int x) NODE *p, *s; int j=0; p = head; while ( p!=NULL) ,if (p=NULL) | (j！= i-1) printf( i值不合法 n); /* 找不到,in+1或i data = x; /* */ s - next =NULL; s - next = p - next; /* */ p - next = s; /* */ ,设有线性表(a1，a2，.，ai-1，ai，ai+1，.，

46、an)，用带头结点的单链表存储，删除第i(1in)个元素ai所在的结点 删除前的逻辑状态如图2-8所示。 为删除数据元素x,(1) 首先要搜索单链表以找到指定删除结点的前趋结点(假设为p)； (2) 然后改变链接，即只要将待删除结点的指针域内容赋予p结点的指针域即可。,4) 单链表的删除,图2-8 带头结点的单链表,图2-9 在单链表中删除一个结点,算法2-5 void delete(NODE *head, int i) NODE *p, *s; int j=0; p = head; while ( p-next != NULL) ,if (p-next = NULL) | (j != i-1

47、) printf(“i值不合法 n”); /* 找不到,in或i next; p - next = s - next; free(s); ,5) 动态建立单链表的算法,输入线性表元素,以单链式存储方式存储,即创建单链表 方法一:正向建立单链表（尾插法） 思想：从一个空表开始，重复读入数据，生成新结点，将读入数 据存放到新结点的数据域中，然后将新结点插入到当前链表尾结 点之后，直至读入结束标志为止，即从第一个元素结点逐个创建 各个元素结点,每次都是链接到当前链表的最后。 创建头结点: head = (NODE *)malloc(sizeof(NODE); head - next = NULL;

48、p = head; 读入一个元素,链入其中: s = (NODE *)malloc(sizeof(NODE); scanf (,head,p,s,算法2-7 NODE * creatlink2( ) NODE *head, *p, *s; int num; head = (NODE *)malloc(sizeof(NODE); /*生成头结点*/ scanf(“%d”, /* 头指针=尾指针 */ while (num!=0) /* 输入为0为输入结束符*/, s = (NODE *)malloc(sizeof(NODE);/*生成新结点*/ s - data = num; /* 新结点上填入

49、输入值 */ p - next = s; /* 新结点*s插入到尾结点*p之后 */ p = s; /* 尾指针p指向新的表尾 */ scanf(“%d”, /* 返回单链表头指针 */ ,方法二：反向建立链表（头插法） 思想：若线性表的元素已顺序存放在一维数组AN 中，建表方法是从线性表的最后一个元素开始，从后向 前依次插入到当前链表的第一个结点之前,头结点之 后。,创建头结点: head = (NODE *)malloc(sizeof(NODE); head - next = NULL; 读入一个元素,链入其中: s = (NODE *)malloc(sizeof(NODE); s - d

50、ata = Ai; s - next = head - next ; head - next = s;,算法2-6 #define N m /* m为链表中数据元素的个数,如m=10 */ int AN; NODE * creatlink1( ) NODE *head, *s; int i; head = (NODE *)malloc(sizeof(NODE); /*生成头结点*/ head - next = NULL; /* 置空表 */ for(i=N-1; i=0; i-) /* 插入10个数据 */, s = (NODE *)malloc(sizeof(NODE); /*生成新结点*/

51、 s - data = Ai; /*将输入数据放入新结点数据域*/ s - next = head - next; /*新结点与原首结点链接*/ head - next = s; /* 将新结点插入到表头 */ return head; /* 返回单链表头指针 */ ,4. 线性链表算法示例 例2-5 求不带头结点的头指针为head的单链表中的结点数目。 解： int length(NODE *head) NODE *p; int j; p = head; j = 0;,while ( p != NULL ) p = p - next; j+; return j; ,例2-6 设计算法：将一个

52、带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序。,解： void disA(NODE *A, NODE *B) NODE *r, *p, *q; B = (NODE *)malloc(sizeof(NODE); /*建立单链表B的头结点*/ r = B; p = A-next; while (p!=NULL) p-next = q-next; r-next = q; r = q; p = p-next; r-next = NULL; p-next = NULL; ,例2-7 已知两个不带头结点的单链表

53、A、B分别表示两个集合，其元素递增有序。试设计算法求出A与B的交集C。要求C另外开辟存储空间，并同样以元素值递增的带头结点的单链表形式存储。,解： void intersectionset(NODE *A, NODE *B, NODE *C) NODE *r, *p, *q, *s; C = (NODE *)malloc(sizeof(NODE); r = C; p = A; q = B; while (p!=NULL) else if (p-data q-data) q = q-next; else if (p-data = q-data) s = (NODE *)malloc(sizeof

54、(NODE); s-data = p-data;,r-next = s; r = s; p = p-next; q = q-next; r-next = NULL; ,2.2.4 循环链表和双向链表 1. 循环链表 如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。 这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。,图2-10 循环单链表,与单链表比较，循环链表有以下特点： (1) 在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。 (2) 循环单链

55、表的空表判定条件是： head-next=head。,循环链表的存储结构的C语言描述为：同单链式 完全一样 struct node int data; struct node *next; ; typedef struct node NODE;,线性表的各个运算在循环单链存储结构下的虚拟实现 基本与单链式存储结构的相同,区别只在于最后一个结点的判断（即循环的条件不同），算法中的循环条件不是p!= NULL或p-next!=NULL，而是p!= head或p-next!=head 。但利用循环链表实现某些运算较单链表方便（从某个结点出发能求出它的直接前驱，而单链表是不行的，只能从头出发）。,2双

56、向链表 前面讨论的链式存储结构中只有一个指示直接后继的指针域，所以从某结点出发只能顺指针往后查找其它结点。若要查找结点的直接前趋，则应从头指针出发(或在循环单链表中从p结点出发)一直往后找，直到结点q满足q-next=p，那么q是p的前趋结点。为克服链表这种单向性的缺点，为有更大的灵活性来操作线性链表，可采用双向链表存储结构。,双向链表存储结构 方式:用任意存储空间单元来存放线性表的各个元素,为了能体现元素之间的前驱和后继逻辑关系,在存放每个元素的同时,也存放其前驱和后继元素的信息(即前驱和后继元素的存储地址),即用两个指针来表示元素之间的前驱和后继逻辑关系,在每个结点上增加另一个指向线性表中

57、每个元素的前趋结 点的指针域prior，就得到双向链表。其结点的结构如图2-11 所示。 其中，prior是指向前趋结点的指针域；data是数据域； next是指向后继结点的指针域。,图2-11 双向链表结点结构,图2-12 带头结点的空双向链表,双向链表的几种不同状态如图2-12，图2-13所示。,图2-13 带头结点的非空双向链表,在图2-13中的非空双向链表中，设p是指向链表中任一结点的指针，则有： p-next-prior = p-prior-next = p 这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是十分方便的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵活性。 双向链表存储结构C语言实现 struct dnode int data; struct dnode *next; struct dnode *prior; ; typedef struct dnode DNODE;,双向链表的运算如LENGTH(Head)，GET(Head, i)，LOCATE(Head, x)等操作，仅涉及一个方向的