[数据结构与算法]c++ 数据结构 链表类（详解）

包含链表类的一些基本操作。

大二数据结构课后题，之后会慢慢更新更多操作。

还有许多方法写法不够简洁完善，会慢慢更新

完整代码在最后

首先是类的设计：

typedef int ElementType;

class LinkList

{

private:

 class Node

 {

    public:

    ElementType data;

    Node * next;

    Node():next(0) {}//默认构造函数

    Node(ElementType dataValue):data(dataValue), next(0){}//显值构造函数

 };

public:

 typedef Node * NodePointer;

 LinkList(){mySize = 0;first = 0;}   //构造函数

 LinkList(const LinkList & origList);//复制构造函数

 ~LinkList();  //析构函数

 //void release();

 const LinkList & operator=(const LinkList & rightSide); //赋值运算符重载

 bool empty();  //链表判空

 void insert(ElementType dataVal, int index); //在链表指定位置插入节点

 void erase(int index);  //删除链表中指定位置的节点

 NodePointer search(ElementType dataVal); //查找链表中指定值的节点

 void display(ostream & out) const;//输出链表节点值

 void input(istream & in,int n);

 int nodeCount();   //计算节点个数

 void reverse();      //链表反转，即尾结点变为链表第一个节点

 bool ascendingOrder();  //判断链表是否为升序排列

 void ListMerge(LinkList & templist);//链表B合并到链表A末尾

 void MergeList(LinkList & listA,LinkList & listB);//链表A和链表B合并到链表C上

 ElementType get(NodePointer temp); 

private:

 NodePointer first; //指向第一个节点的指针

 int mySize; //节点的数目

};

方法的实现：

1.拷贝构造函数：

LinkList::LinkList(const LinkList & origList){//拷贝函数
   mySize = origList.mySize;
   first = 0;
   if(mySize == 0)return;
   NodePointer origPtr,lastPtr;
   first = new Node(origList.first->data);
   lastPtr = first;
   origPtr = origList.first->next;
   while(origPtr != 0){
      lastPtr->next = new Node(origPtr->data);
      origPtr = origPtr->next;
      lastPtr = lastPtr->next;
   }

}

LinkList::~LinkList(){//析构函数
   NodePointer prev = first,ptr;
   while(prev != 0){
      ptr = prev->next;
      delete prev;
      prev = ptr;
   }
}

2.empty函数：

bool LinkList::empty(){//判断是否为空
   if(!mySize)return true;
   return false;
}

3.insert插入节点

void LinkList::insert(ElementType dataVal, int index){//在index位置插入dataVal
   if(index < 0 || index > mySize){
      cerr << "illegal to insert--" << index << endl;
      return; 
   }
   mySize++;
   NodePointer newPtr = new Node(dataVal),prePtr = first;
   if(index == 0){//插入到第一个位置
      newPtr->next = first;
      first = newPtr;
   }
   else{//若列表不为空
      for(int i = 0;i < index-1;i++){//不断移动插入，移动index-1次，即插入到所需位置
         prePtr = prePtr->next;
      }
      newPtr->next = prePtr->next; 
      prePtr->next = newPtr;
   }
}

4.erase 删除节点

void LinkList::erase(int index){//删除第index个节点
   if(index < 0 || index >= mySize || empty()){
      cerr << "illegal to erase--" << index << endl;
      return; 
   }
   mySize--;
   NodePointer prePtr = first;
   if(mySize==1){//若只有一个节点
      first = 0;
   }
   else{
      if(index == 0){
         first = prePtr->next;
         delete prePtr;
         return;
      }
      for(int i = 1;i < index-1;i++)//删除index节点，只需移动到index-1位置
        prePtr = prePtr->next;
      prePtr->next = prePtr->next->next;//将prePtr的next连接至下下个节点
   }
}

5.查找指定数据的指定节点（注意最前面NodePointer要声明是Linklist里的）

LinkList::NodePointer LinkList::search(ElementType dataVal){//查找链表中指定值的节点
   if(empty()){
      cerr << "illegal to search--" << dataVal << endl;
   }
   NodePointer prePtr = first;
   while(prePtr->data != dataVal)
      prePtr = prePtr->next;
   if(prePtr==0)
      cerr << "illegal to search--" << dataVal << endl;
   else
      return prePtr;
}

6.display输出链表节点值，与输出重载相结合使用

void LinkList::display(ostream & out) const{//输出链表节点值
   NodePointer prePtr = first;
   while(prePtr != 0){
      out<<prePtr->data<<" ";
      prePtr = prePtr->next;
   }
}

7.input输入流函数，与提取重载相结合使用

void LinkList::input(istream & in,int n){//输入链表节点值
   int mysize1 = 0;
   for(int i = 0;i < n;i++){
      cout<<"请输入第"<<i+1<<"个节点的数据:";
      ElementType x;
      in>>x;
      insert(x,mysize1);
   }
}

