北京网站建设cnevo,莱州网页,WordPress文章链接重定向,运城网站建设维护前言
在双向链表之前#xff0c;如果需要查看单链表来复习一下#xff0c;链接在这里#xff1a;
http://t.csdnimg.cn/Ib5qS
1.双向链表 1.1 链表的分类
实际中链表的结构非常多样#xff0c;以下情况组合起来就有8种链表结构#xff1a;
1.1.1 单向或者双向 1.1.2 …前言
在双向链表之前如果需要查看单链表来复习一下链接在这里
http://t.csdnimg.cn/Ib5qS
1.双向链表 1.1 链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1.1.1 单向或者双向 1.1.2 带头或者不带头 1.1.3 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了今天我们就来实现这种代码。 1.2 双向链表的实现
DList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include DList.hLTNode* BuyLTNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(Malloc fail);exit(-1);}node-data x;node-next NULL;return node;
}
LTNode* LTInit()
{LTNode* phead BuyLTNode(-1);phead-next phead;phead-prev phead;return phead;
}void LTPrint(LTNode * phead)
{assert(phead);printf(phead);LTNode* cur phead-next;while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//LTNode* tail phead-prev;//LTNode* newnode BuyLTNode(x);//newnode-prev tail;//tail-next newnode;//newnode-next phead;//phead-prev newnode;LTInsert(phead-prev, x);}void LTPopBack(LTNode* phead)
{LTNode* del NULL;//assert(phead);//if (phead-prev ! phead)//链表指向自己说明为空//{// del phead-prev;// phead-prev phead-prev-prev;// phead-prev-next phead;//}//else// printf(链表为空无需尾删);//free(del);LTErase(phead-prev);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//newnode-next phead-next; //先改变新插入的值以免链表断开//newnode-prev phead;//phead-next-prev newnode; //改变原本第二个节点的值//phead-next newnode; //改变为第一个节点//更稳妥的办法双指针//LTNode* newnode BuyLTNode(x);//LTNode* first phead-next;//phead-next newnode;//newnode-prev phead;//newnode-next first;//first-prev newnode;LTInsert(phead-next, x);
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//LTNode* first phead-next;//LTNode* second first-next;//free(first);//phead-next second;//second-prev phead;LTErase(phead-next);
}int LTSize(LTNode* phead)
{assert(phead);int size 0;LTNode* cur phead-next;while (cur ! NULL){size;cur cur-next;}return size;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode BuyLTNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;}
//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev pos-prev;LTNode* posNext pos-next;free(pos);posPrev-next posNext;posNext-prev posPrev;
}//寻找值
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);assert(phead-next);LTNode* pos phead-next;while (pos){if (pos-data x){return pos;}pos pos-next;}
}//删除表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}
}
DList.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;
//申请空间
LTNode* BuyLTNode(LTDataType x);
//初始化指针
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//记录个数
int LTSize(LTNode* phead);
//pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//寻找值
LTNode* LTFind(LTNode* phead, LTDataType x);
//删除表
void LTDestroy(LTNode* phead);test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include DList.hvoid TestList1()
{LTNode* plist NULL;plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist, 99);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* testlist LTFind(plist, 5);LTPrint(testlist);}
int main()
{TestList1();}
