【数据结构】循环链表&&双向链表详解和代码实例

喜好的言语可扫码关注我们的群众号哦,更多美尽在微信公众号【程序猿声】

manbetx手机网页版 1

爱的语句可以扫码关注我们的众生号哦,更多漂亮尽在微信公众号【程序猿声】

manbetx手机网页版 2

01 循环链表

01 单链表(Singly Linked List )

1.1 什么是循环链表?

面前介绍了单链表,相信大家还记系的定义。其实循环链表跟单链表也从未差异很多,只是以少数细节上的处理方式会小有些不跟。

在此之前,大家可先想一个题材:单链表中,要找到中有节点才待自头节点开始遍历链表即可,但是多少时候我们的想法是,能免可知从随机manbetx手机网页版节点开始遍历,也克找到我们需要的非常节点吧?

骨子里什么,这个实现为生粗略自然,把所有链表串成一个围问题即迎刃而解了。所以,关于循环链表,我们来矣之类的概念:

以单链表中的尾节点之指针域由NULL改为本着头结点,使一切单链表形成一个环绕,这种头尾相接的单链表就得称作**单循环链表,简称循环链表(circular
linked list)。

1.1 什么是单独链表?

单链表是同样种植链式存储的布局。它动态的为节点分配存储单元。当有节点插入时,系统动态的也罢结点分配空间。在结点删除时,应该这放出相应的存储单元,以防止内存泄露。由于是链式存储,所以操作单链表时,必须明白头结点或者头指针的岗位。并且,在寻第i只节点时,必须找到第i-1独节点。

1.2 循环链表图示

此处我们谈论的链表还是设置一个头结点(当然,链表并无是必然得一个头结点)。

  • 当链表为空的时,我们得以生出如下表示:

manbetx手机网页版 3

  • 于非空链表则好这么表示:

manbetx手机网页版 4

  • 不得不提的某些

    对于循环链表这种规划,我们于遍历的时刻的了条件虽不再是p为空的早晚了了。而是p等于头结点的时光遍历才形成。这同沾希望大家记住。

  • 再次多说简单句

    咱理解,有矣头结点,我们得轻而易举访问第一单节点。但是当要访问最后一个节点时,却使拿全方位链表扫一全体,效率不可谓不坠……那么,有无发更好的点子吗?

    自然是一些,只不过这里我们需要以循环链表再举行一个微改进,具体表现为:

    manbetx手机网页版 5

    从上图可以见到,我们抛开了以往之头指针,取而代之的凡运一个尾指针指于了最终一个节点。而且,因为链表是循环的,当我们用拜访第一独节点时,也very
    easy!无非需要尾指针往后活动一个就到前方了。

1.2 单链表的蕴藏结构代码描述

对链式存储,通过上同一节的讲课相信大家就了解得够清楚了。如下图所示:

manbetx手机网页版 6

脚我们来探望单链表存储是什么用代码来落实之。

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

鉴于方的组织我们得看来,一个节点由存放数据的数据域和存放地点之指针域组成。假如p指向了第i独节点,那么p->data就是欠节点存放的数量,而p->pnext自然就是负于下一个节点的指针。如下图所示:

manbetx手机网页版 7

这就是说连下去我们看单链表的一一操作实际贯彻吧。(只提几个关键步骤)
备考:下面的代码基于这样的一个单链表:

  • 产生一个头指针phead
  • 发出一个头结点node
  • 头指针指于头结点,头结点位置记为0

1.3 循环链表代码

有关循环链表的插入删除等操作,其实是跟单链表一样的。唯一不同的即使是遍历的时候的收条件差而已。因此我们在这里就是非开了多篇幅的介绍,直接贴完整代码吧。

循环链表就是末尾指向头形成一个巡回的链表.实现思路为杀简短,大体把单链表代码做只细微改变就OK了.这次要封装在一个看似里吧.

CircleLinkList.h 类头文件,各种声明定义

 1#pragma once //VC防止头文件重复包含的一条预编译指令
 2
 3#define status bool
 4#define OK true
 5#define ERROR false
 6#define YES true
 7#define NO false
 8
 9template <typename DType>
10class Node
11{
12public:
13    DType data;
14    Node * pnext;
15};
16template <typename DType>
17class CCircleLinkList
18{
19private:
20    Node<DType> *phead;
21public:
22    CCircleLinkList();
23    ~CCircleLinkList();
24public:
25    //初始化链表
26    status InitCList();
27    //获取链表长度
28    int GetCListLength();
29    //增加一个节点 前插法
30    status AddCListNodeFront(DType idata);
31    //增加一个节点 后插法
32    status AddCListNodeBack(DType idata);
33    //判断链表是否为空
34    status IsCListEmpty();
35    //获取指定位置节点值(注意,本程序规定0号为头节点,e获取删除元素)
36    status GetCListIndexNode(DType *e, int index);
37    //删除指定位置节点(e获取删除元素)
38    status DeleteCListIndexNode(DType *e, int index);
39    //查找链表中指定值(pindex获取位置0==>not found)
40    status SearchCListNode(DType SData, int *pindex);
41    //指定位置前插
42    status InsertCListNodeFront(DType IData, int index);
43    //指定位置后插
44    status InsertCListNodeBack(DType IData, int index);
45    //清空链表(保留根节点)
46    status ClearCList();
47    //销毁链表(all delete)
48    status DestoryCList();
49    //尾部删除一个元素
50    status DeleteCListNodeBack();
51    //打印链表   此函数根据实际情况而定
52    void PrintCList();
53};

CircleLinkList.cpp 类的现实性贯彻代码

  1#include "CircleLinkList.h"
  2
  3#include <stdio.h>
  4
  5template <typename DType>
  6CCircleLinkList<DType>::CCircleLinkList()
  7{
  8    cout << "链表创建" << endl;
  9    InitCList();
 10}
 11
 12template <typename DType>
 13CCircleLinkList<DType>::~CCircleLinkList()
 14{
 15    cout << "链表销毁" << endl;
 16    DestoryCList();
 17}
 18
 19
 20//初始化链表
 21template <typename DType>
 22status CCircleLinkList<DType>::InitCList()
 23{
 24    Node<DType> * ph = new Node<DType>;
 25    if (ph != NULL)
 26    {
 27        ph->pnext = ph;    //尾指向头
 28        this->phead = ph; //头结点
 29        return OK;
 30    }
 31
 32    return ERROR;
 33
 34}
 35
 36//获取链表长度(head_node is not included)
 37template <typename DType>
 38int CCircleLinkList<DType>::GetCListLength()
 39{
 40    int length = 0;
 41    Node<DType> * ph = this->phead;
 42    while (ph->pnext != this->phead)
 43    {
 44        length++;
 45        ph = ph->pnext;
 46    }
 47    return length;
 48}
 49
 50//增加一个节点 前插法
 51template <typename DType>
 52status CCircleLinkList<DType>::AddCListNodeFront(DType idata)
 53{
 54    Node<DType> * pnode = new Node<DType>;
 55    if (pnode != NULL)
 56    {
 57        pnode->data = idata;
 58        pnode->pnext = this->phead->pnext;
 59        this->phead->pnext = pnode; //挂载
 60
 61        return OK;
 62    }
 63
 64    return ERROR;
 65
 66}
 67
 68
 69//增加一个节点 尾插法
 70template <typename DType>
 71status CCircleLinkList<DType>::AddCListNodeBack(DType idata)
 72{
 73    Node<DType> * pnode = new Node<DType>;
 74    Node<DType> * ph = this->phead;
 75    if (pnode != NULL)
 76    {
 77        while (ph->pnext != this->phead)
 78        {
 79            ph = ph->pnext;
 80        }
 81        pnode->data = idata;
 82        pnode->pnext = this->phead;
 83        ph->pnext = pnode; //挂载
 84        return OK;
 85    }
 86
 87    return ERROR;
 88}
 89//判断链表是否为空
 90template <typename DType>
 91status CCircleLinkList<DType>::IsCListEmpty()
 92{
 93    if (this->phead->pnext == this->phead)
 94    {
 95        return YES;
 96    }
 97
 98    return NO;
 99}
100//获取指定位置节点值(注意,本程序规定0号为头节点,e获取节点的值)
101template <typename DType>
102status CCircleLinkList<DType>::GetCListIndexNode(DType *e, int index)
103{
104    Node<DType> * ph = this->phead;
105    int i = 0; //计数器
106    if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
107    {
108        return ERROR; //异常 处理
109    }
110    while (ph->pnext != this->phead)
111    {
112        i++;
113        ph = ph->pnext;
114        if (i == index)
115        {
116            *e = ph->data;
117            return OK;
118        }
119    }
120
121    return ERROR;
122}
123//删除指定位置节点(e获取删除元素)
124template <typename DType>
125status CCircleLinkList<DType>::DeleteCListIndexNode(DType *e, int index)
126{
127    Node<DType> * ph = this->phead;
128    int i = 0; //计数器
129    Node<DType> * q = nullptr;
130    if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
131    {
132        return ERROR; //异常 处理
133    }
134    while (ph->pnext != this->phead)
135    {
136        i++;
137        q = ph; //保存备用
138        ph = ph->pnext;
139        if (i == index)
140        {
141            *e = ph->data;
142            q->pnext = ph->pnext; //删除出局
143            delete ph;
144            return OK;
145        }
146    }
147    return ERROR;
148}
149//查找链表中指定值(pindex获取位置   0==>not found)
150template <typename DType>
151status CCircleLinkList<DType>::SearchCListNode(DType SData, int *pindex)
152{
153    Node<DType> * ph = this->phead;
154    int iCount = 0;//计数器
155    while (ph->pnext != this->phead)
156    {
157        iCount++;
158        ph = ph->pnext;
159        if (ph->data == SData)
160        {
161            *pindex = iCount;
162            return YES;
163        }
164    }
165    *pindex = 0;
166    return NO;
167
168}
169//指定位置前插
170template <typename DType>
171status CCircleLinkList<DType>::InsertCListNodeFront(DType IData, int index)
172{
173    Node<DType> * ph = this->phead;
174    if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
175    {
176        return ERROR; //异常 处理
177    }
178    int iCount = 0; //计数器
179    Node<DType> * q = nullptr; //备用
180    while (ph->pnext != this->phead)
181    {
182        iCount++;
183        q = ph;
184        ph = ph->pnext;
185        if (iCount == index)
186        {
187            Node<DType> * p = new Node<DType>;
188            p->data = IData;
189            p->pnext = ph;
190            q->pnext = p;   //前插
191            return OK;
192        }
193    }
194    return ERROR;
195}
196//指定位置后插
197template <typename DType>
198status CCircleLinkList<DType>::InsertCListNodeBack(DType IData, int index)
199{
200    Node<DType> * ph = this->phead;
201    if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
202    {
203        return ERROR; //异常 处理
204    }
205    int iCount = 0; //计数器
206    Node<DType> * q = nullptr; //备用
207    while (ph->pnext != this->phead)
208    {
209        iCount++;
210        q = ph;
211        ph = ph->pnext;
212        if (iCount == index)
213        {
214            Node<DType> * p = new Node<DType>;
215            q = ph;
216            ph = ph->pnext; //后插就是后一个节点的前插咯
217            p->data = IData;
218            p->pnext = ph;
219            q->pnext = p;
220            return OK;
221        }
222    }
223    return ERROR;
224}
225//清空链表(保留根节点)
226template <typename DType>
227status CCircleLinkList<DType>::ClearCList()
228{
229    Node<DType> * ph = this->phead;
230    Node<DType> * q = nullptr; //防止那啥,野指针
231    ph = ph->pnext;//保留头节点
232    while (ph != this->phead)
233    {
234        q = ph;
235        ph = ph->pnext;
236        delete q; //释放
237    }
238    this->phead->pnext = this->phead;
239    return OK;
240}
241//销毁链表(all delete)
242template <typename DType>
243status CCircleLinkList<DType>::DestoryCList()
244{
245    ClearCList();
246    delete this->phead;//释放头结点 
247    return OK;
248}
249
250template <typename DType>
251status CCircleLinkList<DType>::DeleteCListNodeBack()
252{
253    Node<DType> * ph = this->phead;
254    Node<DType> * q = nullptr; //备用
255    if (ph->pnext == this->phead)
256    {
257        return ERROR; //链表都空了还删鸡毛
258    }
259    while (ph->pnext != this->phead)
260    {
261        q = ph;
262        ph = ph->pnext;
263    }
264    q->pnext = this->phead;
265    delete ph;
266
267    return OK;
268
269}
270template <typename DType>
271void CCircleLinkList<DType>::PrintCList()
272{
273    Node<DType> * ph = this->phead;
274    if (ph->pnext == this->phead)
275    {
276        cout << "链表为空,打印鸡毛" << endl;
277        return;
278    }
279    int i = 1;
280    cout << "===============print list================" << endl;
281    while (ph->pnext != this->phead)
282    {
283        ph = ph->pnext;
284        cout << "node[" << i++ << "] = " << ph->data << endl;
285    }
286}

CircleLinkListTest.cpp 测试代码

 1#include <iostream>
 2#include "CircleLinkList.h"
 3#include "CircleLinkList.cpp"
 4
 5using namespace std;
 6
 7int main()
 8{
 9    CCircleLinkList<int> * pMySList = new CCircleLinkList<int>;
10    cout << pMySList->IsCListEmpty() << endl;
11    pMySList->AddCListNodeFront(111);
12    pMySList->AddCListNodeFront(222);
13    pMySList->AddCListNodeFront(333);
14
15    cout << "链表长度" << pMySList->GetCListLength() << endl;
16
17    pMySList->PrintCList();
18
19    pMySList->AddCListNodeBack(444);
20    pMySList->AddCListNodeBack(555);
21    pMySList->AddCListNodeBack(666);
22
23    pMySList->PrintCList();
24
25    cout << pMySList->IsCListEmpty() << endl;
26    cout << "链表长度" << pMySList->GetCListLength() << endl;
27
28    int GetElem, GetIndex;
29    pMySList->GetCListIndexNode(&GetElem, 2);
30    cout << "Got Elem = " << GetElem << endl;
31
32    pMySList->GetCListIndexNode(&GetElem, 6);
33    cout << "Got Elem = " << GetElem << endl;
34
35    pMySList->GetCListIndexNode(&GetElem, 4);
36    cout << "Got Elem = " << GetElem << endl;
37
38    pMySList->DeleteCListIndexNode(&GetElem, 1);
39    cout << "del Elem = " << GetElem << endl;
40    pMySList->DeleteCListIndexNode(&GetElem, 3);
41    cout << "del Elem = " << GetElem << endl;
42
43
44    pMySList->PrintCList();
45
46    pMySList->SearchCListNode(555, &GetIndex);
47    cout << "Search Index = " << GetIndex << endl;
48    pMySList->SearchCListNode(111, &GetIndex);
49    cout << "Search Index = " << GetIndex << endl;
50    pMySList->SearchCListNode(666, &GetIndex);
51    cout << "Search Index = " << GetIndex << endl;
52
53    pMySList->InsertCListNodeFront(333, 1);
54    pMySList->InsertCListNodeFront(444, 4);
55
56    pMySList->PrintCList();
57
58    pMySList->InsertCListNodeBack(777, 3);
59    pMySList->InsertCListNodeBack(888, 5);
60
61    pMySList->PrintCList();
62
63    pMySList->DeleteCListNodeBack();
64    pMySList->PrintCList();
65    pMySList->DeleteCListNodeBack();
66    pMySList->PrintCList();
67    pMySList->DeleteCListNodeBack();
68    pMySList->PrintCList();
69    return 0;
70}

代码未经严谨测试,如果起误,欢迎指正.

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}

02 双奔链表(doubly linked list)

1.4 单链表的插入

2.1 双朝向链表又是单什么表?

  • 引言

    咱俩且清楚,在单链表中由于发生next指针的存,需要摸索下一个节点的时日复杂度也特是O(1)而已。但是比在并无总是那令人满意,当我们怀念更吃等同凭着回头草的时刻,查找上一致节点的流年复杂度却成了O(n),这正是吃人头格外。

    manbetx手机网页版 8

  • 双向链表

    可是我们老人的科学家都想到了之问题,并提出了老大好的解决办法。在每个节点受到重复多加了一个依针域,所以被一个乘针域指向前一个节点,一个仗针域指向后一个节点。否正是如此,就来了我们今天所说之双向链表了。

    双向链表(doubly linked
    list)是以单链表的每个节点受到,再安装一个对准该前任节点的指针域。

1.4.1 指定位置后插

实际上链表的插入和去都是好简单的操作,初家只要抓住指针指向的节点,并加以区分开来,就老easy了。如下图:

manbetx手机网页版 9

祈求被,假如此时p指向了咱若插入的节点的位置。那么,怎样将咱的S节点给插入到p指向的节点之后?在此我们事先不要惊动p以及p后面的节点:

  1. 咱先行叫S节点指向p之后的节点(步骤①)
  2. 后咱们切断p和p后面那个节点的干(步骤②)
  3. 末段让p节点的指针域指向s节点(步骤③),搞定

算法描述:

  1. 声明一个指针p指向链表头结点,向后全历p=p->next,找到科学的位置。
  2. 新建一个结点s。
  3. s->next
    = p->next ①
  4. 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}

2.2 双为链表图示

国际惯例,这里我们依旧引入了头结点这个玩意儿。不仅如此,为了多又多的激发,我们尚引入了一个尾节点。

  • 双向链表为空时

    manbetx手机网页版 10

    双向链表在初始化时,要被首尾两单节点分配内存空间。成分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是事后用来判断空表的尺度。同时,当链表为空时,要用首节点的next指向尾节点,尾节点的prior指于首节点。

  • 双向链表不为空时

    manbetx手机网页版 11

    各级一个节点(首各节点除外)的星星点点个因针域都各自凭借为那个前任和后。

1.4.2 指定位置前插

咳咳,聪明之小伙伴,用心血想。指定位置前插 ==
指定位置的前面一个职务进行后插。懂了吧?直接扣现实代码:

 1/*
 2 * 函数功能:指定位置后插
 3 * 参数说明:phead链表头结点,IData插入的数据,index索引
 4*/
 5status InsertSListNodeBack(Node * phead, DType IData, 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}

2.3 双为链表存储结构代码描述

双向链表一般可用如下的囤积结构:

1/*线性表的双向链表存储结构*/
2typedef struct DulNode
3{
4    DataType data;
5    struct DulNode *prior; //指向前驱的指针域
6    struct DulNode *next; //指向后继的指针域
7}DulNode, *DuLinkList;

1.5 单链表的去除

单链表的去其实也是特别简单。只要依照使去除p指向的节点,只需要让p之前的节点的指针域直接指向p之后的节点,再将p给free就OK了。如下图:

manbetx手机网页版 12

算法描述:

  1. 宣称一个指针p指向链表头结点,向后整个历p=p->next,找到要刨除的节点位置。
  2. q
    = p->next
  3. p->next
    = q->next ①②
  4. 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}

代码应该好,相信大家还能够充分易看懂。

2.4 双奔链表的插

实则大家别看大抵了一个借助针域就恐怖了。这戏意儿还是暨单链表一样简单得千篇一律批,需要留意的即是清理各个指针之间的涉嫌。该指向哪的便给它依靠于乌去就是OK了。具体的表现吗:

manbetx手机网页版 13

代码描述为蛮简短:

1s->prior=p;
2s->next=p->next;
3p->next->prior=s;
4p->next=s;    

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 = %p\n", 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

代码如果发生免得法的地方,欢迎大家来指正哈。

2.5 双通向链表的勾

删去操作与单链表的操作基本差不多的。都是坐常规操作了。只是多矣一个先驱指针,注意一下即可。如下图:

manbetx手机网页版 14

代码描述:

1    p->prior->next=p->next;
2    p->next->prior=p->prior;
3    free(p);

02 静态链表(circular linked list)

2.6 双朝着链表的共同体代码

任何操作基本和单链表差不多矣。在这边就不再做过多废话,大家一直看完整代码即可。

  1#include<stdio.h>
  2#include<stdlib.h>
  3#include<time.h>
  4#define OK 1
  5#define ERROR 0
  6#define TRUE 1
  7#define FALSE 0
  8typedef int status;
  9typedef int elemtype;
 10typedef struct node{
 11    elemtype data;
 12    struct node * next;
 13    struct node * prior;
 14}node;
 15typedef struct node* dlinklist;
 16
 17status visit(elemtype c){
 18    printf("%d ",c);
 19}
 20
 21/*双向链表初始化*/
 22status initdlinklist(dlinklist * head,dlinklist * tail){
 23    (*head)=(dlinklist)malloc(sizeof(node));
 24    (*tail)=(dlinklist)malloc(sizeof(node));
 25    if(!(*head)||!(*tail))
 26        return ERROR;
 27    /*这一步很关键*/ 
 28    (*head)->prior=NULL;
 29    (*tail)->next=NULL;
 30    /*链表为空时让头指向尾*/
 31    (*head)->next=(*tail);
 32    (*tail)->prior=(*head);
 33}
 34
 35/*判定是否为空*/
 36status emptylinklist(dlinklist head,dlinklist tail){
 37    if(head->next==tail)
 38       return TRUE;
 39    else
 40       return FALSE;
 41} 
 42
 43/*尾插法创建链表*/ 
 44status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
 45    dlinklist pmove=tail,pinsert;
 46    pinsert=(dlinklist)malloc(sizeof(node));
 47    if(!pinsert)
 48         return ERROR;
 49    pinsert->data=data;
 50    pinsert->next=NULL;
 51    pinsert->prior=NULL;
 52    tail->prior->next=pinsert;
 53    pinsert->prior=tail->prior;
 54    pinsert->next=tail;
 55    tail->prior=pinsert;
 56} 
 57
 58/*头插法创建链表*/ 
 59status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
 60    dlinklist pmove=head,qmove=tail,pinsert;
 61    pinsert=(dlinklist)malloc(sizeof(node));
 62    if(!pinsert)
 63        return ERROR;
 64    else{
 65        pinsert->data=data;
 66        pinsert->prior=pmove;
 67        pinsert->next=pmove->next;
 68        pmove->next->prior=pinsert;
 69        pmove->next=pinsert;
 70    }
 71}
 72
 73/*打印链表*/ 
 74status printplist(dlinklist head,dlinklist tail){
 75    /*dlinklist pmove=head->next;
 76    while(pmove!=tail){
 77        printf("%d ",pmove->data);
 78        pmove=pmove->next;
 79    }
 80    printf("\n");
 81    return OK;*/
 82    dlinklist pmove=head->next;
 83    while(pmove!=tail){
 84        visit(pmove->data);
 85        pmove=pmove->next;
 86    }
 87    printf("\n");
 88}
 89
 90/*返回第一个值为data的元素的位序*/
 91status locateelem(dlinklist head,dlinklist tail,elemtype data){
 92    dlinklist pmove=head->next;
 93    int pos=1;
 94    while(pmove&&pmove->data!=data){
 95        pmove=pmove->next;
 96        pos++;
 97    }
 98    return pos;
 99}
