连州网站建设,北京西站地址,智能模板网站建设工具,用什么自己做网站当我们学完顺序表的时候#xff0c;我们发现了好多问题如下#xff1a; 中间/头部的插入删除#xff0c;时间复杂度为O(N)增容需要申请新空间#xff0c;拷贝数据#xff0c;释放旧空间。会有不小的消耗。增容一般是呈2倍的增长#xff0c;势必会有一定的空间浪费。例如当… 当我们学完顺序表的时候我们发现了好多问题如下 中间/头部的插入删除时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们 再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 如何解决上面的问题呢今天就跟着小张一起学习单链表吧 链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 注意1.链式结构在逻辑上是连续的但是在物理上不一定连续 2.结点一般都是在堆上申请出来的malloc 3.从堆上申请的空间是按照一定策略来分配的两次申请的空间可能连续也可能不连续 单链表 单链表的接口实现
void printdata(info* phead)//打印单链表
info* BuySListNode(int x)//创建新结点
void pushback(info** pphead, int x)//尾插
void pushFront(info** pphead, int x)//头插
void popFront(info** pphead)//头删
void popBack(info** pphead)//尾删
info* SListFind(info* pphead, int x)//单链表查找
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
void SeqListErase(info** pphead, info* pos)//删除pos位置的值
void SListInsertAfter(info* pos, int x)//单链表在pos位置之后插入x
void SListEraseAfter(info* pos)//删除pos的后一个位置
0.结构体定义单个结点
typedef struct info {int data;//data存数据struct info* next;//info*next存放下一个结点的地址}info;1.创建新结点
info* BuySListNode(int x)
{info* newnode (info*)malloc(sizeof(info));//空间申请assert(newnode);//断言新结点是否申请到了newnode-data x;//数据赋值newnode-next NULL;//指向的地址赋值return newnode;//将申请好的空间首地址返回回去}断言如果没申请到空间mallo返回空指针断言newnode就会报错 为什么要用二级指针传参在尾插头插尾删头删中
分析
2.尾插
void pushback(info** pphead, int x)//尾插
{info* newnode BuySListNode(x);//将创建好的新结点的地址保存在newnode变量中if (*pphead NULL)//链表无结点{*pphead newnode;// 将创建好的头节点的地址给给*pphead作为新头节点的地址}else{info* tail *pphead;//定义一个指针先指向头结点的地址while (tail-next ! NULL)//循环遍历找尾结点{tail tail-next;//指针指向下一个结点}tail-next newnode;//找到尾结点将尾结点的next存放新接结点的地址}}分析 文字解释大体上就是直接将最后一个结点的next存入新结点的地址然后将新结点的next存入空NULL)。 申请新的结点如果pphead为空地址链表还没有结点将新结点的地址传给pphead,新结点的地址就是头结点的地址如果该链表中已经存在结点定义一个指针先存放头节点的地址然后遍历整个链表循环寻找哪个结点的next为NULL不是的话就将tail指向下一个结点对应操作为tail tail-next;结点的next为NULL那个结点就是尾结点找到尾结点之后将尾结点的next存入要插入新结点的地址新结点的next已经在 BuySListNode(int x)置为空地址 3.打印链表
void printdata(info* phead)
{info* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);}分析 文字描述定义一个指针cur指向头结点使用这个指针循环遍历这个指针指向的不为空的话就继续循环在循环中打印cur-data对应的操作是printf(“%d-”, cur-data);打印%d后面加-是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur cur-next;继续打印。 4.头插
void pushFront(info** pphead, int x)//头插
{info* newnode BuySListNode(x);//创建新结点将新结点的地址存放在newnode指针变量中newnode-next *pphead;//新结点的下一个结点应该为旧头结点的地址*pphead newnode;//新头结点的地址更新为newnode指针所指向的地址}分析 文字描述将创建的新结点的地址存放在newnode指针变量中pphead为原先头结点的地址头插一个新结点后应该将新结点的next存放原先头结点的地址对应操作为newnode-next pphead;然后保存在pphead应该为新的头结点的地址也就是newnode所指向的地址对应操作为pphead newnode; 5.头删
void popFront(info** pphead)
{info* p (*pphead)-next;//定义指针存放头结点的下一个结点的地址free(*pphead);//释放头结点*pphead p;//头结点地址更新为原先头结点的下一个结点的地址
}分析
6.尾删
void popBack(info** pphead)
{info* tailprev NULL;info* tail *pphead;if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{while (tail-next ! NULL){tailprev tail;tail tail-next;}free(tail);tailprev-next NULL;}
}分析 7.修改
info* SListFind(info* pphead, int x)
{info* cur pphead;//cur指针保存pphead指针接收的地址while (cur){if (cur-data x){ //cur-datay可以将查找出来的值修改为y,不用单独写修改函数传参也要多一个yreturn cur;//找到的话返回该结点的地址}cur cur-next;//cur指向下一个结点的地址}return NULL;}分析 8.pos指针指向结点的地址的前一个位置前插插入随便插
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{assert(pphead);//头结点地址不能为空if (pos *pphead)//pos指针指向结点的地址为头结点相当于头插{pushFront(*pphead, x);//调用头插函数}else{info* prev *pphead;//定义一个prev指针先让他保存头结点的地址while (prev-next ! pos)//循环遍历找pos指针指向结点的前一个结点{prev prev-next;}info* newnodeBuySListNode(x);//申请新结点将申请好的结点地址存放在newnode指针变量里面prev-next newnode;//使之前pos指针指向的结点的前一个结点的next存入插入新结点的地址newnode-next pos;//然后新结点的next存入pos指向结点的地址
}
}分析 9.删除pos位置的值
void SeqListErase(info** pphead, info* pos)
{if (pos *pphead)//删除结点是否为头结点{popFront(*pphead);//头删}else{info* prev *pphead;//定义一个prev指针先让他存放头结点的地址while (prev-next ! pos)//循环遍历寻找哪个结点的next存放的是pos指针指向的结点的地址{prev prev-next;//prev指针指向下一个结点}prev-next pos-next;//pos指针指向的结点的上一个结点的next存放pos指针指向的结点的下一个结点的地址free(pos);//释放掉pos指针指向的那块空间}
}分析 10.单链表在pos位置之后插入x
void SListInsertAfter(info* pos, int x)
{assert(pos);//防止在空指针info* newnodeBuySListNode(x);//申请新结点newnode-next pos-next;pos-next newnode;}分析 那么12是否可以反过来 pos-next newnode;newnode-next pos-next; 不行d3的地址会丢失 出现下图的情况 11.删除pos的后一个位置
void SListEraseAfter(info* pos)
{assert(pos);//防止pos指向空地址if (pos-next NULL)//如果pos指针指向最后一个结点return;//直接退出不往下执行info* del pos-next;//保存pos指针指向结点的下一个结点的地址pos-next del-next;//更新pos指针指向的结点的下一个结点为pos指针指向结点下下一个结点的地址free(del);//释放掉保存pos指针指向结点的下一个结点的地址的空间。}分析 12.完整源码
#includestdio.h
#include stdlib.h
#include assert.h
typedef struct info {int data;struct info* next;}info;
void printdata(info* phead)
{info* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);}
info* BuySListNode(int x)
{info* newnode (info*)malloc(sizeof(info));assert(newnode);newnode-data x;newnode-next NULL;return newnode;}
void pushback(info** pphead, int x)//尾插
{info* newnode BuySListNode(x);if (*pphead NULL){*pphead newnode;}else{info* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}
void pushFront(info** pphead, int x)//头插
{info* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;}
void popFront(info** pphead)//头删
{info* p (*pphead)-next;free(*pphead);*pphead p;}
void popBack(info** pphead)//尾删
{info* tailprev NULL;info* tail *pphead;if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{while (tail-next ! NULL){tailprev tail;tail tail-next;}free(tail);tailprev-next NULL;}
}
info* SListFind(info* pphead, int x)//查找
{info* cur pphead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{assert(*pphead);if (pos *pphead){pushFront(*pphead, x);}else{info* prev *pphead;while (prev-next ! pos){prev prev-next;}info* newnodeBuySListNode(x);prev-next newnode;newnode-next pos;}}
void SeqListErase(info** pphead, info* pos)
{if (pos *pphead){popFront(*pphead);}else{info* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}}
void SListInsertAfter(info* pos, int x)
{assert(pos);info* newnodeBuySListNode(x);newnode-next pos-next;pos-next newnode;
}
void SListEraseAfter(info* pos)
{assert(pos);if (pos-next NULL)return;info* del pos-next;pos-next del-next;free(del);}int main()
{info* n1 (info*)malloc(sizeof(info));info* n2 (info*)malloc(sizeof(info));info* n3 (info*)malloc(sizeof(info));info* n4 (info*)malloc(sizeof(info));assert(n1 n2 n3 n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;printf(原链表:);printdata(n1);printf(\n);printf(尾插:);pushback(n1, 5);pushback(n1, 6);pushback(n1, 7);pushback(n1, 8);printdata(n1);printf(\n);printf(头插:);pushFront(n1, 10);pushFront(n1, 20);printdata(n1);printf(\n);printf(头删:);popFront(n1);printdata(n1);printf(\n);printf(尾删:);popBack(n1);popBack(n1);printdata(n1);printf(\n);printf(查找到并修改:);SListFind(n1, 3)-data 80;printdata(n1);printf(\n);printf(pos指针指向结点的地址的前一个位置前插插入:);SeqListInsert(n1, n4, 100);printdata(n1);printf(\n);printf(删除pos位置的值:);SeqListErase(n1, n4);printdata(n1);printf(\n);printf(单链表在pos位置之后插入x:);SListInsertAfter(n2, 1000);printdata(n1);printf(\n);printf(删除pos的后一个位置:);SListEraseAfter(n1);printdata(n1);printf(\n);}13.代码编译运行
