🏠 大家好，我是 兔7 ，一位努力学习C++的博主~💬
🍑 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
🚀 如有不懂，可以随时向我提问，我会全力讲解~
🔥 如果感觉博主的文章还不错的话，希望大家关注、点赞、收藏三连支持一下博主哦~！
🔥 你们的支持是我创作的动力！
🧸 我相信现在的努力的艰辛，都是为以后的美好最好的见证！
🧸 人的心态决定姿态！
🚀 本文章CSDN首发！
目录
0. 前言
此博客为博主以后复习的资料，所以大家放心学习，总结的很全面，每段代码都给大家发了出来，大家如果有疑问可以尝试去调试。
大家一定要认真看图，图里的文字都是精华，好多的细节都在图中展示、写出来了，所以大家一定要仔细哦~
感谢大家对我的支持，感谢大家的喜欢， 兔7 祝大家在学习的路上一路顺利，生活的路上顺心顺意~！
1. 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2. 顺序表
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素
2. 动态顺序表：使用动态开辟的数组存储。
2.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
SeqList.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SeqListDataType;
typedef struct SeqList
{
SeqListDataType* a;
int size;
int capacity;
}SeqList;
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SeqListDataType x);
void SeqListPopBack(SeqList* ps);
void SeqListPushFront(SeqList* ps, SeqListDataType x);
void SeqListPopFront(SeqList* ps);
int SeqListFind(SeqList* ps, SeqListDataType x);
void SeqListInsert(SeqList* ps, size_t pos, SeqListDataType x);
void SeqListErase(SeqList* ps, size_t pos);main.h
#include"SeqList.h"
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListCheckCapacity(SeqList* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SeqListDataType* tmp = (SeqListDataType*)realloc(ps->a, newcapacity * sizeof(SeqListDataType));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
}
void SeqListPushBack(SeqList* ps, SeqListDataType x)
{
//assert(ps);
//SeqListCheckCapacity(ps);
//ps->a[ps->size] = x;
//ps->size++;
SeqListInsert(ps, ps->size, x);
}
void SeqListPopBack(SeqList* ps)
{
//assert(ps);
//if (ps->size == 0)
//{
// perror("SeqListPopBack");
// exit(-1);
//}
//ps->size--;
SeqListErase(ps, ps->size - 1);
}
void SeqListPushFront(SeqList* ps, SeqListDataType x)
{
//assert(ps);
//SeqListCheckCapacity(ps);
//int end = ps->size - 1;
//while (end >= 0)
//{
// ps->a[end + 1] = ps->a[end];
// end--;
//}
//ps->a[0] = x;
//ps->size++;
SeqListInsert(ps, 0, x);
}
void SeqListPopFront(SeqList* ps)
{
//assert(ps);
//if (ps->size == 0)
//{
// perror("SeqListPopBack");
// exit(-1);
//}
//int front = 1;
//int end = ps->size - 1;
//while (end >= front)
//{
// ps->a[front - 1] = ps->a[front];
// front++;
//}
//ps->size--;
SeqListErase(ps, 0);
}
int SeqListFind(SeqList* ps, SeqListDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
void SeqListInsert(SeqList* ps, size_t pos, SeqListDataType x)
{
assert(ps);
assert((int)pos <= ps->size);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= (int)pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
assert((int)pos < ps->size);
// 不用判断小于0的情况，因为pos 类型是size_t的
int end = ps->size - 2;
while ((int)pos <= end)
{
ps->a[pos] = ps->a[pos + 1];
pos++;
}
ps->size--;
}2.3 数组相关面试题
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int count = nums.size();
for (int i = 0; i < count; i++)
{
if (nums[i] == val)
{
nums.erase(nums.begin() + i);
count--;
i--;
}
}
return nums.size();
}
};
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int prev = 0 ;
int next = 1;
while(next < nums.size())
{
if(nums[next] != nums[prev])
{
prev++;
nums[prev] = nums[next];
}
next++;
}
return prev + 1;
}
};
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int nest1 = m - 1;
int nest2 = n - 1;
int tail = m + n - 1;
int cur = 0;
while(nest1 >= 0 && nest2 >= 0)
{
if(nums1[nest1] >= nums2[nest2])
{
nums1[tail--] = nums1[nest1];
nest1--;
}
else
{
nums1[tail--] = nums2[nest2];
nest2--;
}
}
if(nest1 == -1)
{
while(nest2 >= 0)
{
nums1[tail--] = nums2[nest2];
nest2--;
}
}
}
};2.4 顺序表的问题及思考
问题：
- 中间/头部的插入删除，时间复杂度为O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
所以就有了下面的链式结构~！
3. 链表
3.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
现实中数据结构中
3.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3.3 链表的实现
SList.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SLTNode
{
SLTDataType data;
struct SLTNode* next;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x);
void SLTPrint(SLTNode* phead);
void SLTDestroy(SLTNode** phead);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* plist, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);main.h
#include"SList.h"
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuySLTNode");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
SLTNode* next = (*pphead)->next;
while (next)
{
free(cur);
cur = next;
next = cur->next;
}
free(cur);
*pphead = NULL;
}
void SLTPrint(SLTNode* phead)
{
//assert(phead); 不用断言，因为就有可能为空(没数据)
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//按理说不能为NULL，防止别人传NULL
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
if ((*pphead) == NULL)
{
return;
}
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
if ((*pphead) == NULL)
{
return;
}
SLTNode* del = *pphead;
*pphead = del->next;
free(del);
del = NULL;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
//if (phead->data == x)
//{
// return phead;
//}
//else
//{
// SLTNode* cur = phead->next;
// while (cur->data != x)
// {
// if (cur == NULL)
// return NULL;
// cur = cur->next;
// }
// return cur;
//}
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
SLTNode* cur = *pphead;
while (cur != pos)
{
cur = cur->next;
// pos不在链表中.cur为空，还没有找到pos，说明pos传错了
assert(cur);
}
SLTNode* newnode = BuySLTNode(x);
newnode->next = cur->next;
cur->next = newnode;
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
// pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead); // 没数据不能删
SLTNode* cur = *pphead;
if (cur == pos)
{
SLTPopFront(pphead);
}
while (cur->next != pos)
{
cur = cur->next;
assert(cur);
}
cur->next = pos->next;
free(pos);
}
// pos后面位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
return;
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}3.4 链表面试题
可以像我这样先将头节点的 val 判断到非要删除的 val ，再遇到为删除的 val 的时候再跳过，也可以在 while(cur) 里面分为要删除的 val 和非要删除的进行判断执行。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(head == NULL)
return head;
while(head != NULL && head->val == val)
{
head = head->next;
}
ListNode* prev = NULL;
ListNode* cur = head;
while(cur)
{
if(cur->val == val)
{
ListNode* next = cur->next;
if(prev != NULL)
{
prev->next = next;
}
cur = next;
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL)
return head;
ListNode* prev = NULL;
ListNode* cur = head;
while(cur)
{
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
判断这种位置类型的都可以往快慢指针去想。
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;;
while(fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
这里的快慢指针一定要注意，先移动 k 个还是 移动 k-1 个，最后 while(fast) 的判断不同，一个是 nest 是 NULL，一个是已经到了 NULL。
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* fast = pListHead;
ListNode* slow = pListHead;
while(k--)
{
if(fast == NULL)
{
return NULL;
}
fast = fast->next;
}
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail = guard;
ListNode* cur1 = list1;
ListNode* cur2 = list2;
while(cur1 && cur2)
{
if(cur1->val > cur2->val)
{
tail->next = cur2;
cur2 = cur2->next;
}
else
{
tail->next = cur1;
cur1 = cur1->next;
}
tail = tail->next;
}
if(cur1 == NULL)
{
tail->next = cur2;
}
else
{
tail->next = cur1;
}
return guard->next;
}
};
这个是将链表按照之前的顺序先以 x 分为两段，然后再链接起来，如果以 x 这个链为界再头插尾插是不可以的。顺序都不一样了。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
ListNode* greatHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* greatTail = greatHead;
ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* lessTail = lessHead;
ListNode* cur = pHead;
while(cur)
{
if(cur->val >= x)//大于的放后面
{
greatTail->next = cur;
greatTail = greatTail->next;
}
else
{
lessTail->next = cur;
lessTail = lessTail->next;
}
cur = cur->next;
}
lessTail->next = greatHead->next;
greatTail->next = NULL;
pHead = lessHead->next;
free(greatHead);
free(lessHead);
return pHead;
}
}; 
这个回文需要从中间开始将后面的逆序，然后一个从头开始，一个从中间开始，分别向后依次判断 val 是否相同，不过要注意从中间分开后的尾部的指针指向谁这个细节。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
//快慢指针找中间
ListNode* fast = A;
ListNode* slow = A;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
//逆序
ListNode* cur = slow;
ListNode* newHead = NULL;
while(cur)
{
ListNode* next = cur->next;
cur->next = newHead;
newHead = cur;
cur = next;
}
//遍历
// 这个结构不是一个链结构
ListNode* mid = newHead;
ListNode* Head = A;
while(mid)
{
if(Head->val != mid->val)
return false;
Head = Head->next;
mid = mid->next;
}
return true;
}
};
快慢指针走完，然后让慢的先走完相差步数再一起走，直到相遇。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//计算A、B各多少步
int count1 = 0;
int count2 = 0;
ListNode *head1 = headA;
ListNode *head2 = headB;
while(head1)
{
head1 = head1->next;
count1++;
}
while(head2)
{
head2 = head2->next;
count2++;
}
//快慢指针先同步
ListNode* fast = headB , *slow = headA;
int gap = abs(count1 - count2);
if(count1 > count2)
{
fast = headA;
slow = headB;
}
//快的先走
while(gap)
{
fast = fast->next;
gap--;
}
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
如果有环就一定会相遇。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(slow == fast)
return true;
}
return false;
// while(slow != fast)
// {
// fast = fast->next->next;
// slow = slow->next;
// }
// return true;
}
};
这个我在之前的博客写过，我会在下面贴出来。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(slow == fast)
{
ListNode* meet = slow;
ListNode* begin = head;
while(begin != meet)
{
begin = begin->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}
};上面这个博客就是详解，大家可以去看看。
这个思路就是先拷贝节点挂在原节点后面，建立对应关系。
然后调整要 copy 的 random，之间找到被拷贝的 random 的 next 就可以。
最后调整 next，然后恢复原来链就可以了。
struct Node* copyRandomList(struct Node* head) {
//1.拷贝节点挂在原节点后面，建立对应关系。
struct Node* cur = head;
while(cur)
{
struct Node* next = cur->next;
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
cur->next = copy;
copy->next = next;
cur = next;
}
//2.处理copy节点得random
cur = head;
while(cur)
{
struct Node* copy = cur->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
cur = copy->next;
}
//拷贝节点取下来链到一起，恢复原链表
cur = head;
struct Node* copyHead,*copyTail;
copyHead = copyTail = (struct Node*)malloc(sizeof(struct Node));
copyHead->next = NULL;//要是传的为空，直接返回NULL
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
//尾插
copyTail->next = copy;
copyTail = copyTail->next;
cur->next = next;
cur = next;
}
struct Node* guard = copyHead;
copyHead = copyHead->next;
free(guard);
return copyHead;
}3.5 双向链表的实现
DList.h
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* nest;
LTDataType data;
}ListNode;
ListNode* ListInit();
void ListDestory(ListNode* phead);
void Print(ListNode* phead);
void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
bool IsEmpty(ListNode* phead);
size_t Size(ListNode* phead);
ListNode* Find(ListNode* phead, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x);
void ListErase(ListNode* pos);
DList.c
#include "DList.h"
ListNode* ListInit()
{
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
if (guard == NULL)
{
perror("malloc error");
exit(-1);
}
guard->prev = guard;
guard->nest = guard;
return guard;
}
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->nest;
while (cur != phead)
{
ListNode* nest = cur->nest;
free(cur);
cur = nest;
}
free(phead);
}
void Print(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->nest;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->nest;
}
printf("\n");
}
ListNode* BuyListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL)
{
perror("BuyListNode error\n");
exit(-1);
}
newNode->data = x;
newNode->prev = NULL;
newNode->nest = NULL;
return newNode;
}
bool IsEmpty(ListNode* phead)
{
assert(phead);
return phead->nest == phead;
}
size_t Size(ListNode* phead)
{
assert(phead);
size_t n = 0;
ListNode* cur = phead->nest;
while (cur != phead)
{
n++;
cur = cur->nest;
}
return n;
}
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
关心顺序
//phead->prev->nest = newNode;
//newNode->prev = phead->prev;
//newNode->nest = phead;
//phead->prev = newNode;
//不关心顺序
ListNode* tail = phead->prev;
newNode->nest = phead;
newNode->prev = tail;
tail->nest = newNode;
phead->prev = newNode;
}
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* first = phead->nest;
phead->nest = newNode;
newNode->prev = phead;
newNode->nest = first;
first->prev = newNode;
}
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(!IsEmpty(phead));
ListNode* newTail = phead->prev->prev;;
ListNode* del = phead->prev;
newTail->nest = phead;
phead->prev = newTail;
free(del);
}
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(!IsEmpty(phead));
ListNode* newFirst = phead->nest->nest;
ListNode* del = phead->nest;
phead->nest = newFirst;
newFirst->prev = phead;
free(del);
}
ListNode* Find(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->nest;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->nest;
}
return NULL;
}
// pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newNode = BuyListNode(x);
prev->nest = newNode;
newNode->prev = prev;
pos->prev = newNode;
newNode->nest = pos;
}
//删除pos位置
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
prev->nest = pos->nest;
pos->nest->prev = prev;
free(pos);
}
Test.c
#include "DList.h"
void Test1()
{
ListNode* head = ListInit();
ListPushBack(head, 1);
ListPushBack(head, 2);
ListPushBack(head, 3);
ListPushBack(head, 4);
ListPushFront(head, 4);
ListPushFront(head, 5);
ListPushFront(head, 6);
Print(head);
ListPopBack(head);
ListPopBack(head);
ListPopBack(head);
Print(head);
ListPopFront(head);
ListPopFront(head);
Print(head);
ListDestory(head);
}
void Test2()
{
ListNode* head = ListInit();
ListPushBack(head, 1);
ListPushBack(head, 2);
ListPushBack(head, 3);
ListPushBack(head, 4);
ListPushFront(head, 5);
ListPushFront(head, 6);
ListPushFront(head, 7);
ListPushFront(head, 8);
Print(head);
//size_t n = Size(head);
//printf("%d\n", n);
ListNode* pos = Find(head, 1);
ListInsert(pos, 10);
ListInsert(pos, 20);
ListInsert(pos, 30);
Print(head);
ListErase(pos);
Print(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
ListPopFront(head);
//ListPopFront(head);
Print(head);
ListDestory(head);
}
int main()
{
Test2();
return 0;
}
4.顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
如上就是 顺序表和链表 的所有知识，如果大家喜欢看此文章并且有收获，可以支持下 兔7 ，给 兔7 三连加关注，你的关注是对我最大的鼓励，也是我的创作动力~！
再次感谢大家观看，感谢大家支持！