美文网首页
【数据结构】单链表(Singly Linked List ) &

【数据结构】单链表(Singly Linked List ) &

作者: 番茄鸡蛋炒饭被抢注啦 | 来源:发表于2018-02-08 00:53 被阅读34次

    更多精彩尽在微信公众号【程序猿声】

    微信公众号

    数据结构-线性表|顺序表|链表(中)

    本节纲要

    • 预备知识
    • 顺序表(Sequential List)
    • 单链表(Singly Linked List )
    • 静态链表(Static list )
    • 循环链表(circular linked list)
    • 双向链表(doubly linked list)

    03 单链表(Singly Linked List )

    3.1 什么是单链表？

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

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

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


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

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

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


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

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

    3.3 单链表的读取

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

    #define status bool
#define ERROR false
#define OK true
/*
 * 函数功能：获取位置index节点的数据
 * 参数说明：phead链表头结点，e用来获取的变量，index索引
*/

status GetSListIndexNode(Node * phead,DType *e, int index)
{
    int icount = 0; //计数器
    //注：0号位为头结点，头结点不存放任何数据
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength()/*此处为链表长度*/)
    {
        return ERROR; //异常 处理
    }
    while (phead->pnext != nullptr)
    {
        icount++;
        phead = phead->pnext;
        if (icount == index)
        {
            *e = phead->data;
            return OK;
        }
    }
    return ERROR;
}

    3.4 单链表的插入

    3.4.1 指定位置后插

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


    图中，假如此时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 ②③
      具体代码如下：
    #define status bool
#define ERROR false
#define OK true
/*
 * 函数功能：指定位置后插
 * 参数说明：phead链表头结点，IData插入的数据，index索引
*/
status InsertSListNodeFront(Node * phead, DType IData, int index)
{
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    int iCount = 0; //计数器
    Node<DType> * q = nullptr; //备用
    while (phead->pnext != nullptr)
    {
        iCount++;
        q = phead;
        phead = phead->pnext;
        if ( iCount == index )
        {
            Node<DType> * p = new Node<DType>;
            p->data = IData;
            p->pnext = phead;
            q->pnext = p;   //前插
            return OK;
        }
    }
    return ERROR;
}

    3.4.1 指定位置前插

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

    /*
 * 函数功能：指定位置后插
 * 参数说明：phead链表头结点，IData插入的数据，index索引
*/
status InsertSListNodeBack(Node * phead, DType IData, int index)
{
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    int iCount = 0; //计数器
    Node<DType> * q = nullptr; //备用
    while (phead->pnext != nullptr)
    {
        iCount++;
        q = phead;
        phead = phead->pnext;
        if (iCount == index)
        {
            Node<DType> * p = new Node<DType>;
            q = phead;
            phead = phead->pnext; //后插就是后一个节点的前插咯
            p->data = IData;
            p->pnext = phead;
            q->pnext = p;   
            return OK;
        }
    }
    return ERROR;
}

    3.5 单链表的删除

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

    算法描述:

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

    具体代码如下:

    /*
 * 函数功能：指定位置后插
 * 参数说明：phead链表头结点，IData获取删除的数据，index索引
*/
//删除指定位置节点(e获取删除元素)
template <typename DType>
status DeleteSListIndexNode(Node * phead, DType *e, int index)
{
    int i = 0; //计数器
    Node<DType> * q = nullptr;
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    while (phead->pnext != nullptr)
    {
        i++;
        q = phead; //保存备用
        phead = phead->pnext;
        if (i == index)
        {
            *e = phead->data;
            q->pnext = phead->pnext; //删除出局
            return OK;
        }
    }
    return ERROR;
}

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

    3.6 单链表的完整代码

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

    /*
 * 文件名:SingleLinkList.h
 * 说明 ：类的各种声明
 */
#pragma once //VC编译器防止头文件被重复包含的一条预编译指令

#define status bool
#define OK true
#define ERROR false
#define YES true
#define NO false

template <typename DType>
class Node
{
public:
    DType data;
    Node * pnext;
};

