【数据结构】单链表&&静态链表详解和代码实例

发布时间：2020-12-15 05:49:21 所属栏目：安全来源：网络整理

导读：喜欢的话可以扫码关注我们的公众号哦，更多精彩尽在微信公众号【程序猿声】 01 单链表(Singly Linked List ) 1.1 什么是单链表？单链表是一种链式存储的结构。它动态的为节点分配存储单元。当有节点插入时，系统动态的为结点分配空间。在结点删除时，应该及

喜欢的话可以扫码关注我们的公众号哦，更多精彩尽在微信公众号【程序猿声】

01 单链表(Singly Linked List )

1.1 什么是单链表？

单链表是一种链式存储的结构。它动态的为节点分配存储单元。当有节点插入时，系统动态的为结点分配空间。在结点删除时，应该及时释放相应的存储单元，以防止内存泄露。由于是链式存储，所以操作单链表时，必须知道头结点或者头指针的位置。并且，在查找第i个节点时，必须找到第i-1个节点。

1.2 单链表的存储结构代码描述

对于链式存储，通过上一节的讲解相信大家已经了解得够清楚了。如下图所示：

下面我们来看看单链表存储是如何用代码来实现的。

1//单链表的存储结构C语言代码
2typedef?struct?SListNode
3{
4????datatype?data;????//数据域
5????struct?SListNode?*?pnext;//指针域
6}SLinkList;

由上面的结构我们可以看出，一个节点由存放数据的数据域和存放地址的指针域组成。假如p指向了第i个节点，那么p->data就是该节点存放的数据，而p->pnext自然就是指向下一个节点的指针。如下图所示：

那么接下来我们看看单链表的各个操作具体实现吧。(只讲几个关键步骤)
备注：下面的代码基于这样的一个单链表：

有一个头指针phead
有一个头结点node
头指针指向头结点，头结点位置记为0

1.3 单链表的读取

在拿到头指针以后，单链表的读取也并非一件难事。一开始设置一个计数变量，不断遍历链表，让计数器自增。找到合适的位置将数据读取出来。具体代码实现如下：

 1#define?status?bool
 2#define?ERROR?false
 3#define?OK?true
 4/*
 5?*?函数功能：获取位置index节点的数据
 6?*?参数说明：phead链表头结点，e用来获取的变量，index索引
 7*/
 8
 9status?GetSListIndexNode(Node?*?phead,DType?*e,?int?index)
10{
11????int?icount?=?0;?//计数器
12????//注：0号位为头结点，头结点不存放任何数据
13????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength()/*此处为链表长度*/)
14????{
15????????return?ERROR;?//异常?处理
16????}
17????while?(phead->pnext?!=?nullptr)
18????{
19????????icount++;
20????????phead?=?phead->pnext;
21????????if?(icount?==?index)
22????????{
23????????????*e?=?phead->data;
24????????????return?OK;
25????????}
26????}
27????return?ERROR;
28}

1.4 单链表的插入

1.4.1 指定位置后插

其实链表的插入和删除都是很简单的操作，初学者只要抓住指针指向的节点，并加以区分开来，就很easy了。如下图：

图中，假如此时p指向了我们要插入的节点的位置。那么，怎样把我们的S节点给插入到p指向的节点之后？在这里我们先不要惊动p以及p后面的节点：

我们先让S节点指向p之后的节点(步骤①)
之后我们切断p和p后面那个节点的关系(步骤②)
最后让p节点的指针域指向s节点(步骤③)，搞定

算法描述：

声明一个指针p指向链表头结点，向后遍历p=p->next，找到正确的位置。
新建一个结点s。
s->next = p->next ①
p->next = s ②③
具体代码如下：

 1#define?status?bool
 2#define?ERROR?false
 3#define?OK?true
 4/*
 5?*?函数功能：指定位置后插
 6?*?参数说明：phead链表头结点，IData插入的数据，index索引
 7*/
 8status?InsertSListNodeFront(Node?*?phead,?DType?IData,?int?index)
 9{
10????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
11????{
12????????return?ERROR;?//异常?处理
13????}
14????int?iCount?=?0;?//计数器
15????Node<DType>?*?q?=?nullptr;?//备用
16????while?(phead->pnext?!=?nullptr)
17????{
18????????iCount++;
19????????q?=?phead;
20????????phead?=?phead->pnext;
21????????if?(?iCount?==?index?)
22????????{
23????????????Node<DType>?*?p?=?new?Node<DType>;
24????????????p->data?=?IData;
25????????????p->pnext?=?phead;
26????????????q->pnext?=?p;???//前插
27????????????return?OK;
28????????}
29????}
30????return?ERROR;
31}

1.4.2 指定位置前插

