赞
踩
上一篇文章讲述了线性表中的顺序表,这篇文章讲述关于链表的定义、类别、实现、多种不同链表的优缺点和链表与顺序表的优缺点。
关于上一篇文章的链接:线性表之顺序表
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
#pragma once #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> // slist.h typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode* plist);
#include "slist.h" SListNode* BuySListNode(SLTDateType x) { //创造新节点 SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc"); return NULL; } //新节点初始化 newnode->data = x; newnode->next = NULL; return newnode; } void SListPushBack(SListNode** pplist, SLTDateType x) { //这里使用二级指针的原因是: //若链表为空,需要改变的就是结构体指针,需要结构体指针的地址 //若传入的是一级指针,这里传入的只是临时拷贝,无法改变函数外的变量 if (*pplist == NULL) { *pplist = BuySListNode(x); } //若不为空,需要改变的是结构体,只需要结构体的指针 else { SListNode* tail = *pplist; SListNode* newnode = BuySListNode(x); while (tail->next) { tail = tail->next; } tail->next = newnode; } } void SListPrint(SListNode* plist) { while (plist) { printf("%d->", plist->data); plist = plist->next; } printf("NULL"); } void SListPushFront(SListNode** pplist, SLTDateType x) { //这里使用二级指针的原因是:每次头删都需要改变头节点 SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; } //无头单链表尾删删除节点的时候有三种情况 void SListPopBack(SListNode** pplist) { //没有节点 assert(*pplist); //一个节点 if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } //多个节点 else { //尾删既可以找尾找尾的前一个节点,也可以创造一个变量记录尾节点的前一个节点 //创造一个变量记录尾节点的前一个节点 // SListNode* tail = *pplist; // SListNode* prev = NULL; // while (tail->next) // { // prev = tail; // tail = tail->next; // } // free(prev->next); // prev->next = NULL; //找尾找尾的前一个节点 SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //无头单链表头删删除节点的时候有三种情况,但只有一个节点和多个节点的情况可以合并 void SListPopFront(SListNode** pplist) { //无节点时 assert(*pplist); //有节点时 SListNode* del = *pplist; *pplist = del->next; free(del); } SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } void SListInsertAfter(SListNode* pos, SLTDateType x) { //断言:在pos后面插入一个节点,最差的情况是pos为尾节点,但不能为NULL assert(pos); SListNode* cur = (SListNode*)malloc(sizeof(SListNode)); if (cur == NULL) { perror("malloc"); return; } cur->data = x; cur->next = pos->next; pos->next = cur; } void SListEraseAfter(SListNode* pos) { //需要删除节点的前一个节点不能为NULL,删除节点也不能为NULL assert(pos); assert(pos->next); SListNode* next = pos->next; pos->next = next->next; free(next); } void SListDestroy(SListNode* plist) { SListNode* del = NULL; while (plist) { del = plist; plist = plist->next; free(del); } }
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
#include "list.h" // 创建返回链表的头结点. ListNode* ListCreate() { ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); if (phead == NULL) { perror("malloc"); return NULL; } //让头的 next 和 prev 都指向自己 //则双向链表为空 phead->next = phead; phead->prev = phead; return phead; } // 创造新节点 ListNode* BuyTLNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->data = x; return newnode; } // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { /*ListNode* tail = pHead->prev; ListNode* newnode = BuyTLNode(x); newnode->next = pHead; newnode->prev = tail; tail->next = newnode; pHead->prev = newnode;*/ ListInsert(pHead, x); //复用 } // 双向链表打印 void ListPrint(ListNode* pHead) { printf("header <--> "); //打印的时候,由于头内的 data 的值没用 //则从头的的下一个节点开始打印 //并且在循环到头的时候打印结束 ListNode* cur = pHead ->next; while (cur != pHead) { printf("%d <--> ", cur->data); cur = cur->next; } printf("\n"); } // 判断双向链表是否为空 bool LTEmpty(ListNode* pHead) { assert(pHead); return pHead->next == pHead; } // 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); assert(!(LTEmpty(pHead))); /*ListNode* first = pHead->next; ListNode* second = first->next; pHead->next = second; second->prev = pHead; free(first);*/ ListErase(pHead->next); //复用 } // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { /*ListNode* next = pHead->next; ListNode* newnode = BuyTLNode(x); newnode->next = next; newnode->prev = pHead; next->prev = newnode; pHead->next = newnode;*/ ListInsert(pHead->next, x);//复用 } // 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); assert(!(LTEmpty(pHead))); /*ListNode* tail = pHead->prev; ListNode* tailPrev = tail->prev; tailPrev->next = pHead; pHead->prev = tailPrev; free(tail);*/ ListErase(pHead->prev); //复用 } // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { ListNode* cur = pHead ->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyTLNode(x); ListNode* posPrev = pos->prev; newnode->next = pos; newnode->prev = posPrev; posPrev->next = newnode; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* posPrev = pos->prev; ListNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
总之,选择哪种链表数据结构应该根据具体的应用场景和需要做的操作来决定。如果需要频繁地插入和删除节点,且需要支持双向遍历,可以选择带头双向循环链表;如果需要占用较少的内存空间,且不需要双向遍历,可以选择无头单向非循环链表。
O(N)
。O(1)
。O(N)
。如果有什么建议和疑问,或是有什么错误,希望大家能够提一下。
希望大家以后也能和我一起进步!!
如果这篇文章对你有用的话,希望能给我一个小小的赞!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。