C++ 單鏈表的根本操作(詳解)。本站提示廣大學習愛好者：（C++ 單鏈表的根本操作(詳解)）文章只能為提供參考，不一定能成為您想要的結果。以下是C++ 單鏈表的根本操作(詳解)正文
鏈表不斷是面試的高頻題，明天先總結一下單鏈表的運用，下節再總結雙向鏈表的。本文次要有單鏈表的創立、拔出、刪除節點等。
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 once
typedef 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、圖形表示：
原始的單鏈表:
<!--[endif]-->
初始形態時，單鏈表如上圖所示，head指向頭節點A。
1. 取出原始鏈表的第一個節點A，然後將該節點作為新鏈表的頭節點
原始鏈表：
<!--[endif]-->
新鏈表：
<!--[if !vml]--> <!--[endif]-->
<!--[if !supportLists]--> 2.然後同上處置：
原始鏈表：
<!--[if !vml]--> <!--[endif]-->
新鏈表：
<!--[if !vml]--> <!--[endif]-->
以上這篇C++ 單鏈表的根本操作(詳解)就是分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持。
