天津建设工程评标专家网站,站内seo怎么做,沈阳网站建设管理,制作网页可用邮件合并吗文章目录 链表链表的分类 单链表单链表的存储结构单链表主要实现的接口函数单链表尾插动态申请新节点单链表头插单链表的尾删单链表的头删在指定位置之前插入单链表查找插入 在指定位置之后插删除指定位置元素删除指定位置之后的元素顺序输出链表销毁单链表 顺序表和单链表的区… 文章目录 链表链表的分类 单链表单链表的存储结构单链表主要实现的接口函数单链表尾插动态申请新节点单链表头插单链表的尾删单链表的头删在指定位置之前插入单链表查找插入 在指定位置之后插删除指定位置元素删除指定位置之后的元素顺序输出链表销毁单链表 顺序表和单链表的区别关于指针传参 链表
链表是一种物理结构(储存结构)上不一定连续不一定是顺序的存储结构数据元素是通过链表中的指针链接次序实现的
链表的分类 链表有很多种类 两两匹配就一共有八种 这里主要介绍一下单链表(单向不带头不循环)
单链表
单链表的存储结构
图示 链表中的结点一般都是在堆上申请的从堆上申请的空间按照一定的规则申请的两次申请的空间也能相同也可能不相同。用一个指针就能找到下一个结点的空间地址了从而形成线性关系
typedef int ElemType;
typedef struct SListNode
{ElemType data;struct SListNode* next;
}SLTNode;typedef SLTNode* LinkList;//定义链表定义一个数据域和指针域。数据域用来存放数据指针域的指针指向下一个结点的空间地址
单链表主要实现的接口函数
//创建新结点
SLTNode* NewSLTNode(ElemType x);
//尾插
void SLTPushBack(SLTNode** phead, ElemType x);
//头插
void SLTPushFront(SLTNode** phead, ElemType x);
//尾删
void SLTPopBack(SLTNode** phead);
//头删
void SLTPopFront(SLTNode** phead);
//单链表查找
SLTNode* SLTNodeFind(SLTNode* phead, ElemType x);
//在pos之前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x);
//在pos之后插入
void SLTInsertAfter(SLTNode* pos, ElemType x);
//删除pos位置
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos位置后得
void SLTEraseAfter(SLTNode* pos);
//打印
void SLTNodePrintf(SLTNode* ps);单链表尾插
单链表插入主要分为两种情况
没有结点单链表是空的情况 有一个以上的结点 注意: 这里需要一个头指针(pehad 指向第一个结点的指针)来维护这个链表。否则将无法寻找到这个链表
void SLTPushBack(SLTNode** phead, ElemType x)
{//申请结点SLTNode* newnode NewSLTNode(x);//空链表if (*phead NULL){*phead newnode;}//有一个以上的结点else{SLTNode* tail *phead;//遍历找最后一个结点while (tail-next ! NULL){tail tail-next;}//连接新结点tail-next newnode;}
}链表结点的类型是struct SListNode* (结构体指针)类型插入一个新元素需要改变头指针的指向所以实参需要传其地址形参需要一个结构体指针的指针才可接受这个地址即二级指针 每次进行插入操作时都要申请结点封装成函数方便复用
动态申请新节点
SLTNode* NewSLTNode(ElemType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if(newnode NULL){perror(malloc fail);eixt(-1);}newnode-data x;newnode-next NULL;return newnode;
}单链表头插
头插可以只看作一种情况 空和非空的处理结果都一样
图解 代码实现
void SLTPushFront(SLTNode** phead, ElemType x)
{//申请结点SLTNode* newnode NewSLTNode(x);//空和非空链表都可处理newnode-next *phead;*phead newnode;
}单链表的尾删
尾删要注意三种情况分别是
空链表 错误处理只有一个结点 直接释放该结点即可 有两个结点以上的链表 先找到最后一个结点记录最后一个结点的前一个 然后释放最后一个结点再将最后一个的前一个指针域置为NULL
代码实现
void SLTPopBack(SLTNode** phead)
{//空链表assert(*phead);//只有一个结点if ((*phead)-next NULL){free(*phead);*phead NULL;}//有两个结点以上的链表else{SLTNode* tail *phead;SLTNode* tailprev NULL;//记录最后一个的前一个while (tail-next ! NULL){tailprev tail;tail tail-next;}free(tail);tail NULL;tailprev-next NULL;}
}单链表的头删
头删时要注意两种情况分别是
空链表 错误处理有一个或多个结点 先将头指针移动到第二个结点(只有一个结点第二个结点即为NULL也符合逻辑)的位置在释放该结点 代码实现
void SLTPopFront(SLTNode** phead)
{//空assert(*phead);//一个和多个结点处理逻辑一样SLTNode* newhead (*phead)-next;free(*phead);*phead newhead;
}在指定位置之前插入
位置由自己指定 比如链表元素 1 2 3 4 在2的位置之前插入6 链表变为1 6 2 3 4 插入之前首先要找到该元素结点的位置
单链表查找
SLTNode* SLTNodeFind(SLTNode* phead, ElemType x)
{assert(phead);SLTNode* pos phead;while (pos){if (pos-data x){return pos;}pos pos-next;}//没有该元素return NULL;
}然后根据查找到元素的结点位置进行插入
插入
在指定位置插入时要考虑以下情况
空链表 不需要做处理 因为空链表找不到指定的位置指定位置不存在 错误处理指定的位置是第一个结点 复用头插即可其他情况下插入 申请新节点 找到pos的前一个结点 将新结点连接接起来
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x)
{assert(*phead);assert(pos);if (pos *phead){SLTPushFront(phead, x);}else{//申请结点SLTNode* newnode NewSLTNode(x);//找pos的前一个SLTNode* cur *phead;SLTNode* posprev NULL;while (cur ! pos){posprev cur;cur cur-next;}posprev-next newnode;newnode-next pos;}
}在指定位置之后插
比如链表元素 1 2 3 4 在2的位置之后插入6 链表变为1 2 6 3 4 和指定位置之前插入一样首先要找到该元素结点的位置在进行插入 在指定位置后插入要考虑以下情况
空链表 不需要做处理 因为空链表找不到指定的位置指定位置不存在 错误处理其他情况下插入 这里不用考虑插入的位置是最后一个结点的位置这样首先要遍历链表进行判断在复用尾插代价太大。
代码实现
void SLTInsertAfter( SLTNode* pos, ElemType x)
{assert(pos);//申请新结点SLTNode* newnode NewSLTNode(x);newnode-next pos-next;pos-next newnode;
}删除指定位置元素
删除指定位置和插入指定位置一样需要先查找到该元素结点的位置 比如链表元素 1 2 3 4 删除2的位置链表变为 1 3 4 删除pos位置要考虑以下情况
空链表 不需要做处理 因为空链表找不到指定的位置指定位置不存在 错误处理指定位置是第一个结点 复用头删其他情况下删除指定位置 代码实现
void SLTErase(SLTNode** phead, SLTNode* pos)
{//空链表assert(*phead);// 指定位置不存在assert(pos); //复用头删if (pos *phead){SLTPopFront(phead);}else{//找pos前一个SLTNode* cur *phead;SLTNode* prevpos NULL;while (cur ! pos){prevpos cur;cur cur-next;}prevpos-next pos-next;free(pos);}
}删除指定位置之后的元素
比如链表元素 1 2 3 4 删除2之后位置 链表变为 1 2 4 删除指定位置之后的元素分别要考虑以下情况
空链表 不需要做处理 因为空链表找不到指定的位置指定位置不存在 错误处理是否是尾结点 错误处理其他情况下删除指定位置之后 代码实现
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* posnesxt pos-next;pos-next posnesxt-next;free(posnesxt);posnesxt NULL;
}顺序输出链表
void SLTNodePrintf(SLTNode* phead)
{SLTNode* tail phead;while (tail ! NULL){printf(%d , tail-data);tail tail-next;}printf(\n);
}销毁单链表
void SLTNodeDestory(SLTNode** phead)
{assert(*phead);SLTNode* cur *phead;SLTNode* curnext NULL;while (cur ! NULL){curnext cur-next;free(cur);cur curnext;}
}顺序表和单链表的区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续物理上不一定连续随机访问O(1)O(n)任意位置插入或删除可能需要挪动数据效率太低O(n)只需要修改指针指向即可插入元素动态顺序表空间不够时需要扩容没有容量概念用多少申请多少应用场景元素高效存储频繁访问频繁在任意位置插入和删除
关于指针传参 当你传递一个参数给函数的时候这个参数会不会在函数内被改动决定了函数参数形式 如果需要改动则需要传指向这个参数的指针 比如单链表的头插尾插、头删等都需要改变头指针的指向位置也就是这个参数需要被改动那么传这个参数的指针如果不用被改动可以直接传递这个参数 比如单链表中的查找和打印直接传参数就可以了查找和打印不用修改里面的内容