咳咳，聪明的小伙伴，用脑子想想。指定位置前插 == 指定位置的前一个位置进行后插。懂了吧？直接看具体代码：

 1/*
 2?*?函数功能：指定位置后插
 3?*?参数说明：phead链表头结点，IData插入的数据，index索引
 4*/
 5status?InsertSListNodeBack(Node?*?phead,?int?index)
 6{
 7????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
 8????{
 9????????return?ERROR;?//异常?处理
10????}
11????int?iCount?=?0;?//计数器
12????Node<DType>?*?q?=?nullptr;?//备用
13????while?(phead->pnext?!=?nullptr)
14????{
15????????iCount++;
16????????q?=?phead;
17????????phead?=?phead->pnext;
18????????if?(iCount?==?index)
19????????{
20????????????Node<DType>?*?p?=?new?Node<DType>;
21????????????q?=?phead;
22????????????phead?=?phead->pnext;?//后插就是后一个节点的前插咯
23????????????p->data?=?IData;
24????????????p->pnext?=?phead;
25????????????q->pnext?=?p;???
26????????????return?OK;
27????????}
28????}
29????return?ERROR;
30}

1.5 单链表的删除

单链表的删除其实也是很简单。只要比如要删除p指向的节点，只需要让p之前的节点的指针域直接指向p之后的节点，再把p给free就OK了。如下图：

算法描述:

声明一个指针p指向链表头结点，向后遍历p=p->next，找到要删除的节点位置。
q = p->next
p->next = q->next ①②
free(q) ③④

具体代码如下:

 1/*
 2?*?函数功能：指定位置后插
 3?*?参数说明：phead链表头结点，IData获取删除的数据，index索引
 4*/
 5//删除指定位置节点(e获取删除元素)
 6template?<typename?DType>
 7status?DeleteSListIndexNode(Node?*?phead,?DType?*e,?int?index)
 8{
 9????int?i?=?0;?//计数器
10????Node<DType>?*?q?=?nullptr;
11????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
12????{
13????????return?ERROR;?//异常?处理
14????}
15????while?(phead->pnext?!=?nullptr)
16????{
17????????i++;
18????????q?=?phead;?//保存备用
19????????phead?=?phead->pnext;
20????????if?(i?==?index)
21????????{
22????????????*e?=?phead->data;
23????????????q->pnext?=?phead->pnext;?//删除出局
24????????????return?OK;
25????????}
26????}
27????return?ERROR;
28}

代码应该不难，相信大家都能很容易看懂。

1.6.1 单链表的完整代码

好了，前面介绍了几个重要的操作，接下来请大家看看完整的代码吧。小编为了使用方便，就用C++的class和template将整个链表封装到了一个类里面，通过模板实现泛型编程。

 1/*
 2?*?文件名:SingleLinkList.h
 3?*?说明?：类的各种声明
 4?*/
 5#pragma?once?//VC编译器防止头文件被重复包含的一条预编译指令
 6
 7#define?status?bool
 8#define?OK?true
 9#define?ERROR?false
 10#define?YES?true
 11#define?NO?false
 12
 13template?<typename?DType>
 14class?Node
 15{
 16public:
 17????DType?data;
 18????Node?*?pnext;
 19};
 20
 21template?<typename?DType>
 22class?CSingleLinkList
 23{
 24private:
 25????Node<DType>?*phead;?//链表头指针
 26public:
 27????CSingleLinkList();//构造，类被创建时调用
 28????~CSingleLinkList();//析构，类被销毁时调用
 29public:
 30????//初始化链表
 31????status?InitSList();
 32????//获取链表长度
 33????int?GetSListLength();
 34????//增加一个节点?前插法
 35????status?AddSListNodeFront(DType?idata);
 36????//增加一个节点?后插法
 37????status?AddSListNodeBack(?DType?idata);
 38????//判断链表是否为空
 39????status?IsSListEmpty();
 40????//获取指定位置节点值(注意，本程序规定0号为头节点，e获取删除元素)
 41????status?GetSListIndexNode(DType?*e,?int?index);
 42????//删除指定位置节点(e获取删除元素)
 43????status?DeleteSListIndexNode(DType?*e,?int?index);
 44????//查找链表中指定值(pindex获取位置0==>not?found)
 45????status?SearchSListNode(DType?SData,?int?*pindex);
 46????//指定位置前插
 47????status?InsertSListNodeFront(DType?IData,?int?index);
 48????//指定位置后插
 49????status?InsertSListNodeBack(DType?IData,?int?index);
 50????//清空链表(保留根节点)
 51????status?ClearSList();
 52????//销毁链表(all?delete)
 53????status?DestorySList();
 54????//尾部删除一个元素
 55????status?DeleteSListNodeBack();
 56????//打印链表???此函数根据实际情况而定
 57????void?PrintSList();
 58};
 59
 60/*
 61?*?文件名:SingleLinkList.cpp
 62?*?说明?：类的各种方法的实现
 63?*/
 64
 65#include?"SingleLinkList.h"
 66#include?<stdio.h>
 67
 68template?<typename?DType>
 69CSingleLinkList<DType>::CSingleLinkList()
 70{
 71????cout?<<?"链表创建"?<<?endl;
 72????InitSList();
 73}
 74template?<typename?DType>
 75CSingleLinkList<DType>::~CSingleLinkList()
 76{
 77????cout?<<?"链表销毁"?<<?endl;
 78????DestorySList();
 79}
 80//初始化链表
 81template?<typename?DType>
 82status?CSingleLinkList<DType>::InitSList()
 83{
 84????Node<DType>?*?ph?=?new?Node<DType>;
 85????if?(ph?!=?NULL)
 86????{
 87????????ph->pnext?=?nullptr;
 88????????this->phead?=?ph;?//头结点
 89????????return?OK;
 90????}
 91????return?ERROR;
 92}
 93//获取链表长度(head_node?is?not?included)
 94template?<typename?DType>
 95int?CSingleLinkList<DType>::GetSListLength()
 96{
 97????int?length?=?0;
 98????Node<DType>?*?phead?=?this->phead;
 99????while?(phead->pnext?!=?nullptr)
100????{
101????????length++;
102????????phead?=?phead->pnext;
103????}
104????return?length;
105}
106//增加一个节点?前插法
107template?<typename?DType>
108status?CSingleLinkList<DType>::AddSListNodeFront(?DType?idata)
109{
110????Node<DType>?*?pnode?=?new?Node<DType>;
111????if?(pnode?!=?NULL)
112????{
113????????pnode->data?=?idata;
114????????pnode->pnext?=?this->phead->pnext;
115????????this->phead->pnext?=?pnode;?//挂载
116
117????????//printf("pnode?=?%p??pnode->pnext?=?%p?this->phead->pnext?=?%p?this->phead?=?%pn",?pnode,?pnode->pnext,?this->phead->pnext,?this->phead);
118????????return?OK;
119????}
120????return?ERROR;
121}
122
123
124//增加一个节点?尾插法
125template?<typename?DType>
126status?CSingleLinkList<DType>::AddSListNodeBack(DType?idata)
127{
128????Node<DType>?*?pnode?=?new?Node<DType>;
129????Node<DType>?*?phead?=?this->phead;
130????if?(pnode?!=?NULL)
131????{
132????????while?(phead->pnext?!=?nullptr)
133????????{
134????????????phead?=?phead->pnext;
135????????}
136????????pnode->data?=?idata;
137????????pnode->pnext?=?nullptr;
138????????phead->pnext?=?pnode;?//挂载
139????????return?OK;
140????}
141????return?ERROR;
142}
143//判断链表是否为空
144template?<typename?DType>
145status?CSingleLinkList<DType>::IsSListEmpty()
146{
147????if?(this->phead->pnext?==?nullptr)
148????{
149????????return?YES;
150????}
151????return?NO;
152}
153//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)
154template?<typename?DType>
155status?CSingleLinkList<DType>::GetSListIndexNode(DType?*e,?int?index)
156{
157????Node<DType>?*?phead?=?this->phead;
158????int?i?=?0;?//计数器
159????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
160????{
161????????return?ERROR;?//异常?处理
162????}
163????while?(phead->pnext?!=?nullptr)
164????{
165????????i++;
166????????phead?=?phead->pnext;
167????????if?(i?==?index)
168????????{
169????????????*e?=?phead->data;
170????????????return?OK;
171????????}
172????}
173????return?ERROR;
174}
175//删除指定位置节点(e获取删除元素)
176template?<typename?DType>
177status?CSingleLinkList<DType>::DeleteSListIndexNode(?DType?*e,?int?index)
178{
179????Node<DType>?*?phead?=?this->phead;
180????int?i?=?0;?//计数器
181????Node<DType>?*?q?=?nullptr;
182????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
183????{
184????????return?ERROR;?//异常?处理
185????}
186????while?(phead->pnext?!=?nullptr)
187????{
188????????i++;
189????????q?=?phead;?//保存备用
190????????phead?=?phead->pnext;
191????????if?(i?==?index)
192????????{
193????????????*e?=?phead->data;
194????????????q->pnext?=?phead->pnext;?//删除出局
195????????????return?OK;
196????????}
197????}
198????return?ERROR;
199}
200//查找链表中指定值(pindex获取位置???0==>not?found)
201template?<typename?DType>
202status?CSingleLinkList<DType>::SearchSListNode(?DType?SData,?int?*pindex)
203{
204????Node<DType>?*?phead?=?this->phead;
205????int?iCount?=?0;//计数器
206????while?(phead->pnext?!=?nullptr)
207????{
208????????iCount++;
209????????phead?=?phead->pnext;
210????????if?(phead->data?==?SData)
211????????{
212????????????*pindex?=?iCount;
213????????????return?YES;
214????????}
215????}
216????*pindex?=?0;
217????return?NO;
218}
219//指定位置前插
220template?<typename?DType>
221status?CSingleLinkList<DType>::InsertSListNodeFront(DType?IData,?int?index)
222{
223????Node<DType>?*?phead?=?this->phead;
224????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
225????{
226????????return?ERROR;?//异常?处理
227????}
228????int?iCount?=?0;?//计数器
229????Node<DType>?*?q?=?nullptr;?//备用
230????while?(phead->pnext?!=?nullptr)
231????{
232????????iCount++;
233????????q?=?phead;
234????????phead?=?phead->pnext;
235????????if?(?iCount?==?index?)
236????????{
237????????????Node<DType>?*?p?=?new?Node<DType>;
238????????????p->data?=?IData;
239????????????p->pnext?=?phead;
240????????????q->pnext?=?p;???//前插
241????????????return?OK;
242????????}
243????}
244????return?ERROR;
245}
246//指定位置后插
247template?<typename?DType>
248status?CSingleLinkList<DType>::InsertSListNodeBack(?DType?IData,?int?index)
249{
250????Node<DType>?*?phead?=?this->phead;
251????if?(phead->pnext?==?nullptr?||?index?<?1?||?index?>?GetSListLength())
252????{
253????????return?ERROR;?//异常?处理
254????}
255????int?iCount?=?0;?//计数器
256????Node<DType>?*?q?=?nullptr;?//备用
257????while?(phead->pnext?!=?nullptr)
258????{
259????????iCount++;
260????????q?=?phead;
261????????phead?=?phead->pnext;
262????????if?(iCount?==?index)
263????????{
264????????????Node<DType>?*?p?=?new?Node<DType>;
265????????????q?=?phead;
266????????????phead?=?phead->pnext;?//后插就是后一个节点的前插咯
267????????????p->data?=?IData;
268????????????p->pnext?=?phead;
269????????????q->pnext?=?p;???
270????????????return?OK;
271????????}
272????}
273????return?ERROR;
274}
275//清空链表(保留根节点)
276template?<typename?DType>
277status?CSingleLinkList<DType>::ClearSList()
278{
279????Node<DType>?*?phead?=?this->phead;
280????Node<DType>?*?q?=?nullptr;?//防止那啥，野指针
281????phead?=?phead->pnext;//保留头节点
282????while?(phead?!=?nullptr)
283????{
284????????q?=?phead;
285????????phead?=?phead->pnext;
286????????delete?q;?//释放
287????}
288????this->phead->pnext?=?nullptr;
289????return?OK;
290}
291//销毁链表(all?delete)
292template?<typename?DType>
293status?CSingleLinkList<DType>::DestorySList()
294{
295????ClearSList();
296????delete?this->phead;//释放头结点?
297????return?OK;
298}
299
300template?<typename?DType>
301status?CSingleLinkList<DType>::DeleteSListNodeBack()
302{
303????Node<DType>?*?phead?=?this->phead;
304????Node<DType>?*?q?=?nullptr;?//备用
305????if?(phead->pnext?==?nullptr)
306????{
307????????return?ERROR;?//链表都空了还删鸡毛
308????}
309????while?(phead->pnext?!=?nullptr)
310????{
311????????q?=?phead;
312????????phead?=?phead->pnext;
313????}
314????q->pnext?=?nullptr;
315????delete?phead;
316
317????return?OK;
318
319}
320template?<typename?DType>
321void?CSingleLinkList<DType>::PrintSList()
322{
323????Node<DType>?*?phead?=?this->phead;
324????if?(phead->pnext?==?nullptr?||?phead?==?nullptr)
325????{
326????????cout?<<?"链表为空，打印鸡毛"?<<?endl;
327????????return;
328????}
329????int?i?=?1;
330????cout?<<?"===============print?list================"?<<?endl;
331????while?(phead->pnext?!=?nullptr)
332????{
333????????phead?=?phead->pnext;
334????????cout?<<"node["?<<?i++?<<?"]?=?"?<<?phead->data<<endl;
335????}
336}
337
338/*
339?*?文件名:SingleLinkListTest.cpp
340?*?说明?：测试代码
341?*/
342
343?#include?<iostream>
344#include?"SingleLinkList.h"
345#include?"SingleLinkList.cpp"
346
347using?namespace?std;
348
349int?main()
350{
351????CSingleLinkList<int>?*?pMySList?=?new?CSingleLinkList<int>;
352????cout?<<?pMySList->IsSListEmpty()?<<?endl;
353????pMySList->AddSListNodeFront(111);
354????pMySList->AddSListNodeFront(222);
355????pMySList->AddSListNodeFront(333);
356
357????cout?<<?"链表长度"?<<?pMySList->GetSListLength()?<<?endl;
358
359????pMySList->PrintSList();
360
361????pMySList->AddSListNodeBack(444);
362????pMySList->AddSListNodeBack(555);
363????pMySList->AddSListNodeBack(666);
364
365????pMySList->PrintSList();
366
367????cout?<<?pMySList->IsSListEmpty()?<<?endl;
368????cout?<<?"链表长度"?<<?pMySList->GetSListLength()?<<?endl;
369
370????int?GetElem,?GetIndex;
371????pMySList->GetSListIndexNode(&GetElem,?2);
372????cout?<<?"Got?Elem?=?"?<<?GetElem?<<?endl;
373
374????pMySList->GetSListIndexNode(&GetElem,?6);
375????cout?<<?"Got?Elem?=?"?<<?GetElem?<<?endl;
376
377????pMySList->GetSListIndexNode(&GetElem,?4);
378????cout?<<?"Got?Elem?=?"?<<?GetElem?<<?endl;
379
380????pMySList->DeleteSListIndexNode(&GetElem,?1);
381????cout?<<?"del?Elem?=?"?<<?GetElem?<<?endl;
382????pMySList->DeleteSListIndexNode(&GetElem,?3);
383????cout?<<?"del?Elem?=?"?<<?GetElem?<<?endl;
384
385
386????pMySList->PrintSList();
387
388????pMySList->SearchSListNode(555,?&GetIndex);
389????cout?<<?"Search?Index?=?"?<<?GetIndex?<<?endl;
390????pMySList->SearchSListNode(111,?&GetIndex);
391????cout?<<?"Search?Index?=?"?<<?GetIndex?<<?endl;
392????pMySList->SearchSListNode(666,?&GetIndex);
393????cout?<<?"Search?Index?=?"?<<?GetIndex?<<?endl;
394
395????pMySList->InsertSListNodeFront(333,?1);
396????pMySList->InsertSListNodeFront(444,?4);
397
398????pMySList->PrintSList();
399
400????pMySList->InsertSListNodeBack(777,?3);
401????pMySList->InsertSListNodeBack(888,?5);
402
403????pMySList->PrintSList();
404
405????pMySList->DeleteSListNodeBack();
406????pMySList->PrintSList();
407????pMySList->DeleteSListNodeBack();
408????pMySList->PrintSList();
409????pMySList->DeleteSListNodeBack();
410????pMySList->PrintSList();
411
412????return?0;
413}
414
415

