【数据结构】线性表|顺序表|链表(下)

短短的路走走停停

发布于 2019-05-14 18:23:44

4080

发布于 2019-05-14 18:23:44

文章被收录于专栏：程序猿声程序猿声

05 循环链表

5.1什么是循环链表？

前面介绍了单链表，相信大家还记得相关的概念。其实循环链表跟单链表也没有差别很多，只是在某些细节上的处理方式会稍稍不同。

在此之前，大家可以先思考一个问题：单链表中，要找到其中某个节点只需要从头节点开始遍历链表即可，但是有些时候我们的想法是，能不能从任意节点开始遍历，也能找到我们需要的那个节点呢？

其实啊，这个实现也很简单自然，把整个链表串成一个环问题就迎刃而解了。所以，关于循环链表，我们有了如下的定义：

将单链表中的尾节点的指针域由NULL改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表就可以称之为**单循环链表，简称循环链表(circular linked list)。

5.2 循环链表图示

这里我们讨论的链表还是设置一个头结点（当然，链表并不是一定需要一个头结点）。

当链表为空的时候，我们可以有如下表示：

对于非空链表则可以这样表示：

不得不提的一点

对于循环链表这种设计，我们在遍历的时候的结束条件就不再是p为空的时候结束了。而是p等于头结点的时候遍历才完成。这一点希望大家切记。

再多说两句

我们知道，有了头结点，我们可以轻而易举访问第一个节点。但是当要访问最后一个节点时，却要将整个链表扫一遍，效率不可谓不低下……那么，有没有更好的办法呢？

当然是有的，只不过这里我们需要将循环链表再做一个小小的改进，具体表现为：

从上图可以看出，我们抛弃了以往的头指针，取而代之的是采用一个尾指针指向了最后一个节点。而且，因为链表是循环的，当我们需要访问第一个节点时，也very easy！只需要尾指针往后走一个就到前面了。

5.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}

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

06 双向链表(doubly linked list)

6.1 双向链表又是个什么表？

引言

我们都知道，在单链表中由于有next指针的存在，需要查找下一个节点的时间复杂度也只是O(1)而已。但是正如生活并不总是那么如意，当我们想再吃一吃回头草的时候，查找上一节点的时间复杂度却变成了O(n)，这真是让人头大。

双向链表不过我们老一辈的科学家早就想到了这个问题，并提出了很好的解决方法。在每个节点中再多加了一个指针域，从而让一个指针域指向前一个节点，一个指针域指向后一个节点。也正是如此，就有了我们今天所说的双向链表了。双向链表(doubly linked list)是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。

6.2 双向链表图示

国际惯例，这里我们依旧引入了头结点这个玩意儿。不仅如此，为了增加更多的刺激，我们还引入了一个尾节点。

双向链表为空时

双向链表在初始化时，要给首尾两个节点分配内存空间。成功分配后，要将首节点的prior指针和尾节点的next指针指向NULL，这是之后用来判断空表的条件。同时，当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

双向链表不为空时

每一个节点(首位节点除外)的两个指针域都分别指向其前驱和后继。

6.3 双向链表存储结构代码描述

双向链表一般可以采用如下的存储结构：

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

6.4 双向链表的插入

其实大家别看多了一个指针域就怕了。这玩意儿还是跟单链表一样简单得一批，需要注意的就是理清各个指针之间的关系。该指向哪的就让它指向哪里去就OK了。具体的表现为：

image

代码描述也很简单：

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

6.5 双向链表的删除

删除操作和单链表的操作基本差不多的。都是坐下常规操作了。只是多了一个前驱指针，注意一下即可。如下图：

image

代码描述：

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

6.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}

学有余力的小伙伴们，可以尝试一下结合这节课介绍的内容，做一个循环双向链表出来哦。

完整结语

关于线性表大体内容三节课基本讲完了。不过还有很多好玩的操作，比如链表的逆序，合并，排序等等。这些内容咱们下次有空再聊吧。祝大家学有所成！

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-07-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

c++

本文分享自程序猿声微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

c++

登录后参与评论

0 条评论

热度