目录
概念及结构
接口函数实现
顺序表的初始化
容量判断
顺序表尾插
顺序表尾删
顺序表头插
顺序表头删
顺序表查找
顺序表指定位置插入
顺序表指定位置删除
打印顺序表
销毁顺序表
顺序表完整代码
概念及结构
顺序表作为线性表的一种,它是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为:
1、静态顺序表——使用定长数组进行存储元素。
#define N 100 //顺序表的静态存储 typedef int SLDatatype; typedef struct SeqList { SLDataType Data[N]; //定长数组 int size; //有效数据个数 }SeqList;
这种存储方式在存储数据时比较有局限性,当数据存储量非常小的时候,数组长度太长,会造成空间的浪费;当数据存储量非常大的时候,数组空间可能会不够,但是这种存储方式不能进行扩容。所以在实现顺序表时,我们通常使用的是动态顺序表。这样能够提高我们的空间利用率。
2、动态顺序表——使用动态开辟的数组进行存储元素。
//顺序表的动态存储 typedef int SLDatatype; typedef struct SeqList { SLDataType* Data; //定长数组 int size; //有效数据个数 int capacity; //空间容量的大小 }SeqList;
接口函数实现
顺序表的初始化
//初始化链表 void SLInit(SeqList* ps) { assert(ps); //判空,如果传入的空指针,后面对它进行解引用就会报错 ps->data = NULL; //将data初始化为空指针 ps->capacity = ps->size = 0; }
现在顺序表的初始化完成了,接下来就是顺序表的增删查改了。
在实现顺序表增加元素的函数功能前,首先我们先实现一个检查顺序表是否已经存满。如果已经存满了,那么我们就需要对它进行扩容。
容量判断
//容量判断 void Check_Capacity(SeqList* ps) { assert(ps); if (ps->capacity == ps->size) //判断顺序表中有效数据个数是否已经达到容量大小 { int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2; //如果容量为0的话,此时就是第一次向顺序表中添加元素,capacity就设为4 //如果容量不为0,此时就是有效数据个数达到容量,就进行扩容,新容量设置为原容量的2倍 SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType)); if (tmp == NULL) //如果扩容失败,就终止程序。 { perror("ralloc fail"); exit(-1); } ps->data = tmp; ps->capacity = new_capacity; } }
这里扩容使用的是realloc函数,当我们进行第一次插入的时候,ps->data指针还是空指针,这时我们也可以使用realloc,realloc函数在使用的时候,如果传入的指针是空指针,它的作用就与malloc相同。
顺序表尾插
//顺序表尾插 void SL_PushBack(SL* ps, SLDataType x) { assert(ps); Check_Capacity(ps); ps->data[ps->size] = x; ps->size++; }
顺序表尾删
//顺序表尾删 void SL_PopBack(SL* ps) { assert(ps); assert(ps->size > 0); //如果顺序表中已经没有元素,那么就不用进行删除,所以 //这里需要检查顺序表中是否还有元素。 ps->size--; }
无论是尾删还是头删,都要对顺序表进行检查表中是否还有元素。
顺序表头插
//顺序表头插 void SL_PushFront(SL* ps, SLDataType x) { assert(ps); Check_Capacity(ps); //检查容量 //将所有数据向后移动一位 for (int i = ps->size - 1; i >= 0; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[0] = x; ps->size++; }
头插时不仅要对容量进行检查,同时,我们也要将数据向后移动一位再进行插入操作,不然会造成数据丢失。
顺序表头删
//顺序表头删 void SL_PopFront(SL* ps) { assert(ps); //如果顺序表中只有一个数据,那么直接将数据个数-1 //如果对数据进行挪动,会造成越界 if (ps->size == 1) { ps->size--; return; } 如果数据个数不为1,就将数据中第2个到最后一个都往前移动一位 for (int i = 1; i < ps->size; i++) { ps->data[i - 1] = ps->data[i]; } ps->size--; }
顺序表查找
//顺序表查找 int SL_Find(SeqList* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->data[i] == x) { //找到就返回下标 return i; } } //找不到就返回-1 return -1; }
顺序表指定位置插入
//顺序表指定位置插入 void SL_Insert(SeqList* ps, int pos, SLDataType x) { assert(ps); //判定pos是否合法 assert(pos <= ps->size); assert(pos >= 0); Check_Capacity(ps); //检查容量是否够用 //将pos位置后的元素全部都向后移动一位 for (int i = ps->size-1; i >= pos; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[pos] = x; ps->size++; }
顺序表指定位置删除
//顺序表指定位置删除 void SL_Erase(SeqList* ps, int pos) { assert(ps); //检查pos位置是否合法 assert(pos >= 0); assert(pos < ps->size); //将pos位置后面的元素全都向前移动一位 for (int i = pos; i < ps->size; i++) { ps->data[i] = ps->data[i + 1]; } ps->size--; }
有了顺序表指定位置的插入和删除后,我们就可以对尾插尾删、头插头删进行改写:
//尾插 void SL_PushBack(SeqList* ps, SLDataType x) { SL_Insert(ps, ps->size, x); } //尾删 void SL_PopBack(SeqList* ps) { SL_Erase(ps, ps->size - 1); } //头插 void SL_PushFront(SeqList* ps, SLDataType x) { SL_Insert(ps, 0, x); } //头删 void SL_PopFront(SeqList* ps) { SL_Erase(ps,0); }
打印顺序表
//打印顺序表 void SLPrint(SeqList* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->data[i]); } printf("\n"); }
销毁顺序表
//销毁顺序表 void SL_Destroy(SeqList* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->capacity = ps->size = 0; }
顺序表完整代码
SeqList.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include#include #include typedef int SLDataType; typedef struct SeqList { SLDataType* data; int size; int capacity; }SeqList; //初始化顺序表 void SLInit(SeqList* ps); //删除顺序表 void SL_Destroy(SeqList* ps); //打印顺序表 void SLPrint(SeqList* ps); //检查容量 void Check_Capacity(SeqList* ps); //尾插尾删 void SL_PushBack(SeqList* ps,SLDataType x); void SL_PopBack(SeqList* ps); //头插头删 void SL_PushFront(SeqList* ps, SLDataType x); void SL_PopFront(SeqList* ps); //顺序表查找 int SL_Find(SeqList* ps, SLDataType x); //顺序表指定位置插入 void SL_Insert(SeqList* ps, int pos, SLDataType x); //顺序表指定位置删除 void SL_Erase(SeqList* ps, int pos);
SeqList.c
#include "SeqList.h" void SLInit(SeqList* ps) { assert(ps); ps->data = NULL; ps->capacity = ps->size = 0; } void SL_Destroy(SeqList* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->capacity = ps->size = 0; } void SLPrint(SeqList* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->data[i]); } printf("\n"); } void Check_Capacity(SeqList* ps) { assert(ps); if (ps->capacity == ps->size) { int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2; SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType)); if (tmp == NULL) { perror("ralloc fail"); exit(-1); } ps->data = tmp; ps->capacity = new_capacity; } } void SL_PushBack(SeqList* ps, SLDataType x) { //assert(ps); //Check_Capacity(ps); //ps->a[ps->size] = x; //ps->size++; SL_Insert(ps, ps->size, x); } void SL_PopBack(SeqList* ps) { //assert(ps); //assert(ps->size > 0); //ps->size--; SL_Erase(ps, ps->size - 1); } void SL_PushFront(SeqList* ps, SLDataType x) { //assert(ps); //Check_Capacity(ps); //for (int i = ps->size - 1; i >= 0; i--) //{ // ps->a[i + 1] = ps->a[i]; //} //ps->a[0] = x; //ps->size++; SL_Insert(ps, 0, x); } void SL_PopFront(SeqList* ps) { //assert(ps); //if (ps->size == 1) //{ // ps->size--; // return; //} //for (int i = 1; i < ps->size; i++) //{ // ps->data[i - 1] = ps->data[i]; //} //ps->size--; SL_Erase(ps,0); } int SL_Find(SeqList* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->data[i] == x) { return i; } } return -1; } void SL_Insert(SeqList* ps, int pos, SLDataType x) { assert(ps); assert(pos <= ps->size); assert(pos >= 0); Check_Capacity(ps); for (int i = ps->size-1; i >= pos; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[pos] = x; ps->size++; } void SL_Erase(SeqList* ps, int pos) { assert(ps); assert(pos >= 0); assert(pos < ps->size); for (int i = pos; i < ps->size; i++) { ps->data[i] = ps->data[i + 1]; } ps->size--; }
以上就是顺序表相关实现的全部内容了,希望能够帮到大家。