数据结构学习----单向链表类

宫庆义

浏览: 17313 次
性别:
来自: 北京

最近访客更多访客>>

maofujun

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

数据结构与算法

数据结构

图1 链表示意图

图2 链表元素的添加

图3 链表元素的删除



带附加头结点的单链表类. 同时具有栈, 队列, 双端队列的功能

#include <stdio.h>   
#include <stdlib.h>   
#include <iostream>   
using namespace std;   
  
#pragma once   
void Error(string error)   
{   
    cout<<error<<endl;   
    system("pause");   
    exit(1);   
}   
  
    
#pragma region   
//单链表类   
//测试日期 2010-3-3   
#ifndef LINKNODE_H   
#define LINKNODE_H   
template<class T>   
class LinkNode   
{   
public:   
    T data;                                           //数据域   
    LinkNode<T> *next;                                //链指针   
    LinkNode(LinkNode<T> *p=NULL){next=p;}            //仅初始化指针成员的构造函数   
    LinkNode(T item,LinkNode<T> *p=NULL)              //初始化数据与指针成员的构造函数   
    { data=item;next=p;}     
};   
#endif   
  
#ifndef LINKLIST_H   
#define LINKLIST_H   
template<class T>   
class LinkList    
{   
private:   
    LinkNode<T> *head;                                //链表的头指针   
    LinkNode<T> *current;                             //当前结点指针   
    int size;                                         //链表长度   
public:   
    LinkList(){current=head=new LinkNode<T>();size=0;}//构造函数   
    ~LinkList(){ClearList();}                         //析构函数   
    void ClearList();                                 //将链表置为空表    
    int Size()const{return size;}                     //返回链表的长度    
  
    LinkNode<T>* GetItem(int pos);                    //取得第pos个元素的地址[pos从0开始]   
  
    void PushFront(T data);                           //在链表首部添加元素   
    void PushBack(T data);                            //在链表尾部添加元素   
    T PopFront();                                     //删除头节点    
    T PopBack();                                      //删除尾节点    
  
    LinkNode<T>* GetCurrent();                        //返回当前结点指针   
    LinkNode<T>* SetCurrent(int pos);                 //令current指向第i个结点  
  
  
    LinkNode<T>* Next();                              //令current指向当前结点的后一个结点   
    LinkNode<T>* Previous();                          //令current指向当前结点的前一个结点   
  
    T GetData(int pos);                               //取得第pos个表项的值   
    void SetData(int pos,T data);                     //修改第pos个表项的值为x   
    void Insert(int pos,T data);                      //在位置pos处插入x   
    T Delete(int pos);                                //删除第pos个表项    
    void Reverse();                                   //链表反向   
  
    bool IsEmpty()const;                              //判断表是否为空   
  
    LinkList<T>& operator=(LinkList<T>& list);        //运算符重载    
};   
#endif   
#pragma endregion   
  
#pragma region   
template<class T>   
void LinkList<T>::ClearList()   
{   
    LinkNode<T>* node;   
    while(head->next!=NULL)   
    {   
        node=head->next;   
        head->next=node->next;   
        delete node;   
    }   
    node=NULL;   
    size=0;   
}   
  
template<class T>   
LinkNode<T>* LinkList<T>::GetItem(int pos)   
{   
    if(pos<-1||pos>=size)   
        return NULL;   
    LinkNode<T>* node=head;   
    int k=0;   
    while(k<=pos)   
    {   
        node=node->next;   
        k++;   
    }   
    return node;   
}   
  
template<class T>   
void LinkList<T>::PushFront(T data)   
{   
    LinkNode<T> *node=new LinkNode<T>(data);   
    node->next=head->next;   
    head->next=node;   
    size++;   
}   
  
template<class T>   
void LinkList<T>::PushBack(T data)   
{   
    LinkNode<T> *node=new LinkNode<T>(data);   
    GetItem(size-1)->next=node;   
    size++;   
}   
  
template<class T>   
T LinkList<T>::PopFront()   
{   
    LinkNode<T> *node=head->next;   
    if(node!=NULL)   
    {   
        T data=node->data;   
        head->next=node->next;   
        size--;   
        delete node;   
        node=NULL;   
        return data;   
    }   
    else  
    {   
        Error("弹出数据出错!");   
    }   
}   
  
