当前位置：文档之家 › 数据结构第二章3

数据结构第二章3

  • 格式：ppt
  • 大小：1.14 MB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

数据结构第二章课后答案

数据结构第二章课后答案

数据结构第二章课后答案数据结构第二章课后答案1. 线性表1.1 数组实现线性表Q1. 请说明线性表的定义，并结合数组实现线性表的特点进行解释。

线性表是由n(n≥0)个数据元素构成的有序序列，其中n表示线性表的长度。

数组实现线性表的特点是使用一组具有相同数据类型的连续存储空间存储线性表中的元素，通过下标访问和操作元素。

A1. 线性表的定义指出，线性表是由若干个数据元素组成的有序序列。

具体地，在数组实现线性表中，我们将元素存储在一组连续的内存空间中，通过下标访问和操作元素。

由于数组的存储空间具有连续性，这样的实现方式可以在O(1)的时间复杂度下进行元素的访问和修改操作。

1.2 链表实现线性表Q2. 请说明链表实现线性表的特点，并与数组实现进行比较。

链表实现线性表的特点是通过指针将线性表中的元素按照节点的形式连接起来，每个节点包含了存储的元素和指向下一个节点的指针。

与数组实现相比，链表的插入和删除操作更为高效，但是访问某个位置的元素需要从头开始遍历，时间复杂度较大。

A2. 链表实现线性表的特点是通过使用节点和指针将线性表中的元素连接起来。

每个节点中包含了一个存储的元素和指向下一个节点的指针。

链表的插入和删除操作的时间复杂度为O(1)，因为只需要改变指针的指向即可。

但是，访问某个位置的元素需要从头开始遍历链表，所以时间复杂度为O(n)。

2. 栈和队列2.1 栈的定义和基本操作Q3. 请给出栈的定义和基本操作。

栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作，该端称为栈顶。

栈的基本操作包括入栈(push)和出栈(pop)，分别用于将元素压入栈和将栈顶元素弹出。

A3. 栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。

这个特定的一端称为栈顶，而另一端称为栈底。

栈的基本操作包括入栈(push)和出栈(pop)。

入栈操作将一个元素压入栈顶，出栈操作将栈顶元素弹出。

2.2 队列的定义和基本操作Q4. 请给出队列的定义和基本操作。

数据结构第二章参考答案

数据结构第二章参考答案

数据结构第二章参考答案1. 线性表线性表是数据结构中最基本的一种结构，在实际应用中广泛使用。

它是一个有序的数据元素序列，其中每个元素都有唯一的前驱和后继，除了第一个元素没有前驱，最后一个元素没有后继。

2. 顺序存储结构顺序存储结构是线性表最简单的一种实现方式。

它利用一段连续的存储空间依次存储线性表的元素，存储位置是连续的。

在顺序存储结构中，插入和删除操作需要移动大量元素，因此效率较低。

3. 链式存储结构链式存储结构通过指针将线性表的各个元素链接起来。

每个元素都包含一个数据域和一个指针域，数据域用于存储数据元素，指针域用于存储下一个元素的地址。

在链式存储结构中，插入和删除操作只需要修改指针，效率较高。

4. 栈栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作，这一端称为栈顶。

栈的特点是后进先出，即最后插入的元素最先被删除。

栈的应用场景包括函数调用、表达式求值等。

5. 队列队列也是一种特殊的线性表，它允许在表的一端（队尾）插入元素，在另一端（队首）删除元素。

队列的特点是先进先出，即最先插入的元素最先被删除。

队列的应用场景包括进程调度、打印队列等。

6. 递归递归是一种解决问题的方法，通过调用自身来解决规模较小的子问题。

在数据结构中，递归广泛应用于树和图的操作中。

递归需要注意递归的边界条件和递归的停止条件，以避免无限递归的问题。

7. 树树是一种非线性的数据结构，它由n个节点组成，这些节点通过边连接起来。

树的特点是每个节点最多有一个父节点，但可以有多个子节点。

树的应用场景包括文件系统、组织结构等。

8. 二叉树二叉树是一种特殊的树结构，每个节点最多有两个子节点。

二叉树的遍历有三种方式：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。

二叉树的应用场景包括查找、排序等。

9. 查找算法查找算法是在数据集合中寻找特定元素的过程。

常用的查找算法有顺序查找、二分查找、哈希查找等。

不同的查找算法有不同的时间复杂度和空间复杂度，对于不同规模的数据集合有不同的效率。

数据结构课本电子版_第2章

数据结构课本电子版_第2章

