服务器之家

服务器之家 > 正文

解析C++的线性表链式存储设计与相关的API实现

时间:2021-03-27 15:06     来源/作者:YoferZhang

基本概念
链式存储定义:
为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。

解析C++的线性表链式存储设计与相关的API实现解析C++的线性表链式存储设计与相关的API实现

表头结点:
链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息。
数据结点:
链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息。
尾结点:
链表中的最后一个数据结点,其下一元素指针为空,表示无后继。

链表技术领域推演

解析C++的线性表链式存储设计与相关的API实现

链表链式存储_api实现分析:
在C语言中可以用结构体来定义链表中的指针域,链表中的表头结点也可以用结构体实现;

解析C++的线性表链式存储设计与相关的API实现

解析C++的线性表链式存储设计与相关的API实现

带头结点、位置从0的单链表;
返回链表中第3个位置处,元素的值。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkListNode* LinkList_Get(LinkList* list, int pos)
{
 if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
 return NULL;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header);
 
 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 }
 
 return cur->next;
}

返回第三个位置的。
移动pos次以后,当前指针指向哪里?
答案:指向位置2,所以需要返回 ret = current->next。
 
备注:循环遍历时
遍历第1次,指向位置0;
遍历第2次,指向位置1;
遍历第3次,指向位置2;
遍历第n次,指向位置n-1。

删除元素:

解析C++的线性表链式存储设计与相关的API实现

代码实例:

 linklist.h 

?
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
#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_
 
typedef void LinkList;
 
typedef struct _tag_LinkListNode
{
 struct _tag_LinkListNode* next;
}LinkListNode;
 
LinkList* LinkList_Create();
 
void LinkList_Destroy(LinkList* list);
 
void LinkList_Clear(LinkList* list);
 
int LinkList_Length(LinkList* list);
 
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
 
LinkListNode* LinkList_Get(LinkList* list, int pos);
 
LinkListNode* LinkList_Delete(LinkList* list, int pos);
 
#endif


linklist.cpp  
 

?
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstdio>
#include "linklist.h"
 
using namespace std;
 
typedef void LinkList;
 
typedef struct _tag_LinkList
{
 LinkListNode header;
 int length;
}TLinkList;
 
LinkList* LinkList_Create()
{
 TLinkList *tmp = NULL;
 
 tmp = (TLinkList *)malloc(sizeof(TLinkList));
 if (tmp == NULL) {
 printf("function LinkList_Create() err.\n");
 return NULL;
 }
 memset(tmp, 0, sizeof(TLinkList)); // 初始化为空链表
 
 return tmp;
}
 
void LinkList_Destroy(LinkList* list)
{
 if (list == NULL) {
 return;
 }
 free(list);
 
 return;
}
 
void LinkList_Clear(LinkList* list)
{
 if (list == NULL) {
 return;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 tList->header.next = NULL;
 tList->length = 0;
 
 return;
}
 
int LinkList_Length(LinkList* list)
{
 if (list == NULL) {
 return -1;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 
 return tList->length;
}
 
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
 if (list == NULL || node == NULL || pos < 0) {
 return -1;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header);
 
 // 对pos的容错处理,如果pos过大,改为最后面
 if (pos > LinkList_Length(list)) {
 pos = LinkList_Length(list);
 }
 
 // 移动到需要插入的位置
 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 }
 
 // 插入
 node->next = cur->next;
 cur->next = node;
 
 ++tList->length;
 
 return 0;
}
 
LinkListNode* LinkList_Get(LinkList* list, int pos)
{
 if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
 return NULL;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header);
 
 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 }
 
 return cur->next;
}
 
LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
 if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
 return NULL;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header);
 
 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 }
 
 LinkListNode *ret = NULL;
 ret = cur->next;
 
 // 删除结点
 cur->next = ret->next;
 
 --tList->length;
 
 return ret;
}


main.cpp  
 

?
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
#include <iostream>
#include <cstdio>
#include "linklist.h"
 
using namespace std;
 
typedef struct _Student
{
 LinkListNode node;
 char name[32];
 int age;
}Student;
 
int main()
{
 Student s1, s2, s3, s4, s5, s6;
 s1.age = 21;
 s2.age = 22;
 s3.age = 23;
 s4.age = 24;
 s5.age = 25;
 s6.age = 26;
 
 // 创建链表
 Student *list = (Student *)LinkList_Create();
 
 // 插入结点
 LinkList_Insert(list, (LinkListNode *)&s1, 0);
 LinkList_Insert(list, (LinkListNode *)&s2, 0);
 LinkList_Insert(list, (LinkListNode *)&s3, 0);
 LinkList_Insert(list, (LinkListNode *)&s4, 0);
 LinkList_Insert(list, (LinkListNode *)&s5, 0);
 LinkList_Insert(list, (LinkListNode *)&s6, 3);
 
 // 遍历链表
 for (int i = 0; i < LinkList_Length(list); ++i) {
 Student *tmp = (Student *)LinkList_Get(list, i);
 if (tmp == NULL) {
 return 0;
 }
 printf("age: %d\n", tmp->age);
 }
 
 // 删除链表结点
 while (LinkList_Length(list)) {
 Student *tmp = (Student *)LinkList_Delete(list, 0);
 if (tmp == NULL) {
 return 0;
 }
 printf("age: %d\n", tmp->age);
 }
 
 LinkList_Destroy(list);
 
 return 0;
}

优点:

  • 无需一次性定制链表的容量;
  • 插入和删除操作无需移动数据元素。

缺点:

  • 数据元素必须保存后继元素的位置信息;
  • 获取指定数据的元素操作需要顺序访问之前的元素。

工程详情:Github

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部