网站设计 手写,淄博网站排名,增城住房和城乡建设局网站,找个做网站的初识链表
用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的#xff0c;也可以是不连续的#xff0c;甚至是零散分布在内存中的任意位置上的。链表中元素的逻辑次序和物理次序不一定相同。
在存储自己内容的同时也存储下一个元素的地址。存…初识链表
用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的也可以是不连续的甚至是零散分布在内存中的任意位置上的。链表中元素的逻辑次序和物理次序不一定相同。
在存储自己内容的同时也存储下一个元素的地址。存储数据元素的域称为数据域存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成ai的存储映象称为结点(Node)。n个结点(ai(1≤i≤n)的存储映象链结成一个链表即为线性表。把链表中第1个结点的存储位置叫头指针。最后一个元素意味着没有直接后继规定最后一个结点指针为空(通常用NULL或^表示)
单链表由头指针唯一确定因此单链表可用头指针名字来命名。
单链表、双向链表、循环链表 其他基础辨析
结点只有一个指针域的链表称为单链表或线性链表 结点有两个指针域的链表称为双链表 首尾相接的链表叫循环链表 为了更加方便对链表进行操作会在单链表的第1个结点前附设一个头结点.头结点的数据域可以不存储任何信息也可以存储如线性表的长度等附加信息头结点的指针域存储指向线性表第1个元素的结点。 头指针
指链表指向第一个结点的指针若链表有头结点则是指向头结点的指针;
头指针具有标识作用所以常用头指针冠以链表的名字;
无论链表是否为空头指针均不为空。头指针是链表的必要元素
头结点
头结点是为了操作的统一和方便而设立的放在第一元素的结点之前其数据域一般无意义也可存放链表的长度
有了头结点对在第一元素结点前插入结点和删除第一结点其操作与其它结点的操作就统一了
头结点不一定是链表必须要素
首元结点
是指链表中存储第一个数据元素a1的结点
思考
如何表示空表 无头结点时头指针为空时表示空表 有头结点时当头结点的指针域为空时表示空表
有头结点有什么好处
①有了头结点对在第一元素结点前插入结点和删除第一结点其操作与其它结点的操作就统一了
②便于空表和非空表的统一处理 当链表不设头结点时假设L为单链表的头指针它应该指向首元结点则当单链表为长度n为0的空表时L指针为空判定空表的条件可记为L NULL)。增加头结点后无论链表是否为空头指针都是指向头结点的非空指针。头指针指向头结点。若为空表则头结点的指针域为空判定空表的条件可记为L -next NULL)
链表链式存储结构的特点
结点在存储器中的位置是任意的即逻辑上相邻的数据元素在物理上不一定相邻。访问时只能通过头指针进入链表并通过每个结点的指针域依次向后顺序扫描其余结点所以寻找第一个结点和最后一个结点所花费的时间不等 顺序表→随机存取 链表→顺序存取 单链表基本操作实现
单链表的初始化带头结点的单链表
即构造一个空表
步骤 生成新结点作头结点用头指针L指向头结点 将头结点的指针域置空 Status InitList(LinkList L) { //构造一个空的单链表LL new LNode; //生成新结点作为头结点用头指针L指向头结点L-next NULL; //头结点的指针域置空return OK;}补充单链表的几个常用简单算法
自我感觉除了判空都没啥用
判断链表是否为空
int ListEmpty(LinkList L) //若L为空表则返回1否则返回0
{if(L-next) //非空return 0;else return 1;
}单链表的销毁
链表销毁后不存在
从头指针开始依次释放所有结点
void DestoryList(Lnode* L)
{Lnode* p;while (L) {p L;L L-next;free(p);}return;
}清空单链表
链表仍存在但链表中无元素成为空链表头指针和头结点仍然在
依次释放所有结点并将头结点指针域设置为空 void ClearList(Lnode* L)
{Lnode* p, * q;p L-next;while (p){q p-next;free(p);p q;}L-next NULL;
}求单链表的表长
从首元结点开始依次计数
int ListLength(Lnode* L)
{int i 0;Lnode* p L-next; //p指向第一个结点while (p){i;p p-next;}return i;
}取值——取单链表第i个元素
从链表的头指针出发顺着链域next逐个结点往下搜索直至搜索到第i个结点为止。因此链表不是随机存取结构。
/*初识条件顺序线性表L已存在1 ≤ i ≤ListLength(L)操作结构用e返回L中第i个数据元素的值。
*/
int GetElem(LinkList L, int i, int* e)
{int j;Lnode* p; //声明一结点pp L-next; //让p指向链表L的第一个结点j 1; //j为计数器while (p j i ) //p不为空或者计数器j还没有等于i时循环继续{p p-next; //让p指向下一个结点j;}if (!p || j i){return -1; //第i个元素不存在}*e p-data; //取第i个元素的数据return *e;
}算法分析
该算法的基本操作是比较 j 和 i 并后移指针 pwhile循环体中的语句频度与位置 i 有关。若 1 ≤ i ≤ n 则频度为 i - 1 一定能取值成功若 i n则频度为n取值失败。因此取值算法的时间复杂度为O(n)。
假设每个位置上的元素取值概率相等即pi 1/n
则
按值查找——根据特定数据获取该数据所在地址
从第一个及诶点依次与e比较如果找到一个与e相等的元素则返回在列表中的地址如果查边整个链表都没有找到和e相等的元素停止循环并返回
Lnode* LocateElem(LinkList L, int e)
{// 在线性表L中查找值为e的数据元素//找到则返回L中值为e的数据元素的地址查找失败返回NULL因为p最后指向了NULLLnode* p;p L-next;while (p p-data ! e){p p-next;}return p;
}返回该数据位置序号
相当于多加了个计数器而已
int LocateElem2(LinkList L, int e)
{//返回L中值为e的数据元素的位置序号查找失败返回0Lnode* p;p L-next;int j 1;while (p p-data ! e){p p-next; j;}if (p) return j;else return -1;
}该算法的执行时间与待查找的值e相关 其平均时间复杂度分析类似于算法2.7,也为O(n)。
单链表的插入
首先找到ai-1的存储结构p。生成一个数据域为e的新结点s。插入新结点 新结点的指针域指向结点ai s-next p-next结点ai-1的指针域指向新结点 p-next s; /*i表示插入第几个元素之前
最后L要1*/
void ListInsert(LinkList L,int i ,int e)
{int j;Lnode* p, * s;p L; //查找算法从首元素开始pL-next;j1【插入算法i1它的前一个结点的头结点ji-1不循环】j 0;while (p j i - 1){p p-next;j;}if (!p || j i - 1){printf(error);//插入错误并提示return;}s (Lnode*)malloc(sizeof(Lnode));s-data e;s-next p-next; p-next s;return;
}单链表的删除
按位删除
找到第i-1个结点如果有必要的话保存ai的值且将地址存于在q中以被释放找到ai-1的位置赋值给ai-1的next域释放ai
p-next p-next-next /*删除L的第i个数据元素并用e返回其值L的长度减1*/
void Listdelete(LinkList L, int i, int* e)
{int j;Lnode* p, * q;p L; //*i1p是头结点pL;j 0;while (p-next j i - 1)//遍历寻找第i-1个元素{p p-next;j;}if (!(p-next) || j i - 1){/* printf() */return; //第i个元素不存在并提示}q p-next;p-next p-next-next; //或者p-nextq-next *e q-data;free(q);}按值删除
/*按值删除*/
void ListdeleteElem(LinkList L, int e)
{//先查找 有才能删//需要另写一个定位函数int index find(L, e);if (index -1){//没找到}else {//定位到前一个元素Lnode* temp;temp L;int i 0;while (i index)//定位置{temp temp-next;i;}Lnode* free_node temp-next;temp-next temp-next-next;free(free_node);}
}int find(LinkList L, int key)
{ //定位函数定位到待删除元素的前一个Lnode* temp;int i 0;temp L-next;while (temp ! NULL){if (temp-data key){return i;}temp temp-next;i;}return -1;
}头插法 尾插法建立单链表
头插法 – 元素插入在链表头部 前插法
从一个空表开始重复读入数据生成新结点将读入数据存放到新结点的数据域中从最后一个结点开始依次将各结点插入到链表的前端 /*头插法*/
void Linkinsert_head(LinkList L, int e)
{Lnode* temp (Lnode*)malloc(sizeof(Lnode));// 创建新结点//if判断malloc是否分配成功temp-next L-next;L-next temp;temp-data e;
}/*当然也可以考虑加个循环连续插入*/尾插法
从一个空表L开始将新结点逐个插入到链表的尾部尾指针r指向链表的尾结点。初始时r同L均指向头结点。每读入一个数据元素则申请一个新结点将新结点插入到尾结点后r指向新结点。
/*尾插法*/
void Linkinsert_tail(LinkList L, int e)
{Lnode* temp (Lnode*)malloc(sizeof(Lnode));// 创建新结点temp-next NULL;Lnode* r, *p; r L;p-data e;p-next NULL;r-next p;// 插入到表尾r p; //r指向新尾结点
}代码总结
#includestdio.h
#includestdlib.htypedef struct Lnode { //声明结点的类型和指向结点的指针类型int data; //结点数据域struct Lnode* next; //结点指针域
}Lnode, *LinkList; //LinkList为指向结构体Lnode的指针类型/*初始化 空链表
*/Lnode* InitList(LinkList L)
{L (Lnode*)malloc(sizeof(Lnode);if (L NULL){printf(分配失败); //提示分配失败}else {L-next NULL;}return L;
}void DestoryList(Lnode* L)
{Lnode* p;while (L) {p L;L L-next;free(p);}return;
}void ClearList(Lnode* L)
{Lnode* p, * q;p L-next;while (p){q p-next;free(p);p q;}L-next NULL;
}int ListLength(Lnode* L)
{int i 0;Lnode* p L-next; //p指向第一个结点while (p){i;p p-next;}return i;
}/*初识条件顺序线性表L已存在1 ≤ i ≤ListLength(L)操作结构用e返回L中第i个数据元素的值。
*/
int GetElem(LinkList L, int i, int* e)
{int j;Lnode* p; //声明一结点pp L-next; //让p指向链表L的第一个结点j 1; //j为计数器while (p j i ) //p不为空或者计数器j还没有等于i时循环继续{p p-next; //让p指向下一个结点j;}if (!p || j i){return -1; //第i个元素不存在}*e p-data; //取第i个元素的数据return *e;
}
/*按值查找*/
Lnode* LocateElem(LinkList L, int e)
{// 在线性表L中查找值为e的数据元素//找到则返回L中值为e的数据元素的地址查找失败返回NULL因为p最后指向了NULLLnode* p;p L-next;while (p p-data ! e){p p-next;}return p;
}/*按值查找2 返回位置序号*/
int LocateElem2(LinkList L, int e)
{//返回L中值为e的数据元素的位置序号查找失败返回0Lnode* p;p L-next;int j 1;while (p p-data ! e){p p-next; j;}if (p) return j;else return -1;
}/*i表示插入第几个元素之前
最后L要1*/
void ListInsert(LinkList L,int i ,int e)
{int j;Lnode* p, * s;p L; //查找算法从首元素开始pL-next;j1【插入算法i1它的前一个结点的头结点ji-1不循环】j 0;while (p j i - 1){p p-next;j;}if (!p || j i - 1){printf(error);//插入错误并提示return;}s (Lnode*)malloc(sizeof(Lnode));s-data e;s-next p-next; p-next s;return;
}/*按位删除
删除L的第i个数据元素并用e返回其值L的长度减1*/
void Listdelete(LinkList L, int i, int* e)
{int j;Lnode* p, * q;p L; //*i1p是头结点pL;j 0;while (p-next j i - 1)//遍历寻找第i-1个元素{p p-next;j;}if (!(p-next) || j i - 1){/* printf() */return; //第i个元素不存在并提示}q p-next;p-next p-next-next; //或者p-nextq-next *e q-data;free(q);}/*按值删除*/
void ListdeleteElem(LinkList L, int e)
{//先查找 有才能删//需要另写一个定位函数int index find(L, e);if (index -1){//没找到}else {//定位到前一个元素Lnode* temp;temp L;int i 0;while (i index)//定位置{temp temp-next;i;}Lnode* free_node temp-next;temp-next temp-next-next;free(free_node);}
}int find(LinkList L, int key)
{ //定位函数定位到待删除元素的前一个Lnode* temp;int i 0;temp L-next;while (temp ! NULL){if (temp-data key){return i;}temp temp-next;i;}return -1;
}/*头插法*/
void Linkinsert_head(LinkList L, int e)
{Lnode* temp (Lnode*)malloc(sizeof(Lnode));// 创建新结点//if判断malloc是否分配成功temp-next L-next;L-next temp;temp-data e;
}/*尾插法*/
void Linkinsert_tail(LinkList L, int e)
{Lnode* temp (Lnode*)malloc(sizeof(Lnode));// 创建新结点temp-next NULL;Lnode* r, *p; r L;p-data e;p-next NULL;r-next p;// 插入到表尾r p; //r指向新尾结点
}
