网站手机版管理链接,网站做专业团队,开源网站程序,交易平台网站程序描述
顺序表我们可以把它想象成在一个表格里面填数据#xff0c;并对数据做调整#xff1b; 那我们的第一个问题是#xff1a;怎么样在创建出足够的空间呢#xff1f;
我们可以去堆上申请#xff0c;用一个指针指向一块空间#xff0c;如果申请的空间不够#xff0c;我…描述
顺序表我们可以把它想象成在一个表格里面填数据并对数据做调整 那我们的第一个问题是怎么样在创建出足够的空间呢
我们可以去堆上申请用一个指针指向一块空间如果申请的空间不够我们可以再realloc申请出来。 我们的第二个问题是怎么样标记我们用了多少空间呢
这时我们就需要一个变量来记录我们当前的用到第几个“格子”即用了多少空间我们这里用size来表示 我们的第三个问题是怎么样知道我们有空间呢
这时我们就需要一个变量来记录我们“格子”总数即拥有多少空间我们这里用capacity来表示 所以在.h文件中我们线性表的结构体描述为 typedef int SLDataType;typedef struct SeList
{SLDataType* a;int size;int capacity;
}SL;组织
初始化释放尾插尾删头插头删指定位置删除指定位置插入查找指定元素
1.初始化
把我们描述出来的顺序表结构体里的变量初始化
在.h文件中 因为要对创建出来的结构体里的内容进行修改所以函数要进行传址调用
在.c文件中:
我们用malloc来开辟空间,同时注意检查malloc
因为我们刚刚开辟空间并没有往顺序表里增删查改 所以此时size为0
而我们的capacity就是在malloc开辟的空间大小。 void SLInit(SL* ps)
{assert(ps-a);ps-a (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps-a NULL){perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}
2.释放
将描述出来的顺序表结构体里的变量逐个进行释放
在.h 文件中 在.c文件中
首先是指针a需要使用free函数将其释放还需要注意的是free后需要将a置空避免出现野指针
因为size和capacity是临时变量储存在栈上函数调用结束后会自动释放我们这里把它改为0就可以了。 void SLDestroy(SL* ps)
{assert(ps-a);free(ps-a);ps-a NULL;ps-capacity 0;ps-size 0;
}
3.尾插
向顺序表的尾部插入数据
在.h 文件中 在.c文件中
尾插数据时首先需要判断capacity空间是否足够如果不够需要扩容这里我们写个扩容函数 扩容我们用realloc函数最后要返回ps至尾插函数判断是否为空
接着才能将数据尾插
最后别忘了调整size的位置 SL* SLExpand(SL* ps)
{assert(ps-a);if (ps-size ps-capacity){SLDataType* tmp (SLDataType*)realloc(ps-a, sizeof(SLDataType)* ps-capacity*2);if (tmp NULL){perror(realloc fail);return NULL;}ps-capacity *2;ps-a tmp;}return ps;
}void SLPushBack(SL* ps,SLDataType x)
{assert(ps-a);//扩容if (ps-size ps-capacity){SL* ret SLExpand(ps);if (ret NULL){return;}}ps-a[ps-size] x;ps-size;} 4.尾删
将顺序表的尾部删除
在.h 文件中 在.c 文件中
因为顺序表是从开始连续存储size个数据不能单独释放那一块区域所以我们直接将size--就可以了如果往后插入的话就直接把数据覆盖
assert如果当capacity为空的时候还尾删时会报错,并且终止程序 void SLPopBack(SL* ps)
{assert(ps-a);ps-size--;
}
5.头插
向顺序表的头部插入数据
在.h 文件中 在.c 文件中
首先我们得先判断空间是否足够如果不够就扩容
第二步把数据往后移一位数据从最后一位开始向后移动 第三步进行数据头插别忘了把size的大小改改 void SLPushFront(SL* ps, SLDataType x)
{assert(ps-a);//扩容if (ps-size ps-capacity){SL* ret SLExpand(ps);if (ret NULL){return;}}//移动数据for (int i ps-size; i 0 ; i--){ps-a[i] ps-a[i - 1];}//头插ps-a[0] x;ps-size;}
6.头删
将顺序表的头部数据删除
在.h 文件中 在.c 文件中
我们只需要将从第二位数据开始往前移动把前一位的数据覆盖就可以达到头删的效果 void SLPopFront(SL* ps)
{assert(ps-a);assert(ps-size 0);for (int i 0; i ps-size; i){ps-a[i] ps-a[i 1];}ps-size--;
}
7.指定位置删除
将顺序表的指定位置数据删除
在.h 文件中 在.c 文件中
首先要先用assert检查一下空间和size的值是否合理
如果删除的数据是最后一个就直接尾删
如果如果删除的数据不是最后一个就需要移动数据覆盖类似于头删 void SLErase(SL* ps, int pos)
{assert(ps-a);assert(pos 0posps-size);//如果pos是最后一个数据尾删if (pos ps-size - 1){SLPopBack(ps);}else{for (int i pos; i ps-size; i){ps-a[i] ps-a[i 1];}ps-size--;}}
8.指定位置插入
将顺序表的指定位置数据插入
在.h 文件中 在.c 文件中
首先要先用assert检查一下空间和size的值是否合理
如果删除的数据是最后一个就直接尾插
如果如果删除的数据不是最后一个就需要移动数据再插入数据类似于头插 void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps-a);assert(pos 0 pos ps-size);//判断容量if (ps-size ps-capacity){SL* ret SLExpand(ps);if (ret NULL){return;}}//尾插if (pos ps-size - 1){SLPushBack(ps,x);}else{for (int i ps-size; i pos; i--){ps-a[i] ps-a[i - 1];}ps-size;ps-a[pos] x;}
}
9.查找指定元素
在顺序表中查找指定数据并输出其下表和在该表中的个数
在.h 文件中 在.c 文件中
for循环遍历一下顺序表如果遍历过程中找到了直接打印其下标并用一个变量记录它出现的此数。
出循环后打印其和在该表中出现的个数。 void SLFindPoint(SL* ps, SLDataType x)
{assert(ps-a);int cnt 0;for (int i 0; i ps-size; i){if (ps-a[i] x){cnt;printf(找到了第%d个下标为:%d\n,cnt, i);}}if (cnt 0){printf(抱歉无该数据\n);}else{printf(共找到%d个数据\n, cnt);}
}
整个程序
.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
#includestring.htypedef int SLDataType;
#define INIT_CAPACITY 4typedef struct SeList
{SLDataType* a;int size;int capacity;
}SL;void SLPrint(SL* ps);void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLErase(SL* ps,int pos);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLFindPoint(SL* ps, SLDataType x);
.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqlist.hvoid SLPrint(SL* ps)
{assert(ps-a);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}void SLInit(SL* ps)
{assert(ps-a);ps-a (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps-a NULL){perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}void SLDestroy(SL* ps)
{assert(ps-a);free(ps-a);ps-a NULL;ps-capacity 0;ps-size 0;
}SL* SLExpand(SL* ps)
{assert(ps-a);if (ps-size ps-capacity){SLDataType* tmp (SLDataType*)realloc(ps-a, sizeof(SLDataType)* ps-capacity*2);if (tmp NULL){perror(realloc fail);return NULL;}ps-capacity *2;ps-a tmp;}return ps;
}void SLPushBack(SL* ps,SLDataType x)
{assert(ps-a);//扩容if (ps-size ps-capacity){SL* ret SLExpand(ps);if (ret NULL){return;}}ps-a[ps-size] x;ps-size;}void SLPopBack(SL* ps)
{assert(ps-a);ps-size--;
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps-a);//扩容if (ps-size ps-capacity){SL* ret SLExpand(ps);if (ret NULL){return;}}//移动数据for (int i ps-size; i 0 ; i--){ps-a[i] ps-a[i - 1];}//头插ps-a[0] x;ps-size;}void SLPopFront(SL* ps)
{assert(ps-a);assert(ps-size 0);for (int i 0; i ps-size; i){ps-a[i] ps-a[i 1];}ps-size--;
}void SLErase(SL* ps, int pos)
{assert(ps-a);assert(pos 0posps-size);//如果pos是最后一个数据尾删if (pos ps-size - 1){SLPopBack(ps);}else{for (int i pos; i ps-size; i){ps-a[i] ps-a[i 1];}ps-size--;}}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps-a);assert(pos 0 pos ps-size);//判断容量if (ps-size ps-capacity){SL* ret SLExpand(ps);if (ret NULL){return;}}//尾插if (pos ps-size - 1){SLPushBack(ps,x);}else{for (int i ps-size; i pos; i--){ps-a[i] ps-a[i - 1];}ps-size;ps-a[pos] x;}
}void SLFindPoint(SL* ps, SLDataType x)
{assert(ps-a);int cnt 0;for (int i 0; i ps-size; i){if (ps-a[i] x){cnt;printf(找到了第%d个下标为:%d\n,cnt, i);}}if (cnt 0){printf(抱歉无该数据\n);}else{printf(共找到%d个数据\n, cnt);}
}
