【数据结构与算法】之链表的操作和使用
【摘要】
链表的定义
链表:由一系列结点(链表中每一个元素称为结点)组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
链表这种存储方式,其元素个数是不受限定的,当...
链表的定义
- 链表:由一系列结点(链表中每一个元素称为结点)组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
- 链表这种存储方式,其元素个数是不受限定的,当进行添加元素的时候存储的个数就会随之改变。
- 链表和数组的优缺点对比:
数据形式 | 优点 | 缺点 |
---|---|---|
链表 | 运行时确定大小,快速插入和删除元素 | 不能随机访问,用户必须提供编程支持 |
数组 | C直接支持,提供随机访问 | 在编译时确定大小,插入和删除元素很费时 |
- 在链表中有一个头指针变量,这个指针变量保存一个地址,通过这个地址来找到这个链表,头指针节点指向第一个节点,在链表中每个节点包含两个部分:数据部分和指针部分。虽然结构体不能含有与本身类型相同的结构,但是可以含有之相同类型结构的指针,这种定义是链表的基础,链表中每一项都包含在何处能找到下一项的信息。而最后一个节点的指针指向必须为空NULL,从链表的原理来看不用担心链表的长度会超出范围这种问题。
- 链表的声明
typedef struct ListNode{
int val;
struct ListNode* next;
ListNode(int x) :
val(x), next(NULL){
}
};
链表的基本操作
一、创建单链表
- 创建头节点head,并且将当前结点p指向头结点(p=head);
- 创建下一个结点q,当前结点p的下一结点为q(p->next=q);
- 结点p后移一位(p = p->next);
#include <iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
struct ListNode* next;
ListNode(int x) :
val(x), next(NULL){
}
};
int main(){
int num;
cin >> num;
ListNode *head = new ListNode(num);
ListNode *p = head;
// 利用尾插法创建一个链表
while (cin >> num){
ListNode* q = new ListNode(num);
p->next = q;
p = p->next;
}
// 遍历这个链表,并输出每个结点的元素
ListNode *m = head;
while (m != nullptr){
cout << m->val << endl;
m = m->next;
}
return 0;
}
二、插入节点
- 判断原链表是否是空链表,如果是,将head指向新增结点;
- 如果不是空链表,向链表尾部插入新结点;
ListNode* insertNode(ListNode* head, int data){
ListNode *newNode = new ListNode(data);
ListNode *p = head;
if (p == nullptr){
head = newNode;
} else {
while (p->next != nullptr){
p = p->next;
}
p->next = newNode;
}
return head;
}
三、删除节点
ListNode *deleteNode(ListNode* head, int data){
ListNode *p = head;
// 首先判断是不是空链表
if (p == nullptr){
return head;
} else {
// 判断是不是删除头节点
if (p->val == data){
head = p->next;
delete p;
return head;
} else {
// 如果有该结点,遍历到待删除节点的前一节点
while (p->next != nullptr && p->next->val != data){
p = p->next;
}
// 遍历完整个链表都没有待删除节点
if (p->next == nullptr){
return head;
} else {
ListNode *deleteNode = p->next;
p->next = deleteNode->next;
delete deleteNode;
return head;
}
}
}
}
四、遍历链表
- 定义一个用于遍历的临时指针,用while循环实现遍历输出等操作;
void ScanList() {
// 定义一个临时变量来指向头
struct Node *temp = head;
while (temp != NULL){
printf("%d\n",temp->a);
// temp指向下一个的地址 即实现++操作
temp = temp->next;
}
}
五、 查询指定的节点(遍历)
struct Node *FindNode(int a ) {
struct Node *temp = head;
while(temp != NULL) {
if(a == temp->a) {
return temp;
}
temp = temp->next;
}
return NULL;
}
六、链表清空
- FreeList函数仍是采用遍历的方式一个一个的将节点内存释放,最后实现全部删除的效果,但是要注意在最后应该讲头尾节点至NULL否则下次的链表将会接着这次的头尾。
void FreeList() {
// 定义一个临时变量来指向头
struct Node *temp = head;
while (temp != NULL) {
struct Node *pt = temp;
// temp指向下一个的地址 即实现++操作
temp = temp->next;
// 释放当前
free(pt);
}
// 头尾清空,不然下次的头就接着0x10
head = NULL;
end = NULL;
}
七、反转链表
- 假设pNode是当前的节点,pPrev是pNode前面的节点,PNext是PNode后面的节点,那么:
-
- 当pNode不为nullptr,且pNext不为nullptr的时候:
① 将pNode指向pPrev(pNode->next = pPrev);
② 将pNode给pPrev(pPrev= pNode);
③ 将pNext给pNode(pNode = pNext);
- 当pNode不为nullptr,且pNext不为nullptr的时候:
-
- 当pNode不为nullptr,且pNext==nullptr的时候,把反转后的头部指向pNode;
#include <iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL){
}
};
// 反转链表
ListNode *reverse(ListNode *head) {
ListNode *pPrev = nullptr;
ListNode *p = head;
ListNode *pReverseHead = nullptr;
while (p != nullptr){
ListNode *pNext = p->next;
if (pNext == nullptr){
pReverseHead = p;
}
p->next = pPrev;
pPrev = p;
p = pNext;
}
return pReverseHead;
}
int main(){
int num;
cin >> num;
ListNode *head = new ListNode(num);
ListNode *p = head;
while (cin >> num){
ListNode *q = new ListNode(num);
p->next = q;
p = p->next;
}
p->next = nullptr;
ListNode *result = reverse(head);
ListNode *node = result;
while (node != nullptr){
cout << node->val << endl;
node = node->next;
}
return 0;
}
八、倒数第K个节点
- 设置快慢指针,快指针比慢指针多走k-1步,那么快指针走到终点的时候,慢指针指向倒数第K个结点;
ListNode *FindKthToTail(ListNode *pListHead, unsigned int k) {
if (pListHead == nullptr || k == 0){
return nullptr;
}
ListNode *pAhead = pListHead;
// 判断K是不是超出了链表的长度
for (int i = 0; i< k - 1; i++){
if (pAhead->next != nullptr){
pAhead = pAhead->next;
} else {
return nullptr;
}
}
ListNode *pBehind = pListHead;
while (pAhead->next != nullptr){
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}
九、判断链表是否有环
- 可以设置快慢指针,快指针一次走两步,慢指针一次走一步,如果快指针追上了走的慢的指针,那么链表有环,如果走到了链表尾部都没有追上,说明链表无环。
- 如果有环,返回入口节点:返回的节点一定在环内,如果计算出环中节点的个数count,快指针比慢指针多走count步,那么两个指针相遇时,就是环的入口节点。
// 判断快慢指针是否相遇
ListNode *MeetNode(ListNode *pHead){
ListNode *pNode = pHead;
// 判断链表是否为空
if(pNode == nullptr){
return nullptr;
}
// 设置慢指针(慢指针不能为nullptr)
ListNode *slowNode = pNode -> next;
if(slowNode == nullptr){
return nullptr;
}
// 设置快指针
ListNode *fastNode = slowNode -> next;
while(fastNode != nullptr && slowNode != nullptr){
// 相遇返回快/慢指针
if(fastNode == slowNode){
return fastNode;
}
// slow走一步
slowNode = slowNode ->next;
// fast走两步(走下一步需要判读是不是为nullptr)
fastNode = fastNode -> next;
if (fastNode -> next != nullptr){
fastNode = fastNode -> next;
}
}
return nullptr;
}
// 计算环中节点的个数
int Count(ListNode *pMeet){
int count = 0;
ListNode * pNode = pMeet;
while(pNode->next != pMeet){
++count;
pNode = pNode -> next;
}
++ count;
return count;
}
// 计算环的入口节点
ListNode *EntryNodeOfLoop(ListNode *pHead) {
ListNode *meetNode = MeetNode(pHead);
if (meetNode == nullptr){
return nullptr;
}
int count = Count(meetNode);
ListNode *aheadNode = pHead;
ListNode *behindNode = pHead;
for(int i = 0; i< count; i++){
aheadNode = aheadNode ->next;
}
while(aheadNode != behindNode){
aheadNode = aheadNode -> next;
behindNode = behindNode -> next;
}
ListNode *result = aheadNode;
return result;
}
文章来源: blog.csdn.net,作者:Serendipity·y,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/Forever_wj/article/details/107517451
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)