概念
线性表是零个或多个具有相同特性的数据元素组成的有限序列，该序列中所含元素的个数叫做线性表的长度，线性表有以下几个特点：
-
首先是一个序列
-
其次是有限的
-
可以是有序的也可以是无序的
-
线性表的开始元素没有前驱元素只有后继元素，线性表的结束元素没有后继元素只有前驱元素，除了开头元素和结尾元素以外，每个元素都有且只有一个前驱元素和后继元素
线性表的结构分为顺序结构和链式结构
顺序结构
顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到从指定位置开始的一块连续的存储空间，重点是连续的存储空间。
数组长度和线性表的长度区别：数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的，线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
关于顺序表的创建和初始化
#define SUCCESS 1
#define FAIL 0
typedef int elemType;
typedef int status;
typedef struct {
elemType *data;
int length;
}Sqlist;
status initList(Sqlist *list){
list->data = malloc(sizeof(elemType) * MAXSIZE);
if(!list->data) exit(FAIL);
list->length = 0;
return SUCCESS;
}
插入算法步骤
-
如果插入位置不合理，抛出异常；
-
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
-
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
-
将要插入的元素填入位置i处；
-
长度+1
代码如下：
status insertData(Sqlist *list,int index,elemType data){
if((index<1) || (index>list->length+1)) return FAIL;
//存储空间已满
if(L->length == MAXSIZE) return FAIL;
//插入数据不在表尾,则先移动出空余位置
if(index <= list->length){
for(int j = list->length-1; j>=index-1;j--){
list->data[j+1] = L->data[j];
}
}
list->data[index-1] = data;
++list->length;//长度+1
return SUCCESS;
}
删除步骤
-
如果删除位置不合理，抛出异常；
-
取出删除元素；
-
从删除位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
-
长度减1
代码如下：
status listDelete(Sqlist *list,int i){
//线性表为空
if(list->length == 0) return FAIL;
//i值不合法判断
if((i<1) || (i>list->length+1)) return FAIL;
for(int j = i; j < list->length;j++){
//被删除元素之后的元素向前移动
list->data[j-1] = list->data[j];
}
//表长度-1;
list->length --;
return SUCCESS;
}
链式结构
链式结构如图所示
链式结构.png
链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。
在顺序存储结构中，每个数据元素只需要存储数据元素就可以了。现在链式结构中，处理要存储数据元素信息之外，还要存储它的后继元素的存储地址。
在链表中，为了方便定位链表，我们一般会在创建链表的时候，先给他一个头节点，头节点没有实际内容的作用，作为一个链表的哨兵，可以方便定位。
链表主要分成单向链表、单向循环链表、双向链表、双向循环链表，下面我们分别来讲讲。
单向链表
单向链表每一个节点，都包含一个data和一个指向下一个节点的指针
单向链表.png
在初始化单向链表的时候，需要注意头节点是没有内容的，->next下一个节点才是真正的首元节点，代码如下：
Status InitList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
//存储空间分配失败
if(*L == NULL) return ERROR;
//将头结点的指针域置空
(*L)->next = NULL;
return OK;
}
单向链表插入和删除
先来看下示意图：
单向链表插入删除.png
插入的主要步骤：
-
定义一个指针指向链表头节点，初始化j从1开始；
-
当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
-
若到链表末尾p为空，则说明第i个结点不存在；否则查找成功，在系统中生成一个空结点s
-
将数据元素e赋值给 s->data；
-
单链表的插入标准语句 s->next; p->next=s;
-
返回成功
删除的主要步骤
-
定义两个指针指p、s指向链表头节点，初始化i从1开始
-
判断当前链表是否只有头节点，如果不存在其他节点，return error，否则继续执行
-
判断是否删除的首元节点，删除第一个节点的时候需要注意把头节点的指针移动到下一个节点
-
释放，并返回成功
代码如下：
单向链表插入
Status ListInsert(LinkList *L,int i,ElemType e){
int j;
LinkList p,s;
p = *L;
j = 1;
//寻找第i-1个结点
while (p && j<i) {
p = p->next;
++j;
}
//第i个元素不存在
if(!p || j>i) return ERROR;
//生成新结点s
s = (LinkList)malloc(sizeof(Node));
//将e赋值给s的数值域
s->data = e;
//将p的后继结点赋值给s的后继
s->next = p->next;
//将s赋值给p的后继
p->next = s;
return OK;
}
单向链表删除
Status ListDelete(LinkList *L,int i,ElemType *e){
int j;
LinkList p,q;
p = (*L)->next;
j = 1;
//查找第i-1个结点,p指向该结点
while (p->next && j<(i-1)) {
p = p->next;
++j;
}
//当i>n 或者 i<1 时,删除位置不合理
if (!(p->next) || (j>i-1)) return ERROR;
//q指向要删除的结点
q = p->next;
//将q的后继赋值给p的后继
p->next = q->next;
//将q结点中的数据给e
*e = q->data;
//让系统回收此结点,释放内存;
free(q);
return OK;
}
单向循环链表初始化
先来看一下单向循环链表和单向链表的区别，单向循环链表图如下
单向循环链表.png
单向循环链表就像一个首尾相接的蛇，他的最后一个节点的next不是指向NULL，而是指向了首元节点，以此达到循环。在初始化的时候，需要注意
初始化的时候，需要创建一个新的节点指向自身，往里面增加节点的时候需要注意最后一个节点需要指向首元节点。
#define ERROR 0
#define OK 1
#define MAXSIZE 20
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
Status CreateList(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("输入节点的值，输入0结束\n");
while(1) {
scanf("%d",&item);
if(item==0) break;
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己
(*head)->next=*head;
if(*L==NULL) {
*L = (LinkList)malloc(sizeof(Node));
if(!L) exit(0);
(*L)->data=item;
(*L)->next=*L;
} else {
//输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
for (target = *L; target->next != *L; target = target->next);
temp=(LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data=item;
temp->next=*L; //新节点指向头节点
target->next=temp;//尾节点指向新节点
}
}
return OK;
}
单向循环链表插入和删除
插入的主要步骤：
-
定义一个指针target指向链表头节点，初始化j从1开始；
-
当j < i 时，就遍历链表，让target的指针向后移动，不断指向下一个结点，j累加1；
-
若到链表末尾target为空，则说明第i个结点不存在；否则查找成功，在系统中生成一个空结点s
-
将数据元素e赋值给 temp->data = data；
-
单链表的插入标准语句 temp->next = target->next; target->next = temp;
-
返回成功
需要注意的是，在插入节点的时候，我们需要判断插入位置是否是第一个节点。如果是第一个节点，需要让新的节点next指向原节点，并且头节点指向新增加节点，修改尾节点。
删除的主要步骤
-
定义两个指针指temp、taeget向链表头节点，初始化i从1开始
-
判断当前链表收否只有头节点，如果不存在其他节点，return error，否则继续执行
-
删除找到的节点，修改前一个节点的next指向，释放被删除的节点
-
返回成功
删除需要注意头节点
代码定义如下
Status ListInsert(LinkList *L, int place, int num) {
LinkList temp, target;
int i;
if (place == 1) {
//如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2. 找到链表最后的结点_尾结点,
//3. 让新结点的next 执行头结点.
//4. 尾结点的next 指向新的头结点;
//5. 让头指针指向temp(临时的新结点)
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
*L = temp;
} else {
//如果插入的位置在其他位置;
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
//3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
//4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) ;
temp->next = target->next;
target->next = temp;
}
return OK;
}
Status LinkListDelete(LinkList *L, int place) {
LinkList temp, target;
int i;
//temp 指向链表首元结点
temp = *L;
if (temp == NULL) return ERROR;
if (place == 1) {
if ((*L)->next == (*L)) {
(*L) = NULL;
return OK;
}
target->next = (*L)->next;
for (target = *L; target->next != *L; target = target->next) ;
temp = *L;
*L = (*L)->next;
target->next = *L;
free(temp);
} else {
for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) ;
temp = target->next;
target->next = temp->next;
free(temp);
}
return OK;
}
双向链表和双向循环链表
双向链表相比较单向链表，多了一个前驱，而双向循环链表的则在双向链表的情况下，多了首尾的指向
双向链表.png
双向循环链表.png
初始化
双向和双向循环链表创建.png
对比的代码如下
// 双向链表
Status CreateList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
if ((*L) == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
return OK;
}
// 双向循环链表
Status CreateList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
if ((*L) == NULL) return ERROR;
(*L)->prior = *L; // 这里和上面不一样，指向自己，
(*L)->next = *L;
return OK;
}
插入
双向链表的插入和单向列表的插入对比，其实是相似的，不同之处在于，双向链表在找到需要插入的节点后，需要先指定插入节点的prior和next，然后再确定proir->next 和 next->prior，大致步骤如下
-
判断插入的位置是否合法，不合法return error，创建节点temp和指向头节点的链表p，i从1开始
-
遍历链表，让p的指针向后移动，不断指向下一个结点，i累加1；
-
若到链表末尾p为空，则说明第i个结点不存在；否则查找成功，在系统中生成一个空结点temp
-
将数据元素e赋值给 temp->data = e；
-
指定temp的前驱和后驱
-
替换temp的前驱的后驱，temp后驱的前驱
-
返回成功
需要注意的是，在插入节点的时候，我们需要判断插入位置是否是第一个节点。如果是第一个节点，需要让新的节点next指向原节点，并且头节点指向新增加节点，修改尾节点。
双向循环链表步骤比双向链表，少了一步判断首元节点，因为循环链表的尾节点就是指向首元节点。但是需要判断尾节点的指向
代码如下：
// 插入
Status ListInsert(LinkList *L, int place , ElemType v) {
if (place < 1) return ERROR;
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->data = v;
temp->prior = NULL;
temp->next = NULL;
// 找到插入前的节点
LinkList p = *L;
// 找到插入位置 (place 位置的前一个结点)
for (int i = 1; i < place; i++) {
if (p->next == NULL) break;
p = p->next;
}
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
} else {
p->next->prior = temp;
temp->next = p->next;
temp->prior = p;
p->next = temp;
}
return OK;
}
Status ListInsert(LinkList *L, int place , ElemType v) {
// 有头节点 所以插入位置不能是<1
if (place < 1) return ERROR;
// 新节点
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->data = v;
temp->prior = NULL;
temp->next = NULL;
// 找到插入前的节点
LinkList p = *L;
// 找到插入位置 (place 位置的前一个结点)
for (int i = 1; i < place; i++) {
if (p->next == NULL) break;
p = p->next;
}
// 注意：因为有头节点，所有新节点一定是在头节点之后，所以头指针L，一定指向头节点
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
} else {
p->next->prior = temp;
temp->next = p->next;
temp->prior = p;
p->next = temp;
}
return OK;
}
删除
双向链表对比与单向链表的删除，需要注意是不是删除尾节点，因为尾节点的next需要为NULL；双向循环链表的删除对比单向循环链表，仍然需要考虑是不是尾节点，因为他有下一个节点，把下一个节点和他前一个节点建立互相指向，释放自己。因为有头节点的引入，所以我们不需要额外关注头指针的指向了。
代码示例如下：
// 双向链表删除
Status ListDelete(LinkList *L, int place, ElemType *v) {
// 有头节点 所以插入位置不能是<1
if (place < 1) return ERROR;
// 找到place位置的节点
LinkList p = (*L)->next; // 从首元节点开始
int i = 1
for (; i < place; i++) {
if (p->next == NULL) break;
p = p->next;
}
if (i < place) return ERROR;
*v = p->data;
if (p->next == NULL) {
p->prior->next = NULL;
free(p);
} else {
// p是任意位置的节点
// 1、将p的后一个节点指向p的前一个节点
// 2、将p的前一个节点指向p的后一个节点
// 3、释放
p->next->prior = p->prior;
p->prior->next = p->next;
free(p);
}
return 1;
}
// 双向循环链表删除
Status ListDelete(LinkList *L, int place, ElemType *v) {
if (place < 1) return ERROR;
LinkList p = (*L)->next; // 从首元节点开始
int i = 1;
for (; i < place; i++) {
if (p->next == NULL) break;
p = p->next;
}
if (i < place) return ERROR;
*v = p->data;
// p是任意位置的节点
// 1、将p的后一个节点指向p的前一个节点
// 2、将p的前一个节点指向p的后一个节点
// 3、释放
p->next->prior = p->prior;
p->prior->next = p->next;
free(p);
return 1;
}
结尾
总算把单向链表、单向循环链表、双向链表、双向循环链表理了一遍，但是结尾处有点匆忙，下次有时间再补一下图片和详细优化吧。写博客真的好累啊(´▽｀)
网友评论