做app模板网站有哪些,广东网站备案,企业查询学历需要哪些信息,佛山哪里做网站1.链表的概念及结构 链表是⼀种物理存储结构上非连续、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。 2. 顺序表带来的问题 (1)中间/头部的插⼊删除#xff0c;时间复杂度为O(N) (2)增容需要申请新空间#xff0c;拷⻉数据#xff… 1.链表的概念及结构 链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。 2. 顺序表带来的问题 (1)中间/头部的插⼊删除时间复杂度为O(N) (2)增容需要申请新空间拷⻉数据释放旧空间。会有不⼩的消耗。 (3)增容⼀般是呈2倍的增⻓势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插⼊了5个数据后⾯没有数据插⼊了那么就浪费了95个数据空间。 Ps单链表的好处就是比顺序表结构简单节省内存空间随时申请内存随时使用。链表其实就是由节点组成的节点中存储数据指向下一节点的位置指针。 3.单链表实现头部、尾部、任意位置增加删除节点、销毁链表等操作 //SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;//定义节点中的数据类型
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//定义节点的结构体数据以及下一结构体节点的指针地址然后重命名为 SLTNodevoid SLTPrint(SLTNode* phead);//打印节点数据void SLTPushBack(SLTNode** pphead);//尾插void SLTPushFront(SLTNode** pphead);//头插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);//在指定位置之后插入数据void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos(指定位置)节点void SLTEraseAfter(SLTNode* pos);//删除pos之后的节点void SListDesTroy(SLTNode** pphead);//销毁链表 //SList.c#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid SLTPrint(SLTNode* phead)//打印节点数据
{while (phead) //从第一个节点开始遍历遇到NULL结束{printf(%d-, phead-data);pheadphead-next;}printf(NULL\n);
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* NEWNode (SLTNode*)malloc(sizeof(SLTNode)); //内存分配时一定要注意写规范sizeof(SLTNode)8不要写为sizeof(SLTNode*)4, 大小就不一样肯定就会报错分配了一个指向 SLTNode 的指针的内存而不是分配一个 SLTNode 本身的内存。if (NEWNode NULL){perror(malloc);exit(1);}NEWNode-data x;NEWNode-next NULL;return NEWNode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{assert(pphead);if (*ppheadNULL)//*pphead代表指向第一个节点的指针如果是“空链表”进行尾插{*pphead SLTBuyNode(x);}else //如果是“非空链表”进行尾插{ SLTNode* ptail *pphead;while (ptail-next) //从第一个节点开始遍历判断指向下一个节点的指针是否为NULL 不能判断当前节点是否为空while (ptail) 进行结束循环这不能代表下一节点是NULL{ptail ptail-next;}//此时此刻ptail已经是尾节点了,ptail-nextNULLptail-next SLTBuyNode(x); }
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{assert(pphead);// *pphead代表指向第一个节点的指针如果是“空链表”进行头插SLTNode* pur SLTBuyNode(x);pur-next *pphead;*pphead pur;
}void SLTPopBack(SLTNode** pphead)//尾删
{assert(pphead *pphead);//链表不能为空//如果链表只有一个节点 // -优先级高于*所以要加上if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;}//如果链表有多个节点else{SLTNode* prev *pphead; //保存末尾的上一个节点的地址,目的是等释放末尾节点后使上一个节点的指向地址为NULLprev-next NULL;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);//如果链表只有一个节点//if ((*pphead)-next NULL)//{// free(*pphead);// *pphead NULL;//}//else//如果链表有多个节点//{// SLTNode* Nextnode *pphead;// *pphead Nextnode-next;//}//通用//方案一//SLTNode* Nextnode *pphead;//*pphead Nextnode-next;//方案二SLTNode* Nextnode (*pphead)-next;free(*pphead);*pphead Nextnode;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{//assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-data x){printf(找到了\n);return pcur;//找到了}pcur pcur-next;}return NULL;//没找到
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead *pphead);assert(pos);SLTNode* pcur *pphead;SLTNode* newnode SLTBuyNode(x);//申请一个空间存储要插入的节点if (pos *pphead){SLTPushFront(pphead, x);//头插}else{while (pcur-next ! pos){pcur pcur-next;}//pcur-newnode-posnewnode-next pos;pcur-next newnode;}
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}//删除pos(指定位置)节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead *pphead);assert(pos);SLTNode* prev *pphead;if (*pphead pos)//执行头删{SLTPopFront(pphead);}else{while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* after pos-next;pos-next pos-next-next;free(after);after NULL;
}//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* Nextnode pcur-next;free(pcur);pcur Nextnode;}*pphead NULL;
} //SeqList-test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid SList_test()
{//给节点里创建数据SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));//内存分配时一定要注意写规范sizeof(SLTNode)8不要写为sizeof(SLTNode*)4, 大小就不一样肯定 就会报错分配了一个指向 SLTNode 的指针的内存而不是分配一个 SLTNode 本身的内存。node4-data 4;//给节点之间建立联系node1-next node2;node2-next node3;node3-next node4;node4-next NULL;//调用链表打印SLTNode* plist node1;//SLTNode* plist NULL; //SLTPushBack(NULL, 5);//尾插//SLTPrint(plist);//打印节点数据SLTPushBack(plist, 5);//尾插SLTPrint(plist);//打印节点数据SLTPushFront(plist, 0);//头插SLTPrint(plist);//打印节点数据SLTPopBack(plist);//尾删SLTPrint(plist);//打印节点数据SLTPopFront(plist);//头删SLTPrint(plist);//打印节点数据}void SList_test1()
{SLTNode* plist NULL; SLTPushBack(plist, 1);//尾插SLTPrint(plist);//打印节点数据SLTPushBack(plist, 2);//尾插SLTPrint(plist);//打印节点数据SLTPushBack(plist, 3);//尾插SLTPrint(plist);//打印节点数据//SLTPushFront(plist, 0);//头插//SLTPrint(plist);//打印节点数据//SLTPopBack(plist);//尾删//SLTPrint(plist);//打印节点数据//SLTPopFront(plist);//头删//SLTPrint(plist);//打印节点数据//SLTFind(plist,1);//查找//SLTFind(plist, 3);//查找SLTNode* findSLTFind(plist, 3);//查找位置SLTInsert(plist, find, 0);//在指定位置之前插入数据SLTPrint(plist);//打印节点数据 1-2-0-3-NULLfind SLTFind(plist, 2);//查找位置SLTInsertAfter(find, 4);//在指定位置之后插入数据SLTPrint(plist);//打印节点数据 1-2-4-0-3-NULLfind SLTFind(plist, 3);//查找位置SLTErase(plist, find);//删除pos(指定位置)节点SLTPrint(plist);//打印节点数据 1-2-4-0-NULLfind SLTFind(plist, 4);//查找位置SLTEraseAfter(find);SLTPrint(plist);//打印节点数据 1-2-4-NULLSListDesTroy(plist);//销毁链表SLTPrint(plist);//打印节点数据//SLTPushBack(plist, 1);//尾插//SLTPrint(plist);//打印节点数据
}int main()
{//SList_test();SList_test1();//printf(%zd %zd, sizeof(SLTNode), sizeof(SLTNode*)); //8, 4return 0;
}
