数据结构之线性表---C++实现

线性表的逻辑结构

对于非空的线性表：

（1）有且仅有一个开始结点a₁,没有直接前驱，有唯一后继a₂;

（2）有且仅有一个终端结点a_n，没有直接后继，有唯一的直接前驱a_n-1;

（3）其余的内部结点a_i，都有唯一的直接前驱a_i-1和直接后继a_i+1;

下面给出不同的实际实现：

一、顺序表数据结构

  1 /////////////////////////////////////////////////////
  2 
  3 //SqList.h顺序表数据结构c++定义(基类)
  4 
  5 //////////////////////////////////////////////////
  6 
  7 #ifndef SQLIST_H
  8 #define SQLIST_H
  9 
 10 //顺序表使用的一些常量说明
 11 #define  LIST_MAX_SIZE 100 //顺序表初始存储空间的大小
 12 #define  LISTINCREMENT 10  //顺序表的存储空间增量
 13 #define  ERROR -1;
 14 #define  OK 0;
 15 typedef int Status;
 16 ///////////////////////////////////////////////////
 17 //顺序表数据结构声明（基类）
 18 #include <assert.h>
 19 #include <iostream>
 20 using namespace std;
 21 template <typename ElemType>
 22 class SqList
 23 {
 24 public:
 25     //有序顺序表折半查找
 26     int bin_search(ElemType key);
 27     //把顺序表置空
 28     void clear();
 29     //删除第i个元素
 30     Status deleteElem(int i,ElemType& e);
 31     //取第i个元素
 32     ElemType getElem(int i ,ElemType& e);
 33      //求顺序表中元素的个数
 34      int getLength();
 35      //取顺序表存储空间的大小
 36      int getListSize();
 37      //在第i个元素之前插入一个元素
 38      Status insert(int i,ElemType e);
 39      //判断顺序表是否为空
 40      bool isEmpty();
 41      //查找第1个与e满足compare（）关系的元素序号
 42      int locateElem(ElemType e,Status (*compare)(ElemType,ElemType));
 43      //重载赋值运算符的定义
 44      SqList<ElemType> operator = (SqList<ElemType> rightL);
 45      //返回某元素的前驱
 46      Status priorElem(ElemType e, ElemType& prior_e);
 47      //返回某元素的后继
 48      Status nextElem(ElemType e, ElemType& next_e);
 49      //在顺序表中查找某元素
 50      int sequentialSearch(ElemType e);
 51      //********************下面是系统自动调用的构造函数以及析构函数************************
 52 
 53      //顺序表构造函数
 54      SqList();
 55      //顺序表析构函数
 56      ~SqList();
 57      //顺序表靠被初始化构造函数
 58      SqList(const SqList<ElemType>& otherL);
 59 protected:
 60 
 61     ElemType * elem;//顺序表动态存储空间的首地址
 62     int listSize;//顺序表当前已分配的存储空间大小
 63     int n;//顺序表当前元素的个数
 64 private:
 65 };
 66 //////顺序表数据结构Ｃ＋＋实现（基类）
 67 
 68 
 69 //功能：在循序表折半查找
 70 //要求：顺序表实现排好序
 71 //输入：指定值key
 72 //输出：如果存在查找元素，则返回该元素的序号（元素的序号从1开始），否则，返回0
 73 template<typename ElemType>
 74 int SqList<ElemType>::bin_search(ElemType key)
 75 {
 76     int low;
 77     int mid;
 78     int high;
 79 
 80     //首先，把顺序表的整个区间设置为初始查找区域
 81     low = 0,high=n-1;
 82     while(low<=high)
 83     {
 84         mid = (low+high)/2;
 85 
 86         if (elem[mid]==key)
 87         {
 88             return mid+1; //返回元素实际的序号
 89         }
 90 
 91         else if (elem[mid]<key)
 92         {
 93             low = mid +1;
 94         }
 95 
 96         else 
 97         {
 98             high = mid -1;
 99         }
100         
101     }
102 
103     return 0;
104 }
105 
106 
107 //功能：把顺序表置空
108 //说明：只是把顺序表当前元素的个数设置为0，并不回收其存储空间
109 
110 template<typename ElemType>
111 void SqList<ElemType> ::clear()
112 {
113     n=0;
114 }
115 
116 //功能：删除第i个元素
117 
118 template <typename ElemType>
119 Status SqList<ElemType>::deleteElem(int i ,ElemType& e)
120 {
121     //判断第i个元素的序号i是否越界
122     if (i<1||i>n)
123     {
124         return false;
125     }
126 
127     e= elem[i-1];
128     //第i个结点以后的数据都向前移动一个位置
129     for (int j =i+1;j<=n;++j)
130     {
131         elem[j-2] = elem[j-1];
132     }
133     --n;//元素个数减1
134     return true;
135 }
136 
137 
138 //功能：取第i个元素
139 
140 template <typename ElemType>
141 ElemType SqList<ElemType>::getElem(int i ,ElemType& e)
142 {
143     //判断i是否越界
144     if (i<1||i>n)
145     {
146         return ERROR;
147     }
148 
149     e=elem[i-1];
150     return e;
151 }
152 
153 
154 
155 //求顺序表中元素的个数
156 
157 template <typename ElemType>
158 int SqList<ElemType>::getLength()
159 {
160     return n;
161 }
162 
163 
164 //功能：去顺序表存储空间的大小
165 
166 template<typename ElemType>
167 int SqList<ElemType>::getListSize()
168 {
169     return listSize;
170 }
171 
172 
173 //功能：在第i个元素之前插入一个元素
174 
175 
176 template <typename ElemType>
177 Status SqList<ElemType>::insert(int i,ElemType e)
178 {
179     ElemType *newbase;
180 
181     if (i<1||i>(n+1))
182     {
183         return ERROR;
184     }
185 //如果现在顺序表中的元素个数大于等于表的容量
186 if (n>=listSize)
187 {//重新申请新的顺序表空间，扩充容量
188     newbase = new ElemType(listSize+LISTINCREMENT);
189     assert(newbase != 0);
190 //将原来顺序表中的元素复制到新的顺序表中
191     for (int j = 1;j<=n;++j)
192     {
193         newbase[j-1] = elem[j-1];
194     }
195     //删除原来顺序表中的元素
196     delete [] elem;
197     //将顺序表的基地址更改为新申请的空间地址
198     elem = newbase;
199     //更新表容量
200     listSize+=LISTINCREMENT;
201 }
202 //从顺序表的最后一个元素开始，直到第i个元素，每个元素后移一位
203 for (int j=n; j>=i;--j)
204 {
205     elem[j] = elem[j-1];
206     
207 }
208 
209     elem[i-1]=e;
210     ++n;
211     return OK;
212 }
213 
214 
215 //功能：判断顺序表是否为空
216 
217 template <typename ElemType>
218 bool SqList<ElemType>::isEmpty()
219 {
220     return n?false:true;
221 }
222 
223 //功能：查找第1个与e满足compare（）关系的元素
224 
225 template<typename ElemType>
226 int SqList<ElemType>::locateElem(ElemType e,Status (*compare)(ElemType,ElemType))
227 {
228     //查找满足条件的元素，即从顺序表第一个严肃开始，逐一判断顺序表的当前元素
229     //是否与待查值满足比较关系，直到满足或顺序表查找完毕。
230 
231     for (int i = 1;i<n && !(*compare)(elem[i-1],e);i++);
232     
233     if (i <= n)
234     {
235         return i;
236     }
237     else
238         return 0;
239 }
240 
241 //功能：返回某元素的后继
242 template <typename ElemType>
243 int SqList<ElemType>::nextElem(ElemType e, ElemType& next_e)
244 {
245     int i =locateElem(e,equal);
246     
247     if (i<0||i==n)
248     {
249         return ERROR;
250     }
251     else
252         getElem(i+1,next_e);
253     return OK;
254 }
255 //功能：重载赋值运算符的定义
256 template<typename ElemType>
257 SqList<ElemType> SqList<ElemType>::operator =(SqList<ElemType> rightL)
258 {
259     if (this != &rightL)
260     {
261         delete[] elem;
262         elem = new ElemType(rightL.listSize);
263         assert(elem ! = 0);
264         listSize = rightL.listSize;
265     }
266     n = rightL.n;
267     for (int i =1;i<=n;++i)
268     {
269         elem[i-1]=rightL.elem[i-1];
270     }
271     return *this;
272 }
273 //功能：返回某元素的前驱
274 
275 template<typename ElemType>
276 Status SqList<ElemType>::priorElem(ElemType e, ElemType& prior_e)
277 {
278     int i = locateElem(e,equal);
279     if (i<1)
280     {
281         return ERROR;
282     }
283     else
284         getElem(i-1,prior_e);
285     return OK;
286 }
287 //功能：在顺序表中顺序查找某元素
288 template<typename ElemType>
289 int SqList<ElemType>::sequentialSearch(ElemType key)
290 {
291     for (int i =1;i<=n&&key!=elem[i-1];++i);
292 
293     if (i<=n)
294     {
295         return i;
296     }
297     else
298         return 0;
299 }
300 //**********下面为系统自动调用的构造函数和析构函数的实现*********
301 
302 //功能：初始申请一个LIST_MAX_SIZED大小的动态存储空间，并把当前元素的个数置为0；
303 template<typename ElemType>
304 SqList<ElemType>::SqList()
305 {
306     elem = new ElemType(LIST_MAX_SIZE);
307     assert(elem != 0);
308     listSize = LIST_MAX_SIZE;
309     n= 0;
310 }
311 //功能：顺序表析构函数
312 template <typename ElemType>
313 SqList<ElemType>::~SqList()
314 {
315     //释放顺序表的元素空间
316     delete [] elem;
317 }
318 //功能：顺序表拷贝初始化的顺序表
319 template<typename ElemType>
320 SqList<ElemType>::SqList(const SqList<ElemType>& otherL)
321 {
322     elem = new ElemType(otherL.listSize);
323     assert(elem ! = 0;)
324     listSize = otherL.listSize;
325     n = otherL.n;
326     for (int i =1;i<=n;++i)
327     {
328         elem[i-1] = otherL.elem[i-1]
329     }
330 }
331 #endif

View Code

二、非循环单链表结构

为表示逻辑上的顺序关系，线性链表中的每个数据元素除存储本身的数据元素之外，还存储其后继结点的地址信息即指针next，这两部分信息组成的数据元素的存储映像即结点。

#ifndef LINKLIST_H
#define LINKLIST_H
#include <assert.h>
typedef int Status;
template<typename ElemType>
class LinkList
{
    //非循环单链表结点的C++声明
    class LinkNode
    {
    public:
        ElemType data;
        LinkNode* next;
    };
    //指向结点的指针类型声明
    typedef LinkNode * NodePointer;
    //非循环单链表的逆置
    void adverse();
    //把非循环单链表置空
    void clear();
    //删除非循环单链表中数据为e的第一个结点
    Status deleteElem(ElemType e);
    //删除非循环单链表中的重复值
    void deleteRepeat();
    //取非循环单链表的第i个结点
    Status getElem(int i ,ElemType& e);
    //取第一个结点的指针
    NodePointer getHead();
    //求非循环单链表结点个个数
    int getLength();
    //在第i个结点之前插入数据域为e的结点
    Status insert (int i ,ElemType e);
    //判断非循环单链表是否为空
    bool isEmpty();
    //查找第一个与e满足compare（）关系的结点
    Status locateELem(ElemType e,Status (*compare)(ElemType ,ElemType),int& i);
    //返回某结点前驱的数据域
    Status priorElem(ElemType e,ElemType& prior_e);
    //返回某结点后继的数据域
    Status nextElem (ElemType e, ElemType& next_e);
    //重载赋值运算符的定义
    LinkList <ElemType> operator = (LinkList<ElemType> rightL);
////////////////////下面为系统自动调用的构造函数以及析构函数声明////////////
    //非循环单链表的构造函数
    LinkList();
    //非循环单链表的析构函数
    ~LinkList();
    //非循环单链表的靠被初始化构造函数
    LinkList(const LinkList<ElemType>& otherL);
protected:
    //非循环单链表的头指针
    NodePointer head;
};

