【数据结构】链表之无头单向非循环链表_循环链表变非循环

链表的特点是：物理地址不连续
数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表

链表的结构：链表由数据域和指针域两部分组成，数据域是存储数据元素的部分，指针域一般指向下一个节点的指针。

链表的优点
在进行插入和删除操作时比较方便

链表的缺点

• 存储密度小，空间利用率低
• 要访问某特定元素，只能从链表开头进行遍历

头结点的作用
为了保持和后面结点的设计算法一致，保持算法的高效性

链表共有8种结构，分别为

1. 单链表
2. 双向链表
3. 带头单链表
4. 不带头单链表
5. 非循环单链表
6. 循环单链表
7. 无头单向非循环链表
8. 带头双向循环链表

然而在实际中最常用的就是最后两种：无头单向非循环链表、带头双向循环链表
具体结构如下：

1、无头单向非循环链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

2、带头双向循环链表

带头双向循环链表：结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

无头单向非循环链表的模拟实现

无头单向非循环链表的接口

// 1、无头单向非循环链表增删查改实现
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType _data;
	struct SListNode* _next;
}SListNode;
typedef struct SList
{
	SListNode* _head;
}SList;

void SListInit(SList* plist);//初始化链表
void SListPushFront(SList* plist, SLTDataType x);
void SListPopFront(SList* plist);
SListNode* SListFind(SList* plist, SLTDataType x);
void SListInsertAfter(SListNode* pos, SLTDataType x);
void SListEraseAfter(SListNode* pos);
void SListDestory(SList* plist);
void SListPrint(SList* plist);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

具体实现

#include"slist.h"

//初始化链表
void SListInit(SList* plist)
{
	plist->_head = NULL;
}

//头插法
void SListPushFront(SList* plist, SLTDataType x)
{
	assert(plist);

	SListNode * cur = (SListNode *)malloc(sizeof(SListNode));

	//将要插入结点的值赋给cur,此时cur指向原来链表的头结点
	//新的链表的头结点即为cur
	cur->_data = x;
	cur->_next = plist->_head;
	plist->_head = cur;
}

//头删法
void SListPopFront(SList* plist)
{
	assert(plist);

	//判断要删除的结点是否为头结点，若是则需要一个临时结点保存头结点
	SListNode * tmp;
	if (plist->_head)
	{
		tmp = plist->_head;
		plist->_head = tmp->_next;//将原链表头结点的下一个结点设置为头结点
		free(tmp);
	}
}

//查找一个链表中的元素pos
SListNode* SListFind(SList* plist, SLTDataType x)
{
	assert(plist);

	SListNode * cur;
	for (cur = plist->_head; cur; cur = cur->_next)//单链表的遍历
	{
		if (cur->_data == x)
		{
			return cur;
		}
	}
	return NULL;
}

// 在pos的后面进行插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	SListNode * cur = (SListNode *)malloc(sizeof(SListNode));

	cur->_data = x;//创建要插入元素的值
	//待插入元素的指向下一个元素就是pos指向的下一个元素
	//将待插入的元素与下一个元素建立关系
	cur->_next = pos->_next;
	//断开pos与原来下一个元素的关系，建立pos与待插入元素的关系
	pos->_next = cur;
}

//删除pos后的一个元素
void SListEraseAfter(SListNode* pos)
{
	SListNode * tmp = pos->_next;
	//建立一个临时结点来保存pos->next，由于链表的物理地址不是连续的，不保存将会无法找到pos指向的下一个元素
	pos->_next = tmp;
	//此时将pos与pos后的第二个元素（即tmp指向的元素）建立关系
	pos->_next = tmp->_next;
	//释放掉tmp，即删除pos后的元素
	free(tmp);
}

void SListDestory(SList* plist)
{
	assert(plist);

	SListNode *tmp;
	while (plist->_head)
	{
		tmp = plist->_head;
		plist->_head = plist->_head->_next;
		free(tmp);
	}
}

void SListPrint(SList* plist)
{
	assert(plist);

	SListNode *cur;
	for (cur = plist->_head; cur; cur = cur->_next)
	{
		cout << cur->_data << "->" << " ";
	}
	cout << "NULL" << endl;
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

测试

#include"slist.h"

void ListTest()
{
	SList test;

	SListInit(&test);
	SListPushFront(&test, 1);
	SListPushFront(&test, 3);
	SListPushFront(&test, 5);
	SListPushFront(&test, 7);
	SListPushFront(&test, 9);
	SListPrint(&test);

	SListPopFront(&test);
	SListPrint(&test);

	SListInsertAfter(SListFind(&test, 3), 8);
	SListPrint(&test);

	SListEraseAfter(SListFind(&test, 8));
	SListPrint(&test);

	SListDestory(&test);
}

int main()
{
	ListTest();
	system("pause");
	return 0;
}

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

运行结果

注意事项

单链表遍历的方法

for(cur = head; cur; cur = cur->next)    //中间的cur是判空
{
          cur;
}
1
2
3
4