阿里云轻应用服务器 建设网站,莱芜在线董事长,3小时百度收录新站方法,东莞智通人才招聘网下载目录
顺序表的缺点#xff1a;
链表
链表的概念及其结构 链表的分类
链表的实现
链表形式#xff1a;
节点的创建:
链表的增删#xff1a;
尾插
头插
尾删
头删
查找
打印
链表的重点 1、尾删#xff1a;则是需要找到尾节点#xff0c;进行删除
2、头删
链表
链表的概念及其结构 链表的分类
链表的实现
链表形式
节点的创建:
链表的增删
尾插
头插
尾删
头删
查找
打印
链表的重点 1、尾删则是需要找到尾节点进行删除
2、头删找到头节点的下一个节点在删除头节点
在指定位置之前插入数据
在指定位置之后插入数据
删除pos之后的节点
链表的摧毁 以上我们完成了链表的实现可以尝试一下使用顺序表或链表实现通讯录 我们上节学习了顺序表的实现.
顺序表的缺点
任意位置插入或者删除元素的效率低每次插入或者删除需要搬移元素考虑空间的大小是否需要开辟空间
以下为顺序表与链表的不同点 链表
链表的概念及其结构 概念链表是一种物理存储结构上非连续 、非顺序的存储结构数据元素的 逻辑顺序 是通过链表中的 指针链 接次序实现的 。 链表的分类 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 虽然链表的类型很多但是我们实际中最常用还是两种结构 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。 链表的实现
#pragma once
//定义节点的结构
//数据 指向下一个节点的指针
typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
链表形式
//定义节点的结构
//数据 指向下一个节点的指针
typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;
节点的创建:
链表是一个个节点连接起来的所以我们的第一步应该动态申请节点
//开辟新结点
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;
}
链表的增删
尾插
我们先要创建一个存放x的新节点然后找到节点的尾在将为节点的next指向新节点
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode SLTBuyNode(x);//创建一个新节点if (*ppheadNULL) {*pphead newnode;}else {//创建一个尾节点找尾SLTNode* ptail *pphead;while (ptail-next) {ptail ptail-next;//找链表下一个为NULL的地址}//下一个为NULL出循环ptail-next newnode;}
}
头插
头插对于尾插简单不少先创建新节点将新节点的next指向头节点然后将地址赋给头节点
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode SLTBuyNode(x);//创建一个新节点if (*pphead NULL) {*pphead newnode;}else {newnode-next *pphead;*pphead newnode;//头节点为新的节点}
}
尾删
//尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead *pphead);if ((*pphead)-next NULL) {//-的优先级高于();//只存在一个节点free(*pphead);*pphead NULL;}else {//找尾节点SLTNode* pcur *pphead;//保存尾节点的上一个节点SLTNode* ptail *pphead;while (ptail-next) {pcur ptail;ptail ptail-next;}free(ptail);ptail NULL;pcur-next NULL;}
}
头删
//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead *pphead);SLTNode* pcur (*pphead)-next;free(*pphead);*pphead NULL;*pphead pcur;
}
查找
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* pcur phead;while (pcur){if (pcur-data x) {return pcur;}pcur pcur-next;}//没有查找到return NULL;
}
打印
void SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur) {//pcur!NULLprintf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
} 链表的重点 这是一串链表在链表中的增删查改其实是需要关注其节点 1、尾删则是需要找到尾节点进行删除
如果我们将为释放掉那尾节点的上一个节点指向哪里将会沦为野指针是非常危险的所以我们得创建一个指针用来找到这个节点这就是尾删的重点 2、头删找到头节点的下一个节点在删除头节点
与尾删类似我们需要考虑如果将phead删除我们如何找到新的头节点 综上所述链表的难度常常发生在其释放时指针的丢失或者成为野指针如果注意其我们将事半功倍减少bug的产生 //在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);
在指定位置之前插入数据
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead *pphead);assert(pos);SLTNode* newnode SLTBuyNode(x);//创建一个新节点if (pos *pphead) {//头插SLTPushFront(*pphead, x);}else{SLTNode* prev *pphead;//找到pos的上个节点while (prev-next ! pos) {prev prev-next;}newnode-next pos;prev-next newnode;}
}
在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode SLTBuyNode(x);SLTNode* pcur pos-next;//保存pos下一个节点以防节点丢失pos-next newnode;newnode-next pcur;
}
删除pos之后的节点
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}
链表的摧毁
//销毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
} 总体展示
#define _CRT_SECURE_NO_WARNINGS
#includeslist.h
#includeassert.hvoid SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur) {//pcur!NULLprintf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}//开辟新结点
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;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode SLTBuyNode(x);//创建一个新节点if (*ppheadNULL) {*pphead newnode;}else {//创建一个尾节点找尾SLTNode* ptail *pphead;while (ptail-next) {ptail ptail-next;//找链表下一个为NULL的地址}//下一个为NULL出循环ptail-next newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode SLTBuyNode(x);//创建一个新节点if (*pphead NULL) {*pphead newnode;}else {newnode-next *pphead;*pphead newnode;//头节点为新的节点}
}//尾删
void SLTPopBack(SLTNode** pphead) {assert(*pphead pphead);//只有一个节点直接释放掉if ((*pphead)-next NULL) //- 优先级高于*{free(*pphead);*pphead NULL;}else {//链表有多个节点SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next) {prev ptail;ptail ptail-next;}free(ptail);ptail NULL;prev-next NULL;}
}//头删
void SLTPopFront(SLTNode** pphead) {//链表不能为空assert(pphead *pphead);SLTNode* next (*pphead)-next; //- 优先级高于*free(*pphead);*pphead NULL;*pphead next;}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur phead;while (pcur){if (pcur-data x) {return pcur;}pcur pcur-next;}//没有查找到return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead*pphead);assert(pos);SLTNode* newnode SLTBuyNode(x);//创建一个新节点//如果为头插if (pos *pphead) {SLTPushFront(pphead,x);}else {SLTNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}//找到pos的上一个节点prev-next newnode;newnode-next pos;}
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);SLTNode* pcur pos-next;pos-next newnode;newnode-next pcur;}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead *pphead);assert(pos);//pos是头结点/pos不是头结点if (pos *pphead){//头删SLTPopFront(pphead);}else {SLTNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}prev-next pos-next;//减少创建一个节点保存pos-next的节点free(pos);pos NULL;}
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}//销毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
} 以上我们完成了链表的实现可以尝试一下使用顺序表或链表实现通讯录
