彩票网站开发 极云,有的域名怎样做网站,全球域名注册平台,IP网站登记喜欢《数据结构》部分笔记的小伙伴可以订阅专栏#xff0c;今后还会不断更新。#x1f9d1;#x1f4bb; 此外#xff0c;《程序员必备技能》专栏和《程序员必备工具》专栏#xff08;该专栏暂未开设#xff09;日后会逐步更新#xff0c;感兴趣的小伙伴可以点一下订阅… 喜欢《数据结构》部分笔记的小伙伴可以订阅专栏今后还会不断更新。 此外《程序员必备技能》专栏和《程序员必备工具》专栏该专栏暂未开设日后会逐步更新感兴趣的小伙伴可以点一下订阅、收藏、关注 谢谢大家 什么是静态链表
单链表各个结点在内存中星罗棋布、散落天涯每个结点存放一个数据元素和一个指向下一个结点指针静态链表分配一整片连续的内存空间各个结点集中安置每个结点包含一个数据元素和下一个结点的数组下标游标 在静态链表中0号结点充当了头结点的角色也就是说这个结点中是不存放数据元素的而头结点的下一个结点存放在数组下标为2的这个位置。
索引数据元素data指针next0头21 e 2 e_2 e242 e 1 e_1 e113 e 4 e_4 e464 e 3 e_3 e3-156 e 5 e_5 e50
在这个静态链表中 头结点的指针是2指向索引为2的结点也就是 e 1 e_1 e1 e 1 e_1 e1的指针是1指向索引为1的结点也就是 e 2 e_2 e2 e 2 e_2 e2的指针是4指向 e 3 e_3 e3 e 3 e_3 e3的指针是-1表示静态链表的结束
如何定义一个静态链表
用代码定义一个静态链表
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义ElemType data; //存储数据元素int next; //下一个元素的数组下标
};void testSLinkList(){struct Node a[MaxSize]; //数组a作为静态链表//......
}课本上还给了一种定义的方式
#define MaxSize 10
typedef struct{ElemType data;int next;
}SLinkList[MaxSize];其实这种方式和下面的方式等价
#define MaxSize 10
struct Node{ElemType data;int next;
};
typedef struct Node SLinkList[MaxSize];//定义方法 1
void testSLinkList(){SLinkList a;//......
}
//定义方法 2
void testSLinkList(){struct Node a[MaxSize];//......
}
/*
* 定义方法1 和 定义方法2 是等价的
* 那么为什么课本要使用上面那种方法定义静态链表呢
* 因为下面这种定义方式
* 会让我们看起来像是定义了一个Node型的数组而不是链表
* 而用SLinkList一看就知道是静态链表
*/
简述基本操作的实现
初始化静态链表 1. 把a[0]的next设为-1 2. 把其他结点的next设为一个特殊值用来表示结点空闲如-2 查找 从头结点出发挨个往后遍历结点 直到找到想要的数据元素 时间复杂度 O ( n ) O(n) O(n) 插入位序为i的结点 1. 找到空的结点存入数据元素 2. 从头结点出发找到位序为i-1的结点 3. 修改新结点的next 4. 修改i-1号结点的next 删除结点 1. 从头结点出发找到前驱结点 2. 修改前驱结点的游标 3. 被删除结点的next设为-2 静态链表这一部分考试中很少考察代码实现更是如此 总结 静态链表就是用数组的方式来实现的链表 在逻辑上相邻的元素也可以在物理上不相邻 各个元素之间的关系是通过游标来表示的 优点增、删操作不需要大量移动元素 缺点不能随机存取只能从头结点开始依次往后查找容量固定不可变 适用场景 不支持指针的低级语言数据元素数量固定不变的场景如操作系统的文件分配表FAT
