静态链表

2023/01/09 DataStructrue 共 2490 字,约 8 分钟
Mahiro2211
  • 今天复盘一下以前学过的基础数据结构

链表(单向链表与双向链表)

在算法竞赛种很少使用动态链表,因为写起来很繁琐,大都是用数组模拟链表显得更加方便

使用结构体实现静态链表(以约瑟夫环为例洛谷P1996)


  • $n$ 个人围成一圈,从第一个人开始报数,数到 $m$ 的人出列,再由下一个人重新从 $1$ 开始报数,数到 $m$ 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

结构体数组实现单向静态链表

  • 个人觉得结构体数组的优势就是可以储存不止一个数据类型
#include<cstdio>
using namespace std;
const int N = 1e5+10;
struct node{
	int id , nextid;
}nodes[N];
int main(){
	int n , m ;
	scanf("%d%d",&n,&m);
	nodes[0].nextid = 1;//初始化
	for(int i = 1 ; i <= n ; i++){
		nodes[i].id = i;
		nodes[i].nextid = i + 1;**//初始化链表,next指针指向下一个要去的节点**
	}
	nodes[n].nextid = 1;//尾指针再指向头指针,实现闭环
	int pre = 1 , now = 1;//用两个指针记录遍历时的节点
	while(n-- > 1){//直到所有人都出列
		for(int i = 1 ; i < m ; i++){
			//开始数数,数到m,去掉这个节点
			pre = now;//存储以前的值
			now = nodes[now].nextid;//这个也代表着当前数到的人
		}
		printf("%d ",nodes[now].id);
		//让第m出列我们直接越过now,直接让pre指向now下一个,也就是删除掉now节点
		nodes[pre].nextid = nodes[now].nextid;
		now = nodes[pre].nextid;//新建now节点被pre指向,下一次从这里开始数
	}
	printf("%d",nodes[now].nextid);
	return 0 ;
	
}

结构体数组实现双向静态链表

  • 双向链表只不过就是有两个next指针一个指向前面的元素,一个指向后面的元素
  • 双向链表示意图
    #include<cstdio>
    using namespace std;
    const int N = 1e5+10;
    struct node{
    int id , preid , nextid;
    }nodes[N];
    int main(){
    int n , m ;
    scanf("%d%d",&n,&m);
    nodes[0].nextid = 1;
    for(int i = 1 ; i <= n ; i++){
        nodes[i].id = i;
        nodes[i].nextid = i + 1;
        nodes[i].preid = i - 1;
    }
    nodes[n].nextid = 1;
    nodes[1].preid = n;
    int pre = 1 , now = 1 , next = 1;
    while(n -- > 1){
        for(int i = 1 ; i < m ; i++){
            now = nodes[now].nextid;
        }
        printf("%d ",nodes[now].id);
        //此时的now就是要被删除掉的节点
        pre = nodes[now].preid;
        next = nodes[now].nextid;
        nodes[pre].nextid = nodes[now].nextid;
        nodes[next].preid = nodes[now].preid;
        now = next;
    }
    printf("%d",nodes[now].nextid);
    return 0;
    }
    

数组模拟实现单向链表

  • 需要开两个数组一个用来保存值,一个next数组用来指向每个元素下一个指向的位置
  • 设置一个$next[i]$指向i的下一个元素位置,i本身就是元素值
    #include<cstdio>
    using namespace std;
    const int N = 1e5+10;
    int a[N] , next[N];
    int main(){
      int n , m ;
      next[0] = 1;
      scanf("%d%d",&n,&m);
      for(int i = 1 ; i <= n ; i++){
          next[i] = i + 1;
      }
      next[n] = 1;
      int now = 1 , pre = 1;
      while(n-- > 1){
          for(int i = 1 ; i < m ; i++){
              pre = now;
              now = next[now];
          }
          printf("%d ",now);
          next[pre] = next[now];
          now = next[now];
      }
      printf("%d",now);
      return 0 ;
    }
    

    单向链表的删除,添加

int head ;//头指针
int idx ; //表示现在用到哪个点
int e[N],nexte[N];//节点i的值何next指针指向的下一个节点
//在头节点添加一个元素
void init(){
	head = - 1;
	idx = 0;//头指针是空指针,谁也不指
}
void add_to_head(int x){
	e[idx] = x;//储存值
	nexte[idx] = head;//让第一个元素先指向头指针
	head = idx ++;//更新表头,头指针加一
	//刚加进去的元素既是头元素也是尾元素
}
void add(int k ,int x){//在第k个插入的数后面加入x
	e[idx] = x;
	nexte[idx] = nexte[k];
	next[k] = idx++;
}
void remove(int k){
	nexte[k] = nexte[nexte[k]];//直接跳过

数组实现双向链表

int e[N] , l[N] , r[N] , idx;
void init(){
    //默认头指针指向0,尾指针指向1
    idx = 2;
    r[0] = 1 , l[1] = 0;
}
void r_add(int k ,int x ){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

文档信息

Search

    Table of Contents