长春网站建设长春,湖南人文科技学院官网首页,泸县做网站公司,p2p网站开发公司一、带头双向循环链表的定义和结构
1、定义 带头双向循环链表#xff0c;有一个数据域和两个指针域。一个是前驱指针#xff0c;指向其前一个节点#xff1b;一个是后继指针#xff0c;指向其后一个节点。 // 定义双向链表的节点
typedef struct ListNode
{LTDataType dat…一、带头双向循环链表的定义和结构
1、定义 带头双向循环链表有一个数据域和两个指针域。一个是前驱指针指向其前一个节点一个是后继指针指向其后一个节点。 // 定义双向链表的节点
typedef struct ListNode
{LTDataType data; // 数据域struct ListNode* prev; // 前驱指针struct ListNode* next; // 后继指针
}ListNode; 2、结构 带头双向循环链表在所有的链表当中 结构最复杂一般用在 单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多 优势实现反而简单了。 二、带头双向循环链表接口的实现
1、创建文件 test.c主函数、测试顺序表各个接口功能List.c带头双向循环链表接口函数的实现List.h带头双向循环链表的类型定义、接口函数声明、引用的头文件 2、List.h 头文件代码
// List.h
// 带头双向循环链表增删查改实现
#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int LTDataType;// 定义双向链表的节点
typedef struct ListNode
{LTDataType data; // 数据域struct ListNode* prev; // 前驱指针struct ListNode* next; // 后继指针
}ListNode;// 动态申请一个新节点
ListNode* BuyListNode(LTDataType x);
// 创建返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 双向链表的判空
bool ListEmpty(ListNode* phead);
// 获取双向链表的元素个数
size_t ListSize(ListNode* phead); 三、在 List.c 上是西安各个接口函数
1、动态申请一个新结点
// 动态申请一个新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
} 2、创建返回链表的头结点初始化头结点
// 创建返回链表的头结点
ListNode* ListCreate()
{ListNode* phead (ListNode*)malloc(sizeof(ListNode)); // 哨兵位头结点phead-next phead;phead-prev phead;return phead;
}
也可以用下面这个函数道理一样
// 初始化链表
void ListInit(ListNode** pphead)
{*pphead BuyListNode(-1); // 动态申请一个头节点(*pphead)-prev *pphead; // 前驱指针指向自己(*pphead)-next *pphead; // 后继指针指向自己
}头指针初始指向 NULL初始化链表时需要改变头指针的指向使其指向头节点所以这里需要传二级指针。 初始化带头双向循环链表首先动态申请一个头结点头结点的前驱和后继指针都指向自己形成一个循环。 3、双向链表的销毁
// 双向链表的销毁
void ListDestroy(ListNode** pphead)
{assert(pphead);assert(*pphead);ListNode* cur (*pphead)-next;while (cur ! *pphead){ListNode* next cur-next; // 记录cur的直接后继节点free(cur);cur next;}free(*pphead); // 释放头节点*pphead NULL; // 置空头指针
}销毁链表最后要将头指针 plist 置空所以用了二级指针来接收。这里也可以用一级指针但要在函数外面置空 plist 。 一级指针写法 void ListDestroy(ListNode* phead)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){ListNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
} 4、双向链表的打印
// 打印双向链表
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur phead-next; // 记录第一个节点printf(head - );while (cur ! phead){printf(%d - , cur-data);cur cur-next;}printf(head\n);
}5、双向链表的尾插
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead); // 头指针不能为空/* ListNode* newnode BuyListNode(x); // 动态申请一个节点ListNode* tail phead-prev; // 记录尾节点tail-next newnode; // 尾节点的后继指针指向新节点newnode-prev tail; //2、新节点的前驱指针指向尾节点newnode-next phead; // 新节点的后继指针指向头节点phead-prev newnode; // 头节点的前驱指针指向新节点 */ListInsert(phead, x);
} 6、双向链表的尾删
// 双向链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead-next ! phead); // 只剩头节点时 链表为空 不能再继续删除/* ListNode* tail phead-prev; // 记录尾节点ListNode* tailPrev tail-prev; // 记录尾节点的直接前驱tailPrev-next phead; // 尾节点的前驱节点的next指针指向头节点phead-prev tailPrev; // 头节点的prev指针指向尾节点的前驱节点free(tail); // 释放尾节点 */ListErase(pHead-prev);
}7、双向链表的头插
// 双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);/* ListNode* newnode BuyListNode(x); // 申请新节点ListNode* pheadNext phead-next; // 记录第一个节点// 头节点和新节点建立链接phead-next newnode;newnode-prev phead;// 新节点和第一个节点建立链接newnode-next pheadNext;pheadNext-prev newnode; */ListInsert(phead-next, x);
}8、双向链表的头删
// 双向链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead-next ! phead); // 只剩头节点时 链表为空 不能再继续删除/* ListNode* pheadNext phead-next; // 记录第一个节点// 头节点和第一个节点的后继节点建立链接phead-next pheadNext-next;pheadNext-next-prev phead;free(pheadNext); // 头删 */ListErase(phead-next);
} 9、查找双向链表中的元素
// 在双向链表中查找元素并返回该元素的地址
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur; //找到了 返回该元素的地址}cur cur-next;}return NULL; //没找到 返回NULL
}10、在指定pos位置之前插入元素
// 在指定pos位置之前插入元素
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode BuyListNode(x); // 申请一个节点ListNode* posPrev pos-prev; // 记录pos的直接前驱// pos的直接前驱和新节点建立链接posPrev-next newnode;newnode-prev posPrev;// 新节点和pos建立链接newnode-next pos;pos-prev newnode;
} 实现了该函数后可以尝试改进头插函数pos相当于链表的第一个节点和尾插函数pos相当于链表的头节点这样写起来更简便。 11、删除指定pos位置的元素
// 删除指定pos位置的元素
void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev pos-prev; // 记录pos的直接前驱ListNode* posNext pos-next; // 记录pos的直接后继// pos的直接前驱和直接后继建立链接posPrev-next posNext;posNext-prev posPrev;free(pos); // 释放pos位置的元素//pos NULL;
} 实现了该函数后可以尝试改进头删函数pos相当于链表的第一个节点和尾删函数pos相当于链表的最后一个节点这样写起来更简便。 12、双向链表的判空
// 双向链表的判空
bool ListEmpty(ListNode* phead)
{ assert(phead);return phead-next phead; //为空 返回ture 否则返回false
} 13、获取双向链表的元素个数
// 获取双向链表的元素个数
size_t ListSize(ListNode* phead)
{assert(phead);size_t size 0;ListNode* cur phead-next; // 记录第一个节点while (cur ! phead){size;cur cur-next;}return size;
} 四、代码整合
// List.c
#include List.h// 动态申请一个新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
}// 创建返回链表的头结点
ListNode* ListCreate()
{ListNode* phead (ListNode*)malloc(sizeof(ListNode)); // 哨兵位头结点phead-next phead;phead-prev phead;return phead;
}// 双向链表的销毁
void ListDestroy(ListNode** pphead)
{assert(pphead);assert(*pphead);ListNode* cur (*pphead)-next;while (cur ! *pphead){ListNode* next cur-next; // 记录cur的直接后继节点free(cur);cur next;}free(*pphead); // 释放头节点*pphead NULL; // 置空头指针
}// 打印双向链表
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur phead-next; // 记录第一个节点printf(head - );while (cur ! phead){printf(%d - , cur-data);cur cur-next;}printf(head\n);
}// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead); // 头指针不能为空ListInsert(phead, x);
}// 双向链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead-next ! phead); // 只剩头节点时 链表为空 不能再继续删除ListErase(pHead-prev);
}// 双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}// 双向链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead-next ! phead); // 只剩头节点时 链表为空 不能再继续删除ListErase(phead-next);
}// 在双向链表中查找元素并返回该元素的地址
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur; //找到了 返回该元素的地址}cur cur-next;}return NULL; //没找到 返回NULL
}// 在指定pos位置之前插入元素
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode BuyListNode(x); // 申请一个节点ListNode* posPrev pos-prev; // 记录pos的直接前驱// pos的直接前驱和新节点建立链接posPrev-next newnode;newnode-prev posPrev;// 新节点和pos建立链接newnode-next pos;pos-prev newnode;
}// 删除指定pos位置的元素
void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev pos-prev; // 记录pos的直接前驱ListNode* posNext pos-next; // 记录pos的直接后继// pos的直接前驱和直接后继建立链接posPrev-next posNext;posNext-prev posPrev;free(pos); // 释放pos位置的元素//pos NULL;
}// 双向链表的判空
bool ListEmpty(ListNode* phead)
{ assert(phead);return phead-next phead; //为空 返回ture 否则返回false
}// 获取双向链表的元素个数
size_t ListSize(ListNode* phead)
{assert(phead);size_t size 0;ListNode* cur phead-next; // 记录第一个节点while (cur ! phead){size;cur cur-next;}return size;
}