template <typename DType>
class CSingleLinkList
{
private:
    Node<DType> *phead; //链表头指针
public:
    CSingleLinkList();//构造，类被创建时调用
    ~CSingleLinkList();//析构，类被销毁时调用
public:
    //初始化链表
    status InitSList();
    //获取链表长度
    int GetSListLength();
    //增加一个节点 前插法
    status AddSListNodeFront(DType idata);
    //增加一个节点 后插法
    status AddSListNodeBack( DType idata);
    //判断链表是否为空
    status IsSListEmpty();
    //获取指定位置节点值(注意，本程序规定0号为头节点，e获取删除元素)
    status GetSListIndexNode(DType *e, int index);
    //删除指定位置节点(e获取删除元素)
    status DeleteSListIndexNode(DType *e, int index);
    //查找链表中指定值(pindex获取位置0==>not found)
    status SearchSListNode(DType SData, int *pindex);
    //指定位置前插
    status InsertSListNodeFront(DType IData, int index);
    //指定位置后插
    status InsertSListNodeBack(DType IData, int index);
    //清空链表(保留根节点)
    status ClearSList();
    //销毁链表(all delete)
    status DestorySList();
    //尾部删除一个元素
    status DeleteSListNodeBack();
    //打印链表   此函数根据实际情况而定
    void PrintSList();
};

/*
 * 文件名:SingleLinkList.cpp
 * 说明 ：类的各种方法的实现
 */

#include "SingleLinkList.h"
#include <stdio.h>

template <typename DType>
CSingleLinkList<DType>::CSingleLinkList()
{
    cout << "链表创建" << endl;
    InitSList();
}
template <typename DType>
CSingleLinkList<DType>::~CSingleLinkList()
{
    cout << "链表销毁" << endl;
    DestorySList();
}
//初始化链表
template <typename DType>
status CSingleLinkList<DType>::InitSList()
{
    Node<DType> * ph = new Node<DType>;
    if (ph != NULL)
    {
        ph->pnext = nullptr;
        this->phead = ph; //头结点
        return OK;
    }
    return ERROR;
}
//获取链表长度(head_node is not included)
template <typename DType>
int CSingleLinkList<DType>::GetSListLength()
{
    int length = 0;
    Node<DType> * phead = this->phead;
    while (phead->pnext != nullptr)
    {
        length++;
        phead = phead->pnext;
    }
    return length;
}
//增加一个节点 前插法
template <typename DType>
status CSingleLinkList<DType>::AddSListNodeFront( DType idata)
{
    Node<DType> * pnode = new Node<DType>;
    if (pnode != NULL)
    {
        pnode->data = idata;
        pnode->pnext = this->phead->pnext;
        this->phead->pnext = pnode; //挂载
        
        //printf("pnode = %p  pnode->pnext = %p this->phead->pnext = %p this->phead = %p\n", pnode, pnode->pnext, this->phead->pnext, this->phead);
        return OK;
    }
    return ERROR;
}