代码如果有不正确的地方，欢迎大家来指正哈。

02 静态链表(circular linked list)

2.1 什么是静态链表？

我们把线性表的元素存放在数组中，这些元素由两个域组成：

数据域data
指针域cur

数据域是存放数据的，而指针域，这里和链表不同是，它存的不再是指向下一个节点的内存地址。而是下一个节点在数组中的下标。我们就把这种用数组描述的链表称为静态表，该方法也称之为游标实现法。如下图所示：

由上图我们需要注意以下几点：

我们对数组的第一个元素和最后一个元素做特殊处理，不存放数据。
把未使用的数组元素称为备用链表。
数组的第一个元素(下标为0)的cur域存放备用链表第一个节点的下标。
数组的最后一个元素的cur域存放第一个有数据的节点的下标，相当于链表中头结点的存在。链表为空时，其值为0。

如下图：

引出的问题：数组的长度定义的问题，无法预支。所以，为了防止溢出，我们一般将静态表开得大一点。

2.2 静态链表存储的代码描述

基于上面的讲解，我们来看看代码是怎么描述这种存储结构的。

1//---------线性表的静态单链表存储结构--------
2#define?MAXSIZE?1000?/*假设链表最大长度为1000*/
3typedef?struct
4{
5????datatype?data;
6????int?cur;???//为0时表示无指向
7}SLinkList[MAXSIZE];