//////////////////////非循环单链表的Ｃ＋＋实现//////////////////////////////////////////

//功能：非循环单链表的逆置

template <typename ElemType>
void LinkList<ElemType>::adverse()
{
    NodePointer r =NULL;
    NodePointer p = NULL;
    NodePointer q =NULL;

    p = head;
    q = p->next;

    while (p)
    {
        p->next = r;
         r = p;
         p =q;
        if (q)
        {
            q = q->next;
        }
    }
    head = r;

}
//功能：把非循环单链表置空
template<typename ElemType>
void LinkList<ElemType> ::clear()
{
    NodePointer p = NULL;//指向欲删除的结点
    NodePointer q = NULL;//指向欲删除结点的后继
    q= head;
    while(q)
    {
         p =q;
         q = q->next;
         delete p;
    }
    head = NULL;
}
//功能： 删除非循环单链表中数据域为e的第一个结点
template<typename ElemType>
Status LinkList<ElemType>::deleteElem(ElemType e)
{
    NodePointer r =NULL;//指向欲删除结点的前驱
    NodePointer p = NULL;//指向欲删除的结点
    p = head;
    while(p && !equal(p->data,e))
    {
        r = p;
        p = p->next;
    }
    //如果找到链表表尾，则返回-1
    if ( p == NULL)
    {
        return -1;
    }
    //否则删除该结点，重新链接链表
    else
        r->next = p->next;
    delete p;

     return 0;
}

