以图明志

数据结构

[专题] 单链表建环,无环链表变有环

设计一个链表建环函数
我们能否给一个无环链表建环呢?其实貌似也不很难,只要找到最后一个结点 tail,让它指向环的入口就行。所以问题分解为:找到环入口点 cur,把最后的指针 tail 指向 cur即可。首先找到环入口,也就是参数 num。定义工作指针 LinkList cur = *L; 让它遍历到 num 的位置。这个时候让第二个工作指针 tail 接替 cur 遍历到末尾。

数据结构

[专题] 单链表反转/逆序的第三种方法

建立一个新表来拷贝每个元素
昨天介绍了单链表逆序的两种方法,后来我又想到了第三种。我们就是要深入地研究每个细节嘛。这个方法比较简单,这里就直接上函数了。重新建立一个单链表newList,每次将list中的第一个结点放到newList后面。注释比较详细,所以就不具体说了。

数据结构

[专题] 用尾插法实现单链表整表创建

与头插法的区别
昨天我们谈到了头插法,可事实上,我们还是可以不这样干,为什么不把新结点都放到最后呢,这才是排队时的正常思维,所谓的先来后到。我们把每次新结点都插在终端结点的后面,这种算法称之为尾插法。与头插法区别下?*L 是头结点,r这里的角色是尾结点,一开始他们是重合的。

数据结构

[专题] 用头插法实现单链表整表创建

头插法其实就是从表头开始的插入操作
不知道有没有注意到,前面我们在谈“单链表插入操作”的时候,其实我们是用插入操作来完成了单链表的整表创建的。那么创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。其实就是将 p->next 指向结点 (*L)->next,然后再将 结点 (*L)的后继指向p,这个很好理解。

数据结构

[专题] 查找某数在单链表中的位置

单链表的元素查找
这里也同样需要用到“工作指针”。首先声明一个工作指针,并让它指向链表的首元结点 LinkList p=L->next。参数 L 其实就是头指针,L->next 就是头结点。然后用工作指针遍历链表,当 p->data 与传入的查找数 e 相等,返回其位置即可。

数据结构

[专题] 单链表的删除某个元素的操作

详尽介绍单链表删除算法
单链表删除第i个数据结点的算法思路:声明一结点p指向链表第一个结点,初始化j从1开始;当j < i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加 1;若到链表末尾p为空,则说明第i个元素不存在;否则査找成功,将欲删除的结点p->next賦值给q;单链表的删除标准语句p->next=q->next;

数据结构

[专题] 单链表的插入与遍历操作

详细讲解单链表的插入过程
昨天我们说了,单链表如何进行初始化操作。初始化之后,我们就创建了一个单链表了,接下来,我们要往这个链表里填充数据,也就是常说的,插入操作。先把结点s的指针next指向ai+1,即 s->next = p->next. 然后再把ai的指针next指向s,即 p->next = s.

数据结构

[专题] 单链表的初始化

初始化函数的设计
初始化一个链表需要做什么事情呢?头指针是必须要有的,头结点为了规范化操作,最好也得有。那么第一步就是:创建一个头结点,并且让头指针指向这个头结点。其实头指针也有了。参数 *L 传入的 L其实就是链表的首地址,也就是头指针。接下来也就是在内存开辟一个区域来作为头结点。

数据结构

[专题] 线性表链式存储结构的由来与基本概念

开始学习链表
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置。以前在顺序结构中,每个数据元素只需要存数据元素信息就可以了。现在链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。

数据结构

用单循环链表来玩一下约瑟夫环游戏

单循环链表的练习
一群小孩围成一圈,每个小孩都会带有一个随机的密码。然后设定一个数m,从第一个小孩数起,数到第m个的时候,该小孩离开。小孩离开时,其携带的密码将更新这个m值,顺序往下数的第m个小孩会继续出列。依次这样数下去,最后一个小孩是胜利者,问:胜利者是第几个小孩?

数据结构

单链表排序之选择排序

通过这个理解单链表的排序方法
单链表排序是单链表的常见编程任务之一,也是面试中经常出现的题目。单链表排序的关键是交换算法,需要额外考虑。选择排序是比较直观的排序算法之一,这里就使用选择排序实现单链表的排序。如果需要对选择排序复习一下,传送门:算法导论:选择排序的原理与实现。

数据结构

面试题:如何删除单链表的重复结点

使用三个结点完成算法
写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。解决的思路如下:建立指针p,用于遍历链表;建立指针q,q遍历p后面的结点,并与p数值比较;建立指针r,r保存需要删掉的结点,再把需要删掉的结点的前后结点相接。

数据结构

如何用PHP实现一个链表结构

数据类型的约束会不够严格
最近慢慢开始复习数据结构这一块,那么这里用PHP也写一个链表结构吧。PHP本身是弱类型的语言,数据类型的约束会不够严格。虽然下面的代码能够实现链表的基本功能,但也许会存在一些我还没注意到的缺陷。如果你有更好的方案,也可以告诉我~

数据结构

常用于面试的链表操作算法

比较有趣的链表操作
链表操作在面试中会经常出现,下面列举的链表操作方法是比较典型的。问题1:输入一个单向链表,输出该链表中倒数第k个结点。一个单向链表无法像数组一样可以直接索引,那么要找到链表的倒数第K个节点该怎么操作呢,其实思路非常简单,我们只需要设置两个指针p1,p2,首先p1和p2都指向链表的头部head。

数据结构

JavaScript实现的一个单向链表

一个神奇的函数实现了单向链表的模拟
单向链表是一个非常常见的数据结构,下面用JavaScript实现一个单向链表,能够加深对单向链表的理解。已经基本实现了。单链表的基本功能!看下面演示。

计算机算法

时间复杂度为O(1)的删除链表结点方法

从分析与思考中找到答案
这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。
1 / 3 首页 < Prev 1 2 3 Next > 尾页 页码: