[数据结构]顺序表详解

1.线性表 线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。 2.顺序表 2.1概念及结构 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。 1. 静态顺序表：使用定长数组存储元素。

开少了不够用开多了浪费

#define N 100 typedef int SLDateType; struct Seqlist { SLDateType a[N]; int size; }; 2. 动态顺序表：使用动态开辟的数组存储。 2.1按需申请  typedef int SLDateType; struct Seqlist { SLDateType *a; int size;//有效数据个数 这个个数跟空间大小一样的时候就扩容 int capacity;//空间的容量 }; 2.2 接口实现：增删查改

头插尾插的时间复杂度都为o(1)

头删尾删的时间复杂度都为o(n)

SeqList.h: #ifndef SEQLIST_H #define SEQLIST_H #include <errno.h> #include <stdlib.h> #include<assert.h> #include<stdio.h> #define INIT_CAPACITY 10 typedef int SLDataType; typedef struct Seqlist { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间的容量 } SL; //增删改查 void SeqInit(SL* s); // 初始化 void SLDestroy(SL* ps);//销毁 void SLPushBack(SL* ps, SLDataType x);//插入 尾插 void SLPopBack(SL* ps);//删除 尾删 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 SLFind(SL* ps, SLDataType x);//查找x元素的下标 void SLEtdCapacity(SL* ps);//扩容 void SLPrint(SL* ps);//打印 #endif // SEQLIST_H SeqList.c: #include "SeqList.h" //打印 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } } //扩容 void SLEtdCapacity(SL* ps) { //如果空间不够，扩容 if (ps->size == ps->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity); if (tmp == NULL) { perror("realloc fail"); return; } ps->capacity *= 2; ps->a = tmp; } } //初始化 void SeqInit(SL* s) { s->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); if (s->a == NULL) { perror("malloc fail"); return; } s->size = 0; s->capacity = INIT_CAPACITY; } //销毁 void SLDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps -> size = 0; } //尾插 void SLPushBack(SL* ps, SLDataType x) { SLEtdCapacity(&ps);//扩容 ps->a[ps -> size] = x; ps->size++; } //尾删 void SLPopBack(SL* ps) { assert(ps->size>0); ps->size--; } //头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLEtdCapacity(&ps);//扩容 int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; } //头删 void SLPopFront(SL* ps)//删除 头删 { assert(ps); assert(ps->size > 0);//表不能为空 int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; } //在某个位置插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);//如果pos等于size相当于尾插 SLEtdCapacity(&ps); int end = ps->size - 1; while (end >= pos)//类似于头插 { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; } //在某个位置删除 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//删除的时候不能等于size int begin = pos + 1; while (begin < ps->size) { ps->a[begin-1] = ps->a[begin]; begin++; } ps->size--; } //查找x元素的下标 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; } test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void TestSeqList1() { SL s; SeqInit(&s); SLPushFront(&s, 1); SLPushFront(&s, 2); SLPushFront(&s, 3); SLPrint(&s); printf("\n"); SLPopFront(&s); SLPopFront(&s); SLPrint(&s); } int main() { TestSeqList1(); return 0; }