[C][数据结构][顺序表]详细讲解+实现

---

1.线性表

• 线性表(linear list)是n个具有相同特性的数据元素的有限序列
• 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
• 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

---

2.顺序表 - SeqList

• 概念及结构

  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改 (此数组必须从第一个位置开始，连续存储)

  

• 动态顺序表 – 使用动态开辟的数组存储

---

3.实现

• 接口

typedef int SLDataType;//类型重命名，方便以后维护替换别的类型typedef struct SeqList
{SLDataType* arr;//指向动态数组指针int size;//有效数据个数int capacity;//容量 - 空间大小
}SL;//顺序表初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);//检测增容
void SLCheckCapacity();//增删查改
//尾插/尾删 - O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);//头插/头删 - O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);//从任意位置插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);//查找和修改
int SLSearch(SL* ps, SLDataType x);
void SLModify(SL* ps, int pos, SLDataType x);

• 接口实现

void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SLDestroy(SL* ps)
{assert(ps);if (ps->arr){free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->size = 0;}
}void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)
{assert(ps);//检查容量空间，满了扩容if (ps->size == ps->capacity){ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //最大容量扩容SLDataType* tmp = realloc(ps->arr, ps->capacity * sizeof(SLDataType));if (NULL == tmp){perror("realloc:");exit(1);}ps->arr = tmp;}
}void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;//SLInsert(ps, ps->size, x); //以上代码可以用这个封装替换了
}void SLPopBack(SL* ps)
{assert(ps);//暴力检查 - 适用于调试阶段assert(ps->size > 0);//温柔检查 - 适用于和用户交互使用//if (0 == ps->size)//{//	printf("SeqList is empty\n");//	return;//}ps->size--;SLErase(ps, ps->size - 1); //以上代码可以用这个封装替换了
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;//SLInsert(ps, 0, x); //以上代码可以用这个封装替换了
}void SLPopFront(SL* ps)
{int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];begin++;}ps->size--;//SLErase(ps, 0); //以上代码可以用这个封装替换了
}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size); //检验位置合法性SLCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//挪动数据int begin = pos;while (begin < ps->size - 1){//后面的数据往前搬ps->arr[begin] = ps->arr[begin + 1];begin++;}ps->size--;
}int SLSearch(SL* ps, SLDataType x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}

---

4.顺序表缺点

• 空间不够，需要扩容。
  • 扩容有一定性能损耗
  • 一般扩容两倍，存在一些空间浪费
• 头部或者中间位置插入删除效率低下 – 挪动数据
• 改善方案 – 链表 – 对顺序表缺陷的优化
  • 按需申请释放空间
  • 头部或者中间插入删除，不需要挪动数据