2-2线性表-链表

一.单链表

（一）特点
1.优点
不要求大片的连续空间，改变容量方便
2.缺点
不可以随机存取，要耗费一定的空间存放指针

（二）代码定义
1.初步代码

struct LNode {//结点
	ElemType data;
	struct LNode *next;
};
1
2
3
4

2.新增结点

struct LNode {//结点
	ElemType data;
	struct LNode *next;
};
struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));
1
2
3
4
5

简化：将struct LNode定义为LNode

struct LNode {//结点
	ElemType data;
	struct LNode *next;
};
typedef struct LNode LNode;//将struct LNode定义为LNode
LNode* p = (LNode*)malloc(sizeof(LNode));//简化
1
2
3
4
5
6

3.进一步简化

struct LNode {//结点
	ElemType data;
	struct LNode *next;
};
typedef struct LNode LNode;//将struct LNode定义为LNode
typedef struct LNode *LinkList;//将struct LNode *定义为LinkList
1
2
3
4
5
6

即

typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
1
2
3
4

因此 LNode *L 等价于 LinkList L

更多的，使用
LinkList表示单链表，用LNode *表示结点

（三）基本操作1
1.带头结点的单链表，初始化与判空

#include<stdlib.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L) {//初始化
	L = (LNode*)malloc(sizeof(LNode));//头指针L指向无数据的头结点
	if (L == NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点的next指针域设为NULL
	return true;
}

bool Empty(LinkList L) {//判空
	if (L->next == NULL)
		return true;
	else
		return false;
}

void test() {
	LinkList L;//创建单链表L
	InitList(L);//初始化
	Empty(L);//判空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.不带头结点的单链表，初始化与判空

#include<stdlib.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L) {//初始化
	L = NULL;
	return true;
}

bool Empty(LinkList L) {//判空
	if (L == NULL)
		return true;
	else
		return false;
}

void test() {
	LinkList L;//创建单链表L
	InitList(L);//初始化
	Empty(L);//判空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（四）基本操作2
1.头插法建立单链表

#include<stdlib.h>
#include<stdio.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList &L) {
	LNode *s;//工作指针
	int x;//要插入的值
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	L->next = NULL;
	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));//s指向新结点
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

每个结点插入的时间复杂度O(1)，设单链表长n，则总时间复杂度O(n)

2.尾插法建立单链表

#include<stdlib.h>
#include<stdio.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

