快捷導(dǎo)航

C++?實現(xiàn)單鏈表創(chuàng)建、插入和刪除

更新時間：2022年07月13日 09:38:38 作者：Jeff_

這篇文章主要介紹了C++?實現(xiàn)單鏈表創(chuàng)建、插入和刪除方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

C++單鏈表創(chuàng)建、插入和刪除

這里僅提供一種思路。

#include <iostream>
#include <stdio.h>
#include <string>
#include <conio.h>
 
/**
* cstdio是將stdio.h的內(nèi)容用C++頭文件的形式表示出來。
*stdio.h是C標(biāo)準(zhǔn)函數(shù)庫中的頭文件，即：standard buffered input&output。
*提供基本的文字的輸入輸出流操作（包括屏幕和文件等）。
*/
 
/**
*conio是Console Input/Output（控制臺輸入輸出）的簡寫，其中定義了通過控制臺進(jìn)行數(shù)據(jù)輸入和數(shù)據(jù)輸出的函數(shù)，
*主要是一些用戶通過按鍵盤產(chǎn)生的對應(yīng)操作，比如getch()()函數(shù)等等。
*/
 
using namespace std;
 
struct node
{
	int data;
	node *next;
};
typedef struct node node, *list;
 
// 創(chuàng)建單鏈表
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; // 插入節(jié)點(diǎn)
	p0->data = num;// 插入數(shù)據(jù)
 
	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
		{// 插入中間節(jié)點(diǎn) p0,p1和p2位置: p2-> p0 -> p1
			p2->next = p0;
			p0->next = p1;
		}
	}
	else
	{   // 尾部插入節(jié)點(diǎn) 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)// 刪除頭節(jié)點(diǎn)
		{
			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)
		{
			//發(fā)現(xiàn)第一個較大值
			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 << "***創(chuàng)建單鏈表***" << 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 << "****插入節(jié)點(diǎn)****" << endl;
	cout << "Please input the data for inserting operate : ";
	int inData;
	cin >> inData;
	head = insert(head, inData);
	printL(head);
	cout << endl;
 
	cout << "****刪除節(jié)點(diǎn)****" << endl;
	cout << "Please input the data for deleting operate : ";
	int outData;
	cin >> outData;
	head = del(head, outData);
	printL(head);
	cout << endl;
 
	cout << "****進(jìn)行排序****" << endl;
	//第一位地址可以存放指示器，從第二位開始保存數(shù)據(jù)
	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.頭節(jié)點(diǎn)插入和刪除結(jié)果

2.中間節(jié)點(diǎn)插入和刪除結(jié)果

3.尾結(jié)點(diǎn)插入和刪除結(jié)果

C++單鏈表（帶頭結(jié)點(diǎn)）

總結(jié)歸納

頭結(jié)點(diǎn)可以沒有，頭指針必須有。訪問整個鏈表，是用過遍歷頭指針來進(jìn)行的。
這里沒有特別的設(shè)置一個頭指針，因為當(dāng)指針指向整個鏈表 L 時，該指針的實現(xiàn)效果就是頭指針。
關(guān)于函數(shù)中引用的問題，實際上對于帶頭結(jié)點(diǎn)的絕大部分操作，是不需要引用的，因為對于鏈表的任何操作，傳入的實際上都是頭指針（頭結(jié)點(diǎn)），通過頭指針的遍歷訪問后繼結(jié)點(diǎn)。所以，無論是插入刪除還是修改，都不涉及頭指針的改變。但如果是不帶頭指針的單鏈表操作，就需要添加引用，因為當(dāng)插入或刪除第一個位置的元素時，會涉及頭指針的修改，此時的頭指針就是鏈表的第一個元素。
不帶頭結(jié)點(diǎn)的單鏈表，即單鏈表的第一個結(jié)點(diǎn)就存儲數(shù)據(jù)，頭指針也指向第一個結(jié)點(diǎn)；帶頭結(jié)點(diǎn)的單鏈表，第一個結(jié)點(diǎn)是頭結(jié)點(diǎn)，不存儲數(shù)據(jù)，從頭結(jié)點(diǎn)的 next 開始存儲，頭指針可以從頭結(jié)點(diǎn)的 next 開始遍歷。
對于結(jié)點(diǎn)的前插操作，找到對應(yīng)位置的結(jié)點(diǎn)，設(shè)新結(jié)點(diǎn)為該節(jié)點(diǎn)的后繼結(jié)點(diǎn)，將該結(jié)點(diǎn)的 data 后移至新結(jié)點(diǎn)的 data，以此來模擬結(jié)點(diǎn)的后移，并且時間復(fù)雜度為 O(1)，我愿稱之為“偷天換日”。
如果采用尾插法創(chuàng)建單鏈表，可以設(shè)置一個尾指針，指向單鏈表末尾，這樣就不用每次都通過遍歷找到最后一個結(jié)點(diǎn)，但每插入一個都要更新尾指針。這樣的時間復(fù)雜度為O(1)。
在 DeleteNode 函數(shù)中（刪除指定結(jié)點(diǎn)），存在一處 bug ，當(dāng)刪除結(jié)點(diǎn)為最后一個結(jié)點(diǎn)時，由于該結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，該函數(shù)會報錯，初步認(rèn)為只能通過 DeleteNextLNode函數(shù)（刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)）來實現(xiàn)刪除最后一個結(jié)點(diǎn)的操作。
大多數(shù)情況下，單鏈表的查詢、插入、刪除的平均時間復(fù)雜度都是O(n)，因為要遍歷頭結(jié)點(diǎn)開始查找。但如果對指定結(jié)點(diǎn)進(jìn)行插入和刪除，則時間復(fù)雜度為O(1)，因為不需要再通過遍歷找到指定的結(jié)點(diǎn)。要具體分析。
如果不帶頭結(jié)點(diǎn)的單鏈表，則對表頭的操作（插入和刪除）要特殊處理，例如 List_HeadInsert（頭插法創(chuàng)建單鏈表）、ListInsert（按位序插入）。每次插入后都要更新頭指針，而對于帶頭結(jié)點(diǎn)的單鏈表，它的頭指針指向永遠(yuǎn)是頭結(jié)點(diǎn)，只需要修改頭結(jié)點(diǎn)的后繼就可以完成插入。

代碼實現(xiàn)

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
// 單鏈表結(jié)點(diǎn)
struct LNode {
    int data;    // 數(shù)據(jù)域
    LNode *next; // 指針域
};
typedef LNode LNode;     // LNode表示單鏈表的一個結(jié)點(diǎn)
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個結(jié)點(diǎn)
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;
}
// 按值查找：查找數(shù)據(jù)域為e的結(jié)點(diǎn)
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結(jié)點(diǎn)之前插入數(shù)據(jù)e
bool InsertPriorNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s->next = p->next;
    s->data = p->data; // 數(shù)據(jù)后移，模擬結(jié)點(diǎn)后移
    p->next = s;
    p->data = e; // 將前結(jié)點(diǎn)置為新插入的結(jié)點(diǎn)
    return true;
}
// 后插操作：在p結(jié)點(diǎn)之后插入數(shù)據(jù)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個結(jié)點(diǎn)
    InsertNextNode(p, 5244);      // 使用后插法
    /*  // 使用前插法，達(dá)到同樣效果
    LNode *p = GetElem(L, i);
    InsertPriorNode(p, 5244);
    */
    return true;
}
// 刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)
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;
}
// 刪除指定結(jié)點(diǎn)
bool DeleteNode(LNode *p) {
    if (p == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s = p->next;       // q指向被刪除結(jié)點(diǎn)
    p->data = s->data; // 數(shù)據(jù)前移，模擬結(jié)點(diǎn)前移
    p->next = s->next; // 斷開與被刪除結(jié)點(diǎn)的聯(lián)系
    delete s;
    return true;
}
// 按位序刪除
bool ListDelte(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    /*  // 按結(jié)點(diǎn)刪除，實現(xiàn)同樣效果
    LNode *p = GetElem(L, i);  // 被刪除結(jié)點(diǎn)
    e = p->data;
    DeleteNode(p);
    */
    LNode *p = GetElem(L, i - 1);
    e = p->next->data;
    DeleteNextDNode(p);  // 刪除前一結(jié)點(diǎn)的后繼結(jié)點(diǎn)
    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;
}

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: