数据结构：链表结构和例题详解 |
您所在的位置：网站首页 › 尾插法算法思想 › 数据结构：链表结构和例题详解 |
数据结构：链表结构和例题详解
|
目录链表从单链表说起头指针和头结点头指针头结点建立单链表头插法建链表尾插法建链表结点的插入与删除插入新结点删除结点链表实现线性表基本操作初始化链表销毁链表判断是否为空表获取表长链表逆置有序表插入操作有序表归并链表的优缺点分析优点缺点浅谈顺序表和链表的选择循环链表从约瑟夫的故事说起指向头结点头结点与尾指针初始化循环表用尾指针找到头结点合并两个循环表应用解决约瑟夫问题问题解析代码实现双向链表反向遍历链表前驱指针域插入与删除操作插入操作删除操作静态链表SkipList(跳跃表)例题解析jmu-ds-链表分割题干题目分析代码实现jmu-ds-链表倒数第m个数题干题目解析代码实现《剑指 Offer》题 6：从尾到头打印链表《剑指 Offer》题 22：链表中倒数第 k 个结点《剑指 Offer》题 24：反转链表《剑指 Offer》题 25：合并两个排序的链表参考资料
插入、删除操作对于顺序表来说，时间复杂度是较大的，当我们需要一张不断在发生变化的线性表时，顺序表就显得很不合适。这是因为在我们定义一个数组的时候，元素之间的逻辑关系是不需要另附代码描述，这就导致了要修改元素的次序就变得不那么容易。而数组在存储方面，各个元素的存储位置是一个连续的空间，这就导致了我们如果想要插入元素时，需要插入的位置是没有多余的空间来插入的，所以我们只好通过移动其他元素来腾出空间。
首先是存储空间的问题，我们希望我要存储多少数据，就申请多少空间，这种申请是动态的，第二是各个元素之间的逻辑描述，我们希望这种逻辑描述是可变的，以便于我们能直接添加或删除元素，而不是牵一发而动全身。综合这两种思考，我们引入了线性表链式存储结构。
链表
线性表的链式存储结构，是利用一组任意的存储单元存储线性表的数据元素，这些存储单元可以是非连续的，因此它们可以存在于内存的不同且可用的地方。由于这些元素的位置不连续，因此为了使一个元素能够在逻辑上找到下一个元素，我们需要额外设置变量来描述这个关系。在C/C++中我们有指针可以来实现，通过指针来连接逻辑上连续的结点，因此每个结点的存储位置不一定需要连续。每个存储结点都配备数据域和指针域，数据域用于存储数据，指针域用于存放一个指向下一个元素的指针，使得各个元素之间在逻辑上成为一个表结构，这样可以通过一个结点的指针域方便地找到后继结点的位置。每个结点有一个或多个这样的指针域，有多个指针域时，就可以描述更复杂的逻辑结构，若一个结点中的某个指针域不需要指向其他任何结点，则需要将它的值置为空，用常量NULL表示。
在单链表中．由于每个结点只包含有一个指向后继结点的指针，因此当访问过一个结点后，只能接着访问它的后继结点。
链表的第一个结点的存储位置成为头指针，链表的读取从头指针开始。头指针顾名思义是起到表头的作用，通常头指针的名称就是一个链表的名称，由于其重要的地位，它不能为 NULL。 头结点为了操作更方便，我们一般会给链表设置一个头结点。头结点放在线性表第一个元素的前面，指针域指向该元素，头结点的数据域可以是无意义的，也可以做一些其他操作，例如存储表长。通过头结点，我们对表的第一个元素的插入删除结点变得容易，但是头结点并非必要元素，当头结点存在时，指向头结点的指针为头指针。下文所建立的链表都是带头结点的链表。
头插法建立的链表，表中元素顺序与输入时相反，新结点插入位置是表头。
尾插法建立的链表与数据的输入次序相同，建立链表时，新结点被插入链表的表尾上，此时需要一个尾指针用于指向表尾。
要在位置i插入一个新结点，我们需要先找到第i-1个结点的位置，这就需要从头结点遍历到第i-1个结点的位置，然后申请一个新结点，令新结点的后继为原来第i-1个结点的后继，令第i-1个结点的后继为新结点。 s = new LNode; s->next = pre->next pre->next = s;完整代码,将X插入在位置P指向的结点之前，返回true。如果参数P指向非法位置，则返回false： bool Insert(List L, ElementType X, Position P) { List head = L, ptr; ptr = new LNode; ptr->Data = X; while (L != NULL) { if (L->Next == P) { ptr->Next = L->Next; //将新结点的后继连接到后续结点 L->Next = ptr; //插入新结点 return true; } L = L->Next; //移动结点直到i-1位置 } return false; }需要注意的是，上述操作的顺序不能对调，否则原链表的逻辑关系会被切断,后续的元素无法被连接。
删除第i个结点时，我们同样需要找到第i-1个结点，再删除其后的结点。删除操作时，我们需要先拷贝一份被删除的结点，然后修改第i-1个结点的指针域，使其指向下一个结点的后继。删除操作之后，我们需要把被删除的结点的空间释放掉，以免出现内存碎片。 ptr = pre->next; pre->next = pre->next->next; delete ptr;完整代码，将位置P的元素删除并返回true。若参数P指向非法位置，则返回false： bool Delete(List L, Position P) { List head = L, ptr; while (L->Next != NULL) { if (L->Next == P) { ptr = L->Next; //拷贝要删除的结点 L->Next = L->Next->Next; //连接后续结点 delete ptr; //释放空间 return true; } L = L->Next; //移动结点直到P位置之前 } return false; }
初始化链表是，只需要建立一个头结点即可。 List MakeEmpty() { List head; head = new LNode; //为头结点申请空间 head->Next = NULL; //头结点的后继初始化为NULL return head; } 销毁链表销毁链表本质上是重复的删除结点操作，从头结点开始依次将每个结点的空间释放。 void DestroyList(LinkList &L) { LinkList ptr = L; while (L != NULL) //遍历单链表 { ptr = L; //拷贝结点 L = L->next; delete ptr; //释放单个结点的空间 } } 判断是否为空表若线性表L没有后继结点，返回true,否则返回false。 bool ListEmpty(LinkList *L) { return (L->next == NULL); } 获取表长遍历链表直到表尾，返回结点个数。 int Length(LinkList L) { int length = 0; while (L->next != NULL) { length++; L = L->next; } return length; } 链表逆置有一个带头结点的单链表 L，设计一个算法将其逆置，要求不能建立新的结点，只能利用表中已有的结点重新组合。考虑使用头插法建链表，头插法完成后表中的元素顺序和原属租的顺序相反。所以可以将头结点作为新表的头结点，然后用头插法依次插入各个数据元素。 void reversel(LNode *L) { LNode *p = L->next, *q; L->next = NULL; // 将 L 作为新表的头结点 while(p != NULL) { q = p->next; // 暂时保持后续结点的信息 p->next = L->next; // 头插法 L->next = p; p = q; } } 有序表顾名思义，就是有序的线性表，表中的所有元素都以递增或递减的形式有序排列。它本是上还是线性表，因此对于线性表的所有操作都可以应用于有序表，我们需要关注的是有序表的插入操作以及归并操作。有序表是线性表的一个基础的应用，同时我们也可以通过这种应用去体会顺序表和链表的特点与不同之处。下列代码是在元素顺序为升序的有序表中的操作。 插入操作执行插入操作时，我们并不关注元素 e 插入的位置，需要关注的是我要怎么操作才能保证操作结束后，L 仍然是个有序表。 void ListInsert(List &L,ElemType e) { List *pre = L, *ptr; while(pre->next != NULL && e > pre->next->data) { pre = pre->next; //找到插入位置的前驱结点 } ptr = new LNode; //申请空间作为新结点 ptr->data = e; ptr->next = pre->next; //插入操作 pre->next = ptr; } 有序表归并
不支持随机读取，要使用链表的单个元素，必须从第一个开始遍历。 浅谈顺序表和链表的选择 若线性表需要随机提取元素，频繁查找元素，很少进行插入和删除操作时，用顺序存储结构。需要频繁插入和删除时，采用单链表结构； 若事先知道线性表大致需要多少空间，用顺序存储结构，当线性表中的元素个数需要动态变化或者不知道有需要多少空间存储时，最好用单链表结构； 顺序表和链表各有优缺点，需要结合实际的需求选择合适的结构存储。其实我们每次用链表来做事情，都觉的挺累的，因为我们建链表需要写一段代码，输出链表元素需要一段代码，获取表长、插入删除结点都需要一波操作才能实现，我们一直在为一些必要的操作投入时间。我们想到的问题，开发者也想到了，我们希望更便利于利用链式存储结构来解决问题，优化代码效率，提高代码的正确性，那么C++要怎么实现我们的愿望呢？
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。————百度百科
当我们建一条单链表的时候，头结点的后继会先被我们初始化为 NULL，无论我们使用头插法还是尾插法建链表，建好的表的最后一个结点的指针域也会是 NULL，一次表示链表的表尾。我们能不能把这个指针利用起来，实现复位到表头的操作呢？答案是显然的、我们可以将单链表的最后一个结点的指针域由 NULL 修改为指向头结点，在经过这样的操作之后，这个单链表就会形成一个环结构，这种头尾相接的单链表就是循环链表。
制作一个循环表，令我们无论从哪个结点开始遍历，都能遍历到所有的结点，不过为了让我们能够找到表头，我们还是需要头结点这个好东西，使用循环表能够是一些功能的实现变得简单。
与初始化单链表类似，不过我们得把头结点的后继指向它本身，如图所示：
代码实现： List MakeEmpty() { List head; head = new LNode; //为头结点申请空间 head->Next = head; //头结点的后继初始化为头结点 return head; } 用尾指针找到头结点在单链表中，我们的苦恼还有很多，例如我有一个已经建好的单链表，这时我要在链表的表尾添加新数据，我就必须从头结点开始遍历一遍链表，知道表尾，这么干的时间复杂度为 O(n)。当我们在写程序的时候，我们总是喜欢思考如何让算法更快，例如我有一个时间复杂度为 O(n) 的算法，我们能不能让它更快，时间复杂度降到 O(㏒n) 甚至更快呢？
在循环表中，使用尾指针让我们能够轻松地访问表尾，顾名思义，“尾指针”就是要指向表尾的。那么表头怎么办呢？别忘了，我们现在建的是循环表，那么表尾结点的后继就是头结点，表尾结点的后继的后继就是表头结点，也就是说在循环表中尾指针不仅可以指向尾结点，还可以通过尾结点达到访问头结点的目的。
合并循环链表并不是一件很复杂的事情，与合并两个单链表操作类似，先找到第一个表的尾结点，令其的后继为第二个表的表头结点。对于循环表，我们还得多做一步，将第二个表的表尾结点的后继修改为第一个表的头结点，也就是说我们得花点时间找到第二个表的尾结点，时间复杂度为 O(n)。
不过，当我们有了尾指针，合并循环表的操作将变得更为简单，而且时间复杂度为 O(1)。
问题的情景是：有 n 个人围成一圈，按顺序从1到 n 编好号，从第一个人开始报数，报到 m（next = head; //后继指针域初始化为头结点 head->prior = head； //前驱指针域初始化为头结点 return head; }
根据我们一开始提出的思想：复杂的操作是由基本操作组合而成。双向链表虽然多了一个指针域，需要额外描述结点与前驱结点的逻辑关系，但是在操作上也并不复杂，无非是在修改与后继结点的逻辑关系上再多修改与前驱结点的逻辑关系而已。需要牢记的是，我们做插入删除操作时思路要清晰，顺序不能乱。 插入操作假设需要插入新结点 ptr，插入位置是 pre 和 pre->next 两个结点之间。 ptr->prior = pre; //修改 ptr 的前驱为 pre ptr->next = pre->next; //修改 ptr 的后继为 pre->next pre->next->prior = ptr; //修改 pre->next 的前驱为 ptr pre->next = ptr; //修改 pre 的后继为 ptr
假设要删除双向链表的结点 ptr，只需要把 ptr 结点的前驱和后继安排明白即可。 ptr->prior->next = ptr->next; //修改 ptr 前驱的后继为 ptr->next ptr->next->prior = ptr->prior; //修改 ptr 后继的前驱为 ptr->prior delete ptr; //释放 ptr 的空间
左转我的另一篇博客静态链表解析及思想应用。 SkipList(跳跃表)左转我的另一篇博客SkipList (跳跃表)解析及其实现。 例题解析 jmu-ds-链表分割 题干
我们需要去理解和体会复杂的操作是有简单的操作组合而成这种思想，接着我们要去深刻体会链表的特点，链表是一个动态的结构，链表结点的插入删除操作极其方便，因此我们可以将结点从一个表中移动到另一个结点。 代码实现 void SplitList(LinkList& L, LinkList& L1, LinkList& L2) { LinkList head = L->next, ptr; L2 = new LNode; L2->next = NULL; while (head != NULL && head->next != NULL) { ptr = head->next; head->next = head->next->next; head = head->next; ptr->next = L2->next; L2->next = ptr; } L1 = L; } jmu-ds-链表倒数第m个数 题干
刚看到这道题，我们最直观的想法是，先遍历一遍链表，统计表长，然后再一次遍历链表，遍历到倒数第 n 个结点之后返回对应的数值，所以我们可以很自然地写出这样的代码。
《剑指 Offer》学习记录：题 6：从尾到头打印链表 《剑指 Offer》题 22：链表中倒数第 k 个结点《剑指 Offer》学习记录：题 22：链表中倒数第 k 个结点 《剑指 Offer》题 24：反转链表《剑指 Offer》学习记录：题 24：反转链表 《剑指 Offer》题 25：合并两个排序的链表《剑指 Offer》学习记录：题 25：合并两个排序的链表 参考资料《大话数据结构》—— 程杰 著，清华大学出版社 《数据结构教程》—— 李春葆 主编，清华大学出版社 《数据结构与算法》—— 王曙燕 主编，人民邮电出版社 线性表之顺序表与单链表的区别及优缺点 C语言中文网 |
我们来写一个单链表的结点类型 LinkList：
要归并两个有序表，相比归并两个无顺序要求的线性表要复杂一些，因为有序表需要时刻保证表中的数据是有序的。执行归并操作的时候，我们要采用动态操作的思想，同时遍历两张表，同时移动下标或指针，遇到较小的元素就归并到新表上。
写单链表归并时，我们换一种思路来，顺序表我们为了便于操作，将两个有序表的元素拷贝到新表上，而链表我们用转移的思想去实现，因为链表的元素为结点，结点的插入和删除是一件容易的事情，所以我们的想法是把 L2 中的结点依次转移到 L1 中，就不需要再申请新的空间了。
这个故事还有其他的描述，例如猴子选大王、报数问题等等，这故事也产生了一个著名的算法————约瑟夫算法。我们曾经是怎么解决这个问题的？可能是开一个一维数组，用数组的下标表示人或猴子的序号，然后开始报数操作，出局的序号对应的数组单元改成另一个值，如果遇到已经出局的下标就跳过，跑到数组的上限就复位到第一个单元上，直到剩下最后一个下标。要描述我们以前的做法还是很麻烦的，其中一个最头疼的地方就是如果报数报到了数组的上限，那我们还得敲几行代码手动复位，好麻烦啊，有没有一种结构可以在我们跑到结构的最底端时，能够帮我们轻松地回到结构的顶端呢？
但是，如果是这么搞的话，就不可避免地遍历2遍链表，第一次遍历只是为了获取表长，然后第二次访问对应结点，这两个操作很相似，但是由于我们不知道表长，本质上也就是不知道尾结点在哪里，我们只能先定位尾结点，再访问。那么，我们现在的想法是，如何在定位到尾结点的同时，就能够找到倒数第 n 个结点呢？
我们来想一个问题，如果在一个跑道上有两位运动员，这两位运动员的跑步速度始终是一样的。在起跑的时候，一位运动员先跑 10m,另一位再开始跑，由于两位运动员速度始终相同，因此他们的路程差始终是 10m。我们定义两个指针，把一个线性表抽象成跑道，两个指针抽象成运动员，我们让其中一个指针先遍历 n 个结点，之后另一个指针苏醒，两个指针同时遍历线性表，它们的步长相等。当先开始遍历的指针遍历到尾结点的时候，后开始遍历的指针所在的位置就是第 (表长-步差) 个结点，这个结点就是倒数第 n 个结点了。
在遍历同一个线性表的时候，对于两个指针的步长和步差有差异，我们把这样的两个特殊的指针成为快指针和慢指针。本题的快、慢指针的步长相同，步差为一个定值，除了本题的用法，例如快、慢指针的步差为 0，但是快指针的步长为慢指针的2倍，当快指针遍历完线性表时，慢指针所在的位置就是中位结点。灵活应用快、慢指针，我们可以巧妙地忽略一些不必要的操作，提高我们的效率。【本文地址】