广州网站建设商城,网站建设公司潍坊,做网站怎么招广告,wordpress博客好用吗个人主页 水月梦镜花 个人专栏 C语言 #xff0c;数据结构 文章目录 一、顺序表二、实现思路1.存储结构2.初始化顺序表(SeqListInit)3.销毁顺序表(SeqListDestroty)4.打印顺序表(SeqListPrint)5.顺序表尾插(SeqListPushBack)and检查容量(SeqListCheckCapacity)6.顺序表头插(Se… 个人主页 水月梦镜花 个人专栏 C语言 数据结构 文章目录 一、顺序表二、实现思路1.存储结构2.初始化顺序表(SeqListInit)3.销毁顺序表(SeqListDestroty)4.打印顺序表(SeqListPrint)5.顺序表尾插(SeqListPushBack)and检查容量(SeqListCheckCapacity)6.顺序表头插(SeqLsitPushFront)7.顺序表尾删(SeqListPopBack)8.顺序表头删(SeqListPopFront)9.顺序表查找(SeqListFind)10.在pos位置前插入元素(SeqListInsert)11.删除pos位置的值(SeqListErase) 三、代码实现总结 一、顺序表
顺序表是用一段物理结构连续的存储单元依次存储数据元素的线性结构一般采用数组存储。 顺序表一般分为两种
静态顺序表使用定长数组实现动态顺数表使用动态开辟的数组实现
本篇文章顺序表是使用动态开辟的数组实现(动态顺序表)。要实现的功能如下
//初始化顺序表
void SeqListInit(SeqList* ps);//销毁顺序表
void SeqListDestroty(SeqList* ps);//打印顺序表
void SeqListPrint(SeqList* ps);//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDateType x);//顺序表尾删
void SeqListPopBack(SeqList* ps);//顺序表头删
void SeqListPopFront(SeqList* ps);//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDateType x);//删除pos位置的值
void SeqListErase(SeqList* ps, int pos);//检查容量
void SeqListCheckCapacity(SeqList* ps);二、实现思路
画图理解起来更佳
1.存储结构
我们重命名int类型为SLDataType方便以后我们修改顺序表存储元素的类型。 指针data指向动态开辟的空间变量sz记录有效的数据元素变量capacity记录动态开辟空间的大小。
typedef int SLDataType;typedef struct SeqList
{SLDataType* data;int sz;int capacity;
}SeqList;2.初始化顺序表(SeqListInit)
动态开辟一块空间用data指针保存空间首地址。 此时data指向空间中有效元素为0使sz 0变量capacity在等于此时开辟空间的大小。
#define SIZE 4void SeqListInit(SeqList* ps)
{ps-data (SLDataType*)malloc(sizeof(SLDataType) * SIZE);if (ps-data NULL){perror(malloc);exit(-1);}ps-sz 0;ps-capacity SIZE;
}3.销毁顺序表(SeqListDestroty)
free所开辟的空间使data NULL此时数据有效元素为0空间大小为0那么sz 0capacity 0
//销毁顺序表
void SeqListDestroty(SeqList* ps)
{assert(ps);//free(ps);free(ps-data);ps-data NULL;ps-sz 0;ps-capacity 0;
}4.打印顺序表(SeqListPrint)
这个函数非常简单只要遍历一遍所开辟的空间即可注意范围是(0sz)。
//打印顺序表
void SeqListPrint(SeqList* ps)
{assert(ps);for (int i 0; i ps-sz; i){printf(%d , ps-data[i]);}printf(\n);}5.顺序表尾插(SeqListPushBack)and检查容量(SeqListCheckCapacity)
每次加入数据时我们要先检查空间大小是否充足再加入数据 检查容量 在尾插数据前要检查空间大小是否充足(sz capacity)如果空间大小不够要扩大空间大小capacity记录新的空间大小。 尾插元素 变量sz不仅代表空间有效元素个数也代表了新数据元素将要放入的位置。所以尾插元素只要空间大小充足那么在data[sz]处放入数据即可不要忘记sz要加一。
//检查容量
void SeqListCheckCapacity(SeqList* ps)
{SLDataType* tmp (SLDataType*)realloc(ps-data, sizeof(SLDataType) * ps-capacity * 2);if (tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capacity * 2;
}//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{assert(ps);if (ps-sz ps-capacity){SeqListCheckCapacity(ps);}ps-data[ps-sz] x;ps-sz;
}6.顺序表头插(SeqLsitPushFront)
顺序表除了尾插尾删不用挪到数据其它的增删都要挪到数据。 头插数据要先检查空间大小再向后挪到数据将数据放入data[0]处sz在加一。
//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDataType x)
{assert(ps);if (ps-sz ps-capacity){SeqListCheckCapacity(ps);}int end ps-sz;while (end 0){ps-data[end] ps-data[end - 1];end--;}ps-data[0] x;ps-sz;
}7.顺序表尾删(SeqListPopBack)
变量sz代表有效数据的个数那么只要sz减一就代表最后一个数据被删除了。
//顺序表尾删
void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps-sz ! 0);ps-sz--;
}8.顺序表头删(SeqListPopFront)
头删数据要将数据从后向前挪到覆盖掉第一个数据sz要减一。
//顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps-sz ! 0);for (int i 0; i ps-sz - 1; i){ps-data[i] ps-data[i 1];}ps-sz--;
}9.顺序表查找(SeqListFind)
遍历一遍动态开辟的数组如果找到了就放回下标没有就放回-1。
//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-sz; i){if (ps-data[i] x){return i;}}return -1;
}10.在pos位置前插入元素(SeqListInsert)
要先检查空间容量是否充足和要插入的位置是否合法(要在顺序表的有效数据内)再将pos下标后的数据向后挪到将数据放入data[pos]处sz加一。 这个函数思路简单但要注意下面两点
如果pos 0不就是要在顺序表第一个元素前插入元素不就是顺序表的头插。如果pos sz我们知道sz还表示下一个数据要放入的位置那么我在下一个数据要放入的位置前插入元素不就是顺序表的尾插。
理解这点后我们以后的头插尾插都可以用该函数复用。方便我们手撕顺序表
//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-sz);if (ps-sz ps-capacity){SeqListCheckCapacity(ps);}int end ps-sz;while (end pos){ps-data[end] ps-data[end - 1];end--;}ps-data[pos] x;ps-sz;
}
11.删除pos位置的值(SeqListErase)
删除pos位置处的数据先检查pos的合法性(要属于[0sz-1])要将数据从后向前挪到数据sz减一。 这个函数思路简单但要注意下面两点
如果pos 0不就是要删除第一个数据不就是头删。如果pos sz - 1不就是要删除最后一个数据不就是尾删。
所以对于尾删头删函数而言我们也可以使用该函数复用。
//删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos 0 pos ps-sz);for (int i pos; i ps-sz - 1; i){ps-data[i] ps-data[i 1];}ps-sz--;
}三、代码实现
头删头插尾删尾插我都复用了SeqListInsert和SeqListErase。 SeqList.h 文件存放有关函数的声明以及结构体的声明 SeqList.c 文件存放函数的定义
//SeqList.h 文件#pragma once#include stdio.h
#include stdlib.h
#include assert.h#define SIZE 4typedef int SLDataType;typedef struct SeqList
{SLDataType* data;int sz;int capacity;
}SeqList;//初始化顺序表
void SeqListInit(SeqList* ps);//销毁顺序表
void SeqListDestroty(SeqList* ps);//打印顺序表
void SeqListPrint(SeqList* ps);//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDateType x);//顺序表尾删
void SeqListPopBack(SeqList* ps);//顺序表头删
void SeqListPopFront(SeqList* ps);//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDateType x);//删除pos位置的值
void SeqListErase(SeqList* ps, int pos);//检查容量
void SeqListCheckCapacity(SeqList* ps);//SeqList.c 文件#include SeqList.h//初始化顺序表
void SeqListInit(SeqList* ps)
{ps-data (SLDataType*)malloc(sizeof(SLDataType) * SIZE);if (ps-data NULL){perror(malloc);exit(-1);}ps-sz 0;ps-capacity SIZE;
}//检查容量
void SeqListCheckCapacity(SeqList* ps)
{SLDataType* tmp (SLDataType*)realloc(ps-data, sizeof(SLDataType) * ps-capacity * 2);if (tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capacity * 2;
}//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{/*assert(ps);if (ps-sz ps-capacity){SeqListCheckCapacity(ps);}ps-data[ps-sz] x;ps-sz;*/SeqListInsert(ps, ps-sz, x);
}//打印顺序表
void SeqListPrint(SeqList* ps)
{assert(ps);for (int i 0; i ps-sz; i){printf(%d , ps-data[i]);}printf(\n);}//销毁顺序表
void SeqListDestroty(SeqList* ps)
{assert(ps);//free(ps);free(ps-data);ps-data NULL;ps-sz 0;ps-capacity 0;
}//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDataType x)
{/*assert(ps);if (ps-sz ps-capacity){SeqListCheckCapacity(ps);}int end ps-sz;while (end 0){ps-data[end] ps-data[end - 1];end--;}ps-data[0] x;ps-sz;*/SeqListInsert(ps, 0, x);
}//顺序表尾删
void SeqListPopBack(SeqList* ps)
{/*assert(ps);assert(ps-sz ! 0);ps-sz--;*/SeqListErase(ps, ps-sz - 1);
}//顺序表头删
void SeqListPopFront(SeqList* ps)
{/*assert(ps);assert(ps-sz ! 0);for (int i 0; i ps-sz - 1; i){ps-data[i] ps-data[i 1];}ps-sz--;*/SeqListErase(ps, 0);
}//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-sz; i){if (ps-data[i] x){return i;}}return -1;
}//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-sz);if (ps-sz ps-capacity){SeqListCheckCapacity(ps);}int end ps-sz;while (end pos){ps-data[end] ps-data[end - 1];end--;}ps-data[pos] x;ps-sz;
}//删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos 0 pos ps-sz);for (int i pos; i ps-sz - 1; i){ps-data[i] ps-data[i 1];}ps-sz--;
}总结
以上就是顺序表的实现。谢谢支持
