单链表(C++达成)

单链表(C++实现),单链表实现

单链表的结构有多种

这里介绍的链表有头结点、有尾节点并且尾节点指向头结点

图片 1

 

单链表的每个结点的地址存放在其直接前驱结点的指针域中。其中第一个结点没有前驱结点,因此需要一个头指针指向第一个节点,便于我们对整个链表进行操作;这里的单链表的最后一个节点的指针域存放的是头结点的地址。

单链表不能随意存取,必要的时候我们可以通过已知结点的指针域不断遍历从而获取我们要的结点。

SList.h

/****************************************************************************************************/
/*
功能:应用C++语言实现单链表的各项操作
    建立链表的节点类LinkNode,封装一个SList类将有效节点链接起来
基本的成员函数:
           构造函数、拷贝构造函数、赋值运算符的重载、析构函数
**
**单链表的具体操作:
**                  1:在尾部插入节点
**                  2:打印单链表
**                  3:链表置空
**                  4:尾除尾节点
**                  5:头插
**                  6:删除首节点
**                  7:固定位置插入一个节点
**                  8:删除某一节点
**                  9:查找某节点并返回这个节点的位置
**                10:计算链表节点的数目
**             11:查找某节点并删除
**             12:删除链表中所有的x
**             13:去重
**             14:合并两个链表
**             15:冒泡排序
**             16:翻转单链表
**
**                                                             By :Lynn-Zhang
**
*/
/*****************************************************************************************************/
//****************/

typedef int DataType;

//节点类(复合形态)
//struct LinkNode     
//{
//  friend class SList;      //将SList设为友元,便于SList类可以访问节点类的私有成员
//public:
//  LinkNode(const DataType x);  
//private:
//  DataType _data;    //节点的数据
//  LinkNode* _next;    //指向该节点的下一个节点
//};

//直接用struct定义LinkNode类,因为struct的成员默认为公有数据成员,所以可直接访问
struct LinkNode      //节点类(建议写法)
{
    LinkNode(const DataType x);
    DataType _data;    //节点的数据
    LinkNode* _next;    //指向该节点的下一个节点
};
class SList
{
public:
    SList();         //构造函数
    SList(const SList& s);        //拷贝构造
    SList &operator=(SList& s);    //赋值运算符的重载
    ~SList();

public:   
        //单链表的具体操作
    void Uniqe();         //去重
    void Merge(SList &s);  //合并
    void Sort();       //冒泡
    void Reverse();   //翻转
    void Swap(SList& s);      //交换
    void PrintSList();   //打印链表
    void PushBack(const DataType& x);    //在尾部插入一个节点
    void Clear();         //链表置空
    void PopBack();       //删除尾节点
    void PushFront(DataType x);  //头插
    void PopFront();    //删除首节点
    void Insert(LinkNode* pos, DataType x);//固定位置插入一个节点
    void Erase(LinkNode* pos);        //删除某一节点
    LinkNode* Find(DataType x);       //查找节点并返回这个节点的地址
    int Amount();   //计算链表节点的数目
    void Remove(DataType x);     //查找某节点并删除
    void RemoveAll(DataType x);      //删除链表中所有的x

private:   
    LinkNode* _head;     //指向头节点
    LinkNode* _tail;        //指向尾节点
};
//*********************//

SList.cpp   (函数实现)

//**********************/////////
#include<iostream>
using namespace std;
#include<assert.h>
#include"SList.h"

   LinkNode::LinkNode(const DataType x)
           :_data(x)
           , _next(NULL)
           {}

    SList::SList()         //构造函数
        :_head(NULL)
        , _tail(NULL)
    {}
    SList::SList(const SList& s)          //拷贝构造
        :_head(NULL)
        , _tail(NULL)
    {
        if (s._head == NULL)
        {
            return;
        }
        LinkNode* tmp = s._head;
        do{
            PushBack(tmp->_data);
            tmp = tmp->_next;
            } while (tmp != s._head);

    }
    //赋值运算符的重载(传统方法)
    //SList & SList::operator=(const SList& s)    
    //{
    //  if (this != &s)
    //  {
    //      _head = NULL;
    //      _tail = NULL;
    //      LinkNode* tmp = s._head;
    //  do{
    //      PushBack(tmp->_data);
    //      tmp = tmp->_next;
    //       } while (tmp != s._head);
    //  }
    //  return *this; 
    //}

    //赋值运算符的重载(高效写法)
    /*void SList::Swap(SList& s)     
    {
    swap(_head, s._head);
    swap(_tail, s._tail);

    }
    SList&  SList::operator=(SList &s)
    {
    if (this != &s)
    {
    SList tmp(s);
    Swap(tmp);
    }
    return *this;
    }*/

    SList&  SList::operator=(SList &s)     //赋值运算符的重载再优化(推荐写法)
    {
        if (this != &s)
        {
            swap(_head, s._head);
            swap(_tail, s._tail);
        }
        return *this;
    }
    SList::~SList()    //析构
    {
        Clear();
    }

        void SList::Reverse()   //链表逆置(利用头插新节点的方法)
    {
        if (_head == NULL||_head->_next==_tail)
        {
            return;
        }
        int ret = Amount();
        _tail = new LinkNode(_head->_data);
        LinkNode* begin=NULL;
        LinkNode* tmp = _tail;
        while (--ret)
        {
            LinkNode* del = _head;
            _head = _head->_next;
            delete del;    //这里不要忘记做清理工作,否则内存泄漏
            begin = new LinkNode(_head->_data);
            begin->_next = tmp;
            _tail->_next = begin;
            tmp = begin;
        }
        _head = begin;
    }  

        //打印链表
    void SList::PrintSList()  
    {
        //头结点为空时,无需打印链表
        if (_head==NULL)
        {
            cout << "This SList is Empty !" << endl;
            return;
        }
        else
        {
            LinkNode* tmp = _head;
            do{ 
                cout << tmp->_data << "-->";
                tmp = tmp->_next;
                } while (tmp != _head);
            cout << endl;
        }
    }
    void SList::PushBack(const DataType& x)    //在尾部插入一个节点
    {
        //如果链表为空,插入节点后只有一个节点,此时_head=_tail
        if (_head == NULL)
        {
            _head = new LinkNode(x);
            _tail = _head;
            _tail->_next = _head;
        }
        else
        {
            _tail->_next = new LinkNode(x);
            _tail = _tail->_next;
            _tail->_next = _head;
        }
    }
    void SList::Clear()         //链表置空
    {
        LinkNode* begin = _head;
        while (begin != _tail)
        {
            _head = _head->_next;
            delete begin;
            begin = _head;
        }
        _head = NULL;
        _tail = NULL;
    }
    void SList::PopBack()    //尾删
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
        }
        else if (_head == _tail)
        {
            delete _head;
            _head = NULL;
            _tail = NULL;
        }
        else
        {
            LinkNode* cur = _head;
            while (cur->_next != _tail)
            {
                cur = cur->_next;
            }
            delete _tail;
            _tail = cur;
            _tail->_next = _head;
         }
    }
    void SList::PushFront(DataType x)  //头插
    {
        if (_head == NULL)
        {
            PushBack(x);
        }
        else
        {
            LinkNode* tmp = _head;
            _head = new LinkNode(x);
            _head->_next = tmp;
            _tail->_next = _head;
        }
    }
    void SList::PopFront()    //删除首节点
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return;
        }
        LinkNode* tmp = _head;
        _head = _head->_next;
        _tail->_next = _head;
        delete tmp;
    }

    //固定位置插入一个节点(这个函数需和Find函数搭配使用)
    //先用Find函数找到新节点需要插入的位置
    //(将Find函数的返回值传给Insert函数的参数pos),再在pos节点后面插入新节点x
    void SList::Insert(LinkNode* pos, DataType x)
    {
        assert(pos);
        if (pos==_tail)
        {
            PushBack(x);
        }
        else
        {
            LinkNode* tmp = new LinkNode(x);
            tmp->_next = pos->_next;
            pos->_next = tmp;
        }
    }

        //删除某一节点,同样,要先找到该节点并传参给Erase函数
    void SList::Erase(LinkNode* pos)        
    {
        assert(pos);
        if (pos == _tail)
        {
            PopBack();
        }
        if (pos == _head)
        {
            PopFront();
        }
        else
        {
            LinkNode* prev = _head;
            while (prev->_next != pos)
            {
                prev = prev->_next;
            }
            prev->_next = pos->_next;
            delete pos;
        }
    }
    LinkNode* SList::Find(DataType x)       //查找节点并返回这个节点的地址
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return NULL;
        }
        else
        {
            LinkNode* tmp = _head;
            do{
                    if (tmp->_data == x)
                    {
                        return tmp;
                    }
                        tmp = tmp->_next;
            } while (tmp != _head);
            return NULL;
        }
    }
    int SList::Amount()   //计算链表节点的数目
    {
        if (_head == NULL)
        {
            return 0;
        }
        else
        {
            int count = 0;
            LinkNode* cur = _head;
            while (cur != _tail)
            {
                count++;
                cur = cur->_next;
            }
            return ++count;
        }
    }
    void SList::Remove(DataType x)      //查找某节点并删除
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
        }
        else
        {
            LinkNode* tmp = Find(x);
            if (tmp != NULL)
            {
                Erase(tmp);
            }
        }
    }
    void SList::RemoveAll(DataType x)       //删除链表中所有的x
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return;
        }
