宿迁网站建设电话,wordpress在新窗口打开,为学校网站建设,wordpress站点链接打不开网址为了弥补链表在内存分配上的不足#xff0c;出现了静态链表这么一个折中的办法。静态链表比较类似于内存池#xff0c;它会预先分配一个足够长的数组#xff0c;之后链表节点都会保存在这个数组里#xff0c;这样就不需要频繁的进行内存分配了。 当然#xff0c;这个方法的… 为了弥补链表在内存分配上的不足出现了静态链表这么一个折中的办法。静态链表比较类似于内存池它会预先分配一个足够长的数组之后链表节点都会保存在这个数组里这样就不需要频繁的进行内存分配了。 当然这个方法的缺点是需要预先分配一个足够长的数组肯定会导致内存的浪费。数组不够长到不是什么大不了的使用第一节的动态扩容方法就是了。 静态链表一般是由两个链表组成一个保存数据的链表一个空闲节点的链表如图 3 所示。 图 3 静态链表 当需要向链表中添加节点时就从空闲链表中摘下一个使用。从链表中删除节点时就将被删除的节点归还到空闲链表中。 在实现上由于静态链表的节点都是存储在数组中的所以经常使用数组索引代替指针如果数组扩容了也不会影响现有的节点。下面简单的实现了一个静态双向链表没有添加动态扩容的能力。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 struct snode { int value; int prev; int next; }; struct sllist { snode *nodes; int head, freeHead; sllist():head(-1), freeHead(0) { // 初始化空闲链表静态分配长度为 100。 nodes new snode[100]; for (int i 0;i 100;i) { nodes[i].next i 1; } } void add(int value) { // 从空闲链表中摘取节点。 int newNode freeHead; freeHead nodes[freeHead].next; nodes[newNode].value value; nodes[newNode].prev -1; nodes[newNode].next head; if (head ! -1) { nodes[head].prev newNode; } head newNode; } void remove(snode node) { int idx head; if (node.prev -1) { head node.next; } else { idx nodes[node.prev].next; nodes[node.prev].next node.next; } if (node.next ! -1) { nodes[node.next].prev node.prev; } // 将节点归还空闲链表。 nodes[idx].next freeHead; freeHead idx; } }; 静态链表的效率几乎跟数组一样极大的提升了链表的效率。不过因为链表的效率受内存分配影响不同的语言可能有不同的表现具体情况还需要实验分析才可以。
