网站建设怎么谈,要做网站,潍坊住房公积金贷款额度,杭州企业网站建设 哪里好文章目录链表单链表尾插头插尾删第一种方式删除第二种头删查找pos之前插入pos位置删除pos后面插入pos位置后面删除链表
顺序表缺点#xff1a;
空间不够了 需要扩容#xff0c;但是扩容是有消耗的头部或中间位置需要插入或删除#xff0c;需要挪动 #xff0c;但是挪动是…
文章目录链表单链表尾插头插尾删第一种方式删除第二种头删查找pos之前插入pos位置删除pos后面插入pos位置后面删除链表
顺序表缺点
空间不够了 需要扩容但是扩容是有消耗的头部或中间位置需要插入或删除需要挪动 但是挪动是有消耗的避免频繁扩容 一次一般都是去按倍数去扩2倍可能存在一定的空间浪费 我们采用链表解决问题
顺序表优点
支持随机访问
链表优点
按照需求申请空间不用了就释放空间更加合理的运用空间头部中间插入或删除数据 不需要挪动数据不存在空间浪费
缺点
每插入一个数据都需要存一个指针去链接后面的数据节点 不支持随机访问用下标直接访问第i个 arr[ i ] )
单链表
typedef struct SListNode // 单链表
{SLDataType data;struct SListNode* next;
}SLTNode; //单链表类型
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}
}尾插
尾插的本质是原来的尾节点需要存储新的尾节点地址
void SListPushBack(SLTNode** pphead , SLDataType x) // 尾插
{ //插入SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;if (*pphead NULL) //链表中一个节点都没有就不用去找尾{*pphead newnode;}else{//找到尾节点SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}头插 SLTNode * BuySingListNode(SLDataType x)//创建节点
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;return newnode;
}
void SListPushFront(SLTNode** pphead, SLDataType x) // 头插
{//创建节点SLTNode* newnode BuySingListNode(x);newnode-next *pphead;*pphead newnode;
}尾删
第一种方式删除
void SListPopBack(SLTNode** pphead) // 尾删
{assert(*pphead ! NULL); //头指针是否为空//只有一个节点if ( (*pphead)-next NULL){free(*pphead);*pphead NULL;}//两个或两个以上的节点else{SLTNode* p NULL;//找尾节点SLTNode* tail *pphead;while (tail-next ! NULL){p tail;//p指针记录倒数第二个节点 并且将节点置空tail tail-next;}free(tail);//删除tail NULL;p-next NULL;}}第二种
void SListPopBack(SLTNode** pphead) // 尾删
{assert(*pphead ! NULL); //头指针是否为空//只有一个节点if ( (*pphead)-next NULL){free(*pphead);*pphead NULL;}else //不创建临时变量p的方式去尾删{//找尾节点SLTNode* tail *pphead;while (tail-next-next){tail tail-next;}//删除free(tail-next);tail-next NULL;}}头删
void SingleListPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* first *pphead;*pphead first-next;free(first);first NULL;}查找
int SingleListFind(SLTNode* phead, SingleListDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;}pos之前插入
void SingleListInsert(SLTNode** pphead, SLTNode* pos, SingleListDataType x)
{assert(pos);assert(pphead);//只有一个节点相当于头插if (*pphead pos){SingleListPushFront(pphead ,x);}else//多个节点{//找到pos的前一个位置SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySingListNode(x);prev-next newnode;newnode-next pos;}
}pos位置删除
void SingleListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//只有一个节点相当于头删if (*ppheadpos){SingleListPopFront(pphead);}// 多个节点else{//找到pos的前一个位置SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}}pos后面插入
void SingleListInsertAfter(SLTNode* pos, SingleListDataType x) //pos后面插入
{assert(pos);SLTNode* newnode BuySingListNode(x);newnode-next pos-next;pos-next newnode;
}pos位置后面删除
void SingleListEraseAfter(SLTNode* pos) // 从pos后面删除
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}如果你觉得这篇文章对你有帮助不妨动动手指给点赞收藏加转发给鄃鳕一个大大的关注 你们的每一次支持都将转化为我前进的动力
