網站首頁 編程語言 正文
C++單鏈表創建、插入和刪除
這里僅提供一種思路。
#include <iostream>
#include <stdio.h>
#include <string>
#include <conio.h>
/**
* cstdio是將stdio.h的內容用C++頭文件的形式表示出來。
*stdio.h是C標準函數庫中的頭文件，即：standard buffered input&output。
*提供基本的文字的輸入輸出流操作（包括屏幕和文件等）。
*/
/**
*conio是Console Input/Output（控制臺輸入輸出）的簡寫，其中定義了通過控制臺進行數據輸入和數據輸出的函數，
*主要是一些用戶通過按鍵盤產生的對應操作，比如getch()()函數等等。
*/
using namespace std;
struct node
{
int data;
node *next;
};
typedef struct node node, *list;
// 創建單鏈表
node *creat()
{
node *head, *p;
head = new node;
p = head;
int x, cycle = 1;
while (cycle)
{
cout << "Please input the data for single linker : ";
cin >> x;
if (x != 0)
{
node *s = new node;
s->data = x;
cout << "Input data : " << x << endl;
p->next = s;
p = s;
}
else
{
cycle = 0;
cout << "Input done! " << endl;
}
}
head = head->next;
p->next = NULL;
//cout << "\nFirst data of single linker is " << head->data << endl;
return head;
}
// 單鏈表測長
int length(node *head)
{
int n = 0;
node *p = head;
while (p != NULL)
{
p = p->next;
n++;
}
return n;
}
// 單鏈表打印
void printL(node *head)
{
node *p = head;
while (p != NULL)
{
cout << "Single Linker data is " << p->data << endl;
p = p->next;
}
}
// 單鏈表插入
node *insert(node *head, int num)
{
node *p0, *p1, *p2;
p1 = head;
p2 = new node;
p0 = new node; // 插入節點
p0->data = num;// 插入數據
while (p0->data > p1->data && p1->next != NULL)
{
p2 = p1;
p1 = p1->next;// p0,p1和p2位置: p2->p1->p0
}
if (p0->data <= p1->data)
{
if (p1 == head)
{// 頭部前段插入 p0和p1位置: p0->p1->...
head = p0;
p0->next = p1;
}
else
{// 插入中間節點 p0,p1和p2位置: p2-> p0 -> p1
p2->next = p0;
p0->next = p1;
}
}
else
{ // 尾部插入節點 p0,p1和p2位置: p2->p1->p0->NULL
p1->next = p0;
p0->next = NULL;
}
return head;
}
// 單鏈表刪除
node *del(node *head, int num)
{
node *p1, *p2;
p2 = new node;
p1 = head;
while (num != p1->data && p1->next != NULL)
{
p2 = p1;
p1 = p1->next;// p1和p2位置: p2->p1
}
if (num == p1->data)
{
if (p1 == head)// 刪除頭節點
{
head = p1->next;
delete p1;
}
else
{
p2->next = p1->next;
delete p1;
}
}
else
{
cout << num << " could not been found in the current single linker!" << endl;
}
return head;
}
//=============插入排序====================
node *insertSort( node *head )
{
node *p1, *prep1, *p2, *prep2, *temp;
prep1 = head->next;
p1 = prep1->next;
//prep1和p1是否需要手動后移
bool flag;
while (p1 != NULL)
{
flag = true;
temp = p1;
//由于是單向鏈表，所以只能從頭部開始檢索
for (prep2 = head, p2 = head->next; p2 != p1; prep2 = prep2->next, p2 = p2->next)
{
//發現第一個較大值
if (p2->data > p1->data)
{
p1 = p1->next;
prep1->next = p1;
prep2->next = temp;
temp->next = p2;
flag = false;
break;
}
}
//手動后移prep1和p1
if (flag)
{
prep1 = prep1->next;
p1 = p1->next;
}
}
return head;
}
int main()
{
cout << "***創建單鏈表***" << endl;
node *head = creat();
cout << endl;
cout << "***計算鏈表長***" << endl;
int n = length(head);
cout << "The length of input single linker is " << n << "." << endl;
cout << endl;
cout << "***打印單鏈表***" << endl;
printL(head);
cout << endl;
cout << "****插入節點****" << endl;
cout << "Please input the data for inserting operate : ";
int inData;
cin >> inData;
head = insert(head, inData);
printL(head);
cout << endl;
cout << "****刪除節點****" << endl;
cout << "Please input the data for deleting operate : ";
int outData;
cin >> outData;
head = del(head, outData);
printL(head);
cout << endl;
cout << "****進行排序****" << endl;
//第一位地址可以存放指示器，從第二位開始保存數據
node *mylist = new node[sizeof(node)];
mylist->data = 0;
mylist->next = NULL;
int len = length(head);
int i = 0;
node * cur = mylist;
node *headcopy = head;
while (len--)
{
//node * newNode = (node *)malloc(sizeof(node));
node *newNode = new node[sizeof(node)];
newNode->data = headcopy->data;
newNode->next = NULL;
cur->next = newNode;
cur = cur->next;
headcopy=headcopy->next;
}
head = insertSort(mylist);
head = del(head, 0);
printL(head);
return 0;
}1.頭節點插入和刪除結果
2.中間節點插入和刪除結果
3.尾結點插入和刪除結果
C++單鏈表（帶頭結點）
總結歸納
- 頭結點可以沒有，頭指針必須有。訪問整個鏈表，是用過遍歷頭指針來進行的。
- 這里沒有特別的設置一個頭指針，因為當指針指向整個鏈表 L 時，該指針的實現效果就是頭指針。
- 關于函數中引用的問題，實際上對于帶頭結點的絕大部分操作，是不需要引用的，因為對于鏈表的任何操作，傳入的實際上都是頭指針（頭結點），通過頭指針的遍歷訪問后繼結點。所以，無論是插入刪除還是修改，都不涉及頭指針的改變。但如果是不帶頭指針的單鏈表操作，就需要添加引用，因為當插入或刪除第一個位置的元素時，會涉及頭指針的修改，此時的頭指針就是鏈表的第一個元素。
- 不帶頭結點的單鏈表，即單鏈表的第一個結點就存儲數據，頭指針也指向第一個結點；帶頭結點的單鏈表，第一個結點是頭結點，不存儲數據，從頭結點的 next 開始存儲，頭指針可以從頭結點的 next 開始遍歷。
- 對于結點的前插操作，找到對應位置的結點，設新結點為該節點的后繼結點，將該結點的 data 后移至新結點的 data，以此來模擬結點的后移，并且時間復雜度為 O(1)，我愿稱之為“偷天換日”。
- 如果采用尾插法創建單鏈表，可以設置一個尾指針，指向單鏈表末尾，這樣就不用每次都通過遍歷找到最后一個結點，但每插入一個都要更新尾指針。這樣的時間復雜度為O(1)。
- 在 DeleteNode 函數中（刪除指定結點），存在一處 bug ，當刪除結點為最后一個結點時，由于該結點沒有后繼結點，該函數會報錯，初步認為只能通過 DeleteNextLNode函數（刪除p結點的后繼結點）來實現刪除最后一個結點的操作。
- 大多數情況下，單鏈表的查詢、插入、刪除的平均時間復雜度都是O(n)，因為要遍歷頭結點開始查找。但如果對指定結點進行插入和刪除，則時間復雜度為O(1)，因為不需要再通過遍歷找到指定的結點。要具體分析。
- 如果不帶頭結點的單鏈表，則對表頭的操作（插入和刪除）要特殊處理，例如 List_HeadInsert（頭插法創建單鏈表）、ListInsert（按位序插入）。每次插入后都要更新頭指針，而對于帶頭結點的單鏈表，它的頭指針指向永遠是頭結點，只需要修改頭結點的后繼就可以完成插入。
代碼實現
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
// 單鏈表結點
struct LNode {
int data; // 數據域
LNode *next; // 指針域
};
typedef LNode LNode; // LNode表示單鏈表的一個結點
typedef LNode *LinkList; // LinkList表示一個單鏈表
// 初始化單鏈表
void InitList(LinkList &L) {
L = new LNode;
// L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
}
// 判斷單鏈表是否為空
bool Empty(LinkList &L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
// 獲取單鏈表長度
int GetLength(LinkList &L) {
LNode *p = L->next;
int length = 0;
while (p != NULL) {
p = p->next;
length++;
}
return length;
}
// 按位查找：查找第i個結點
LNode *GetElem(LinkList &L, int i) {
if (i < 0) {
return NULL; // i值不合法
}
LNode *p = L;
int j = 0;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
// 按值查找：查找數據域為e的結點
LNode *GetLNode(LinkList &L, int e) {
LNode *p = L->next;
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}
// 頭插法建立單鏈表
LinkList List_HeadInsert(LinkList &L) {
int e;
cin >> e;
while (e != 9999) {
LNode *s = new LNode;
s->data = e;
s->next = L->next;
L->next = s;
cin >> e;
}
return L;
}
// 尾插法建立單鏈表
LinkList List_TailInsert(LinkList &L) {
LNode *r = L; // r為尾指針
int e;
cin >> e;
while (e != 9999) {
LNode *s = new LNode;
s->next = r->next;
s->data = e;
r->next = s;
r = s; // 將r置為新的尾指針
cin >> e;
}
r->next = NULL; // 尾指針的next置為NULL
return L;
}
// 前插操作：在p結點之前插入數據e
bool InsertPriorNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *s = new LNode;
s->next = p->next;
s->data = p->data; // 數據后移，模擬結點后移
p->next = s;
p->data = e; // 將前結點置為新插入的結點
return true;
}
// 后插操作：在p結點之后插入數據e
bool InsertNextNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *q = new LNode;
q->data = e;
q->next = p->next;
p->next = q;
return true;
}
// 按位序插入
bool InserstList(LinkList &L, int i, int e) {
if (i < 1) { // i值不合法
return false;
}
LNode *p = GetElem(L, i - 1); // 遍歷查找i-1個結點
InsertNextNode(p, 5244); // 使用后插法
/* // 使用前插法，達到同樣效果
LNode *p = GetElem(L, i);
InsertPriorNode(p, 5244);
*/
return true;
}
// 刪除p結點的后繼結點
bool DeleteNextDNode(LNode *p) {
if (p == NULL || p->next == NULL) {
return false;
}
LNode *s = new LNode;
s = p->next;
p->next = s->next;
delete s;
return true;
}
// 刪除指定結點
bool DeleteNode(LNode *p) {
if (p == NULL) {
return false;
}
LNode *s = new LNode;
s = p->next; // q指向被刪除結點
p->data = s->data; // 數據前移，模擬結點前移
p->next = s->next; // 斷開與被刪除結點的聯系
delete s;
return true;
}
// 按位序刪除
bool ListDelte(LinkList &L, int i, int &e) {
if (i < 1) {
return false;
}
/* // 按結點刪除，實現同樣效果
LNode *p = GetElem(L, i); // 被刪除結點
e = p->data;
DeleteNode(p);
*/
LNode *p = GetElem(L, i - 1);
e = p->next->data;
DeleteNextDNode(p); // 刪除前一結點的后繼結點
return true;
}
// 遍歷單鏈表
void TraverseList(LinkList &L) {
if (L->next == NULL) {
return;
}
LNode *p = L->next; // 指向頭指針
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
LinkList L;
InitList(L);
L = List_TailInsert(L); // 尾插法
// L = List_HeadInsert(L); // 頭插法
TraverseList(L);
InserstList(L, 1, 5244);
TraverseList(L);
int e = -1;
ListDelte(L, 3, e);
cout << "被刪除的值：" << e << endl;
TraverseList(L);
cout << "長度：" << GetLength(L) << endl;
return 0;
}原文鏈接：https://blog.csdn.net/weixin_40539125/article/details/82491073
相關推薦
- 2024-03-24 required a single bean, but 2 were found
- 2022-06-30 MongoDB排序時內存大小限制與創建索引的注意事項詳解_MongoDB
- 2022-11-08 Numpy安裝、升級與卸載的詳細圖文教程_python
- 2022-03-26 .Net?Core微服務rpc框架GRPC通信基礎_基礎應用
- 2022-03-22 聚合函數和group?by的關系（理解group by 和聚合函數）
- 2022-10-17 VSCode安裝Django插件后實現html語法提示的方法步驟_python
- 2022-07-10 DHCP服務配置——CentOS/Windows2003
- 2022-05-27 python繪制棉棒圖的方法詳解_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速