专栏：《数据结构实战篇》

---

        生活中有着无穷无尽的数据需要存储，大到全国人口普查，小到微信、QQ好友列表，都需要有一个合理的存储方式才能使得我们的数据更方便管理，线性表就是其中之一

一、线性表

        线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

        线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

 二、顺序表

        2.1 顺序表概念及结构

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

        2.2 顺序表的分类

        顺序表一般可以分为两大类：

        2.2.1 静态顺序表

#define N 8struct seqlist
{int arr[N]; //定长数组size_t size; //数组的有效长度
};

         现然可以看出静态顺序表和数组差不多，因此他的缺点就很明显了：

        1. 当数据存满的时候无法再开辟空间

        2. 如果整个数组的长度为100，但是我只存了5个数据在里面，那就会形成很大一块的空间浪费（剩下的95个空间全是空间浪费）

        针对上述问题，聪明的人类想到了动态空间管理，就是动态顺序表

        2.2.2 动态顺序表

typedef int seq_list_data;struct seq_list
{seq_list_data* arr;//指向动态开辟的数组int size;//有效数据个数int capacity；//容量空间的大小
};

        合理运用malloc和realloc两个函数可以帮我们实现很多我们想要的操作

        静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

        2.3 顺序表的增删查改实现

        其实动态顺序表的实现和我之前写过的通讯录项目类似，感兴趣的朋友可以去浅看一下《C语言动态内存管理》

        2.3.1 初始化顺序表

        先把动态内存默认大小开辟出来，方便后续操作

void init_seqlist(seq_list* ps)
{seq_list_data* tmp = (seq_list_data*)malloc(2*sizeof(seq_list_data));if (tmp == NULL){perror("init_seqlist::malloc");return;}ps->arr = tmp;ps->capacity = 2;ps->size = 0;
}

        2.3.2 打印顺序表

        为方便后续操作，我个人建议先把打印的函数写了，之后再写增删查改就可以能观察到我们想要的东西

        想要打印顺序表也很简单，只需要从0到size打印出来就好啦

void print_seqlist(seq_list* ps)
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

        2.3.3 增加一个数据

        增加一个数据分为两种方式，头插和尾插，尾插相对简单，就不多说了，主要是头插，其实就是先把数据全部诺向后一个位置，留着第一个位置，然后插入数据

        先展示尾插

void push_back(seq_list* ps, int x)
{//检查容量满了没if (ps->size == ps->capacity){seq_list_data* tmp = (seq_list_data*)realloc(ps->arr, 2 * ps->capacity * sizeof(seq_list_data));if (tmp == NULL){perror("push_back::realloc");return;}ps->arr = tmp;}ps->arr[ps->size] = x;ps->size++;
}

        头插图示：（都学数据结构啦，就别摆烂了，好好画图哈~~）

 

void push_frnot(seq_list* ps, int x)
{//检查容量满了没if (ps->size == ps->capacity){seq_list_data* tmp = (seq_list_data*)realloc(ps->arr, 2 * ps->capacity * sizeof(seq_list_data));if (tmp == NULL){perror("push_back::realloc");return;}ps->arr = tmp;ps->capacity *= 2;}//将数据移到后面int i = 0;for (i = ps->size; i >= 0; i--){ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;ps->size++;
}

        2.3.4 删除一个数据

        同样删除一个数据也有头删和尾删，尾删就是直接size--就好啦，头删则是把后面的数据覆盖到前面

        头删

//头删
void pop_front(seq_list* ps)
{assert(ps);//检查size要大于0assert(ps->size);//把后面的数据向前覆盖int i = 0;for (i = 0; i < ps->size; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

        尾删

//尾删
void pop_back(seq_list* ps)
{assert(ps);//检查size要大于0assert(ps->size);ps->size--;
}

        2.3.5 查找数据

        就找到这个数据返回数据的地址就好啦

//查找
int seq_find(seq_list* ps, int x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}

        2.3.6 销毁数据表

        当数据表用完的时候，最后记得要把malloc借来的空间释放了哟~有借有还，再借不难嘛~

//销毁
void distory(seq_list* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->size = 0;
}

三、顺序表缺点

        顺序表的缺点也很明显，虽然可以实现动态内存开辟和释放，但是如果要在中间加入一个数据的话，就比较费事，因此聪明的人类又发明了链表，至于链表是什么，还请各位稍等下一期内容，我们将在手搓一个链表出来，并分享一下顺序表链表有关的oj题，大家可以期待一下啦~

        最后还是希望各位帅哥美女留下一个宝贵的三连吧

        拜托啦 >_<