【数据结构|链表】单链表基本操作_【头歌】单链表的基本操作

一、链表

    链表为线性表的另一种表达方法——链式存储结构（链表的存储方式）其特点为不需要逻辑上相邻的元素在物理位置上也相邻，即在不连续的地址中存储一系列数据 ，所以也失去了顺序表的随机存储优点。
    线性表的链式存储方式的特点是一组任意的存储单元存储数据元素（可连续可不连续），为了表示每个数据元素和后一个数据元素的逻辑关系，对于当前数据元素来说，除了存储本身信息外还需要存储与后继元素的关系，这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域:其中存储数据元素信息的域称为数据域；存储后继元素存储位置的域称为指针域。

二、链表分类

• 单链表
• 双向链表
• 循环链表
• 静态链表

三、单链表基本操作

  3.1 单链表存储结构Init

typedef struct Node{
	Elemtype data;
	struct LNode *next;
}Node,*Linklist;
1
2
3
4

    但是，上面Node,Linklist两个怎么理解呢

Node ： struct node
Linklist : struct node *
//应用时如此替换即可
1
2
3

    假设L是Linklist型的变量，则L为单链表的头指针，它指向表中第一个结点。若L为“空”(L=NULL)，则所表示的线性表为“空”表，其长度n为“零”。有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。此时，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”。

    引入头结点有什么好处呢？

1. 便于首元结点的处理，首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理；
2. 便于空表和非空表的统一处理，无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

  3.2 遍历链表visitlist函数

    实现方案：

1. 创建Linklist类型p作为头结点后继节点
2. 输出当前指针域的值后向后“移动”
   

void visitlist(Linklist L)
{
	Linklist p = (Linklist)malloc(sizeof(Node));
	p = L->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

  3.3 求表长length

    相同思路，额外取一个计数即可

void Length(Linklist L)
{
	int count = 0;
	Linklist p = (Linklist)malloc(sizeof(Node));
	p = L->next;
	while (p)
	{
		p = p->next;
		count++;
	}
	cout << "表长为：" << count << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

  3.4 查找listfind

    实现方案：

1. 创建Linklist类型p作为头结点后继节点
2. p不为空作为循环结束标志进行计数和比对

int listfind(Linklist L, Elemtype e)
{
	Linklist p = (Linklist)malloc(sizeof(Node));
	p = L->next;
	int count = 0;  //计数 
	while (p)
	{
		count++;
		if (p->data == e)
			break;
		p = p->next;
		//cout << count << " " << p->data << endl;
	}
	cout << count << endl;
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、单链表插入操作

    要实现在第i个元素前插入e，由于链式存储，只需要“拨针”，思路如下：

• 首先找到ai-1的存储位置p
• 生成一个新结点q且数据域为e
• 插入新结点

注意：目前已知P，P->next，即此时ai-1的后继节点是ai

• 此时若先执行s = p->next，则无法锁定ai且链表断裂
• 执行步骤：1.s->next = p->next; 2.s = p->next;
• 上述顺序不能改变！！！

  4.1 头插法实现

Linklist headcreatelist()
{
	Linklist head = (Linklist)malloc(sizeof(Node));
	head->next = NULL;
	Elemtype i;  //键盘输入输入i，i = -1时结束 
	while (cin >> i && i != -1)
	{
		Linklist node = (Linklist)malloc(sizeof(Node));
		//node->next = NULL;  个人习惯后继设为空 
		node->data = i;
		node->next = head->next;
		head->next = node;
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  4.2 尾插法实现

Linklist rearcreatelist()
{
	Linklist head = (Linklist)malloc(sizeof(Node));
	Linklist rear = (Linklist)malloc(sizeof(Node));
	head->next = NULL;
	rear = head;
	Elemtype i;  //键盘输入输入i，i = -1时结束 
	while (cin >> i && i != -1)
	{
		Linklist node = (Linklist)malloc(sizeof(Node));
		node->next = NULL;  //后继设为空,后面不会出现后继找不到 
		node->data = i;
		rear->next = node;
		rear = node;
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17