发布时间:2024-11-17 15:01
- 线性表
- 顺序表
- 链表
- 顺序表和链表的区别和联系
#pragma once
#define N 1000
typedef double SLDataType
//静态顺序表
typedef struct SeqList{
SLDataType a[N];
int size; //表示数组中存储了多少个函数
}SL;
///接口函数 ---命名风格跟着STL
void SeqInit(SL* ps);
//静态特点:如果满了就不让插入 缺点:给多少的合适呢?这个很难确定
//N给小了不够用,N给大了浪费
void SeqPushBack(SL* ps,SLDataType x);
void SeqPopBack(SL* ps);
void SeqPushFront(SL* ps,SLDataType x);
void SeqPopFront(SL* ps);
void SeqPrintf(SL* ps);
//
#pragma once
typedef int SLDataType
//动态顺序表
typedef struct SeqList{
SLDataType *a;
int size; //表示数组中存储了多少个函数
int capacity; //数据实际能存的空间容量是多大
}SL;
///接口函数 ---命名风格跟着STL
void SeqListInit(SL* ps);
//静态特点:如果满了就不让插入 缺点:给多少的合适呢?这个很难确定
//N给小了不够用,N给大了浪费
void SeqListPushBack(SL* ps,SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps,SLDataType x);
void SeqListPopFront(SL* ps);
//
#include \"SeqList.h\"
void SeqListInit(SL ps){
ps.a=NULL;
ps.size=ps.capacity=0;
}
void SeqListPushBack(SL* ps,SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps,SLDataType x);
void SeqListPopFront(SL* ps);
#include \"SeqList.h\"
void SeqListInit(SL* ps){
ps.a=NULL;
ps.size=ps.capacity=0;
}
void SeqListPushBack(SL* ps,SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps,SLDataType x);
void SeqListPopFront(SL* ps);
#include \"SeqList.h\"
void TestSeqList1()
{
SL sl;
SeqListInit(&sl);
}
int main(){
return 0;
}
讨论一下情况:
#include \"SeqList.h\"
void SeqListInit(SL* ps){
ps.a=NULL;
ps.size=ps.capacity=0;
}
void SeqPushBack(SL* ps,SLDataType x){
if(ps->capacity=ps->size){
int newcapacity=(capacity==0?(4:capacity*2));
SLDataType* tmp=(SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType));
if(tmp==NULL){
perror(\"realloc failed\");
exit(-1);
}
ps->a=tmp;
ps->capacity=newcapacity;
}
ps->a[size]=x;
ps->size++;
}
void SeqPrintf(SL* ps){
for(int i=0;i<ps->size;i++){
printf(\"%d \",ps->a[i]);
}printf(\"\\n\");
}
void SeqPopBack(SL* ps);
void SeqPushFront(SL* ps,SLDataType x);
void SeqPopFront(SL* ps);
#include \"SeqList.h\"
void TestSeqList1()
{
SL sl;
SeqInit(&sl);
SeqPushBack(&s1,1);
SeqPushBack(&s1,2);
SeqPushBack(&s1,3);
SeqPushBack(&s1,4);
SeqPushBack(&s1,5);
}
int main(){
return 0;
}
void SeqListDestroy(SL* ps){
free(ps->a);
ps->a=NULL;
ps->size=ps->capacity=0;
}
#include \"SeqList.h\"
void TestSeqList1()
{
SL sl;
SeqInit(&sl);
SeqPushBack(&s1,1);
SeqPushBack(&s1,2);
SeqPushBack(&s1,3);
SeqPushBack(&s1,4);
SeqPushBack(&s1,5);
SeqListDestroy(&s1);
}
int main(){
return 0;
}
void SeqListPopBack(ST* ps){
assert(ps->size!=0);
ps->size--;
}
#include \"SeqList.h\"
void TestSeqList1()
{
SL sl;
SeqInit(&sl);
SeqPushBack(&s1,1);
SeqPushBack(&s1,2);
SeqPushBack(&s1,3);
SeqPushBack(&s1,4);
SeqPushBack(&s1,5);
SeqPushPop();
SeqPushPop();
SeqPushPop();
SeqPushPop();
SeqPushPop();
SeqPushPop();
SeqListDestroy(&s1);
}
int main(){
TestSeqList1();
return 0;
}
void SeqPushFront(Sq* ps){
if(ps->sz==ps->capacity){
int newcapacity=(capacity==0?4:capacity*2);
SLDataType* tmp=(SLDataType*)realloc(capacty*sizeof(SLDataType));
if(tmp==NULL){
perror(\"realloc\");
exit(-1);
}
ps->a=tmp;
ps->capacity=newcapacity;
}
int end=ps->size-1;
while(end>=0){
ps->a[end+1]=ps->a[end];
end--;
}
ps->a[0]=x;
ps->sz++;
}
void TestSeqList2(){
SL sl;
SeqInit(&sl);
SeqPushBack(&s1,1);
SeqPushBack(&s1,2);
SeqPushBack(&s1,3);
SeqPushBack(&s1,4);
SeqPushBack(&s1,5);
SeqListPushFront(&s1,10);
SeqListPushFront(&s1,20);
SeqListPushFront(&s1,30);
SeqListPushFront(&s1,40);
SeqListPushFront(&s1,50);
SeqPrintf(&s1);
SeqListDestroy(&s1);
}
int main(){
TestSeqList1();
TestSeqList2();
}
void SeqListCheckCapacity(Sq* ps){
if(ps->capacity==ps->size){
int newcapacity=(capacity==0?4:capacity*2);
SLDataType* tmp=(DataType*)realloc(newcapacity*sizeof(SLDataType));
if(tmp==NULL){
perror(\"SeqListCheckCapacity\");
exit(-1);
}
ps->a=tmp;
ps->capacity=newcapacity;
}
}
void SeqPopFront(SL* sq){
assert(ps->size>0);
int begin= 1;
while(begin<ps->size){
sq->a[begin-1]=sq->a[begin];
begin++;
}
ps->size--;
}
int SeqListFind(SL* ps,SLDataType x){
for(int i=0;i<ps->size;i++){
if(ps->a[i]==x){
return i;
}
}
return -1;
}
头插尾插可以复用insert。
// 指定pos下标位置插入
void SeqListInsert(SL* ps,int pos,SLDataType x){
assert(pos>=0&&pos<=ps->size);
SeqCheckList(ps);
LL ed=ps->size;
while(ed>pos){
ps->a[ed]=ps->a[ed-1];
ed--;
}
ps->a[pos]=x;
ps->size++;
}
头删尾删可以复用erase
void SeqListErase(SL* ps,int pos,SLDataType x){
assert(pos>=0&&pos<ps->size);
ps->size--;
while(pos<ps->size){
ps->a[pos]=ps->a[pos+1];
pos++;
}
}
顺序表缺陷:
顺序表优点:
支持随机访问
针对顺序表缺陷,就设计出链表。
链表优点:
链表缺点:
每一个数据,都要存一个指针去链接后面数据节点
不支持随机访问(用下标直接访问第i个)【比如二分,优化的快排等都要这个性质】
前言:
顺序表的缺陷:
- 空间不够需要扩容,扩容是有消耗的。
- 顺序表要求数据从开始位置连续存储,那么我们在头部或者中间位置插入删除数据就需要挪动数据,挪动数据是有消耗的
- 避免频繁扩容,一次一般都是按倍数去扩2倍。可能会存在一定空间的浪费。
针对顺序表缺陷,就设计出链表。
优点:
- 按需申请空间,不用了就释放空间(更合理地使用了空间)
- 头部中间插入删除数据,不需要挪动数据
缺点:
每一个数据,都要存一个指针去链接后面数据节点
不支持随机访问(用下标直接访问第i个)【比如二分,优化的快排等都要这个性质】
实际中要实现的链表的结构非常多样,以下情况组合起来就有8种链表结构:
单向、双向
带头、不带头
循环、非循环
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。在笔试面试中出现很多。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带很多优势,实现反而简单了。
逻辑结构:想象出来的,更形象,方便理解。
物理结构:
//无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入?
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置?
void SListEraseAfter(SListNode* pos);
//SList.h
#pragma once
#include
#include
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SLTNode;
void SListPrint(SLTNode* phead);
void SListPushBack(SLTNode** pphead, SLTDateType x);
#include \"SList.h\"
//这块也可以二级指针但没必要
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf(\"%d->\", cur->data);
cur = cur->next;
}
}
// 单链表尾插
// 尾节点的标志是next==NULL
// 注意由于开始的空节点要变成一个节点,因此要二级指针
void SListPushBack(SListNode** pphead, SLTDateType x){
STLNode* newnode =(STLNode*)malloc(sizeof(STLNode));
newnode->val=x;
newnode->next=NULL;
if(*pphead==NULL){
*pphead=newnode;
return;
}
//找到尾节点
SLTNode* tail=*pphead;
while(tail->next!=NULL){
tail=tail->next;
}
//
tail->next=newnode;
}
//但是空的时候 ->是解引用访问对应内存,开始时空的肯定崩掉。
注意这里存在实参和形参的问题。也就是老生常谈的值拷贝。
由于直接传指针只会进行指针的值赋值,要改变外面的指针变量需要在函数参数中传指针地址,参数中以二级指针接收来处理。
//改变不了实参i void fun(int i){ i=3; } //能改变实参i void fun(int* i){ *i=3; } //该表不了实参int* i void fun(int* i){ i=NULL; } //能改变实参int* i void fun(int** i){ *i=NULL; }
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
先想清楚问题:头删和尾删要不要二级指针
头删除要改变plist一定要。
尾巴删除到一个节点的时候就要二级指针了。
所以两个统一要
尾删处理前一个节点置NULL的方法:
但是两种方法都存在单个节点的缺陷问题
void SlistPopBack(STLNode** pphead){
STLNode* prev=NULL;
STLNode* tail=*pphead;
while(tail->next){
prev=tail;
tail=tail->next;
}
free(tail);
tail=NULL;
prev->next=NULL;
}
STLNode* tail=**pphead;
while(tail->next->next){
tail=tail->next;
}
free(tail->next);
tail->next=NULL;
所以要分类讨论链表为空,单个节点,多个节点
void SlistPopBack(STLNode** pphead){
assert(*pphead!=NULL);//判链表为空
STLNode* prev=NULL;
STLNode* phead=*pphead;
//一个节点
if((*pphead)->next==NULL){
free(*pphead);
*phead=NULL;
}//两个及多个节点
else{
while(tail->next){
prev=tail;
tail=tail->next;
}
free(tail);
tail=NULL;
prev->next=NULL;
}
}
同样类比头删,考虑一下链表为空,单个节点和两个及多个节点的情况
void SListPopFront(STLNode** pphead)
{
//空链表
assert( *(pphead)!=NULL );
//1个
if((*pphead)->Next==NULL){
free(*pphead);
*pphead=NULL;
}
else{
STLNode* phead=(*pphead)->next;
free(*pphead);
*pphead=phead;
}
}
void SListPopFront(STLNode** pphead)
{
//空链表
assert( *(pphead)!=NULL );
//1个及多个
STLNode* phead=(*pphead)->next;
free(*pphead);
*pphead=phead;
}
返回节点指针可以修改
SLTNode* SListFind(SLTNode* phead,STLDateType x){
SLTNode* cur = phead;
while(cur){
if(cur->data==x){
return cur;
}
else{
cur=cur->next;
}
}
return NULL;
}
void TestSList4(){
SLTNode* pos =SListFind(plist,2);
int i=1;
while(pos){
printf(\"第%d个pos节点:%p->%d\\n\",i++,pos,pos->data);
pos=SListFind(pos->next,2);
}
//第一个 3修改成30
pos=SListFind(plist,3);
if(pos)
{
pos->data=30;
}
SListPrint(plist);
}
大致有两种方式,第一种也是很多书上的方式
void SListInsert(SLTNode* phead,int pos,SLTDateType x){ };
这里采用第二种方式:在pos位置之前去插入一个节点。【这里遵循STL库forward_list的方式】
void SListInsert(SLTNode** phead,SLTNode* pos,SLTDateType x);
pos位置是find函数找的。
但是要注意如果搜到的元素是第一个元素,要转化成头插函数处理
void TestSList5()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
SListInsert(&plist, pos, 30);
}
SListPrint(plist);
}
void SListInsert(SLTNode** phead,SLTNode* pos,SLTDateType x)
{
assert(pos!=NULL);
STLNode* newnode=BuyListNode(x);
//找到pos的前一个位置
if(*pphead==pos){
SListPushFront(phead,x);
}
else{
STLNode* posPrev=*pphead;
while(posPrev->next!=pos)
{
posPrev=posPrev->next;
}
posPrev->next=newnode;
newnode->next=pos;
}u
}
但是前面插入比较麻烦,所以像后面STL里面实现的都是pos后面插入。一个是为了简便,第二个是为了节省一层 ${O(n)} $的常数(利用了find的O(n)查找一次)
//在pos的后面插入,这个更简单也更适合
void SListInsert_After(STLNode* pos,SLTDateType x){
assert(pos!=NULL);
STLNode* newnode=(STLNode*)malloc(sizeof(STLNode));
STLNode* tmp=pos->next;
pos->next=newnode;
newnode->next=tmp;
}
void SListErase(SLTNode** phead,SLTNode* pos){
STLNode* head=*SLTNode phead;
assert(head!=NULL);
if(head==pos){
*phead=head->next;
free(head);
//SListPopFront(pphead);复用!
}
else{
STLNode* prev=*STLNode phead;
while(prev->next!=pos){
prev=prve->next;
}
prev->next=pos->next;
free(pos);
}
}
虽然EraseAfter有点反直觉
void SListEraseAfter(SLTNode* phead,STLNode* pos){
assert(pos!=NULL);
assert(phead->next!=NULL)
STLNode* tmp=pos->next;
pos->next=pos->next->next;
free(tmp);
}
void SListDestroy(SLTNode** phead){
assert(phead);
STLNode* head=*phead;
while(head->next!=NULL){
STLNode* tmp=head;
head=head->next;
free(tmp);
}
*phead=NULL;
}
#include \"SList.h\"
void TestSList1()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
}
void TestSList2()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
//SListPopBack(&plist);
SListPrint(plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
}
void TestSList4()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 2);
SListPushFront(&plist, 4);
SListPushFront(&plist, 2);
SListPushFront(&plist, 2);
SListPushFront(&plist, 4);
SListPrint(plist);
// 找
SLTNode* pos = SListFind(plist, 2);
int i = 1;
while (pos)
{
printf(\"第%d个pos节点:%p->%d\\n\",i++, pos, pos->data);
pos = SListFind(pos->next, 2);
}
// 修改 3->30
pos = SListFind(plist, 3);
if (pos)
{
pos->data = 30;
}
SListPrint(plist);
}
void TestSList5()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
SListInsert(&plist, pos, 30);
}
SListPrint(plist);
pos = SListFind(plist, 1);
if (pos)
{
SListInsert(&plist, pos, 10);
}
SListPrint(plist);
pos = SListFind(plist, 4);
if (pos)
{
SListInsert(&plist, pos, 40);
}
SListPrint(plist);
}
//int main()
//{
// //TestSList1();
// //TestSList2();
// //TestSList3();
// //TestSList4();
// TestSList5();
//
//
// return 0;
//}
// Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* prev = NULL, *cur = head;
while (cur)
{
if (cur->val == val)
{
// 1、头删
// 2、中间删除
prev->next = cur->next;
free(cur);
cur = prev->next;
}
else
{
// 迭代往后走
prev = cur;
cur = cur->next;
}
}
return head;
}
int main()
{
// 方便快速调试oj代码
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
n1->val = 7;
n2->val = 7;
n3->val = 7;
n4->val = 7;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
struct ListNode* head = removeElements(n1, 7);
return 0;
}
单链表的缺陷还是很多的,单纯单链表的增删查改意义不大。
链表存储数据还是要用带头双向循环链表。
由于单链表的结构,所以要考虑
对于RE等报错的处理方法:
走读代码,画图对照样例
实在不行放VS调试(注意面试没有调试)
把oj定义的结构体注释删除
手动创建一个链表,malloc节点
样例板子如下:
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* prev = NULL, *cur = head;
while (cur)
{
if (cur->val == val)
{
// 1、头删
// 2、中间删除
prev->next = cur->next;
free(cur);
cur = prev->next;
}
else
{
// 迭代往后走
prev = cur;
cur = cur->next;
}
}
return head;
}
int main()
{
// 方便快速调试oj代码
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
n1->val = 7;
n2->val = 7;
n3->val = 7;
n4->val = 7;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
struct ListNode* head = removeElements(n1, 7);
return 0;
}
反转链表
//带头+双向+循环链表增删查改框架
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode * pos);
#pragma once
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}ListNode;
ListNode* BuyListNode(LTDataType x){
ListNode* node=(ListNode*)malloc(sizeof(ListNode));
node->next=node->prev=NULL;
node->data=x;
return node;
}
ListNode* ListInit(){
ListNode* phead=BuyListNode(0);
phead->next=phead;
phead->prev=phead;
}
//后期发现可以复用insert(phead,x);
void ListPushBack(ListNode* phead,LTDataType x){
assert(phead);
ListNode* tail=phead->prev;
ListNode* newNode=BuyListNode(x);
tail->next=newNode;
newNode->prev=tail;
newNode->next=phead;
phead->prev=newNode;
}
//后期发现可以复用insert(phead->next,x);
void ListPushFront(ListNode* phead,LTDataType x){
assert(phead);
ListNode* right=phead->next;
ListNode* newnode =BuyListNode(x);
phead->next=newcode;
newcode->prev=phead;
newcode->next=right;
right->prev=newcode;
}
///后期发现可以复用ListErase(phead-prev)
void ListPopBack(ListNode* phead){
assert(phead);
assert(phead->next!=phead);///保证数据不是头结点自己
ListNode* tail=phead->prev;
ListNode* right=tail->prev;
free(tail);
phead->prev=right;
right->next=phead;
}
//后期发现可以复用ListErease(phead->next);
void ListPopFront(ListNode* phead){
assert(phead);
assert(phead->next!=phead);//保证数据不是头节点自己
ListNode* de=head->next;
ListNode* ne=de->next;
free(de);
ne->prev=phead;
head->next=ne;
}
void ListPrint(ListNode* phead){
ListNode* cur=phead->next;
while(cur!=phead){
printf(\"%d \",phead->data);
cur=cur->next;
}printf(\"\\n\");
}
ListNode* Listfind(ListNode* phead,LTDataType x){
assert(phead);
ListNode* cur=phead->next;
while(cur!=phead){
if(cur->data==x){
return cur;
}
cur=cut->next;
}
}
void ListInsert(ListNode* pos,LTDataTyped x){
assert(pos);
ListNode* prev=pos->prev;
ListNode* newnode=BuyListNode(x);
prev->next=newnode;
newnode->prev=prev;
newnode->next=pos;
pos->prev=newnode;
}
void ListErase(ListNode* pos){
assert(pos);
ListNode* pre=pos->prev;
ListNode* next=pos->next;
pre->next=next;
next->prev=prev;
free(pos);
}
int ListEmpty();
int ListSize(ListNode* phead);
void ListDestroy(ListNode* phead){
assert(phead);
ListNode* cur=phead->next;
while(cur!=phead){
ListNode* next=cur->next;///提前保存
free(cur);
cur=next;
}
free(phead);
phead=NULL;//一级指针没用,这是临时变量
//1.传二级指针
//2.用完自己赋值NULL;保持接口的一致性
}
void TestList1()
{
ListNode* plist=ListInit();
ListPushBack(plist,1);
ListPushBack(plist,2);
ListPushBack(plist,3);
ListPushBack(plist,4);
ListPrint(plist);
}
void TestList2()
{
ListNode* plist=ListInit();
ListPushBack(plist,1);
ListPushBack(plist,2);
ListPushBack(plist,3);
ListPushBack(plist,4);
ListPrint(plist);
ListPushFront(plist,1);
ListPushFront(plist,2);
ListPushFront(plist,3);
ListPushFront(plist,4);
ListPrint(plist);
}
void TestList2(){
ListNode* plist=ListInit();
ListPushBack(plist,1);
ListPushBack(plist,2);
ListPushBack(plist,3);
ListPushBack(plist,4);
ListPushBack(plist,5);
ListPushBack(plist,6);
ListNode* pos=ListFind(plist,4);
if(pos){
ListInsert(pos,40);
}
ListPrint(plist);
}
顺序表:
优点:
缺点:
链表(双向带头循环链表)
优点:
缺点:
对于缓存结构:
假设不命中,一次加载20byte到缓存(具体加载多大取决硬件体系)
当访问数据的时候会先在cache里面找,找不到再去内存找。(即缓存不命中)
而顺序表的连续存储根据局部性原理命中率肯定是大于链表的。因为链表本身的空间存储都是不连续的,命中一块也不一定能命中另一块。根据替换算法还会造成缓存污染。
具体了解可以参考【https://coolshell.cn/articles/20793.html】
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持;O(n) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |