C++数据结构02--链式线性表（单链表的实现）

头文件：

//实现链式线性表
#include "stdafx.h"
using namespace std;

typedef int DataType; //将数据类型设为int类型/或者其他类型均可

//链式结构体定义
typedef struct Node{
    DataType data; //当前的数据
    struct Node* next; //保留着指向下个数据的地址
}LinkList;

//链式线性表类的声明
class Linkential{

public:
    //构造函数和非构造函数
    Linkential();
    ~Linkential();

private:
    
    //查找数据
    //@param[in]:L:需要查询的链表
    //@param[in]:pos:序号
    //return:该位置的值
    DataType GetDataByPos(LinkList* L,int pos );

    //查找数据
    //@param[in]:L:需要查询的链表
    //@param[in]:pos:序号
    //return:查找位置的地址
    LinkList* FindListByPos(LinkList* L,int pos );

    //插入数据
    //@param[in]:L:需要查询的链表
    //@param[in]:pos:序号:
    //@param[in]:data:需要插入的值
    //return:false:插入失败，true:插入成功
    bool InsertLinkData(LinkList* L, int pos, DataType data);

    //删除数据
    //@param[in]:L:需要查询的链表
    //@pos:删除的位置
    //return:false:删除失败，true:删除成功
    bool DeleteLinkData(LinkList* L, int pos);

    //清空链表
    bool ClearLinkData(LinkList* L);

    //得到链表长度
    //@param:L:链表头,
    //return:长度
    int getLinkLength(LinkList* L);
};

实现cpp文件：

#include "stdafx.h"
#include "LinkLineList.h"

//实现Linkential类的方法

//构造函数
Linkential::Linkential(){

}

//析构函数
Linkential::~Linkential()
{

}


DataType  Linkential::GetDataByPos(LinkList* L,int pos )
{
  LinkList * m = L;
  int i = 1;
  while((m!=nullptr) &&(i < pos))
  {
    m = m->next; //往下遍历
    i++;
  }
  //判断是否i为pos
  if (i!=pos)
  {
    return NULL;//返回空 说明链表长度小于它；
  }
  return m->data;
}

LinkList* Linkential::FindListByPos(LinkList* L,int pos )
{
  LinkList * m = L;
  int i = 1;
  while((m!=nullptr) &&(i < pos))
  {
    m = m->next; //往下遍历
    i++;
  }
  //判断是否i为pos
  if (i!=pos)
  {
    return nullptr;//返回空 说明链表长度小于它；
  }
  return m;
}

bool Linkential::InsertLinkData(LinkList* L, int pos, DataType data)
{
  //pos=1，说明需要在线性表头插入
  if (pos==1)
  {
    //创建新的线性表 下个指针指向L
    LinkList * s = new LinkList;
    s->data = data;
    s->next = L;
    return true;
  }

  //不在表头的情况
  LinkList* cur_list = FindListByPos(L,pos-1);
  
  //说明长度超过了--
  if (cur_list==nullptr)
  {
    return false;
  }
    
  LinkList * sList = new LinkList;
  sList->data=data;
  LinkList* nex_list = cur_list->next;//可能nex_list地址为空 但是不影响
  cur_list->next = sList;
  sList->next = nex_list;
  return true;
}

bool Linkential::DeleteLinkData(LinkList* L, int pos)
{
  //删除第一个节点
  if (pos==1)
  {
    LinkList * p = L;
    if(p==nullptr)
    {
      return false;
    }
    L = L->next;
    delete p;
    return true;
  }

  LinkList * q = L;
  //得到需要删除的前一个节点
  LinkList * m = FindListByPos(L,pos-1);
  if (m==nullptr)
  {
    return false;
  }
  LinkList*del_list = m->next;
  if (del_list==nullptr)
  {
    return false;
  }
  m->next = del_list->next;
  delete del_list;
  return true;
}

bool Linkential::ClearLinkData(LinkList* L)
{
  LinkList *mm = L;
  while ( L->next!=nullptr)
  {
    mm = L->next;
    delete L;
    L = mm;
  }
  return true;
}

int Linkential::getLinkLength(LinkList* L)
{
  //原理 根据next指针为空==说明到底了
  int  length = 0;
  LinkList * cur_List = L;
  //当List存在时
  while (cur_List)
  {
    length++;
    cur_List = cur_List->next;
  }
  //返回长度
  return length;
}

比较好理解，就不讲解了 具体可以看我的github