//如果链表不为空,设置left和right前后指针,从头至尾遍历一遍,delete节点的data为x的节点

            LinkNode* left = _tail;
            LinkNode* right = _head;
            int count = Amount();
            while (count--)
            {
             //当要删掉的节点是头节点时,需要注意头节点要指向它的下一个节点
             //当要删掉的节点是尾节点时,需要注意尾节点要指向它的上一个节点
             //当left和right指向同一块要删掉的节点时,将链表置空

                if (right->_data == x)
                {
                    if (_head == right)   
                    {
                        _head = _head->_next;
                    }
                    if (_tail == right)   
                    {
                        _tail =left;
                    }
                    if (right == left)    
                    {
                        _head = NULL;
                        _tail = NULL;
                        return;
                    }
                    LinkNode* tmp = right;
                    right = right->_next;
                    delete tmp;
                    left->_next = right;
                }
                else
                {
                    left = right;
                    right = right->_next;
                }
            }  
    }
    void SList::Uniqe()       //去重(针对有序链表)
    {
        assert(_head &&_head!= _tail);
        LinkNode* left = _head;
        LinkNode* right = _head->_next;
        while (left != _tail)
        {
            while(left->_data == right->_data)
            {
                LinkNode* tmp = right;
                right = right->_next;
                left->_next = right;
                delete tmp;
            }
            left = left->_next;
            right = right->_next;
        }
    }
    void SList::Merge(SList &s)    //合并(针对有序链表),合并后依然有序
    {
        //  1. _head为空
        //  2. 链表s为空
        if (_head == NULL)
        {
            _head = s._head;
            _tail = s._tail;
        }
        if (s._head == NULL)
        {
            return;
        }
        //  3. 两个链表都不为空
        LinkNode* phead = _head;
        if (phead->_data <= s._head->_data)
        {
            phead = phead->_next;
        }
        else
        {
            _head = s._head;
            s._head = s._head->_next;
        }
        LinkNode* cur = _head;
        while (1)
        {
            if (phead->_data <= s._head->_data)
            {
                _head->_next = phead;
                _head = _head->_next;
                if (phead == _tail)
                {
                    _head->_next = s._head;   
                    _tail=s._tail;
                    _tail->_next = cur;
                    break;
                }
                phead = phead->_next;
            }
            else
            {
                _head->_next = s._head;
                _head = _head->_next;
                if (s._head ==s._tail)
                {
                    _head->_next = phead;
                    _tail->_next = cur;
                    break;
                }
                s._head = s._head->_next;
            }

        }
        _head = cur;
    }
    void SList::Sort()                      //冒泡排序
    {
        assert(_head);
        if (_head == _tail)
        {
            return;
        }
        int size = Amount();
        for (int i = 0; i < size-1 ; i++)  
        {
            LinkNode* left = _head;
            LinkNode* right = _head->_next;
            for (int j = 0; j < size - i-1 ; j++)
            {              
                if (left->_data>right->_data)
                {
                    swap(left->_data, right->_data);
                }
                right = right->_next;
                left = left->_next;
            }      
        }
    }
///************************

测试用例(Test.cpp)

#include"SList.h"
#include<stdlib.h>

void Test3()
{
    //排序 去重 合并
    cout << "list 1:" << endl;
    SList list1;
  /*list1.PushBack(2);
    list1.PushBack(3);
    list1.PushBack(2);
    list1.PushBack(2);
    list1.PushBack(1);
    list1.PrintSList();
    list1.Sort();
    list1.PrintSList();
  list1.Uniqe();
    list1.PrintSList();*/

    list1.PushBack(5);
    list1.PushBack(3);
    list1.PushBack(8);
    list1.PushBack(2);
    list1.PushBack(9);
    list1.PushBack(10);
    list1.PushBack(2);
    list1.PushBack(2);
    list1.PushBack(1);
    list1.PrintSList();
    list1.Sort();
    list1.PrintSList();

    cout << "list 2:" << endl;
    SList list2;
    list2.PushBack(1);
    list2.PushBack(6);
    list2.PushBack(4);
    list2.PushBack(0);
    list2.PushBack(7);
    list2.PrintSList();
    list2.Sort();
    list2.PrintSList();

    cout << "list 1:" << endl<<endl;
    list1.Merge(list2);
    list1.PrintSList();
}
void Test2()
{
    SList list1;
    list1.PushBack(1);
    list1.PushBack(3);
    list1.PushBack(4);
    list1.PushBack(2);
    list1.PushBack(6);
    list1.PrintSList();

    /*list1.RemoveAll(2);
    list1.PrintSList();*/

    SList list2 = list1;
    /*list2.PushBack(2);
    list2.PushBack(3);
    list2.PushBack(4);
    list2.PushBack(2);
    list2.PushBack(2);*/
    list2.PrintSList();
    list2.Reverse();
    list2.PrintSList();

}
void Test1()
{
    //SList list1;
    //list1.PushBack(1);
    //list1.PushBack(2);
    //list1.PushBack(3);
    //list1.PushBack(4);
    //list1.PushBack(5);
    //list1.PrintSList();

    //list1.Remove(2);
    //list1.PrintSList();

    //int num =list1.Amount();
    //cout <<"节点个数:"<< num << endl;

    /*//检验Erase函数
    LinkNode* del = list1.Find(2);
    list1.Erase(del);
    list1.PrintSList();
    */

    /*//找到某节点并在其后插入新节点
    LinkNode* In =list1.Find(5);
    list1.Insert(In, 0);
    list1.PrintSList();*/

    /* //删除头结点
    list1.PopFront();
    list1.PrintSList();
    *//////

    /*//////查找节点
    LinkNode* ret=list1.Find(5);
    if (ret != NULL)
    {
    cout << "要查找的节点data是:" << ret->_data << endl;
    cout << "要查找的节点adress是:" <<ret<< endl;
    }
    else
    {
    cout << "not exit !" << endl;
    }*////////

    //验证构造函数
    //SList list2(list1);
    //list2.PrintSList();

    //验证赋值运算符的重载
    //SList list3 = list2;
    //list3.PrintSList();

    //验证析构函数
    //list3.Clear();
    //list3.PrintSList();

    //验证尾删和头插
    ///*list3.PopBack();
    //list3.PrintSList();*/
    //list3.PushFront(0);
    //list3.PrintSList();
}

int main()
{
    //Test1();
    Test2();
    system("pause");
}

  本文利用C++语言,在Windows平台 Visual Studio 2013开发环境下实现

 

单链表的结构有多种
这里介绍的链表有头结点、有尾节点并且尾节点指向头结点
单链表的每个结点的地址…

单链表的结构有多种

线性表之单链表C++实现,线性单链

    **线性表之单链表**

一、头文件:LinkedList.h

//单链表是用一组任意的存储单元存放线性表的元素,这组单元可以是连续的也可以是不连续的,甚至可以是零散分布在内存中的任意位置。
//单链表头文件
#include<iostream>
using namespace std;
//定义单链表结点-结构体类型
template<class DataType>
struct Node
{
  //数据域,存放该结点的数据
  DataType data;
  //指针域,指向下一个结点
  Node<DataType> *next;
};

template<class DataType>
class LinkedList{
public:
  //单链表无参构造器
  LinkedList();
  //单链表有参构造器
  LinkedList(DataType array[], int n);
  LinkedList(int n, DataType array[]);
  //单链表析构函数
  ~LinkedList();
  //获取单链表的长度
  int GetLength();
  //查找单链表指定元素的序号
  int GetLocal(DataType x);
  //获取单链表指序号的元素
  DataType GetElement(int index);
  //单链表中在指定位置插入指定的元素
  void Insert(int index, DataType x);
  //在单链表中删除指定位置的元素
  DataType Delete(int index);
  //按序号输出单链表中的元素
  void PrintLinkedList();

private :
  //声明单链表的头指针
  Node<DataType> *first;
};

//实现单链表的无参构造函数
template<class DataType>
LinkedList<DataType>::LinkedList()
{
  first = new Node<DataType>;
  first->next = NULL;
}

//头插法建立单链表
template<class DataType>
LinkedList<DataType>::LinkedList(int n,DataType array[])
{
  //初始化一个空链表
  first = new Node<DataType>;
  first->next = NULL;
  for (int i = 0; i < n; i++)
  {
    //为每一个数组元素都申请新结点
    Node<DataType> *s = new Node<DataType>;
    //数组元素赋值给结点数据域
    s->data = array[i];
    //将结点插入到头结点之前
    s->next = first->next;
    first->next = s;

  }
}

//尾插法建立单链表
template<class DataType>
LinkedList<DataType>::LinkedList(DataType array[], int n)
{
  //生成头结点
  first = new Node<DataType>;
  //定义尾结点
  Node<DataType> *r = first;
  for (int i = 0; i < n; i++)
  {
    //为每一个数组元素申请一个结点
    Node<DataType> *s = new Node<DataType>;
    //把数组元素赋值给结点的数据域
    s->data = array[i];
    //将每一个结点追加到终端结点之后
    r->next = s;
    r = s;
  }
  //尾结点尾NULL
  r->next = NULL;
}

//实现单链表的析构函数
template<class DataType>
LinkedList<DataType>::~LinkedList()
{
  //声明工作指针
  Node<DataType> *q;
  while (first != NULL)
  {
    //暂存被释放的结点
    q = first;
    //让头指针指向要释放结点的下一个结点
    first = first->next;
    delete q;
  }
}

//实现单链表插入:在指定的位置插入指定的元素
template<class DataType>
void LinkedList<DataType>::Insert(int index, DataType x)
{
  //定义工作指针
  Node<DataType> *p = first->next;
  //定义计数器,初始值为0
  int count = 0;
  while (p != NULL &&count < index – 1)
  {
    //工作指针后移
    p = p->next;
    count ++;
  }
  //找到 index-1 的位置
  if (p == NULL)
  {
    throw “插入的位置有误”;
  }
  else
  {
    //申请一个新结点
    Node<DataType> *s;
    s= new Node<DataType>;
    //其数据域为 x
    s->data = x;
    //在新结点的指针域存放工作指针p的指针域
    s->next = p->next;
    //将结点s插入到p结点之后
    p->next = s;
  }
}

//实现单链表的按值查找,返回指定元素在单链表中的序号(如不存在,则返回0)
template<class DataType>
int LinkedList<DataType>::GetLocal(DataType x)
{
  //定义工作指针
  Node<DataType> *p = first->next;
  //定义计数器,初始值是1
  int count = 1;
  //查找序号所对应的位置
  while (p != NULL)
  {
    if (p->data == x)
    {
      return count;
    }
    //工作指针后移
    p = p->next;
    //计数器加1
    count++;
  }
  //如果找不到该元素,则返回0
  return 0;
}