接下来我们讲解几个重要的操作实现。

2.3 静态链表的插入操作

前面我们讲动态链表的时候说过，增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。但是现在由于我们操作的是静态表，它可是用数组存的，可没有这种操作了。因此我们首先来自己实现一个静态表的malloc和free。

那么怎么辨别数组中哪些空间没有被使用呢？一个好的解决办法是，将所有未使用或者被删除的空间串成一个备用链表。插入节点时便可以从备用链表获取第一个未使用的空间的下标。因此我们在初始化的时候会做这样的工作：

 1void?SListInit(SLinkList?space)
 2{
 3????int?i;
 4????for(i?=?0;?i?<?MAXSIZE;?i++)
 5????????space[i].cur?=?i+1;?//将所有结点链入备用链表
 6????//备用链表头指针链像第二个结点
 7????space[0].cur?=?space[1].cur;?
 8????//第一个结点作为链表的头结点??
 9????space[1].cur?=?0;??????????????
10}

分配内存

 1/分配备用链表的一个结点,返回下标
 2//若为0，则说明备用链表用完
 3int?Malloc_SL(SLinkList?space)
 4{
 5????int?i?=?space[0].cur;
 6????//判断备用链表是否非空
 7????if(space[0].cur)????
 8????????//备用链表头指针指向第二个空结点
 9????????space[0].cur?=?space[i].cur;?
10
11????return?i;????//返回第一个空结点
12}

