day20 雙向鏈表

雙向鏈表的函數功能


注意事項?

1.雙向鏈表還需要關注到前指針的指向

2.函數都需要判斷邏輯

3.函數的增刪都要關注到len的變化

4.函數的改查功能都需要遍歷結束的標志NULL

5.注意p->next->prio時,p->next是否指向NULL

創建雙向鏈表頭節點

Node_ptr list_create()

函數功能:申請一個頭結點初始化len

參數:無

返回值:頭結點地址

    //指針接收申請的空間地址Node_ptr L=(Node_ptr)malloc(sizeof(Node));	//判斷邏輯if(L==NULL){printf("申請空間失敗\n");return NULL;}//初始化邏輯L->len=0;L->prio=NULL;L->next=NULL;//返回邏輯return L;

判空函數

int list_empty(Node_ptr head)

函數功能:判斷雙向鏈表是否為空
參數:頭結點地址
返回值:鏈表為空返回1,非空返回0?

return L->next==NULL;

節點封裝函數

Node_ptr list_node_apply(datatype e)

函數功能:申請一個新節點初始化數據域為e
參數:待封裝的數據e
返回值:新節點地址

    //申請空間Node_ptr p=(Node_ptr)malloc(sizeof(Node));//判斷邏輯if(p==NULL){printf("節點空間申請失敗\n");return NULL;}//初始化邏輯p->data=e;p->prio=NULL;p->next=NULL;//返回邏輯return p;

頭插函數

int list_insert_head(Node_ptr head, datatype e)

函數功能:在鏈表頭部插入新節點
參數:頭結點地址,待插入數據e
返回值:成功返回1,失敗返回0

    //節點申請Node_ptr p=list_node_apply(e);//頭插邏輯if(list_empty(L)){//鏈表為空L->next=p;p->prio=L;//長度自增L->len++;return 0;}else{    //鏈表不為空//先確定尾指針的指向p->next=L->next;L->next=p;//再確定頭指針的指向p->prio=L;p->next->prio=p;//長度自增L->len++;//返回邏輯printf("頭插成功\n");return 0;}

尾插函數?

int list_insert_tail(Node_ptr head,datatype e);

函數功能:在鏈表尾部插入新節點
參數:頭結點地址,待插入數據e
返回值:成功返回1,失敗返回0

    //節點申請Node_ptr p=list_node_apply(e);if(p==NULL){printf("尾插失敗\n");return -1;}//遍歷邏輯Node_ptr q=L->next;while(q->next!=NULL) //遍歷到最后一個節點{q=q->next;}//插入邏輯p->next=q->next;q->next=p;p->prio=q;//長度自增L->len++;

?

遍歷函數

void list_show(Node_ptr head)

函數功能:打印雙向鏈表所有節點的數據
參數:頭結點地址
返回值:無

按位置查找節點

Node_ptr list_search_post(Node_ptr head, int post)

函數功能:查找鏈表中指定位置的節點
參數:頭結點地址,位置pos(從1開始)
返回值:找到返回節點地址,失敗返回NULL

任意位置插入

int list_insert_post(Node_ptr head, int post, datatype e)

函數功能:在指定位置插入新節點
參數:頭結點地址,位置post,待插入數據e
返回值:成功返回1,失敗返回0

判斷邏輯

申請空間

插入邏輯?

表長變化

返回邏輯

    //申請空間Node_ptr q=list_node_apply(e);if(q==NULL){printf("插入失敗1\n");return -1;}//post位置查找Node_ptr post_ptr=list_search_post(L,post);//插入邏輯//繼承post節點的指向q->prio=post_ptr->prio;q->prio->next=q;//完善鏈接q的指向q->next=post_ptr;post_ptr->prio=q;//表長變化L->len++;//返回邏輯return 0;	

頭刪函數

int list_delete_head(Node_ptr head)

