C++詳解如何實(shí)現(xiàn)單鏈表

更新時(shí)間：2022年06月25日 09:55:14 作者：肩上風(fēng)騁

線性表的鏈?zhǔn)酱鎯?chǔ)又稱為單鏈表，它是指通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素。本文將用C++實(shí)現(xiàn)單鏈表，需要的可以參考一下

單鏈表

鏈表內(nèi)存空間不一定連續(xù)，其擴(kuò)展性較好。多余的不多說了。該文主要記錄單鏈表的實(shí)現(xiàn)，該單鏈表含有一個(gè)非空的頭節(jié)點(diǎn)。鏈表的操作實(shí)際上是對其指針域與數(shù)據(jù)域的操作。

線性表的鏈?zhǔn)酱鎯?chǔ)又稱為單鏈表，它是指通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素。為了建立數(shù)據(jù)元素之間的線性關(guān)系，對每個(gè)鏈表結(jié)點(diǎn)，除存放元素自身的信息外，還需要存放一個(gè)指向其后繼的指針。

單鏈表中結(jié)點(diǎn)類型的描述如下：

typedef struct  LNode{  // 定義單鏈表節(jié)點(diǎn)類型
  ElemType data;    // 數(shù)據(jù)域
  struct LNode* next; // 指針域
};LNode, *LinkList;

單鏈表的基本操作

1.初始化

單鏈表的初始化操作就是構(gòu)造一個(gè)空表。

具體代碼：

// 初始化單鏈表
void InitList(LinkList &L) // 構(gòu)造一個(gè)空的單鏈表L
{
  L=new LNode;  // 生成新節(jié)點(diǎn)作為頭節(jié)點(diǎn)，用頭指針L指向頭節(jié)點(diǎn)
  L->next=NULL; // 頭節(jié)點(diǎn)的指針域置空
}

2.取值

和順序表不同，在鏈表中并沒有存儲(chǔ)在物理相鄰的單元中。所以我們只能從鏈表的首節(jié)點(diǎn)出發(fā)，順著鏈域next逐個(gè)節(jié)點(diǎn)向下訪問。

具體代碼：

// 單鏈表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
  LinkList p=L->next;int j=1; // 初始化，p指向首元節(jié)點(diǎn)，計(jì)數(shù)器j初值為1
  while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個(gè)元素
  {
    p=p->next;  // p指向下一個(gè)節(jié)點(diǎn)
    ++j;  // 計(jì)數(shù)器j相應(yīng)加1
  }
  if(!p||j>i)return false;   // i值不合法
  e=p->data;  // 取第i個(gè)節(jié)點(diǎn)的數(shù)據(jù)域
  return true;
}

3.查找

從鏈表的首元節(jié)點(diǎn)出發(fā)，依次將節(jié)點(diǎn)值和給定值e進(jìn)行比較，返回查找結(jié)果。

具體代碼：

//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
  //在單鏈表中查找第一個(gè)數(shù)據(jù)為e的結(jié)點(diǎn)
  p = L->next;//p指向首元結(jié)點(diǎn)
  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個(gè)結(jié)點(diǎn)
  {
    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個(gè)結(jié)點(diǎn)刪除
  LinkList p = L;
  LNode* q;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
  {
    return false;
  }
  q = p->next;//臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放
  p->next = q->next;
  e = q->data;//保存被刪結(jié)點(diǎn)的數(shù)據(jù)
  delete q;//釋放被刪結(jié)點(diǎn)的空間
  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;
	//找到前一個(gè)位置（pos從0開始）
	LinkList *pPre = m_pHead;
	for (int i = 0; i < pos; ++i)
	{
		pPre = pPre->pNext;
	}
	//有頭節(jié)點(diǎn)的鏈表
	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 ;
	}
	//找到前一個(gè)位置（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)
	{
		//有空的頭節(jié)點(diǎn)
		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;//有空的頭節(jié)點(diǎn)
}
void LinkNode::printLinkList(PrintLinkList print)
{
	if (m_pHead == nullptr)
	{
		return ;
	}
	//不能直接移動(dòng)頭節(jié)點(diǎn)，需要保留頭節(jié)點(diǎn)
	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 = { "術(shù)后",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 <<"鏈表的節(jié)點(diǎn)數(shù)： "<< plinkList->getSizeLinkList() << endl;
	plinkList->removeByPosInLinkList(1);
	cout << "remove" << endl;
	plinkList->printLinkList(myPrint);
	cout << "刪除后鏈表的節(jié)點(diǎn)數(shù)： " << plinkList->getSizeLinkList() << endl;
	cout << "p3位置： " << plinkList->findValueInLinkList(&p3) << endl;
	myPrint(plinkList->getFirstNodeLinkList()->data);
	delete plinkList;
	plinkList = nullptr;
}
int main()
{
	test();
	return 0;
}

以上是單鏈表實(shí)現(xiàn)及測試代碼。