自学考试：数据结构导论课件.pdf

《自学考试：数据结构导论课件.pdf》由会员分享，可在线阅读，更多相关《自学考试：数据结构导论课件.pdf（139页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 需要把原始数据按照某种方式组织起来，以便很好地体现数据之间的关系，数据及数据的组 在每个步骤中，数据的表现形式都不相同，实际问题中的数据称为原始数据。在数学模型中， （3）用某种计算机语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解答。 （2）设计一个求解该数学模型的算法； （1）从具体的问题抽象出一个适当的数学模型； 1、计算机解决一个具体问题时，一般需要经过以下几个步骤： 第一节 引言 们在计算机内的存储方式，以及定义在该组数据上的一组操作。 更进一步地说，数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它 简单地说，数据结构是计算机组织数据和存储数据的方式

2、。 第零节 概论 第一章 概论 2 数据的存储结构和数据的基本运算。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包括数据的逻辑结构、 数据元素组成，而数据元素又可由若干个数据项组成。 从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个 它是数 据的不可分割的最小标识单位。 （3）数据项：一般情况下，数据元素由数据项组成。在数据库中数据项又称为字段或域。 运算的基本单位，通常具有完整确定的实际意义。数据元素常常又简称为元素。 （2）数据元素：数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元素是 （1）数据：所有被计算机存储、处理的对象。

3、 一、数据、数据元素和数据项 第二节 基本概念和术语 法+数据结构=程序。该公式简洁地描述了算法、数据结构和程序之间关系。 2、1976年瑞士计算机科学家尼克劳斯维尔特（NiklausWirth）曾提出一个著名公式：算 存储的存储结构。如下图： 织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机 3 （1）存储数据元素； 一个存储结构包括以下两个部分： 1、数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。一般情况下， 三、数据的存储结构 （4）图结构最复杂，其中任何两个结点都可以相邻接。 结点相邻接，但下层结点只能和上层的一个结点相邻接。 （3）树

4、形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个 （2）线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。 （1）集合中任意两个结点之间都没有邻接关系，组织形式松散。 2、根据数据元素之间的关系，有四类基本的逻辑结构： 方式或“邻接关系”。 1、数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联 二、数据的逻辑结构 4 心概念。 运算的实现是指该运算的算法。算法是计算机科学的一个基本概念，也是程序设计的一个核 （一）算法的概念 第三节 算法及描述 它们是不同的数据结构。 2、线性表、栈和队列中的元素具有相同的逻辑结构（

5、即线性结构），但有不同的运算集， 查找、读取、插入和删除等。 结构为对象。一般来说，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：建立、 1、运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑 四、运算 级和语言级上讨论。 储结构称为给定逻辑结构的存储实现或存储映像。如何来描述存储结构呢？可以分别在机器 3、一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存 除了上述两种存储方式之外，还有索引存储方式和散列存储方式。 向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。 （2）链式存储方式是指每个存储结点除了含有一个数据

6、元素外，还包含指针，每个指针指 相对位置来表示数据元素之间的逻辑关系。 （1）顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的 2、表示数据元素之间的关联方式主要有顺序存储方式和链式存储方式。 （2）数据元素之间的关联方式。5 else 语句; if(表达式) 语句; 或 if(表达式) 语句; （1）条件语句： 4、选择语句 变量名=表达式; 3、赋值语句 输出语句：printf(格式串，变量1,变量n); 输入语句：scanf(格式串，变量1,变量n); 2、输入、输出语句 语句序列 /算法说明 函数类型 函数名（函数参数表） 1、函数描述形式 算法可以用某种语言

7、加以描述。本书采用类C语言来描述算法。 （二）算法的描述6 7、出错语句error(“错误描述”) （3）异常结束语句：exit(异常代码)； （2）case 结束语句：break； （1）函数结束语句：return表达式； 6、结束语句 while(条件); 语句; do while(条件) 语句; for(赋初值表达式序列;条件;修改表达式序列) 语句; 5、循环语句 default: 语句序列; /可以省略 case 条件n: 语句序列;break; case条件2: 语句序列;break; case条件1: 语句序列;break; switch （2）分支语句：7 时间与n2成正比。

