mes系统,合肥关键词排名优化,wordpress文章底部版权说明,广西建设网官网证书查询【数据结构】单链表---C语言版 一、顺序表的缺陷二、链表的概念和结构1.概念#xff1a; 三、链表的分类四、链表的实现1.头文件#xff1a;SList.h2.链表函数#xff1a;SList.c3.测试函数#xff1a;test.c 五、链表应用OJ题1.移除链表元素#xff08;1#xff09;题目… 【数据结构】单链表---C语言版 一、顺序表的缺陷二、链表的概念和结构1.概念 三、链表的分类四、链表的实现1.头文件SList.h2.链表函数SList.c3.测试函数test.c 五、链表应用OJ题1.移除链表元素1题目描述2思路表述3代码实现 2.翻转一个单链表1题目描述2思路表述3代码实现 3.返回一个链表的中间节点1题目描述2思路表述3代码实现 4.链表中倒数第k个结点1题目描述2思路表述3代码实现 5.合并两个有序链表1题目描述2思路表述3代码实现 6. 链表分割1题目描述2思路表述3代码实现 7. 链表的回文结构1题目描述2思路表述3代码实现 8.相交链表1题目描述2思路表述3代码实现 9.判断链表中是否有环1题目描述2思路表述3代码实现 六、链表和顺序表的优缺点对比 一、顺序表的缺陷
1挪动数据时间开销较大如果是头插或者头删后面的数据都需要挪动时间复杂度为ON这样的代价就比较大。 2增容有代价每次扩容都需要向系统申请空间然后拷贝数据然后再释放原来的旧空间这样对系统的消耗还是不小的。 3空间浪费我们每次空间不够都会扩大原来空间的二倍如果我只需要两个字节的空间但是我扩大了原来100的2倍那98个字节的空间就浪费了。
但是谁能来解决这个问题呢那么就是接下来要讲的链表 ;//申请新结点函数
SLTNode* BuySListNode(SLTDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头删
void SLTPopFront(SLTNode** pphead);//尾删
void SLTPopBack(SLTNode** pphead);//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos位置之后插入一个数字x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除POS位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除POS位置的下一个值
void SLTEraseAfter(SLTNode* pos);2.链表函数SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include SList.hvoid SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d- , cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}//头插void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}//尾插
//如果我要改变指针的指向我不可能通过传值调用我只能通过来改变指针的地址
//也就是用二级指针才能改变结构体指针的指向。
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);//创建新节点if (*pphead NULL){// 改变的结构体的指针所以要用二级指针*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next)//tail-next!NULL{tail tail-next;}// 改变的结构体用结构体的指针即可tail-next newnode;//因为tail-next是结构体中的一个成员}
}//头删
void SLTPopFront(SLTNode** pphead)
{//空//如果直接指向空指针,那就不用删了assert(*pphead);//非空// 我们需要运用空瓶思想创建个临时变量来存放要删那个节点的下一个节点的地址//要不然删除那个节点之后下一个节点的地址就连接不上了。SLTNode* newnode (*pphead)-next;free(*pphead);*pphead newnode;}//尾删
void SLTPopBack(SLTNode** pphead)
{//1.空assert(*pphead);//1个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//1个以上结点else{//因为是尾删所以需要一个前摇标志tailPrevSLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}//方法2//SLTNode* tail *pphead;//while (tail-next-next)//{// tail tail-next;//}//free(tail-next);//tail-next NULL;
}//查找函数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur)//而不是cur-text!NULL查找因为我要遍历完{if (cur-data x){return cur;}cur cur-next;}return NULL;//当全部都遍历完了还没找到的话就直接返回 空 NULL
}//在POS之前插入一个结点void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//SLTNode* prev *pphead;if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}//在pos位置后插入一个数字
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);//while()为啥不用循环newnode-next pos-next;pos-next newnode;}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);//pos NULL;}
}//删除pos后位置的一个值
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查尾节点是否为空assert(pos-next);//空瓶思想需要先做一个标记,posnext就是空瓶存放,在pos的下一个位置SLTNode* posNext pos-next;pos-next posNext-next;free(posNext);posNext NULL;}3.测试函数test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include SList.hvoid TestList1()
{int n0;printf(请输入链表的长度);scanf(%d, n);printf(\n请依次输入每个节点的值);SLTNode* plist NULL;for (int i 0; i n; i){int val 0;scanf(%d, val);SLTNode* newnode BuySListNode(val);//头插newnode-next plist;plist newnode;}SLTPrint(plist);SLTPushBack(plist, 10000);SLTPrint(plist);
}//void SLTPushBack(SLTNode** phead, SLTDataType x)
//{
// //如果我要改变指针的指向我不可能通过传值调用我只能通过来改变指针的地址也就是用二级指针才能改变结构体指针的指向。
// SLTNode* newnode BuySListNode(x);
// SLTNode* tail phead;
// while (tail-next)//tail-next!NULL
// {
// tail tail-next;
// }
// tail-next newnode;
//}//测试尾插
void TestList2()
{SLTNode* plist NULL;SLTPushBack(plist, 10);SLTPrint(plist);SLTPushBack(plist, 20);SLTPrint(plist);SLTPushBack(plist, 30);SLTPrint(plist);SLTPushBack(plist, 40);SLTPrint(plist);SLTPushBack(plist, 50);SLTPrint(plist);
}//测试头插
void TestList3()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPrint(plist);SLTPushFront(plist, 20);SLTPrint(plist);SLTPushFront(plist, 30);SLTPrint(plist);SLTPushFront(plist, 40);SLTPrint(plist);SLTPushFront(plist, 50);SLTPrint(plist);
}//测试尾删
void TestList4()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPushFront(plist, 50);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);
}//测试头删
void TestList5()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPushFront(plist, 50);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);
}//测试查找
void TestList6()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPushFront(plist, 50);SLTPrint(plist);SLTNode* pos SLTFind(plist, 40);if (pos){pos-data * 10;}SLTPrint(plist);int x 0;printf(请输入要查找数字的位置);scanf(%d, x);pos SLTFind(plist, x);if (pos){SLTInsert(plist, pos, x * 10);}SLTPrint(plist);}void TestList7()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPushFront(plist, 50);SLTPrint(plist);int x;printf(请输入你想要查找的数字);scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTInsertAfter(pos, x * 10);}SLTPrint(plist);}void TestList8()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPushFront(plist, 50);SLTPrint(plist);int x 0;printf(请输入你想要查找的数字);scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTErase(plist, pos);}SLTPrint(plist);
}void TestList9()
{SLTNode* plist NULL;SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPushFront(plist, 50);SLTPrint(plist);int x 0;printf(请输入你想要查找的数字);scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTEraseAfter(pos);}SLTPrint(plist);}int main()
{//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();//TestList6();//TestList7();TestList8();//TestList9();return 0;
}五、链表应用OJ题
1.移除链表元素
1题目描述
点击链接
2思路表述
创建的prev和tmp指针都是用来保存 cur当前节点指针的前一个和后一个因为如果你直接销毁cur的话他前一个和后一个连接不起来所以说你要先创建暂时的节点来保存它。 分类讨论 从头往后找如果没找到要删的目标节点就一直往后走 prev-nextcur; curcur-next; 如果找到目标节点这里面还要分为如果目标节点是在“头”我们要进行“头删”如果在除了“头”的其他位置是另一种情况注意只要我找到了要删的目标节点我一定要先保存当前要删节点的下一个
3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prevNULL;struct ListNode* curhead;while(cur){if(cur-valval)//只要找到了我就保存{struct ListNode* tmpcur-next;//接下来我就要判断了//1.如果他这个链表里面第1个就是我们要删除的节点。prevNULL就说明第1个就是目标if(prevNULL){free(cur);headtmp;curtmp;}else//2.除了头删的其他任意位置{prev-nexttmp;free(cur);curtmp;}}else//没找到就都往下一个走{prev-nextcur;curcur-next;}}return head;
}2.翻转一个单链表
1题目描述
点击链接
2思路表述
1. 2. 3.
3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* curhead;struct ListNode* newheadNULL;while(cur){//1.保存cur的下一个结点struct ListNode* tmpcur-next;//2.头插头插之后一定要记得newhead要往前走一步cur-nextnewhead;newheadcur;//3.原链表中的cur继续往后走curtmp;}return newhead;
}3.返回一个链表的中间节点
1题目描述
点击链接
2思路表述
利用两个指针一个是快指针fast一个慢指针slow快指针移动的速度是慢指针的二倍
3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next)//1.fast存在针对奇数个结点 2.fast—next存在针对偶数个结点{fastfast-next-next;slowslow-next;}return slow;
}4.链表中倒数第k个结点
1题目描述
点击链接
2思路表述
如果要求倒数第k个节点并返回k节点还是利用快慢指针法先让fast指针走k步slow在第一个节点不动完了之后呢然后他们再一起走最后如果fast走到了NULL那么就直接返回slow就OK了 自己要尝试画画图
3代码实现
/*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * param pListHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* fastpListHead;struct ListNode* slowpListHead;//fast(fast-next)*k;//先让fast指针走K步while(k--){if(fastNULL){return NULL;}fastfast-next;}while(fast){fastfast-next;slowslow-next;}return slow;
}5.合并两个有序链表
1题目描述
题目链接
2思路表述 2. 3. 4. 5.
3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{struct ListNode* headNULL;struct ListNode* tailNULL;//前提排除如果有一个链表就是空的咋办if(l1NULL){return l2;}if(l2NULL){return l1;}//1.确定好l1和l2谁为head,tailif(l1-vall2-val){headtaill1;l1l1-next;}else{headtaill2;l2l2-next;}//2.逐个节点判断while(l1l2){if(l1-vall2-val){tail-nextl1;l1l1-next;tailtail-next;}else{tail-nextl2;l2l2-next;tailtail-next;}}//3.如果跳出了循环那么肯定有一个指向了NULLif(l1NULL){tail-nextl2;}if(l2NULL){tail-nextl1;}return head;
}6. 链表分割
1题目描述
点击链接
2思路表述
分析申请两个链表一个放比x小的节点一个放比x大的节点最后将大链表链接在小链表末尾即可。
3代码实现
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include cstddef
class Partition {public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* cur pHead;struct ListNode* lhead;struct ListNode* ltail;struct ListNode* ghead;struct ListNode* gtail;lhead ltail (struct ListNode*)malloc(sizeof(struct ListNode));ghead gtail(struct ListNode*)malloc(sizeof(struct ListNode));while (cur) {if (cur-val x) {ltail-next cur;ltail ltail-next;}else {gtail-next cur;gtail gtail-next;}cur cur-next;}ltail-next ghead-next;//不置空会导致死循环gtail-next NULL;//释放哨兵位但需先创建结构体保存lhead的第一个struct ListNode* head lhead-next;free(lhead);free(ghead);return head;}
};7. 链表的回文结构
1题目描述
点击链接
2思路表述
分析判断链表是否是回文结构可以结合前面的题
1利用快慢指针找到链表中间结点
2将后半部分逆置
3将2中的链表从第一个节点开始和中间结点开始同时进行访问如果所有val相等则链表为回文结构。
3代码实现
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {public:bool chkPalindrome(ListNode* head) {struct ListNode* middleNode(struct ListNode * head);struct ListNode* reverseList(struct ListNode * head);//找到中间节点struct ListNode* middleNode(struct ListNode * head) {struct ListNode* fast head;struct ListNode* slow head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow;}//将中间节点后的都逆置struct ListNode* reverseList(struct ListNode * head) {struct ListNode* cur head;struct ListNode* newhead NULL;while (cur) {//这个next定义一定要在while循环内部因为每次头插之前都要保存下一个节点的地址!!!struct ListNode* next cur-next;//头插cur-next newhead;newhead cur;cur next;}return newhead;}struct ListNode* mid middleNode(head);struct ListNode* rmid reverseList(mid);//head相当于原来链表的前一半的头指针//rmid相当于原来链表后一半的头指针while (head rmid) {if (head-val ! rmid-val) {return false;}head head-next;rmid rmid-next;}return true;}};8.相交链表
1题目描述
点击链接
2思路表述
分别计算出L1链表和L2链表的总长度然后用两个指针一个是fast一个是slow让fast先走他们的差值步让他们处在同一竖直平行线上然后他们两个一起走两个指针一起走后如果所指向的节点的值相同那么就返回这个公共节点也就是相交节点
3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{//1.极端条件的判断要么L1为空要么L2为空我就返回空所以说不可能有公共交点。if(headA NULL || headB NULL){return NULL;}struct ListNode *curA headA, *curB headB;int lenA 0,lenB 0;while(curA-next){curA curA-next;lenA;}while(curB-next){curB curB-next;lenB;}//2.此时此刻两个循环都结束了current a指向的是最后一个节点current b也指向最后一个节点如果他们两个不相等的话走到最后一个节点还没有公共交点那么他们两个永远远远不可能会有公共节点所以说我们直接返回空就ok了。if(curA ! curB){return NULL;}//3.此时两个指针都指向数值水平线的平行线上处于同一位置,现在不知道lena大?还是lenb大?所以说我先假设lena大struct ListNode *longList headA,*shortList headB;if(lenA lenB){longList headB;shortList headA;}int gap abs(lenA - lenB);while(gap--){longList longList-next;}while(longList ! shortList){longList longList-next;shortList shortList-next;}return longList;
}9.判断链表中是否有环
1题目描述
点击链接 2思路表述
分析
如何判断链表是否有环使用快慢指针慢指针一次走1步快指针一次走2步如果链表带环那么快慢同时从链表起始位置开始向后走一定会在环内相遇此时快慢指针都有可能在环内打圈直到相遇否则如果链表不带环那么快指针会先走到链表末尾慢指针只能在链表末尾追上快指针。 如果快指针不是一次走2步而是一次走3步一次走4步一次走x步呢能不能判断出链表是否带环呢
如果快指针一次走两步当slow从直线中间移动到直线末尾时fast又走了slow的2倍因此当slow进环时fast可能在环的任意位置具体要看直线有多长环有多大。在环内一定是fast追slow因为fast比slow移动的快。
fast一次走3步假设slow进环的时候fast跟slow相差N步环的长度为C追击时slow走1步fast走3步每走1次差距就缩小 总结如果slow进环时slow和fast的差距N是奇数且环的长度C为偶数(则C-1为奇数上面举例可以看出差距最小为1或-1)那么就永远追不上了。
3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head)
{struct ListNode* slowhead;struct ListNode* fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){return true;}}return false;
}六、链表和顺序表的优缺点对比 没有谁好谁坏不同情况具体对待相辅相成罢了 好了今天的分享就到这里了 如果对你有帮助记得点赞关注哦 我的主页还有其他文章欢迎学习指点。关注我让我们一起学习一起成长吧