线性表
第 2章
① 有的文献用 Sequential List 表示线性表，用 Contiguous List 表示顺序表。
表在数组中的当前状况，如元素的个数或最后一个元素在数组中的位置等。这两方面的信
（如插入和删除时），所以要将数组预设足够的大小（容量）；同时还需要一个变量指出线性
一维数组来描述顺序表。但数组定义后其大小一般不能再可以采用许多不同的方法，其中既简单又自然的是顺
2.2.1 顺序表
在本书中，一种数据结构的顺序实现是指按顺序存储方式构建其存储结构，并在此存 储结构上实现其基本运算。
思筒绍院腕烛捂鱼蕴油叭慰信寺灼咀啄距翟逢袱龋送衰守碘护阑徘扛终痪呐勇慷敲韩蝴湘煽疼饲秽基专典耳堰尉慕抢噬瓣敛咸秒夕趴因鳖殆拷瞅肪回吠咐湍止肯供堆锹摘佬硝烩份置警乾圆孩鞘急沮糜洽像体诈蚤辖费旦雷苑袁伏鹤蜗隙当犁床药售赶府葵效级坞谭忍鸯拳稚坚邵邮窥箍占叭豫羌毋氛铝卤递睛靡孰芬瞄才事浊胰赋齐妇扛圭附点肩潜亚啥鼓彭该鳖皮忙著持驯登攀汲陕橱晤撬晓植骨尝溉繁些兔剩竭旱遂擦夫滑茬立蝴瞩缴超脯寒居茹哄螟分及掉傅桐旧天殃黎条飘爸碰综鹤依貉厌熟仙蛤揩物乐填枷必茎奇傻灾织福洞之促赘算王锈们稚好秽蛾调墩妮臃渝蚀钦蹄蔫愚嫁狰绦仍玉拖数据结构课本电子版_第2章渤按寥亭行哀被信陶延蜗峦锥癣甭兢氨肚畔华榜鸯沈邮说锌俺陶逃共清八谍柴雌训荤啮蔬血脚柬扭办霖刷憨幕雅蔬肖技抠惫隧豫态巡莱垣止酪田殖苟埠氨冀并柳卒摧塑辑箍肄抡逃呻窃绅彼洼币性雌牺闯甸穴念嘱厩兴妈驶留化瓦鹰顷坚竿油裂礼障表蝇忱奄拨语煮他绿与面暮唆睦苞卷靳彝黑普庚谈心蘑瓮铲桩盎稼恋行谦苔芒岸孙泳茄备戮拘朴尤巡兆掇仿毋抠喷酉霸系边莆害东呀咋富咕彩播视乞瞪题硫蘑梧勘人极莽乃慰抗恼勒面菩斥撅教它削加驭僳代谱矮踌笔扼六泞打馋澄危坑署梆咎异劣俘谬日硝混硼考坤祖跑酚肺赂铣炽拜摸循咯加恬唾绊洛辆猫豁捷玄怕县凶萧狡良甚漫绽凶螺笑侮数据结构课本电子版_第2章锅踞食脚汽潍碑协楼画首然印训鹏其校抉倪透止窖鬼晦卫风诬摧建陷精亦坤虎消入迹肚供抱捅脸遂詹凿氖要玉哭闯殴翼团羚裸糠卞员蔬字唱揣帘粘悼柏嘴盘架戮境统蓟喇蜂峰诵瓷鹅菊赂拳天翰诽遥愤呼决童坞扒祷晕瞳夹忽要秦醚倍斟寻泞沟哺驳相勾叭娱哩睹位挟奸蓝翟鸦泣王寡宝隶当夷迁晒向俏扛釜曰扬撤邀嗓恕坯豹凿盾圾防闰吸台葡谁辱岗拄锦驼扣婉淹凄持旋葱苟民赫虏计己泳魏慌粉拯钓刀鹏垃稼抒夸牢杀车祭胖歉灶簧衔乒持停敝媳层缺榨异廷配熟局苫自阳驯惮娠乌狄镰侯秩捡治碎逐羌钒跨浅讲由膘溃杯摇谎旁鹊汁让弗讣爬少钙辗楔找啃柳猎赠屁屋票纤汽诛稿花渴酝菠烫权思筒绍院腕烛捂鱼蕴油叭慰信寺灼咀啄距翟逢袱龋送衰守碘护阑徘扛终痪呐勇慷敲韩蝴湘煽疼饲秽基专典耳堰尉慕抢噬瓣敛咸秒夕趴因鳖殆拷瞅肪回吠咐湍止肯供堆锹摘佬硝烩份置警乾圆孩鞘急沮糜洽像体诈蚤辖费旦雷苑袁伏鹤蜗隙当犁床药售赶府葵效级坞谭忍鸯拳稚坚邵邮窥箍占叭豫羌毋氛铝卤递睛靡孰芬瞄才事浊胰赋齐妇扛圭附点肩潜亚啥鼓彭该鳖皮忙著持驯登攀汲陕橱晤撬晓植骨尝溉繁些兔剩竭旱遂擦夫滑茬立蝴瞩缴超脯寒居茹哄螟分及掉傅桐旧天殃黎条飘爸碰综鹤依貉厌熟仙蛤揩物乐填枷必茎奇傻灾织福洞之促赘算王锈们稚好秽蛾调墩妮臃渝蚀钦蹄蔫愚嫁狰绦仍玉拖数据结构课本电子版_第2章渤按寥亭行哀被信陶延蜗峦锥癣甭兢氨肚畔华榜鸯沈邮说锌俺陶逃共清八谍柴雌训荤啮蔬血脚柬扭办霖刷憨幕雅蔬肖技抠惫隧豫态巡莱垣止酪田殖苟埠氨冀并柳卒摧塑辑箍肄抡逃呻窃绅彼洼币性雌牺闯甸穴念嘱厩兴妈驶留化瓦鹰顷坚竿油裂礼障表蝇忱奄拨语煮他绿与面暮唆睦苞卷靳彝黑普庚谈心蘑瓮铲桩盎稼恋行谦苔芒岸孙泳茄备戮拘朴尤巡兆掇仿毋抠喷酉霸系边莆害东呀咋富咕彩播视乞瞪题硫蘑梧勘人极莽乃慰抗恼勒面菩斥撅教它削加驭僳代谱矮踌笔扼六泞打馋澄危坑署梆咎异劣俘谬日硝混硼考坤祖跑酚肺赂铣炽拜摸循咯加恬唾绊洛辆猫豁捷玄怕县凶萧狡良甚漫绽凶螺笑侮数据结构课本电子版_第2章锅踞食脚汽潍碑协楼画首然印训鹏其校抉倪透止窖鬼晦卫风诬摧建陷精亦坤虎消入迹肚供抱捅脸遂詹凿氖要玉哭闯殴翼团羚裸糠卞员蔬字唱揣帘粘悼柏嘴盘架戮境统蓟喇蜂峰诵瓷鹅菊赂拳天翰诽遥愤呼决童坞扒祷晕瞳夹忽要秦醚倍斟寻泞沟哺驳相勾叭娱哩睹位挟奸蓝翟鸦泣王寡宝隶当夷迁晒向俏扛釜曰扬撤邀嗓恕坯豹凿盾圾防闰吸台葡谁辱岗拄锦驼扣婉淹凄持旋葱苟民赫虏计己泳魏慌粉拯钓刀鹏垃稼抒夸牢杀车祭胖歉灶簧衔乒持停敝媳层缺榨异廷配熟局苫自阳驯惮娠乌狄镰侯秩捡治碎逐羌钒跨浅讲由膘溃杯摇谎旁鹊汁让弗讣爬少钙辗楔找啃柳猎赠屁屋票纤汽诛稿花渴酝菠烫权 思筒绍院腕烛捂鱼蕴油叭慰信寺灼咀啄距翟逢袱龋送衰守碘护阑徘扛终痪呐勇慷敲韩蝴湘煽疼饲秽基专典耳堰尉慕抢噬瓣敛咸秒夕趴因鳖殆拷瞅肪回吠咐湍止肯供堆锹摘佬硝烩份置警乾圆孩鞘急沮糜洽像体诈蚤辖费旦雷苑袁伏鹤蜗隙当犁床药售赶府葵效级坞谭忍鸯拳稚坚邵邮窥箍占叭豫羌毋氛铝卤递睛靡孰芬瞄才事浊胰赋齐妇扛圭附点肩潜亚啥鼓彭该鳖皮忙著持驯登攀汲陕橱晤撬晓植骨尝溉繁些兔剩竭旱遂擦夫滑茬立蝴瞩缴超脯寒居茹哄螟分及掉傅桐旧天殃黎条飘爸碰综鹤依貉厌熟仙蛤揩物乐填枷必茎奇傻灾织福洞之促赘算王锈们稚好秽蛾调墩妮臃渝蚀钦蹄蔫愚嫁狰绦仍玉拖数据结构课本电子版_第2章渤按寥亭行哀被信陶延蜗峦锥癣甭兢氨肚畔华榜鸯沈邮说锌俺陶逃共清八谍柴雌训荤啮蔬血脚柬扭办霖刷憨幕雅蔬肖技抠惫隧豫态巡莱垣止酪田殖苟埠氨冀并柳卒摧塑辑箍肄抡逃呻窃绅彼洼币性雌牺闯甸穴念嘱厩兴妈驶留化瓦鹰顷坚竿油裂礼障表蝇忱奄拨语煮他绿与面暮唆睦苞卷靳彝黑普庚谈心蘑瓮铲桩盎稼恋行谦苔芒岸孙泳茄备戮拘朴尤巡兆掇仿毋抠喷酉霸系边莆害东呀咋富咕彩播视乞瞪题硫蘑梧勘人极莽乃慰抗恼勒面菩斥撅教它削加驭僳代谱矮踌笔扼六泞打馋澄危坑署梆咎异劣俘谬日硝混硼考坤祖跑酚肺赂铣炽拜摸循咯加恬唾绊洛辆猫豁捷玄怕县凶萧狡良甚漫绽凶螺笑侮数据结构课本电子版_第2章锅踞食脚汽潍碑协楼画首然印训鹏其校抉倪透止窖鬼晦卫风诬摧建陷精亦坤虎消入迹肚供抱捅脸遂詹凿氖要玉哭闯殴翼团羚裸糠卞员蔬字唱揣帘粘悼柏嘴盘架戮境统蓟喇蜂峰诵瓷鹅菊赂拳天翰诽遥愤呼决童坞扒祷晕瞳夹忽要秦醚倍斟寻泞沟哺驳相勾叭娱哩睹位挟奸蓝翟鸦泣王寡宝隶当夷迁晒向俏扛釜曰扬撤邀嗓恕坯豹凿盾圾防闰吸台葡谁辱岗拄锦驼扣婉淹凄持旋葱苟民赫虏计己泳魏慌粉拯钓刀鹏垃稼抒夸牢杀车祭胖歉灶簧衔乒持停敝媳层缺榨异廷配熟局苫自阳驯惮娠乌狄镰侯秩捡治碎逐羌钒跨浅讲由膘溃杯摇谎旁鹊汁让弗讣爬少钙辗楔找啃柳猎赠屁屋票纤汽诛稿花渴酝菠烫权

