天马行空

说明对于相同的逻辑结构,采用不同的存储方式会影响其操作效率

说明对于相同的逻辑结构,采用不同的存储方式会影响其操作效率

顺序表和链表都是线性表,这是他们的共同之处(逻辑结构相同),但它们的存储方式是不同的。那就看看在顺序表和链表中运算效率是怎样产生不同的? 线性表既可以采用顺序存储方式,也可以采用链式存储方式来实现。 (1)在顺序存储方式下,在线性表中插入和删除元素,平均要移动一半的元素,事件复杂度是O(n)。 事实上,就是……

  • c/c++
  • 2019-06-25 22:07:41
  • 9 次阅读

链式存储设计时,链表结点内的存储单元地址是如何分布的?

链式存储设计时,链表结点内的存储单元地址是如何分布的?

A.一定连续B.一定不连续C.不一定连续D.部分连续,部分不连续 链式存储设计时,各个不同结点的存储空间可以不连续,但是结点内的存储单元地址则必须连续。 typedef struct LNode { int value; // value中存放结点值域,默认是int型 struct Lnode *next;//指向后继结点的指针 }LNode; // 定义单链表结点类型 上述定……

  • c/c++
  • 2019-06-23 11:20:18
  • 24 次阅读

数据结构的逻辑结构与存储结构相关问题

数据结构的逻辑结构与存储结构相关问题

下列属于逻辑结构的是? A.顺序表B.哈希表C.有序表D.单链表 (1)ABD中的这三种数据结构既描述了逻辑结构,同时也描述了存储结构(物理结构),以及数据的运算。因此,这三种不是纯粹的逻辑结构。 (2)C中的选项有序表是一种纯粹的逻辑结构。有序表是指关键字有序的线性表,它只描述了这些关键字或者说元素之间的逻辑关系,只……

  • c/c++
  • 2019-06-22 18:59:25
  • 34 次阅读

树和森林的遍历相关总结

树和森林的遍历相关总结

树和森林都有两种遍历方法,分别为先序遍历和后序遍历。但对于森林的后序遍历,有的教材叫中序遍历,其实它们是同一种遍历方法,只是叫法不同。而二叉树的遍历方式有先序遍历,中序遍历,后序遍历和层次遍历。树或森林转化为二叉树后,树或森林的先序遍历对应二叉树的先序遍历,树或森林的后序遍历对应二叉树的中序遍历。……

字符串模式匹配之KMP改进算法

字符串模式匹配之KMP改进算法

串是字符串的简称,是计算机中常见且重要的数据结构。串 (string)是由零个或多个字符组成的有限连续序列。串中字符的个数称为串的长度,含有零个元素的串叫空串。空格串不是空串,而是由一个或多个空格组成的串。空格串也是字符集合的一个元素。 串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。串的……

链式队列的插入和删除操作

链式队列的插入和删除操作

链式队列就是采用链式存储结构存储队列,其采用单链表来实现。一个链队列需要两个分别指向队头和队尾的指针(front和rear)。在什么情况下使用链式队列和顺序队列呢?当一个应用程序同时使用多个队列时,采用链式队列比较好,而当只有一个队列时,使用顺序队列比较好。插入和删除元素即为链式队列的主要操作对象。 ①链式……

循环队列进队与出队算法

循环队列进队与出队算法

队列是插入位置和删除位置受限制的线性表,它只能在一端进行插入,而另一端进行删除元素,其只允许插入的一端称为队尾,只允许删除的一端称为队首。 由于队列中的元素在插入与删除时,两端的都要变化,所以需要两个指针,一个是front指向队首元素,另一个是rear指向队尾的下一个地址。有的课本上是front指针指向前一个地……

链式栈的插入与删除算法

链式栈的插入与删除算法

链式栈在设计时要注意的问题是判断栈是否为空,链栈不存在栈满的情况(假定内存无限大的情况不存在)。现在要求设计一个用不带头结点的单链表存储栈,将一个新结点插入到栈顶中,然后将其删除的算法。具体算法内容如下: ①链式栈插入(push)参考图: ②链式栈插入(push)代码: void push(LNode *&lst,int x) { LNode *p;……

顺序栈的进栈与出栈操作

顺序栈的进栈与出栈操作

栈是一种线性的逻辑结构,是一种稍加限制的只能在一端进行插入或删除操作的线性表。栈由栈顶和栈底组成,其栈顶进行插入和删除操作。 栈具有后进先出的特点,比如在生活中,我们用浏览器上网时一连窜点击了好几个链接,这个时候想回到前一页,点击后退按钮就能实现了,这就运用了栈的特点。 栈按存储结构(物理结构)分为……

单链表元素结点插入的重要环节

单链表元素结点插入的重要环节

单链表结点的插入过程,可以理解为元素结点指针的链接过程,即改变结点指针域的地址而改变指针指向。虽然单链表结点整个插入过程很简单,但重点是体会结点链接思想,从而感觉到学习单链表也能找到很多的乐趣。 单链表结点插入图解如下所示: 上图简单概括为:将p指针当前所指结点指针域中的地址赋值给s指针所指结点指针……

头插法建立带头结点的单链表

头插法建立带头结点的单链表

单链表的删除和插入操作是线性表中比较重要一部分,而这些操作又是线性表中的难点,同时也是考试的重点。对于初学者来说,在看一些算法描述时往往读起来很费劲,为此我们可以做一些图解,方便加深理解。下面是头插法建立带头结点单链表的图解及算法。 ①头插法单链表图解如下: ②头插法单链表算法如下: void insertFront……

堆排序步骤+算法

堆排序步骤+算法

堆可以看作一棵完全二叉树,利用一维数组将数据元素按照完全二叉树的形式,从上到下,从左到右,依次存放。若任何一个双亲结点值都比其左右孩子的值大,则称为大顶堆;反之称为小顶推。 堆排序基本思想是:将待排序的序列构造成一个大顶堆(或小顶堆)。此时,整个序列的最大值就是堆顶的根结点。然后将其与堆数组的末尾……