//增加一个节点 尾插法
template <typename DType>
status CSingleLinkList<DType>::AddSListNodeBack(DType idata)
{
    Node<DType> * pnode = new Node<DType>;
    Node<DType> * phead = this->phead;
    if (pnode != NULL)
    {
        while (phead->pnext != nullptr)
        {
            phead = phead->pnext;
        }
        pnode->data = idata;
        pnode->pnext = nullptr;
        phead->pnext = pnode; //挂载
        return OK;
    }
    return ERROR;
}
//判断链表是否为空
template <typename DType>
status CSingleLinkList<DType>::IsSListEmpty()
{
    if (this->phead->pnext == nullptr)
    {
        return YES;
    }
    return NO;
}
//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)
template <typename DType>
status CSingleLinkList<DType>::GetSListIndexNode(DType *e, int index)
{
    Node<DType> * phead = this->phead;
    int i = 0; //计数器
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    while (phead->pnext != nullptr)
    {
        i++;
        phead = phead->pnext;
        if (i == index)
        {
            *e = phead->data;
            return OK;
        }
    }
    return ERROR;
}
//删除指定位置节点(e获取删除元素)
template <typename DType>
status CSingleLinkList<DType>::DeleteSListIndexNode( DType *e, int index)
{
    Node<DType> * phead = this->phead;
    int i = 0; //计数器
    Node<DType> * q = nullptr;
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    while (phead->pnext != nullptr)
    {
        i++;
        q = phead; //保存备用
        phead = phead->pnext;
        if (i == index)
        {
            *e = phead->data;
            q->pnext = phead->pnext; //删除出局
            return OK;
        }
    }
    return ERROR;
}
//查找链表中指定值(pindex获取位置   0==>not found)
template <typename DType>
status CSingleLinkList<DType>::SearchSListNode( DType SData, int *pindex)
{
    Node<DType> * phead = this->phead;
    int iCount = 0;//计数器
    while (phead->pnext != nullptr)
    {
        iCount++;
        phead = phead->pnext;
        if (phead->data == SData)
        {
            *pindex = iCount;
            return YES;
        }
    }
    *pindex = 0;
    return NO;
}
//指定位置前插
template <typename DType>
status CSingleLinkList<DType>::InsertSListNodeFront(DType IData, int index)
{
    Node<DType> * phead = this->phead;
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    int iCount = 0; //计数器
    Node<DType> * q = nullptr; //备用
    while (phead->pnext != nullptr)
    {
        iCount++;
        q = phead;
        phead = phead->pnext;
        if ( iCount == index )
        {
            Node<DType> * p = new Node<DType>;
            p->data = IData;
            p->pnext = phead;
            q->pnext = p;   //前插
            return OK;
        }
    }
    return ERROR;
}
//指定位置后插
template <typename DType>
status CSingleLinkList<DType>::InsertSListNodeBack( DType IData, int index)
{
    Node<DType> * phead = this->phead;
    if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
    {
        return ERROR; //异常 处理
    }
    int iCount = 0; //计数器
    Node<DType> * q = nullptr; //备用
    while (phead->pnext != nullptr)
    {
        iCount++;
        q = phead;
        phead = phead->pnext;
        if (iCount == index)
        {
            Node<DType> * p = new Node<DType>;
            q = phead;
            phead = phead->pnext; //后插就是后一个节点的前插咯
            p->data = IData;
            p->pnext = phead;
            q->pnext = p;   
            return OK;
        }
    }
    return ERROR;
}
//清空链表(保留根节点)
template <typename DType>
status CSingleLinkList<DType>::ClearSList()
{
    Node<DType> * phead = this->phead;
    Node<DType> * q = nullptr; //防止那啥，野指针
    phead = phead->pnext;//保留头节点
    while (phead != nullptr)
    {
        q = phead;
        phead = phead->pnext;
        delete q; //释放
    }
    this->phead->pnext = nullptr;
    return OK;
}
//销毁链表(all delete)
template <typename DType>
status CSingleLinkList<DType>::DestorySList()
{
    ClearSList();
    delete this->phead;//释放头结点 
    return OK;
}

template <typename DType>
status CSingleLinkList<DType>::DeleteSListNodeBack()
{
    Node<DType> * phead = this->phead;
    Node<DType> * q = nullptr; //备用
    if (phead->pnext == nullptr)
    {
        return ERROR; //链表都空了还删鸡毛
    }
    while (phead->pnext != nullptr)
    {
        q = phead;
        phead = phead->pnext;
    }
    q->pnext = nullptr;
    delete phead;

    return OK;
    
}
template <typename DType>
void CSingleLinkList<DType>::PrintSList()
{
    Node<DType> * phead = this->phead;
    if (phead->pnext == nullptr || phead == nullptr)
    {
        cout << "链表为空，打印鸡毛" << endl;
        return;
    }
    int i = 1;
    cout << "===============print list================" << endl;
    while (phead->pnext != nullptr)
    {
        phead = phead->pnext;
        cout <<"node[" << i++ << "] = " << phead->data<<endl;
    }
}

/*
 * 文件名:SingleLinkListTest.cpp
 * 说明 ：测试代码
 */

 #include <iostream>
#include "SingleLinkList.h"
#include "SingleLinkList.cpp"

using namespace std;

