C++详解如何实现单链表

单链表

单链表的基本操作

1.初始化

2.取值

3.查找

4.插入

5.删除

示例代码

开发环境

运行结果

单链表

链表内存空间不一定连续，其扩展性较好。多余的不多说了。该文主要记录单链表的实现，该单链表含有一个非空的头节点。链表的操作实际上是对其指针域与数据域的操作。

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述如下：

typedef struct  LNode{  // 定义单链表节点类型
  ElemType data;    // 数据域
  struct LNode* next; // 指针域
};LNode, *LinkList;

单链表的基本操作 1.初始化

单链表的初始化操作就是构造一个空表。

具体代码：

// 初始化单链表
void InitList(LinkList &L) // 构造一个空的单链表L
{
  L=new LNode;  // 生成新节点作为头节点，用头指针L指向头节点
  L->next=NULL; // 头节点的指针域置空
}

2.取值

和顺序表不同，在链表中并没有存储在物理相邻的单元中。所以我们只能从链表的首节点出发，顺着链域next逐个节点向下访问。

具体代码：

// 单链表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
  LinkList p=L->next;int j=1; // 初始化，p指向首元节点，计数器j初值为1
  while(p&&j<i) // 顺着链域向后查找，直到p为空或p指向第i个元素
  {
    p=p->next;  // p指向下一个节点
    ++j;  // 计数器j相应加1
  }
  if(!p||j>i)return false;   // i值不合法
  e=p->data;  // 取第i个节点的数据域
  return true;
}

3.查找

从链表的首元节点出发，依次将节点值和给定值e进行比较，返回查找结果。

具体代码：

//单链表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
  //在单链表中查找第一个数据为e的结点
  p = L->next;//p指向首元结点
  while (p && p->data != e)
  {
    p = p->next;
  }
  if (p)
  {
    return true;
  }
  return false;
}

4.插入

// 单链表的插入
bool ListInsert(LinkList &L, int i, ElemType e)
{
  LinkList p = L;
  LNode* s;
  int j = 0;
  while (p && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!p || i < 1)//i大于表长+1或小于1，插入位置不合法
  {
    return false;
  }
  s = new LNode;
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

5.删除

//单链表的删除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
  //将单链表的第i个结点删除
  LinkList p = L;
  LNode* q;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大于表长或小于1，删除位置不合法
  {
    return false;
  }
  q = p->next;//临时保存被删结点的地址以备释放
  p->next = q->next;
  e = q->data;//保存被删结点的数据
  delete q;//释放被删结点的空间
  return true;
}

示例代码

直接上代码：

LinkList.h

#pragma once
typedef struct LINKLIST {
void * data;
struct LINKLIST *pNext;
}LinkList;
typedef void(*PrintLinkList)(void *);
//无头的链表
class LinkNode
{
public:
LinkNode();
~LinkNode();
void insertLinkList(int pos,void * data);
void removeByPosInLinkList(int pos);
int getSizeLinkList();
int findValueInLinkList(void* value);
LinkList* getFirstNodeLinkList();
void printLinkList(PrintLinkList print);
private:
LinkList *m_pHead;
int m_size;
};

LinkList.cpp

// LinkList.cpp
//
#include "LinkList.h"
#include <iostream>
using namespace std;
LinkNode::LinkNode()
{
m_pHead = new LinkList;
m_pHead->data = nullptr;
m_pHead->pNext = nullptr;
m_size = 0;
}
LinkNode::~LinkNode()
{
if (m_pHead != nullptr)
{
while (m_pHead != nullptr)
{
LinkList *pNext = m_pHead->pNext;
delete m_pHead;
m_pHead = nullptr;
m_pHead = pNext;
}
}
}
void LinkNode::insertLinkList(int pos, void * data)
{
if (m_pHead == nullptr)
{
return;
}
if (data == nullptr)
{
return;
}
//插入位置矫正
if (pos < 0 || pos > m_size )
{
pos = m_size;
}
LinkList * insertNode = new LinkList;
insertNode->data = data;
insertNode->pNext = nullptr;
//找到前一个位置（pos从0开始）
LinkList *pPre = m_pHead;
for (int i = 0; i < pos; ++i)
{
pPre = pPre->pNext;
}
//有头节点的链表
insertNode->pNext = pPre->pNext;
pPre->pNext = insertNode;
m_size++;
}
void LinkNode::removeByPosInLinkList(int pos)
{
if (m_pHead == nullptr)
{
return;
}
if (pos < 0 || pos >= m_size)
{
return ;
}
//找到前一个位置（pos从0开始）
LinkList *pPre = m_pHead;
for (int i = 0; i < pos; ++i)
{
pPre = pPre->pNext;
}
LinkList *delNode = pPre->pNext;
pPre->pNext = delNode->pNext;
delete delNode;
delNode = nullptr;
m_size--;
}
int LinkNode::getSizeLinkList()
{
return m_size;
}
int LinkNode::findValueInLinkList(void* value)
{
int nPos = -1;
if (m_pHead == nullptr)
{
return nPos;
}
if (value == nullptr)
{
return nPos;
}
LinkList *pHead = m_pHead;
for (int i = 0; i < m_size; ++i)
{
//有空的头节点
pHead = pHead->pNext;
if (pHead->data == value)
{
nPos = i;
break;
}
}
return nPos;
}
LinkList * LinkNode::getFirstNodeLinkList()
{
if (m_pHead == nullptr)
{
return nullptr;
}
return m_pHead->pNext;//有空的头节点
}
void LinkNode::printLinkList(PrintLinkList print)
{
if (m_pHead == nullptr)
{
return ;
}
//不能直接移动头节点，需要保留头节点
LinkList *pTemp = m_pHead;
pTemp = pTemp->pNext;
while (pTemp != nullptr)
{
print(pTemp->data);
pTemp = pTemp->pNext;
}
cout << endl;
}

mian.cpp

#include <iostream>
#include "LinkList.h"
using namespace std;
typedef struct PERSON {
char name[64];
int age;
int score;
}Person;
void myPrint(void *data) 
{
Person *p = (Person*)data;
cout << "name : " << p->name << " age: " << p->age << " score: " << p->score << endl;
}
void test() 
{
LinkNode *plinkList = new LinkNode;
Person p1 = {"husdh",23,78};
Person p2 = { "hudfs",23,98 };
Person p3 = { "术后",23,78 };
Person p4 = { "喀什",23,67 };
plinkList->insertLinkList(0, &p1);
plinkList->insertLinkList(1, &p2);
plinkList->insertLinkList(2, &p3);
plinkList->insertLinkList(3, &p4);
plinkList->printLinkList(myPrint);
cout <<"链表的节点数： "<< plinkList->getSizeLinkList() << endl;
plinkList->removeByPosInLinkList(1);
cout << "remove" << endl;
plinkList->printLinkList(myPrint);
cout << "删除后链表的节点数： " << plinkList->getSizeLinkList() << endl;
cout << "p3位置： " << plinkList->findValueInLinkList(&p3) << endl;
myPrint(plinkList->getFirstNodeLinkList()->data);
delete plinkList;
plinkList = nullptr;
}
int main()
{
test();
return 0;
}

以上是单链表实现及测试代码。

开发环境

vs2017控制台输出程序。

运行结果