做企业营销网站,WordPress个性萌化插件,温州网站建设首选国鼎网络,wordpress去掉购物车顺序表#xff0c;好像学C语言时从来没听过#xff0c;实际上就是给数组穿了层衣服#xff0c;本质是一模一样的。 这里的顺序表实际是定义了一个结构体#xff0c;设计各种函数来实现它的功能#xff0c;比如说数组中的增删改查插入#xff0c;这些基本操作其实平时就会…顺序表好像学C语言时从来没听过实际上就是给数组穿了层衣服本质是一模一样的。 这里的顺序表实际是定义了一个结构体设计各种函数来实现它的功能比如说数组中的增删改查插入这些基本操作其实平时就会在使用数组的时候用到。 那么今天就带你深度剖析线性表数组的底层原理 这节知识只是个开胃菜但也属于要必备的知识所以各位同学不要松懈哦
引入
顺序表有静态的也有动态的
静态顺序表静无非就是初始化这个静态表后这个静态表的空间就不能变化了例如 struct SeqList
* {
* int arr[20];
* int size;
* };当初始化线性表后这个数组存的数据就不能更改了那有人会想我用个宏常量替换数组的大小到时后想扩大或缩小更改宏常量就行了 #define N 20 int arr[N];这个想法不错但也只能在线性表初始化之前更改如果你初始化后你正在使用线性表的功能时内存不够用了怎么办
那么接下来我所编写的代码就是动态顺序表当你不够用内存的时候会自动给你开辟当看到这里如果前面【C语言进阶】— 动态内存管理你看过那接下来的知识易如反掌甚至不用看我对代码的注释就可以清楚没看过的朋友强烈推荐很重要数据结构会经常用到这篇的知识 1. 顺序表在内存中的存储方式
是一块连续的内存 2. 顺序表的定义
这里是用结构体定义了一个顺序表类型
typedef int SeqListType;//因为顺序表中存储的数据不见得都是int型也可能是别的类型数据所以,想存放别的数据时只需把int换成你想存的数据的类型//动态顺序表
typedef struct SeqList
{SeqListType* data;//指针指向的是SeqListType这个类型的数据int size;//记录当前有效储存数据的个数int capacity;//data开辟数组空间的容量
}SeqList;初始化、销毁、打印功能
//初始化顺序表开辟空间赋初值
void SLInit(SeqList* ps)
{//开辟一块大小为sizeof(SeqListType) * 4的内存并把首地址传给指针ps-dataps-data (SeqListType*)malloc(sizeof(SeqListType) * 4);if (ps-data NULL){perror(malloc);return;}ps-size 0;ps-capacity 4;
}
//销毁空间因为是在堆区开辟的数据用完要用free函数释放
void SLDestory(SeqList* ps)
{free(ps-data);ps-data NULL;ps-size 0;ps-capacity 0;
}void SLPrint(SeqList* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-data[i]);}printf(\n);
}3. 顺序表的功能实现
扩容功能先跳过看头插法
//检查容量不足顺便扩容
void CheckCapacity(SeqList* ps)
{if (ps-capacity ps-size){//用realloc给ps-data开辟一个原来2倍的空间SeqListType* new_ps (SeqListType*)realloc(ps-data,sizeof(SeqListType)*ps-capacity * 2);if (new_ps ! NULL)//判断返是否开辟成功若为NULL则开辟失败{ps-data new_ps;new_ps NULL;ps-capacity * 2;}else{perror(realloc);return;}}
}3.1 头插法、尾插法
//头插法
void SLPushFront(SeqList* ps, SeqListType x)
{//检查目前容量不足就扩容CheckCapacity(ps);for (int i ps-size - 1; i 0; i--){ps-data[i 1] ps-data[i];}ps-data[0] x;ps-size;
}//尾插法
void SLPushBack(SeqList* ps, SeqListType x)
{CheckCapacity(ps);ps-data[ps-size] x;ps-size;
}3.2 头删法、尾删法
//头删法
void SLPopFront(SeqList* ps)
{//这里断言的原因是如果ps是空指针for循环条件判断就会访问空指针assert(ps ! NULL);
//*****************当size0时也会执行ps-size--,后续可能会造成越界访问***************assert(ps-size 0);for (int i 1; i ps-size; i){ps-data[i - 1] ps-data[i];}ps-size--;
}
//尾删法
void SLPopBack(SeqList* ps)
{assert(ps ! NULL);assert(ps-size 0);ps-size--;
}3.3 给指定位置插入数据
void SLInsert(SeqList* ps, int position, SeqListType x)
{assert(ps ! NULL);//判断给的位置是否越界若越界程序执行完会告诉你这里出的问题assert(position 1 position ps-size);CheckCapacity(ps);for (int i ps-size - 1; i position - 1; i--){ps-data[i 1] ps-data[i];}ps-data[position - 1] x;ps-size;
}3.4 指定位置删除数据
void SLErase(SeqList* ps, int position)
{assert(ps ! NULL);assert(position 1 position ps-size);assert(ps-size 0);for (int i position; i ps-size; i){ps-data[i - 1] ps-data[i];}ps-size--;
}3.5 查找指定数据
int SLFind(SeqList* ps, SeqListType x)
{assert(ps ! NULL);for (int i 0; i ps-size; i){if (ps-data[i] x)return i;}return -1;
}4.顺序表的优缺点
4.1 优点
因为它跟数组一样可以进行下表访问所以当你要查询数据时时间复杂度为O(1)是常数级访问速度很快很方便这与它的内存是一片连续的内存密切相关因为当你访问数组下标为i的数据时arr[i]本质是*(arri)首元素地址i解引用
4.3 缺点
也正因它的内存是连续的所以当你要删除、插入数据时必须要移动后面的数据时间复杂度是O(N)级别的。
5 完整代码
5.1 头文件 SeqList.h 中的代码
#pragma once#includestdio.h
#includestdlib.h
#includeassert.htypedef int SeqListType;//动态顺序表
typedef struct SeqList
{SeqListType* data;int size;int capacity;
}SeqList;//初始化顺序表
void SLInit(SeqList* ps);
//销毁顺序表
void SLDestory(SeqList* ps);
//打印顺序表
void SLPrint(SeqList* ps);
//头插法插入数据
void SLPushFront(SeqList* ps, SeqListType x);
//尾插法
void SLPushBack(SeqList* ps, SeqListType x);
//头删法
void SLPopFront(SeqList* ps);
//尾删法
void SLPopBack(SeqList* ps);
//指定位置插入数据
void SLInsert(SeqList* ps, int position, SeqListType x);
//指定位置删除
void SLErase(SeqList* ps, int position);
//查找数据
int SLFind(SeqList* ps, SeqListType x);5.2 函数实现的文件 SeqList.c
#define _CRT_SECURE_NO_WARNINGS#includeSeqList.hvoid SLInit(SeqList* ps)
{ps-data (SeqListType*)malloc(sizeof(SeqListType) * 4);if (ps-data NULL){perror(malloc);return;}ps-size 0;ps-capacity 4;
}void SLDestory(SeqList* ps)
{free(ps-data);ps-data NULL;ps-size 0;ps-capacity 0;
}void SLPrint(SeqList* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-data[i]);}printf(\n);
}//检查容量不足顺便扩容
void CheckCapacity(SeqList* ps)
{if (ps-capacity ps-size){//用realloc给ps-data开辟一个原来2倍的空间SeqListType* new_ps (SeqListType*)realloc(ps-data,sizeof(SeqListType)*ps-capacity * 2);if (new_ps ! NULL){ps-data new_ps;new_ps NULL;ps-capacity * 2;}else{perror(realloc);return;}}
}void SLPushFront(SeqList* ps, SeqListType x)
{//检查目前容量不足就扩容CheckCapacity(ps);for (int i ps-size - 1; i 0; i--){ps-data[i 1] ps-data[i];}ps-data[0] x;ps-size;}
//尾插法
void SLPushBack(SeqList* ps, SeqListType x)
{CheckCapacity(ps);ps-data[ps-size] x;ps-size;
}void SLPopFront(SeqList* ps)
{//这里断言的原因是如果ps是空指针for循环条件判断就会访问空指针assert(ps ! NULL);
//*****************当size0时也会执行ps-size--,后续可能会造成越界访问***************assert(ps-size 0);for (int i 1; i ps-size; i){ps-data[i - 1] ps-data[i];}ps-size--;
}
//尾删法
void SLPopBack(SeqList* ps)
{assert(ps ! NULL);assert(ps-size 0);ps-size--;
}void SLInsert(SeqList* ps, int position, SeqListType x)
{assert(ps ! NULL);assert(position 1 position ps-size);CheckCapacity(ps);for (int i ps-size - 1; i position - 1; i--){ps-data[i 1] ps-data[i];}ps-data[position - 1] x;ps-size;
}void SLErase(SeqList* ps, int position)
{assert(ps ! NULL);assert(position 1 position ps-size);assert(ps-size 0);for (int i position; i ps-size; i){ps-data[i - 1] ps-data[i];}ps-size--;
}int SLFind(SeqList* ps, SeqListType x)
{assert(ps ! NULL);for (int i 0; i ps-size; i){if (ps-data[i] x)return i;}return -1;
}这两套代码不能直接运行主函数int main(){}中的内容自己写就剩调用函数了让自己动动手敲几行代码吧好的程序员一定是需要实践的尽管顺序表这一节相对不难但里面有些边界值的判断只有你亲手敲代码的时候才能真正进入思考加油各位
