数组模拟链表

数组模拟链表,第1张

​ 如果你很难理解指针这些,没关系,还有一种使用数组来实现链表的方式,叫做模拟链表。


​ 链表中每一个节点只有两个部分。


我们可以用一个数组data来存储序列中的每一个数。


那么每一个数的右边的数是谁呢?这样要怎么解决呢?我们还需要一个数组right来存放序列中每一个数右边的数是谁就行了。




​ 上图的两个数组,第一个整型数组data用来存储序列中具体数字的,另外的一个数组right是用来存放序列中每一个元素右边的元素在数组中data中位置的。


例如right[1]的值为2,就表示了data[1]的右边的元素存放在data[2],如果是0,就表示序列的右边没有元素了。


​ 现在我们需要在8的前面插入一个6,只需要将6直接放在data的末尾即可,即data[9]=6。


接下来就是只需要将right[3]的值改10,再将right[9]的值改为4就可以了。


​ 完整代码如下所示:

#include 

int main()
{
    int data[101], right[101];
    int i, n, t, len;
    
    // 读入已有的数
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &data[i]);
    }
    len = n;
    
    // 初始化数组right
    for (i = 1; i <= n; i++) {
        if (i != n) {
            right[i] = i + 1;
        } else {
            right[i] = 0;
        }
    }
    
    // 直接在数组data的末尾增加一个数
    len++;
    scanf("%d", &data[len]);
    
    // 从链表的头部开始遍历
    t = 1;
    while (t != 0) {
        if (data[right[t]] > data[len]) { // 如果当前节点下一个节点的值大于待插入数,将数插入到中间
            right[len] = right[t]; // 新插入数的下一个几点标号等于当前节点的下一个节点编号
            right[t] = len; // 当前节点的下一个节点编号就是先插入数的编号
            break;
        }
        t = right[t];
    }
    
    // 输出链表中所有的数
    t = 1;
    while(t != 0) {
        printf("%d ", data[t]);
        t = right[t];
    }
    
    return 0;
}
    t = right[t];
}

return 0;

}


使用模拟数组也可以实现双向链表和循环链表,有兴趣可以试一下。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562367.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-01
下一篇 2022-04-01

发表评论

登录后才能评论

评论列表(0条)

保存