int main()
{
    CSingleLinkList<int> * pMySList = new CSingleLinkList<int>;
    cout << pMySList->IsSListEmpty() << endl;
    pMySList->AddSListNodeFront(111);
    pMySList->AddSListNodeFront(222);
    pMySList->AddSListNodeFront(333);

    cout << "链表长度" << pMySList->GetSListLength() << endl;

    pMySList->PrintSList();

    pMySList->AddSListNodeBack(444);
    pMySList->AddSListNodeBack(555);
    pMySList->AddSListNodeBack(666);

    pMySList->PrintSList();

    cout << pMySList->IsSListEmpty() << endl;
    cout << "链表长度" << pMySList->GetSListLength() << endl;

    int GetElem, GetIndex;
    pMySList->GetSListIndexNode(&GetElem, 2);
    cout << "Got Elem = " << GetElem << endl;

    pMySList->GetSListIndexNode(&GetElem, 6);
    cout << "Got Elem = " << GetElem << endl;

    pMySList->GetSListIndexNode(&GetElem, 4);
    cout << "Got Elem = " << GetElem << endl;

    pMySList->DeleteSListIndexNode(&GetElem, 1);
    cout << "del Elem = " << GetElem << endl;
    pMySList->DeleteSListIndexNode(&GetElem, 3);
    cout << "del Elem = " << GetElem << endl;
    

    pMySList->PrintSList();

    pMySList->SearchSListNode(555, &GetIndex);
    cout << "Search Index = " << GetIndex << endl;
    pMySList->SearchSListNode(111, &GetIndex);
    cout << "Search Index = " << GetIndex << endl;
    pMySList->SearchSListNode(666, &GetIndex);
    cout << "Search Index = " << GetIndex << endl;

    pMySList->InsertSListNodeFront(333, 1);
    pMySList->InsertSListNodeFront(444, 4);

    pMySList->PrintSList();

    pMySList->InsertSListNodeBack(777, 3);
    pMySList->InsertSListNodeBack(888, 5);

    pMySList->PrintSList();

    pMySList->DeleteSListNodeBack();
    pMySList->PrintSList();
    pMySList->DeleteSListNodeBack();
    pMySList->PrintSList();
    pMySList->DeleteSListNodeBack();
    pMySList->PrintSList();

    return 0;
}

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

    04 静态链表(circular linked list)

    4.1 什么是静态链表？

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

    • 数据域data
    • 指针域cur

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


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

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

    如下图：

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

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

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

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

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

    4.3 静态链表的插入操作

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

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

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

    分配内存

    /分配备用链表的一个结点,返回下标
//若为0，则说明备用链表用完
int Malloc_SL(SLinkList space)
{
    int i = space[0].cur;
    //判断备用链表是否非空
    if(space[0].cur)    
        //备用链表头指针指向第二个空结点
        space[0].cur = space[i].cur; 

    return i;    //返回第一个空结点
}

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

    //在链表的第i个位置插入元素e
void SlistInsert(SLinkList space, int i, ElemType e)
{
    //超出范围
    if(i < 1 || i > SListLength(space)+1) 
        return;
    int k = 1, j;
    //使k指示要插入的结点的前一个结点
    for(j = 0; j <i-1; j++) 
        k = space[k].cur;

    int v = Malloc_SL(space);
    if(v)     //如果有空间
    {
        space[v].data = e;
        space[v].cur = space[k].cur;
        space[k].cur = v;  //链入链表
    }
}

    注意几点：

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

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

    4.4 静态链表的删除操作

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

    回收内存

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

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

    //删除第i个位置的元素
void SListDelete(SLinkList space, int i)
{   //超出范围退出
    if(i < 1 || i > SListLength(space))  
        return ;
    int k = 1, j;
     //使k指示要删除的结点的前一个结点
    for(j = 0; j <i-1; j++)  
        k = space[k].cur;

    int temp = space[k].cur;
    space[k].cur = space[temp].cur;
    Free_SL(space, temp);
}

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

    4.5 静态链表的完整代码

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

    StaticLinkList.h

    #pragma once
#include <iomanip>

#define MAXSIZE 100

#define status bool
#define YES true
#define NO false
#define OK true
#define ERROR false

template <typename DATATYPE>
class Component
{
public:
    DATATYPE data; //数据域
    int cur;       //cur域，指向下一个元素的下标
};


template <typename DATATYPE>
class CStaticLinkList
{
public:
    Component<DATATYPE>  StaticLinkList[MAXSIZE];  //静态表
//自定义malloc和free
public:
    int MallocNodeSSL();
    status FreeNodeSSL(int index);
public:
    status InitList(); //初始化静态表
    status BackAddList( DATATYPE AddData); //尾增加
    status InsertNodeList(DATATYPE InsertData, int index);//指定位置插入
    status DeleteNodeList(DATATYPE *DelData, int index); //指定位置删除
    int SearchList(DATATYPE sData);       //搜索数据为sData的节点,返回其在数组中的下标,0表示失败
    status GetIndexList(DATATYPE *gData, int index);//获取指定索引的节点数据
    int GetLengthList(); //获取静态表的长度
    status ClearList(); //清空静态表
    status IsEmptyList(); //判断静态表是否为空
    status IsFullList(); //判断静态表是否满了
    void PrintList(); //打印静态表,此函数根据实际情况编写

public:
    CStaticLinkList();
    ~CStaticLinkList();
};

    StaticLinkList.cpp

    #include "StaticLinkList.h"

