C++資料結構之單連結串列的實現

2022-05-31 22:00:10

一、單連結串列的定義

線性表的鏈式儲存又稱為單連結串列，它是指通過一組任意的儲存單元來儲存線性表中的資料元素。為了建立資料元素之間的線性關係，對每個連結串列結點，除存放元素自身的資訊外，還需要存放一個指向其後繼的指標。

單連結串列中結點型別的描述如下：

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++單連結串列的資料請關注it145.com其它相關文章！

C++資料結構之單連結串列的實現

目錄

一、單連結串列的定義

二、單連結串列的基本操作的實現

1.初始化

2.取值

3.查詢

4.插入

5.刪除

三、完整程式碼

四、測試一下程式碼

熱門文章