链表分为：单链表，双链表，循环链表，静态链表
一，单链表的定义
在内存空间中，各个节点在逻辑上相邻，但在物理上不相邻。
在单个的结点内部需要存放 数据域 和 指针域（存放指向下一个结点的指针）
优点：不要求一大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定的空间存放指针。
定义
typedef struct LNode{ //定义单链表结点类型
int data; //每个节点存放一个数据元素
struct LNode * next; //指针指向下一个节点
}LNode,* LinkList;
定义一个结构体类型，内部分别存放 元素 和 指向下一个节点的指针。
并且为了后续方便，在此使用typedef函数，将 struct LNode 简称为LNode.
初始化单链表
//初始化单链表
bool InitList(LinkList &L) {
/*无头结点
L = NULL; //空表，暂未节点
return true;
*/
//带头结点
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL) {
return false;
}
L->next = NULL;
return true;
}
void test() {
LinkList L; //声明一个指向单链表的指针
//初始化一个空表
InitList(L);
}
//判断单链表是否为空
bool Empty(LinkList L) {
return (L == NULL);
}
假设我们以及建立了这样一个单链表
1）按位序插入
假设我们将在2，3结点中插入一个新结点
只需要将2结点中的next指针指向新结点，将原指针赋值给新结点的next
//按位插入（带头结点）
//在单链表L中，第i个结点上插入数据域是e的新结点。
bool ListInsert(LinkList &L ,int i,int e) { //在单链表L中，第i个结点上插入数据域是e的新结点。
if (i < 1) {
return false;
}
LNode * p; //指针P指向当前扫描到的结点
int j = 0;
p = L; //p指向头结点（无数据）
while (p != NULL && j<i-1){//循环找到第i-1个结点
p = p->next;
j++;
}
if (p == NULL) { //i值不合法
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
归纳：从头结点开始循环，找到第i-1位的结点。将s（新结点）的地址赋值给i-1位的结点的next，将原来的第i位结点的地址赋值给s的next即可。
*注意i的合法性。
平均时间复杂度o (n)；
/* 不带头结点
if (i == 1) {
LNode* s = (LNode*)malloc(sizeof(LNode));
s->next = L;
s->data = e;
L = s;
return true;
}
*/
后插操作
只需将结点1的指针指向新结点，将原指针赋值给新结点的next
（在结点p后面插入一个元素e）
//按位插入（后插）
bool InsertNextNode(LNode* p, int e) { //在结点p后面插入一个元素e
//判断结点p是否存在
if (p == NULL) {
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL) { //分配内存失败
return false;
}
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
前插操作
//指定结点的前插
bool InsertPriorNode(LNode* p, int e) { //在结点P前插入一个新元素e
//数据跑路型(无需寻找p结点的前驱结点)
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = p->data;
p->data = e;
s->next = p->next;
p->next = s;
}
bool InsertPriorNode2(LNode* t, LNode* s) { //在结点P前插入一个新结点S
if (t = NULL) {
return false;
}
if (s == NULL) {
return false;
}
s->next = t->next;
t->next = s;
int temp = t->data;
t->data = s->data;
s->data = temp;
}
//按位序删除
若要将第三个结点删除：只需将它的下一个结点存放的指针赋值给第二个结点即可
最后通过free函数释放掉要删除的结点的内存即可
bool ListDelete(LinkList& L, int i, int e) { //将单链表中第i个结点删除
if (i < 1) {
return false;
}
int j = 0;
LNode* K;
K = L;
//循环找到第i-1位的结点
while (K!=NULL && j<i-1)
{
K = K->next;
j++;
}
//判断 i-1位结点 是否存在以及 i位结点是否存在
if (K == NULL|| K->next==NULL) {
return false;
}
//创一个新的结点q，令其等于 要删除的第i位结点
LNode* q;
q = K->next;
K->next = q->next; //将i结点中存放下一位结点的指针赋值给 i-1结点
e = q->data; //提出删除结点的值
free(q); //释放内存
return true;
}
//按结点删除
若要将1结点删除，则将它的下结点的data和next复制到1结点即可
最后释放下节点。
//删除指定结点
bool DeleteNode(LNode* p) {
if (p == NULL) {
return false;
}
LNode* q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);
return true;
}
**但如果要删除的结点是单链表中的最后一个结点，则会发生错误。
删除最后一个结点需要遍历整个单链表，同上。
总结：单链表不能逆向检索，有时会不太方便。
1）按位查找
//单链表的查找
//单链表的按位查找
LNode * GetElem(LinkList & L, int i) {
if (i < 1) {
return NULL;
}
LNode * p;
p = L;
int j = 0;
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
2）按值查找与求表长
//按值查找
LNode* LocateElem(LinkList L, int e) {
LNode* p = L;
while (p != NULL && p->data != e)
{
p = p->next;
}
return p;
}
//求表长
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p != NULL)
{
p = p->next;
len++;
}
return len;
}
单链表的建立分为头插法和尾插法
一，尾插法创建单链表
//尾插法插入数据
LinkList TailInsert(LinkList& L) { //用户输入创建单链表
int x;
L = (LinkList)malloc(sizeof(LNode)); //初始化空表
LNode* s,* r = L;
scanf("%d", &x);
while (x != 999) //输入999结束
{
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", x);
}
r->next = NULL;
return L;
}
二，头插法建立单链表
//头插法建立单链表
LinkList HeadInsert(LinkList& L) {
LNode* s;
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next == NULL; //防止内存 中的脏数据
scanf("%d", &x);
while (x != 9999) //输入9999结束建立
{
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", x);
}
return L;
}
