在数据结构基础-基本概念中，已经介绍了基本概念，知道数据结构分为线性结构和非线性结构。今天要探讨的是线性结构的存储方式线性表。
线性表的特点
首先介绍线性表中最简单的结构：顺序表
#include <stdlib.h>
#define MAXSIZE 100
#define INCRSIZE 50
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//使用typedef定义int的别名，使用别名和使用int的含义一样，只不过别名更加易懂
typedef int Status;
typedef int ElementType;
typedef struct {
ElementType *data;
//int arry[100];//可以使用数组
int length;//顺序表长度，记录表中数据量
int listSize;//顺序表的容量，用于判断表是否满
} lSqlist;
//初始化表
//我们定义了线性表的一个变量，但没有对他进行初始化
Status initList(lSqlist *l){//初始化表，需要修改表，所以要传入地址
/*这个地方你可以使用数组来实现，也可以使用malloc来开辟一块连续的内存空间。
这里我们使用malloc，是因为存储满的时候方便增加存储空间，
你可以想象成OC中的可变数组*/
l->data = (ElementType *)malloc(sizeof(ElementType) * MAXSIZE);
if (!l->data)
exit(ERROR);
l->length = 0;
l->listSize = MAXSIZE;
return OK;
}
//顺序表插入
/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L)+1;
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
Status insertList(lSqlist *l, ElementType e, int i){//插入元素，需要修改表，所以要传入地址
if (l == NULL)//表不存在
return ERROR;
//插入位置超出范围
//为什么是l->length+1，因为你可以在末尾直接插入，不用向后一个个移动元素
if (i < 1 || i > l->length+1)
return ERROR;
if (i <= l->length) {
//插入数据不在表尾，移动位置空出插入位置
for (int j = l->length - 1; j >= i-1; j--) {
l->data[j+1] = l->data[j];
}
}
//将元素放在第i个位置
l->data[i-1] = e;
//表长增加
++(l->length);
return OK;
}
//顺序表删除
/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：删除L中第i个位置的数据元素，L的长度减1
*/
Status deleteList(lSqlist *l, int i){
if (l->data == NULL)//表不存在
return ERROR;
if (i < 1 || i > l->length)
return ERROR;
//如果删除的元素不在表尾，将在删除位置之后的元素前移
for (int j = i; j < l->length; j++) {
//被删除元素之后的元素向前移动
l->data[j - 1] = l->data[j];
}
--(l->length);
return OK;
}
//从顺序表中获取元素
Status getElement(lSqlist l, int i, ElementType *e){
if (l.data == NULL)//表不存在
return ERROR;
if (i < 1 || i > l.length)
return ERROR;
*e = l.data[i-1];
return OK;
}
//清空顺序表
Status clearList(lSqlist *l){
l->length = 0;
return OK;
}
顺序表总结
在删除某个元素或清空顺序表时，只是改变了顺序表的数据个数，没有对元素做操作。原因是你已经分配了一个连续内存空间，无论删除某个元素，还是清空顺序表，内存空间依然在，我们只控制长度就好了。
单链表
在单链表中，数据都是有节点组成的，节点有数据域和指针域组成的。如下图：
image.png
单链表的逻辑状态
image.png
带头节点的单链表的逻辑状态
image.png
单链表插入
假设要在单链表的两个数据元素a和b之间插⼊入一个数据元素x,先找到指向a指针p. x->next = p->next,p->next = x。如下图所示
image.png
单链表删除
要删除次第i个元素：
1.找到第i-1个元素的节点p
2.要删除的节点q，q=p->next
3.修改p的后继，使其指向q的后继，同时，删除q节点，释放占用的内存
image.png
注意：在代码中例子中，链表都是有头节点的。为什么要用头节点呢？一个是便于首元节点处理，另一个是便于空表和非空表统一处理。
单链表的头插法
单链表的头插法也叫前插法，就是创建链表时，节点总是插在首元节点的位置。
单链表的尾插法
单链表的尾插法也叫后插法，就是创建链表时，节点总是插在末尾节点的位置。这个时候，要定义一个临时节点来记录末尾节点
单链表例子代码
我这个代码可能会跟有的人不一样，因人而异。不同的地方是：每次写lNode *会麻烦，所以在定义结构体的时候，会定义别名，然后使用别名
typedef struct Node{
struct Node *next;//指针域
ElementType data;//数据域
}lNode;
typedef struct Node * LinkList;
或者
typedef struct Node{
struct Node *next;//指针域
ElementType data;//数据域
}lNode, *LinkList;
在本示例中，没有使用别名LinkList
typedef struct Node{
struct Node *next;//指针域
ElementType data;//数据域
}lNode;
//链表初始化
Status initNodeList(lNode *node){//初始化表，需要修改表，所以要传入地址
node = (lNode *)malloc(sizeof(lNode));
//创建的节点不存在
if (node == NULL)
return ERROR;
//将头节点指指针域置空
node->next = NULL;
return OK;
}
//在链表中插入节点
Status insertNodeList(lNode *node,int i,ElementType e){
if (node == NULL)
return ERROR;
int j = 1;
lNode *p,*s;
p = node;
//寻找第i-1个节点
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
//生成新节点
s = malloc(sizeof(lNode));
s->data = e;
//将p的后继赋值s
s->next = p->next;
//将s赋值给p的后继
p->next = s;
return OK;
}
//从链表中删除某个节点
Status deleteNodeList(lNode *node,int i, ElementType *e){
if (!node)
return ERROR;
int j = 1;
lNode *p,*temp;
p = node;
//找到第i-1个节点
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
//记录第i个节点
temp = p->next;
//将p的后继指向temp的后继
p->next = temp->next;
temp->next = NULL;
*e = temp->data;
//让系统回收该节点，释放内存
free(temp);
return OK;
}
//链表中获取数据
Status getNodeElement(lNode *node, int i, ElementType *e){
if(node == NULL)
return ERROR;
int j = 1;
lNode *p;
p = node->next;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return ERROR;
}
*e = p->data;
return OK;
}
//单链表清空
Status clearNodeList(lNode *node){
if (node == NULL)
return ERROR;
lNode *p,*q;
p = node->next;
while (p) {
q = p->next;
free(p);
p = q;
}
node->next = NULL;
return OK;
}
链表的头插法和尾插法，只是用于创建链表的时候。此时要是用Linklist *，因为要在内部进行创建
//链表的头插法
void createNodeHead(Linklist *node,int n){
//建立1个带头结点的单链表
*node = (lNode *)malloc(sizeof(lNode));
(*node)->next = NULL;
Linklist p;
for (int i = 1; i < n; i++) {
p = (lNode *)malloc(sizeof(lNode));
p->data = i;
//将新节点指向头节点
p->next = (*node)->next;
//头节点指向新节点
(*node)->next = p;
}
}
//尾插法
void createNodeTail(Linklist *node,int n){
Linklist p,tail;
//创建头节点
*node = malloc(sizeof(lNode));
(*node)->next = NULL;
//记录尾节点
tail = *node;
for (int i = 1; i < n; i++) {
//创建节点
p = malloc(sizeof(lNode));
p->data = i;
//表尾终端结点指向新建节点
tail->next = p;
//将当前的新结点定义为表尾终端结点
tail = p;
}
//将尾指针的next = null
tail->next = NULL;
}
