C++數據結構之單鏈表的實現

Posted on by

一、單鏈表的定義

線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數據元素。為瞭建立數據元素之間的線性關系，對每個鏈表結點，除存放元素自身的信息外，還需要存放一個指向其後繼的指針。

單鏈表中結點類型的描述如下：

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;
}

三、完整代碼

#include<iostream>
using namespace std;
#define ElemType int

typedef struct  LNode{  // 定義單鏈表節點類型
  ElemType data;    // 數據域
  struct LNode* next; // 指針域
}LNode,*LinkList;


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


//單鏈表的創建
void CreateList_H(LinkList& L)//前插法創建單鏈表
{
  //創建一個長度為n的單鏈表L,逆序位插入
  int n;
  LNode *p;
  cout << "請輸入創建的單鏈表長度：" << endl;
  cin >> n;
  for (int i = 0; i < n; i++) {
    p = new LNode;
    cout << "請輸入插入的第" << i + 1 << "個數據值" << endl;
    cin >> p->data;
    p->next = L->next;
    L->next = p;
  }
}


// 單鏈表的取值
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;
}



//單鏈表的查找
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;
}


// 單鏈表的插入
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;
}


//單鏈表的刪除
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;
}

四、測試一下代碼

#include<iostream>
using namespace std;
#define ElemType int

//************************單鏈表的存儲結構********************
typedef struct LNode
{
  ElemType data;//結點的數據域
  struct LNode* next;//結點的指針域
}LNode, * LinkList;//LinkList為指向結構體LNode的指針類型

//***********************單鏈表的基本操作函數******************

//單鏈表的初始化
void InitList(LinkList& L)
{
  //構造一個空的單鏈表
  L = new LNode;
  L->next = NULL;
}
//單鏈表的創建
void CreateList_H(LinkList& L)//前插法創建單鏈表
{
  //創建一個長度為n的單鏈表L,逆序位插入
  int n;
  LNode* p;
  cout << "請輸入創建的單鏈表長度：" << endl;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    p = new LNode;
    cout << "請輸入插入的第" << i + 1 << "個數據值" << endl;
    cin >> p->data;
    p->next = L->next;
    L->next = p;
  }
}

void CreateList_R(LinkList& L)//後插法創建單鏈表
{
  //創建一個長度為n的單鏈表L,正序位插入
  int n;
  LNode* p, * r;
  r = L;//尾指針r指向頭結點
  cout << "請輸入創建的單鏈表長度：" << endl;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    p = new LNode;
    cout << "請輸入插入的第" << i + 1 << "個數據值" << endl;
    cin >> p->data;
    p->next = NULL;
    r->next = p;
    r = p;
  }
}

//單鏈表的插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
  //在帶頭結點的單鏈表L的第i個結點前插入新結點
  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;
}

//單鏈表的刪除
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;
}

//單鏈表的取值
bool GetElem(LinkList L, int i, ElemType& e)
{
  //獲取單鏈表中第i個結點的數據
  LinkList p = L;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1個結點
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大於表長或小於1，第i個結點不存在
  {
    return false;
  }
  e = p->next->data;//獲取第i個結點的數據
  return true;
}

//單鏈表的查找
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;
}

//*********************************單鏈表的基本功能函數******************************

//1、插入
void ListInsert(LinkList& L)
{

  ElemType e;
  int i;
  bool flag;
  cout << "請輸入要插入的數據：" << endl;
  cin >> e;
  cout << "請輸入要插入的位置：" << endl;
  cin >> i;
  flag = ListInsert(L, i, e);
  if (flag)
    cout << "插入成功!" << endl;
  else
    cout << "位置不對，插入失敗！" << endl;
}

//2、刪除
void ListDelete(LinkList& L)
{
  ElemType e;
  int i;
  bool flag;
  cout << "請輸入要刪除數據的位置：" << endl;
  cin >> i;
  flag = ListDelete(L, i, e);
  if (flag)
    cout << "刪除成功，刪除的數據為：" << e << endl;
  else
    cout << "位置不對，刪除失敗！" << endl;
}

//3、取值
void GetElem(LinkList L)
{
  ElemType e;
  int i;
  bool flag;
  cout << "請輸入要獲取數據的位置：" << endl;
  cin >> i;
  flag = GetElem(L, i, e);
  if (flag)
    cout << "獲取的數據為：" << e << endl;
  else
    cout << "位置不對，獲取數據失敗！" << endl;
}