//实现单链表按位查找,返回指定位置的元素
template<class DataType>
DataType LinkedList<DataType>::GetElement(int index)
{
  //定义工作指针
  Node<DataType> *p = first->next;
  //定义计数器,初始值是1
  int count = 1;
  //查找序号所对应的位置
  while (p != NULL&&count < index)
  {
    //工作指针后移
    p = p->next;
    //计数器加1
    count++;
  }
  //如果找到单链表的末尾,还找不到指定的位置,则抛出异常
  if (p == NULL)
  {
    throw “查找的位置有误”;
  }
  else
  {
    //当找到合适的位置时,返回该位置上的元素
    return p->data;
  }

}

//实现获取单链表的长度
template<class DataType>
int LinkedList<DataType>::GetLength()
{
  //定义计数器,用来计算单链表的长度
  int count = 0;
  //定义工作指针
  Node<DataType> *p = first->next;
  while (p != NULL)
  {
    p = p->next;
    count++;
  }
  return count;

}

//实现单链表的按序号输出元素
template<class DataType>
void LinkedList<DataType>::PrintLinkedList()
{
  //声明工作指针
  Node<DataType> *p;
  //初始化工作指针
  p = first->next;
  while(p != NULL)
  {
    cout << p->data << ” “;
    //工作指针向后移动
    p = p->next;
  }
  cout << endl;
}

//实现单链表的删除
template<class DataType>
DataType LinkedList<DataType>::Delete(int index)
{
  Node<DataType> *p = first->next;
  int count = 0;
  //查找第 index-1 位置结点
  while (p != NULL&&count < index – 1)
  {
    p = p->next;
    count++;
  }
  //如果能找到
  if (p == NULL || p->next == NULL)
  {
    throw “删除的位置有误”;
  }
  else
  {
    Node<DataType> *q = p->next;
    DataType x = q->data;
    p->next = q->next;
    delete q;
    return x;
  }
}

 二、测试线性表之单链表的源文件:TestLinkedList.cpp

 

#include<iostream>
#include “LinkedList.h”
using namespace std;
void show()
{
  cout << “—————————————” <<
endl;
}
int main()
{
  int array[] = { 1, 3, 5, 2, 7, 6, 9, 8, 10, 4};
  //声明单链表
  LinkedList<int> linkedList =
LinkedList<int>(10,array);
  cout << “输出单链表:” << endl;
  linkedList.PrintLinkedList();
  show();
  cout << “单链表的长度:” << linkedList.GetLength()
<< endl;
  cout << “单链表中第5个元素是:” <<
linkedList.GetElement(5) << endl;
  cout << “单链表中元素5的位置是:” <<
linkedList.GetLocal(5) << endl;
  show();
  cout << “在单链表的第5个位置上插入元素22” << endl;
  linkedList.Insert(5, 22);
  cout << “输出单链表:” << endl;
  linkedList.PrintLinkedList();
  cout << “单链表的长度:” << linkedList.GetLength()
<< endl;
  show();
  cout << “删除第5位置的元素” << endl;
  linkedList.Delete(5);
  cout << “输出单链表:” << endl;
  linkedList.PrintLinkedList();
  cout << “单链表的长度:” << linkedList.GetLength()
<< endl;
  show();
  return 0;
}

 

线性表之单链表
一、头文件:LinkedList.h
//单链表是用一组任意的存储单元存放线性表的元素,这组单元…

链表是一种线性表,但是并不是顺序存储,而是每个节点里面存储着下一个节点的指针,把存储数据元素的数据串链起来。图片 2