100
101/*返回表长*/
102status listlength(dlinklist head,dlinklist tail){
103    dlinklist pmove=head->next;
104    int length=0;
105    while(pmove!=tail){
106        pmove=pmove->next;
107        length++;
108    }
109    return length;
110}
111
112
113/*删除链表中第pos个位置的元素,并用data返回*/
114status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
115    int i=1;
116    dlinklist pmove=head->next;
117    while(pmove&&i<pos){
118        pmove=pmove->next;
119        i++;
120    }
121    if(!pmove||i>pos){
122        printf("输入数据非法\n");
123        return ERROR;
124    }
125    else{
126        *data=pmove->data;
127        pmove->next->prior=pmove->prior;
128        pmove->prior->next=pmove->next;
129        free(pmove);
130    }
131}
132
133/*在链表尾插入元素*/
134status inserttail(dlinklist head,dlinklist tail,elemtype data){
135    dlinklist pinsert;
136    pinsert=(dlinklist)malloc(sizeof(node));
137    pinsert->data=data;
138    pinsert->next=NULL;
139    pinsert->prior=NULL;
140    tail->prior->next=pinsert;
141    pinsert->prior=tail->prior;
142    pinsert->next=tail;
143    tail->prior=pinsert;
144    return OK;
145} 
146int main(void){
147    dlinklist head,tail;
148    int i=0;
149    elemtype data=0;
150    initdlinklist(&head,&tail);
151    if(emptylinklist(head,tail))
152        printf("链表为空\n");
153    else
154        printf("链表不为空\n");
155    printf("头插法创建链表\n"); 
156    for(i=0;i<10;i++){
157        createdlinklisthead(head,tail,i);
158    }
159    traverselist(head,tail);
160
161    for(i=0;i<10;i++){
162        printf("表中值为%d的元素的位置为",i); 
163        printf("%d位\n",locateelem(head,tail,i));
164    }
165    printf("表长为%d\n",listlength(head,tail));
166    printf("逆序打印链表");
167    inverse(head,tail);
168    for(i=0;i<10;i++){
169        deleteelem(head,tail,1,&data);
170        printf("被删除的元素为%d\n",data);
171    }
172    traverselist(head,tail);
173    if(emptylinklist(head,tail))
174        printf("链表为空\n");
175    else
176        printf("链表不为空\n");
177        printf("尾插法创建链表\n");
178    for(i=0;i<10;i++){
179        //inserttail(head,tail,i);
180        createdlinklisttail(head,tail,i);
181    }
182    printplist(head,tail);
183
184}

PS:学有余力的同伴等,可以品尝一下做当下节课介绍的情节,做一个循环双向链表出来啊。

2.1 什么是静态链表?

俺们把线性表的要素存放于频繁组吃,这些因素由少数个地区组成:

  • 数据域data
  • 指针域cur

数据域是存放数据的,而借助于针域,这里跟链表不同是,它抱的不再是负于下一个节点的内存地址。而是下一个节点在反复组被的下标。我们就将这种用数组描述的链表称为静态表,该法吧叫游标实现学。如下图所示:

manbetx手机网页版 15

由于达到图我们要小心以下几点:

  • 咱们本着反复组的首先单因素和尾声一个要素做特殊处理,不存数量。
  • 拿不使用的数组元素称为备用链表。
  • 一再组的首先独因素(下标为0)的cur域存放备用链表第一单节点的下标。
  • 反复组的终极一个元素的cur域存放第一个发数量的节点的下标,相当给链表中头结点的在。链表为空时,其值为0。

如下图:

manbetx手机网页版 16

引出的题目:数组的长定义之问题,无法预支。所以,为了防范溢起,我们一般将静态表开得特别一点。

完全结语

至于线性表大体内容三节课基本讲了了。不过还有许多幽默的操作,比如链表的逆序,合并,排序等等。这些情节咱们下次空余再聊吧。祝大家马到成功!

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}

运作结果

manbetx手机网页版 17运作结果

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图