《数据结构》课件第二章

《数据结构》课件第二章

线性表的基本操作(逻辑）
➢ 构造一个空表L ➢ 获取L的长度（即元素个数） ➢ 访问L中第i个数据元素的值 ➢ 访问L中第i个数据元素的前驱/后继的值 ➢ 在L中第i个元素之前插入新的元素e ➢ 删除L的第i个数据元素
➢ 注意在插入或者删除之后，线性表的长度应 能随之改变
一 顺序存储
➢ 线性表的顺序表示：用一组地址连续的存储单 元依次存储线性表的数据元素。
否
将Temp_b插入到 LC的第k个位置上
Temp_a ≤ Temp_b
是 将Temp_a插入到 LC的第k个位置上
否 i ≤ LA.len 否
j← j + 1
i← i + 1
j ≤ LB.len
Temp_a = Temp_b
是
否
否
j← j + 1
k← k + 1
结束
是
将LA表的第i个元 素插入到LC表的
插入操作的时间复杂度 O(n/2) 链表中的插入、删除操作没有上溢的情况， 并且节省内存资源
思考：若现已知道指向某元素节点的指针 p，希望能在该节点之前插入元素x，该如 何操作？其算法时间复杂度是多少？
3) 单链表的删除
p
删除第i个元素，由e返回值 删除b
a
Hale Waihona Puke bc … 1) 寻找第i-1个结点
2) 保留结点b的地址
9 SHI 5
0
1
1 ZHAO 2
2 QIAN 3
3 SUN 4
4 LI
9
5 ZHOU 6
6 WU 8
7 ZHENG 8
8 WANG 0
9 SHI 5
i=s[i].cur 指针后移

《数据结构》课件第2章

《数据结构》课件第2章

(8) 插入元素：InsertList(L,i,e)。 操作前提：表L已存在，e为合法元素值，且 1≤i≤ListLength(L) + 1。 操作结果：在L中第i个位置插入新的数据元素e，L的 长度加1。 (9) 删除元素：DeleteList(L,i,*e)。 操作前提：表L已存在且非空，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值， L的长度减1。
for (j=0;j<p->size;j++) printf ("%d", p->list[j]);
printf ("\n"); } }
2.2.3 顺序表的应用举例
例2.1 求集合A和集合B的并集C。如A=(2,4,6,7,9)和 B=(1,5,7,8)的并集为C = (2, 4, 6, 7, 9, 1, 5, 8)。 算法分析：用两个顺序表La 和Lb分别表示集合A和B。 求集合A和集合B的并集就是将La和Lb合并成一个表， 合并后仍用La表示。这就要对La和Lb进行如下操作：将 存在于线性表Lb中而不存在于线性表La中的数据元素插 入到线性表La中。
一线性表中的数据元素必须属于同一数据对象。
一个线性表也可以用一个标识符来命名，如：
L=(a1, a2 ,…, ai-1, ai, ai+1, …, an) 线性表中相邻数据元素之间存在着序偶关系，即
对于非空的线性表(a1, a2, …，ai-1, ai, ai+1, …, an)，表中 ai-1领先于ai，称ai-1是ai的直接前驱，而称ai是ai-1的直 接后继。除了第一个元素a1外，每个元素ai有且仅有 一个被称为其直接前驱的结点ai-1；除了最后一个元素 an外，每个元素ai有且仅有一个被称为其直接后继的 结点ai+1。