LinkList List_TailInsert(LinkList &L) {
	LNode *s;//工作指针
	LNode *r = L;//r做为表尾指针
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	scanf("%d", &x);
	while (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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度O(n)

3.按序号查找

#include<stdlib.h>
#include<stdio.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

LNode *GetElem(LinkList L, int i) {
	int j = 0;//0号位是头结点
	LNode *p = L;//p指向头结点
	/*以上两行也可写为
	int j=1;//从第一个结点开始
	LNode *p=L->next;//p指向第一个结点
	*/
	if (i == 0)
		return L;//0号是头结点，返回
	if (i < 1)
		return NULL;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度O(n)

4.按值查找

#include<stdlib.h>
#include<stdio.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

LNode* LocateElem(LinkList L, ElemType e) {
	LNode *p=L->next;
	while (p!=NULL&&p->data!=e) {
		p = p->next;
	}
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度O(n)

5.按位序插入（带头结点）

#include<stdlib.h>
#include<stdio.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LinkList &L, int i, ElemType e) {
	//在第i个位置插入元素e
	if (i < 1)
		return false;
	LNode *p=L;//p指向头结点
	int j = 0;//从0号位的头结点开始
	while (p != NULL &&j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL) {
		return false;
	}
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

平均时间复杂度O(n)

6.按位序插入（不带头结点）

#include<stdlib.h>
#include<stdio.h>
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LinkList &L, int i, ElemType e) {
	if (i < 1)
		return false;
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;//头指针指向新结点
		return true;
	}
	LNode *p=L;//p指向第一个结点
	int j = 1;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next = p->next;
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

7.指定结点前插
（1）传入要插入元素

bool InsertPriorNode(LNode* p, ElemType e) {
	if (p == NULL)
		return false;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->next = p->next;//p当前结点，s新结点
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）传入结点

bool InsertPriorNode(LNode* p, LNode *s) {
	if (p == NULL||s==NULL)
		return false;
	s->next = p->next;//p当前结点，s新结点
	p->next = s;
	ElemType temp = p->data;//存储p的数据
	p->data = s->data;
	s->data = temp;
	return true;
}
1
2
3
4
5
6
7
8
9
10

8.按位删除（带头结点）

bool ListDelete(LinkList &L, int i, ElemType &e) {
	if (i < 1)
		return false;
	LNode *p=L;
	int j = 0;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	if (p->next == NULL)
		return false;//p已经是最后一个结点，无法完成删除
	LNode *q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二.双链表

1.基本定义

typedef struct DNode {
	ElemType data;
	struct DNode *prior, *next;
}DNode,DLinklist;
1
2
3
4

2.初始化

typedef struct DNode {
	ElemType data;
	struct DNode *prior, *next;
}DNode,*DLinklist;

bool InitDLinkList(DLinklist &L) {
	L=(DNode*)malloc(sizeof(DNode));
	if (L == NULL)
		return false;
	L->prior = NULL;
	L->next = NULL;
	return true;
}

void testDLinklist() {
	DLinklist L;
	InitDLinkList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.判空

bool Empty(DLinklist L) {
	if (L->next == NULL)
		return true;
	else
		return false;
}
1
2
3
4
5
6

4.插入

bool InsertNextDNode(DNode *p, DNode *s) {
	//p当前，s新
	s->next = p->next;
	if(p->next!=NULL)
		p->next->prior = s;
	s->prior = p;
	p->next = s;
}
1
2
3
4
5
6
7
8

在这里插入图片描述
5.删除

bool DeleteNextDNode(DNode *p) {//删除某结点
	if (p == NULL)
		return false;
	DNode *q = p->next;
	if (q == NULL)
		return false;
	p->next = q->next;
	if(q->next!=NULL)
		q->next->prior = p;
	free(q);
	return true;
}
bool DestoryList(DLinklist &L) {//销毁双链表
	while (L->next != NULL) {//依次删除头结点的后继结点
		DeleteNextDNode(L);
	}
	free(L);
	L = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里插入图片描述

三.循环链表

1.循环单链表
在这里插入图片描述
（1）初始化

typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL)
		return false;
	L->next = L;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）判空
L->next=L

（3）判断结点p是否为循环单链表的表尾结点
p->next=L

2.循环双链表
在这里插入图片描述
（1）初始化

typedef struct DNode {
	ElemType data;
	struct DNode *next,*prior;
}DNode,*DLinkList;

bool InitDList(DLinkList &L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL)
		return false;
	L->prior = L;
	L->next = L;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）判空
L->next=L

（3）判断结点p是否为循环双链表的表尾结点
p->next=L

（4）插入

bool InsertNextDNode(DNode *p,DNode *s){
	//s是新结点，p是当前结点
	s->next = p->next;
	p->next->prior = s;
	s->next = p;
	p->prior = s;
}
1
2
3
4
5
6
7

（5）删除

bool DeleteDNode(DNode *p){
	//p是q的前驱结点，要删除后面的q
	DNode *q = p->next;
	if (q == NULL)
		return false;
	p->next = q->next;
	q->next->prior = p;
	free(q);
}
1
2
3
4
5
6
7
8
9

四.静态链表

1.特点
（1）优点：增、删操作不需要大量移动元素
（2）缺点：不能随机存取，只能从头结点开始依次查找，容量固定不可变
在这里插入图片描述
2.代码

#define MaxSize 10
struct Node {
	ELemType data;
	int next;
};
void testSLinkList() {
	struct Node a[MaxSize];
}
1
2
3
4
5
6
7
8

即

#define MaxSize 10
struct Node {
	ELemType data;
	int next;
};
typedef struct Node SLinkList[MaxSize];
void testSLinkList() {
	SLinkList a;//用SLinkList定义一个长度为MaxSize的Node型数组
}
1
2
3
4
5
6
7
8
9

即

#define MaxSize 10
typedef struct {
	ElemType data;
	int next;
}SLinkList[MaxSize];
void testSLinkList() {
	SLinkList a;
}
1
2
3
4
5
6
7
8

相关阅读:
【LeetCode】No.46. Permutations -- Java Version
＞＞数据管理：DAMA简介
 采集数据重复解决方法
 Spark的基础
 PostgreSQL 数据类型详细说明
 Python基础分享之面向对象的进一步拓展
 小程序源码：纯头像微信小程序源码下载,多分类头像自动采集
 Java锁的逻辑（结合对象头和ObjectMonitor）
将符号分隔的文本文件txt转换为excel的实现
 经纬高到北东天的坐标相互转换matlab
原文地址：https://blog.csdn.net/weixin_45825865/article/details/125603316