雙向鏈表的函數功能
注意事項?
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;
}