《408篇》线性表与链表
目录
一、线性表
1.1、顺序表
1.1.1、定义顺序表(静态分配)
1.1.2、初始化InitList(&L)（静态分配）
1.1.3、定义顺序表(动态分配)
1.1.4、初始化InitList(&L)（动态分配）
1.1.5、插入元素ListInsert(&L, i, e)
1.1.6、删除元素ListDelete(&L, i, &e)
1.1.7、按值查找 LocateElem(&L, i, e)
1.1.8、测试
1.2、单链表
1.2.1、定义链表
1.2.2、初始化链表
1.2.3、头插法
1.2.4、尾插法
1.2.5、按序号查找节点
1.2.6、按值查找节点
1.2.7、插入元素
1.2.8、删除元素
1.3、双链表
1.3.1、双链表的类型定义
1.3.2、双链表的插入操作
1.3.3、双链表的删除操作
一、线性表
线性表一般包含以下功能：
初始化线性表：将一个线性表进行初始化，得到一个全新的线性表。
获取指定位置上的元素：直接获取线性表指定位置i上的元素。
获取元素的位置：获取某个元素在线性表上的位置i。
插入元素：在指定位置i上插入一个元素。
删除元素：删除指定位置i上的一个元素。
获取长度：返回线性表的长度。
线性表的结构一般有两种，一种是顺序存储实现，还有一种是链式存储实现。
1.1、顺序表
1.1.1、定义顺序表(静态分配)
#define Maxsize 50 //定义线性表最大长度
typedef int ElemType; //定义元素类型
typedef struct { //定义结构体ElemType data[Maxsize]; //定义顺序表的元素int length; //定义线性表的长度
}SqList;1.1.2、初始化InitList(&L)（静态分配）
void InitList(SqList *L){L -> length = 10;
}1.1.3、定义顺序表(动态分配)
typedef int ElemType; //定义元素类型
typedef struct { //定义结构体ElemType *data; //定义顺序表的元素int length; //定义线性表的长度int Maxsize; //定义最大长度
}SqList;1.1.4、初始化InitList(&L)（动态分配）
_Bool InitList(SqList *L){L->length = 10;L->data = malloc(sizeof (ElemType) * L->length); //malloc函数手动申请一片空间if(L->data == NULL) return false; // 如果申请的结果为NULL表示内存空间分配失败L->Maxsize = 0; //默认长度0return true;
}1.1.5、插入元素ListInsert(&L, i, e)
//在位置i插入元素e
_Bool ListInsert(SqList *L, int i, ElemType e){if(i < 1 || i > L->length + 1) return false; //判断i是否合法，小于1或者大于最大长度返回falseif(L->length > L->Maxsize) return false; //存储空间已满，不可插入
// j为顺序表的长度，将j向i靠近（j--）到达i的位置for (int j = L->length; j >= i; j--) {L->data[j] = L->data[j - 1]; //将j位置的元素后移一位，通过for不断循环直到到达i位置，此时候原数组中i位置空缺
}L->data[i - 1] = e; //此时j在i的位置，由于顺序表从0开始，在i位置就是在L.data[j-1]插入L->length++; //顺序表长度+1return true;
}1.1.6、删除元素ListDelete(&L, i, &e)
//在第i个位置删除元素e
_Bool ListDelete(SqList *L, int i, ElemType *e){if(i < 1 || i > L->length + 1) return false; //判断i是否合法，小于1或者大于最大长度返回falsee = L->data[i - 1]; //将第i个位置的元素赋给e，此时顺序表中第i个位置空for (int j = i; j < L->length; j++) {L->data[j - 1] = L->data[j]; //循环，将第j个赋给第j-1个，也就是向前放}L->length--; //长度减1return true;
}1.1.7、按值查找 LocateElem(&L, i, e)
//按值查找
int LocateElem(SqList *L, ElemType e) {int i;for (i = 0; i < L->length; i++) { //遍历顺序表if (L->data[i] == e) return i + 1; //当L.data[i] == e时，返回该元素的位序，i是该元素的下标}return 0;
}1.1.8、测试
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ElemType;
//定义一个顺序表，动态存储
typedef struct {ElemType *data;int length,Maxsize;
}SqList;//初始化一个顺序表
_Bool InitList(SqList *L){L->data = malloc(sizeof (ElemType) * L->length);if(L->data == NULL) return false;L->length = 0; //初始化为0L->Maxsize = 50; // 定义最大长度return true;
}//插入元素
//在i位置插入元素e
_Bool ListInsert (SqList *L, int i, ElemType e){if(i < 1 || i > L->length + 1) return false;if(i > L->Maxsize) return false;for (int j = L->length; j >= i; j--) {L->data[j] = L->data[j-1];}L->data[i-1] = e;L->length ++;return true;
}//删除元素
_Bool ListDelete(SqList *L, int i, ElemType *e){if(i < 1 || i > L->length + 1) return false;if(i > L->Maxsize) return false;e = L->data[i-1];for (int j = i; j < L->length; j++) {L->data[j-1] = L->data[j];}L->length --;return true;
}int ListSize(SqList *L){return L->length;
}//按值查找
int LocateElem(SqList *L, ElemType e) {int i;for (i = 0; i < L->length; i++) { //遍历顺序表if (L->data[i] == e) return i + 1; //当L.data[i] == e时，返回该元素的位序，i是该元素的下标}return 0;
}void printList(SqList *L){for (int i = 0; i < L->length; ++i) {printf("%d", L->data[i]);}printf("\\n");
}int main() {SqList L;InitList(&L);ListInsert(&L, 1, 6);printList(&L);ListInsert(&L, 2, 44);printList(&L);ListInsert(&L, 3, 444);printList(&L);
}
1.2、单链表
链表不同于顺序表，顺序表采用数组作为存储容器，需要分配一块连续且完整的内存空间进行使用，而链表则不需要，它通过一个指针来连接各个分散的节点，形成一个链状的结构。它不需要申请连续的空间，只需要按照顺序连接即可，逻辑上依然相邻。
1.2.1、定义链表
typedef int ElemType;
typedef struct LNode{ElemType data; //数据域struct LNode * next; //指向下一节点的指针
}LNode, *LinkList;1.2.2、初始化链表
void InitList(LNode *L){ // 将定义的结构体命名为LL->next = NULL; // 链表L中的next指针指向NULL
}
1.2.3、头插法
//头插法
LinkList List_HeadInsert(LinkList &L){LNode *s; int x; //定义结点指针s，插入数据xL = (LinkList)malloc(sizeof (LNode)); //创建头结点,前面表示LinkList型的L->next = NULL; //初始化链表，指针指向NULLscanf("%d", &x); //输入结点的值，也就是数据域while (x!=9999) { //输入9999时表示结束链表创建s = (LNode *) malloc(sizeof(LNode)); //创建一个新的，待插入的结点s->data = x;s->next = L->next;L->next = s;scanf("%d", &x); //继续读取数据，读一次插一次}return L; }
1.2.4、尾插法
//尾插法
LinkList List_TailInsert(LinkList L){int x; //数据域L = (LinkList) malloc(sizeof (LNode)); //为链表开创一段内存空间LNode *s, *r=L; //定义两个指针，其中r是表尾指针，s是指向新结点的指针scanf("%d", &x); //通过输入接受到数据xwhile (x!=9999) {s = (LNode *) malloc(sizeof(LNode)); //为待插入的结点赋予一段内存空间s->data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL; //表尾指针置空return L;}
1.2.5、按序号查找节点
//按序号查找节点，序号为i
_Bool GetElem(LinkList L, int i) {if (i < 1) return 0; //当序号小于1时，此时不存在，返回0int j = 1; //计数LNode *p = L->next; //第一个位置赋值给pwhile (p != NULL && j < i) { //当j<i时继续遍历，当j=i时跳出遍历，当p不断后移后直到NULL，跳出循环p = p->next; //当j<i时候p指向它的下一个节点j++; // 遍历一次j就+1}return p;
}
1.2.6、按值查找节点
LNode *LocateElem(LinkList L, ElemType e){ //待查找的链表L 数据元素为eLNode *p = L->next; // p指向头结点while (p!=NULL && p->data != e) // 当p为空或查找到p的数据域为e时跳出循环p = p->next; // 没找到，向后指，p指向下一节点return p;
}1.2.7、插入元素
P = GetElem(L, i-1); //调用GetElem函数找到前驱节点
s -> next = p -> next; // 结构同前面头插法
p -> next = s;1.2.8、删除元素
p = GetElem(L, i-1); //调用GetElem函数获取待删除元素前一个位置
q = p -> next; // q指针指向待删除结点
p -> next = q -> next; // p指向q的后一个结点
free(q); // 释放q结点1.3、双链表
1.3.1、双链表的类型定义
typedef int ElemType;
//定义双链表的结点类型
typedef struct DNode{ElemType data; //数据域struct DNode *prior, *next; // 前驱结点的指针；后继结点的指针
}DNode, *DLinklist;
1.3.2、双链表的插入操作
一图胜千言
s -> next = p -> next;
p -> next -> prior = s;
s -> prior = p;
p -> next = s;1.3.3、双链表的删除操作
p->next = q->next;
q->next->prior=p;
free(q);