数据结构-------单链表

单链表：

每个结点除了存放数据元素外，还要存储指向下一个节点的指针。

单链表的特点：

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

用代码定义一个单链表：

链表名，数据，节点指针

struct LNode //定义单链表节点的类型
{
	ElemType data;//每个结点存放一个数据元素
	struct LNode* next;//指针指向下一个节点
};
//需在内存中增加一个节点
struct LNode* p = (struct LNode*)malloc(sizeof(struct LNode));
//在内存中申请一个节点所需的空间，并用指针p指向这个节点
1
2
3
4
5
6
7
8

typedef关键字------数据类型重命名：

方法：

typedef <数据类型> <别名>
1

例1：

int mian()
{
	int X=1;
	int* p;
	typedef int zhengshu;//将类型int起别名为zhengshu
	typedef int* zhengshuzhizhen;//将类型int*起别名为zhnegshuzhizhen
	//数据类型重命名后，别名可以直接使用
	zhengshu X = 1;
	zhengshuzhizhen p;	
}
1
2
3
4
5
6
7
8
9
10

对结构体类型名重命名：

typedef struct LNode //给结构体LNode起别名
{
	ELemtype data;//存放每个结点的数据元素
	struct LNode* next;//存放指向下一个节点的指针

}LNode,*LinkList;//命结构体LNode的别名为LNode/*LinkList
LNode* GetElem(LinkList L, int i)
//将函数GetElem的返回类型设置为LNode*是为了强调返回类型为指针
//LinkList为了强调L是一个链表
{
	;
}
1
2
3
4
5
6
7
8
9
10
11
12

单链表的初始化：

不带头节点的单链表：初始化和判空

举例：

#include
//初始化一个单链表
bool InitList(LinkList &L)
{
	L =NULL;//初始化链表：防止该空间中之前遗留的数据影响
	return true;
}
bool Empty(LinkList L) //判断链表是否为空链表
{
	if (L == NUll)
		return true;
	else
		return false;
}
void test()
{
	LinkList L;//声明一个指向单链表的指针
	InitList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

带头节点的单链表：分配头结点和判空

typedef struct LinkNode
{
	int  data;
	struct LNode* next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L = （LNode*)malloc(sizeof(LNode));//分配一个头结点
	if (L == NUll)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点之后暂时还没有节点，头结点不存储数据
	return true;
}
bool Empty(LinkList L)//判断单链表是否为空
{
	if (L->next == NULL)
		return true;
	else
		return false;
}
void test()
{
	LinkList L;//声明一个指向单链表的指针
	InitList(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

单链表按位序插入：

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e

带头结点：

方法：先找到第i-1个元素，申请一个节点空间用来存放需要插入的元素，再通过指针实现元素的插入。

#include
#include
typedef struct LNode
{
	ElemType  data;
	struct LNode* next;
}LNode, * LinkList;
bool ListInsert(LinkList &L, ELemType i, ElemType e)
{
	if (i < 1)//位序从1开始
		return false;
	//找到要插入的位置的前一个节点
	LNode* p;//指针p指向头结点
	int j = 0;//扫描p指向的是第几个节点
	p = L;//使指向节点的指针指向单链表L的头结点（不存放数据）
	while (p != NULL && j < i - 1)//找到要插入的位置的前一个节点
	{
		p = p->next;
		j++;
	}
	if (p == NULL)//i值不合法
		return false;
	//实现插入节点和后续链表的链接
	LNode* s = (LNode*)malloc(sizeof(LNode));//申请新的节点空间
	s->data = e;//将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

插入过程如下所示：
注意：

如下所示的代码顺序不能发生改变，否则会出现无法和后面的节点：

s->next = p->next;
p->next = s;
1
2

不带头结点：

方法：与带头结点的插入方法相类似，不同之处在于当我们要插入元素在表头时，我们就需要修改头结点，并且指针的指向是从1开始的，而带头结点的链表，指针指向是从0开始。

#include
#include
typedef struct LNode
{
	ElemType  data;
	struct LNode* next;
}LNode, * LinkList;
bool ListInsert(LinkList &L, ELemType i, ElemType e)
{
	if (i < 1)//位序从1开始
		return false;
	//当插入到表头位置，需要修改头结点
	if (i == 1)
	{
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode* p;
	int j = 1;//指向第一个节点
	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;//将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
32
33
34
35

插入过程如下所示：

与带头结点不同的是：

不带头节点的链表，当我们插入的元素的位置在表头时，此时的头结点已经变成我们插入的这个元素，也就是说，不带头节点的链表，它的头结点是会发生变化的，也就是位序为1的元素，但带头结点的链表，它的头结点是不会发生变化的，我们可以形象的将之称为位序为0的节点，但实际上位序为0的节点并不存在。

指定节点实现后插操作：

方法：先找到第i-1个节点，再调用后插（按位序插入）操作

bool ListInsert(LinkList& L, int i, ELemType e)
{
	if (i < 1)
		return false;
	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
	return InsertNextNOde(p, e);
}
bool InsertNode(LNode* p, ElemType e)
{
	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;
}
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

分析如下：

指定节点的前插操作：

方法：先找到第i-1个节点，再进行前插操作：建立一个中间变量temp用来存放要插入的元素，再使用三数交换的方法实现数的插入。

bool ListInsert(LinkList& L, int i, ELemType e)
{
	if (i < 1)
		return false;
	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
	return InsertPriorNOde(p, e);
}
bool InsertPriorNode(LNode* p, LNode*s)
{
	if (p == NULL||s=NULL)
		return false;
	s->next = p->next;
	p->next = s;
	ElemType temp = p->data;
	p->data = s->data;
	s->data = temp;
	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

分析如下所示：

按位序删除（带头结点）：

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

带头结点：

方法：先找到第i-1个元素，建立新指针指向要删除的元素，再将要删除的元素存放在变量e中，最后通过指针实现数的删除。

bool ListDelete(LinkList& L, int i, ELemType& e)
{
	if (i < 1)
		return false;
	int j = 0;
	p = L;
	//找到第i-1个节点
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
if (p == NULL)
	return false;
if (p->next == NULL)
	return false;
LNode* q = p->next;//指向要删除的元素
e = q->data;//将要删除的元素存放在e中，以便于返回它的值
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
20
21
22

分析如下：

指定节点的删除：

方法：先将要删除元素的后继节点存放在新定义指针中，在通过指针指向实现数据域覆盖，最后连接前驱和后继节点。

bool DeleteNode(LNode* p)
{
	if (p = NULL)
		return false;
	LNode* q = p->next;//指向要删除指定元素的下一个节点
	p->data = p->next->data;//覆盖此时指针p指向的节点，相当于要删除的节点
	p->next = q->next;//实现删除元素前面的节点和删除元素后面节点的链接
	free(q);
	return true;
}
1
2
3
4
5
6
7
8
9
10

注：如果我们寻找的元素恰好是最后一个节点，p->data = p->next->data该语句是不能实现的，这种情况下，我们只能从表头开始依次寻找p的前驱

单链表的局限性：无法逆向检索，有时候会比较麻烦

单链表的查找：

按位查找，返回第i个元素（带头结点）

方法：通过循环的方式，根据位序一一查找。

LNode* GetELem(LinkList L, int i)
{
	if (i < 0)
		return NULL;//返回头结点
	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i)//使指针一直指向第i个元素
	{
		p = p->next;
		j++;
	}
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

按值查找，返回第i个元素（带头结点）：

方法：通过循环遍历的方式，判断元素是否相等。

LNode* LocateElem(LinkLIst L, ElemType e)
{
	LNode* p = L->next;//使其指向第一个节点
	while (p != NULL && p->data != e)//查找链表中和e相同的值
		p = p->next;
	return p;//找到后返回该指针，否则返回NULL
}
1
2
3
4
5
6
7

注：如果想查找的元素类型是struct类型，则不能使用p->data != e进行比较，需要将结构体中的每个成员分别进行比较

求表的长度：

（带头结点）方法：通过循环遍历的方式

int Length(LinkList)
{
	int len = 0;
	LNode* p = L;
	while (p->next！ = NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}
1
2
3
4
5
6
7
8
9
10
11

单链表的建立：

步骤：

1：初始化一个单链表

2：每次取一个数据元素，插入到表尾/表头

带头结点，举例：

初始化一个单链表：
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}*LinkList,LNode;
//初始化一个单链表（带头结点）
bool InitList(LinkLIst& L)
{
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点之后暂时没有节点
	return true;
}
void test()
{
	LinkList L;//声明指向单链表的指针
	初始化一个空表
	InitList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

尾插法建立单链表：

LinkList ListInsert(LinkList &L)
{   
	 int x;								
	L = (LinkList)malloc(sizeof(LNode));//建立头结点
	LNode *s,*r=L;						//设置r为表尾指针
	scanf("%d",&x);						//输入结点的值
	while (x != 9999)
	{  				
		s= (LNode *)malloc(sizeof(LNode));
		s->data = x;  
		r->next = s;   
		r = s;				//指针r永远指向最后一个节点
		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

上述这种方法虽然对，但是它的时间复杂度为O(n*n)，导致时间复杂度高的原因就是每次我们都要从第一个元素开始往后查找直到查找到第i-1个元素，也就相当于找到表尾的元素，由此我们可以设置一个表尾的指针，这样一来就不用每次进行插入操作的时候都从表头依次往后查找了。

代码实现如下：

LinkList ListInsert(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->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

头插法建立单链表：（重要应用：链表的逆置）

其实本质也是进行后插操作，不过后插操作的元素是头结点

注：一定不要忘记将单链表进行初始化，只要是进行单链表的初始化，都先将头指针指向NULL