以图明志

数据结构

结构之美:双向循环链表的结构与定义

从图中直观认识双向链表
双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。注意:链表由头指针head惟一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来,为双(向)循环链表。

数据结构

单循环链表的初始化、创建、删除、查找与遍历

单循环链表的基本操作
循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。链表、双链表、单循环链表、双循环链表 的实现代码都差不多,区别只是在对指针域的修改。下面,是对单循环链表的实现。

数据结构

结构之美:获取单链表倒数第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;

数据结构

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

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

数据结构

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

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

数据结构

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

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

数据结构

结构之美:单链表的销毁删除

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

数据结构

结构之美:使用尾插法创建单链表

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

数据结构

结构之美:使用头插法创建单链表

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

数据结构

结构之美:单链表的头结点与头指针

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

数据结构

结构之美:单链表的初始化、创建与遍历

写一个简单的单链表
前面已经对单链表做了一些解释。链表在进行循环遍历时效率不高,但是插入和删除时优势明显。单链表实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。而向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。

数据结构

结构之美:线性表的链式存储结构——链表

链表的详细了解
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素与其直接后继数据元素 之间的逻辑关系,对数据元素来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。由这两部分信息组成一个“结点”,表示线性表中一个数据元素 。

数据结构

结构之美:线性表的查找、插入与删除操作

顺序存储结构的操作
查找线性表是最基本的操作之一,比如根据序号查找元素的值,或者根据值查找该值是否在线性表中,如果在,那么序号是几等等。分析上述插入和删除两段代码和更早的获取元素代码,我们可以发现,线性表的顺序存储结构,在存/读数据时,不管是哪个位置,时间复杂度O(1),而插入或删除时,时间复杂度都是O(n)。

数据结构

结构之美:定义一个线性表

从最简单的线性表开始讲起
在计算机中,数据并不是孤立的,而是具有一定内在联系的数据集合,这种联系就是数据结构,说明数据如何被组织在一起的。下面我们从最简单的线性表开始讲起。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。
1 / 1 首页 < Prev 1 Next > 尾页 页码: