数据结构与算法：线性表之单链表的基本操作

线性表的顺序储存结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，他的存储位置可以用一个简单、直观的公式来表示。然而，这样也导致在做插入或删除操作时，需要移动大量元素，所以，我们来看看线性表的另一种表示方法——链式存储结构。它不要求逻辑上相邻的元素在物理位置上也相邻，因此他没有顺序储存结构所具有的弱点，但同时也失去了顺序表可随机存取的特点。

---

---

一、基本概念

各结点由两个域组成：

数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置

一些基本定义

结点：数据元素的存储映像。 由数据域和指针域两部分组成

链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构

单链表：结点只有一个指针域的链表，称为单链表或线性链表

双链表：有两个指针域的链表，称为双链表

循环链表：首尾相接的链表称为循环链表

头指针：是指向链表中第一个结点的指针

首元结点：是指链表中存储第一个数据元素a1的结点

头结点：是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息

Q：1.如何表示空表？

有头结点时，当头结点的指针域为空时表示空表

Q：2. 在链表中设置头结点有什么好处

1.便于首元结点的处理 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
⒉便于空表和非空表的统一处理

无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

这种存取元素的方法被称为顺序存取法

优点
数据元素的个数可以自由扩充
插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点
存储密度小
存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

二、单链表的基本操作

定义： 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

1.1 创造结点

struct Node
{
	int data;				//数据域
	struct Node* next;		//指针域(指向节点的指针）
}Node,*LinkList;
1
2
3
4
5

1.2 全局定义链表头尾指针 (方便调用)

struct Node* head= NULL;
struct Node* end = NULL;

1
2
3

1.3.1 创建链表,实现在链表中增加一个结点：头或尾添加

void AddListTill(int a )
{
		//创建一个节点
		struct Node* temp=(struct Node*)malloc(sizeof(struct Node));		//此处注意强制类型转换

		//节点数据进行赋值
		temp->data=a;
		temp->next=NULL;		
		
		//连接分两种情况
		//1.一个节点都没有
		//2.已经有节点了，添加到尾巴上
		if(NULL==head)//没有节点
		{	
			head=temp;
		//	end=temp;
		}
		else
		{
		end->next=temp;
	//	end=temp;			//尾结点应该始终指向最后一个
		}
		end=temp;			//尾结点应该始终指向最后一个
}

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

1.3.2 在指定位置插入节点 ：特定位置添加

void AddListRand(int index,int a)
{	

    if (NULL==head)
	{
		printf("链表没有节点\n");
		return;
	}	
    struct Node* pt =FindNode(index);//添加之前需要找到该结点的位置
	if(NULL==pt)    //没有此节点
	{
		printf("没有指定节点\n");
		return;
	}
    //有此节点
    //创建临时节点，申请内存
	struct Node* temp =(struct Node *)malloc(sizeof(struct Node));
	//节点成员进行赋值
	temp->data=a;
	temp->next=NULL;
	//连接到链表上 
	//1.找到的节点在尾部 
	//2.找到的节点在中间 
	if (pt == end)
	{
	//尾巴的下一个指向新插入的节点
	end->next=temp;
	//新的尾巴
	end=temp;
	}else
	{
	// 先连后面 （先将要插入的节点指针指向原来找到节点的下一个）
	temp->next=pt->next;
	//后连前面
	pt->next=temp;
	}

}

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
36
37
38
39

1.4 查询指定的节点 （遍历：只能一个一个找）

struct Node* FindNode(int a )//a是结点的序号
{
	struct Node *temp =head;//创建一个临时结点为头结点
	while(temp !=NULL)
	{
	if(a == temp->data)//找到该节点
	{
		return temp;
	}
	temp = temp->next;//依次顺序寻找
	}
	//没找到
		return NULL;
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.5.1 链表清空：全部删除

void FreeList()
{
	//一个一个NULL
	struct Node *temp =head;		//定义一个临时变量来指向头结点
	while (temp !=NULL)
	{
	//	printf("%d\n",temp->a);
		struct Node* pt =temp;
		temp = temp->next;		//temp指向下一个的地址 即实现++操作
		free(pt);					//释放当前
	}
	//头尾清空	不然下次的头就接着0x10
	head =NULL;
	end =NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.5.2 结点的删除：尾删除

void DeleteListTail()
{ 
	if (NULL == end)
	{
		printf("链表为空，无需删除\n");
		return;
	}
	//链表不为空 
	//链表有一个节点
	 if (head==end)
	 {
		 free(head);
		 head=NULL;
		 end=NULL; 
	 }
	 else
	 {
		//找到尾巴前一个节点
		 struct Node* temp =head;
		 while (temp->next!=end)
		 {
			 temp = temp->next;
		 }
		 //找到了，删尾巴
		//释放尾巴
		 free(end);
		 //尾巴迁移
		 end=temp;
		 //尾巴指针为NULL
		 end->next=NULL;
	 }

}

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.5.2 结点的删除：头删除

void DeleteListHead()
{	//记住旧头
	struct Node* temp=head;
	//链表检测 
	if (NULL==head)
	{
			printf("链表为空\n");
			return;
	}

	head=head->next;//头的第二个节点变成新的头
	free(temp);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.5.3 删除指定节点

void DeleteListRand(int a)
{

	//链表判断 是不是没有东西
	if(NULL==head)
	{
	printf("链表没东西\n");
	return;
	}
    //链表有东西，找这个节点
	struct Node* temp =FindNode(a);//找到这个结点
	if(NULL==temp)
	{
	printf("查无此点\n");
	return;
	}
	//找到了,且只有一个节点
	if(head==end)
	{
	free(head);
	head=NULL;
	end=NULL;
	}
	else if(head->next==end) //有两个节点
	{
	//看是删除头还是删除尾
	if(end==temp)
		{	DeleteListTail(); }
	else if(temp==head)
		{	DeleteListHead(); }	
	}
	else//多个节点
	{
		//看是删除头还是删除尾
		if(end==temp)
			DeleteListTail();
		else if(temp==head)
			DeleteListHead();	
		else	//删除中间某个节点
		{	//找要删除temp前一个，遍历
			struct Node*pt =head;
			while(pt->next!=temp)
			{
			pt=pt->next;
			}
			//找到了
			//让前一个直接连接后一个 跳过指定的即可
			 pt->next=temp->next;
			 free(temp);
		
		}
	}

}

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

1.6 有序线性链表合并

分析：算法主要包括线性表链式结构的三种操作：搜索、比较、插入

//C=AUB,La,Lb非递减顺序排列
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	struct Node* pa=La->next;
	//pa指向的是第一个元素
	struct Node* pb=Lb->next;
	Lc=La;
	//用La的头结点作为Lc的头结点
	struct Node* pc=Lc;
	//pc指向的是头结点
while(pa&&pb)
{
if(pa->data<pb->data)//取La的元素
{
	pc->next=pa;
	pc=pa;
//pc=pc->pNext
	pa=pa->next;
}
else if(pa->data>pb->data)
//取Lb的元素
{
	pc->next=pb;
	pc=pb;
	pb=pb->next;
}
else
//取La的元素，删除Lb的元素
{
	pc->next=pa;
	pc=pa;
	pa=pa->next;
	q=pb->next;
	free(pb);
	pb=q;
}
}//while
	pc->next=pa?pa:pb;
	free(Lb);
	La=NULL;
	Lb=NULL;
}
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
36
37
38
39
40
41
42

1.7检测主程序

void main ()
{	
	struct Node *pFind ;
	//创建5个节点
	for(i=0;i<6;i++)
	AddListTill(i);
	
//	AddListRand(4,14);		//在指定位置4增加节点14
//	DeleteListTail();		//删除一个尾结点
	DeleteListRand(4);		//删除4节点
	ScanList();				//便利输出链表
	FreeList();				//删除链表
/*	pFind = FindNode(5);	//查找5节点

	if (pFind !=  NULL)
	{
		printf("找到%d\n",pFind->a);	//找到节点并且输出该节点数据
	}
	else
	{
		printf("No Find!\n");
	}

*/

}

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