上面的代码应该是没有难度的。写完了这个函数，我们来看看静态表中具体如何插入：

 1//在链表的第i个位置插入元素e
 2void?SlistInsert(SLinkList?space,?int?i,?ElemType?e)
 3{
 4????//超出范围
 5????if(i?<?1?||?i?>?SListLength(space)+1)?
 6????????return;
 7????int?k?=?1,?j;
 8????//使k指示要插入的结点的前一个结点
 9????for(j?=?0;?j?<i-1;?j++)?
10????????k?=?space[k].cur;
11
12????int?v?=?Malloc_SL(space);
13????if(v)?????//如果有空间
14????{
15????????space[v].data?=?e;
16????????space[v].cur?=?space[k].cur;
17????????space[k].cur?=?v;??//链入链表
18????}
19}

注意几点：

首先我们让k指向了要插入节点(记为X)的前一个位置(记为Y节点)，前插法。
然后我们在静态表内申请空间，存放新的节点(记为N)。
把数据放进新申请的节点里面。
新节点N的cur域指向X节点，然后让Y节点指向N节点。

该过程不难理解。就不上图了……

2.4 静态链表的删除操作

删除同样需要自己实现free函数，我们来看看代码：

回收内存

1//将下标为k的空闲结点回收到备用链表
2void?Free_SL(SLinkList?space,?int?k)
3{
4????//将备用链表链到k之后
5????space[k].cur?=?space[0].cur;??
6????//将k链到备用链表头之后
7????space[0].cur?=?k;???????????????
8}

删除以后记得把空间重新挂载到备用链表上以便下一次使用。下面我们实现删除的代码：

 1//删除第i个位置的元素
 2void?SListDelete(SLinkList?space,?int?i)
 3{???//超出范围退出
 4????if(i?<?1?||?i?>?SListLength(space))??
 5????????return?;
 6????int?k?=?1,?j;
 7?????//使k指示要删除的结点的前一个结点
 8????for(j?=?0;?j?<i-1;?j++)??
 9????????k?=?space[k].cur;
10
11????int?temp?=?space[k].cur;
12????space[k].cur?=?space[temp].cur;
13????Free_SL(space,?temp);
14}

其实代码也很好理解了。假如X、Y、Z……等等排列，我们要删除Y。无非就是告诉X，你不要指向Y了，你直接指向Z，然后我们再把Y给free了。就直接变成了X、Z……简单吧。

2.5 静态链表的完整代码

熬了一个下午,终于写完了.哈哈,用了C++的类模板封装了一个静态链表,简单的增删查改功能都有了.具体可以看代码:

StaticLinkList.h

 1#pragma?once
 2#include?<iomanip>
 3
 4#define?MAXSIZE?100
 5
 6#define?status?bool
 7#define?YES?true
 8#define?NO?false
 9#define?OK?true
10#define?ERROR?false
11
12template?<typename?DATATYPE>
13class?Component
14{
15public:
16????DATATYPE?data;?//数据域
17????int?cur;???????//cur域，指向下一个元素的下标
18};
19
20
21template?<typename?DATATYPE>
22class?CStaticLinkList
23{
24public:
25????Component<DATATYPE>??StaticLinkList[MAXSIZE];??//静态表
26//自定义malloc和free
27public:
28????int?MallocNodeSSL();
29????status?FreeNodeSSL(int?index);
30public:
31????status?InitList();?//初始化静态表
32????status?BackAddList(?DATATYPE?AddData);?//尾增加
33????status?InsertNodeList(DATATYPE?InsertData,?int?index);//指定位置插入
34????status?DeleteNodeList(DATATYPE?*DelData,?int?index);?//指定位置删除
35????int?SearchList(DATATYPE?sData);???????//搜索数据为sData的节点,返回其在数组中的下标,0表示失败
36????status?GetIndexList(DATATYPE?*gData,?int?index);//获取指定索引的节点数据
37????int?GetLengthList();?//获取静态表的长度
38????status?ClearList();?//清空静态表
39????status?IsEmptyList();?//判断静态表是否为空
40????status?IsFullList();?//判断静态表是否满了
41????void?PrintList();?//打印静态表,此函数根据实际情况编写
42
43public:
44????CStaticLinkList();
45????~CStaticLinkList();
46};

