一、顺序表十种接口实现
typedef int SLDataType; typedef struct SeqList { SLDataType* num;//存放数据 int capacity;//记录容量 int size;//记录存储数据的个数 }SL; //顺序表的初始化 void SeqListInit(SL* pc); //顺序表的打印 void SeqListPrint(SL* pc); //顺序表得到尾插 void SeqListPushBack(SL* pc, SLDataType x); //顺序表的头插 void SeqListPushFront(SL* pc, SLDataType x); //顺序表的尾删 void SeqListPopBack(SL* pc); //顺序表的头删 void SeqListPopFront(SL* pc); //顺序表在pos位置插入指定x void SeqListInsert(SL* pc, int pos, SLDataType x); //顺序表删除pos位置的值 void SeqListErase(SL* pc, int pos); //顺序表的查找 int SeqListFind(SL* pc, SLDataType x); //顺序表的销毁 void SeqListDestroy(SL* pc);
顺序表可以采用静态存储和动态存储的方式，一般是采用动态存储的方式，目的在于减少空间的浪费
1.顺序表的初始化
顺序表的初始化 相对简单，我们定义了有一个顺序表的指针、 容量、数据的个数
//顺序表的初始化 void SeqListInit(SL* pc) { pc->num = NULL; pc->capacity = pc->size = 0; }
2.顺序表的打印
//顺序表的打印 void SeqListPrint(SL* pc) { assert(pc); for (int i = 0; i < pc->size; ++i) { printf("%d ", pc->num[i]); } printf("\n"); }
3.顺序表的扩容函数
顺序表在存储数据时，需要空间的使用，我们这里采用的是动态存储，我们要保证每次存放数据时顺序表的容量是足够的，就需要动态开辟空间
//扩容函数 void SeqListCheckCapacity(SL* pc) { if (pc->size == pc->capacity) { //当我们第一次插入数据时，顺序表的容量和数据个数都是0，可以采用三目操作符，先给它一块空间 int newcapacity = pc->size == 0 ? 4 : pc->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(pc->num, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pc->num = tmp; pc->capacity = newcapacity; } }
4. 顺序表的尾插
//顺序表的尾插 void SeqListPushBack(SL* pc, SLDataType x) { assert(pc); //判断容量 SeqListCheckCapacity(pc); pc->num[pc->size] = x; pc->size++; //SeqListInsert(pc, pc->size, x);这是指定位置插入的函数 }
5.顺序表的头插
//顺序表的头插 void SeqListPushFront(SL* pc, SLDataType x) { assert(pc); //判断容量 SeqListCheckCapacity(pc); int end = pc->size - 1; while (end >= 0) { pc->num[end + 1] = pc->num[end];//把每个数向后挪一个位置 end--; } pc->num[0] = x; pc->size++; //SeqListInsert(pc, 0, x); }
6.顺序表的尾删
//顺序表的尾删 void SeqListPopBack(SL* pc) { assert(pc); pc->size--; //SeqListErase(pc, pc->size - 1);指定位置删除函数 }
直接数据个数减一，让其访问不到
7.顺序表的头删
//顺序表的头删 void SeqListPopFront(SL* pc) { assert(pc); int begin = 1; while (begin < pc->size) { pc->num[begin - 1] = pc->num[begin]; begin++; } pc->size--; //SeqListErase(pc, 0); }
8.顺序表在pos位置插入指定的数字x
//顺序表在pos位置插入指定x void SeqListInsert(SL* pc, int pos, SLDataType x) { assert(pc); assert(pos >= 0 && pos <= pc->size); SeqListCheckCapacity(pc); int end = pc->size - 1; while (end >= pos) { pc->num[end + 1] = pc->num[end]; end--; } pc->num[pos] = x; pc->size++; }
在头插接口中和这里的指定位置 插入功能一样，所以我们就可以在需要调用头插时直接转换为调用这里的函数，下面的删除也是一个道理；
9.顺序表删除pos位置的值
//顺序表删除pos位置的值 void SeqListErase(SL* pc, int pos) { assert(pc); assert(pos >= 0 && pos < pc->size); int begin = pos + 1; while (begin < pc->size) { pc->num[begin - 1] = pc->num[begin]; begin++; } pc->size--; }
10.顺序表的查找和销毁
//顺序表的查找 int SeqListFind(SL* pc, SLDataType x) { assert(pc); for (int i = 0; i < pc->size; ++i) { if (pc->num[i] == x) { return i; } } return -1; } //顺序表的销毁 void SeqListDestroy(SL* pc) { free(pc->num); pc->num = NULL; pc->capacity = pc->size = 0; }
二、源代码展示
1. SeqList.h
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLDataType; typedef struct SeqList { SLDataType* num; int capacity; int size; }SL; //顺序表的初始化 void SeqListInit(SL* pc); //顺序表的打印 void SeqListPrint(SL* pc); //顺序表得到尾插 void SeqListPushBack(SL* pc, SLDataType x); //顺序表的头插 void SeqListPushFront(SL* pc, SLDataType x); //顺序表的尾删 void SeqListPopBack(SL* pc); //顺序表的头删 void SeqListPopFront(SL* pc); //顺序表在pos位置插入指定x void SeqListInsert(SL* pc, int pos, SLDataType x); //顺序表删除pos位置的值 void SeqListErase(SL* pc, int pos); //顺序表的查找 int SeqListFind(SL* pc, SLDataType x); //顺序表的销毁 void SeqListDestroy(SL* pc);
2.SeqList.c
#include "SeqList.h" //顺序表的初始化 void SeqListInit(SL* pc) { pc->num = NULL; pc->capacity = pc->size = 0; } //顺序表的打印 void SeqListPrint(SL* pc) { assert(pc); for (int i = 0; i < pc->size; ++i) { printf("%d ", pc->num[i]); } printf("\n"); } //扩容函数 void SeqListCheckCapacity(SL* pc) { if (pc->size == pc->capacity) { int newcapacity = pc->size == 0 ? 4 : pc->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(pc->num, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pc->num = tmp; pc->capacity = newcapacity; } } //顺序表的尾插 void SeqListPushBack(SL* pc, SLDataType x) { /*assert(pc);*/ //判断容量 //SeqListCheckCapacity(pc); //pc->num[pc->size] = x; //pc->size++; SeqListInsert(pc, pc->size, x); } //顺序表的头插 void SeqListPushFront(SL* pc, SLDataType x) { //assert(pc); 判断容量 //SeqListCheckCapacity(pc); //int end = pc->size - 1; //while (end >= 0) //{ // pc->num[end + 1] = pc->num[end];//把每个数向后挪一个位置 // end--; //} //pc->num[0] = x; //pc->size++; SeqListInsert(pc, 0, x); } //顺序表的尾删 void SeqListPopBack(SL* pc) { //assert(pc); //pc->size--; SeqListErase(pc, pc->size - 1); } //顺序表的头删 void SeqListPopFront(SL* pc) { //assert(pc); //int begin = 1; //while (begin < pc->size) //{ // pc->num[begin - 1] = pc->num[begin]; // begin++; //} //pc->size--; SeqListErase(pc, 0); } //顺序表在pos位置插入指定x void SeqListInsert(SL* pc, int pos, SLDataType x) { assert(pc); assert(pos >= 0 && pos <= pc->size); SeqListCheckCapacity(pc); int end = pc->size - 1; while (end >= pos) { pc->num[end + 1] = pc->num[end]; end--; } pc->num[pos] = x; pc->size++; } //顺序表删除pos位置的值 void SeqListErase(SL* pc, int pos) { assert(pc); assert(pos >= 0 && pos < pc->size); int begin = pos + 1; while (begin < pc->size) { pc->num[begin - 1] = pc->num[begin]; begin++; } pc->size--; } //顺序表的查找 int SeqListFind(SL* pc, SLDataType x) { assert(pc); for (int i = 0; i < pc->size; ++i) { if (pc->num[i] == x) { return i; } } return -1; } //顺序表的销毁 void SeqListDestroy(SL* pc) { free(pc->num); pc->num = NULL; pc->capacity = pc->size = 0; }
3.test.c
#include "SeqList.h" void Test1() { SL p; SeqListInit(&p); //尾插 SeqListPushBack(&p, 1); SeqListPushBack(&p, 2); SeqListPushBack(&p, 3); SeqListPushBack(&p, 4); SeqListPushBack(&p, 5); SeqListPrint(&p); //头插 SeqListPushFront(&p, 1); SeqListPushFront(&p, 2); SeqListPushFront(&p, 3); SeqListPushFront(&p, 4); SeqListPushFront(&p, 5); SeqListPrint(&p); //尾删 SeqListPopBack(&p); SeqListPopBack(&p); SeqListPrint(&p); //头删 SeqListPopFront(&p); SeqListPopFront(&p); SeqListPrint(&p); //在pos位置插入，我们在下标为2的位置插入20 SeqListInsert(&p, 2, 20); SeqListPrint(&p); //删除pos位置的值，我们删除下标为2中的值20 SeqListErase(&p, 2, 20); SeqListPrint(&p); } void Test2() { SL p; SeqListInit(&p); //尾插 SeqListPushBack(&p, 1); SeqListPushBack(&p, 2); SeqListPushBack(&p, 3); SeqListPushBack(&p, 4); SeqListPushBack(&p, 5); SeqListPrint(&p); SeqListPopBack(&p); SeqListPrint(&p); SeqListPopFront(&p); SeqListPrint(&p); SeqListPushBack(&p, 10); SeqListPrint(&p); SeqListPushFront(&p, 5); SeqListPrint(&p); } int main() { //Test1(); Test2(); return 0; }