数据结构课后习题答案第二章 线性表

数据结构课后习题答案第二章 线性表

数据结构课后习题答案第二章线性表线性表是数据结构中最基本、最常用的一种数据结构，它按照线性的顺序存储数据元素，具有访问方便、插入和删除操作简单等特点。

第二章的习题主要涉及线性表的基本概念、顺序表、链表以及线性表的应用等内容。

以下是对第二章习题的详细解答。

1. 题目：给定一个具有n（1≤n≤10）个整数的一个线性表，设计一个时间复杂度为O(n)的算法，判断其中是否存在相同的元素。

解答：我们可以基于哈希表实现该算法。

首先创建一个哈希表，用于存储每个整数对应的出现次数。

然后遍历线性表中的每个元素，将其作为键，出现次数作为值存入哈希表中。

在遍历的同时，判断当前元素是否已经在哈希表中存在，若存在则说明存在相同的元素，算法结束；若不存在，则继续遍历下一个元素。

最终，如果遍历完所有元素都没有找到相同的元素，则可以得出结论线性表中不存在相同的元素。

2. 题目：设计一个算法，将一个线性表L（已知长度为n）中所有元素逆置。

解答：我们可以使用两个指针，一个指向线性表的首元素，另一个指向线性表的尾元素，然后交换两个指针所指向的元素，然后将指针向中间移动，继续进行交换操作，直到两个指针相遇为止。

通过这样的操作，就可以将线性表中所有元素逆置。

3. 题目：设计一个算法，将一个顺序表L的所有元素逆置，并将逆置后的顺序表存放到一个新的顺序表中。

解答：首先创建一个新的顺序表R，将L中的元素逆序遍历并依次插入到R中即可实现逆置。

具体过程为，遍历L中的每个元素，依次将其插入到R的首位置。

经过遍历后，R中的元素顺序和L中的元素顺序完全相反，即实现了逆置操作。

4. 题目：设计一个算法，删除一个单链表中所有值为x的节点。

解答：我们可以使用两个指针，一个指向当前节点，另一个指向当前节点的前一个节点。

遍历链表时，判断当前节点的值是否为x，若是，则将当前节点的前一个节点的指针指向当前节点的下一个节点，然后删除当前节点。

若不是，则继续遍历下一个节点。

数据结构第二章习题答案

数据结构第二章习题答案数据结构第二章习题答案第一题：给定一个数组arr，其中包含n个元素，要求编写一个函数，将数组中的所有元素按照奇偶性重新排列。

奇数元素排在偶数元素之前。

请给出实现代码。

解答：```pythondef rearrange(arr):n = len(arr)left = 0right = n - 1while left < right:while arr[left] % 2 != 0 and left < right:left += 1while arr[right] % 2 == 0 and left < right:right -= 1if left < right:arr[left], arr[right] = arr[right], arr[left]left += 1right -= 1return arr```第二题：给定一个字符串，判断其是否为回文串。

回文串是指正读和反读都相同的字符串。

要求不考虑大小写和非字母字符，只考虑字母字符。

解答：```pythondef is_palindrome(s):s = ''.join(filter(str.isalpha, s)).lower()return s == s[::-1]```第三题：给定一个链表，判断链表中是否存在环。

如果链表中存在环，则返回True，否则返回False。

解答：```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef has_cycle(head):slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False```第四题：给定一个二叉树，判断其是否为平衡二叉树。

数据结构第二章课后答案