函數功能:刪除鏈表首元素節點
參數:頭結點地址
返回值:成功返回1,失敗返回0

    Node_ptr p=L->next;//刪除邏輯L->next=p->next;if(L->next!=NULL)L->next->prio=L;//釋放節點,置空free(p);p=NULL;//len自減邏輯L->len--;

尾刪函數

?int list_delete_tail(Node_ptr L)

函數功能:刪除鏈表尾元素節點
參數:頭結點地址
返回值:成功返回1,失敗返回0

    //遍歷邏輯Node_ptr p=L->next;while(p->next!=NULL) //遍歷到最后一個節點{p=p->next;}//刪除邏輯p->prio->next=NULL; //倒數第二個節點置空//長度自減L->len--;

?

任意位置刪除

int list_delete_post(Node_ptr head, int post)

函數功能:刪除指定位置的節點
參數:頭結點地址,位置pos
返回值:成功返回1,失敗返回0

    //查找邏輯Node_ptr p=list_search_post(L,post);//刪除邏輯//最后一個節點只執行一條p->prio->next=p->next;if(p->next!=NULL){   //如果不為最后一個節點p->next->prio=p->prio;}//自減L->len--;//釋放節點,置空free(p);p=NULL;

任意位置修改

int list_updata_post(Node_ptr head, int post, datatype e)

函數功能:修改指定位置節點的數據
參數:頭結點地址,位置pos,新數據e
返回值:成功返回1,失敗返回0

    //查找邏輯Node_ptr p=list_search_post(L,post);//修改邏輯p->data=e;

銷毀鏈表

int list_free(Node_ptr head)

函數功能:釋放雙向鏈表所有節點內存
參數:頭結點地址
返回值:成功返回1,失敗返回0

    //刪除邏輯//結點刪除 Node_ptr p=L->next;while(!list_empty(L)){list_delete_head(L);	}//頭節點刪除free(L);L=NULL;

鏈表與順序表的比較

存儲:1.順序表是一段連續空間存儲,鏈表不一定連續的空間

? ? ? ? ? ?2.順序表是靜態分配空間,鏈表是動態分配空間????????(創建時體現)

? ? ? ? ? ?3.順序表存在存滿的情況,鏈表不存在

? ? ? ? ? ?4.順序表需要提前預估空間,鏈表不需要

時間復雜度
增刪改查
順序表O(n)? ? ? 其他數據元素后移O(1)? ??????對應的元素修改即可
鏈表? ? ? ? ? ?O(1)? ? ? 只需改變指針指向O(n)? ? ? ? 需要遍歷到其位置

因此:增刪鏈表,改查順序表

完整代碼

Dlink.h

#ifndef _Dlink_H
#define _Dlink_H
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char datatype;//定義數據類型
//雙向鏈表
typedef struct Node
{   //數據域union{datatype data;int len;};//指針域struct Node *prio;   //前指針struct Node *next;   //后指針
}Node,*Node_ptr;   //創建雙向鏈表頭節點
Node_ptr list_create();//判空
int list_empty(Node_ptr );//節點封裝函數
Node_ptr list_node_apply(datatype e);//頭插
int list_insert_head(Node_ptr ,datatype );//尾插
int list_insert_tail(Node_ptr,datatype);
//遍歷
void list_show(Node_ptr );//按位置查找返回節點(位置從1開始)
Node_ptr list_search_post(Node_ptr ,int);//任意位置插入數據
int list_insert_post(Node_ptr ,int ,datatype);//頭刪
int list_delete_head(Node_ptr );
//尾刪
int list_delete_tail(Node_ptr );
//任意位置刪除
int list_delete_post(Node_ptr ,int );//任意位置修改
int list_updata_post(Node_ptr ,int ,datatype);//銷毀雙向鏈表
int list_free(Node_ptr );
#endif

Dlink.c

