网站分辨率兼容怎么做,揭阳市住房和城乡建设局网站,ui培训设计机构,软件开发公司哪里好什么叫静态链表#xff1f;——用顺序表模拟链表#xff0c;就叫做静态链表 第一列相当于数据域data#xff0c;第二列相当于指针域next#xff0c;
第一行#xff08;0#xff09;相当于头结点#xff08;头结点的数据域不放数据#xff09;
#xff08;a#xff…什么叫静态链表——用顺序表模拟链表就叫做静态链表 第一列相当于数据域data第二列相当于指针域next
第一行0相当于头结点头结点的数据域不放数据
a图中0的next是1,1的next是2……7的next是8,8的next是0一遍下来又返回头结点
所以静态链表模拟的是——循环链表 这张图片中有一个姓氏是被删掉不存在也就是无效之前说过数组中的数据域都是有数字的只不过有些数字有效有些数字无效无效的数字在数组中就当做不存在的可以看出来是第7个ZHENG
所以数组中有一个有效数据长度lengthlength为几这个数组的有效数据就是几
其余数据可能是0也可能是其他数字不过均无效 因为通过next的数字将每个格子串起来发现串完一遍回到0后7不在这串的里面且指针域里面也没有7. 而在静态链表中找空闲结点的时间复杂度为——O(n^2。并不是On
因为如果要看1是不是空闲结点就要从头到尾串一遍看看1在不在这个串里面数组中的所有指针域里面有没有1出现过同理2到n每个都要遍历一遍n个n遍为n方。
如果已知有一个空闲结点的情况下是遍历一次所以有的说On但若是有5000个结点且不知道里面一共有几个空闲结点时且第几个为空闲结点时那就每个结点都需要遍历一遍看看在不在里面了。——时间复杂度取最坏的可能情况第5000个
其时间复杂度太大但对于我们来说我们使用链表最常用的操作是————头插尾插按值删。
前面指针类型的链表在头插尾插按值删的时候每次插入我们都要malloc申请一个结点每次删除我们要free释放p结点。老是跟外部的空间也会有影响
而静态链表是为了解决这个频繁malloc申请free释放造成内存的碎片化麻烦的。
它一次给你总数固定的格子点数不扩容的情况下比如图中的给你10个点然后你在里面插入删除
而在静态链表里面要想插入只要找到空闲结点On^2将要插入的有效数据val赋值覆掉原来的无效数据O1盖然后把它接入先绑后再接前到有效数据链里面O1就完成了。时间复杂度为On^2
要想删除只要找到要删除的结点然后把它从有效数据链里面踢出去接入到无效空闲数据链里面就完成了。
所以静态链表要改一下设计为了缩小原来找空闲结点的时间复杂度上图中a,b图就不对了 改造就是————把所有的空闲结点串起来这样就找的快
找空闲结点的时间复杂度就能降为O(1)
所以上图中就要划分为2张链表一个链叫有效数据链一个链叫空闲数据链也就叫空闲链。
然后插入就是你去找你就从空闲链里拿出去然后插入到有效链里。 然后规定0号位置作为有效链的头结点1号位置作为无效链的头结点
那么该静态链表的结构设计要怎么做看图写话
其内部成员就有int data和int next
一个结点就是一个SNode即 MAXSIZE就是一个静态链表里面有多少对这样的 头文件中的函数声明
#pragma once#define MAXSIZE 10
typedef struct SNode
{int data;//数据域int next;//后继指针表示下一个结点的意思实际上就是数组中的下标
}SNode,SLinkList[MAXSIZE];//SLinkList s;//s是一个长度为MAXSIZE的结构体数组s指向该数组//初始化
void InitList(SNode* ps);//头插
bool Insert_head(SNode* ps, int val);//尾插
bool Insert_tail(SNode* ps, int val);//插入数据在链表plsit的pos位置插入val数据元素,这个不写了静态链表不考这么深//判空
bool IsEmpty(SNode* ps);//获取数据结点的个数
int Getlength(SNode* ps);//在链表ps中 查找第一个key值找到返回key值的结点下标没有找到返回-1
int Search(SNode* ps, int key);//删除链表ps中pos位置的值删除跟插入一样成功或失败2种结果,这个也不写//删除第一个val的值
bool DelVal(SNode* ps, int val);//返回key的前驱地址返回key的后继下标这些也不写//输出
void Show(SNode* ps);//清空链表中的数据
void Clear(SNode* ps);//销毁整个链表内存交回
void Destroy(SNode* ps);