//功能：删除非循环单链表中的重复值
//步骤：（1）查找指针p所指的当前结点是否与前面的每个结点有重复值，即从非循环单链表的第一个结点（s指向）开始，
//直到指针p所指的当前结点为止，逐一判断指针s所指结点的数据域是否与指针p所指的当前结点相同；如果相同转向（2）；
//否则r和p均向前移动一个位置，重复（1）；
//(2)将删除s所指结点，r和p均向前移动一个为位置。
template<typename ElemType>
void LinkList<ElemType>::deleteRepeat()
{
    NodePointer r =NULL;//指向前驱结点的指针
    NodePointer p = NULL;//指向欲比较结点的指针
    NodePointer s = NULL;

    p = head;

    while(p)
    {
        s = head;
        while(s!=p)
        {
            if (s->data == p->data)
            {
                r->next = p->next;
                delete p ;
                p = r;
                break;
            }
            s= s->next;
        }
        r = p;
        if (p)//判断p是否到达链表尾部
        p = p->next;

    }
}
//功能：取非循环单链表的第i个结点

template <typename ElemType>
Status LinkList<ElemType>::getElem(int i ,ElemType& e)
{
    
    NodePointer p = head;
    int j = 1;

    while(p && j<i)
    {
        p = p->next;
        ++j;
    }

    if (!p || j>i)
    {
        return ERROR;
    }

    e = p->data;
    return OK;
    
}

//功能：取非循环单链表的头指针head
template<typename ElemType>
typename LinkList<ElemType>::NodePointer LinkList<ElemType>::getHead()
{
    return head;
}
//功能：求非循环单链表结点的个数
template <typename ElemType>
int LinkList<ElemType>::getLength()
{
    int n = 0;//记录此时结点的个数

    NodePointer p = head;

    while(p)
    {
        ++n;
        p = p->next;
    }
    return n;
}

//功能：在第i个结点之前插入一个数组域为e的结点
template<typename ElemType>
Status LinkList<ElemType>::insert(int i ,ElemType e)
{
    int j =1;
    NodePointer p =head;//用来指向所插位置的前驱
    NodePointer s;//指向新申请结点的地址
    //指针p向前移动到第i-1个结点的位置
    while(p && j<i-1)
    {
        ++j;
        p = p->next;
    }

    if (!p ||ｊ＞ｉ)
    {
        return ERROR;
    }

     s = new LinkNode;
     assert(s ! = 0);

     s->data = e;
     //如果在第一个位置插入
     if (i=1)
     {
         s->next = head;
         head =s;
     }
     else 
     {
         s->next = p->next;
         p->next = s;
     }
     return OK;
}
//功能：判断非循环单链表是否为空
template<typename ElemType>
bool LinkList<ElemType>::isEmpty()
{
    return(head?false:true);
}