template <typename DATATYPE>
CStaticLinkList<DATATYPE>::CStaticLinkList()
{
    cout << "===========静态表创建===========" << endl;
    InitList();
}

template <typename DATATYPE>
CStaticLinkList<DATATYPE>::~CStaticLinkList()
{
    cout << "===========静态表销毁===========" << endl;
}

template <typename DATATYPE>
int CStaticLinkList<DATATYPE>::MallocNodeSSL()
{
    int index = StaticLinkList[0].cur; //把备用链表第一个节点拿出来用
    if (StaticLinkList[0].cur) //判断是否还有位置
    {
        StaticLinkList[0].cur = StaticLinkList[index].cur; //让备用链表第二个节点上来顶替第一个的位置
    }

    return index; //返回0表示分配失败
}

template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::FreeNodeSSL(int index)
{
    //将删除节点挂接到备用链表上
    this->StaticLinkList[index].cur = this->StaticLinkList[0].cur;
    this->StaticLinkList[0].cur = index;
    
    return OK;
}

template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::InitList()
{
    int i;
    for (i = 0; i < MAXSIZE - 1; i++)
    {
        StaticLinkList[i].cur = i + 1;//全部塞入备用链表
    }
    StaticLinkList[MAXSIZE - 1].cur = 0;/*因为目前静态表为空,最后一个节点的cur域为0*/
    return OK;
}

template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::BackAddList(DATATYPE AddData) //尾增加
{
    if (IsFullList())
    {
        return ERROR;
    }
    int index = MAXSIZE - 1;
    int last = index;

    while (index != 0)
    {
        last = index;
        index = StaticLinkList[index].cur;
    }

    int k = MallocNodeSSL(); //获取空闲位置下标
    if (k)
    {
        StaticLinkList[k].data = AddData; //存入数据
        StaticLinkList[k].cur = 0;   //末尾指向0
        StaticLinkList[last].cur = k;
        return OK;
    }

    return ERROR;
    
}
//在List中第i个节点之前插入新的节点
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::InsertNodeList(DATATYPE InsertData, int index)//指定位置插入
{
    int i, GetFree, pos;
    pos = MAXSIZE - 1;//最后节点下标
    if (index < 1 || index > GetLengthList() || IsFullList())
    {
        return ERROR; //位置异常处理
    }

    GetFree = MallocNodeSSL();
    if (GetFree)
    {
        StaticLinkList[GetFree].data = InsertData;
        for (i = 0; i < index - 1; i++)
        {
            pos = StaticLinkList[pos].cur; //定位
        }
        StaticLinkList[GetFree].cur = StaticLinkList[pos].cur;
        StaticLinkList[pos].cur = GetFree; //插入

        int q = StaticLinkList[MAXSIZE - 1].cur;
        if (q == 0) //静态表为空
        {
            StaticLinkList[MAXSIZE - 1].cur = 1;
        }
        return OK;
    }
    return ERROR;
}