StaticLinkList.cpp

 1#include?"StaticLinkList.h"
 2
 3template?<typename?DATATYPE>
 4CStaticLinkList<DATATYPE>::CStaticLinkList()
 5{
 6????cout?<<?"===========静态表创建==========="?<<?endl;
 7????InitList();
 8}
 9
 10template?<typename?DATATYPE>
 11CStaticLinkList<DATATYPE>::~CStaticLinkList()
 12{
 13????cout?<<?"===========静态表销毁==========="?<<?endl;
 14}
 15
 16template?<typename?DATATYPE>
 17int?CStaticLinkList<DATATYPE>::MallocNodeSSL()
 18{
 19????int?index?=?StaticLinkList[0].cur;?//把备用链表第一个节点拿出来用
 20????if?(StaticLinkList[0].cur)?//判断是否还有位置
 21????{
 22????????StaticLinkList[0].cur?=?StaticLinkList[index].cur;?//让备用链表第二个节点上来顶替第一个的位置
 23????}
 24
 25????return?index;?//返回0表示分配失败
 26}
 27
 28template?<typename?DATATYPE>
 29status?CStaticLinkList<DATATYPE>::FreeNodeSSL(int?index)
 30{
 31????//将删除节点挂接到备用链表上
 32????this->StaticLinkList[index].cur?=?this->StaticLinkList[0].cur;
 33????this->StaticLinkList[0].cur?=?index;
 34
 35????return?OK;
 36}
 37
 38template?<typename?DATATYPE>
 39status?CStaticLinkList<DATATYPE>::InitList()
 40{
 41????int?i;
 42????for?(i?=?0;?i?<?MAXSIZE?-?1;?i++)
 43????{
 44????????StaticLinkList[i].cur?=?i?+?1;//全部塞入备用链表
 45????}
 46????StaticLinkList[MAXSIZE?-?1].cur?=?0;/*因为目前静态表为空,最后一个节点的cur域为0*/
 47????return?OK;
 48}
 49
 50template?<typename?DATATYPE>
 51status?CStaticLinkList<DATATYPE>::BackAddList(DATATYPE?AddData)?//尾增加
 52{
 53????if?(IsFullList())
 54????{
 55????????return?ERROR;
 56????}
 57????int?index?=?MAXSIZE?-?1;
 58????int?last?=?index;
 59
 60????while?(index?!=?0)
 61????{
 62????????last?=?index;
 63????????index?=?StaticLinkList[index].cur;
 64????}
 65
 66????int?k?=?MallocNodeSSL();?//获取空闲位置下标
 67????if?(k)
 68????{
 69????????StaticLinkList[k].data?=?AddData;?//存入数据
 70????????StaticLinkList[k].cur?=?0;???//末尾指向0
 71????????StaticLinkList[last].cur?=?k;
 72????????return?OK;
 73????}
 74
 75????return?ERROR;
 76
 77}
 78//在List中第i个节点之前插入新的节点
 79template?<typename?DATATYPE>
 80status?CStaticLinkList<DATATYPE>::InsertNodeList(DATATYPE?InsertData,?int?index)//指定位置插入
 81{
 82????int?i,?GetFree,?pos;
 83????pos?=?MAXSIZE?-?1;//最后节点下标
 84????if?(index?<?1?||?index?>?GetLengthList()?||?IsFullList())
 85????{
 86????????return?ERROR;?//位置异常处理
 87????}
 88
 89????GetFree?=?MallocNodeSSL();
 90????if?(GetFree)
 91????{
 92????????StaticLinkList[GetFree].data?=?InsertData;
 93????????for?(i?=?0;?i?<?index?-?1;?i++)
 94????????{
 95????????????pos?=?StaticLinkList[pos].cur;?//定位
 96????????}
 97????????StaticLinkList[GetFree].cur?=?StaticLinkList[pos].cur;
 98????????StaticLinkList[pos].cur?=?GetFree;?//插入
 99
100????????int?q?=?StaticLinkList[MAXSIZE?-?1].cur;
101????????if?(q?==?0)?//静态表为空
102????????{
103????????????StaticLinkList[MAXSIZE?-?1].cur?=?1;
104????????}
105????????return?OK;
106????}
107????return?ERROR;
108}
109
110//判断是否为空
111template?<typename?DATATYPE>
112status?CStaticLinkList<DATATYPE>::IsEmptyList()
113{
114????if?(StaticLinkList[MAXSIZE-1].cur?==?0)
115????{
116????????return?YES;?
117????}
118
119????return?NO;
120}
121//判断静态表是否满了
122template?<typename?DATATYPE>
123status?CStaticLinkList<DATATYPE>::IsFullList()
124{
125????if?(GetLengthList()?==?MAXSIZE?-?2)?//因为首位不存数据,因此pass掉
126????{
127????????return?YES;
128????}
129????return?NO;
130}
131template?<typename?DATATYPE>
132int?CStaticLinkList<DATATYPE>::GetLengthList()?//获取静态表的长度
133{
134????int?iCount?=?0;
135????int?k?=?MAXSIZE?-?1;
136????while?(StaticLinkList[k].cur?!=?0)
137????{
138????????iCount++;
139????????k?=?StaticLinkList[k].cur;
140????}
141
142????return?iCount;
143}
144template?<typename?DATATYPE>
145status?CStaticLinkList<DATATYPE>::DeleteNodeList(DATATYPE?*DelData,?int?index)//指定位置删除
146{
147????int?i,?pos,?k;
148????pos?=?MAXSIZE?-?1;//最后节点下标
149????if?(index?<?1?||?index?>?GetLengthList()?||?IsEmptyList())
150????{
151????????return?ERROR;?//位置异常处理
152????}
153????for?(i?=?0;?i?<?index?-?1;?i++)
154????{
155????????pos?=?StaticLinkList[pos].cur;?//定位到被删除节点的前一个节点
156????}
157????k?=?StaticLinkList[pos].cur;?
158????*DelData?=?StaticLinkList[k].data;?//获取数据
159????StaticLinkList[pos].cur?=?StaticLinkList[k].cur;//让前一个节点直接指向后一个节点.把夹在中间的踢掉
160????FreeNodeSSL(k);?//释放空间
161
162????return?OK;
163}
164//搜索数据为sData的节点,返回其在静态表中的第i个位置,0表示没找到
165template?<typename?DATATYPE>
166int?CStaticLinkList<DATATYPE>::SearchList(DATATYPE?sData)
167{
168????int?pos?=?StaticLinkList[MAXSIZE-1].cur;
169????int?iCount?=?1;
170????while?(pos?!=?0)
171????{
172????????if?(StaticLinkList[pos].data?==?sData)?//找到数据
173????????{
174????????????return?iCount;
175????????}
176????????pos?=?StaticLinkList[pos].cur;?//循环遍历
177????????iCount++;
178????}
179
180????return?0;
181}
182template?<typename?DATATYPE>
183status?CStaticLinkList<DATATYPE>::GetIndexList(DATATYPE?*gData,?int?index)//获取第index个节点数据
184{
185????int?i,?pos;
186????pos?=?MAXSIZE?-?1;//最后节点下标
187????if?(index?<?1?||?index?>?GetLengthList()?||?IsEmptyList())
188????{
189????????return?ERROR;?//位置异常处理
190????}
191????for?(i?=?0;?i?<?index;?i++)
192????{
193????????pos?=?StaticLinkList[pos].cur;?//定位到第index个节点
194????}
195????*gData?=?StaticLinkList[pos].data;
196
197????return?OK;
198}
199template?<typename?DATATYPE>
200status??CStaticLinkList<DATATYPE>::ClearList()?//清空静态表
201{
202????InitList();//再初始化一次就是清空了
203????return??OK;
204}
205template?<typename?DATATYPE>
206void??CStaticLinkList<DATATYPE>::PrintList()
207{
208????int?pos?=?StaticLinkList[MAXSIZE?-?1].cur;
209????if?(pos?==?0)
210????{
211????????cout?<<?"===========静态链表为空,打印鸡毛!!!==========="?<<?endl;
212????????return;
213????}
214????cout?<<?setiosflags(ios::left);
215????cout?<<?setw(10)?<<?"索引"?<<?setw(10)?<<?"下标"?<<?setw(10)?<<?"data"?<<?setw(10)?<<?"cur"?<<?endl;
216????int?iCount?=?1;
217????while?(pos?!=?0)
218????{
219????????cout?<<?setw(10)?<<?iCount?<<?setw(10)?<<?pos?<<?setw(10)?<<?StaticLinkList[pos].data?<<?setw(10)?<<?StaticLinkList[pos].cur?<<?endl;
220????????pos?=?StaticLinkList[pos].cur;?//循环遍历
221????????iCount++;
222????}
223}

