1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
那顺序表和链表有什么区别呢？
顺序表其实本质就是对数组的操作，只要知道数组的起始地址就可以找到后面的所有内容，而链表是在内存中开辟一个一个的空间，各个空间之间靠指针相互联系，指针中存放的是下一个空间的地址。
所以顺序表要实现删除数据只需要用后面的数据将前面的数据覆盖，而链表要实现删除数据，如下图，要删除2号空间的数据，直接在1号空间中存放3号空间的地址即可，相当于跳过了2号空间。
但是数组有一个它的绝对优势，就是下标的随机访问，比如数组能实现二分查找，但是链表就不行，而数组之所以能实现下标的随机访问就是因为它的物理空间连续，但是链表的物理空间并不连续。
顺序表和链表各有特点，那今天我们先来学习顺序表。
一般顺序表分为两种：
1. 静态顺序表：使用定长数组存储数据。
例如：
//静态顺序表 #define N 10 typedef int SLDatatype; struct SeqList { SLDatatype arr[N]; int size;//存储有效数据的个数 };
但是静态顺序表有一个很大的缺点：开辟的空间是固定的，给小了不够用，给多了浪费。
这时就需要动态顺序表了。
2. 动态顺序表：使用动态开辟的内存存储数据。
使用动态顺序表，我们要知道什么时候空间不够了去扩容，这就需要再增加一个描述容量的变量。
例如：
//动态顺序表 #define N 10 typedef int SLDatatype; struct SeqList { SLDatatype*a; int size;//存储有效数据的个数 int capacity;//容量 };
2.2 顺序表的实现
初始化顺序表：
//初始化顺序表 void SLInit(SL* ps1) { ps1->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4); if (ps1->a == NULL) { perror("malloc fail"); return; } ps1->size = 0; ps1->capacity = 4; }
可以使用动态内存开辟函数malloc为初始化数据开辟空间。
扩容函数：
为了确保插入数据时不发生越界，定义一个扩容函数，当容量满了的时候，使用realloc增加容量。
//扩容函数 void SLCheckCapacity(SL* ps1) { if (ps1->size == ps1->capacity) { SLDatatype*tmp = (SLDatatype*)realloc(ps1->a, sizeof(SLDatatype) * ps1->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps1->a = tmp; ps1->capacity*=2; } }
顺序表尾插数据：
//顺序表尾插数据 void SLPushBack(SL* ps1, SLDatatype x) { SLCheckCapacity(ps1); ps1->a[ps1->size] = x; ps1->size++; }
打印函数:
//打印函数 void SLPrint(SL* ps1) { int i = 0; for (i = 0; i < ps1->size; i++) { printf("%d ", ps1->a[i]); } printf("\n"); }
测试尾插数据的功能：
顺序表头插数据：
要想在顺序表头部插入一个数据，只要将现有数据整体往后挪动一位，然后将该数据放在第一位就行。注意为了防止覆盖，只能从后往前挪动。
//顺序表头插数据 void SLPushFront(SL* ps1, SLDatatype x) { SLCheckCapacity(ps1); int i = 0; for (i = 0; i < ps1->size; i++) { ps1->a[ps1->size-i] = ps1->a[ps1->size - 1 - i]; } ps1->a[0] = x; ps1->size++; }
测试头插数据：
顺序表尾删数据：
想要尾删数据，只要将size--即可。注意检查是否删除完所有数据
//顺序表尾删数据 void SLPopBack(SL* ps1, SLDatatype x) { //检查 assert(ps1->size > 0); ps1->size--; }
测试尾删数据：
顺序表头删数据：
头删数据只需要将后面的数据从前往后覆盖即可。
//顺序表头删数据 void SLPopFront(SL* ps1) { assert(ps1->size > 0); int i = 0; for (i = 0; i < ps1->size - 1; i++) { ps1->a[0 + i] = ps1->a[1 + i]; } ps1->size--; }
测试头删数据：
顺序表中间位置插入数据：
在pos位置插入一个数据，先将pos位置的数据及往后的数据往后移一位，然后就可以在pos位置插入了。
//顺序表中间插入数据 void SLInsert(SL* ps1, int pos, SLDatatype x) { SLCheckCapacity(ps1); int end = ps1->size; while (end >= pos) { ps1->a[end] = ps1->a[end-1]; end--; } ps1->a[pos] = x; ps1->size++; }
测试顺序表中间插入数据：
顺序表中间位置删除数据：
要删除pos位置的数据，只需将pos后面的数据往前覆盖即可。
//顺序表中间位置删除数据 void SLErase(SL* ps1, int pos) { assert(pos>=0 > 0 && pos< ps1->size); assert(ps1->size > 0); while (pos < ps1->size-1) { ps1->a[pos] = ps1->a[pos + 1]; pos++; } ps1->size--; }
测试：
顺序表查找数据：
//顺序表查找数据 //找到返回下标，没找到返回-1 int SLFind(SL* ps1, SLDatatype x) { int i = 0; for (i = 0; i < ps1->size; i++) { if (x == ps1->a[i]) { return i; } } return -1; }
顺序表查找可以和删除配合使用：
顺序表修改数据：
//顺序表修改数据 void SLModify(SL* ps1, int pos, SLDatatype x) { assert(pos >= 0 > 0 && pos < ps1->size); ps1->a[pos] = x; }
过于简单，不再测试。
销毁顺序表：
//销毁顺序表 void SLDestory(SL* ps1) { free(ps1->a); ps1->a = NULL; }
以上就是顺序表的增删查改，下面我们给出完整代码：
3.完整代码：
test.c:
这里仅仅是一个测试用例，当然也可以试试测试其他的功能。
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" void test1() { SL s; s.a = NULL; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushBack(&s, 6); SLPrint(&s); int pos = SLFind(&s, 6); if (pos != -1) { SLErase(&s, pos); } SLPrint(&s); SLDestory(&s); } int main() { test1(); return 0; }
SeqList.h:
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //动态顺序表 #define N 10 typedef int SLDatatype; typedef struct SeqList { SLDatatype*a; int size;//存储有效数据的个数 int capacity;//容量 }SL; //初始化 void SLInit(SL* ps1); //销毁 void SLDestory(SL* ps1); //打印 void SLPrint(SL* ps1); //尾插 void SLPushBack(SL* ps1, SLDatatype x); //头插 void SLPushFront(SL* ps1, SLDatatype x); //尾删 void SLPopBack(SL* ps1); //头删 void SLPopFront(SL* ps1); //中间插入 void SLInsert(SL* ps1, int pos, SLDatatype x); //中间删除 void SLErase(SL* ps1, int pos); //查找 int SLFind(SL* ps1, SLDatatype x); //修改 void SLModify(SL* ps1, int pos,SLDatatype x);
SeqList.c:
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" //初始化顺序表 void SLInit(SL* ps1) { assert(ps1); ps1->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4); if (ps1->a == NULL) { perror("malloc fail"); return; } ps1->size = 0; ps1->capacity = 4; } //打印函数 void SLPrint(SL* ps1) { assert(ps1); int i = 0; for (i = 0; i < ps1->size; i++) { printf("%d ", ps1->a[i]); } printf("\n"); } //销毁顺序表 void SLDestory(SL* ps1) { free(ps1->a); ps1->a = NULL; } //扩容函数 void SLCheckCapacity(SL* ps1) { assert(ps1); if (ps1->size == ps1->capacity) { SLDatatype*tmp = (SLDatatype*)realloc(ps1->a, sizeof(SLDatatype) * ps1->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps1->a = tmp; ps1->capacity*=2; } } //顺序表尾插数据 void SLPushBack(SL* ps1, SLDatatype x) { assert(ps1); SLCheckCapacity(ps1); ps1->a[ps1->size] = x; ps1->size++; } //顺序表头插数据 void SLPushFront(SL* ps1, SLDatatype x) { assert(ps1); SLCheckCapacity(ps1); int i = 0; for (i = 0; i < ps1->size; i++) { ps1->a[ps1->size-i] = ps1->a[ps1->size - 1 - i]; } ps1->a[0] = x; ps1->size++; } //顺序表尾删数据 void SLPopBack(SL* ps1) { assert(ps1); //检查 assert(ps1->size > 0); ps1->size--; } //顺序表头删数据 void SLPopFront(SL* ps1) { assert(ps1); assert(ps1->size > 0); int i = 0; for (i = 0; i < ps1->size - 1; i++) { ps1->a[0 + i] = ps1->a[1 + i]; } ps1->size--; } //顺序表中间插入数据 void SLInsert(SL* ps1, int pos, SLDatatype x) { assert(ps1); assert(pos >= 0 && pos <= ps1->size); SLCheckCapacity(ps1); int end = ps1->size; while (end >= pos) { ps1->a[end] = ps1->a[end-1]; end--; } ps1->a[pos] = x; ps1->size++; } //顺序表中间位置删除数据 void SLErase(SL* ps1, int pos) { assert(ps1); assert(pos>=0 > 0 && pos< ps1->size); while (pos < ps1->size-1) { ps1->a[pos] = ps1->a[pos + 1]; pos++; } ps1->size--; } //顺序表查找数据 //找到返回下标，没找到返回-1 int SLFind(SL* ps1, SLDatatype x) { assert(ps1); int i = 0; for (i = 0; i < ps1->size; i++) { if (x == ps1->a[i]) { return i; } } return -1; } //顺序表修改数据 void SLModify(SL* ps1, int pos, SLDatatype x) { assert(ps1); assert(pos >= 0 > 0 && pos < ps1->size); ps1->a[pos] = x; }
以上就是我们今天关于顺序表的所有内容了，未完待续。。。
