当前位置：首页 > news >正文

数据结构——线性表

news 来源：原创 2024/5/11 0:18:54

逻辑结构——线性表

1.线性表的定义（逻辑结构）

要点：

相同数据类型
有限
序列

几个概念：

$a_i$ 是线性表中的“第i个”元素线性表中的位序
$a_1$ 是表头元素； $a_n$ 是表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
⭐注意：位序从1开始，数组下标从0开始

物理结构——顺序表

顺序表，按数组理解即可。

2.顺序表（物理结构）

顺序表：用顺序存储的方式实现线性表。

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

物理结构——链表

什么是链表？

链表是一种通过指针串联在一起的线性结构。

每一个节点由两部分组成，一个是数据域 data ，一个是指针域 next（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

3.单链表（物理结构）

单链表：每个结点除了存放数据元素外，还要存储指向下一个节点的指针。

单链表中的指针域只能指向节点的下一个节点。

单链表代码：

head 表示头结点的下标
e[i] 表示结点i的值
ne[i] 表示节点i的next指针是多少
idx 存储当前已经用到了哪个点

头插法

//头插法
void head_insert(int x){e[idx]=x;ne[idx]=head;head=idx;idx++;
}

一般插入

//在第k个插入的数后插入一个数
void insert(int k,int x){//插入的是第k+1个数，下标是ke[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;
}

全部代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int head,e[N],ne[N],idx;
//初始化
void initial(){head=-1,idx=1;
} 
//头插法
void head_insert(int x){e[idx]=x;ne[idx]=head;head=idx;idx++;
} //在第k个插入的数后插入一个数
void insert(int k,int x){//插入的是第k+1个数，下标是ke[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;
} 
//删除第k个插入的数后面的数
void move(int k){//k=0时， if(k==0)head=ne[head];elsene[k]=ne[ne[k]];
} 
int main(){int m;cin>>m;//初始化memset(ne,-1,sizeof ne); initial();//cout<<ne[1]<<ne[10];while(m--){char a;cin>>a;if(a=='H'){int x;cin>>x;head_insert(x);}else if(a=='I'){int k,x;cin>>k>>x;insert(k,x);}else{//a==Dint k;cin>>k;move(k);}}//cout<<ne[15];//输出for(int i=head;i!=-1;i=ne[i]){cout<<e[i]<<" ";} return 0;
}

4.双链表（物理结构）

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

双链表插入

//在第k个结点的右边插入一个结点
void r_insert(int k,int x){e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}
//在第k个结点的左边插入
void l_insert(int k,int x){r_insert(l[k],x); 
} 
//在最右侧插入
void right(int x){r_insert(l[1],x);
} 
//在最左侧插入
void left(int x){r_insert(0,x);
}

删除

//删除第K个插入的数 
void remove(int k){r[l[k]]=r[k];l[r[k]]=l[k]; 
}

所有代码

//双链表
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int l[N],r[N],idx,e[N];
//初始化
void init(){r[0]=1;l[1]=0;idx=2;
} 
//在第k个结点的右边插入一个结点
void r_insert(int k,int x){e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}
//在第k个结点的左边插入
void l_insert(int k,int x){r_insert(l[k],x); 
} 
//在最右侧插入
void right(int x){r_insert(l[1],x);
} 
//在最左侧插入
void left(int x){r_insert(0,x);
} 
//删除第K个插入的数 
void remove(int k){r[l[k]]=r[k];l[r[k]]=l[k]; 
}int main(){int m;cin>>m;char op[6];int x;int k;init();while(m--){scanf("%s",&op);if(op[0]=='L'){cin>>x;left(x);}else if(op[0]=='R'){cin>>x;right(x);}else if(op[0]=='D'){cin>>k;remove(k+1);}else if(op[1]=='L'){cin>>k>>x;l_insert(k+1,x);}else{cin>>k>>x;r_insert(k+1,x);}}//outputfor(int i=r[0];i!=1;i=r[i]) {cout<<e[i]<<" ";}return 0;}