C++編程語言實現(xiàn)單鏈表詳情
更新時間：2021年10月08日 08:51:09 作者：tyl2021
這篇文章主要介紹的是利用C語言實現(xiàn)單鏈表，實現(xiàn)的是鏈表中最簡單的一種單鏈表且每個結點中只含有一個指針域，下面將詳細舉例說明,需要的朋友可以參考一下
一、單鏈表簡單介紹
首先，我們再回顧一下線性表的兩種存儲方式——順序存儲與鏈式存儲
上圖左邊為順序存儲，右邊為鏈式存儲
之前我們利用數(shù)組來實現(xiàn)順序表，對于順序表的優(yōu)點缺點，總結來說就是，查找方便，增刪復雜。
線性表之順序存儲的優(yōu)缺點
而鏈表特點可以說恰恰相反，增刪方便，查找復雜。
今天實現(xiàn)的是鏈表中最簡單的一種——單鏈表（每個結點中只含有一個指針域）
對于鏈表我們只知道它每個結點的存儲的物理地址是不連續(xù)的，但邏輯上還是符合線性表“一對一”的特點。因此，我們就需要用“線”（指針）把這些不連續(xù)的結點按順序連接起來。
鏈表的結點在內存中存儲不連續(xù)
通過指針把每個結點按順序連起來
到這里我們可以發(fā)現(xiàn)，要想表示鏈表中的結點，光存儲結點的數(shù)據(jù)是不夠的，還得有指針。因此，單鏈表的結點結構如下：
數(shù)據(jù)域存儲數(shù)據(jù)，指針域存儲指針
//================線性表的單鏈表存儲結構=================
typedef struct LNode {
ElemType data;//數(shù)據(jù)域
struct LNode *next;//指針域
}LNode;
注意：因為指針是指向每個結點的，也就是指向struct LNode這個自定義的結構體類型，所以指針的類型就是struct LNode*。
二、下面我們先實現(xiàn)單鏈表的初始化。
單鏈表的初始化其實就是創(chuàng)建幾個結點，然后用指針把他們連接起來。
先創(chuàng)建一個頭指針，實際上就是創(chuàng)建一個頭結點，然后頭指針指向頭結點就OK
LNode* CreateList_L(int n) {//順位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L
LNode *p = (LNode*)malloc(sizeof(LNode));//創(chuàng)建頭結點（p也就是頭指針）
LNode *temp = p;//聲明一個指針指向頭結點,用于遍歷鏈表(不是頭指針，因為它只是暫時指向頭結點)
//生成鏈表
for (int i = n; i > 0; --i)
{
LNode *node = (LNode *)malloc(sizeof(LNode));//創(chuàng)建結點
if (node){//分配地址成功
scanf_s("%c", &(node->data));
node->next = NULL;
//建立新結點與直接前驅結點的邏輯關系
temp->next = node;
temp = temp->next;
}
else {//如果分配地址失敗，則返回錯誤信息
printf("結點創(chuàng)建失??！\n");
}
}
return p;
}
三、實現(xiàn)單鏈表的插入與刪除數(shù)據(jù)
單鏈表插數(shù)據(jù)情況
觀察可知，我們要實現(xiàn)插入操作，需要的操作是一樣的。
S1：將后繼結點的指針賦給新結點的指針域；
S2：將前驅節(jié)點的指針域改為指向新結點的指針。
注意：S1和S2不能換順序。
//===============================算法2.9==========================
Status ListInsert_L(LNode *L, int i, ElemType e) {
//在帶頭結點的單鏈表L中第i個位置之前插入元素e
int j = 0;
LNode *p = L;
while (p&&j < i - 1) {
p = p->next;
++j;
}//尋找第i-1個結點
if (!p || j > i - 1)return ERROR;//i小于1或者大于表長時
LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的結點
s->data = e; s->next = p->next;//S1
p->next = s;//S2
return OK;
}
單鏈表刪除數(shù)據(jù)示意圖
觀察可知，只需要將待刪結點的前驅結點的指針域的值換成待刪結點的后繼結點的指針即可。
//=====================算法2.10=================================
Status ListDelete_L(LNode *L, int i, ElemType *e) {
//在帶頭結點的單鏈表L中，刪除第i個元素，并由e返回其值
LNode *p = L;
int j = 0;
while (p->next&&j < i - 1) {//尋找第i個結點，并令p指向其前驅
p = p->next; ++j;
}
if (!(p->next) || j > i - 1)return ERROR;//刪除位置不合理
LNode *q = p->next; p->next = q->next;//刪除并釋放結點
*e = q->data; free(q);
return OK;
}
三、參考代碼實現(xiàn)與截圖
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define ElemType char
typedef int Status;
//================線性表的單鏈表存儲結構==================
typedef struct LNode {
ElemType data;//數(shù)據(jù)域
struct LNode *next;//指針域
}LNode;
LNode* CreateList_L(int n) {//順位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L
LNode *p = (LNode*)malloc(sizeof(LNode));//創(chuàng)建頭結點
LNode *temp = p;//聲明一個指針指向頭結點,用于遍歷鏈表(不是頭指針)
//生成鏈表
for (int i = n; i > 0; --i)
{
LNode *node = (LNode *)malloc(sizeof(LNode));//創(chuàng)建結點
if (node){//分配地址成功
scanf_s("%c", &(node->data));
node->next = NULL;
//建立新結點與直接前驅結點的邏輯關系
temp->next = node;
temp = temp->next;
}
else {//如果分配地址失敗，則返回錯誤信息
printf("結點創(chuàng)建失??！\n");
}
}
return p;
}
//===============================算法2.9==========================
Status ListInsert_L(LNode *L, int i, ElemType e) {
//在帶頭結點的單鏈表L中第i個位置之前插入元素e
int j = 0;
LNode *p = L;
while (p&&j < i - 1) {
p = p->next;
++j;
}//尋找第i-1個結點
if (!p || j > i - 1)return ERROR;//i小于1或者大于表長時
LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的結點
s->data = e; s->next = p->next;
p->next = s;
return OK;
}
//=====================算法2.10=================================
Status ListDelete_L(LNode *L, int i, ElemType *e) {
//在帶頭結點的單鏈表L中，刪除第i個元素，并由e返回其值
LNode *p = L;
int j = 0;
while (p->next&&j < i - 1) {//尋找第i個結點，并令p指向其前驅
p = p->next; ++j;
}
if (!(p->next) || j > i - 1)return ERROR;//刪除位置不合理
LNode *q = p->next; p->next = q->next;//刪除并釋放結點
*e = q->data; free(q);
return OK;
}
void display(LNode *L) {
LNode *temp =L;//將temp指針重新指向頭結點
//只要temp指針指向的結點的next不是Null，就執(zhí)行輸出語句。
while (temp->next) {
temp = temp->next;
printf("%c", temp->data);
}
printf("\n");
}
int main() {
LNode *L = NULL;
L=CreateList_L(5);
display(L);
ListInsert_L(L, 2, 'Y');
display(L);
ElemType e;
ListDelete_L(L, 2, &e);
display(L);
printf("返回值為：%c", e);
system("pause");
return 0;
}
初始化鏈表為abcdef，在第2個位置插入Y，然后刪除Y
到此這篇關于C++編程語言實現(xiàn)單鏈表詳情的文章就介紹到這了,更多相關C++編程語言實現(xiàn)單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
想研究std::invalid_argument的朋友可以參考下2013-01-01
教你Visual?Studio?2022如何新建一個C語言工程(圖文詳解)
這篇文章主要介紹了Visual?Studio?2022如何新建一個C語言工程,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-09-09
這篇文章主要介紹了用遞歸算法解決島嶼問題的流程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-10-10
正如標題所說，我們不要被C++語法中所描述的那些條條框框所“蒙騙”了。的確，相信這些生成規(guī)則不會對我們的編程帶來多大的影響（不會產(chǎn)生錯誤），但是只有了解它們的背后操作，我們才知道編譯器究竟為我們做了什么,感興趣的朋友可以了解下,希望本文對你有所幫助2013-01-01
這篇文章主要介紹了C語言實現(xiàn)“幸運數(shù)”的實例詳解的相關資料,需要的朋友可以參考下2017-07-07
這篇文章主要為大家詳細介紹了C++實現(xiàn)迷宮游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了C語言中靜態(tài)關鍵字static的作用，對大家學習C語言非常有幫助，有需求的小伙伴可以參考下2020-05-05
詳解如何在VS2019和VScode中配置C++調用python接口
這篇文章主要介紹了詳解如何在VS2019和VScode中配置C++調用python接口，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
堆是計算機科學中一類特殊的數(shù)據(jù)結構的統(tǒng)稱，通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。而堆排序是利用堆這種數(shù)據(jù)結構所設計的一種排序算法。本文將通過圖片詳細介紹堆排序，需要的可以參考一下2022-06-06
這篇文章主要介紹了C++11 原生字符串的相關資料，幫助大家更好的理解和學習c++11,感興趣的朋友可以了解下2020-08-08