//功能：查找第一个数据域与e满足compare（）比较关系的点
template <typename ElemType>
Status LinkList<ElemType>::locateELem(ElemType e,Status (*compare)(ElemType ,ElemType),int& i)
{
    
    NodePointer  p =head;
    i =1;
    //从第一个结点开始，查找与e满足compare关系的结点
    while( p && !(*compare)(p->data,e))
    {
         p = p->next;
         ++i;
    }
    //如果p为空，则返回错误
    if (!p)
    {
        return ERROR;
    }

    return OK;

}

//功能：返回某结点（数据域为e）后继的数据域
template <typename ElemType>
Status LinkList<ElemType>::nextElem(ElemType e, ElemType& next_e)
{
    NodePointer p =head;

    while (p && !equal(p->data,e))
    {
        p = p->next;
    }

    if (!p||!p->next)
    {
        return ERROR;
    }

    next_e = p->next->data;
    return OK;
}

//功能：重载赋值运算符的定义

template <typename ElemType>
LinkList<ElemType> LinkList<ElemType>::operator =(LinkList<ElemType>rightL)
{
    NodePointer p =NULL;//指向新链表的最后一个元素的指针
    NodePointer rp =rightL.getHead();//rp为欲赋值链表的头指针
    NodePointer s = NULL;//指向新申请结点的指针

    if (this != &rightL)
    {
        clear();

        while (rp)
        {
            s =new LinkNode;
            assert(s!=0);
            s->data = rp->data;

            if (!head)
            {//如果头指针为空，则将头指针指向新结点
                head =s ;
            }
            else
                p->next = s;
            p =s;//将p指向新申请的结点
            rp = rp->next;//指针前移
        }
        if (p)
        {
            p->next = NULL
        }
    }
    return *this;


}


//功能：返回某结点（数据域为e）前驱的数据域

template <typename ElemType>
Status LinkList<ElemType>::priorElem(ElemType e,ElemType& prior_e)
{
    NodePointer r =NULL;//指向欲查找结点的前驱
    NodePointer p = head;//指向欲查找的结点


    while (p && !equal((p->data,e)))
    {
        r = p ;
        p = p->next;
    }

    if (!p || !r)
    {
        return ERROR;
    
    }
    prior_e = r->data;
    return OK;
}

//*************下面为系统自动调用的构造函数以及析构函数的实现****************************

//功能：非循环单链表构造函数
template <typename ElemType>
LinkList <ElemType>::LinkList()
{
    head = NULL;
}
//非循环单链表析构函数
template<typename ElemType>
LinkList<ElemType>::~LinkList()
{
    clear();
}

//功能：非循环单链表拷贝初始换构造函数
//类似赋值操作符
template <typename ElemType>
LinkList<ElemType>::LinkList(const LinkList& otherL)
{
     NodePointer p = NULL;//预指向当前非循环单链表当前结点的指针
     NodePointer op = otherL.head;
     NodePointer s = NULL;//预指向新结点的指针
     head =NULL;
     while(op)
     {
         s = new LinkNode;
         assert(s != 0);
         s->data = op->data;
         if (!head)
         {
             head = s;
         }
         else
             p->next = s;

         p=s;
         op=op->next;
     }
     if (head)
     {
         p->next = NULL;
     }
}
#endif

View Code

三、循环单链表结构

和非循环单链表的操纵基本一致，差别仅在于当前指针沿着链表滑动时，如何判断到达链表的结尾，其条件是否为空，该为是否与头指针相同。而且最后一个结点的指针域next设置为指向头结点。

///////////////////////////////////////////////////////////////////////
//////////////////循环单链表数据结构Ｃ＋＋声明（基类）//////////////////
///////////////////////////////////////////////////////////////////////
typedef int Status ;
template <typename ElemType>
class CircularLinkList
{
public:
    class LinkNode
    {
    public:
        ElemType data;
        LinkNode * next;
    };
    typedef LinkNode * NodePointer;

