C语言实现带头双向循环链表的接口 C语言实现带头双向循环链表的

本文实例为大家分享了C语言实现带头双向循环链表的接口，供大家参考，具体内容如下
【C语言实现带头双向循环链表的接口】各函数功能如下
申请空间

ListNode* BuyListNode(LTDataType x){ ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = https://www.it610.com/article/x; return node; }

初始化

ListNode* ListInit(){ ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }

指定位置插入

void ListInsert(ListNode* pos, LTDataType x){ assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

头插

void ListPushFront(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* first = phead->next; //ListNode* newnode = BuyListNode(x); phead newnode first //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; ListInsert(phead->next, x); //实现了指定位置插入后，可以套用}

尾插

void ListPushBack(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* tail = phead->prev; //ListNode* newnode = BuyListNode(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); }

指定位置删除

void ListErase(ListNode* pos){ assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }

头删

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; ListErase(phead->next); }

尾删

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; ListErase(phead->prev); }

查找

ListNode* ListFind(ListNode* phead, LTDataType x){ assert(phead); ListNode* cur = phead->next; while (cur) {if (cur->data =https://www.it610.com/article/= x){return cur; }cur = cur->next; } return NULL; }

判空

int ListEmpty(ListNode* phead){ assert(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 ListDestory(ListNode* phead){ assert(phead); ListNode* cur = phead->next; while (cur != phead) {ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }

List.h

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include #include #include typedef int LTDataType; typedef struct ListNode{ struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //打印void ListPrint(ListNode* phead); //申请空间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); //删除void ListErase(ListNode* pos); //空返回1，非空返回0int ListEmpty(ListNode* phead); //元素个数int ListSize(ListNode* phead); //链表销毁void ListDestory(ListNode* phead);

List.c

#include "List.h"ListNode* BuyListNode(LTDataType x){ ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = https://www.it610.com/article/x; return node; }ListNode* ListInit(){ ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }//打印void ListPrint(ListNode* phead){ ListNode* cur = phead->next; while (cur != phead) {printf("%d ", cur->data); cur = cur->next; } puts("\n------------------------------------------------\n"); }void ListPushBack(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* tail = phead->prev; //ListNode* newnode = BuyListNode(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); }//头插void ListPushFront(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* first = phead->next; //ListNode* newnode = BuyListNode(x); phead newnode first //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; ListInsert(phead->next, x); }//尾删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; ListErase(phead->prev); }//头删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; ListErase(phead->next); }//查找ListNode* ListFind(ListNode* phead, LTDataType x){ assert(phead); ListNode* cur = phead->next; while (cur) {if (cur->data =https://www.it610.com/article/= x){return cur; }cur = cur->next; } return NULL; }//插入void ListInsert(ListNode* pos, LTDataType x){ assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }//删除void ListErase(ListNode* pos){ assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }//空返回1，非空返回0int ListEmpty(ListNode* phead){ assert(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 ListDestory(ListNode* phead){ assert(phead); ListNode* cur = phead->next; while (cur != phead) {ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }

test.c

#include "List.h"void TestList1(){ ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 0); ListPushFront(plist, -1); ListPushFront(plist, -2); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListDestory(plist); plist = NULL; }int main(){ TestList1(); return 0; }

总结链表优点：
1.按需申请内存，需要存一个数据，就申请一块内存。不存在空间浪费。
2.任意位置O(1)时间内插入删除数据

链表缺点：
1.不支持下标的随机访问
2.缓存命中率相对低。

顺序表优点
1.按下标去进行随机访问
2.cpu高速缓存命中率比较高

顺序表缺点
1.空间不够需要增容。（一定程序的性能消耗），可能存在一定的空间浪费
2.头部或者中间插入删除数据，需要挪动数据，效率比较低->O(N)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。