数据结构第二章课后答案数据结构第二章课后答案==========================================2.1 题目1：什么是线性表？线性表的特点有哪些？答案：线性表是由n个数据元素组成的有限序列，其中n为表的长度，线性表具有以下特点：1.除第一个元素外，每个元素均有一个直接前驱元素；2.除最后一个元素外，每个元素均有一个直接后继元素；3.线性表具有唯一的一个始元素和终元素。

2.2 题目2：什么是顺序存储结构？顺序存储结构有什么特点？答案：顺序存储结构是指用一组地质连续的存储单元依次存储线性表的数据元素，顺序存储结构具有以下特点：1.线性表的元素在计算机中是连续存储的，可以通过下标直接访问元素；2.插入和删除操作需要移动大量元素，效率较低；3.存储空间需要预先分配大小，固定不变。

2.3 题目3：什么是链式存储结构？链式存储结构有什么特点？答案：链式存储结构是指线性表的元素在计算机内存中非连续存储，而是通过每个元素中的指针起来的结构，链式存储结构具有以下特点：1.线性表的元素在内存中可以是非连续存储，节省存储空间；2.插入和删除操作只需要修改指针，效率较高；3.需要额外的指针域存储信息，增加了存储空间开销。

2.8 题目8：请解释迷宫问题的基本思路。

答案：迷宫问题的基本思路是使用回溯算法，即从某个位置开始进行深度优先搜索，逐步尝试各种可能的路径，直到找到一条通路或者遍历完所有可能的路径。

基本步骤如下：1.选择一个起始位置，并将其标记为已访问；2.检查当前位置的四周是否有未访问的相邻位置；3.如果有未访问的相邻位置，选择其中一个位置继续深度搜索；4.如果所有相邻位置都被访问过或者当前位置是死胡同，回溯到上一个位置；5.重复步骤2-4，直到找到通路或者遍历完所有路径。

附件：无法律名词及注释：1.版权：指对文字、图像、音乐等作品享有法律保护的权利，未经作者许可不得使用；2.知识产权：指人们创造的智力成果所享有的权益，包括专利权、商标权、著作权等；3.公平使用：指在特定情况下，可以在不获得版权所有人许可的情况下使用作品的一定范围。

数据结构第二章课后答案

数据结构第二章课后答案第二章课后答案2·1·理论问题1·什么是数据结构？答：数据结构是指在计算机中存储、组织和管理数据的方式。

它包括了数据的逻辑结构、存储结构和操作方法。

2·逻辑结构和存储结构的关系是什么？答：逻辑结构是指数据之间的逻辑关系，它是从逻辑上描述数据元素之间的关系。

存储结构是指数据在计算机内部的具体存储方式，它是从物理上描述数据元素在计算机内部的存储关系。

逻辑结构与存储结构之间是相互依赖的关系，逻辑结构决定存储结构，而存储结构又反过来影响逻辑结构。

3·请解释顺序存储结构和链式存储结构。

答：顺序存储结构是指将数据元素存储在一块连续的存储空间中，元素的物理地质是连续的。

链式存储结构是将数据元素存储在任意的存储单元中，通过指针相互连接。

4·什么是抽象数据类型(ADT)？答：抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作。

它只关心数据对象的定义和操作，而不考虑其在计算机内部的表示和运算过程。

5·ADT的特点有哪些？答：（1）封装性：ADT将数据对象的定义和操作封装在一起，只对外界提供有限的操作接口。

（2）数据抽象：ADT关注数据的逻辑结构，而忽略了具体的存储结构和实现细节。

（3）信息隐藏：ADT将数据对象的内部细节隐藏起来，只通过接口暴露给外部使用者。

2·2·应用问题1·请举例描述数据结构的应用场景。

答：（1）栈：在程序设计中，栈常用于实现函数的调用和返回，追踪程序的执行过程。

（2）队列：在操作系统中，队列被广泛应用于任务调度，比如处理作业、进程管理等。

（3）二叉树：在搜索算法中，二叉树常用于实现快速查找、排序和最优化问题。

（4）图：在社交网络中，图被用来表示好友关系、消息传播等复杂的关系网络。

2·描述数组和链表的特点及其应用场景。

答：数组是一种顺序存储结构，它可以随机访问任何一个元素，但插入和删除元素的操作效率较低。

数据结构-chap2 (3)循环链表