template<class T>   
T LinkList<T>::PopBack()   
{   
    LinkNode<T> *node1=GetItem(size-2);   
    if(node1!=NULL)   
    {   
        LinkNode<T> *node2=node1->next;   
        T data=node2->data;   
        node1->next=NULL;   
        size--;   
        delete node2;   
        node2=NULL;   
        return data;   
    }   
    else  
    {   
        Error("弹出数据出错!");   
    }   
}   
  
template<class T>   
LinkNode<T>* LinkList<T>::GetCurrent()   
{ return current;}   
  
template<class T>   
LinkNode<T>* LinkList<T>::SetCurrent(int pos)   
{   
    LinkNode<T>* node=GetItem(pos);   
    if(node!=NULL)   
    {   
        current=node;    
        return current;   
    }   
    else  
        Error("当前指针不能为空!");   
}   
  
template<class T>   
LinkNode<T>* LinkList<T>::Next()   
{   
    if(current->next!=NULL)   
    {   
        current=current->next;   
        return current;   
    }   
    else  
        Error("当前指针不能为空!");   
}   
  
template<class T>   
LinkNode<T>* LinkList<T>::Previous()   
{   
    if(current==head)   
        Error("当前指针不能为空!");   
    LinkNode<T> *node=head;   
    while(node->next!=current)   
    {   
        node=node->next;   
    }   
    current=node;   
    return current;    
}   
  
template<class T>   
T LinkList<T>::GetData(int pos)   
{    
    if(pos<0||pos>=size)    
        Error("索引越界!");    
    LinkNode<T>* node=GetItem(pos);   
    if(node==NULL)    
        Error("取值出错!");    
    else  
        return node->data;   
}   
  
template<class T>   
void LinkList<T>::SetData(int pos, T data)   
{   
    if(pos<0||pos>=size)   
        Error("索引越界!");   
    LinkNode<T>* node=GetItem(pos);   
    if(node==NULL)    
        Error("赋值出错!");    
    else  
        node->data=data;   
}   
  
template<class T>   
void LinkList<T>::Insert(int pos, T data)   
{   
    if(pos<0||pos>size)   
        Error("索引越界!");   
    LinkNode<T>* node=GetItem(pos-1);   
    if(node==NULL)   
        Error("添加数据出错!");   
    LinkNode<T>* newNode=new LinkNode<T>(data);   
    if(newNode==NULL)    
        Error("内存分配错误!");    
    newNode->next=node->next;   
    node->next=newNode;   
    size++;   
}   
  
template<class T>   
T LinkList<T>::Delete(int pos)   
{   
    if(pos<0||pos>=size)   
        Error("索引越界");   
    LinkNode<T> *node1,*node2;   
    node1=GetItem(pos-1);   
    node2=node1->next;   
    node1->next=node2->next;   
    T data=node2->data;   
    delete node2;   
    node2=NULL;   
    size--;   
    return data;     
}   
  
template<class T>   
void LinkList<T>::Reverse()   
{   
   LinkNode<T> *next,*pre,*cur;   
   if(head->next==NULL||head->next->next==NULL) return;   
   pre=head->next;   
   cur=pre->next;   
   next=NULL;   
   while(cur->next!=NULL)   
   {   
      next=cur->next;   
      cur->next=pre;   
      pre=cur;   
      cur=next;   
   }   
   cur->next=pre;   
   head->next=cur;   
}   
  
template<class T>   
bool LinkList<T>::IsEmpty() const  
{      
    return (size==0)?true:false;    
}   
  
template<class T>   
LinkList<T>& LinkList<T>::operator =(LinkList<T> &list)   
{    
    T data;   
    LinkNode<T> *src=list.GetItem(-1);    
    LinkNode<T> *des=head;   
    while(src->next!=NULL)   
    {   
        data=src->next->data;   
        des->next=new LinkNode<T>(data);   
        des=des->next;   
        src=src->next;   
        size++;   
    }   
    return *this;    
}   
#pragma endregion