健身房网站建设,天津做网站排名,黄骅贴吧二手房,华为网站推广策略目录
单链表
1.单链表的存储定义
2.结点的创建
3.链表尾插入结点
4.单链表尾删结点 5.单链表头插入结点
6.单链表头删结点
7.查找元素#xff0c;返回结点 8.在pos结点前插入一个结点
编辑 9.在pos结点后插入一个结点
10.删除结点
11.删除pos后面的结点
12.修改…目录
单链表
1.单链表的存储定义
2.结点的创建
3.链表尾插入结点
4.单链表尾删结点 5.单链表头插入结点
6.单链表头删结点
7.查找元素返回结点 8.在pos结点前插入一个结点
编辑 9.在pos结点后插入一个结点
10.删除结点
11.删除pos后面的结点
12.修改链表结点的值
13.打印链表 14.销毁链表 线性表的链式存储链表
前言:
之前介绍过线性表的顺序存储方式顺序表 发现顺序表在 插入删除操作需要移动大量元素当静态顺序表长度变化较大时难以确定存储空间的容量造成存储空间的碎片。 数据结构中 注意 这里的是没有哨兵卫的链表。
单链表
1.单链表的存储定义
单链表的存储与顺序表的存储不一样单链表不仅仅存放数值还要存放下一个结点的地址
代码
typedef int SLNDataType;typedef struct SListNode
{SLNDataType val; //存放单链表的值struct SListNode* next; //存放下一个单链表的地址
}SLNode; 当有了单链表的存储定义我们就可以对单链表进行存放结点。
2.结点的创建
这里使用malloc函数进行创建
代码
//创建一个结点
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(CreateNode-malloc);exit(-1);}newnode-val x; //结点赋值newnode-next NULL; //结点下一个结点为NULLreturn newnode;
}
3.链表尾插入结点
尾插结点这里需要考虑两方面。
1、单链表为空插入结点的情况这里直接让头指针指向创建的新结点即可。
2、单链表不为空时例如下图要尾插结点4 这里只需创建一个尾指针tail 遍历到第三个结点,把 第三个结点的next 指向 第四个结点即可 代码
//尾插结点
void SListPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newnode CreateNode(x); //创建一个结点if (*pphead NULL) //单链表为空直接指向新结点{*pphead newnode;}else {SLNode* tail *pphead; //定义一个尾指针while (tail-next ! NULL) //找到表尾{tail tail-next; //指向下一个结点}//找到表尾后指向新结点即可tail-next newnode;}
}
注意这里的二级指针。*pphead phead,指向第一个结点。 4.单链表尾删结点
单链表尾部删除结点分两种情况。1)只有一个结点的情况 2)多个结的情况
因为平时删除结点对于单链表我们需要找到前面的结点。所以这里采取经典的双指针的方法
定义一个指向当前的结点(cur)一个指向前面的结点(pre)当遍历到表尾时释放cur指向的结点后把pre-next NULL这样就完成了尾删一个结点。 但是我们发现只有一个结点时 这里free(cur) ,但是pre指向NULL, 这条语句 pre-next NULL 就是错的。 当然有些人会可能想到为什么不让pre也指向第一个结点如果这样想这里显然是对free()这知识点模糊不清 。因为free(cur) 时 第一个结点的内存空间已经释放返还给操作系统了所以pre此时指向的内存空间属于访问野指针了。
所以我们对 1)只有一个结点的情况 2)多个结点的情况 分别处理
1一个结点的情况 if ((*pphead)-next NULL) //只有一个结点的情况{free(*pphead);*pphead NULL;}
2) 多个结点的情况
定义一个指向当前的结点(cur)一个指向前面的结点(pre)当遍历到表尾时释放cur指向的结点后把pre-next NULL这样就完成了尾删一个结点。 SLNode* cur *pphead;SLNode* pre NULL;while (cur-next ! NULL){pre cur;cur cur-next;} free(cur);cur NULL;pre-next NULL; 代码
//尾删结点
void SListPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead); //避免链表为空if ((*pphead)-next NULL) //只有一个结点的情况{free(*pphead);*pphead NULL;}else //多个结点的情况{SLNode* cur *pphead;SLNode* pre NULL;while (cur-next ! NULL){pre cur;cur cur-next;}free(cur);cur NULL;pre-next NULL;}
}
当然上方代码也可以不用定义pre,来实现
//尾删结点
void SListPopBack(SLNode** pphead)
{assert(*pphead); //避免链表为空if ((*pphead)-next NULL) //只有一个结点的情况{free(*pphead);*pphead NULL;}else //多个结点的情况{SLNode* cur *pphead;while (cur-next-next ! NULL){cur cur-next;}free(cur-next);cur-next NULL;}
} 5.单链表头插入结点
首先创建一个新结点然后让新结点指向 头指针指向的结点头指针再指向新结点。
注意先后指向的顺序不能变。
代码
//头插结点
void SListPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newnode CreateNode(x); //创建一个新结点newnode-next *pphead; //新结点指向 头指针指向的结点*pphead newnode; //再让头指针指向新结点
} 这样就变成 如果指向的顺序变了那就会出现这种错误 结点的next指向自己,这样是错误的
6.单链表头删结点
单链表头删除结点时先临时创建一个next指针来指向第一个结点的下一个结点然后释放第一个结点再让头指针指向next这样就完成删除第一个结点。 代码
//头删结点
void SListPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* next (*pphead)-next;free(*pphead);*pphead next;
}
方法二
当然也可以先临时存放第一个结点让*pphead指向第二个结点然后再删除第一个结点。
代码
//头删结点
void SListPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
}
7.查找元素返回结点
代码
//查找元素返回结点
SLNode* SListFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x)return cur; //查找成功返回当前结点cur cur-next;}return NULL; //查找失败返回NULL
} 8.在pos结点前插入一个结点
assert(pheadpos); 这里的意思是避免是空指针的情况 首先在某结点前插入结点当在第一个结点前插入结点时这相当于表头插入结点当在不是第一个结点前插入结点时定义一个pre的指针遍历找到pos结点的前一个结点。
代码
//在pos结点前插入一个结点
void SListInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{//避免指针为空assert(pphead);assert(*pphead); assert(pos);if (*pphead pos){SListPushFront(pphead,x);return;}SLNode* newnode CreateNode(x);SLNode* pre *pphead; //定义一个指向第一个结点的指针while (pre-next ! pos){assert(pre);//避免空指针pre pre-next;}pre-next newnode;newnode-next pos;
}
图解 注意更改顺序 上述说的是在有头指针的情况下进行在pos结点前插入一个结点。 题目变形
当在没有给头指针的情况下在pos的结点前如何插入一个结点
解析这里给出一个取巧的方法即先在pos后面插入结点然后再把pos的值和新插入结点的值交换一下。这样就完成了在没有头指针的情况下在pos前插入一个结点。
代码
//在pos结点前插入一个结点
void SListInsert(SLNode* pos, SLNDataType x)
{//避免指针为空assert(pos);SLNode* newnode CreateNode(x);//先在pos后插入结点newnode-next pos-next;pos-next newnode;//交换两个结点的值SLNDataType tmp pos-val;pos-val newnode-val;newnode-val tmp;
}
图解 9.在pos结点后插入一个结点
这里定义一个指针next用于记录pos后面结点的地址pos指向newnode, newnode指向next。 代码
//在pos结点后插入结点
void SListInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* next pos-next; //先记录pos后面的结点SLNode* newnode CreateNode(x);pos-next newnode;newnode-next next;
} 也可以这样写,注意顺序避免指向自己。 代码
//在pos结点后插入结点
void SListInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newnode CreateNode(x);newnode-next pos-next;pos-next newnode;
} 10.删除结点
例删除结点pos, 在只有一个结点中删除结点在多个结点中删除结点。
在只有一个结点中删除那就相当于头删结点。
在多个结点中删除结点那就需要知道被删除结点的前一个结点。这里采用双指针的思想进行删除结点。pre指针负责记录pos的前一个结点next指针记录pos后面的结点。这样释放pos结点后pre指向next就完成了pos结点的删除。 代码
//删除结点pos
void SListErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead);//pos为第一个结点且是第一个结点if (*pphead pos){//相当于头删结点SListPopFront(pphead);}else{//在多个结点中删除结点posSLNode* pre *pphead;SLNode* next pos-next;while (pre-next ! pos){pre pre-next;}free(pos);pos NULL;pre-next next; }}
图解 11.删除pos后面的结点
首先断言一下避免头指针和pos后面的结点为空。assert(phead pos-next); 代码
//删除pos之后的一个结点
void SListEraseAfter(SLNode* pos)
{assert(pos);assert(pos-next); //避免为空指针//先使用next记录pos后面的结点SLNode* next pos-next-next;free(pos-next);pos-next next;
}
图解 12.修改链表结点的值 代码
//修个pos结点中的值
void SListModify(SLNode* phead, SLNode* pos, SLNDataType x)
{assert(pheadpos); //避免为空指针SLNode* cur phead; //cur指向头指针while(cur ! pos){cur cur-next;}cur-val x; //修个值
} 13.打印链表 代码
//打印结点
void SListPrint(SLNode* phead)
{SLNode* cur phead;while (cur){printf(%d-,cur-val);cur cur-next;}printf(NULL\n);
} 14.销毁链表
这里因为是使用mallco开辟的空间所以是需要进行手动释放的。
注意可能是多个结点也就是开辟了多个不连续内存空间
所以首先应该记录被释放结点的下一个结点的地址避免释放后找不到下一个结点
释放完所有的结点,头指针置为NULL 代码
//销毁链表
void SListDestory(SLNode** pphead)
{assert(pphead);SLNode* p *pphead;//注意结点的内存空间的释放要释放多个while (p) {//首先应该记录被释放结点的下一个结点的地址避免释放后找不到下一个结点SLNode* tmp p-next; free(p);p tmp; //指向下一个结点}//释放完所有的结点,头指针置为NULL*pphead NULL;
} 总结
单链表在找出位置的指针后插入和删除时间复杂度为O(1),
但在查找方面上单链表的时间复杂度为O(n),
当线性表中的元素个数变化较大或者根本不知道有多大时最好用单链表结构。