#include"Dlink.h"//創建雙向鏈表
Node_ptr list_create()
{   //指針接收申請的空間地址Node_ptr L=(Node_ptr)malloc(sizeof(Node));	//判斷邏輯if(L==NULL){printf("申請空間失敗\n");return NULL;}//初始化邏輯L->len=0;L->prio=NULL;L->next=NULL;//返回邏輯return L;
}
//判空
//空返回1,非空返回0,非法返回-1
int list_empty(Node_ptr L)
{   //判斷邏輯if(L==NULL){printf("非法地址\n");return -1;}return L->next==NULL;
}
//節點封裝函數
Node_ptr list_node_apply(datatype e)
{//申請空間Node_ptr p=(Node_ptr)malloc(sizeof(Node));//判斷邏輯if(p==NULL){printf("節點空間申請失敗\n");return NULL;}//初始化邏輯p->data=e;p->prio=NULL;p->next=NULL;//返回邏輯return p;
}//頭插
//成功返回0,失敗返回-1
int list_insert_head(Node_ptr L,datatype e)
{//判斷邏輯if(L==NULL){printf("非法地址\n");return -1;}//節點申請Node_ptr p=list_node_apply(e);//頭插邏輯if(list_empty(L)){//鏈表為空L->next=p;p->prio=L;printf("插入成功\n");//長度自增L->len++;return 0;}else{//先確定尾指針的指向p->next=L->next;L->next=p;//再確定頭指針的指向p->prio=L;p->next->prio=p;//長度自增L->len++;//返回邏輯printf("頭插成功\n");return 0;}
}
//尾插
int list_insert_tail(Node_ptr L,datatype e)
{//判斷邏輯if(L==NULL){printf("尾插失敗\n");return -1;}//節點申請Node_ptr p=list_node_apply(e);if(p==NULL){printf("尾插失敗\n");return -1;}//遍歷邏輯Node_ptr q=L->next;while(q->next!=NULL) //遍歷到最后一個節點{q=q->next;}//插入邏輯p->next=q->next;q->next=p;p->prio=q;//長度自增L->len++;//返回邏輯return 0;
}//遍歷
void list_show(Node_ptr L)
{//判斷邏輯if(L==NULL){printf("非法地址\n");}//遍歷邏輯Node_ptr p=L->next; //定義遍歷指針while(p!=NULL){printf("%-4c",p->data); //訪問數據域p=p->next;//指針移到下一個節點}putchar(10);
}//按位置查找返回節點(位置從1開始)
Node_ptr list_search_post(Node_ptr L,int post)
{//判斷邏輯if(list_empty(L)||post<1||post>L->len){printf("post不合理\n");return NULL;}//查找邏輯Node_ptr p=L->next;for (int i=1; i<post; i++){p=p->next;}return p;
}
//任意位置插入數據
int list_insert_post(Node_ptr L,int post,datatype e)
{//判斷邏輯if(post<1||post>L->len+1){printf("插入位置不合理\n");return -1;}//申請空間Node_ptr q=list_node_apply(e);if(q==NULL){printf("插入失敗1\n");return -1;}//post位置查找Node_ptr post_ptr=list_search_post(L,post);//插入邏輯//繼承post節點的指向q->prio=post_ptr->prio;q->prio->next=q;//完善鏈接q的指向q->next=post_ptr;post_ptr->prio=q;//表長變化L->len++;//返回邏輯return 0;		
}//頭刪
int list_delete_head(Node_ptr L)
{//判斷邏輯if(list_empty(L)){printf("頭刪失敗\n");return -1;}Node_ptr p=L->next;//刪除邏輯L->next=p->next;if(L->next!=NULL)L->next->prio=L;//釋放節點,置空free(p);p=NULL;//len自減邏輯L->len--;//返回邏輯return 0;
}
//尾刪
int list_delete_tail(Node_ptr L)
{//判斷邏輯if(L==NULL||list_empty(L)){printf("尾刪失敗\n");return -1;}//遍歷邏輯Node_ptr p=L->next;while(p->next!=NULL) //遍歷到最后一個節點{p=p->next;}//刪除邏輯p->prio->next=NULL; //倒數第二個節點置空//長度自減L->len--;//返回邏輯printf("尾刪成功\n");return 0;}
//任意位置刪除
int list_delete_post(Node_ptr L,int post )
{//判斷邏輯if(list_empty(L)||post<1||post>L->len){printf("位置刪除失敗\n");return -1;}//查找邏輯Node_ptr p=list_search_post(L,post);//刪除邏輯//最后一個節點只執行一條p->prio->next=p->next;if(p->next!=NULL){   //如果不為最后一個節點p->next->prio=p->prio;}//自減L->len--;//釋放節點,置空free(p);p=NULL;//返回邏輯return 0;
}
//任意位置修改
int list_updata_post(Node_ptr L ,int post ,datatype e)
{//判斷邏輯if(list_empty(L)||post<1||post>L->len){printf("修改位置不合理\n");return -1;}//查找邏輯Node_ptr p=list_search_post(L,post);//修改邏輯p->data=e;//返回邏輯return 0;
}
//銷毀雙向鏈表
int list_free(Node_ptr L)
{//判斷邏輯if(L==NULL){printf("銷毀失敗\n");return -1;}//刪除邏輯//結點刪除 Node_ptr p=L->next;while(!list_empty(L)){list_delete_head(L);	}//頭節點刪除free(L);L=NULL;//返回邏輯printf("銷毀成功\n");return 0;
}

?Dmain.c

#include"Dlink.h"
int main(int argc, const char *argv[])
{		//接收申請的空間Node_ptr x=list_create();if(x==NULL){printf("申請失敗\n");return -1;}printf("申請成功\n");//頭插printf("-----------頭插-----------\n");list_insert_head(x,'a');list_insert_head(x,'b');list_insert_head(x,'c');list_insert_head(x,'d');list_insert_head(x,'e');list_insert_head(x,'f');list_insert_head(x,'p');list_insert_head(x,'q');printf("-----------遍歷------------\n");list_show(x);printf("------按位置查找-----------\n");Node_ptr q=list_search_post(x,3);printf("%c\n",q->data);//按位置插入printf("--------位置插入-----------\n");list_insert_post(x,3,'x');list_insert_post(x,x->len,'z');list_show(x);//頭刪printf("----------頭刪-------------\n");list_delete_head(x);list_delete_head(x);list_show(x);//尾刪printf("----------尾刪-------------\n");list_delete_tail(x);list_delete_tail(x);list_show(x);//尾插printf("----------尾插-------------\n");list_insert_tail(x,'D');list_insert_tail(x,'O');list_show(x);//任意位置刪除printf("-------位置刪除------------\n");list_delete_post(x,x->len);list_delete_post(x,2);list_show(x);//任意位置修改printf("-------位置修改------------\n");list_updata_post(x,x->len,'G');list_show(x);printf("-------鏈表銷毀------------\n");list_free(x);return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/90618.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/90618.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/90618.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

[Rust 基礎課程]猜數字游戲-獲取用戶輸入并打印

創建項目 按照之前的章節講的創建一個 Cargo 項目的方法&#xff0c;自己創建一個名為 guessing_game 的 cargo 項目并執行&#xff0c;確保能成功打印出 Hello World。 編寫代碼 使用 RustRover 打開項目&#xff0c;打開 src/main.rs 文件&#xff0c;我們將在這個文件中編寫…

重讀《人件》Peopleware -(22)Ⅲ 適當人選 Ⅵ 樂在其中(上)

本章以一個小測驗開始&#xff1a;問題1&#xff1a;在過去幾年里&#xff0c;你們組織的年員工流失率是多少&#xff1f; 問題2&#xff1a;替換一個離職員工平均需要多少成本&#xff1f;評分標準如下&#xff1a;如果你對這兩個問題有任何答案&#xff0c;則通過&#xff1b…

Go、Node.js、Python、PHP、Java五種語言的直播推流RTMP協議技術實施方案和思路-優雅草卓伊凡

Go、Node.js、Python、PHP、Java五種語言的直播推流RTMP協議技術實施方案和思路-優雅草卓伊凡既然我們甲方要做直播私有化&#xff0c;既然我們做了這么多年系統&#xff0c;我們對直播的理解很深&#xff0c;那么我們2025年就應該用更先進的技術棧&#xff0c;不然怎么讓我們的…

SpringBoot 集成Mybatis Plus

一、為什么SpringBoot不推薦使用MybatisSpring Boot 不推薦使用 MyBatis&#xff0c;主要源于二者在設計理念、生態融合和開發風格上的差異。Spring Boot 強調“約定優于配置”&#xff0c;追求高效的開發體驗和統一的框架風格。它通過自動配置和依賴注入&#xff0c;將復雜的基…

PI 思維升級 PI設計的典范轉移:從阻抗思維到諧振控制

們先來回想一件事&#xff0c;根據歐姆定律&#xff0c;阻抗是不是越低越好&#xff1f; 代表即使有很大的瞬時電流&#xff0c;瞬間的電壓降也不會超過某個極限&#xff01;理論上是&#xff01; 可是這其實忽略了兩個關鍵的要素&#xff1a;PDN阻抗有諧振&#xff1a;諧振代表…

如何制定企業級服務器安全策略(Security Policy)

制定一套**企業級服務器安全策略&#xff08;Security Policy&#xff09;**對于保護服務器資源、數據安全和業務連續性至關重要。以下是制定安全策略的詳細指南&#xff0c;包括安全策略的核心要素、實施步驟和具體措施&#xff0c;幫助企業構建全面的服務器安全防護體系。1. …

n1 armbian docker compose 部署aipan mysql

apt update apt install docker-compose-plugin -y #安裝docker compose docker compose version Docker Compose version v2.38.2 sudo mkdir -p /sda1/data/mysql/conf.d sudo chown -R 999:999 /sda1/data/mysql # MySQL 用戶 UID 通常為 999 cat docker-compose.yml vers…

RAG情境化分段向量模型voyage-context-3,聚焦分段細節,融入全局文檔上下文

最近看到一個有意思的工作&#xff0c;原文來自&#xff1a; https://blog.voyageai.com/2025/07/23/voyage-context-3/?utm_sourceTWITTER&utm_mediumORGANIC_SOCIAL voyage-context-3&#xff1a;聚焦分段細節&#xff0c;融入全局文檔上下文 概要&#xff1a; Voyage A…

計算機體系結構中的中斷服務程序ISR是什么?

計算機體系結構中的中斷服務程序ISR是什么&#xff1f; 在計算機體系結構中&#xff0c;中斷服務程序&#xff08;Interrupt Service Routine, ISR&#xff09; 是操作系統或硬件直接調用的關鍵代碼模塊&#xff0c;用于響應來自硬件設備、軟件異常或系統事件的中斷信號。其核心…

開源項目XBuilder前端框架

spx-gui/ 配置文件package.json 項目依賴和腳本配置vite.config.ts Vite構建工具配置tsconfig.json TS項目配置主文件tsconfig.app.json 應用程序的TS配置tsconfig.node.json Node.js環境的TS配置index.html 應用入口HTML文件src/ 源碼目錄main.ts 應用入口文件&#xff0c;初始…

0723 單項鏈表

Part 1.完成單向鏈表&#xff0c;并完成下面功能1.單鏈表節點創建鏈表是物理空間上不連續的一個結構&#xff0c;需要創建一個next作為指向下一個節點的指針&#xff0c;所以需要建立一個結構體包含數據域&#xff0c;next指針域&#xff0c;記錄長度的數據域。因為長度只有頭節…

基于 ASP.NET Web 應用程序(.NET Framework)的花店系統

1.1功能模塊實現1.1.1整體結構界面由兩部分組成&#xff1a;左側導航欄、右側內容展示區。使用了 Bootstrap 5 的樣式庫&#xff0c;并結合了 ASP.NET MVC 的 Html.ActionLink 和 Razor 條件判斷語句來動態生成菜單項。1.1.2導航欄功能模塊導航欄基礎結構導航欄基礎結構使用 Bo…

C++ Qt6 CMake qml文件啟動方式說明

在Qt6之后,Qt程序默認使用CMake進行構建,當然也可以使用qmake, 本篇博客介紹Qt6.8之前和Qt6.8版本中QtQuick程序的啟動方式。 在QtQuick程序main.cpp里qml的文件啟動分為兩種:(1)直接加載qml文件,(2)加載qml模塊,下面分別介紹這兩種啟動方式。 方式1:直接啟動qml文…

字符串 “asdasjkfkasgfgshaahsfaf” 經過哈夫曼編碼之后存儲比特數是多少?

要計算字符串 “asdasjkfkasgfgshaahsfaf” 經過哈夫曼編碼后的存儲比特數&#xff0c;需按以下步驟進行&#xff1a;步驟 1&#xff1a;統計字符出現頻率先統計字符串中每個字符的出現次數&#xff1a;a&#xff1a;出現 6 次s&#xff1a;出現 6 次d&#xff1a;出現 1 次j&a…

什么是游戲盾(高防版)?

隨著網絡游戲產業的快速發展&#xff0c;游戲服務器的安全問題日益受到關注。DDoS攻擊、CC攻擊等網絡威脅常常導致游戲卡頓、斷線甚至服務器宕機&#xff0c;嚴重影響玩家體驗。游戲盾&#xff08;高防版&#xff09;是一種專為游戲業務設計的網絡安全防護服務&#xff0c;集成…

openGauss數據庫在CentOS 7 中的單機部署與配置

部署 版本選擇 通過openGuass官網下載地址 &#xff0c;我們可以看到它支持x86_64與Aarch64兩種平臺&#xff0c;又分成openEuler 22、openEuler 20、Centos 7以及Docker 版本。 進入CentOS 7標簽&#xff0c;看到又分成企業版、輕量版、極簡版與分布式鏡像版。 本文只討論…

HTTP響應狀態碼詳解

HTTP 響應狀態碼&#xff08;HTTP Status Code&#xff09;是服務器在響應客戶端請求時返回的 3 位數字代碼&#xff0c;用于表示請求的處理狀態。以下是常見的 HTTP 狀態碼及其含義&#xff1a; 1xx&#xff08;信息性狀態碼&#xff09; 表示請求已被接收&#xff0c;需要繼…

Pytorch中register_buffer和torch.nn.Parameter的異同

說下register_buffer和Parameter的異同 相同點方面描述追蹤都會被加入 state_dict&#xff08;模型保存時會保存下來&#xff09;。與 Module 的綁定都會隨著模型移動到 cuda / cpu / float() 等而自動遷移。都是 nn.Module 的一部分都可以通過模塊屬性訪問&#xff0c;如 self…

吉吉巳資源整站源碼完整打包,適用于搭建資源聚合/整合類站點,全網獨家,拿來就用

想要搭建一個資源整合站點&#xff0c;如影視聚合類站點、資訊聚合類站點、圖集聚合類站點等&#xff0c;需要花費大量的時間來查找合適的系統或源碼。然后要去測試&#xff0c;修復bug&#xff0c;一直到能夠正常的運營使用&#xff0c;花費的時間絕對不短&#xff0c;今天分享…

嵌入式學習的第三十五天-進程間通信-HTTP

TCP/IP協議模型&#xff1a;應用層&#xff1a;HTTP;傳輸層&#xff1a;TCP UDP;網絡層&#xff1a;IPv4 IPv6網絡接口層一、HTTP協議1. 萬維網WWW(World Wide Web) 世界范圍內的&#xff0c;聯機式的信息儲藏所。 萬維網解決了獲取互聯網上的數據時需要解決的以下問題&#x…