快捷導(dǎo)航

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

更新時(shí)間：2016年12月18日 12:47:45 投稿：jingxian

下面小編就為大家?guī)?lái)一篇C++ 單鏈表的基本操作(詳解)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

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

1、概念

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。

鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素 + 指針，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。如下圖：

2、鏈表的基本操作

SingleList.cpp:

#include "stdafx.h"
#include "SingleList.h"
#include <cstdlib>
#include <iostream>
#include <string.h>
#include <conio.h>
#include <stdio.h>

/*c++實(shí)現(xiàn)簡(jiǎn)單的單鏈表操作*/
using namespace std;

SingleList::SingleList()
{
  int num;
  char name[128];

  // 創(chuàng)建鏈表
  node *stuList = CreatNode();
  PrintList(stuList);

  // 插入節(jié)點(diǎn)
  printf("\n請(qǐng)輸入要插入的學(xué)生學(xué)號(hào)和姓名，輸入0 0表示結(jié)束.");
  scanf_s("%d%s", &num, name, 100);
  stuList = InsertNode(stuList, num, name);
  PrintList(stuList);

  // 刪除節(jié)點(diǎn)
  printf("\n請(qǐng)輸入要?jiǎng)h除的學(xué)生學(xué)號(hào)：");
  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));  // 為頭結(jié)點(diǎn)分配內(nèi)存空間
  head->next = nullptr;
  p = head;    // p指向頭節(jié)點(diǎn)

  while (cycle)
  {
    printf("\n請(qǐng)輸入學(xué)生的學(xué)號(hào)和姓名:");
    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;    // 指向新插入的節(jié)點(diǎn)
      p = s;    // p指向當(dāng)前節(jié)點(diǎn)
    }
    else
    {
      cycle = 0;
    }
  }

  head = head->next;
  p->next = NULL;
  printf("頭節(jié)點(diǎn)學(xué)生信息為: %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)
    {
      // 插入首節(jié)點(diǎn)
      s->next = p1;
      head = s;
    }
    else
    {
      // 插入中間節(jié)點(diǎn)
      p2->next = s;
      s->next = p1;
    }
  }
  else
  {
    // 插入尾節(jié)點(diǎn)
    p1->next = s;
    s->next = NULL;
  }

  return head;
}

// 計(jì)算單鏈表長(zhǎng)度
int SingleList::GetLength(node *head)
{
  int length = 0;
  node *p;
  p = head;

  while (p != NULL)
  {
    p = p->next;
    length++;
  }
  return length;
}

//單鏈表刪除某個(gè)元素 
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("找不到學(xué)號(hào)為%d 的學(xué)生!\n", num);
  }
  return head;

}

//單鏈表逆序
node *SingleList::ReverseList(node *head)
{
  // A->B->C->D
  node *old_head;    // 原來(lái)鏈表的頭
  node *new_head;    // 新鏈表的頭
  node *cur_head;    // 獲得原來(lái)鏈表的頭

  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;    // 將原來(lái)鏈表的頭取出，并將第二個(gè)節(jié)點(diǎn)作為頭節(jié)點(diǎn)
    cur_head->next = new_head;  // 將取出的頭設(shè)為新鏈表的頭
    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 個(gè)學(xué)生的信息:\n", n);

  p = head;
  while (p != NULL)
  {
    printf("學(xué)號(hào)： %d ，姓名： %s\n", p->num, p->name);
    p = p->next;
  }
}

SingleList.h:

#pragma once
typedef struct student
{
  int num;        // 學(xué)號(hào)
  char name[128]; // 姓名
  struct student *next;
}node;

class SingleList
{
public:
  SingleList();
  ~SingleList();

  //建立單鏈表 
  node *CreatNode();
  //單鏈表插入
  node *InsertNode(node *head, int num, char* name);
  // 計(jì)算單鏈表長(zhǎng)度
  int GetLength(node *head);
  //單鏈表刪除某個(gè)元素 
  node *DeleteNode(node *head, int num);
  //單鏈表逆序
  node *ReverseList(node *head);
  //打印單鏈表
  void PrintList(node *head);

};

關(guān)于逆序邏輯，研究了一下：

1、主要思路：

假設(shè)有單鏈表A->B->C->D，首先取出首節(jié)點(diǎn)A作為新逆序出來(lái)的鏈表

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

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

2、圖形表示：

　　原始的單鏈表: