线性表的概念
线性表（linear list）是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表： 顺序表、链表、栈、队列、字符串......
线性表在逻辑上线性结构，也就是说 连续的一条直线 。但是在物理结构上 并不一定是连续 的，线性表在物理上存储时，通常是 以数组和链式结构 的形式存储。
顺序表的概念
顺序表是用一段 物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用 数组存储。在数组上完成数据的增删查改。
顺序表是数组，但在数组的基础上，它还要求数据是从头开始连续存储的，不能跳跃间隔。
顺序表的结构
静态顺序表
#define N 100 //存储容量 typedef int SLDataType; //方便修改存储的数据类型 typedef struct SeqList { SLDataType a[N]; int size; //表示数组中存储了多少个数据 }SL; //接口函数 void SeqListInit(SL* ps); void SeqListPushBack(SL* ps, SLDataType x); void SeqListPopBack(SL* ps); void SeqListPushFront(SL* ps, SLDataType x); void SeqListPopFront(SL* ps); //......
动态顺序表
typedef int SLDataType; //方便修改存储的数据类型 typedef struct SeqList { SLDataType* a; int size; //表示数组中存储了多少个数据 int capacity;//表示数组实际能存数据的空间容量的大小 }SL; //接口函数 //顺序表初始化 void SeqListInit(SL* ps); //检查空间，如果满了，进行增容 void SeqListCheckCapacity(SL* ps); //顺序表尾插 void SeqListPushBack(SL* ps, SLDataType x); //顺序表尾删 void SeqListPopBack(SL* ps); //顺序表头插 void SeqListPushFront(SL* ps, SLDataType x); //顺序表头删 void SeqListPopFront(SL* ps); //顺序表查找 int SeqListFine(SL* ps,SLDataType x); //顺序表在pos位置插入x void SeqListInsert(SL* ps,size_t pos,SLDataType x); //顺序表删除pos位置的值 void SeqListErase(SL* ps,size_t pos); //顺序表销毁 void SeqListDestory(SL* ps); //顺序表打印 void SeqListPrint(SL* ps);
检查增容
void CheckCapacity(SL* ps) { //如果没有空间或者空间不足，那么就增容 if(ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2; SLDataType* tmp = (SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType)); if(tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } }
顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x) { SeqListCheckCapacity(SL* ps); ps->a[ps->size] = x; ps->size++; }
顺序表尾删
void SeqListPopBack(SL* ps) { //温柔处理方式 //if(ps->size > 0) //{ // ps->size--; //} //暴力处理方式 assert(ps->size > 0); ps->size--; }
顺序表头插
void SeqListPushFront(SL* ps, SLDataType x) { SeqListCheckCapacity(SL* ps); //挪动数据 int end = ps->size - 1; while(end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; }
顺序表头删
void SeqListPopFront(SL* ps) { assert(ps->size > 0); //挪动数据 int begin = 1; while(begin < ps->size) { ps->a[begin - 1] = ps->[begin]; begin++; } ps->size--; }
顺序表查找
int SeqListFine(SL* ps,SLDataType x) { for(int i = 0;i < ps->a[i]size;i++) { if(ps->a[i] == x) { return i; } } return -1; }
顺序表在pos位置插入x
void SeqListInsert(SL* ps,size_t pos,SLDataType x) { assert(pos >=0 && pos <= ps->size); //挪动数据 int end = ps->size - 1; while(end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }
顺序表删除pos位置的值
void SeqListErase(SL* ps,size_t pos) { assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while(begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
顺序表销毁
void SeqListDestory(SL* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; }