//判断是否为空
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::IsEmptyList()
{
    if (StaticLinkList[MAXSIZE-1].cur == 0)
    {
        return YES; 
    }

    return NO;
}
//判断静态表是否满了
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::IsFullList()
{
    if (GetLengthList() == MAXSIZE - 2) //因为首位不存数据,因此pass掉
    {
        return YES;
    }
    return NO;
}
template <typename DATATYPE>
int CStaticLinkList<DATATYPE>::GetLengthList() //获取静态表的长度
{
    int iCount = 0;
    int k = MAXSIZE - 1;
    while (StaticLinkList[k].cur != 0)
    {
        iCount++;
        k = StaticLinkList[k].cur;
    }

    return iCount;
}
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::DeleteNodeList(DATATYPE *DelData, int index)//指定位置删除
{
    int i, pos, k;
    pos = MAXSIZE - 1;//最后节点下标
    if (index < 1 || index > GetLengthList() || IsEmptyList())
    {
        return ERROR; //位置异常处理
    }
    for (i = 0; i < index - 1; i++)
    {
        pos = StaticLinkList[pos].cur; //定位到被删除节点的前一个节点
    }
    k = StaticLinkList[pos].cur; 
    *DelData = StaticLinkList[k].data; //获取数据
    StaticLinkList[pos].cur = StaticLinkList[k].cur;//让前一个节点直接指向后一个节点.把夹在中间的踢掉
    FreeNodeSSL(k); //释放空间

    return OK;
}
//搜索数据为sData的节点,返回其在静态表中的第i个位置,0表示没找到
template <typename DATATYPE>
int CStaticLinkList<DATATYPE>::SearchList(DATATYPE sData)
{
    int pos = StaticLinkList[MAXSIZE-1].cur;
    int iCount = 1;
    while (pos != 0)
    {
        if (StaticLinkList[pos].data == sData) //找到数据
        {
            return iCount;
        }
        pos = StaticLinkList[pos].cur; //循环遍历
        iCount++;
    }

    return 0;
}
template <typename DATATYPE>
status CStaticLinkList<DATATYPE>::GetIndexList(DATATYPE *gData, int index)//获取第index个节点数据
{
    int i, pos;
    pos = MAXSIZE - 1;//最后节点下标
    if (index < 1 || index > GetLengthList() || IsEmptyList())
    {
        return ERROR; //位置异常处理
    }
    for (i = 0; i < index; i++)
    {
        pos = StaticLinkList[pos].cur; //定位到第index个节点
    }
    *gData = StaticLinkList[pos].data;

    return OK;
}
template <typename DATATYPE>
status  CStaticLinkList<DATATYPE>::ClearList() //清空静态表
{
    InitList();//再初始化一次就是清空了
    return  OK;
}
template <typename DATATYPE>
void  CStaticLinkList<DATATYPE>::PrintList()
{
    int pos = StaticLinkList[MAXSIZE - 1].cur;
    if (pos == 0)
    {
        cout << "===========静态链表为空,打印鸡毛!!!===========" << endl;
        return;
    }
    cout << setiosflags(ios::left);
    cout << setw(10) << "索引" << setw(10) << "下标" << setw(10) << "data" << setw(10) << "cur" << endl;
    int iCount = 1;
    while (pos != 0)
    {
        cout << setw(10) << iCount << setw(10) << pos << setw(10) << StaticLinkList[pos].data << setw(10) << StaticLinkList[pos].cur << endl;
        pos = StaticLinkList[pos].cur; //循环遍历
        iCount++;
    }
}

    StaticLinkListTest.cpp测试代码

    #include <iostream>
#include <iomanip>
#include "StaticLinkList.h"
#include "StaticLinkList.cpp"
using namespace std;

int main()
{
    char get;
    CStaticLinkList<char> *p = new CStaticLinkList<char>;
    p->PrintList();
    
    p->BackAddList('a'); //pass
    p->BackAddList('b');
    p->BackAddList('c');
    p->BackAddList('d');
    p->BackAddList('e');

    //p->ClearList();      //pass

    p->PrintList();

    p->DeleteNodeList(&get, 2);  //pass
    cout << "get = " << get << endl;

    p->DeleteNodeList(&get, 2);
    cout << "get = " << get << endl;

    p->PrintList();
    p->BackAddList('f');

    p->PrintList();
    cout << "length = " << p->GetLengthList() << endl;//pass

    p->GetIndexList(&get, 3);  //pass
    cout << "get = " << get << endl; 

    p->InsertNodeList('h', 2);
    p->InsertNodeList('i', 3);

    p->PrintList();
    cout << "length = " << p->GetLengthList() << endl;//pass

    cout << "search_pos = " << p->SearchList('q') << endl;
    cout << "search_pos = " << p->SearchList('h') << endl;
    cout << "search_pos = " << p->SearchList('i') << endl;

    delete p;

    return 0;
}

    运行结果

    运行结果

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

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

    另外：部分资料参考自网络，来源和作者实在无法考证，如果有侵犯到您的劳动成果，请速与我联系。

    相关文章

      网友评论

          本文标题：【数据结构】单链表(Singly Linked List ) &

          本文链接：https://www.haomeiwen.com/subject/gnszzxtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|【数据结构】单链表(Singly Linked List ) &|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！