软件开发流程怎么写_qq空间网页版_seo产品优化免费软件_东莞疫情最新消息今天又封了

1.单链表

1.1概念与结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

现实中数据结构：

1.1.1结点

与顺序表不同的是，链表里的每节“车厢 ”都是独立申请下来的空间，我们称之为“结点”。

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

图中指针变量pList保存的是第一个结点的地址，我们称pList此时“指向”第一个结点，如果我们希望pList“指向”第二个结点时，只需要修改pList保存的内容为第二个的地址。

链表中每个结点都是独立申请的（需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

1.1.2链表的性质

链式结构在逻辑上是连续的，在物理结构上不一定连续
结点一般是从堆上申请的
从堆上申请来的空间是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

结构体代码：

typedef struct SListNode
{int data;struct SListNode* next;
}SL;

当我们要保存一个整形数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整形数组，也需要保存下一个结点的地址。

1.2实现单链表

SList.h

#pragma once
#include"stdio.h"
#include"stdlib.h"
#include"assert.h"//定义链表的结构
typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SL;//打印
void SLTPrint(SL* phead);//插入
void SLTPushBack(SL** pphead, SLDataType x);//尾插
void SLTPushFront(SL** pphead, SLDataType x);//头插//删除
void SLTPopBack(SL** pphead);//尾删
void SLTPopFront(SL** pphead);//头删//查找
SL* SLTFind(SL* phead, SLDataType x);//在指定位置之前插⼊数据
void SLTInsert(SL** pphead, SL* pos, SLDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SL* pos, SLDataType x);//删除pos结点
void SLTErase(SL** pphead, SL* pos);
//删除pos之后的结点
void SLTEraseAfter(SL* pos);
//销毁链表
void SListDestroy(SL** pphead);

功能1：打印

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

功能2：申请新的结点

SL* SLTBuyNode(SLDataType x)
{SL* node = (SL*)malloc(sizeof(SL));if (node == NULL){perreor("malloc fail");exit(1);}node->data = x;node->next = NULL;return node;
}

功能3：插入新的结点

void SLTPushBack(SL** pphead, SLDataType x)//尾插
{assert(pphead);SL* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SL* pcur = *pphead;//找尾结点while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}
void SLTPushFront(SL** pphead, SLDataType x)//头插
{assert(pphead);SL* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

功能4：删除结点

void SLTPopBack(SL** pphead)//尾删
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SL* pcur = *pphead;SL* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}prev->next = NULL;free(pcur);pcur = NULL;}
}
void SLTPopFront(SL** pphead)//头删
{assert(pphead && *pphead);SL* next = (*pphead)->next;free(*pphead);*pphead = next;
}

功能5：查找

SL* SLTFind(SL* phead, SLDataType x)
{assert(phead);SL* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

功能6：在指定位置之前插入数据

void SLTInsert(SL** pphead, SL* pos, SLDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SL* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}else{SL* newnode = SLTBuyNode(x);SL* pcur = *pphead;while (pcur->next == pos){pcur = pcur->next;}newnode->next = pcur->next;pcur->next = newnode;}
}

功能7：在指定位置之后插入数据

void SLTInsertAfter(SL* pos, SLDataType x)
{assert(pos);SL* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

功能8：删除pos结点

void SLTErase(SL** pphead, SL* pos)
{assert(pphead && *pphead);assert(pos);if (pos = *pphead){SL* next = (*pphead)->next;free(*pphead);*pphead = next;}else{SL* pcur = *pphead;while (pcur->next != pos);{pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

功能9：删除pos之后的结点

void SLTEraseAfter(SL* pos)
{assert(pos && pos->next);SL* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

功能10：销毁

void SListDestroy(SL** pphead)
{assert(pphead && *pphead);SL* pcur = *pphead;while (pcur){SL* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

1.3链表的分类

链表的结构非常多样，以下有8种链表结构：

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

2.双向链表

2.1概念与结构

带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”

2.2实现双向链表

LIst.h

#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;
}LTNode;//为了保持接口的一致性，优化接口都为一级指针
//初始化
LTNode* LTInit();//销毁
void LTDesTroy(LTNode** pphead);//打印
void LTPrint(LTNode* phead);//插入
//第一个参传一级还是二级，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如何不发生改变，pphead不会影响实参，传一级
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);//删除
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//找x值
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);

功能1：创建新的结点

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

功能2：初始化

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

功能3：插入结点

void LTPushBack(LTNode* phead, LTDataType x)//尾插
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->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);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

功能4：打印

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

功能5：判断链表是否为空

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next = phead;//正确说明链表为空，不正确说明链表不为空
}

功能6：删除结点

void LTPopBack(LTNode* phead)//尾删
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
void LTPopFront(LTNode* phead)//头删
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->next;LTNode* prev = del->next;phead->next = prev;prev->prev = phead;free(del);del = NULL;
}

功能7：找x值

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：在pos位置之后插入结点

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

功能9：删除指定位置结点

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

功能10：销毁

void LTDesTroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead);{LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;pcur = NULL;
}

3.顺序表与链表的分析

不同点	顺序表	链表（单链表）
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容和空间浪费	没有容量概念，按需申请释放，不存在空间浪费
应用场景	元素高效存储+频繁访问	任意位置高效插入和删除

软件开发流程怎么写_qq空间网页版_seo产品优化免费软件_东莞疫情最新消息今天又封了

1.单链表

1.1概念与结构

1.1.1结点

1.1.2链表的性质

1.2实现单链表

SList.h

功能1：打印

功能2：申请新的结点

功能3：插入新的结点

功能4：删除结点

功能5：查找

功能6：在指定位置之前插入数据

功能7：在指定位置之后插入数据

功能8：删除pos结点

功能9：删除pos之后的结点

功能10：销毁

1.3链表的分类

2.双向链表

2.1概念与结构

2.2实现双向链表

LIst.h

功能1：创建新的结点

功能2：初始化

功能3：插入结点

功能4：打印

功能5：判断链表是否为空

功能6：删除结点

功能7：找x值

功能8：在pos位置之后插入结点

功能9：删除指定位置结点

功能10：销毁

3.顺序表与链表的分析

最新新闻

热搜词