C++单链表的操作
2017-12-25


  1 // 单链表.cpp: 定义控制台应用程序的入口点。
  2 //Author:kgvito 
  3 //Date: 2017.12.25
  4 
  5 
  6 #include "stdafx.h"
  7 #include<iostream>
  8 using namespace std;
  9 
 10 typedef int DataType;
 11 #define Node ElemType
 12 #define ERROR NULL
 13 
 14 //构建一个节点类
 15 class Node                          
 16 {
 17 public:
 18     int data;     //数据域
 19     Node * next;  //指针域
 20 };
 21 
 22 //构建一个单链表类
 23 class LinkList                      
 24 {
 25 public:
 26     LinkList();                      //构建一个单链表;
 27     ~LinkList();                  //销毁一个单链表;
 28     void CreateLinkList(int n);   //创建一个单链表
 29     void TravalLinkList();        //遍历线性表
 30     int GetLength();              //获取线性表长度
 31     bool IsEmpty();               //判断单链表是否为空
 32     ElemType * Find(DataType data); //查找节点
 33     void InsertElemAtEnd(DataType data);            //在尾部插入指定的元素
 34     void InsertElemAtIndex(DataType data,int n);    //在指定位置插入指定元素
 35     void InsertElemAtHead(DataType data);           //在头部插入指定元素
 36     void DeleteElemAtEnd();       //在尾部删除元素
 37     void DeleteAll();             //删除所有数据
 38     void DeleteElemAtPoint(DataType data);     //删除指定的数据
 39     void DeleteElemAtHead();      //在头部删除节点
 40 private:
 41     ElemType * head;              //头结点
 42 };
 43 
 44 //初始化单链表
 45 LinkList::LinkList()                  
 46 {
 47     head = new ElemType;            
 48     head->data = 0;               //将头结点的数据域定义为0
 49     head->next = NULL;            //头结点的下一个定义为NULL
 50 }     
 51 
 52 //销毁单链表
 53 LinkList::~LinkList()
 54 {
 55     delete head;                 //删除头结点
 56 } 
 57 
 58 //创建一个单链表
 59 void LinkList::CreateLinkList(int n)
 60 {
 61     ElemType *pnew, *ptemp;
 62     ptemp = head;
 63     if (n < 0) {       //当输入的值有误时,处理异常
 64         cout << "输入的节点个数有误" << endl;
 65         exit(EXIT_FAILURE);
 66     }
 67     for (int i = 0; i < n;i++) {        //将值一个一个插入单链表中
 68         pnew = new ElemType;
 69         cout << "请输入第" << i + 1 << "个值: " ;
 70         cin >> pnew->data;
 71         pnew->next = NULL;          //新节点的下一个地址为NULL
 72         ptemp->next = pnew;         //当前结点的下一个地址设为新节点
 73         ptemp = pnew;               //将当前结点设为新节点
 74     }
 75 }
 76 
 77 //遍历单链表
 78 void LinkList::TravalLinkList()
 79 {
 80     if (head == NULL || head->next ==NULL) {
 81         cout << "链表为空表" << endl;
 82     }
 83     ElemType *p = head;                 //另指针指向头结点
 84     while (p->next != NULL)        //当指针的下一个地址不为空时,循环输出p的数据域
 85     {
 86         p = p->next;               //p指向p的下一个地址
 87         cout << p->data << " ";
 88     }
 89 }
 90 
 91 //获取单链表的长度
 92 int LinkList::GetLength()
 93 {
 94     int count = 0;                  //定义count计数
 95     ElemType *p = head->next;           //定义p指向头结点
 96     while (p != NULL)                //当指针的下一个地址不为空时,count+1
 97     {
 98         count++;                  
 99         p = p->next;                //p指向p的下一个地址
100     }
101     return count;                   //返回count的数据
102 }
103 
104 //判断单链表是否为空
105 bool LinkList::IsEmpty()
106 {
107     if (head->next == NULL) {                 
108         return true;
109     }
110     return false;
111 }
112 
113 //查找节点
114 ElemType * LinkList::Find(DataType data)
115 {
116     ElemType * p = head;
117     if (p == NULL) {                           //当为空表时,报异常
118         cout << "此链表为空链表" << endl;
119         return ERROR;
120     }
121     else
122     {
123         while (p->next != NULL)               //循环每一个节点
124         {
125             if (p->data == data) {
126                 return p;                     //返回指针域
127             }
128             p = p->next;
129         }
130         return NULL;                           //未查询到结果
131     }
132 }
133 
134 //在尾部插入指定的元素
135 void LinkList::InsertElemAtEnd(DataType data)
136 {
137     ElemType * newNode = new ElemType;    //定义一个Node结点指针newNode
138     newNode->next = NULL;         //定义newNode的数据域和指针域
139     newNode->data = data;
140     ElemType * p = head;              //定义指针p指向头结点
141     if (head == NULL) {           //当头结点为空时,设置newNode为头结点
142         head = newNode;
143     }
144     else                          //循环知道最后一个节点,将newNode放置在最后
145     {
146         while (p->next != NULL)
147         {
148             p = p->next;
149         }
150         p->next = newNode;
151     }
152 }
153 
154 //在指定位置插入指定元素
155 void LinkList::InsertElemAtIndex(DataType data,int n)
156 {
157     if (n<1 || n>GetLength())                   //输入有误报异常
158         cout << "输入的值错误" << endl;
159     else
160     {
161         ElemType * ptemp = new ElemType;        //创建一个新的节点
162         ptemp->data = data;                     //定义数据域
163         ElemType * p = head;                    //创建一个指针指向头结点
164         int i = 1;
165         while (n > i)                           //遍历到指定的位置
166         {
167             p = p->next;
168             i++;
169         }
170         ptemp->next = p->next;                 //将新节点插入到指定位置
171         p->next = ptemp;
172     }
173 }
174 
175 //在头部插入指定元素
176 void LinkList::InsertElemAtHead(DataType data)
177 {
178     ElemType * newNode = new ElemType;    //定义一个Node结点指针newNode
179     newNode->data = data;
180     ElemType * p = head;              //定义指针p指向头结点
181     if (head == NULL) {           //当头结点为空时,设置newNode为头结点
182         head = newNode;
183     }
184     newNode->next = p->next;          //将新节点插入到指定位置
185     p->next = newNode;
186 }
187 
188 //在尾部删除元素
189 void LinkList::DeleteElemAtEnd()
190 {
191     ElemType * p = head;          //创建一个指针指向头结点
192     ElemType * ptemp = NULL;      //创建一个占位节点
193     if (p->next == NULL) {        //判断链表是否为空
194         cout << "单链表空" << endl;
195     }
196     else
197     {
198         while (p->next != NULL)   //循环到尾部的前一个
199         {
200             ptemp = p;            //将ptemp指向尾部的前一个节点
201             p = p->next;          //p指向最后一个节点
202         }
203         delete p;                //删除尾部节点
204         p = NULL;
205         ptemp->next = NULL;
206     }
207 }
208 
209 //删除所有数据
210 void LinkList::DeleteAll()
211 {
212     ElemType * p = head->next;
213     ElemType * ptemp = new ElemType;
214     while (p != NULL)                    //在头结点的下一个节点逐个删除节点
215     {
216         ptemp = p;
217         p = p->next;
218         head->next = p;
219         ptemp->next = NULL;
220         delete ptemp;
221     }
222     head->next = NULL;                 //头结点的下一个节点指向NULL
223 }
224 
225 //删除指定的数据
226 void LinkList::DeleteElemAtPoint(DataType data)
227 {
228     ElemType * ptemp = Find(data);    //查找到指定数据的节点位置
229     if (ptemp == head->next) {        //判断是不是头结点的下一个节点,如果是就从头部删了它
230         DeleteElemAtHead();
231     }
232     else
233     {
234         ElemType * p = head;          //p指向头结点
235         while (p->next != ptemp)      //p循环到指定位置的前一个节点
236         {
237             p = p->next;
238         }
239         p->next = ptemp->next;         //删除指定位置的节点
240         delete ptemp;
241         ptemp = NULL;               
242     }
243 
244 }
245 
246 //在头部删除节点
247 void LinkList::DeleteElemAtHead()
248 {
249     ElemType * p = head;
250     if (p == NULL || p->next == NULL) {   //判断是否为空表,报异常
251         cout << "该链表为空表" << endl;
252     }
253     else
254     {
255         ElemType * ptemp = NULL;      //创建一个占位节点
256         p = p->next;
257         ptemp = p->next;              //将头结点的下下个节点指向占位节点
258         delete p;                     //删除头结点的下一个节点
259         p = NULL;
260         head->next = ptemp;           //头结点的指针更换
261     }
262 }
263 
264 //测试函数
265 int main()
266 {
267     LinkList l;
268     int i;
269     cout << "1.创建单链表   2.遍历单链表   3.获取单链表的长度   4.判断单链表是否为空   5.获取节点\n";
270     cout << "6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在头部插入指定元素\n";
271     cout<<"9.在尾部删除元素   10.删除所有元素   11.删除指定元素   12.在头部删除元素   0.退出" << endl;
272     do
273     {
274         cout << "请输入要执行的操作: ";
275         cin >> i;
276         switch (i)
277         {
278         case 1:
279             int n;
280             cout << "请输入单链表的长度: ";
281             cin >> n;
282             l.CreateLinkList(n);
283             break;
284         case 2:
285             l.TravalLinkList();
286             break;
287         case 3:
288             cout << "该单链表的长度为" << l.GetLength() << endl;
289             break;
290         case 4:
291             if (l.IsEmpty() == 1)
292                 cout << "该单链表是空表" << endl;
293             else
294             {
295                 cout << "该单链表不是空表" << endl;
296             }
297             break;
298         case 5:
299             DataType data;
300             cout << "请输入要获取节点的值: ";
301             cin >> data;
302             cout << "该节点的值为" << l.Find(data)->data << endl;
303             break;
304         case 6:
305             DataType endData;
306             cout << "请输入要在尾部插入的值: ";
307             cin >> endData;
308             l.InsertElemAtEnd(endData);
309             break;
310         case 7:
311             DataType pointData;
312             int index;
313             cout << "请输入要插入的数据: ";
314             cin >> pointData;
315             cout << "请输入要插入数据的位置: ";
316             cin >> index;
317             l.InsertElemAtIndex(pointData, index);
318             break;
319         case 8:
320             DataType headData;
321             cout << "请输入要在头部插入的值: ";
322             cin >> headData;
323             l.InsertElemAtHead(headData);
324             break;
325         case 9:
326             l.DeleteElemAtEnd();
327             break;
328         case 10:
329             l.DeleteAll();
330             break;
331         case 11:
332             DataType pointDeleteData;
333             cout << "请输入要删除的数据: ";
334             cin >> pointDeleteData;
335             l.DeleteElemAtPoint(pointDeleteData);
336             break;
337         case 12:
338             l.DeleteElemAtHead();
339             break;
340         default:
341             break;
342         }
343     }while (i != 0);
344 
345     system("pause");
346     return 0;
347 }

