C++ 單鏈表的基本操作(詳解)

2020-01-26 14:21:45

字體：大中小

來源：轉載

供稿：網友

鏈表一直是面試的高頻題，今天先總結一下單鏈表的使用，下節再總結雙向鏈表的。本文主要有單鏈表的創建、插入、刪除節點等。

1、概念

單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。

鏈表中的數據是以結點來表示的，每個結點的構成：元素 + 指針，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。如下圖：

2、鏈表的基本操作

SingleList.cpp:

#include "stdafx.h"#include "SingleList.h"#include <cstdlib>#include <iostream>#include <string.h>#include <conio.h>#include <stdio.h>/*c++實現簡單的單鏈表操作*/using namespace std;SingleList::SingleList(){  int num;  char name[128];  // 創建鏈表  node *stuList = CreatNode();  PrintList(stuList);  // 插入節點  printf("/n請輸入要插入的學生學號和姓名，輸入0 0表示結束.");  scanf_s("%d%s", &num, name, 100);  stuList = InsertNode(stuList, num, name);  PrintList(stuList);  // 刪除節點  printf("/n請輸入要刪除的學生學號：");  scanf_s("%d", &num, 100);  stuList = DeleteNode(stuList, num);  PrintList(stuList);  // 逆序  printf("/n逆序后的鏈表為：/n");  stuList = ReverseList(stuList);  PrintList(stuList);  system("PAUSE");}SingleList::~SingleList(){}//建立單鏈表 node *SingleList::CreatNode(){  node *head, *p, *s;  int num = 0;  char name[128];  int cycle = 1;  head = (node *)malloc(sizeof(node));  // 為頭結點分配內存空間  head->next = nullptr;  p = head;    // p指向頭節點  while (cycle)  {    printf("/n請輸入學生的學號和姓名:");    scanf_s("%d%s", &num, name, 100);    if (num != 0)    {      s = (node *)malloc(sizeof(node));      s->num = num;      memcpy(s->name, name, 128);      printf("%d%s", s->num, s->name);      p->next = s;    // 指向新插入的節點      p = s;    // p指向當前節點    }    else    {      cycle = 0;    }  }  head = head->next;  p->next = NULL;  printf("頭節點學生信息為: %d%s/n", head->num, head->name);  return head;}//單鏈表插入node *SingleList::InsertNode(node *head, int num, char* name){  node *s, *p1, *p2 = NULL;  p1 = head;  s = (node *)malloc(sizeof(node));  s->num = num;  strcpy_s(s->name, name);  while ((s->num > p1->num) && p1->next != NULL)  {    p2 = p1;    p1 = p1->next;  }  if (s->num <= p1->num)  {    if (head == p1)    {      // 插入首節點      s->next = p1;      head = s;    }    else    {      // 插入中間節點      p2->next = s;      s->next = p1;    }  }  else  {    // 插入尾節點    p1->next = s;    s->next = NULL;  }  return head;}// 計算單鏈表長度int SingleList::GetLength(node *head){  int length = 0;  node *p;  p = head;  while (p != NULL)  {    p = p->next;    length++;  }  return length;}//單鏈表刪除某個元素 node *SingleList::DeleteNode(node *head, int num){  node *p1, *p2 = nullptr;  p1 = head;  while (num != p1->num && p1->next != NULL)  {    p2 = p1;    p1 = p1->next;  }  if (num == p1->num)  {    if (p1 == head)    {      head = p1->next;    }    else    {      p2->next = p1->next;    }    free(p1);  }  else  {    printf("找不到學號為%d 的學生!/n", num);  }  return head;}//單鏈表逆序node *SingleList::ReverseList(node *head){  // A->B->C->D  node *old_head;    // 原來鏈表的頭  node *new_head;    // 新鏈表的頭  node *cur_head;    // 獲得原來鏈表的頭  if (head == NULL || head->next == NULL)    return head;  new_head = head;        // A  cur_head = head->next;    // B  while (cur_head)  {    old_head = cur_head->next;    // 將原來鏈表的頭取出，并將第二個節點作為頭節點    cur_head->next = new_head;  // 將取出的頭設為新鏈表的頭    new_head = cur_head;        // 新鏈表的頭就是目前新鏈表的頭    cur_head = old_head;          // 接著處理  }  head->next = NULL;  head = new_head;  return head;}//打印單鏈表void SingleList::PrintList(node *head){  node *p;  int n;  n = GetLength(head);  printf("/n打印出 %d 個學生的信息:/n", n);  p = head;  while (p != NULL)  {    printf("學號： %d ，姓名： %s/n", p->num, p->name);    p = p->next;  }}

SingleList.h:

#pragma oncetypedef struct student{  int num;        // 學號  char name[128]; // 姓名  struct student *next;}node;class SingleList{public:  SingleList();  ~SingleList();  //建立單鏈表   node *CreatNode();  //單鏈表插入  node *InsertNode(node *head, int num, char* name);  // 計算單鏈表長度  int GetLength(node *head);  //單鏈表刪除某個元素   node *DeleteNode(node *head, int num);  //單鏈表逆序  node *ReverseList(node *head);  //打印單鏈表  void PrintList(node *head);};

關于逆序邏輯，研究了一下：

1、主要思路：

假設有單鏈表A->B->C->D，首先取出首節點A作為新逆序出來的鏈表

這樣，原鏈表就為：B->C->D，逆序后的新鏈表為：A

2. 按照上述方法，依次取出B、C、D放入新鏈表

2、圖形表示：

　　原始的單鏈表: