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 #include #include 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,非法返回-1int 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，失败返回-1int 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)||postL->len){printf(\"post不合理\\n\");return NULL;}//查找逻辑Node_ptr p=L->next;for (int i=1; inext;}return p;}//任意位置插入数据int list_insert_post(Node_ptr L,int post,datatype e){//判断逻辑if(postL->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)||postL->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)||postL->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;}