这里介绍的链表有头结点、有尾节点并且尾节点指向头结点

单链表的基本实现:

 

图片 3

typedef int DataType;
//定义单链表
typedef struct ListNode
{
 DataType _data;    //数据
   struct ListNode * _next;   //指向下一个节点的指针
}ListNode;

//初始化
void InitList(ListNode * &pHead)
{
    pHead = NULL;
}

//创建节点
ListNode * BuyNode(DataType x)
{
  ListNode * tmp = (ListNode *)malloc(sizeof(ListNode));
   assert(tmp);
 tmp->_data = x;
   tmp->_next = NULL;
    return tmp;
}

//尾插
void PushBack(ListNode * &pHead, DataType x)
{
    if (NULL == pHead)      //为空时,表示没有节点,创建新节点
  {
        pHead = BuyNode(x);
  }
    else
 {
        ListNode * tail = pHead;   
      while (tail->_next != NULL)
       {
            tail = tail->_next;     //令tail指向最后一个节点
       }
        tail->_next = BuyNode(x);
 }
}

//头插
void PushFront(ListNode * &pHead, DataType x)
{
   if (NULL == pHead)
   {
        pHead = BuyNode(x);
  }
    else
 {
        ListNode * tmp = BuyNode(x);
     tmp->_next = pHead;
       pHead = tmp;
 }
}

//尾删
void PopBack(ListNode * &pHead)    //1.为空  2.一个节点  3,多个节点
{
 if (NULL == pHead)
   {
        printf("List is empty!\n");
      return;
  }
    else if (NULL == pHead->_next)
    {
        free(pHead);
     pHead = NULL;
    }
    else
 {
        ListNode * prevtail = NULL, *tail = pHead;
       while (tail->_next != NULL)
       {
            prevtail = tail;         //令tail指向尾部,prevtail指向倒数第二个
         tail = tail->_next;
       }
        prevtail->_next = NULL;
       free(tail);
  }
}

//头删
void PopFront(ListNode * &pHead)
{
    if (NULL == pHead)    //为空
    {
        printf("List is empty!\n");
      return;
  }
    else      //不为空
    {
        ListNode* cur = pHead;
       pHead = pHead->_next;
     free(cur);
   }
}

//查找
ListNode * Find(ListNode * pHead, DataType x)
{
   ListNode * cur = pHead;
  while (cur)
  {
        if (cur->_data == x)
      {
            return cur;
      }
        cur = cur->_next;
 }
    return NULL;
}

//插入
void Insert(ListNode * &pos, DataType x)    //在pos节点后插入
{
  assert(pos);
 ListNode * tmp = BuyNode(x);
 tmp->_next = pos->_next;
   pos->_next = tmp;
}

//删除某节点
void Erase(ListNode * &pHead, ListNode * pos)
{
   assert(pos);

    if (pos == pHead)    //当要删除的节点就是第一个时,直接删
 {
        pHead = pHead->_next;
     free(pos);
   }
    else
 {
        ListNode * cur = pHead;
      while (cur)
      {
            if (cur->_next == pos)
            {
                cur->_next = pos->_next;
               free(pos);
               break;
           }
            cur = cur->_next;
     }
    }
}

//删除数据为x的节点
void Remove(ListNode * &pHead, DataType x)
{
 if (NULL == pHead)
   {
        printf("List is empty!\n");
      return;
  }
    else
 {
        ListNode * ret = Find(pHead, x);    //用ret变量指向x所在节点
      if (ret)
     {
            Erase(pHead, ret);      //删除此节点
      }
    }
}

//释放
void DestroyList(ListNode* & pHead)
{
 ListNode* cur = pHead;
   while (cur)
  {
        ListNode* tmp = cur;
     cur = cur->_next;
     free(tmp);
   }
    pHead = NULL;
}

//打印输出
void PrintList(ListNode * pHead)
{
    ListNode * cur = pHead;
  while (cur != NULL)
  {
        printf("%d -> ", cur->_data);
      cur = cur->_next;
 }
    printf("NULL\n");
}

 

单链表的每个结点的地址存放在其直接前驱结点的指针域中。其中第一个结点没有前驱结点,因此需要一个头指针指向第一个节点,便于我们对整个链表进行操作;这里的单链表的最后一个节点的指针域存放的是头结点的地址。

单链表不能随意存取,必要的时候我们可以通过已知结点的指针域不断遍历从而获取我们要的结点。

SList.h

/****************************************************************************************************/
/*
功能:应用C++语言实现单链表的各项操作
    建立链表的节点类LinkNode,封装一个SList类将有效节点链接起来
基本的成员函数:
           构造函数、拷贝构造函数、赋值运算符的重载、析构函数
**
**单链表的具体操作:
**                  1:在尾部插入节点
**                  2:打印单链表
**                  3:链表置空
**                  4:尾除尾节点
**                  5:头插
**                  6:删除首节点
**                  7:固定位置插入一个节点
**                  8:删除某一节点
**                  9:查找某节点并返回这个节点的位置
**                10:计算链表节点的数目
**                 11:查找某节点并删除
**                 12:删除链表中所有的x
**                 13:去重
**                 14:合并两个链表
**                 15:冒泡排序
**                 16:翻转单链表
**
**                                                             By :Lynn-Zhang
**
*/
/*****************************************************************************************************/
//****************/

typedef int DataType;

//节点类(复合形态)
//struct LinkNode     
//{
//  friend class SList;      //将SList设为友元,便于SList类可以访问节点类的私有成员
//public:
//  LinkNode(const DataType x);  
//private:
//  DataType _data;    //节点的数据
//  LinkNode* _next;    //指向该节点的下一个节点
//};