//4、查找
void LocateElem(LinkList L)
{
  ElemType e;
  LNode* p = NULL;
  bool flag;
  cout << "請輸入要查找的數據：" << endl;
  cin >> e;
  flag = LocateElem(L, p, e);
  if (flag)
    cout << "查找成功，該數據的地址為：" << p << endl;
  else
    cout << "查找失敗！" << endl;
}

//5、判空
void ListEmpty(LinkList L)
{
  if (L->next)
    cout << "鏈表不為空！" << endl;
  else
    cout << "鏈表為空！" << endl;
}

//6、求長
void ListLength(LinkList L)
{
  LinkList p = L->next;//p指向第一個結點
  int i = 0;
  while (p)//遍歷單鏈表，統計結點數
  {
    i++;
    p = p->next;
  }
  cout << "鏈表的長度為：" << i << endl;
}

//7、清空
void ClearList(LinkList& L)
{
  LNode* p, * q;
  p = L->next;
  while (p)//從首元結點開始，依次刪除
  {
    q = p->next;
    delete p;
    p = q;
  }
  L->next = NULL;//頭結點指針域置空
}

//8、銷毀
void DestroyList(LinkList& L)
{
  LNode* p;
  while (L)//從頭結點開始依次刪除
  {
    p = L;
    L = L->next;
    delete p;
  }
}

//9、打印
void PrintList(LinkList L)
{
  LinkList p = L->next;//p指向第一個結點
  int i = 0;
  while (p)//遍歷單鏈表
  {
    i++;
    cout << "鏈表第" << i << "個數據為：" << p->data << endl;
    p = p->next;
  }
}

//菜單
void menu()
{
  cout << "***************************************************************************" << endl;
  cout << "***********************************1、插入*********************************" << endl;
  cout << "***********************************2、刪除*********************************" << endl;
  cout << "***********************************3、取值*********************************" << endl;
  cout << "***********************************4、查找*********************************" << endl;
  cout << "***********************************5、判空*********************************" << endl;
  cout << "***********************************6、求長*********************************" << endl;
  cout << "***********************************7、清空*********************************" << endl;
  cout << "***********************************8、銷毀*********************************" << endl;
  cout << "***********************************9、打印*********************************" << endl;
  cout << "***********************************0、退出*********************************" << endl;
  cout << "***************************************************************************" << endl;
}

int main()
{
  LinkList L;
  InitList(L);
  int select;
  cout << "請先創建單鏈表：1、前插法！  2、後插法！" << endl;
  cin >> select;
  switch (select)
  {
  case 1://插入
    CreateList_H(L);
    system("pause");//按任意鍵繼續
    break;
  case 2://刪除
    CreateList_R(L);
    system("pause");
    break;
  default:
    cout << "輸入有誤,創建失敗！" << endl;
    system("pause");
    break;
  }
  while (1)
  {
    system("CLS");//清屏操作
    menu();
    cout << "請輸入菜單序號：" << endl;
    cin >> select;
    switch (select)
    {
    case 1://插入
      ListInsert(L);
      system("pause");//按任意鍵繼續
      break;
    case 2://刪除
      ListDelete(L);
      system("pause");
      break;
    case 3://取值
      GetElem(L);
      system("pause");
      break;
    case 4://查找
      LocateElem(L);
      system("pause");
      break;
    case 5://判斷鏈表是否為空
      ListEmpty(L);
      system("pause");
      break;
    case 6://求單鏈表的長度
      ListLength(L);
      system("pause");
      break;
    case 7://清空
      ClearList(L);
      system("pause");
      break;
    case 8://銷毀
      DestroyList(L);
      system("pause");
      return 0;
      break;
    case 9://打印
      PrintList(L);
      system("pause");
      break;
    case 0:
      cout << "歡迎下次使用!" << endl;//退出
      system("pause");
      return 0;
      break;
    default:
      cout << "菜單序號輸入有誤！" << endl;
      system("pause");
      break;
    }
  }
  system("pause");
  return 0;
}

以上就是C++數據結構之單鏈表的實現的詳細內容，更多關於C++單鏈表的資料請關註WalkonNet其它相關文章！

推薦閱讀：