阅读量:1
顺序表
顺序表
顺序表是线性表的一种。
线性表:具有相同特性的数据结构，线性表在逻辑结构上一定是连续的，在物理结构上不一定是连续的。
顺序表：用顺序存储的方式实现线性表，把逻辑上相邻的两个变量在物理位置也相邻的存储。
顺序表的底层是数组
（文章结尾处放完整代码）
顺序表分类：
静态顺序表：底层是一个静态数组。静态顺序表并不方便，当数组的空间给大时，会造成空间浪费；当数组的空间给小了，会造成数据的丢失。
动态顺序表：一个指针，动态开辟内层。可以动态的增容。
创建一个顺序表：
(静态顺序表顺序表)
typedef struct SeqList { int arr[100]; int size;//记录的是顺序表有效数据个数 int capacity;//记录的是有效空间大小 } 静态顺序表这里不过多阐述，主要动态顺序表。
typedef int SLDatatype;//为什么要对Int重命名？ typedef struct SeqList { SLDatatype* arr; SLDatatype size;//记录的是顺序表有效数据个数 SLDatatype capacity;//记录的是有效空间大小 } 为什么要对int重命名？如果我们后面需求变更，要在顺序表中存储的数据类型是char类型，只需要修改typedef int SLDatatype;即可。
顺序表初始化
void SeqListInit(SL* ps) { ps->arr = NULL; ps->size = ps->capacity = 0; } 为什么要对顺序表初始化？我们知道，顺序表的空间是我们动态内层分配的来的，在将这块空间分配给顺序表前，这块空间中可能已经存储了其他值（脏数据），那么，我们在使用顺序表的时候可能会得到一些不是我们想要的值。
顺序表的销毁
//顺序表的销毁 void SeqListDestory(SL* ps) { if (ps->arr) { free(ps->arr); } ps->capacity = ps->size = 0; } 在使用完顺序表后，要将空间归还，否则会造成内存泄漏。如果不归还，可能在当下不会有什么问题，但时间久了，被占用的空间多了，程序就会出现问题。
顺序表的头/尾插
void SLCheckCapacity(SL* ps)//检查顺序表的空间是否足够 { if (ps->capacity == ps->size)//如果空间不足，则增容。当有效数据个数与顺便的空间大小相等时，表示空间以用完。 { int newCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity); SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype)); if (tmp == NULL) { perror("realloc Fail"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } } void SeqPushBack(SL*ps,SLDatatype x)//尾插 { assert(ps);//传入的数值不能为NULL，因为不能对空指针解引用 SLCheckCapacity(ps);//检查顺序表空间是否足够 ps->arr[ps->size++] = x; } void SeqPushFront(SL*ps,SLDatatype x)//头插 { assert(ps); SLCheckCapacity(ps);//检查顺序表空间是否足够 for (int i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; } 顺序表的头/尾删
void SeqPopBcack(SL*ps)//尾删 { assert(ps); assert(ps->size); //ps->arr[ps->size - 1] = 0; 可要可不要 ps->size--;//当作数组来理解，就是把数组的长度减1 } void SeqPopFront(SL*ps)//头删 { assert(ps); assert(ps->size); for (int i = 0; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1];//当作数组来理解，头删就是将所有数据前移一位，第一个数据直接被后面的数据覆盖掉。 } ps->size--; } 顺序表插入数据
void SLInsert(SL*ps,SLDatatype x,int pos)//在指定位置之前插入数据 { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); for (int i = ps->size; i > pos; i--)//当作数组来理解，就是从pos下标处开始，（包括pos下标处），每个元素后移一位，再在pos处插入数据 { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x;//在Pos位置插入数据 ps->size++; } void SLErase(SL *ps,int pos)//删除指定位置的数据 { assert(ps); assert(pos >= 0 && pos < ps->size); for(int i=pos;i<ps->size-1;i++) { ps->arr[i] = ps->arr[i + 1];//当作数组,就是从pos下标开始(不包括pos下标位置)，每个元素前移一位，把Pos位置处的数据覆盖掉 } ps->size--; } 顺序表查找数据
int SLFind(SL *ps,SLDatatype x )//查找数据 { assert(ps); for (int i=0;i<ps->size;i++) { if (ps->arr[i]==x) { return i; } } return -1; } 顺序表完整代码
将顺序表的代码分别放在两个个文件下，一个.h头文件，一个.c文件，最好在创建一个test.c文件对顺序表代码进行测试就行了。
SeqList.h文件 头文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLDatatype; //顺序表 typedef struct SeqList { SLDatatype* arr; SLDatatype size;//元素个数 SLDatatype capacity;//空间大小 }SL; void SeqPrint(SL ps);//打印 void SeqListInit(SL*ps);//顺序表初始化 void SeqListDestory(SL*ps);//顺序表的销毁 void SeqPushBack(SL*ps,SLDatatype x);//尾插 void SeqPushFront(SL*ps,SLDatatype x);//头插 void SeqPopBcack(SL*ps);//尾删 void SeqPopFront(SL*ps);//头删 void SLInsert(SL*ps,SLDatatype x,int pos);//在指定位置之前插入数据 void SLErase(SL *ps,int pos);//删除指定位置的数据 int SLFind(SL *ps,SLDatatype x );//查找数据 SeqList.c文件，放的是顺序表函数的实现
#include"SeqList.h" void SeqPrint(SL ps) { for (int i=0;i<ps.size;i++) { printf("%d ", ps.arr[i]); } printf("\n"); } //顺序表的初始化 void SeqListInit(SL* ps) { ps->arr = NULL; ps->size = ps->capacity = 0; } //顺序表的销毁 void SeqListDestory(SL* ps) { if (ps->arr) { free(ps->arr); } ps->capacity = ps->size = 0; } void SLCheckCapacity(SL* ps) { if (ps->capacity == ps->size) { int newCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity); SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype)); if (tmp == NULL) { perror("realloc Fail"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } } //尾插 void SeqPushBack(SL* ps, SLDatatype x) { assert(ps); SLCheckCapacity(ps); ps->arr[ps->size++] = x; } //头插 void SeqPushFront(SL* ps, SLDatatype x) { assert(ps); SLCheckCapacity(ps); for (int i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; } void SeqPopBcack(SL* ps)//尾删 { assert(ps); assert(ps->size); //ps->arr[ps->size - 1] = 0; 可要可不要 ps->size--; } void SeqPopFront(SL* ps)//头删 { assert(ps); assert(ps->size); for (int i = 0; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; } void SLInsert(SL* ps, SLDatatype x, int pos)//在指定位置之前插入数据 { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); for (int i = ps->size; i > pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; } void SLErase(SL* ps, int pos)//删除指定位置的数据 { assert(ps); assert(pos >= 0 && pos < ps->size); for(int i=pos;i<ps->size-1;i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; } int SLFind(SL* ps, SLDatatype x)//查找数据 { assert(ps); for (int i=0;i<ps->size;i++) { if (ps->arr[i]==x) { return i; } } return -1; } test.c测试文件，这个文件可以不用看了，但是为了文章的完整性，所有我写在了这里。
#include"SeqList.h" void test1() { SL s; SeqListInit(&s); /* SeqPushBack(&s,1); SeqPushBack(&s,2); SeqPushBack(&s,3); SeqPushBack(&s,4); SeqPrint(s);*/ SeqPushFront(&s,1); SeqPushFront(&s,2); SeqPushFront(&s,3); SeqPrint(s); //SeqPopBcack(&s); //SeqPrint(s); //SeqPopBcack(&s); //SeqPrint(s); //SeqPopBcack(&s); //SeqPrint(s); //SeqPopBcack(&s); //SeqPrint(s); /*1111*/ /*SeqPopFront(&s); SeqPrint(s);*/ /*SLInsert(&s,9,s.size); SeqPrint(s); SLErase(&s,s.size-1); SeqPrint(s);*/ int find=SLFind(&s,2); if (find==-1) { printf("没找到"); } else { printf("找到了"); } SeqListDestory(&s); } int main() { test1(); return 0; } 