    //把循环单链表置空
    void clear();

    //删除第i个结点，头指针移至下一个结点

    Status deleteElem(int i ,ElemType& e);

    //取循环单链表第一个结点的数据域

    Status getHeadElem(ElemType& e);

    //判断循环单链表是否为空
    
    bool isEmpty();

    //把循环单链表的头指针后移至第i个结点

    Status moveHead(int i);

    //重载赋值运算符

    CircularLinkList<ElemType> operator= (CircularLinkList<ElemType>& rightL);

    //********************下面为系统自用调用的构造函数以及析构函数声明********

    //循环单链表构造函数

    CircularLinkList();

    //循环单链表析构函数

    virtual ~CircularLinkList();

    //循环单链表拷贝初始化函数

    CircularLinkList(const CircularLinkList& otherL);
protected:
    NodePointer  head;
};





/////////////////////////////////////////////////
///循环单链表的Ｃ＋＋实现
/////////////////////////////////////////////////

//功能：把循环单链表置空

template<typename ElemType>
void CircularLinkList<ElemType>::clear()
{
    NodePointer p;
    while(head !=head->next)
    {
        p=head->next;
        head->next = p->next;
        delete p;
    }
    delete head;
    head = NULL;
}
//功能：删除第i个结点，头指针移至其下一个结点
template<typename ElemType>
Status CircularLinkList<ElemType>::deleteElem(int i ,ElemType& e)
{
    int j =1;
    NodePointer r =NULL;
    NodePointer p =head;

    if (!head)
    {
        return ERROR;
    }

    while(j<i)
    {
        r = p;
        p=p->next;
        ++j;
    }

    e=p->data;
    //如果链表只有一个结点，则将head置空
    if (p == p->next)
    {
        head=NULL;
    }
    else
    {
        r->next = p->next;
        head = r->next;
    }
         delete p;
         return OK;
}


//功能：取循环单链表第一个结点的数据域

template<typename ElemType>
Status CircularLinkList<ElemType>::getHeadElem(ElemType& e)
{
    if (!head)
    {
        return ERROR;
    }
    e=head->data;
    return OK;
}
//功能：判断循环单链表是否为空
template<typename ElemType>
bool CircularLinkList<ElemType>::isEmpty()
{
    return (head?false:true);
}
//功能：把循环单链表的头指针移到第i个结点
template<typename ElemType>
Status CircularLinkList<ElemType>::moveHead(int i)
{
    int j= 1;
    NodePointer priorHead = head;
    //如果链表为空，返回错误
    if (!head)
    {
        return ERROR;
    }
    while(j<i)
    {
        head = head->next;
        ++j;
        //如果结点总数小于i，则返回错误
        if (head =priorHead)
        {
            return ERROR;
        }
    }
    return OK;
}
//功能：重载赋值运算符的定义
template<typename ElemType>
CircularLinkList<ElemType> CircularLinkList<ElemType>::operator =(CircularLinkList& rightL)
{
    NodePointer p =NULL;
    NodePointer rp = rightL.head;
    NodePointer s;
    if ( this!=&rightL )
    {
        clear();

    while (rp->next != rightL.head)
    {
        s =new LinkNode;
        assert(s!=0);

        s->data = rp->data;

        if (!head)
        {
            head =s;
        }
        else
        {
            p->next = s;
        }
        p= s;
        rp = rp->next;
    }
   if(head)
   {
       p->next = head;//最后一个结点的后继为头结点
   }
    }
    return *this;
} 



////////////////下面是系统自动调用的构造函数和析构函数//////////////
//功能：循环单链表构造函数

template <typename ElemType>
CircularLinkList <ElemType>::CircularLinkList()
{
    head = NULL;
}

//功能：循环单链表析构函数