8、如：T(n)=O(n )，这种表示法称为大O表示法，它的含义是：当n充分大时，算法的执行 2 算法的渐进时间复杂度，简称时间复杂度。 不考虑具体的运行时间，只给出算法在问题规模n下执行时间的上界。T(n)=O(f(n)称为 0 对所有nn 成立。其中，f(n)为问题规模n的某个函数。大O表示法也称渐进表示法，它 T(n)cf(n) 大O表示法的具体提法是：当且仅当存在正常数c和n ，使得 0 1、大O表示法 一、时间复杂度 间效率）， 前者是算法包含的计算量，后者是算法需要的存储量。 （4）时空性：一个算法的时空性是指该算法的时间性能（或时间效率）和空间性能（或空 到的运行结果。 （3）健壮性

9、：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不 （2）易读性：易于阅读、理解和交流，便于调试、修改和扩充。 （1）正确性：能正确地实现预定的功能，满足具体问题的需要。 评价算法好坏的因素包括以下几个方面： 第四节 算法分析 多行注释：/* 注释内容 */ 单行注释：/注释内容 8、注释8 常可记为： 1、个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模n的函数。通 二、空间复杂度 程序步的计算机上运行所需要的时间。 4、为了比较不同量级时间复杂度的差异，下表为不同时间复杂度阶数f(n)在每秒20亿个 平均时间复杂度是指，对所有相同输入数据量的各种不同输入数据

10、，算法时间用量的平均值。 最坏时间复杂度是指，对相同输入数据量的不同输入数据，算法时间用量的最大值。 3、最坏时间复杂度和平均时间复杂度 效率的。 通常认为，时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高 (5) 指数阶0(C )，C为大于1的正整数，常见的指数阶有O(2 )。 n n (4) 多项式阶O(n )，C为大于1的正整数，常见的多项式阶有O(n )和O(n )； C 2 3 (3) 线性阶O(n)； (2) 对数阶O(log2n)； (1) 常数阶O(1)（即算法的时间复杂度与输入规模n无关）； 2、时间复杂度常见的阶数 9 的空间。 （3）辅助变量所占用的

11、空间，在估算算法空间复杂度时，一般只需要分析辅助变量所占用 （2）输入数据所占用的空间； （1）程序代码所占用的空间； 期间所需要的存储空间量应包括以下三个部分： 2、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在执行 其中，g(n)为问题规模n的某个函数。 S(n)=0(g(n)10 D:算法中需要的辅助变量所占用存储空间的大小 C:算法中所占用的所有存储空间的大小 B:算法本身所占用的存储空间的大小 A:算法中输入数据所占用的存储空间的大小 5. 算法的空间复杂度是指（） C:O(n2) D:O(2n) A:O(log n) B:O(n) 2 4. 下面几种算法时

12、间复杂度阶数中，最小的是（） C:健壮性 D:时空性 A:正确性 B:易读性 果，这种算法好坏的评价因素称为（） 3. 即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结 C:树形结构 D:图结构 A:集合 B:线性结构 的一个结点相邻接，这种组织形式称为（） 2. 具有分支、层次特性，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层 C:数据元素 D:数据变量 A:数据项 B:数据记录 1. 数据的不可分割的最小标识单位是（） 【单选题】 章节练习11 7. 链式存储的特点是利用指针来表示数据元素之间的_关系。 6. 计算机图灵奖获得者 N.Wirth曾提出

13、一个著名公式:算法+_=程序。 【填空题】12 所需要的存储空间量应包括以下三个部分： 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。一个算法在执行期间 解析：一个算法的空间复杂度定义为该算法所耗费的存储空间。 5. 答案：C 解析： 4. 答案：A 或进行处理,不会产生预料不到的运行结果。 解析：通常评价算法好坏的因素包括：健壮性,即使输入非法数据,算法也能适当地做出反应 3. 答案：C 相邻接，但下层结点只能和上层的一个结点相邻接。 解析：树形结构具有分支层次特性，其形态像自然界的树，上层的结点可以和下层多个结点 2. 答案：C 的不可分割的最小标识单位。 解析：一般情况下

14、，数据元素由数据项组成。在数据库中数据项又称为字段或域。它是数据 1. 答案：A 【单选题】 答案及解析 13 向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。 解析：链式存储方式是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指 7. 答案：逻辑 算法+数据结构=程序。该公式简洁地描述了算法、数据结构和程序之间关系。 解析：1976年瑞士计算机科学家尼克劳斯维尔特(NiklausWirth)曾提出一个著名公式： 6. 答案：数据结构 【填空题】 （3）辅助变量所占用的空间 （2）输入数据所占用的空间； （1）程序代码所占用的空间；14 (1) 初始化Initia

15、te(L)：建立一个空表L=()，L不含数据元素。 3、线性表基本运算及功能描述。 点有且仅有一个直接后继。 接前驱外，其他每个结点有且仅有一个直接前驱；除终端结点没有直接后继外，其他每个结 2、基本特征：线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直 一对相邻结点a 和a i i+1 (1i0时，线性表通常表示成(a ，a 1 2 ,，a )，a n 1 称为起始结点，a n 为终端结点。对任意 点。结点个数n称为表长。当n=0时，线性表不含任何数据元素，称为空表，记为()或。 1、线性表是一种线性结构，它是由n(n0)个数据元素组成的有穷序列，数据元素又称结 第一节 线

16、性表的基本概念 第二章 线性表 15 1、插入 顺序表的“第i个数据元素”存放在数组下标为“i-1”的位置。 二、线性表的基本运算在顺序表上的实现 用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。 点其存储位置也相邻。 数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结 线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中， 一、线性表顺序存储的类型定义 第二节 线性表的顺序存储 a )，表长度减1。 n 删除后线性表L由(a ，a 1 2 ，a i-1 ， a ，a i i+1 ，.，a )变为(a n 1 ，a ，a 2

17、i-1 ，a i+1 ，.， (6) 删除Delete(L，i)：删除线性表L的第i个数据元素a ，i的有效取值范围是1in。 i i+1 1 i-1 i+1 ，.，a )，表长度加 1。 n ，x， a ，a i ，a ，a 2 ，.，a )变为(a n a 参数i的合法取值范围是1in+1。操作结束后线性表L由（a ，a 1 2 ，a i-1 ， a ， i (5) 插入Insert(L，x，i)：在线性表L的第i个数据元素之前插入一个值为x的新数据元素， 值与x相等，运算结果为这些结点中序号的最小值，若找不到该结点，则运算结果为0。 (4) 定位Locate(L，x)：查找线性表中数据元

18、素值等于x的结点序号，若有多个数据元素 回一特殊值。 (3) 读表元素Get(L，i)：返回线性表第i个数据元素，当i不满足1iLength(L)时，返 (2) 求表长Length(L)：返回线性表L的长度。16 点a ）；表长度减1。此处无需考虑溢出，只判断参数i是否合法即可。算法描述如下： i i+1 n 删除运算的基本步骤是：结点a ,，a 依次向左移动一个元素位置（从而覆盖掉被删结 i-1 i+1 ，.，a )。 n a ，a 度为n的线性表（a ，a 1 2 ，a i-1 ， a ，a i i+1 ，.，a )变为长度为n-1的线性表(a n 1 ，a ， 2 删除运算DeleteS

19、eqlist(SeqListL,inti)是指将线性表的第i(1in)个数据元素删去，使长 2、删除 L.length+; /表长度加1 L.datai-1=x; /元素x置入到下标为i-1的位置 L.dataj=L.dataj-1; /依次后移 for(j=L.length;j=i;j-) /初始 i=L.length if(iL.length+1) exit(“位置错”)；/检查插入位置是否合法 if(L.length=Maxsize) exit(“表已满”); /将元素x插入到顺序表L的第i个数据元素之前 voidInsertSeqlist(SeqListL,DataTypex,inti

20、) 数据元素的位置；然后将x置入该空位，最后表长加1。具体的插入算法描述如下： 插入算法的基本步骤是：首先将结点a a i n 依次向后移动一个元素的位置，这样空出第i个 a )变为长度为n+1的线性表(a n 1 ，a ，a 2 i-1 ，x， a ，a i i+1 ，.，a )。 n n+1)个元素之前，插入一个新元素x。使长度为n的线性表（a ，a 1 2 ，a i-1 ，a ，a i i+1 ，.， 顺序表的插入运算InsertSeqlist(SeqListL,DataTypex,inti)是指在顺序表的第i(1i17 elsereturn0; /未查找到值为x的兀素，返回0 if(i

21、L.length) returni+1; /若找到值为x的兀素，返回兀素的序号 i+; while(iL.length)&(L.datai!=x) /在顺序表中查找值为 x 的结点 inti=0; intLocateSeqlist(SeqListL,DataTypex) 元素，考察元素的值是否等于x，描述算法如下： 序号的最小值，当找不到值为x的结点时，返回结果0。下列算法从左往右扫描顺序表中的 定位运算LocateSeqlist(SeqListL,DataTypex)的功能是查找出线性表L中值等于x的结点 3、定位 L.length-; /表长度减1 L.dataj-1=L.dataj; /

22、依次左移 for(j=i;jL.length;j+) /第i个元素的下标为i-1 exit(“非法位置”); if(iL.length) /检查位置是否合法 /删除线性表L中的第i个数据结点 voidDeleteSeqList(SeqListL,inti)18 1、结点结构 一、单链表的类型定义 链表和双向循环链表，其中最简单的是单链表。 线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环 第三节 线性表的链接存储 到最低。 平均时间复杂度为O(n)。求表长和读表元素算法的时间复杂度为O(1)，就阶数而言，己达 （3）对于定位算法，需要扫描顺序表中的元素。以参数x

23、与表中结点值的比较为标准操作， O(n)，元素平均移动次数约为（n-1）/2，时间复杂度为O(n)。 （2）删除算法DeleteSeqlist，可得其在最坏情况下元素移动次数为n-1，时间复杂度为 比较和移动的次数为n-i+1次，插入算法的平均移动次数约为n/2，其时间复杂度是O(n)。 还与插入的位置i有关。插入算法在最坏情况下，其时间复杂度为O(n)。一般情况下元素 （1）设表的长度length=n，在插入算法中，元素的移动次数不仅与顺序表的长度n有关， 在分析线性表的顺序表实现算法时，一个重要指标就是数据元素的比较和移动的次数。 三、顺序表实现算法的分析 顺序表的求表长操作，直接输出L.

24、length即可。 19 structnode*next; /指针域 DataTypedata; /数据域 typedefstructnode 3、单链表的类型定义如下： 如果head等于NULL，则表示该链表无任何结点，是空单链表。 空指针，它不指向任何结点，表示链表结束。 （3）链表中最后一个数据元素结点称为尾结点或终端结点。尾结点指针域的值NULL称为 （2）链表中第一个数据元素结点称为链表的首结点。 针变量来命名单链表。 （1）head称为头指针变量，该变量的值是指向单链表的第一个结点的指针。可以用头指 所有结点通过指针链接形成链表。 2、单链表 直接后继结点。 （2）next部分称为

25、指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的 （1）data部分称为数据域，用于存储线性表的一个数据元素。 20 LinkList head; /头指针 /建立一个空的单链表 LinkList InitiateLinkList() 空表由一个头指针和一个头结点组成。算法描述如下： 1、初始化 二、线性表的基本运算在单链表上的实现 和尾结点。 点，称之为头结点，其他结点称为表结点。表结点的第一个和最后一个结点分别就是首结点 在本书的讨论中，为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结 4、带头结点的单链表 Node,*LinkList; 21 线性表的定位运

26、算，就是对给定表元素的值，找出这个元素的位置。在单链表的实现中，则 4、定位 一直往后移动，直到第i个结点。 指针相连，一个结点的位置包含在直接前驱结点的next域中。所以，必须从头指针出发， 通常给定一个序号i，查找线性表的第i个元素。在链表中，任何相邻的两个结点通过一个 3、读表元素 成对所有结点的访问，计数器cut的值即是表的长度。 让计数器加1。直到工作指针p-next为NULL时，说明已经走到了表的尾部，这时已完 后，让工作指针p通过指针域逐个结点向尾结点移动，工作指针每向尾部移动一个结点， 设置一个工作指针p，初始时，p指向头结点，并设置一个计数器cnt，初值设置为0。然 外的结点

27、的个数。 在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头 结点以 2、求表长 有一个头结点，它的指针域为NULL。 在算法中，变量head是链表的头指针，它指向新创建的结点，即头结点。一个空单链表仅 returnhead; head-next=NULL; head=malloc(sizeof(Node); /动态构建一结点，它是头结点22 步骤：（1）先找到链表的第i-1个结点q。（2）生成一个值为x的新结点p，p的指针域 单链表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。 5、插入 elsereturn0; if(p!=NULL) return

28、i+1; p=p-next; i+; while(p!=NULL&p-data!=x) /访问链表 inti=0; /i代表结点的序号，这里置初值为 p=p-next; /初始时p指向首结点 Node*p=head; /p是工作指针 /求表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果为0 intLocateLinklist(LinkListhead,DataTypex) 定位运算算法描述如下： 返回0。 在定位运算中，也需要从头至尾访问链表，直至找到需要的结点，返回其序号。若未找到， 是给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称作按值查找。23 q-n

29、ext=p; /修改*q的链域 p-next=q-next; /新结点链域指向*q的后继结点 p=malloc(sizeof(Node);p-data=x;/生成新结点 else exit(“找不到插入的位置”); if(q=NULL) /第i-1个结点不存在 else q=GetLinklist(head,i-1); /找第 i-1个数据元素结点 if(i=1) q=head; Node*p,*q; /在表head的第i个数据元素结点之前插入一个以x为值的新结点 voidInsertLinklist(LinkListhead,DataTypex,inti) 插入运算描述如下： 指向q的直接后

30、继结点，如下图。（3）q的指针域指向P，如下图。 24 elseexit(“找不到要删除的结点”); /结点不存在 free(p); /释放已移出结点p的空间 q-next=p-next; /移出待删结点 p=q-next; /p指向待删结点 if(q!=NULL&q-next!=NULL) /若直接前驱存在且待删结点存在 elseq=GetLinklist(head,i-1); /先找待删结点的直接前驱 if(i=1) q=head; Node *q; /删除表head的第i个结点 voidDeleteLinklist(LinkListhead,inti) 单链表的删除运算算法描述如下： 的

31、指针域，使其指向移出结点a 的直接后继结点。 i 以维持剩余结点的链接关系。如下图，将a 结点移出后，需要修改该结点的直接前驱结点 i 删除运算是给定一个值i，将链表中第i个结点从链表中移出，并修改相关结点的指针域， 6、删除 点*q的链域值（即指向原表第i个结点的指针）将丢失。 注意：链接操作p-next=q-next和q-next=p两条语句的执行顺序不能颠倒，否则结25 指针始终指向“当前比较结点”的前驱结点。 在线性表中，若有重复结点，一般只保留结点序号最小的那个结点。为了便于删除操作，P 二、删除重复结点 最终形成的链表的数据顺序与输入顺序正好相反。 用方法二建立的链表，最终形成的链

32、表的数据顺序与输入顺序相同，用方法三建立的链表， 操作。它的时间复杂度也是O(n)。 方法三：始终将新增加的结点插入到头结点之后，第一个数据结点之前，可称之为“前插” 个数成正比，故其时间复杂度为O(n)，比前一个算法快。 方法二：用一个指针指向尾结点，这样就为下一个新结点指明了插入位置。它的时间与元素 大插入位置i，使新的结点链入到链表中。其时间复杂度为O(n2)。 方法一：通过已实现的插入算法InsertLinklist(LinkListhead，intx,inti)来实现，依次增 将新结点链接到表尾这两个步骤，直到线性表中所有元素链接到单链表中。 点，然后将新结点链接到头结点之后，这个结

33、点为尾结点（也是首结点）；复建立新结点和 建立含头结点的单链表。这个过程分为三步：首先建立带头结点的空表；其次建立一个新结 一、建表 第四节 其他运算在单链表上的实现 变成一个无用的结点，它会一直占用着系统内存空间，其他程序将无法使用这块空间。 注意：free(p)是必不可少的，因为当一个结点从链表移出后，如果不释放它的空间，它将26 /移出结点*(p-next)，p-next指向原来*(p-next)的后继结点 p-next=r-next; r=p-next; /r指向待删结点 if(p-next-data=q-data) /若*(p-next)是*q的重复结点 while(p-next!=

34、NULL) /当*p的后继结点存在时,将其数据域与*q数据域比较 p=q; /工作指针p指向*q /当前检查结点*q不是尾结点时，寻找并删除它的重复结点 while(q!=NULL) q=head-next; /q指示当前检查结点的位置，置其初值指向首结点 Node*p,*q,*r; /删除表head中多余的重复结点 voidPurgeLinklist(LinkListhead) 用链表作为存储结构，细化上述算法得到最后的算法描述： 27 在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior，这样每个结点有两 二、双向循环链表 中，从任一结点出发能够扫描整个链表。 在单链表中，如

35、果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表 一、循环链表 第五节 其他链表 q=q-next; /更新检查结点 elsep=p-next; /否则，让p指向下一个结点 free(r); 28 （1）、（2）这两个语句的执行顺序可以颠倒。 (3) free(p); /释放*p的空间 (2) p-next-prior=p-prior; /p后继结点的前链指向p的前驱结点 (1) p-prior-next=p-next; /p前驱结点的后链指向p的后继结点 设p指向待删结点，删除*p可通过下述语句完成： 1、删除 即结点p的前驱结点的next和后继结点的prior都指向结点p

36、。 双向循环链表的对称性可以用下列等式表示：p=p-prior-next=p-next-prior。 双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。 个结点的next指向头结点，由这种结点构成的链表称为双向循环链表，如图： prior与next类型相同，它指向直接前驱结点。头结点的prior指向最后一个结点，最后一 个指针，其结点结构如图： 29 (1) 对于按位置查找运算，顺序表是随机存取，时间复杂度为O(1)。单链表需要对表元 素 1、线性表和链表的时间性能和空间性能进行比较 第六节 顺序实现与链接实现的比较 (4) p-next=t; (3) p-next-prior=t;

37、(2) t-next=p-next; (1) t-prior=p; 在p所指结点的后面插入一个新结点*t，需要修改四个指针: 2、插入 30 的结点个数就没有限制。 过小，又将发生上溢；单链表不需要预先分配空间，只要内存空间没有耗尽，单链表中 (2) 从整体考虑，顺序表要预分配存储空间，如果预先分配得过大，将造成浪费，若分配得 (1) 单链表的每个结点包括数据域与指针域，指针域需要占用额外空间。 2、线性表与链表的优缺点 间复杂度仍然为O(n)。 (3) 对于插入、删除运算。在顺序表中，平均时间复杂度为O(n)。在单链表中，其平均时 的，均为O(n)。 (2) 对于定位运算，基本操作是比较，顺

38、序表和单链表上的实现算法的时间复杂度都是相同 进行扫描，它时间为复杂度为O(n)。31 件是_。 5. 设有一个单链表，若结点的指针域为next，则指针p所指的结点为最后一个结点的条 _有关。 4. 在表长为 n 的顺序表中插入或删除一个元素，则需移动元素的具体个数与表长和 【填空题】 C:L D: A: B: 3. 在带头结点的单链表L中，第一个数据元素结点的指针为（） C:开始结点 D:终端结点 A:直接前趋 B:直接后继 向该结点的（ ） 2. 在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指 C:6 D:7 A:4 B:5 1. 设顺序表的表长为10，则执行

39、插入算法的元素平均移动次数约为（） 【单选题】 章节练习 32 的访问。 解析：工作指针p-next为NULL时，说明已经走到了表的尾部，这时已完成对所有结点 5. 答案：p-next=NULL 时，需要比较和移动元素的次数是n。 还与插入的位置i有关。当插入位置i=n+1时，需要比较和移动元素的次数为0；当i=1 解析：设表的长度length=n，在插入算法中，元素的移动次数不仅与顺序表的长度n有关， 4. 答案：该元素所处的位置 【填空题】 。 头结点,其他结点称为表结点。在带头结点的单链表中，第一格数据元素的的结点的指针为 解析：为了便于运算的实现，在单链表的第一个结点之前增设一个类型相

40、同的结点，称之为 3. 答案：B 含数据元素的直接后继结点 性表的一个数据元素,next部分称为指针域或链域,用于存放一个指针,该指针指向本结点所 解析：一个数据元素和一个指针组成单链表的一个结点。data部分称为数据域,用于存储线 2. 答案：B 解析：设顺序表的长度为n，插入算法的平均移动次数约为n/2。 1. 答案：B 【单选题】 答案及解析 33 2、栈的修改原则是后进先出（LastInFirstOut），因此，栈又称为后进先出线性表，简 处于栈顶位置的数据元素称为栈顶元素。 允许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。 栈（Stack）是运算受限的

41、线性表，这种线性表上的插入和删除运算限定在表的某一端进行。 1、概念 一、栈的基本概念 第一节 栈 数组类型是许多程序设计语言的基本类型。常用的有一维数组和二维数组。 集，它们是运算受限的线性表。栈和队列是计算机科学中使用得较为广泛的两种结构。 栈和队列可看作是特殊的线性表。它们的特殊性表现在它们的基本运算是线性表运算的子 第零节 队列和数组 第三章 队列和数组 34 top为标志榜顶位置的变量，常用整型表示，范围为0(maxsize-1)。 datamaxsize为存储栈中数据元素的数组。 maxsize为顺序栈的容量。 将上述定义存放到Seqstack.h中。 SeqStk; inttop

42、; /标志栈顶位置的变量 DataTypedatamaxsize; /存储栈中数据元素的数组 typedefstructseqstack constintmaxsize=6; /顺序桟的容量 2、顺序栈用类C语言定义如下： 顺序存储。 底。栈的顺序实现称为顺序栈。通常用一个一维数组和一个记录栈顶位置的变量来实现栈的 1、桟的顺序存储结构是用一组连续的存储单元依次存放桟中的每个元素，并用始端作为栈 二、栈的顺序实现 (5) 取栈顶GetTop(S)：返回栈顶元素。 (4) 出栈Pop(S)：删除栈顶元素； (3) 进栈Push(S,x)：将元素x插入栈S中，使x成为栈S的栈顶元素； (2) 判栈

43、空EmptyStack(S)：若栈S为空栈，则结果为1，否则结果为0； (1) 初始化InitStack(S)：构造一个空栈S； 3、栈的基本运算： 称后进先出表。栈的插入和删除运算分别称为进栈和出栈。35 if(stk-top=maxsize-1) /判断找是否满 /若栈未满，元素x进栈stk中，否则提示出错信息 intPush(SeqStk*stk,DataTypex) （3）进栈 elsereturn0; return1; if(stk-top=0) /若栈为空，则返回值1，否则返回值0 intEmptyStack(SeqStk*stk) （2）判栈空 return1; stk-top=

44、0; intInitStack(SeqStk*stk) （1）初始化 当栈中的数据元素已经填满了，如果再进行进桟操作，会发生“上溢”。 当空栈，栈顶下标值top=0，如果此时做出栈运算，则产生“下溢”。 3、栈的基本运算在顺序栈上的实现算法：36 DataTypeGetTop(SeqStk*stk) （5）取栈顶元素 return1; stk-top-; /top值减1 else /未下溢，栈顶元素出栈 return0; error(“下溢”); if(EmptyStack(stk) /判断是否下溢（栈空） intPopSeqStk*stk) （4）出栈 return1; stk-datast

45、k-top=x; /元素x进桟 stk-top+; /栈未满，top值加1 else return0; error(“栈已满”);37 向链表的头结点，首结点是栈顶结点，LS-next指向栈顶结点，尾结点为栈底结点。 1、栈的链接实现称为链栈，链栈可以用带头结点的单链表来实现，如图3-4所示。LS 指 三、栈的链接实现 top2=max-1时栈2为空桟。 注意：判断上溢为top1+1=top2。判栈空时，两个栈不同，当top1=0时栈1为空栈， “上溢”，双栈如图： 量分别为top1、top2，仅当两个栈的栈顶位置在中间相遇时（top1+1=top2）才发生 成为双栈，两个栈的栈底分别设在数组

46、两端，让两个栈彼此迎面“增长”，两个栈的栈顶变 在某些应用中，为了节省空间，让两个数据元素类型一致的栈共享一维数组空间datamax， 4、双栈 returnstk-datastk-top; /返回栈顶数据元素 else if(EmptyStack(stk)returnNULLData; /栈空，返回 NULLData /取栈顶数据元素,栈顶数据元素逋过参数返回 38 /若栈为空则返回值1，否则返回值0 intEmptyStack(LkStk*LS) （2）判栈空 栈初始化时，生成一个结点，将该结点的next域设置为NULL，如下图所示。 LS-next=NULL; /建立一个空找 LS=(L

47、kStk*)malloc(sizeof(LkStk); voidInitStack(LkStk*LS) （1）初始化 3、栈的基本运算在链栈上的实现算法如下： 将上述定义存放到Lkstack.h中。 LkStk; structnode*next; DataTypedata; typedefstructnode 2、链栈用类C语言定义如下： 容量的大小。 各结点通过链域的连接组成栈，由于每个结点空间都是动态分配产生，链栈不用预先考 虑 39 在进栈操作算法中采用前插操作，新增结点始终插入到头结点之后，如下图所示： LS-next=temp; /指向新的找顶结点 temp-next=LS-next

48、; /temp的next域指向原来的栈顶结点 temp-data=x; /新结点的data域赋值为x temp=(LkStk*)malloc(sizeof(LkStk); /temp 指向申请的新结点 LkStk*temp; voidPush(LkStk*LS,DataTypex) （3）进栈 return0; else return1; if(LS-next=NULL) 40 if(!EmptyStack(LS) DataTypeGetTop(LkStk*LS) （5）取栈顶元素 出栈操作始终是栈顶结点出栈，即删除头结点之后的结点，如下图： elsereturn0； return1; fre

49、e(temp); /释放原栈顶结点空间 LS-next=temp-next; /原栈顶的下一个结点成为新的栈顶 temp=LS-next; /temp指向栈顶结点 if(!EmptyStack(LS) /判断栈是否为空 LkStk*temp; /栈顶数据元素通过参数返回，它的直接后继成为新的栈顶 intPop(LkStk*LS) （4）出栈 41 2、用类C语言定义顺序队列类型如下： 指针。 分别指示队列首和队列尾元素的变量组成，这两个变量分别称为“队列首指针”和“队列尾 1、顺序存储实现的队列称为顺序队列，它由一个一维数组（用于存储队列中元素）及两个 二、队列的顺序实现 (5) 取队列首元素

50、GetHead(Q)：返回队列首元素的值。 (4) 出队列OutQueue(Q)：删除队列首元素； 素； (3) 入队列EnQUeUe(Q，x)：将数据元素x从队尾一端插入队列，使其成为队列的新尾元 (2) 判队列空EmptyQueue(Q)：若队列Q为空，则返回值为1，否则返回值为0； (1) 队列初始化InitQueue(Q)：设置一个空队列Q； 2、队列的基本运算： 规则是不允许插队。 的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。排队的 1、队列（Queue）是有限个同类型数据元素的线性序列，是一种先进先出(FirstInFirstOut) 一、队列的基本概