StaticLinkListTest.cpp测试代码

 1#include?<iostream>
 2#include?<iomanip>
 3#include?"StaticLinkList.h"
 4#include?"StaticLinkList.cpp"
 5using?namespace?std;
 6
 7int?main()
 8{
 9????char?get;
10????CStaticLinkList<char>?*p?=?new?CStaticLinkList<char>;
11????p->PrintList();
12
13????p->BackAddList(‘a‘);?//pass
14????p->BackAddList(‘b‘);
15????p->BackAddList(‘c‘);
16????p->BackAddList(‘d‘);
17????p->BackAddList(‘e‘);
18
19????//p->ClearList();??????//pass
20
21????p->PrintList();
22
23????p->DeleteNodeList(&get,?2);??//pass
24????cout?<<?"get?=?"?<<?get?<<?endl;
25
26????p->DeleteNodeList(&get,?2);
27????cout?<<?"get?=?"?<<?get?<<?endl;
28
29????p->PrintList();
30????p->BackAddList(‘f‘);
31
32????p->PrintList();
33????cout?<<?"length?=?"?<<?p->GetLengthList()?<<?endl;//pass
34
35????p->GetIndexList(&get,?3);??//pass
36????cout?<<?"get?=?"?<<?get?<<?endl;?
37
38????p->InsertNodeList(‘h‘,?2);
39????p->InsertNodeList(‘i‘,?3);
40
41????p->PrintList();
42????cout?<<?"length?=?"?<<?p->GetLengthList()?<<?endl;//pass
43
44????cout?<<?"search_pos?=?"?<<?p->SearchList(‘q‘)?<<?endl;
45????cout?<<?"search_pos?=?"?<<?p->SearchList(‘h‘)?<<?endl;
46????cout?<<?"search_pos?=?"?<<?p->SearchList(‘i‘)?<<?endl;
47
48????delete?p;
49
50????return?0;
51}

运行结果

运行结果

代码未经过严谨测试,如果有错,欢迎大家指正和交流啊.

这次就先到这里吧。更多精彩内容，请期待下回分解。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

【数据结构】单链表&amp;&amp;静态链表详解和代码实例