8.nodeCount计算共有几个节点

int LinkList::nodeCount(){   //计算节点个数
   return mySize;
}

9.reverse反转函数

void LinkList::reverse(){//链表反转，即尾结点变为链表第一个节点
   NodePointer old_head = first,new_head=0,temp;
   while(old_head){
      temp = old_head->next;
      old_head->next = new_head;
      new_head =old_head;
      old_head = temp;
   }
   first = new_head;
}

10.判断是否递增

bool LinkList::ascendingOrder(){//判断链表是否为升序排列
   NodePointer prePtr = first;
   while(prePtr->next != 0){
      if(prePtr->data > prePtr->next->data)return false;
      prePtr = prePtr->next;
   }
   return true;
}

11.把B合并进A，且B不变，两个指针同时递增，B中每个节点拷贝一个，防止B发生改变

void LinkList::ListMerge(LinkList & templist){//链表B合并到链表A末尾
   NodePointer prePtr = first;
   while(prePtr->next != 0)
      prePtr = prePtr->next;
   NodePointer prePtrB = templist.first;
   while(prePtrB != 0){
      this->mySize++;
      prePtr->next = new Node(prePtrB->data);
      prePtrB = prePtrB->next;
      prePtr = prePtr->next;
   }
}

12.把A，B合并，再接到C（本身）

void LinkList::MergeList(LinkList & listA,LinkList & listB){//链表A和链表B合并到链表C上
   listA.ListMerge(listB);
   this->ListMerge(listA);
}

13.get函数

ElementType LinkList::get(NodePointer temp){
   return temp->data;
}

14.插入运算符重载

ostream & operator<<(ostream & out, const LinkList &List){ //插入运算符重载（可选做）
   List.display(out);
   return out;
}

15.提取运算符重载

istream & operator>>(istream & in, LinkList &List){//提取运算符重载（可选做）
   cout<<"请输入链表节点的个数:";
   int N;
   cin >> N;
   List.input(in,N);
   return in;
}

16.赋值重载符：

LinkList const &LinkList::operator=(const LinkList &rightSide) //赋值运算符重载
{
    mySize = rightSide.mySize;
    first=0;
    NodePointer origPtr,lastPtr;
    first = new Node(rightSide.first->data);
    lastPtr = first;
    origPtr = rightSide.first->next;
    while (origPtr != 0)
    {
        lastPtr->next = new Node(origPtr->data);
        origPtr= origPtr->next;
        lastPtr = lastPtr->next;
    }
    return *this;
}

完整code（含测试）：

#include<iostream>
using namespace std;
typedef int ElementType;

class LinkList

{

private:

 class Node

 {

    public:

    ElementType data;

    Node * next;

    Node():next(0) {}//默认构造函数

    Node(ElementType dataValue):data(dataValue), next(0){}//显值构造函数

 };

public:

 typedef Node * NodePointer;

 LinkList(){mySize = 0;first = 0;}   //构造函数

 LinkList(const LinkList & origList);//复制构造函数

 ~LinkList();  //析构函数

 //void release();

 const LinkList & operator=(const LinkList & rightSide); //赋值运算符重载

 bool empty();  //链表判空

 void insert(ElementType dataVal, int index); //在链表指定位置插入节点

 void erase(int index);  //删除链表中指定位置的节点

 NodePointer search(ElementType dataVal); //查找链表中指定值的节点

 void display(ostream & out) const;//输出链表节点值

 void input(istream & in,int n);

 int nodeCount();   //计算节点个数

 void reverse();      //链表反转，即尾结点变为链表第一个节点

 bool ascendingOrder();  //判断链表是否为升序排列

 void ListMerge(LinkList & templist);//链表B合并到链表A末尾

 void MergeList(LinkList & listA,LinkList & listB);//链表A和链表B合并到链表C上

 ElementType get(NodePointer temp); 

private:

 NodePointer first; //指向第一个节点的指针

 int mySize; //节点的数目

};

LinkList::LinkList(const LinkList & origList){//拷贝函数
   mySize = origList.mySize;
   first = 0;
   if(mySize == 0)return;
   NodePointer origPtr,lastPtr;
   first = new Node(origList.first->data);
   lastPtr = first;
   origPtr = origList.first->next;
   while(origPtr != 0){
      lastPtr->next = new Node(origPtr->data);
      origPtr = origPtr->next;
      lastPtr = lastPtr->next;
   }

}

LinkList::~LinkList(){//析构函数
   NodePointer prev = first,ptr;
   while(prev != 0){
      ptr = prev->next;
      delete prev;
      prev = ptr;
   }
}

bool LinkList::empty(){//判断是否为空
   if(!mySize)return true;
   return false;
}

