搜索

  • 《数据结构和算法-线性表》

  • 价格：免费
  • 状态：全书已完结
  • 在读人数：22
  • 热度：1429
创建者
内容简介
这是一本关于数据结构与算法的的书，更准确的说是一本关于线性表的数据结构与算法的小册子。我想这本书的出现，对于那些想要学习数据结构与算法的小伙伴是一个不错的消息。如果你喜欢本书，那就赶紧加入书架吧。
章节目录
  • 绪论
  • 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。数据结构包括三个方面的内容，数据的逻辑结构，数据的存储结构和数据的运算。数据的逻辑结构和存储（物理）结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。一.数据结构的三要素 1.1数据的逻辑结构 数据的逻辑结构是指数据元素之
  • 第一章 线性表
  • 1.1线性表的定义
  • 在绪论中，我们了解到数据结构主要由三部分组成——数据的逻辑结构；数据的存储（物理）结构；数据的运算。如下图所示：这章我们开始讲解数据的逻辑结构中线性结构的第一个部分——一般线性表。一.线性表的定义 线性表是具有相同数据类型的n(n≥0)个数据元素
  • 1.2 线性表的顺序表示
  • 一.顺序表的定义 线性表的顺序存储有称之为顺序表。它是用一组地址连续的存储单元，依次存储线性表的数据元素，从而使得逻辑上相邻的两个元素在物理上也相邻。第一个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的时第i+1个元素。 因此，顺序表的特点时表中元素的逻辑顺序与物理顺序相同。 这里，我们假定元素类型为
  • 1.2.1 练习题：删除最小值的实现
  • 问题描述 从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删元素的值。空出的位置由最有一个元素填补，若顺序表为空则显示出错信息，并退出运行。算法思想 搜索整个顺序表，查找最小值元素并记下其所在位置，搜索结束后用最后一个元素填补空出的最小值元素位置。算法描述 ElemType DelMin(SqList *L) {int i=0,k;
  • 1.2.2 练习题：逆置顺序表
  • 问题描述 设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1)。算法思想 扫描顺序表L的前半部分，并且同时与L的后半部分交换。算法描述 int Reverse(SqList *L) {ElemType temp;for(int i=0;i<L->length/2;i++){temp=L->data[i];L->data[i]=L->dat
  • 1.2.3 练习题: 删除指定元素
  • 问题描述 长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为e的数据元素算法思想1 用k记录顺序表L中不等于e的元素个数（即需要保存的元素个数），边扫描边统计k，并将不等于e的元素向前放置到k的位置上，最后修改顺序表的长度。算法描述 vo
  • 1.2.4 练习题: 有序表删除指定区间值
  • 问题描述 从有序顺序表中删除其值在定值s和t之间s<t的所有元素，如果s或t不合理或者顺序表为空，则显示出错信息并退出运行。算法思想 考虑到本题中给出的是有序顺序表，因此需要删除的元素必然是相连的整体。那么我们只需要找到值大于等于s的第一个元素，然后寻找值大于t的元素（即：即将被删除的元素的下一个元素）
  • 1.2.5 练习题：无序表删除指定区间值
  • 问题描述 从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，如果s或t不合理或者顺序表为空则显示出错信息并退出运行。算法思想 注意理解题意，本题与练习题4是不同的，练习题4中说明了该顺序表逻辑上有序，而本题中，逻
  • 1.2.6 练习题: 删除重复值
  • 问题描述 从有序表中删除所有其值重复的元素，使表中所有的元素的值均不同。算法思想 注意此题中所提到的线性表是有序顺序表，那么值相同的元素一定在连续的位置上，既然这样，那么我们可以使用类似与练习题5的方法。对顺序表进行一次遍历，
  • 1.2.7 练习题: 顺序表的归并
  • 问题描述 将两个有序的顺序表合并成一个新的有序顺序表，由函数返回结果顺序表算法思想 本题实际就是归并排序的一种特殊情况，因为两个顺序表皆有序，这样我们只需要不断的取下两个顺序表中表头元素较小的那个数，然后将其存入新的顺序表，最后看哪个表还有剩余，将剩下的部分直接添加到新的顺序
  • 1.2.8 练习题: 顺序表循环移位
  • 问题描述 **描述1：**已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn),试编写一个函数，将数组中两个顺序表互换，即将(b1,b2,b
  • 1.2.9 练习题：查找指定值
  • 问题描述 线性表(a1,a2,a3,...,an)中元素递增有序，且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数据值为x的元素；若找到，将其与后继元素位置交换；若找不到将其插入到表中，使表中的元素仍递增有序算法思想 本题递增有序，为了在最少的事件内完成指定数据x的查找，那
  • 1.2.10 练习题：查找中位数
  • 问题描述 一个长度为L(L ≥1) 的升序序列S，处在第 ⌜ L/2 ⌝ 个位置的数称为S的中位数。例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15； 两个序列的中位数是含它们所有元素所组成的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11。 现在有两个等长升序序列A和B，试设计一个在时间和空间都尽可能高效的算法，找出两个序列
  • 1.3.1 线性表的链式表示(1)
  • 由于顺序表的插入，删除操作需要移动大量的元素，影响了运算效率，由此线性表的链式存储便应运而生。链式存储线性表时，逻辑上连续的元素物理结构上不需要连续，它们彼此可以通过“链”建立起数据元素之间的逻辑关系，因此对于线性表的插入，删除操作并不需要移动元素，只需修改指针即可。一.单
  • 1.3.2 线性表的链式表示(2)
  • 单链表中只有一个指向其后继结点的指针，使得单链表只能从前向后依次遍历，若要访问某个结点的前驱结点（或插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，而访问前驱结点时，其事件复杂度为O(n)。 为了克服单链表的上述缺点，引入了双链表。一.双链表的定义 在双链表中引入了两个指针，分别为指向前驱结点的指针prior和指向后继结点的指针
  • 1.3.3 线性表的链式表示(3)
  • 一.循环链表 当使用单链表进行遍历的时候，我们只能从头结点开始，尾结点结束，如果需要查看指针所指向结点的前面结点，我们又必须从头结点开始遍历。为了解决这个问题，我们便引入了双链表，使其能够双向遍历，但是它又引
  • 1.3.4 练习题1 递归删除指定结点
  • 问题描述 设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点。算法思想 因为题目要求使用递归的方式删除指定结点，那么我们可以先列出递归的基本模型：指针p指向要删除的结点，指针q则为要删除结点的后继结点。递归出口：if(p==NULL){return;} 递归主体：if(p-&g
  • 1.3.4 练习题2 非递归删除指定结点
  • 问题描述 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法实现以上的操作算法思想 使用指针p指向数据域为x的结点，使用指针pre指向指针p所指结点的前驱结点，从前向后进行遍历。如果指针p指向的结点的数据域为x，则删除，如果指针p指向的结点的数据域不为x，继续向后遍历即可。算法描述 void DelNodeX(LNode *head, Ele
  • 1.3.4 练习题3 删除最小值结点
  • 问题描述 试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）算法思想 在链表中删除最小值的前提是必须找到最小值元素是哪个结点，因此设置指针p对所有结点进行遍历，使用指针min指向最小值结点。但是因为涉及到删除操作，明显在只有指针min和指针p的条件下删除操作是极为不方便的。若单纯的删除指针p指向
  • 1.3.4 练习题4 删除指定区间结点
  • 问题描述 设一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有其值在给定值s与t之间（包含s和t，要求s<t）的所有结点算法思想 因为链表逻辑上无序，删除指定区间结点的前提是找到这些指定区间结点。因此从头节点开始对整个链表进行一次
  • 1.3.4 练习题5 删除重复结点
  • 问题描述 在一个递增有序的单链表中，有数据相同的结点存在。试设计一个算法，删除数值相同的结点，使表中不再有重复的结点。 例如（7,10,10,21,30,42,42,42,51,70）将变作（7,10,21,30,42,51,70）算法思想 考虑到本题中的单链表逻辑上有序，因此若存在数据域相同的结点那么它们必定是连
  • 1.3.4 练习题6 反向输出
  • 问题描述 设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值算法思想 如果此题是不带头结点的单链表时，使用递归是最简单的方式。但是因为拥有头结点，因此如果继续使用递归会将头节点输出，而头结点本身并不存储任何数据，因此递归必然出错。 本题中，首先将头（head）结点单独摘下，形成头结点和后继链表两个部分；采用2.1.1头插法建立单链表中头插法
  • 1.3.5 练习题7 递减输出
  • 问题描述 给定一个带表头结点的单链表，试写出算法：按递减次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）算法思想 如果本题不限制使用数组的话，最快捷的方法便是将链表中的数据复制到数组中，然后使用时间复杂度为 O(nlog2(n))的排序算法进行排序，然后
  • 1.3.6 练习题8 奇偶拆分单链表
  • 问题描述 将一个带头结点的单链表分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有元表中序号为偶数的元素，且保持其相对顺序不变。算法思想 因为本题中涉及到到按序号拆分单链表的操作，因此我们对单链表的定义进行一次修改，加入序号元素num，这样只需要对num元素判断奇偶便可。因为题目
  • 1.3.7 练习题9 查找公共结点
  • 问题描述 给定两个单链表，编写算法找出两个链表的共同结点算法思想 我们从单链表的定义中可以发现每一个结点只有一个next域，那么从第一个公共结点开始，后面所有的结点都应该是重合的，形状应该类似与倒Y型（“>-”）。既然如此，那么对两条单链表同时开始遍历，只要它们的指针同时指向同一个结点（即：两指针相等）时不就找到公共结点了吗？ 但在实现的时候，
  • 1.3.8 练习题10 查找指定倒数结点
  • 问题描述 已知一个带有头结点的单链表，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点。若查找成功，算法输出该结点的data域的值算法思想 倒数第k个位置，很容易想到的算法便是遍历整条单链表，得出单链表的长度len，然后再遍历(l
  • 1.3.9 练习题11 就地逆置单链表
  • 问题描述 试编写在带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)算法思想1 将头结点摘下，然后从第一个结点开始，依次插入到头节点的后面（类似与头插法创建单链表），直到最后一个结点为止，实现了链表的逆置。如下图所示：算法描述1 void RverList(LNode *head){
  • 1.3.10 练习题12 单链表之插入排序
  • 问题描述 有一个带头结点的单链表对其排序，使之递增有序。算法思想 本题是仅仅要求完成排序，因此我们很容易的想到使用插入排序算法完成单链表的排序。 首先将单链表的头结点拆下，用指针p指向剩余的不带头结点的
  • 1.3.11 练习题13 单链表之选择排序
  • 问题描述 有一个带头结点的单链表对其排序，使之递增有序。算法思想 因为是单链表的一次排序，练习题12中采用的是插入排序的算法，同样类似，我们可以想到使用选择排序算法完成排序。选择排序一共分成两个部分，即查找最小值和将最小值结点插入合适的位置两个部分。具体算法如下
  • 1.3.12 练习题14 判断子序列
  • 问题描述 两个整数序列A=a1,a2,a3,...,am和B=b1,b2,b3,...,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。算法思想 因为此题需要判断序列B是否为序列A的子序列，即单链表B中所有连续结点的数据域的值是否在A中能够找到同样连续的一部分。 既然如此，那么我们可以从两个链表的第一个结点开始，若对应的数据相等，则后移指
  • 1.3.13 练习题15 拆分并逆序单链表
  • 问题描述 设C={a1,b1,a2,b2,...,an,bn}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1,a2,a3,...an}，B={bn,...,b2,b
  • 1.3.14 练习题16 归并并逆序单链表
  • 问题描述 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。试编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来的两个单链表结点存放归并后的单链表算法思想 分析本题可见，本题实际上就是一次有序归并排序，因此我们借鉴归并排序的思想来实习本算法。
  • 1.3.15 练习题17 使用相同值结形成新单链表
  • 问题描述 设A和B是两个单链表（带头结点），其中元素按递增有序。设计一个算法从A和B中公共元素产生单链表C，要求不破坏A，B的结点算法思想 本算法实际上和第1章第2节练习题16 归并并逆序单链表并没有太大的区别，同样对两张链表进行遍历，对于具有相同值的结点进行一次复制，然后将复制出来的新节点采用尾插法建立单链表的方式形成新的单链表。算法描述 LinkList CreatNew
  • 1.3.16 练习题18 求两个单链表的交集
  • 问题描述 已知两个链表A和B分别表示两个集合，其元素递增排列。编写函数，求A与B的交集，并存放于A链表中算法思想 本题算法实际和 第1章第2节练习题17 使用相同值结形成新单链表 并无太大区别，但是也应注意
  • 1.3.17 练习题19 判断循环双链表对称
  • 问题描述 设计一算法用于判断带头结点的循环双链表是否对称算法思想 考虑到题目要求的是循环双链表，因此设置两个指针p和q，让p从头节点开始，从前往后遍历；指针q从头节点的prior域指示的尾结点开始，从后往前遍历，直到它们指向同一结点（循环双链表的结点数为奇数）或相邻结点时循环双链表的结点数为偶数为止。 在遍历期间，如果两个指针指向的结点的数据域的值一直保持相
  • 1.3.18 练习题20 连接两个循环单链表
  • 问题描述 有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2连接到链表h1之后，要求链表后的链表仍保持循环链表的形式算法思想 因为这是两个循环单链表，仅仅只是考虑将它们连接起来形成新的循环单链表即可。 那么我们首先找到第一个循环单链表h1的尾结点，然后让其n
  • 1.3.19 练习题21 输出并删除最小值结点
  • 问题描述 设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值的最小的结点并输出，然后将该结点从中删除，直到单链表空为止，最后删除头结点算法思想 本题可以借鉴 第1章第2节练习题3 删除最小值结点 的算法来实现，但是也应该注意到本题时循环单链表，因此判断是否已经为空表的方法是he
  • 1.3.20 练习题22 按结点访问频度排序
  • 问题描述 设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有prior（前驱指针），data（数据），next（后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在连表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使
  • 1.4 线性表的比较
  • 本章主要介绍了下线性表的两种存储结构——顺序存储和链式存储，然后引入了大量的练习题来巩固这两种存储方式。 继续使用第1章线性表 中的配图来比较下顺序表和链表。一.顺序表和链表的比较 1.1存取方式 顺序表既可以顺序存取，又可以随机存取；链表只能从表头到表尾顺序存取。1.2逻辑结构与物理结构（存储方式） 顺序表中，逻辑上相邻的元素，其对应的
  • 第二章 受限的线性表
  • 在绪论中，我们介绍了数据结构三要素， 第1章中，讲解了逻辑结构分类中线性结构的第一个部分——一般线性表，这章开始讲解逻辑结构线性结构的第二个部分——受限的线性表。这里先巩固下逻辑结构的分类，如下图所示：受限线性表最简单直白的理解便是插入，删
  • 2.1 栈
  • 栈作为一种受限的线性表，同样可以划分为顺序结构存储的栈（这里简称顺序栈）和链式结构存储的栈（这里简称链栈）。一.顺序栈 1.1定义 栈的顺序存储称为顺序栈，是利用一组地址连续的存储单元存放从栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。如图所示：栈的顺序存储类型则可以描述为： typedef struct{ElemType data[MaxSize];int
  • 2.1.1 练习题1 判断栈的操作次序是否合法
  • 问题描述 假设I和O分别表示入栈和出栈操作。栈的初状和终态均为空，入栈和出栈的操作序列可表示仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。 试写一个算法完成对下列输入序列的合法性的判断。 A. IOIIOIOO B. IOOIOIIO C.III
  • 2.1.2 练习题2 判断是否中心对称
  • 问题描述 试写一算法来判断单链表的前n个字符是否中心对称。 例如xyx，xyyx都是中心对称算法思想 在第1章第2节练习题19 判断循环双链表对称中已经初次涉及到了判断链表中心对称的问题，但是因为单链表只能从前往后遍历，因此不能使用与其相同算法进行解决，那么借助栈来判断单链表中的数据是否中心对称。将单链表的前一半
  • 2.2 队列
  • 关于队列的基本定义已经在第2章栈和队列以及串中说到了，与栈类似，同样有使用顺序结构存储的队列（这里简称顺序队列）和链式结构存储的队列（ 这里简称链队列）。一. 顺序队列 1.1定义 队列的顺序实现是指分配一块连续的存储单元用于存放队列中的元素，并附设两个指针front和rear分别指
  • 2.2.1 练习题1 共享栈的基本操作
  • 问题描述 设有两个栈s1,s2都采用顺序栈方式，并且共享一个存储区[0,…,MaxSize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的方式。试设计s1,s2有关入栈和出栈的操作算法。算法思想 因为两个栈公
  • 2.2.2 练习题2 逆置队列
  • 问题描述 Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法算法思想 因为Q是一个队列，如果仅仅按照队列先进先出的特性时无法完成自身元素逆置操作的，而题目中又给出了一个可用栈，那么我们只需借助栈先进后
  • 2.2.3 练习题3 使用栈模拟队列操作
  • 问题描述 利用两个栈S1，S2来模拟一个队列，已知栈的4的运算定义如下： Push(S,x); 元素x入栈S Pop(S,x); S出栈并将出栈的值赋给x StackEmpty(S); 判断栈是否为空 StackOverflow(S); 判断栈是否满Enqueue; 将元素x入队 Dequeue
  • 2.2.4 练习题3 使用队列模拟渡口管理
  • 问题描述 汽车轮渡口，过江渡船每次能载10辆车过江。过江车分为客车和货车类，上渡船有如下规定：1).同类车先到先上船； 2).客车先于货车上渡船，其每上4辆客车，才允许放上一辆货车； 3).若等待客车不足4辆，则以货车代替； 4).若无货车等待，允许客车都上船。试设计一个算法模拟渡口管理算法思想 经过分析，发现此题实际上就是队列的基本操作，唯一的不同就是在入
  • 2.3 串
  • 关于串的基本定义已经在第2章栈和队列以及串中介绍过了，与栈和队列类似，同样存在顺序结构存储的串（这里简称顺序串）和链式结构存储的串（这里简称链串）。一.顺序串 1.1定义 串的顺序实现是指分配一块连续的存储单元用于串中的元素，并附设表示串长度的标志。 串的顺序结构存储可以描述为： typedef char ElemType; typedef
  • 2.3.1 练习题1 串的模式匹配(Basic)
  • 问题描述 设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。 通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。 模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。算法描述 本算法与第1章第2节练习题14 判断子序列 本质相同，那么运用同样的算法也可
  • 2.3.2 练习题2 串的模式匹配(KMP)
  • 问题描述 设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。算法简述 在练习题1中的算法是最简单的模式匹配算法，但是该种算法每当匹配失败时，对主串已经匹配过的字符又需要重新匹配一次，时间复杂度为O(n2)。因此这里引入了KMP算法。KMP算法与第2章第3节练习题1 串的模式匹配(Basic) 中算法最大的不同便是重新创建了一张跳转
读者评论
  • 你还没登录，点击这里
  • 本书评论
你可能对这些书也感兴趣
最近这些人在读这本书
联系我们    duidaima.com版权所有    闽ICP备12022853号-1