《C++》解密--单链表
郭小宝耶 2024-10-03 16:05:01 阅读 58
目录
一、概念与结构
二、实现单链表
三、链表的分类
四、单链表算法题
一、概念与结构
1、节点
结点的组成主要有：当前结点要保存的数据和保存下一个节点的地址（指针变量）
图中指针变量plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点。
链表中每个结点都是独立申请的（如果需要插入数据时才去申请一块结点的空间），我们需 要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
2、链表的性质
【链表机构在逻辑上是连续的，在物理结构上不一定连续。
【结点一般是从堆上申请的。
【从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。
二、实现单链表
1、创立文件
2、定义链表的结构
【SList.h】
<code>//定义链表(结点)的位置
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
3、打印函数
【SList.h】
//打印函数
void SLTPrint(SLTNode* phead);
【SList.c】
//打印函数
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->;", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
【test.c】
//创建一个链表，并且打印链表
void createSList()
{
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
//第一个结点的地址作为参数传递过去
SLTNode* plist = node1;
SLTPrint(node1);
}
4、判断插入时，空间是否足够
【SList.c】
//判断插入数据时，空间是否足够
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}
5、尾插
【SList.h】
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);
【SList.c】
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//形参：pphead --> 实参：&plist
//*pphead 解引用 --> plist
//申请新结点
SLTNode* newnode = SLTBuyNode(x); //判断是否有足够空间
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//尾节点 --> 新结点
//找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail --> newnode
ptail->next = newnode;
}
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPrint(plist); //1->NULL
SLTPushBack(&plist, 2);
SLTPrint(plist); //1->2->NULL
SLTPushBack(&plist, 3);
SLTPrint(plist); //1->2->3->NULL
SLTPushBack(&plist, 4);
SLTPrint(plist); //1->2->3->4->NULL
}
【运行结果】
6、头插
【SList.h】
<code>//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x);
【SList.c】
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x); //判断是否有足够空间
//newnode *pphead
newnode->;next = *pphead;
*pphead = newnode;
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL
}
【运行结果】
7、尾删
【SList.h】
<code>//尾删
void SLTPopBack(SLTNode** pphead);
【SList.c】
//尾删
void SLTPopBack(SLTNode** pphead)
{
//判断链表是不是空，若为空则不可以删
assert(pphead && *pphead);
//处理只有一个结点的情况：要删除的就是头结点（当next指针为空）
if ((*pphead)->;next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找尾结点ptail 和尾结点的前一个结点prev
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
//遍历数组,找尾结点
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
//尾删
SLTPopBack(&plist);
SLTPrint(plist); //4->3->2->NULL
SLTPopBack(&plist);
SLTPrint(plist); //4->3->NULL
SLTPopBack(&plist);
SLTPrint(plist); //4->NULL
SLTPopBack(&plist);
SLTPrint(plist); //NULL
}
【运行结果】
8、头删
【SList.h】
<code>//头删
void SLTPopFront(SLTNode** pphead);
【SList.c】
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->;next;
//删除*pphead --> next
free(*pphead);
*pphead = next;
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
//SLTPrint(plist); //4->3->2->1->NULL
//头删
SLTPopFront(&plist);
SLTPrint(plist); //3->2->1->NULL
SLTPopFront(&plist);
SLTPrint(plist); //2->1->NULL
SLTPopFront(&plist);
SLTPrint(plist); //1->NULL
SLTPopFront(&plist);
SLTPrint(plist); //NULL
}
【运行结果】
9、查找
【SList.h】
<code>//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
【SList.c】
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->;data == x)
{
return pcur;
}
pcur = pcur->next;
}
//跳出循环，说明没找到
return NULL;
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
//SLTPrint(plist); //4->3->2->1->NULL
//查找
SLTNode* find = SLTFind(plist, 3);
if (find == NULL)
{
printf("没找到！\n");
}
else
{
printf("find it!\n");
}
}
【运行结果】
10、在指定位置之前插入数据
【SList.h】
<code>//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
【SList.c】
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//如果pos恰好是头结点
if (pos == *pphead)
{
SLTPushFront(pphead, x); //相当于头插
}
else
{
SLTNode* newnode = SLTBuyNode(x);
//找到pos的前一个结点:prev
SLTNode* prev = *pphead;
while (prev->;next != pos)
{
prev = prev->next;
}
//跳出这个循环，说明prev的前一个结点就是pos
//将newnode插入prev和pos之间
newnode->next = pos;
prev->next = newnode;
}
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL
//查找
SLTNode* find = SLTFind(plist, 2);
//在指定位置之前插入数据
SLTInsert(&plist, find, 11); //在2之前插入11
SLTPrint(plist); //4->3->11->2->1->NULL
}
【运行结果】
11、在指定位置之后插入数据
【SList.h】
<code>//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
【SList.c】
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//把newnode放到pos的下一个位置（pos->;next）
newnode->next = pos->next;
pos->next = newnode;
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL
//查找
SLTNode* find = SLTFind(plist, 2);
//在指定位置之后插入数据
SLTInsertAfter(find, 9); //在2之后插入9
SLTPrint(plist); //4->3->2->9->1->NULL
}
【运行结果】
12、删除pos结点
【SList.h】
<code>//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
【SList.c】
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos);
assert(pphead && *pphead);
//头插（如果pos恰好为头结点*pphead,那就没有前一个结点prev了）
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->;next != pos)
{ //遍历数组，寻找pos
prev = prev->next;
}
//跳出循环，prev刚好是pos的前一个结点(要删除pos)
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL
//查找
SLTNode* find = SLTFind(plist, 2);
//删除pos结点
SLTErase(&plist, find); //删除pos(2)这个结点
SLTPrint(plist); //4->3->1->NULL
}
【运行结果】
13、删除pos之后的结点
【SList.h】
<code>//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
【SList.c】
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->;next);
//删除pos的下一个结点，就要让pos的下一个结点直接指向pos的next的next
//但是后面要把pos->next释放删除掉，所以先把这个指针保存起来
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL
//查找
SLTNode* find = SLTFind(plist, 2);
//删除pos之后的结点
SLTEraseAfter(find);
SLTPrint(plist); //4->3->2->NULL
}
【运行结果】
14、销毁链表
【SList.h】
<code>//销毁链表
void SListDestroy(SLTNode** pphead);
【SList.c】
//销毁链表
void SListDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->;next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
【test.c】
void SListTest01()
{
SLTNode* plist = NULL;
//头插
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); //4->3->2->1->NULL
//查找
SLTNode* find = SLTFind(plist, 2);
//销毁链表
SListDestroy(&plist);
SLTPrint(plist); //NULL
}
【运行结果】
三、链表的分类
四、单链表算法题
1、反转链表
【思路】
【代码】
<code>typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
//处理空链表
if(head == NULL)
{
return head;
}
//创建三个指针
ListNode* n1,*n2,*n3;
n1 = NULL , n2 = head , n3 = n2->;next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
{
n3 = n3->next;
}
}
//此时n1就是链表反转后新的头结点head
return n1;
}
2、链表的中间结点
【思路】
【代码】
<code>typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode* slow = head,*fast = head;
//慢指针每次走一步
//快指针每次走两步
while(fast && fast->;next) //等价于fast!=NULL && fast->next!=NULL
//当fast或fast->fast任何一个为空指针（为假）时，就跳出循环
{
slow = slow->next;
fast = fast->next->next;
}
//此时slow指向得节点刚好就是中间节点
return slow;
}
3、合并两个有序链表
【思路】
【代码】
<code>typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//处理链表为空的情况
if(list1 == NULL)
{
return list2;
}
if(list2 == NULL)
{
return list1;
}
//创建新链表
ListNode*newHead = NULL,*newTail = NULL;
//创建两个指针分别指向两个链表的头结点
ListNode* l1 = list1;
ListNode* l2 = list2;
//比大小
while(l1 && l2)
{
if(l1->;val < l2->val)
{
//l1尾插到新链表中
if(newHead == NULL)
{
newHead = newTail = l1;
}
else
{
newTail->next = l1;
newTail = newTail->next;
}
l1 = l1->next;
}
else
{
//l2尾插到新链表
if(newHead == NULL)
{
newHead = newTail = l2;
}
else
{
newTail->next = l2;
newTail = newTail->next;
}
l2 = l2->next;
}
}
//跳出while循环，只有两种情况：l1为空（l2肯定不为空） 或 l2为空（l1不为）
if(l1) //l1不为空
{
newTail->next = l1;
}
if(l2) //l2不为空
{
newTail->next = l2;
}
return newHead;
}
4、链表分割
【思路】
【代码】
<code>class Partition
{
public:
ListNode* partition(ListNode* pHead, int x)
{
//创建两个非空链表：小链表、大链表
//小链表
ListNode* lessHead,*lessTail;
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
//大链表
ListNode* greaterHead,*greaterTail;
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
//遍历原链表，与x比较大小
// >=x的尾插进入大链表 ， <x的尾插进入小链表
ListNode* pcur = pHead;
while(pcur) //等价于pcur != NULL
{
if(pcur->;val < x)
{ //尾插到小链表
lessTail->next = pcur;
lessTail = lessTail->next;
}
else
{ //尾插到大链表
greaterTail->next = pcur;
greaterTail = greaterTail->next;
}
pcur = pcur->next;
}
//将大链表的尾结点的next置为空
greaterTail->next = NULL;
//让大小链表首尾相连
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(lessHead);
free(greaterHead);
lessHead = greaterHead = NULL;
return ret;
}
};
5、链表的回文结构
【代码】
class PalindromeList
{
public:
ListNode* findMidNode(ListNode* phead)
{//使用快慢指针，寻找中间结点
ListNode* slow = phead;
ListNode* fast = phead;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverseList(ListNode* phead)
{
//链表反转
ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = phead;
n3 = n2->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
{
n3 = n3->next;
}
}
return n1;
}
bool chkPalindrome(ListNode* A)
{
//1、找中间结点
ListNode* mid = findMidNode(A);
//2、根据中间结点，将中间结点后的链表反转
ListNode* right = reverseList(mid);
//3、从原链表的头和反转链表比较结点值 (开始时，left指头，right指尾)
ListNode* left = A;
while(right)
{
if(left->val != right->val)
{
return false;
}
left = left->next;
right = right->next;
}
return true;
}
};
未完待续...
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。