刨析数据结构(二)-拓冰建站

🌈个人主页：小田爱学编程
🔥 系列专栏：数据结构————"带你无脑刨析"
🏆🏆关注博主，随时获取更多关于数据结构的优质内容！🏆🏆

😀欢迎来到小田代码世界~
😁 喜欢的小伙伴记得一键三连哦 ૮(˶ᵔ ᵕ ᵔ˶)ა

一.线性表的链式储存

链表：线性表的链式储存方式，逻辑结构不一定连续，物理结构不一定连续

描述：由数据域和指针域组成

🌏头结点：点是为了操作方便而设立的，放在第一个元素结点之前，不保存任何有意义的数据

🌏头节点：即为指向第一个节点的地址

🔥链表分类：八种

👨‍🚀 以单链表（不带头单向不循环链表）

二.单链表

1.优缺点

🔥任意位置插入删除，时间复杂度小
🔥没有增容问题，插入一个开辟一个空间

🔥不支持随机访问

2.创建

//定义链表
typedef int SLTDataType;//数值域
//链表是由节点组成
typedef struct SListNode
{SLTDataType data;//int datastruct  SListNode* next;//它用来存储当前节点的下一个节点的地址
}SLTNode;//typedef struct SListNode SLTNode;

3.打印

void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode* plist = node1;
SLTPrint(plist);

3.申请空间

SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

4.增加元素

尾插：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;
}

头插：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}

在指定位置插入

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头结点if (pos == *pphead) {//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;
}

5.删除元素

尾删

void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点，有多个节点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}

头删

void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

🔥指定位置删除:注意删除的逻辑

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos) {//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;
}
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能为空assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

6.修改元素

//给一个数据，找到这个数据所在的节点，并用新数据修改
void SListChangeDate(SLTNode*pphead, SLTDataType x, SLTDataType y)
//不需要改变节点的地址，所以值传递即可 
//x是查找的数据，y是新的数据，用来修改查找的数据                                              
{SLTNode*cru = pphead;while (cru != NULL)//如果没有节点，根本不会进入循环去找{if (cru->data == x){cru->data = y;break;//修改完数据后，就跳出循环}else{cru = cru->next;}}if (cru == NULL)//如果循环完单链表，没有找到要修改的那个数据{printf("要修改的数据不存在，请重新修改数据\n");}else{printf("修改成功\n");}
}

7.查找元素

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表 SLTNode* pcur = *pphead;while (pcur) //pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

8.销毁链表

void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

三.双向链表

1.注意

🔥带头双向循环链表

🔥当链表中只要头节点的时候，为空链表

🔥头节点是不能删除的，指向可以改变

🔥不需要改变头节点的指向，不需要传二级指针

🔥二级指针对实参会产生影响

2.创建

typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;

3.打印

LTNode* LTInit() {LTNode* phead = LTBuyNode(-1);return phead;
}

4.增加元素

尾插（不需要找尾操作）

//尾插
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev(ptail)  newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

头插

//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

任意位置插入

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);//pos->prev pos  pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

5.删除元素

头删

void LTPopFront(LTNode* phead) {assert(phead);assert(phead->next != phead);LTNode* del = phead->next;LTNode* next = del->next;//phead del nextnext->prev = phead;phead->next = next;free(del);del = NULL;
}

尾删

void LTPopBack(LTNode* phead) {assert(phead);//链表为空：只有一个哨兵位节点assert(phead->next != phead);LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}

任意位置删除

void LTErase(LTNode* pos) {assert(pos);//pos->prev pos  pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

6.修改元素

void DeleteNode(LTNode** pHead, LTNode* toBeDeleted) {if (pHead == NULL || toBeDeleted == NULL) {return;}LTNode* head = *pHead;// 要删除的节点是头节点if (head == toBeDeleted) {*pHead = toBeDeleted->next;}// 调整前驱节点的next指针if (toBeDeleted->prev != NULL) {toBeDeleted->prev->next = toBeDeleted->next;}// 调整后继节点的prev指针if (toBeDeleted->next != NULL) {toBeDeleted->next->prev = toBeDeleted->prev;}free(toBeDeleted);
}

7.查找元素

LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

8.销毁链表

void LTDesTroy(LTNode* phead) {//哨兵位不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//链表中只有一个哨兵位free(phead);phead = NULL;
}

🥇这是博主年前的最后一篇文章哦，年后再继续更新，年后会开启新的刷题专栏！😊

🥇还有不到不到一周就过年喽！祝大家新的一年财源滚滚，学习进步，身体健康，咱们明年见！