LinkList const &LinkList::operator=(const LinkList &rightSide) //赋值运算符重载
{
    mySize = rightSide.mySize;
    first=0;
    NodePointer origPtr,lastPtr;
    first = new Node(rightSide.first->data);
    lastPtr = first;
    origPtr = rightSide.first->next;
    while (origPtr != 0)
    {
        lastPtr->next = new Node(origPtr->data);
        origPtr= origPtr->next;
        lastPtr = lastPtr->next;
    }
    return *this;
}
void LinkList::insert(ElementType dataVal, int index){//在index位置插入dataVal
   if(index < 0 || index > mySize){
      cerr << "illegal to insert--" << index << endl;
      return; 
   }
   mySize++;
   NodePointer newPtr = new Node(dataVal),prePtr = first;
   if(index == 0){//插入到第一个位置
      newPtr->next = first;
      first = newPtr;
   }
   else{//若列表不为空
      for(int i = 0;i < index-1;i++){//不断移动插入，移动index-1次，即插入到所需位置
         prePtr = prePtr->next;
      }
      newPtr->next = prePtr->next; 
      prePtr->next = newPtr;
   }
}

void LinkList::erase(int index){//删除第index个节点
   if(index < 0 || index >= mySize || empty()){
      cerr << "illegal to erase--" << index << endl;
      return; 
   }
   mySize--;
   NodePointer prePtr = first;
   if(mySize==1){//若只有一个节点
      first = 0;
   }
   else{
      if(index == 0){
         first = prePtr->next;
         delete prePtr;
         return;
      }
      for(int i = 1;i < index-1;i++)//删除index节点，只需移动到index-1位置
        prePtr = prePtr->next;
      prePtr->next = prePtr->next->next;//将prePtr的next连接至下下个节点
   }
}

LinkList::NodePointer LinkList::search(ElementType dataVal){//查找链表中指定值的节点
   if(empty()){
      cerr << "illegal to search--" << dataVal << endl;
   }
   NodePointer prePtr = first;
   while(prePtr->data != dataVal)
      prePtr = prePtr->next;
   if(prePtr==0)
      cerr << "illegal to search--" << dataVal << endl;
   else
      return prePtr;
}

void LinkList::display(ostream & out) const{//输出链表节点值
   NodePointer prePtr = first;
   while(prePtr != 0){
      out<<prePtr->data<<" ";
      prePtr = prePtr->next;
   }
}

void LinkList::input(istream & in,int n){//输入链表节点值
   int mysize1 = 0;
   for(int i = 0;i < n;i++){
      cout<<"请输入第"<<i+1<<"个节点的数据:";
      ElementType x;
      in>>x;
      insert(x,mysize1);
      mysize1++;
   }
}

int LinkList::nodeCount(){   //计算节点个数
   return mySize;
}

void LinkList::reverse(){//链表反转，即尾结点变为链表第一个节点
   NodePointer old_head = first,new_head=0,temp;
   while(old_head){
      temp = old_head->next;
      old_head->next = new_head;
      new_head =old_head;
      old_head = temp;
   }
   first = new_head;
}

bool LinkList::ascendingOrder(){//判断链表是否为升序排列
   NodePointer prePtr = first;
   while(prePtr->next != 0){
      if(prePtr->data > prePtr->next->data)return false;
      prePtr = prePtr->next;
   }
   return true;
}

void LinkList::ListMerge(LinkList & templist){//链表B合并到链表A末尾
   NodePointer prePtr = first;
   while(prePtr->next != 0)
      prePtr = prePtr->next;
   NodePointer prePtrB = templist.first;
   while(prePtrB != 0){
      this->mySize++;
      prePtr->next = new Node(prePtrB->data);
      prePtrB = prePtrB->next;
      prePtr = prePtr->next;
   }
}

void LinkList::MergeList(LinkList & listA,LinkList & listB){//链表A和链表B合并到链表C上
   listA.ListMerge(listB);
   this->ListMerge(listA);
}

ElementType LinkList::get(NodePointer temp){
   return temp->data;
}
ostream & operator<<(ostream & out, const LinkList &List){ //插入运算符重载（可选做）
   List.display(out);
   return out;
}

istream & operator>>(istream & in, LinkList &List){//提取运算符重载（可选做）
   cout<<"请输入链表节点的个数:";
   int N;
   cin >> N;
   List.input(in,N);
   return in;
}

int main(){
   LinkList l;
   LinkList l2;
   cin>>l;
   LinkList l1(l);
   l2 = l;
   cout<<l2<<endl;
   cout<<l<<endl;
   l.reverse();
   cout<<l<<endl;
   cout<<l.nodeCount()<<endl;
   l.ListMerge(l1);
   cout<<l<<endl;
   cout<<l.nodeCount()<<endl;
   l.erase(4);
   cout<<l<<endl;
   l.insert(10,7);
   cout<<l<<endl;
   if(l.ascendingOrder())cout<<"递增"<<endl;
   else cout<<"不递增"<<endl;
   if(l.empty())cout<<"空链表"<<endl;
   else cout<<"非空链表"<<endl;
   return 0;
}