template<typename ElemType>
CircularLinkList<ElemType>::~CircularLinkList()
{
    clear();
}
//功能：循环单链表拷贝初始化构造函数
template<typename ElemType>
CircularLinkList<ElemType>::CircularLinkList(const CircularLinkList& otherL)
{
    NodePointer p = NULL;

    NodePointer op = otherL.head;

    NodePointer s = NULL;

     head = NULL;
     

     while(op != otherL.head)
     {
         s =new(LinkNode);
         assert(s != 0);

         s->data = op->data;

         if (!head)
         {
             head = s;
         }
         else
             p->next = s;
         p=s;
         op = op->next;
     }
     if (head)
     {
         p->next = head;
     }
}

View Code

四、循环双链表结构

在循环单链表中，给每个结点增加一个指针域prior，用于指向其前驱结点，第一个结点的前驱指针prior指向最后一个结点，即为循环双链表。

#ifndef DOUBLELINKLIST_H
#define  DOUBLELINKLIST_H
typedef int Status;
#include <iostream>
using namespace std;

template <typename ElemType>
class DoubleLinkList
{
public:
    class LinkNode
    {
    public:
        ElemType data;
        LinkNode *next;
        LinkNode *prior;
    };
    //定义结点指针
    typedef LinkNode* NodePointer;
    //把循环双链表置空
    void clear();

    //删除循环双链表中数据域为e的第一个结点

    Status deleteElem(ElemType e);


    //取循环双链表的头指针
    NodePointer getHead();

    //求双循环链表中的结点个数

    Status getLength();

    //在第i个结点之前插入一个数据域为e的结点
    Status insert(int i ,ElemType e);

    //判断循环双链表是否为空

    bool isEmpty();

    //返回双循环链表中数据域为e的第i个结点的指针
    Status locataElem(ElemType find_e,NodePointer &r);
    //去双环双链表中第i个结点
   
    Status getElem(int i ,ElemType& e);

    //返回某结点的后继的数据域

    Status nextElem(ElemType e ,ElemType& next_e);

  //重载赋值运算符的定义

    DoubleLinkList<ElemType> operator = (DoubleLinkList<ElemType>& rightL);

    //返回某结点前驱的数据域

    Status priorElem(ElemType e,ElemType& prior_e);

///********************************下面是双循环链表的构造函数和析构函数 拷贝构造函数的声明*********

    //双循环链表的构造函数

    DoubleLinkList();

    //双循环链表的析构函数

    ~DoubleLinkList();

    //双循环链表的拷贝初始化构造函数

    DoubleLinkList(const DoubleLinkList &otherL);
    
protected:
    NodePointer head;
};
///******以下是双循环链表的Ｃ＋＋数据结构实现**********

//功能：将双循环链表置空
template<typename ElemType>
void DoubleLinkList<ElemType>::clear()
{
    NodePointer r = NULL;//指向欲删除结点的前驱
    NodePointer p = NULL;//指向欲删除的结点
    //如果链表为空，返回
    if (!head)
    {
        return;
    }
    //如果链表不为空，从头结点的prior开始，即最后一个结点开始回收结点，然后向前逐一回收结点。
    p = head->prior;
    while(p!=head)
    {
        r = p->prior;
        delete p;
        p=r;
    }
    delete p ;
    head = NULL;
}
//功能：删除双循环链表中数据域为e的第一个结点
template<typename ElemType>
Status DoubleLinkList<ElemType>::deleteElem(ElemType e)
{
    NodePointer p =head;
    //如果不存在数据为e的结点，返回错误
    if (!locataElem(e,p))
    {
        return ERROR;
    }
    else
    {
        if (p == head)
        {
            head = p->next;
        }
        //断掉p
        p->prior->next = p->next;
        p->next->prior = p->prior;
    }
    delete p ;
    return OK;
}



//功能：取循环双链表第i个结点的数据域

