C++深入分析講解鏈表
更新時間：2022年06月03日 09:30:23 作者：Bright-SKY
當我們在寫一段代碼時，如果要頻繁的在一塊區(qū)域進行插入或者刪除操作時，會發(fā)現(xiàn)用數(shù)組實現(xiàn)會比較復雜，這時候我們就要用另一種數(shù)據(jù)結(jié)構(gòu)，鏈表來實現(xiàn)
鏈表的概述
1、數(shù)組特點
1、空間連續(xù)、元素類型相同、通過下標快速訪問
2、靜態(tài)數(shù)組：空間一旦確定不能更改（動態(tài)數(shù)組除外）
3、靜態(tài)、動態(tài)數(shù)組 插入刪除元素 需要移動大量數(shù)據(jù)
2、鏈表的概述
鏈表是一種物理存儲上非連續(xù)，數(shù)據(jù)元素的邏輯連續(xù)通過鏈表節(jié)點中的指針變量保存下個節(jié)點的地址，實現(xiàn)的一種線性存儲結(jié)構(gòu)。
3、鏈表的特點
鏈表由一系列節(jié)點（鏈表中每一個元素稱為節(jié)點）組成，節(jié)點在運行時動態(tài)生成（malloc，calloc），每個節(jié)點包 括兩個部分：
數(shù)據(jù)域：存放節(jié)點數(shù)據(jù)（核心）
指針域：結(jié)構(gòu)體指針變量 保存下一個節(jié)點的地址
靜態(tài)鏈表
#include <stdio.h>
//設(shè)計節(jié)點類型
typedef struct stu
{
//數(shù)據(jù)域
int num;
char name[32];
float score;
//指針域
struct stu *next;
}STU;
int main(int argc, char const *argv[])
{
//靜態(tài)鏈表的節(jié)點 不是從堆區(qū)申請
STU node1={100, "lucy", 77.7f};
STU node2={101, "bob", 66.7f};
STU node3={102, "tom", 55.7f};
STU node4={103, "hehe", 74.7f};
STU node5={104, "xixi", 73.7f};
//構(gòu)建成鏈表
STU *head = NULL;
head = &node1;
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;
node5.next = NULL;
//遍歷鏈表(從頭節(jié)點 逐個節(jié)點遍歷)
STU *pb = head;
while(pb != NULL)
{
printf("%d %s %f\n", pb->num, pb->name, pb->score);
//移動到下一個節(jié)點
pb = pb->next;
}
return 0;
}
鏈表的操作
增、刪、改、查
學生管理系統(tǒng) 講解鏈表
1、鏈表插入節(jié)點
幫助信息函數(shù)：
void help(void)
{
printf("******************************\n");
printf("* insert:插入鏈表節(jié)點 *\n");
printf("* printf:遍歷鏈表節(jié)點 *\n");
printf("* search:查詢鏈表節(jié)點 *\n");
printf("* delete:刪除鏈表節(jié)點 *\n");
printf("* free:釋放鏈表節(jié)點 *\n");
printf("* quit:遍歷鏈表節(jié)點 *\n");
printf("******************************\n");
return;
}頭部之前插入節(jié)點
STU* insert_link(STU *head, STU tmp)
{
//為插入的節(jié)點申請空間
STU *pi = (STU *)calloc(1,sizeof(STU));
//給空間賦值
*pi = tmp;
pi->next = NULL;
//判斷鏈表是否存在
if(NULL == head)//空
{
head = pi;
//return head;
}
else//非空
{
pi->next = head;
head = pi;
//return head;
}
return head;
}尾部之后插入節(jié)點
//尾部插入節(jié)點
STU* insert_link(STU *head, STU tmp)
{
//為插入的節(jié)點申請空間
STU *pi = (STU *)calloc(1,sizeof(STU));
//給空間賦值
*pi = tmp;
pi->next = NULL;
//判斷鏈表是否存在
if(NULL == head)
{
head = pi;
return head;
}
else
{
//尋找尾部節(jié)點
STU *pb = head;
while(pb->next != NULL)
pb = pb->next;
//將pi插入到 尾節(jié)點后
pb->next = pi;
return head;
}
return head;
}有序插入節(jié)點
//有序插入節(jié)點
STU* insert_link(STU *head, STU tmp)
{
//為插入的節(jié)點申請空間
STU *pi = (STU *)calloc(1,sizeof(STU));
//給空間賦值
*pi = tmp;
pi->next = NULL;
//判斷鏈表是否存在
if(NULL == head)
{
head = pi;
return head;
}
else
{
//尋找插入點
STU *pf = NULL, *pb = NULL;
pf = pb = head;
//從小--->大排序
while((pb->num < pi->num) && (pb->next != NULL))
{
pf = pb;
pb = pb->next;
}
if(pb->num >= pi->num)//頭部插入、中部插入
{
if(pb == head)//頭部插入
{
pi->next = head;
head = pi;
}
else//中部插入
{
pf->next = pi;
pi->next = pb;
}
}
else if(pb->next == NULL)//尾部插入
{
pb->next = pi;
}
}
return head;
}2、遍歷鏈表節(jié)點
void printf_link(STU *head)
{
//1、判斷鏈表是否存在
if(NULL == head)
{
printf("鏈表不存在\n");
return;
}
else//2、鏈表存在，逐個節(jié)點遍歷鏈表
{
STU *pb = head;
while(pb != NULL)
{
printf("%d %s %f\n", pb->num, pb->name, pb->score);
//pb指向下一個節(jié)點
pb = pb->next;
}
}
return;
}3、查詢指定節(jié)點
STU *search_link(STU *head, char *name)
{
//判斷鏈表是否存在
if(NULL == head)
{
printf("鏈表不存在\n");
return NULL;
}
else//鏈表存在
{
//逐個節(jié)點查詢
STU *pb = head;
while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
{
pb = pb->next;
}
if(strcmp(pb->name, name) == 0)//找到
return pb;
else
{
printf("未找到相關(guān)節(jié)點信息\n");
return NULL;
}
}
return NULL;
}4、刪除指定節(jié)點
STU* delete_link(STU *head, char *name)
{
//判斷鏈表是否存在
if(NULL == head)
{
printf("鏈表不存在\n");
return head;
}
else
{
STU *pf =NULL, *pb=NULL;
pf = pb = head;
//尋找刪除點
while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
{
pf = pb;
pb = pb->next;
}
//找到刪除點
if(strcmp(pb->name, name) == 0)
{
if(head == pb)//頭部刪除
{
head= head->next;
}
else//中尾部刪除
{
pf->next = pb->next;
}
//釋放pb
if(pb != NULL)
{
free(pb);
pb=NULL;
}
}
else//未找到刪除點
{
printf("未找到刪除的相關(guān)節(jié)點信息\n");
}
}
return head;
}5、釋放鏈表
STU* free_link(STU *head)
{
//判斷鏈表是否存在
if(NULL == head)
{
printf("鏈表不存在\n");
return head;
}
else//鏈表存在
{
STU *pb = head;
while(pb != NULL)
{
//head紀錄下一個節(jié)點的位置
head = head->next;
//釋放pb指向的節(jié)點
if(pb != NULL)
{
free(pb);
pb = NULL;
}
//pb指向下一個節(jié)點
pb=head;
}
printf("鏈表節(jié)點已經(jīng)完全釋放\n");
}
return head;
}6、鏈表的翻轉(zhuǎn)
STU* reverse_link(STU *head)
{
//判斷鏈表是否存在
if(NULL == head)
{
printf("鏈表不存在\n");
return head;
}
else
{
STU *pb = head->next;
STU *pn = NULL;
//將頭結(jié)點指針域指向NULL
head->next = NULL;
//逐個節(jié)點翻轉(zhuǎn)
while(pb != NULL)
{
//pn紀錄pb->next的節(jié)點
pn = pb->next;
//進行反向連接
pb->next = head;
//移動head到pb上
head = pb;
//pb指向pb的節(jié)點
pb = pn;
}
}
return head;
}7、鏈表的排序
//選擇法對鏈表排序
void sort_link(STU *head)
{
//判斷鏈表是否存在
if(NULL == head)
{
printf("鏈表不存在\n");
return;
}
else
{
STU *p_i = head, *p_j = head;//int i=0, j=0;
while(p_i->next != NULL)//for(i=0;i<n-1; i++)
{
STU *p_min = p_i;//int min = i;
p_j = p_min->next;//j=min+1
while(p_j != NULL)//j<n
{
if(p_min->num > p_j->num)//if(arr[min] > arr[j])
p_min = p_j;//min = j;
p_j = p_j->next;//j++
}
if(p_i != p_min)//if(i != min)
{
//整體交換
STU tmp = *p_i;
*p_i = *p_min;
*p_min = tmp;
//指針域交換
tmp.next = p_i->next;
p_i->next = p_min->next;
p_min->next = tmp.next;
}
p_i = p_i->next;//i++
}
}
return;
}到此這篇關(guān)于C++深入分析講解鏈表的文章就介紹到這了,更多相關(guān)C++鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++輸入一個字符串,把其中的字符按照逆序輸出的兩種方法解析
以下是對C++中輸入一個字符串,把其中的字符按照逆序輸出的兩種方法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-07-07
C語言中6組指針和自增運算符結(jié)合方式的運算順序問題
本文通過代碼實現(xiàn)分析了6種組合：* p++,(* p)++,* (p++),++* p,++( * p), * (++p)，需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細介紹了C++線程中的thread，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了C語言中反斜杠的作用及說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要為大家詳細介紹了opencv檢測直線方法之形態(tài)學方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要為大家詳細介紹了epoll多路復用的一個實例程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要為大家詳細介紹了OpenCV如何提取圖片中曲線，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了?C++?new?和?delete?關(guān)鍵字詳解，文章圍繞主題展開new?和?delete?的使用方法的介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-06-06
VS2017開發(fā)C語言出現(xiàn)“no_init_all“的解決辦法
這篇文章介紹了VS2017開發(fā)C語言出現(xiàn)“no_init_all“的解決辦法，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-12-12
今天小編就為大家分享一篇關(guān)于C++Primer中變量和基本類型的文章，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2021-09-09