©2020-2024 ioDraw All rights reserved
带头结点的双向循环链表的实现
038-List.h
#define _CRT_SECURE_NO_WARNINGS 1 //带头结点 typedef int LTDataType; typedef
struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType
data; }ListNode; //创建新结点 ListNode* BuyListNode(LTDataType x); //初始化 ListNode*
ListInit(); //尾插 void ListPushBack(ListNode* phead, LTDataType x); //头插 void
ListPushFront(ListNode* phead, LTDataType x); //尾删 void ListPopBack(ListNode*
phead); //头删 void ListPopFront(ListNode* phead); //查找 ListNode*
ListFind(ListNode* phead, LTDataType x); //前一个位置插入 void ListInsert(ListNode*
pos, LTDataType x); //删除pos位 void ListErase(ListNode* pos); //链表判空，空返回1，非空返回0
int ListEmpty(ListNode* phead); //链表大小 int ListSize(ListNode* phead); //链表销毁
void ListDestroy(ListNode* phead);
038-List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "038-List.h" #include<stdio.h>
#include<stdlib.h> #include<assert.h> //带头结点 void ListPrint(ListNode* phead) {
ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data);
cur = cur->next; } printf("\n"); } //创建新结点 ListNode* BuyListNode(LTDataType x)
{ ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->prev =
NULL; newNode->next = NULL; newNode->data = x; return newNode; } //初始化
ListNode* ListInit() { ListNode* phead = BuyListNode(0); phead->prev = phead;
phead->next = phead; return phead; } //尾插 void ListPushBack(ListNode* phead,
LTDataType x) { ListNode* tail = phead->prev; ListNode* newNode =
BuyListNode(x); tail->next = newNode; newNode->prev = tail; newNode->next =
phead; phead->prev = newNode; } //头插 void ListPushFront(ListNode* phead,
LTDataType x) { ListNode* first = phead->next; ListNode* newNode =
BuyListNode(x); newNode->next = first; first->prev = newNode; phead->next =
newNode; newNode->prev = phead; } //尾删 void ListPopBack(ListNode* phead) {
assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev;
ListNode* tailprev = tail->prev; free(tail); tailprev->next = phead;
phead->prev = tailprev; } //头删 //如果只有一个结点，那么就有问题 void ListPopFront(ListNode*
phead) { assert(phead); assert(phead->next != phead); ListNode* first =
phead->next; ListNode* second = first->next; free(first); phead->next = second;
second->prev = phead; } //查找 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; } //在前一个位置插入
void ListInsert(ListNode* pos, LTDataType x) { //assert(phead); ListNode* prev
= pos->prev; ListNode* newNode = BuyListNode(x); newNode->next = pos; pos->prev
= newNode; prev->next = newNode; newNode->prev = prev; } //删除pos位 void
ListErase(ListNode* pos) { ListNode* prev = pos->prev; ListNode* next =
pos->next; prev->next = next; next->prev = prev; free(pos); } //链表判空，空返回1，非空返回0
int ListEmpty(ListNode* phead) { return phead->next == phead ? 1 :
0;//头结点的下一个是否指向头结点自己 } //链表大小 int ListSize(ListNode* phead) { assert(phead);
int size = 0; ListNode* cur = phead->next; while (cur != phead) { size++; cur =
cur->next; } return size; } //链表销毁 void ListDestroy(ListNode* phead) {
assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode*
next = cur->next; free(cur); cur = next; } free(phead); }
038-test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "038-List.h" #include<stdio.h>
#include<assert.h> //带头结点 testList1() { ListNode* plist = ListInit();
ListPushBack(plist, 1); ListPrint(plist); ListPushBack(plist, 1);
ListPrint(plist); ListPushFront(plist, 2); ListPrint(plist);
ListPushBack(plist, 3); ListPrint(plist); ListPopBack(plist); ListPrint(plist);
ListPopFront(plist); ListPrint(plist); ListPushFront(plist, 4);
ListPrint(plist); ListPushFront(plist, 5); ListPrint(plist); ListNode* pos =
ListFind(plist, 5); ListInsert(pos, 100); ListErase(pos); ListPrint(plist);
printf("%d", ListSize(plist)); ListDestroy(plist); plist = NULL; } int main() {
testList1(); return 0; }