网站开发工程师前景,建公司网站建设明细报价表,网站兼容ie7,wordpress插件修改1.定义#xff1a;
#xff08;1#xff09;单链表#xff1a;各个结点散落在内存中的各个角落#xff0c;每个结点有指向下一个节点的指针(下一个结点在内存 中的地址);
#xff08;2#xff09;静态链表#xff1a;用数组的方式来描述线性表的链式存储结构: 分配一…1.定义
1单链表各个结点散落在内存中的各个角落每个结点有指向下一个节点的指针(下一个结点在内存 中的地址);
2静态链表用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间各个结点集中安置包括了——数据元素and下一个结点的数组下标(游标)
其中数组下标为0的结点充当头结点
游标为-1表示已经到达表尾
若每个数据元素为4B每个游标为4B则每个结点共8B假设起始地址为addr则数据下标为2的存放地址为addr8*2
注意 数组下标——物理顺序位序——逻辑顺序 优点增、删操作不需要大量移动元素
缺点不能随机存取只能从头结点开始依次往后查找容量固定不变
2.静态链表用代码表示
也可以这样 也等同于 注意SLinkList a 强调a是静态链表struct Node a 强调a是一个Node型数组 3.静态链表基本操作的实现
1初始化静态链表把a[0]的next设为-1 void InitList(StaticLinkedList *list) { list-head -1; // 设置头节点的next为-1表示空链表 list-size 0; // 初始化所有节点为未使用状态通常将next设置为下一个节点的索引表示空闲 for (int i 0; i MAXSIZE - 1; i) { list-nodes[i].next i 1; } list-nodes[MAXSIZE - 1].next -1; // 最后一个节点的next设置为-1 } 2查找某个位序不是数组下标位序是各个结点在逻辑上的顺序的结点从头结点出发挨个往后遍历结点时间复杂度O(n) Index FindByPosition(StaticLinkedList *list, int position) { if (position 0 || position list-size) { return -1; // 位序无效 } int curPosition 0; Index currentIndex list-head; while (currentIndex ! -1 curPosition position) { currentIndex list-nodes[currentIndex].next; curPosition; } return currentIndex; }
3在位序为i上插入结点① 找到一个空的结点存入数据元素② 从头结点出发找到位序为i-1的结点③修改新结点的next④ 修改i-1号结点的next void Insert(StaticLinkedList *list, ElementType element, int position) { if (position 0 || position list-size) { return; // 位序无效 } // 找到一个空闲节点用于插入新元素 Index newNodeIndex list-nodes[0].next; if (newNodeIndex ! -1) { // 确保还有空闲节点 list-nodes[0].next list-nodes[newNodeIndex].next; list-nodes[newNodeIndex].data element; // 存储数据 if (position 0) { // 如果是在头部插入 list-nodes[newNodeIndex].next list-head; // 新节点指向原头节点 list-head newNodeIndex; // 头节点更新为新节点 } else { Index prevNodeIndex FindByPosition(list, position - 1); // 找到前一个节点 list-nodes[newNodeIndex].next list-nodes[prevNodeIndex].next; // 新节点指向前节点的下一节点 list-nodes[prevNodeIndex].next newNodeIndex; // 前节点指向新节点 } list-size; } }
4删除某个结点① 从头结点出发找到前驱结点② 修改前驱节点的游标③ 被删除节点next设为-2 4.学习总结
静态链表使用数组模拟链表每个元素包含数据和游标下一个节点的索引。 初始化时需设置一个头节点并将所有节点串联起来作为一个空闲节点列表。 查找时需要遍历链表直到达到指定位置。这个操作的时间复杂度为O(n)。 插入操作包括寻找空闲节点、连接与前一个节点以及更新链表大小。 静态链表的操作相较于动态链表来说更为复杂但是在没有动态内存分配的环境下很有用。 在实践中应用静态链表需要仔细管理空闲节点列表避免内存的浪费和碎片化。 静态链表虽然不如动态链表灵活但在某些限制内存的场景下可能非常有用。
