网站内页检测,柳州网站建设推荐,亚马逊雨林原始部落,个人博客网站建设选题说明文章目录前言初始化顺序表打印顺序表检查容量判空顺序表数据个数尾部插入尾部删除头部插入头部删除在pos位置插入数据删除pos位置的数据查找数据修改数据销毁顺序表整体代码写在最后前言 顺序表作为数据结构中的小小弟#xff0c;还是很好应付的。说到数据结构#xff0c;顺序…
文章目录前言初始化顺序表打印顺序表检查容量判空顺序表数据个数尾部插入尾部删除头部插入头部删除在pos位置插入数据删除pos位置的数据查找数据修改数据销毁顺序表整体代码写在最后前言 顺序表作为数据结构中的小小弟还是很好应付的。说到数据结构顺序表是我们的向导它让你明白数据结构到底是干啥的为啥数据结构这么的重要。 实际上通讯录的底层就是一个顺序表里面的增添联系人删除联系人等一系列操作都是基于顺序表实现的这也侧面拖出了数据结构的作用。所以学好数据结构是必须的。 要是能够自主实现通讯录我肯定顺序表学起来会非常的轻松。 初始化顺序表
实现顺序表需要三个文件一个是.h为后缀的头文件SeqList.h用来放相关头文件宏定义结构体声明以及函数声明。一个是.c为后缀的C文件SeqList.c用来实现函数接口。还有一个是.c为后缀的C文件test.c用来测试代码。我们只要在SeqList.c文件和test.c文件最上面包含一下 SeqList.h文件整个程序链接就OK了。
下面是所需头文件宏定义以及顺序表的定义的代码
// 防止SeqList.h被重复包含
#pragma once// 所需头文件
// 输入输出所需头文件
#include stdio.h
// reallocfree所需头文件
#include stdlib.h
// 判空所需头文件
#include stdbool.h
// assert断言所需头文件
#include assert.h// 初始化容量每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;// 顺序表
typedef struct SeqList
{// a指向一个在堆上的空间就是顺序表SLDateType* a;// 顺序表数据个数int size;// 顺序表容量int capacity;
}SL; // typedef将struct SeqList重新命名为SL定义好主体后首先是对顺序表初始化。可以看到上面的结构体也就是顺序表里面的成员都是未初始化的所以第一步就是将他们初始化这里引出一个初始化函数接口下面是相关功能代码实现
// 初始化顺序表
void SLInit(SL* ps)
{// 这里断言是防止ps为一个空指针传个NULL直接暴打assert(ps);ps-a NULL;ps-size 0;ps-capacity 0;
}打印顺序表 该接口放在前面实现是为了后面能够更好的测试通过对顺序表的数据的一个直观的展现我们可以及时发现某些接口的bug。 顺序表的结构体中定义了一个size这里size的作用就体现出来了当然size的作用很大不止是这里我们可以通过size来对顺序表中的数据顺序打印
// 打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i) printf(%d , ps-a[i]);printf(\n);
}检查容量 当我们在顺序表中插入数据时一定要检查容量够不够用如果不够的话再插入数据就会出现非法访问空间的问题此时程序会报错因此这里要扩容。 由于size是统计数据个数的所以只要size等于capacity就说明当前的容量已经满了需要扩容。由于初始化顺序表时没有分配空间所以当我们第一次插入数据的时候就要扩容每次扩容增加的容量大小为INIT_CAPACITY(8)而每增容一次capacity就要更新一次。
下面是相关功能代码实现
// 检查容量
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){int newcapacity ps-capacity 0 ? INIT_CAPACITY : ps-capacity INIT_CAPACITY;// 开始没有空间其功能相当于mallocSLDateType* tmp (SLDateType*)realloc(ps-a, sizeof(SLDateType) * newcapacity);assert(tmp);ps-a tmp;ps-capacity newcapacity;}
}这一步实现后每次插入数据就要引用该函数检查一下容量。 判空
判空很容易理解这里如果通讯录为空返回真不为空返回假。
下面是相关功能代码实现
// 判空
bool SLEmpty(SL* ps)
{assert(ps);return ps-size 0;
}顺序表数据个数
该功能只要返回size就ok啦。
// 顺序表数据个数
int SLSize(SL* ps)
{assert(ps);return ps-size;
} 尾部插入
尾部插入就是在最末尾插入数据首先当然是要检查一下容量然后将要插入的数据插入进去最后size计数一次该函数的功能就OK啦。
下面是相关功能代码实现
void SLPushBack(SL* ps, SLDateType x)
{assert(ps);SLCheckCapacity(ps);ps-a[ps-size] x;
}尾部删除 如果顺序表中没有数据那还删个啥呢直接assert暴打也就是判断一下size是否大于0(判空一下)。 尾部删除实际上只要size减一就可以了至于删除的那个数据改不改为0都无所谓因为打印不会打印到那个数据还有就是不能在那个位置释放空间free,这是规定不允许的要有占着茅坑不拉屎的原则。
下面是相关功能代码实现
void SLPopBack(SL* ps)
{assert(ps !SLEmpty(ps));ps-size--;
}头部插入 对顺序表头部的操作相比于尾部的操作麻烦的多主要是因为顺序表是一段连续的空间在头部插入或者删除需要挪动后面的数据这样以来整个程序的效率也会降低但这是没办法的该挪动还是嘚挪动不然怎么进行操作对吧。顺序表最明显的缺点 挪动的时候只要从后面开始依次将每一个数据向后挪动一位直到将第一个数据挪动完停止挪动再将要插入的数据放在头部即可这里需要注意以下边界问题。 当然size要计数一次可不敢忘记了。
下面是相关功能代码实现
void SLPushFront(SL* ps, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i 0; i--) ps-a[i] ps-a[i - 1];ps-a[0] x;ps-size;
}头部删除 只要是删除就要assert判断是否要暴打。 有了头部插入的经验头部删除显得游刃有余了相反的只要将每个数据向前挪动也就是依次覆盖即可最终第一个数据被覆盖的无影无踪。 当然size要减一可不敢忘记了。
下面是相关功能代码实现
void SLPopFront(SL* ps)
{assert(ps !SLEmpty(ps));for (int i 0; i ps-size - 1; i) ps-a[i] ps-a[i 1];ps-size--;
}在pos位置插入数据 首先插入需要检查容量。 在pos位置插入数据首先对这个pos理解一下本章的pos不是下标注意他不是下标而是规规矩矩的第几个位置比如一串数列1234第一个位置就是只1所占的位置如果要在第一个位置插入那么1就会到当前的2的位置上去也就是所谓的第二个位置。所以这个pos是以用户角度出发但我们实现函数的时候要脑子清醒我们操作的实际上是下标。 同样的与头插差不多都是要挪动数据只不过挪动的数据范围不同要操作的数的位置也不同这也就更加要注意边界问题了。 当然操作完成后要记得size计数一次噢。
下面是相关功能代码实现
// 在pos位置插入,pos表示在第几个位置插入不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i pos - 1; i--) ps-a[i] ps-a[i - 1];ps-a[pos - 1] x;ps-size;
}有了该函数之后前面的头插尾插都可以复用这个函数。 删除pos位置的数据 既然是删除首先就要来一套assert检查看是否要毒打。 删除就是将pos后面的数据依次往前挪最终pos这个位置上的数据会被覆盖因为会挪动数据依次效率也不是很高。 当然别忘了size减一噢。
下面是相关功能代码实现
// 删除第pos个数据pos不是下标表示删除第几个
void SLErase(SL* ps, int pos)
{assert(ps !SLEmpty(ps) pos 0 pos ps-size);for (int i pos - 1; i ps-size - 1; i) ps-a[i] ps-a[i 1];ps-size--;
}有了该函数后前面的头删尾删都可以复用这个函数。 查找数据
查找数据就是遍历一遍顺序表如果找到了就返回下标加一没找到就返回-1。
下面是相关功能代码实现
// 查找数据返回正常对应位置不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{assert(ps);for (int i 0; i ps-size; i)if (ps-a[i] val) return i 1;return -1;
}修改数据 修改数据也是根据pos位置来修改的传入你想修改的位置然后传入修改后的新数据然后直接在pos - 1(下标)位置修改不需要遍历。 如果传入的pos不正确直接暴打。 当然也可以先查找在修改也就是说查找数据和修改数据两个接口函数可以一起用。
**下面是相关功能代码实现**c
// 修改数据,修改pos正常对应位置不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{assert(ps pos 0 pos ps-size);ps-a[pos - 1] Mval;
}销毁顺序表
由于向堆申请了空间因此程序结束后需要将空间返还给系统这里说的粗暴了点销毁顺序表。
下面是相关功能代码实现
// 销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps-a);ps-capacity 0;ps-size 0;
}整体代码
SeqList.h
// 防止SeqList.h被重复包含
#pragma once// 所需头文件
// 输入输出所需头文件
#include stdio.h
// reallocfree所需头文件
#include stdlib.h
// 判空所需头文件
#include stdbool.h
// assert断言所需头文件
#include assert.h// 初始化容量每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;// 顺序表
typedef struct SeqList
{// a指向一个在堆上的空间就是顺序表SLDateType* a;// 顺序表数据个数int size;// 顺序表容量int capacity;
}SL; // typedef将struct SeqList重新命名为SL// 初始化顺序表
void SLInit(SL* ps);
// 打印顺序表
void SLPrint(SL* ps);// 检查容量
void SLCheckCapacity(SL* ps);// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);
// 在pos位置插入,pos表示在第几个位置插入不是下标
void SLInsert(SL* ps, int pos, SLDateType x);
// 删除第pos个数据pos不是下标表示删除第几个
void SLErase(SL* ps, int pos);// 查找数据返回对应位置不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val);
// 修改数据
void SLModify(SL* ps, int pos, SLDateType Mval);// 判空
bool SLEmpty(SL* ps);
// 顺序表数据个数
int SLSize(SL* ps);// 使用了realloc在堆上申请了空间程序结束时要返还空间给系统
// 销毁顺序表
void SLDestroy(SL* ps);
SeqList.c
#include SeqList.h// 初始化顺序表
void SLInit(SL* ps)
{assert(ps);ps-a NULL;ps-size 0;ps-capacity 0;
}
// 打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i) printf(%d , ps-a[i]);printf(\n);
}// 检查容量
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){int newcapacity ps-capacity 0 ? INIT_CAPACITY : ps-capacity INIT_CAPACITY;// 开始没有空间其功能相当于mallocSLDateType* tmp (SLDateType*)realloc(ps-a, sizeof(SLDateType) * newcapacity);assert(tmp);ps-a tmp;ps-capacity newcapacity;}
}// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x)
{//assert(ps);//SLCheckCapacity(ps);//ps-a[ps-size] x;SLInsert(ps, ps-size 1, x);
}
void SLPopBack(SL* ps)
{//assert(ps !SLEmpty(ps));//ps-size--;SLErase(ps, ps-size);
}
void SLPushFront(SL* ps, SLDateType x)
{//assert(ps);//SLCheckCapacity(ps);//for (int i ps-size; i 0; i--) ps-a[i] ps-a[i - 1];//ps-a[0] x;//ps-size;SLInsert(ps, 1, x);
}
void SLPopFront(SL* ps)
{//assert(ps !SLEmpty(ps));//for (int i 0; i ps-size - 1; i) ps-a[i] ps-a[i 1];//ps-size--;SLErase(ps, 1);
}
// 在pos位置插入,pos表示在第几个位置插入不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i pos - 1; i--) ps-a[i] ps-a[i - 1];ps-a[pos - 1] x;ps-size;
}
// 删除第pos个数据pos不是下标表示删除第几个
void SLErase(SL* ps, int pos)
{assert(ps !SLEmpty(ps) pos 0 pos ps-size);for (int i pos - 1; i ps-size - 1; i) ps-a[i] ps-a[i 1];ps-size--;
}// 查找数据返回正常对应位置不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{assert(ps);for (int i 0; i ps-size; i)if (ps-a[i] val) return i 1;return -1;
}
// 修改数据,修改pos正常对应位置不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{assert(ps pos 0 pos ps-size);ps-a[pos - 1] Mval;
}// 判空
bool SLEmpty(SL* ps)
{assert(ps);return ps-size 0;
}
// 顺序表数据个数
int SLSize(SL* ps)
{assert(ps);return ps-size;
}// 销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps-a);ps-capacity 0;ps-size 0;
}test.c
#include SeqList.hvoid test1()
{SL s;SLInit(s);SLPushBack(s, 1);SLPrint(s);SLPushBack(s, 2);SLPrint(s);SLPushBack(s, 3);SLPrint(s);SLPushBack(s, 4);SLPrint(s);SLPushBack(s, 5);SLPrint(s);SLPushBack(s, 6);SLPrint(s);SLDestroy(s);
}void test2()
{SL s;SLInit(s);SLPushFront(s, 1);SLPrint(s);SLPushFront(s, 2);SLPrint(s);SLPushFront(s, 3);SLPrint(s);SLPushFront(s, 4);SLPrint(s);SLPushFront(s, 5);SLPrint(s);SLPushFront(s, 6);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLDestroy(s);
}void test3()
{SL s;SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushBack(s, 3);SLPushBack(s, 4);SLPushBack(s, 5);SLPrint(s);SLInsert(s, 3, 99999);SLPrint(s);SLErase(s, 3);SLPrint(s);SLModify(s, SLFind(s, 3), 99999);SLPrint(s);SLDestroy(s);
}int main()
{//test1();//test2();test3();return 0;
}写在最后 学到这里数据结构总算是入门了当然数据结构后面还有很长的路要走要继续努力 感谢阅读本小白的博客错误的地方请严厉指出噢