//直接用struct定义LinkNode类,因为struct的成员默认为公有数据成员,所以可直接访问
struct LinkNode      //节点类(建议写法)
{
    LinkNode(const DataType x);
    DataType _data;    //节点的数据
    LinkNode* _next;    //指向该节点的下一个节点
};
class SList
{
public:
    SList();         //构造函数
    SList(const SList& s);        //拷贝构造
    SList &operator=(SList& s);    //赋值运算符的重载
    ~SList();

public:   
        //单链表的具体操作
    void Uniqe();         //去重
    void Merge(SList &s);  //合并
    void Sort();       //冒泡
    void Reverse();   //翻转
    void Swap(SList& s);      //交换
    void PrintSList();   //打印链表
    void PushBack(const DataType& x);    //在尾部插入一个节点
    void Clear();         //链表置空
    void PopBack();       //删除尾节点
    void PushFront(DataType x);  //头插
    void PopFront();    //删除首节点
    void Insert(LinkNode* pos, DataType x);//固定位置插入一个节点
    void Erase(LinkNode* pos);        //删除某一节点
    LinkNode* Find(DataType x);       //查找节点并返回这个节点的地址
    int Amount();   //计算链表节点的数目
    void Remove(DataType x);     //查找某节点并删除
    void RemoveAll(DataType x);      //删除链表中所有的x

private:   
    LinkNode* _head;     //指向头节点
    LinkNode* _tail;        //指向尾节点
};
//*********************//

SList.cpp   (函数实现)

//**********************/////////
#include<iostream>
using namespace std;
#include<assert.h>
#include"SList.h"

   LinkNode::LinkNode(const DataType x)
           :_data(x)
           , _next(NULL)
           {}

    SList::SList()         //构造函数
        :_head(NULL)
        , _tail(NULL)
    {}
    SList::SList(const SList& s)          //拷贝构造
        :_head(NULL)
        , _tail(NULL)
    {
        if (s._head == NULL)
        {
            return;
        }
        LinkNode* tmp = s._head;
        do{
            PushBack(tmp->_data);
            tmp = tmp->_next;
            } while (tmp != s._head);

    }
    //赋值运算符的重载(传统方法)
    //SList & SList::operator=(const SList& s)    
    //{
    //  if (this != &s)
    //  {
    //      _head = NULL;
    //      _tail = NULL;
    //      LinkNode* tmp = s._head;
    //  do{
    //      PushBack(tmp->_data);
    //      tmp = tmp->_next;
    //       } while (tmp != s._head);
    //  }
    //  return *this; 
    //}

    //赋值运算符的重载(高效写法)
    /*void SList::Swap(SList& s)     
    {
    swap(_head, s._head);
    swap(_tail, s._tail);

    }
    SList&  SList::operator=(SList &s)
    {
    if (this != &s)
    {
    SList tmp(s);
    Swap(tmp);
    }
    return *this;
    }*/

    SList&  SList::operator=(SList &s)     //赋值运算符的重载再优化(推荐写法)
    {
        if (this != &s)
        {
            swap(_head, s._head);
            swap(_tail, s._tail);
        }
        return *this;
    }
    SList::~SList()    //析构
    {
        Clear();
    }

        void SList::Reverse()   //链表逆置(利用头插新节点的方法)
    {
        if (_head == NULL||_head->_next==_tail)
        {
            return;
        }
        int ret = Amount();
        _tail = new LinkNode(_head->_data);
        LinkNode* begin=NULL;
        LinkNode* tmp = _tail;
        while (--ret)
        {
            LinkNode* del = _head;
            _head = _head->_next;
            delete del;    //这里不要忘记做清理工作,否则内存泄漏
            begin = new LinkNode(_head->_data);
            begin->_next = tmp;
            _tail->_next = begin;
            tmp = begin;
        }
        _head = begin;
    }  

        //打印链表
    void SList::PrintSList()  
    {
        //头结点为空时,无需打印链表
        if (_head==NULL)
        {
            cout << "This SList is Empty !" << endl;
            return;
        }
        else
        {
            LinkNode* tmp = _head;
            do{ 
                cout << tmp->_data << "-->";
                tmp = tmp->_next;
                } while (tmp != _head);
            cout << endl;
        }
    }
    void SList::PushBack(const DataType& x)    //在尾部插入一个节点
    {
        //如果链表为空,插入节点后只有一个节点,此时_head=_tail
        if (_head == NULL)
        {
            _head = new LinkNode(x);
            _tail = _head;
            _tail->_next = _head;
        }
        else
        {
            _tail->_next = new LinkNode(x);
            _tail = _tail->_next;
            _tail->_next = _head;
        }
    }
    void SList::Clear()         //链表置空
    {
        LinkNode* begin = _head;
        while (begin != _tail)
        {
            _head = _head->_next;
            delete begin;
            begin = _head;
        }
        _head = NULL;
        _tail = NULL;
    }
    void SList::PopBack()    //尾删
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
        }
        else if (_head == _tail)
        {
            delete _head;
            _head = NULL;
            _tail = NULL;
        }
        else
        {
            LinkNode* cur = _head;
            while (cur->_next != _tail)
            {
                cur = cur->_next;
            }
            delete _tail;
            _tail = cur;
            _tail->_next = _head;
         }
    }
    void SList::PushFront(DataType x)  //头插
    {
        if (_head == NULL)
        {
            PushBack(x);
        }
        else
        {
            LinkNode* tmp = _head;
            _head = new LinkNode(x);
            _head->_next = tmp;
            _tail->_next = _head;
        }
    }
    void SList::PopFront()    //删除首节点
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return;
        }
        LinkNode* tmp = _head;
        _head = _head->_next;
        _tail->_next = _head;
        delete tmp;
    }

    //固定位置插入一个节点(这个函数需和Find函数搭配使用)
    //先用Find函数找到新节点需要插入的位置
    //(将Find函数的返回值传给Insert函数的参数pos),再在pos节点后面插入新节点x
    void SList::Insert(LinkNode* pos, DataType x)
    {
        assert(pos);
        if (pos==_tail)
        {
            PushBack(x);
        }
        else
        {
            LinkNode* tmp = new LinkNode(x);
            tmp->_next = pos->_next;
            pos->_next = tmp;
        }
    }

        //删除某一节点,同样,要先找到该节点并传参给Erase函数
    void SList::Erase(LinkNode* pos)        
    {
        assert(pos);
        if (pos == _tail)
        {
            PopBack();
        }
        if (pos == _head)
        {
            PopFront();
        }
        else
        {
            LinkNode* prev = _head;
            while (prev->_next != pos)
            {
                prev = prev->_next;
            }
            prev->_next = pos->_next;
            delete pos;
        }
    }
    LinkNode* SList::Find(DataType x)       //查找节点并返回这个节点的地址
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return NULL;
        }
        else
        {
            LinkNode* tmp = _head;
            do{
                    if (tmp->_data == x)
                    {
                        return tmp;
                    }
                        tmp = tmp->_next;
            } while (tmp != _head);
            return NULL;
        }
    }
    int SList::Amount()   //计算链表节点的数目
    {
        if (_head == NULL)
        {
            return 0;
        }
        else
        {
            int count = 0;
            LinkNode* cur = _head;
            while (cur != _tail)
            {
                count++;
                cur = cur->_next;
            }
            return ++count;
        }
    }
    void SList::Remove(DataType x)      //查找某节点并删除
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
        }
        else
        {
            LinkNode* tmp = Find(x);
            if (tmp != NULL)
            {
                Erase(tmp);
            }
        }
    }
    void SList::RemoveAll(DataType x)       //删除链表中所有的x
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return;
        }
