定义
通过学习我们知道，具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。那么，什么是线性表呢？
线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。
线性表.png
将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。
使用线性表存储的数据，如同向数组中存储数据那样，要求数据类型必须一致，也就是说，线性表存储的数据，要么全不都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性表存储。
顺序存储结构和链式存储结构
把这“一串儿”数据放置到物理空间，我们可以选择以下两种方式：
-
1、顺序存储；
顺序存储结构.png
如上图所示，将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；
-
2、链式存储。
链式存储结构.png
如上图所示，数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；
也就是说，线性表存储结构可细分为顺序存储结构和链式存储结构。
对于非空的线性表和线性结构,其特点如下:
- 存在唯⼀的一个被称作”第⼀个”的数据元素;
- 存在唯⼀的一个被称作”最后一个"的数据元素；
- 除了了第一个之外,结构中的每个数据元素均有一个前驱；
- 除了了最后一个之外,结构中的每个数据元素都有一个后继。
顺序表代码实现
顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。
我们可以发现，顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。
使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：
- 顺序表申请的存储容量；
- 顺序表的长度，也就是表中存储数据元素的个数；
typedef struct{
ElemType *data;
int length;
} SqlTable;
1、顺序表的初始化
//1、初始化顺序结构线性表
Status initTable(SqlTable *table){
table->data = malloc(sizeof(ElemType) * MAX_SIZE);
if (!table->data) {
return ERROR;
}
table->length = 0;
return OK;
}
2、顺序表插入数据
//2、往线性表中插入数据
Status insertTable(SqlTable *table, int index, ElemType data){
//存储位置不对
if (index < 1 || index > table->length + 1) {
return ERROR;
}
//存储空间已满
if (table -> length >= MAX_SIZE) {
return ERROR;
}
//如果不在表尾插入数据，则需要在指定位置的后继元素都向后移动一位
if (index < table->length + 1) {
for (int i = table->length + 1; i > index; i--) {
table->data[i] = table->data[i-1];
}
}
table->data[index] = data;
table->length ++;
return OK;
}
3、顺序表遍历
//3、遍历线性表
void traverseTable(SqlTable table){
printf("遍历表：");
for (int i = 1; i <= table.length ; i ++) {
printf("%d ",table.data[I]);
}
printf("\n");
}
4、顺序表取出值
//4 顺序表的取值
Status GetElem(SqlTable table, int index, ElemType *data){
//存储位置不对
if (index < 1 || index > table.length) {
return ERROR;
}
*data = table.data[index];
return OK;
}
5、顺序表删除数据
//5 顺序表删除
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果: 删除L的第i个数据元素,L的长度减1
*/
Status deleteElem(SqlTable *table, int index){
if (index < 1 || index > table->length) {
return ERROR;
}
if (table->length == 0) {
return ERROR;
}
for (int i = index; i < table->length; i++) {
table->data[i] = table->data[i+1];
}
table->length --;
return OK;
}
6、清空顺序表
//6 清空顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
void ClearTable(SqlTable *table){
table->length = 0;
}
7、判断顺序表是否为空
//7 判断顺序表是否为空
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status tableEmpty(SqlTable table){
if (table.length <= 0) {
return S_TRUE;
}
else {
return S_FALSE;
}
}
8、获取顺序表长度
//8 获取顺序表长度ListEmpty元素个数 */
int tableLength(SqlTable table){
return table.length;
}
9、顺序表查找元素并返回位置
//9 顺序表查找元素并返回位置
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int locateElem(SqlTable table, ElemType data){
for (int i = 1; i <= table.length; i ++) {
if (data == table.data[i]) {
return I;
}
}
return 0;
}
其它辅助代码
#include "stdlib.h"
#define MAX_SIZE 100
#define OK 1
#define ERROR 0
#define S_TRUE 1
#define S_FALSE 0
//ElemType 元素类型，这里设置为int
typedef int ElemType;
//状态码，返回操作是否成功，用OK或者ERROR
typedef int Status;
typedef struct{
ElemType *data;
int length;
} SqlTable;
int main(int argc, const char * argv[]) {
printf("Hello, World!\n");
//初始化
SqlTable table;
Status initStatus = initTable(&table);
printf("线性表初始化是否成功 %d \n",initStatus);
//插入数值
for (int i = 1; i <= 10; i++) {
insertTable(&table, i, i);
}
traverseTable(table);
//取值
ElemType data;
GetElem(table, 6, &data);
printf("顺序表第6个值是%d\n",data);
//删除
deleteElem(&table, 6);
printf("删掉第6个值\n");
traverseTable(table);
//查找8在哪个位置
int locate = locateElem(table, 8);
printf("顺序表中8在第 %d 位\n",locate);
//获取长度
int length = tableLength(table);
printf("获取长度是 %d\n",length);
//清空
ClearTable(&table);
printf("清空表\n");
//判断是否为空
Status isEmpty = tableEmpty(table);
printf("是否为空(1是0否)：%d\n",isEmpty);
traverseTable(table);
printf("\n");
return 0;
}
输出结果
输出结果.png
链表代码实现
与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
如果只有一个值根本无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。
链表示意图.png
于是，链表中每个数据的存储都由以下两部分组成：
- 数据元素本身，其所在的区域称为数据域；
-
指向直接后继元素的指针，所在的区域称为指针域；
结点.png
代码实现如下：
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
一个完整的链表需要由以下几部分构成：
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
- 节点：链表中的节点又细分为头节点、首元节点和其他节点：
- 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
- 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
- 其他节点：链表中其他的节点；
1、链表的初始化
//1、初始化单链表
Status InitList(LinkList *list){
*list = malloc(sizeof(Node));
if (*list == NULL) {
return ERROR;
}
(*list)->next = NULL;
return OK;
}
2、单链表插入数据
//2、单链表插入
Status ListInsert(LinkList *list, int index, ElemType data){
LinkList p = *list;
int i = 1;
while (p && i < index) {
p = p->next;
I++;
}
if (i > index || !p) {
return ERROR;
}
LinkList q = malloc(sizeof(Node));
q->data = data;
q->next = p->next;
p->next = q;
return OK;
}
3、链表遍历
//3、遍历链表
/* 初始条件：链表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
void ListTraverse(LinkList list){
printf("遍历链表：");
LinkList p = list->next;
if (!p) {
printf("空链表");
}
else {
while (p) {
printf("%d ",p->data);
p = p->next;
}
}
printf("\n");
}
4、链表取值
//4、单链表取值
Status GetElem(LinkList list, int index, ElemType *data){
LinkList p = list;
int i = 0;
while (p && i < index) {
p = p->next;
I++;
}
if (i > index || !p) {
return ERROR;
}
*data = p->data;
return OK;
}
5、链表删除元素
//5、单链表删除元素
Status ListDelete(LinkList *list, int index, ElemType *data){
LinkList p = *list;
LinkList q = p->next;
int i = 1;
while (p && i < index) {
p = q;
q = p->next;
I++;
}
if (i > index || !p || !q) {
return ERROR;
}
p->next = q->next;
*data = q->data;
free(q);
return OK;
}
6、清空链表
//6、清空链表
/* 初始条件：链表List已存在。操作结果：将List重置为空表 */
void ClearList(LinkList *list){
LinkList p,q;
p = (*list)->next;
while (p) {
q = p->next;
free(p);
p = q;
}
(*list)->next = NULL;
}
7、链表前插法
前插法.png
//7、单链表前插法
/* 随机产生n个元素值,建立带表头结点的单链线性表List(前插法)*/
void CreateListHead(LinkList *list, int n){
*list = malloc(sizeof(Node));
(*list)->next = NULL;
LinkList p;
for (int i = 1; i <= n; i ++) {
p = malloc(sizeof(Node));
p->data = I;
p->next = (*list)->next;
(*list)->next = p;
}
}
8、链表后插法
后插法.png
//8、单链表后插法
/* 随机产生n个元素值,建立带表头结点的单链线性表List(后插法)*/
void CreateListTail(LinkList *list, int n){
*list = malloc(sizeof(Node));
LinkList p = *list;
LinkList q;
for (int i = 1; i <= n; i ++) {
q = malloc(sizeof(Node));
q->data = I;
p->next = q;
p = q;
}
p->next = NULL;
}
其它辅助代码
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define S_TRUE 1
#define S_FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
int main(int argc, const char * argv[]) {
//初始化
LinkList list;
InitList(&list);
printf("初始化链表\n");
//插入数据
for (int i = 1; i <= 10; i ++) {
ListInsert(&list, 1, i);
}
printf("插入数据后\n");
//遍历数据
ListTraverse(list);
//删除数据
ElemType deleteData;
ListDelete(&list, 6, &deleteData);
printf("删除第6个元素：%d\n",deleteData);
//遍历数据
ListTraverse(list);
//取出数据
ElemType data;
GetElem(list, 6, &data);
printf("取出第6个数：%d\n",data);
//清空链表
ClearList(&list);
printf("清空链表\n");
//遍历数据
ListTraverse(list);
printf("前插法创建链表\n");
CreateListHead(&list, 20);
ListTraverse(list);
printf("后插法创建链表\n");
CreateListTail(&list, 20);
ListTraverse(list);
printf("\n");
return 0;
}
输出结果
输出结果.png
如有不对的地方，请指正，谢谢您的阅读～