template<typename ElemType>
Status DoubleLinkList<ElemType>::getElem(int i ,ElemType& e)
{
    int j =1;

    NodePointer p =head;
    while(p && p->next != head && j<i)
    {
        p = p->next;
        ++j;
    }
    if (j == i)
    {
        e = p->data;
        return OK;
    }
    return ERROR;

}
//功能：取循环双链表的头指针
template<typename ElemType>
typename DoubleLinkList<ElemType>::NodePointer DoubleLinkList<ElemType>::getHead()
{
    return head;
}
//功能：求循环双链表中结点的个数
template<typename ElemType>
int DoubleLinkList<ElemType>::getLength()
{
    NodePointer p =head;
    int length = 0;
    while (p)
    {
        ++length;
        p = p->next;
        if (p==head)
        {
            break;
        }
    }
    return length;
}
//在第i个结点之前插入一个数据域为e的结点
template <typename ElemType>
Status DoubleLinkList<ElemType>::insert(int i,ElemType e)
{
    int j =1;
    NodePointer p = head;
    NodePointer s =NULL;

    while(p && p->next!= head && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!head && i!=1 || j<i)
    {
        return ERROR;
    }

    s = new(LinkNode);
    assert(s != NULL);

    s->data = e;

    if (i = =1)
    {
        if (!head)
        {
            head = s->prior = s->next =s;
            return OK;
        }
        head = s;
    }
    p->prior->next = s;
    s->prior = p->prior;
    p->prior = s;
    s->next = p;
    return OK;
}

//功能：判断双循环链表是否为空
template <typename ElemType>
bool DoubleLinkList<ElemType>::isEmpty()
{
    return (head?false::true);
}
//功能：返回循环双链表中数据域为e的第一个节点的指针
template <typename ElemType>
Status DoubleLinkList<ElemType>::locataElem(ElemType find_e,NodePointer &r)
{
    NodePointer p = head;

    while(p && p->data!=find_e && p->next != head)
    {
        p=p->next;
    }
    if (p->data == find_e)
    {
        r = p;
        return OK;
    }
    else
    {
        return ERROR;
    }
}

//功能：返回某结点后继的数据域
template<typename ElemType>
Status DoubleLinkList<ElemType>::nextElem(ElemType e ,ElemType& next_e)
{
    NodePointer p = NULL;
    if (locataElem(e,p))
    {
        next_e = p->next->data;
        return OK;
    }
    else
    {
        return ERROR;
    }
}
//功能：重载赋值运算符的定义
template<typename ElemType>
DoubleLinkList<ElemType> DoubleLinkList<ElemType>::operator = (DoubleLinkList<ElemType>& rightL)
{
    NodePointer p = NULL;
    NodePointer rp = rightL.head;
    NodePointer s = NULL;

    if (this != &rightL)
    {
        clear();
         
        while(rp->next != rp.head)
        {
            s = new LinkNode;

            assert(s != NULL);

            s->data = rp->data;

            if (!head)
            {
                head = p = s;

            }

            p->next =s;
            s->prior =p;

            p=s;
            rp = rp->next;
        
        }
        //设置头指针指向前驱指向最后一个结点，最后一个结点的后继指向第一个结点
        if (head)
        {
            head->prior = p;
            p->next = head;
        }
    }
    return *this;
}


//功能：返回某结点前驱的数据域
template<typename ElemType>
Status DoubleLinkList<ElemType>::priorElem(ElemType e,ElemType& prior_e)
{
    NodePointer p = NULL;
    if (locataElem(e,p))
    {
        prior_e = p->prior->data;
        return OK;

    }
    else
        return ERROR;
}
//***************************下面为系统自动调用的构造函数、析构函数、拷贝初始化函数*********************

//功能：循环双链表构造函数

template <typename ElemType>
DoubleLinkList<ElemType>::DoubleLinkList()
{
    head =NULL;
}

template<typename ElemType>
DoubleLinkList<ElemType>::~DoubleLinkList()
{
    clear();
}

template<typename ElemType>
DoubleLinkList<ElemType>::DoubleLinkList(const DoubleLinkList& otherL)
{
    NodePointer p = NULL;
    NodePointer op = otherL.head;

    NodePointer s = NULL;

    head = NULL;

    while(op->next != otherL.head)
    {
        s= new LinkNode;
        assert(s != NULL);
        s->data = op->data;

        if (!head)
        {
            head = p =s;
        }

        p->next = s;
        s->prior = p;

        p=s;
         op=op->nxet;
    
    }
    if (head)
    {
        head->prior = p;
        p->next = head; 
    }
}
#endif

View Code

数据结构之线性表---C++实现

推荐阅读