//如果链表不为空,设置left和right前后指针,从头至尾遍历一遍,delete节点的data为x的节点

            LinkNode* left = _tail;
            LinkNode* right = _head;
            int count = Amount();
            while (count--)
            {
             //当要删掉的节点是头节点时,需要注意头节点要指向它的下一个节点
             //当要删掉的节点是尾节点时,需要注意尾节点要指向它的上一个节点
             //当left和right指向同一块要删掉的节点时,将链表置空

                if (right->_data == x)
                {
                    if (_head == right)   
                    {
                        _head = _head->_next;
                    }
                    if (_tail == right)   
                    {
                        _tail =left;
                    }
                    if (right == left)    
                    {
                        _head = NULL;
                        _tail = NULL;
                        return;
                    }
                    LinkNode* tmp = right;
                    right = right->_next;
                    delete tmp;
                    left->_next = right;
                }
                else
                {
                    left = right;
                    right = right->_next;
                }
            }  
    }
    void SList::Uniqe()       //去重(针对有序链表)
    {
        assert(_head &&_head!= _tail);
        LinkNode* left = _head;
        LinkNode* right = _head->_next;
        while (left != _tail)
        {
            while(left->_data == right->_data)
            {
                LinkNode* tmp = right;
                right = right->_next;
                left->_next = right;
                delete tmp;
            }
            left = left->_next;
            right = right->_next;
        }
    }
    void SList::Merge(SList &s)    //合并(针对有序链表),合并后依然有序
    {
        //  1. _head为空
        //  2. 链表s为空
        if (_head == NULL)
        {
            _head = s._head;
            _tail = s._tail;
        }
        if (s._head == NULL)
        {
            return;
        }
        //  3. 两个链表都不为空
        LinkNode* phead = _head;
        if (phead->_data <= s._head->_data)
        {
            phead = phead->_next;
        }
        else
        {
            _head = s._head;
            s._head = s._head->_next;
        }
        LinkNode* cur = _head;
        while (1)
        {
            if (phead->_data <= s._head->_data)
            {
                _head->_next = phead;
                _head = _head->_next;
                if (phead == _tail)
                {
                    _head->_next = s._head;   
                    _tail=s._tail;
                    _tail->_next = cur;
                    break;
                }
                phead = phead->_next;
            }
            else
            {
                _head->_next = s._head;
                _head = _head->_next;
                if (s._head ==s._tail)
                {
                    _head->_next = phead;
                    _tail->_next = cur;
                    break;
                }
                s._head = s._head->_next;
            }

        }
        _head = cur;
    }
    void SList::Sort()                      //冒泡排序
    {
        assert(_head);
        if (_head == _tail)
        {
            return;
        }
        int size = Amount();
        for (int i = 0; i < size-1 ; i++)  
        {
            LinkNode* left = _head;
            LinkNode* right = _head->_next;
            for (int j = 0; j < size - i-1 ; j++)
            {              
                if (left->_data>right->_data)
                {
                    swap(left->_data, right->_data);
                }
                right = right->_next;
                left = left->_next;
            }      
        }
    }
///************************

测试用例(Test.cpp)

#include"SList.h"
#include<stdlib.h>

void Test3()
{
    //排序 去重 合并
    cout << "list 1:" << endl;
    SList list1;
  /*list1.PushBack(2);
    list1.PushBack(3);
    list1.PushBack(2);
    list1.PushBack(2);
    list1.PushBack(1);
    list1.PrintSList();
    list1.Sort();
    list1.PrintSList();
  list1.Uniqe();
    list1.PrintSList();*/

    list1.PushBack(5);
    list1.PushBack(3);
    list1.PushBack(8);
    list1.PushBack(2);
    list1.PushBack(9);
    list1.PushBack(10);
    list1.PushBack(2);
    list1.PushBack(2);
    list1.PushBack(1);
    list1.PrintSList();
    list1.Sort();
    list1.PrintSList();

    cout << "list 2:" << endl;
    SList list2;
    list2.PushBack(1);
    list2.PushBack(6);
    list2.PushBack(4);
    list2.PushBack(0);
    list2.PushBack(7);
    list2.PrintSList();
    list2.Sort();
    list2.PrintSList();

    cout << "list 1:" << endl<<endl;
    list1.Merge(list2);
    list1.PrintSList();
}
void Test2()
{
    SList list1;
    list1.PushBack(1);
    list1.PushBack(3);
    list1.PushBack(4);
    list1.PushBack(2);
    list1.PushBack(6);
    list1.PrintSList();

    /*list1.RemoveAll(2);
    list1.PrintSList();*/

    SList list2 = list1;
    /*list2.PushBack(2);
    list2.PushBack(3);
    list2.PushBack(4);
    list2.PushBack(2);
    list2.PushBack(2);*/
    list2.PrintSList();
    list2.Reverse();
    list2.PrintSList();

}
void Test1()
{
    //SList list1;
    //list1.PushBack(1);
    //list1.PushBack(2);
    //list1.PushBack(3);
    //list1.PushBack(4);
    //list1.PushBack(5);
    //list1.PrintSList();

    //list1.Remove(2);
    //list1.PrintSList();

    //int num =list1.Amount();
    //cout <<"节点个数:"<< num << endl;

    /*//检验Erase函数
    LinkNode* del = list1.Find(2);
    list1.Erase(del);
    list1.PrintSList();
    */

    /*//找到某节点并在其后插入新节点
    LinkNode* In =list1.Find(5);
    list1.Insert(In, 0);
    list1.PrintSList();*/

    /* //删除头结点
    list1.PopFront();
    list1.PrintSList();
    *//////

    /*//////查找节点
    LinkNode* ret=list1.Find(5);
    if (ret != NULL)
    {
    cout << "要查找的节点data是:" << ret->_data << endl;
    cout << "要查找的节点adress是:" <<ret<< endl;
    }
    else
    {
    cout << "not exit !" << endl;
    }*////////

    //验证构造函数
    //SList list2(list1);
    //list2.PrintSList();

    //验证赋值运算符的重载
    //SList list3 = list2;
    //list3.PrintSList();

    //验证析构函数
    //list3.Clear();
    //list3.PrintSList();

    //验证尾删和头插
    ///*list3.PopBack();
    //list3.PrintSList();*/
    //list3.PushFront(0);
    //list3.PrintSList();
}

int main()
{
    //Test1();
    Test2();
    system("pause");
}

  本文利用C++语言,在Windows平台 Visual Studio 2013开发环境下实现

 

相关文章