静态链表及应用

浅浅的花香味﹌ 2022-03-25 08:07 286阅读 0赞

一般链表都是动态的,需要指针来建立结点之间的连接关系。不过一些结点的地址是比较小的整数,这样就没有必要去建立动态链表,可以使用静态链表去建立结点之间的关系

静态链表的原理是hash,建立一个结点结构体数组,数组的下标直接表示结点的地址,可以通过下标(结点的地址)来达到直接访问的效果,同时静态链表是不需要给出头节点的,只需给出某个结点的地址,就可以实现部分(或全部)遍历

const int MAXN = 100010;
    struct Node {
    	int key;
    	int next;  //指向下一个结点的地址
    }nodes[MAXN];

next用来存放下一个结点的地址:比如我们给出一串数字11111,22222,33333分别代表链表中3个结点的地址

node[11111]=22222;
    node[22222]=33333;
    node[33333]=-1; //-1表示NULL

### 应用: ###

有的时候题目会给出一些结点以及他的地址和他的next地址,需要我们筛选出链表中的结点(链表外的结点为无效结点)

并对这些结点进行操作,解决步骤模板如下:

1.建立结点结构体和数组

const int MAXN = 100010;
    struct Node {
    	int key;
    	int next;  //指向下一个结点的地址
        int valid;  //结点是否为有效结点
    }nodes[MAXN];

2.对链表进行初始化,将所有结点设置为无效结点

for (int i = 0; i < MAXN; ++i) {
    		nodes[i].validation = -1;  //先全部设置为无效结点
    }

3.根据题目中的测试用例,筛选出有效结点

int p1 = headAddr;
    	while (p1 != -1) {
    		counter++;
    		nodes[p1].validation = 1;
    		p1 = nodes[p1].next;  
    	}

4.编写排序函数,将有效结点集中在数组左边,无效结点集中在链表右边

bool cmp(Node a, Node b) {
    	if (a.validation == -1 || b.validation == -1) {
    		return a.validation > b.validation;  //将有效结点左移
    	}
    	else {
    		//二级排序,根据题目编写即可
    	}
    }

相关习题:[https://blog.csdn.net/alex1997222/article/details/86553806][https_blog.csdn.net_alex1997222_article_details_86553806]

[https_blog.csdn.net_alex1997222_article_details_86553806]: https://blog.csdn.net/alex1997222/article/details/86553806

静态链表及应用

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关模拟链表、静态链表及PAT例题A1032 Sharing

相关静态链表

相关静态链表的介绍及实现

相关数据结构静态链表的应用

相关静态链表

相关静态链表

相关静态链表

相关静态链表

相关静态链表及应用

相关静态链表