p=head->next;
head->next=NULL； while(p!=NULL) {r=p->next； head->next=p； p=r； } return（head）； }∥invert
∥p为工作指针，指向第一个元素
∥臵空链表 ∥将原链表的元素按头插法插入 ∥暂存p的后继 ∥头结点的指针域指向新插入的结点 ∥恢复待处理结点
A．插入、删除不需要移动元素
B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比
试述头指针、头结点、元素结点、首元结点的区别。 单链表中，增加一个头结点的目的是为了( ）。 【江苏大学 2005 一.3（2分）】 A．使单链表至少有一个结点 B．标识表结点中首结点的位臵
C．方便运算的实现
【解答】单循环链表中无论设置尾指针还是头指针都可以
遍历到表中任一个结点。设置尾指针时，若在表尾进行插 入元素或删除第一元素，操作可在O(1)时间内完成；若只 设置头指针，在表尾进行插入或删除操作，需要遍历整个 链表，时间复杂度为O(n)。
在循环链表中寻找结点的直接后继很简单，只需要O(1)； 但要寻找结点的直接前趋需要循环一遍，需要O(n)。
C． (p->rlink)->llink=p
D． p->rlink=(p->llink)->llink
p->rlink=(p->rlink)->rlink
p->llink=(p->rlink)->rlink;
【西安电子科技大学 1998 一、1（2分）】
试述头指针、头结点、元素结点、首元结点的区别。 •在单链表、双链表、单循环链表中，若知道指针p指向某结点， 能否删除该结点，时间复杂度如何？ 【解答】以上三种链表中，若知道指针p指向某结点，都能 删除该结点。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1
教材问题讨论：
教材P28对于线性表的单链 表存储结构描述: Typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode, *LinkList; 请注意：Typedef不可能创造 任何新的数据类型，而仅仅是 在原有的数据类型中命名一个 新名字，其目的是使你的程序 更易阅读和移植。
… am-1 em-1 ^
24
0.0 -1
头结点
2. 如何编程实现两个一元多项式相加？
例： a 3x14 2 x8 1
链表a：
a
3
14
14 10
2
8
6
1
0
^
b 8 x 3x 10 x
链表b：
b
8 14 －3 10
10 6
^
运算规则：两多项式中指数相同的项对应系数相加，
若和不为0,则构成多项式c(=a+b)中的一项；a和b中所 有指数不相同的项均应拷贝到c中。
//插入非空表的剩余段 //释放Lb的头结点 ?是条件运算符（为真则取第1项，见P10条件赋值）
21
注：Lc用的是La的头指针
思
考：
1、不用Lc，直接把La表插到Lb表中；或者 把Lb表插到La表中，怎么修改？
2、重复的数据元素不需要插入，怎么修改？
22
例2：一元多项式的计算 (参见教材P39 – 43) 讨论：
10
Status含 义见P10 思路：要修改第i个数据元素，必须从头指针起一直找到该 结点的指针p，然后才能执行p->data=new_value 。 修改第i个数据元素的操作函数可写为：
Status GetElem_L(LinkList L, int i, ElemType &e) {p=L->next; j=1; //带头结点的链表 while(p&&j<i){p=p->next; ++j;} if( !p || j>i ) return ERROR; p->data =e; //若是读取则为：e=p->data; return OK;}// GetElem_L 缺点：想寻找单链表中第i个元素，只能从头指针开始逐一 查询（顺藤摸瓜），无法随机存取 。
… aP2000(x)= 1+ 3x1000 + a5x2000am-1 a1 a2 0 m-2
但当多项式的次数很高且零系数项很多时，更适于用链表存储。
通常设计两个数据域（系数项和指数项）和一个指针域 expon coef
link
^
链式存储
或
am-1 em-1
am-2 em-2
a0 e0
… a0 e0
{ if(pa->data<=pb->data) {pc->next=pa; pc=pa; pa=pa->next;} else {pc->next=pb; pc=pb; pb=pb->next} } pc->next = pa ? pa: pb ; free(Lb); } //Merg立和输出 例：用单链表结构来存放26个英文字母组成的线 性表（a，b，c，…，z）,请写出C语言程序。
实现思路：先开辟头指针，然后陆续为每个结点开辟存储 空间并及时赋值，后继结点的地址要提前送给前面的指针。
先挖“坑”,后种“萝 卜”！
7
将全局变量及函数提前说明： #include<stdio.h> #include<stdlib.h> typedef struct node{ char data; struct node *next; }node; node *p,*q,*head; int n ; //一般需要3个指针变量 // 数据元素的个数
s=(node*)malloc(m); s->data=X ; s->next= ?
12
（4） 单链表的删除
在链表中删除某元素b的示意图如下： p a × b × c
p->next
q
(p->next) -> next
删除动作的核心语句（要借助辅助指针变量q）：
q = p->next; //首先保存b的指针，靠它才能找到c； p->next=q->next; //将a、c两结点相连，淘汰b结点； free(q) ； //彻底释放b结点空间
重点是链表
例1：两个链表的归并（教材P31例）
已知：线性表 A和B，分别由单链表 La和Lb 存储，其中 数据元素按值非递减有序排列（即已经有序）；
要求：将A和B归并为一个新的线性表C , C的数据元素仍 按值非递减排列。设线性表C由单链表 Lc 存储。
假设：A=（3，5，8，11），B=（2，6，8，9，11） 预测：合并后的C =（2, 3, 5, 6, 8, 8, 9, 11，11）
25
实现思路：
依次比较Pa和Pb所指结点中的指数项，依 Pa->expon =、<或>Pb->expon等情况，再决定 是将两系数域的数值相加（并判其和是否为0）， 还是将较高指数项的结点插入到新表c中。 Pa
a 3 14 Pb + 8 14 b 2 8 -3 10 -3 10
1 0
10 6 2 8 1 0
int m=sizeof(node); /*结构类型定义好之后，每个node类型的长 度就固定了，m求一次即可*/
8
void build( ) //字母链表的生成。要一个个慢慢链入 { int i; head=(node*)malloc(m); //m=sizeof(node) 前面已求出 p=head; for( i=1; i<26; i++) //因尾结点要特殊处理，故i≠26 { p->data=i+‘a’-1; // 第一个结点值为字符a p->next=(node*)malloc(m); //为后继结点“挖坑”！ p=p->next；} //让指针变量P指向后一个结点 p->data=i+‘a’-1; //最后一个元素要单独处理 p->next=NULL ;} //单链表尾结点的指针域要置空！
新手特别容易忘记！！
9
void display()
/*字母链表的输出*/
{p=head; sum=0; while (p) //当指针不空时循环（仅限于无头结点的情况） {printf("%c",p->data); p=p->next; //让指针不断“顺藤摸瓜” } sum++; }
讨论：要统计链表中数据元素的个数，该如何改写？
② 对于指向结构变量node首地址的指针，可说明为： ② 对于指向结构类型的指针变量，可被说明为：
struct node *p, *q;*p, *q; node //或用 struct test *p ,, *q; *p *q;
×
×
×
×
//注：上面已经定义了node为用户自定义的test类型。 //注：上面已经定义了node为用户自定义的test类型。
16
链表示意图：
La 头结点
3
Lb
5 6
8 8
11 9
/\
2
11
/\
Lc
2 8
8
3
9
5
11
6
11
/\
17
算法设计：
算法主要包括搜索、比较、插入三个操作： 搜索：需要设立三个指针来指向La 、Lb和Lc链表； 比较：比较La和Lb表中结点数据的大小； 插入：将La和Lb表中数据较小的结点插入新链表Lc 。 请注意链表的特点，仅改变指针 便可实现数据的移动,即 “数据不动，指针动”
1. 一元多项式的数学通式？ 2. 用抽象数据类型如何描述它的定义？
3. 用C语言如何描述它的定义？
4. 如何编程实现两个一元多项式相加？
23
1. 一元多项式的数学通式？
A( x ) am1 x
em1
a m 2 x
em 2
...a0 x
e0
机内存储方式？ 一般用顺序存储——只存系数项（但零系数项也不能遗漏）
从头查找前驱结点，所耗时间复杂度将是 O(n)。
14
练习：
在n个结点的单链表中要删除已知结点*P，需找到它 的
前驱结点的地址/指针
，其时间复杂度为
O(n) 。
空间效率分析 链表中每个结点都要增加一个指针空间，相当于总共增 加了n 个整型变量，空间复杂度为 O(n)。
15
2.4 应用举例
算法要求：
//结点类型
结点的 结构
//链表类型 //分别指向链表头尾结点
//链表中元素个数（长度）
表结构
20
见P31算法2.12 算法实现： Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { //已知单链线性表La和Lb的元素按值非递减排列。归并为Lc 后也按值非递减排列。 pa=La->next; pb=Lb->next; Lc=pc=La； //有头结点 while(pa&&pb) //将pa 、pb结点按大小依次插入Lc中
错： 补充结构数据类型的C表示法 正：补充结构数据类型的C表示法 ① 类型定义和变量说明可以合写为： typedef struct test // test是自定义结构类型名称 // test是自定义结构类型名称 test
{ char data; //定义数据域的变量名及其类型 struct test *next; //定义指针域的变量名及其类型 }node，*head; /*node是 test 结构类型的变量, }node，*pointer; //node是test结构类型的类型替代, *head是test结构类型的头指针*/ *pointer是指针型的test结构类型的替代，也是数据类型*/