C语言中带头双向循环链表基本操作的实现详解
目录
- 一、概念与结构
- 二、基本操作的实现
- 1.创建结点
- 2.初始化链表
- 3.打印链表
- 4.尾插
- 5.尾删
- 6.头插
- 7.头删
- 8.查找某个数并返回其指针
- 9.在某个位置之前插入
- 10.删除某个位置
- 11.判断链表是否为空
- 12.计算链表中有效值的个数
- 13.销毁链表
- 三、测试代码
一、概念与结构
无头单向非循环链表结构简单,一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。而带头双向循环链表的结构较为复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表,虽然它的结构复杂但是因为结构优势用代码实现起来会变得简单。
二、基本操作的实现
1.创建结点
LTNode* BuyListNode(ListDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->val = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }
2.初始化链表
void ListInit(LTNode** pphead)//初始化 { *pphead = (LTNode*)malloc(sizeof(LTNode)); *pphead = BuyListNode(-1); (*pphead)->next = *pphead; (*pphead)->prev = *pphead; } //LTNode* ListInit()//初始化 //{ // LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1; // phead->next = phead; // phead->prev = phead; // return phead; //}
初始化链表有两种方式,一种是有返回类型(注释部分),另一种是在初始化函数中给结构体开辟空间(不过注意参数要为二级指针)。因为是带头结点的循环链表,所以prev和next指针都指向自己。
3.打印链表
void ListPrint(LTNode* phead)//打印 { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
注意while循环的结束条件,保证能够打印链表中的所有有效值。要对头结点进行assert判断,不能为空。
4.尾插
void ListPushBack(LTNode* phead, ListDataType x)//尾插 { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; newnode->next = tail->next; phead->prev = newnode; newnode->prev = tail; tail->next = newnode; //ListInsert(phead, x); }
5.尾删
void ListPopBack(LTNode* phead)//尾删 { assert(phead); assert(phead->next != phead); LTNode* prevnode = phead->prev; prevnode->prev->next = phead; phead->prev = prevnode->prev; free(prevnode); //ListErase(phead->prev); }
尾删时要注意判断phead->next != phead,不能删除头结点,同时记得要free(prevnode)释放删除后的空间。
6.头插
void ListPushFront(LTNode* phead, ListDataType x)//头插 { assert(phead); LTNode* tail = phead->next; LTNode* newnode = BuyListNode(x); tail->prev = newnode; newnode->next = tail; newnode->prev = phead; phead->next = newnode; //ListInsert(phead->next,x); }
7.头删
void ListPopFront(LTNode* phead)//头删 { assert(phead); assert(phead->next != phead); LTNode* tail = phead->next; phead->next = tail->next; tail->next->prev = phead; //ListErase(phead->next); }
8.查找某个数并返回其指针
LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针 { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; }
9.在某个位置之前插入
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入 { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* tail = pos->prev; tail->next = newnode; newnode->prev = tail; newnode->next = pos; pos->prev = newnode; }
10.删除某个位置
void ListErase(LTNode* pos)//删除pos位置 { assert(pos); LTNode* prevnode = pos->prev; LTNode* nextnode = pos->next; free(pos); prevnode->next = nextnode; nextnode->prev = prevnode; /*pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos);*/ }
11.判断链表是否为空
bool ListEmpty(LTNode* phead)//判断是否为空,如果是空,返回true { assert(phead); return phead->next == phead; }
12.计算链表中有效值的个数
size_t ListSize(LTNode* phead)//计算链表中有效值的个数 { assert(phead); size_t size = 0; LTNode* tail = phead->next; while (tail != phead) { size++; tail = tail->next; } return size; }
13.销毁链表
void ListDestroy(LTNode* phead)//销毁链表 { assert(phead); LTNode* tail = phead->next; while (tail != phead) { LTNode* nextnode = tail->next; free(tail); tail = nextnode; } free(phead); }
销毁链表时要注意要保证每个结点都释放,同时最后也要将头结点释放free(phead)。
三、测试代码
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int ListDataType; typedef struct ListNode { ListDataType val; struct ListNode* prev; struct ListNode* next; }LTNode; LTNode* BuyListNode(ListDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->val = x; newnode->prev = NULL; newnode->next = NULL; return newnode; } void ListInit(LTNode** pphead)//初始化 { *pphead = (LTNode*)malloc(sizeof(LTNode)); *pphead = BuyListNode(-1); (*pphead)->next = *pphead; (*pphead)->prev = *pphead; } //LTNode* ListInit()//初始化 //{ // LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1; // phead->next = phead; // phead->prev = phead; // return phead; //} void ListPrint(LTNode* phead)//打印 { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); } void ListPushBack(LTNode* phead, ListDataType x)//尾插 { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; newnode->next = tail->next; phead->prev = newnode; newnode->prev = tail; tail->next = newnode; //ListInsert(phead, x); } void ListPopBack(LTNode* phead)//尾删 { assert(phead); assert(phead->next != phead); LTNode* prevnode = phead->prev; prevnode->prev->next = phead; phead->prev = prevnode->prev; free(prevnode); //ListErase(phead->prev); } void ListPushFront(LTNode* phead, ListDataType x)//头插 { assert(phead); LTNode* tail = phead->next; LTNode* newnode = BuyListNode(x); tail->prev = newnode; newnode->next = tail; newnode->prev = phead; phead->next = newnode; //ListInsert(phead->next,x); } void ListPopFront(LTNode* phead)//头删 { assert(phead); assert(phead->next != phead); LTNode* tail = phead->next; phead->next = tail->next; tail->next->prev = phead; //ListErase(phead->next); } LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针 { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; } void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入 { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* tail = pos->prev; tail->next = newnode; newnode->prev = tail; newnode->next = pos; pos->prev = newnode; } void ListErase(LTNode* pos)//删除pos位置 { assert(pos); LTNode* prevnode = pos->prev; LTNode* nextnode = pos->next; free(pos); prevnode->next = nextnode; nextnode->prev = prevnode; /*pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos);*/ } bool ListEmpty(LTNode* phead)//判断是否为空,如果是空,返回true { assert(phead); return phead->next == phead; } size_t ListSize(LTNode* phead)//计算链表中有效值的个数 { assert(phead); size_t size = 0; LTNode* tail = phead->next; while (tail != phead) { size++; tail = tail->next; } return size; } void ListDestroy(LTNode* phead)//销毁链表 { assert(phead); LTNode* tail = phead->next; while (tail != phead) { LTNode* nextnode = tail->next; free(tail); tail = nextnode; } free(phead); } void TestList() { //LTNode* plist = ListInit(&plist); LTNode* plist = NULL; ListInit(&plist); ListPushBack(plist, 100); ListPushBack(plist, 200); ListPushBack(plist, 300); ListPushBack(plist, 400); ListPushBack(plist, 500); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPrint(plist); ListPushFront(plist, 1000); ListPushFront(plist, 2000); ListPushFront(plist, 3000); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); LTNode* pos = ListFind(plist, 1000); if (pos != NULL) { ListInsert(pos, 500); ListErase(pos); } ListPrint(plist); if (!ListEmpty(plist)) printf("%d\n", ListSize(plist)); } int main() { TestList(); return 0; }
以上就是C语言中带头双向循环链表基本操作的实现详解的详细内容,更多关于C语言 带头双向循环链表的资料请关注我们其它相关文章!
赞 (0)