东莞网站公司排名,百度推广最简单方法,海南建设交易中心网站,设计网站的制作框架一、双向链表的结构 注意#xff1a;这里的“带头”跟前面我们说的“头节点”是两个概念#xff0c;带头链表里的头节点#xff0c;实际为“哨兵位”#xff0c;哨兵位节点不存储任何有效元素#xff0c;只是站在这里“放哨的”。 “哨兵位”存在的意义#xff1a;遍历循…一、双向链表的结构 注意这里的“带头”跟前面我们说的“头节点”是两个概念带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这里“放哨的”。 “哨兵位”存在的意义遍历循环链表避免死循环。 二、双向链表的实现
2.1 双向链表结点的创建
typedef int DLType;
//创建结构体
typedef struct DList
{DLType data;struct DList* prev;struct DList* next;
}DL;2.2 双向链表的初始化与销毁
//初始化phead
DL* init(void)
{DL* phead BuyNewNode(0);return phead;
}//销毁链表这里需要主要phead是形参这里的最后将phead置空并不能将原链表中的phead置空
//因此原链表中的phead需要手动置空详细实现见源码
void DLDesdroy(DL* phead)
{assert(phead);DL* tail phead-next;while (tail ! phead){DL* next tail-next;free(tail); tail next;}free(phead);phead NULL;
}2.3 双向链表的增删查改
由于多次创建结点因此我们将它提炼为一个函数
//创造新的节点
DL* BuyNewNode(DLType x)
{DL* newnode (DL*)malloc(sizeof(DL));if (newnode NULL){perror(malloc is failed!\n);return 1;}newnode-data x;newnode-next newnode-prev newnode;return newnode;
}//尾插
void DLPushBack(DL* phead,DLType x)
{assert(phead);DL* newnode BuyNewNode(x);newnode-next phead;phead-prev-next newnode;newnode-prev phead-prev;phead-prev newnode;
}//尾删
void DLPopBack(DL* phead)
{assert(phead);assert(phead-next ! phead);DL* tail phead-prev;DL* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL; }//头插
void DLPushFront(DL* phead, DLType x)
{assert(phead);DL* newnode BuyNewNode(x);DL* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prevphead;
}//头删
void DLPopFront(DL* phead)
{assert(phead);assert(phead-next ! phead);DL* first phead-next;DL* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}//查找
DL* DLFind(DL* phead,DLType x)
{assert(phead);DL* cur phead-next;while ( cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//pos位置插入数据
void DLInsert(DL* pos,DLType x)
{assert(pos);DL* newnode BuyNewNode(x);DL* prev pos-prev;prev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}//pos位置之后插入数据
void DLInsertAfter(DL* pos, DLType x)
{assert(pos);DL* newnode BuyNewNode(x);DL* next pos-next;newnode-next next;next-prev newnode;pos-next newnode;newnode-prev pos;
}//删除pos位置元素
void DLErase(DL* pos)
{assert(pos);DL* next pos-next;DL* prev pos-prev;prev-next next;next-prev prev;free(pos);pos NULL;
}2.4 双向链表的打印
//打印链表
void DLPrint(DL* phead)
{DL* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}2.5 双向链表的源码
//DL.h#pragma once#includestdio.h
#includestdlib.h
#includeassert.htypedef int DLType;typedef struct DList
{DLType data;struct DList* prev;struct DList* next;
}DL;//初始化
DL* init(void);
//打印
void DLPrint(DL* phead);//尾插、尾删
void DLPushBack(DL* phead, DLType x);
void DLPopBack(DL* phead);//头插、头删
void DLPushFront(DL* phead, DLType x);
void DLPopFront(DL* phead);//查找
DL* DLFind(DL* phead, DLType x);//指定位置插入数据、指定位置之后插入数据
void DLInsert(DL* pos, DLType x);
void DLInsertAfter(DL* pos, DLType x);//删除pos
void DLErase(DL* phead);void DLDesdroy(DL** phead);//DL.c
#include DList.h//创造新的节点
DL* BuyNewNode(DLType x)
{DL* newnode (DL*)malloc(sizeof(DL));if (newnode NULL){perror(malloc is failed!\n);return 1;}newnode-data x;newnode-next newnode-prev newnode;return newnode;
}//初始化phead
DL* init(void)
{DL* phead BuyNewNode(0);return phead;
}//打印链表
void DLPrint(DL* phead)
{DL* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}//尾插
void DLPushBack(DL* phead,DLType x)
{assert(phead);DL* newnode BuyNewNode(x);newnode-next phead;phead-prev-next newnode;newnode-prev phead-prev;phead-prev newnode;
}//尾删
void DLPopBack(DL* phead)
{assert(phead);assert(phead-next ! phead);DL* tail phead-prev;DL* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL; }//头插
void DLPushFront(DL* phead, DLType x)
{assert(phead);DL* newnode BuyNewNode(x);DL* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prevphead;
}//头删
void DLPopFront(DL* phead)
{assert(phead);assert(phead-next ! phead);DL* first phead-next;DL* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}//查找
DL* DLFind(DL* phead,DLType x)
{assert(phead);DL* cur phead-next;while ( cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//pos位置插入数据
void DLInsert(DL* pos,DLType x)
{assert(pos);DL* newnode BuyNewNode(x);DL* prev pos-prev;prev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}//pos位置之后插入数据
void DLInsertAfter(DL* pos, DLType x)
{assert(pos);DL* newnode BuyNewNode(x);DL* next pos-next;newnode-next next;next-prev newnode;pos-next newnode;newnode-prev pos;
}//删除
void DLErase(DL* pos)
{assert(pos);DL* next pos-next;DL* prev pos-prev;prev-next next;next-prev prev;free(pos);pos NULL;
}//销毁链表
void DLDesdroy(DL* phead)
{assert(phead);DL* tail phead-next;while (tail ! phead){DL* next tail-next;free(tail); tail next;}free(phead);phead NULL;
}
