以图明志

数据结构

[专题] 结构之美:获取单链表倒数第N个结点值

距离——标尺的方法
这是一个比较常见的面试算法题:一次遍历找链表倒数第n个节点。不管是顺数n个还是倒数n个,其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量,我们能够判断倒数第一个节点,因为他的next==NULL。如果我们用两个指针,并保持他们的距离为n,那么当这个线段的右端指向末尾节点时,左端节点就指向倒数第n个节点。

数据结构

[专题] 结构之美:判断单链表中是否有环

两种判定方法介绍
有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过6之后,会重新回到3,那么我们可以在遍历时使用两个指针,看两个指针是否相等。方法一:使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。

数据结构

[专题] 结构之美:单链表逆序

让单链表逆序输出
题目:已知单向链表的头结点head,写一个函数把这个链表逆序 (Intel)。这个题目算是考察数据结构的最基础的题目了,下面我们一步步解析这个算法步骤。首先我们创建一个新结点 current p1,并且让它指向首元结点,即 current p1 = L -> next;然后我们创建另外一个新结点 pnext p2,用来保存当前节点的下一个节点,即 pnext p2 = current p1 -> next;

数据结构

《编程之美》3.4:没有头结点的单链表如何删除结点

一个巧妙的思路
题目:假设有一个没有头结点的单链表。一个指针指向此单链表中间的一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表中删除。典型的“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点的前面节点的指针,但是由于单链表中没有头结点,所以无法追溯到该节点前面的那个节点,因此,这里采用了“移花接木”的方法。

数据结构

[专题] 结构之美:删除单链表指定位置的数据

单链表删除结点
删除单链表指定的某个结点是单链表的一个基本操作。删除操作大致分为如下三种:删除p所指向结点的后继结点(假设存在),删除p所指向的结点。删除线性表中值为x的数据元素。大致算法思想:删除运算是将表的第i个结点删去。删除结点算法的时间复杂度和插入结点一样,也是O(n)。链表上实现的插入和删除运算,无须移动结点,仅需修改指针。

数据结构

[专题] 结构之美:在单链表指定位置插入数据

单链表插入结点
在单链表指定位置插入数据是单链表的常用操作之一。插入操作大致分为如下三种:在已知P指针所指向的结点后插入一个元素x。在p指针所指向的结点前插入一个元素x。在线性表中值为y的元素插入一个值为x的数据元素。大致算法思想:插入运算是将值为x的新结点插入到表的第i个结点的位置上,即插入到ai-1与ai之间。

C/C++编程语言

typedef与define在用法上的区别

typedef是为类型取了个“别名”
简单来讲:#define只是简单的进行了替换,而typedef则是为类型取了个“别名”。 #define是预处理指令,在编译预处理时进行简单的替换,不作正确性检查,不关含义是否正确照样带入,只有在编译已被展开的源程序时才会发现可能的错误并报错。如果你把#define语句中的数字9 写成字母g 预处理也照样带入。

数据结构

[专题] 结构之美:查找单链表指定位置结点的数据

获取指定结点的数据
查找单链表上指定节点的数据是单链表的一个基本编程要求。假设我们需要查找第i个节点的值,我们可以声明一个节点p,并且让它指向链表的首元节点,同时开始循环。只要循环数j小于i,就让p指向下一个节点。当j=i时跳出循环,这个时候p就到达了我们需要查找的那个节点,p->data就是我们所需要的结果。

数据结构

怎样才算是掌握单链表呢?

单链表的一些基本操作与思路
很多人学习单链表的时候,觉得学得不够深刻,不知道该深入到哪个程度。这里就罗列一下,学了单链表之后至少需要会写的一些对单链表的一些操作。只是简单罗列下,如果你有建议可以补充。首先要声明一个结构体,包含两部分:一是数据域,就是存放数据的。另一个是指针域,指向下一个节点的指针。

数据结构

[专题] 结构之美:单链表的销毁删除

将结点循环free掉
当我们不再使用某个单链表时,我们就要把它销毁,就是要把它在内存中释放掉。单链表的整表删除,先写一些算法思路:声明一节点p和q;将第一个结点赋值给p;循环,将下一结点赋值给q,释放p,将q赋值给p。实现代码如下:……初始条件:顺序线性表L已存在。操作结果:将L重置为空表。

数据结构

[专题] 结构之美:使用尾插法创建单链表

单链表整表创建
头插法建立链表虽然算法简单,但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致,可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针real,使其始终指向当前链表的尾结点。尾插法从字面意思可以理解为在表的最后插入结点。从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。

数据结构

[专题] 结构之美:使用头插法创建单链表

单链表整表创建
一般有两种常用的方法来建立单链表:头插法与尾插法。头插法从一个空表开始,读取数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。比如学校食堂吃饭排了一大队人,你一上来就插到头一个,那么打饭师傅面对的NEXT就是你了,你的下一个就是原来的队头,队头的上一个就是你。

数据结构

单链表的基础知识问与答

从问答中理解单链表的特性
简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现?若用结点表示某个数据元素,则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表示。

数据结构

带头结点的单链表的12个基本操作

熟悉带头结点的单链表
前面说了带头结点与不带头结点这两种单链表的一些情况,同时我们知道设置了头结点的单链表可以降低程序复杂性与减少BUG出现率,那么接下来我们来探讨一下关于带头结点的单链表的一些基本操作,这很重要。线性表的单链表存储结构定义如下:……以下是带有头结点的单链表的12个基本操作:……

数据结构

带头结点与不带头结点的单链表初始化

带头结点与不带头结点
不带头结点的单链表对于第一个节点的操作与其他节点不一样,需要特殊处理,这增加了程序的复杂性和出现bug的机会,因此,通常在单链表的开始结点之前附设一个头结点。带头结点的单链表,初始时一定返回的是指向头结点的地址,所以一定要用二维指针,否则将导致内存访问失败或异常。

数据结构

[专题] 结构之美:单链表的头结点与头指针

理解单链表的两个重要概念
当链表的每个结点只包含一个指针域时,我们称此链表为单链表。关于单链表的存取,有时候我们在单链表的第一个结点(有效元素)之前附设一个结点,称之为头结点;指向头结点的指针,称之为头指针;对单链表的存取必须从头指针开始进行,由于单链表的最后一个数据元素没有直接后继,则指针为NULL。
136 / 140 首页 < Prev 134 135 136 137 138 Next > 尾页 页码: