静态链表
学过C语言的人基本都知道链表就是通过指针来建立节点之间的关系,那种称之为动态链表,而对于有些简单的问题,我们可以用静态链表来替代
建立结构体数组,数组的下标直接表示节点地址,
1
2
3
4
5
|
struct
{
typename data;
int next;
}node[size];
|
PAT1052
参考PAT1052,题目大意是给出一个静态链表,要求我们根据节点的值来对链表进行排序.
定义一个结构体,其中带有bool变量flag代表该节点是否出现,遍历一遍链表对出现过的节点置true,之后就对链表进行排序,没有出现过的排序过程就到后面,之后对链表遍历输出即可.要注意链表中无节点的情况进行特别判别.
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
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include<algorithm>
using namespace std;
const int maxn=100005;
struct
{
int address,data,next;
bool flag;
}node[maxn];
bool cmp(Node a,Node b)
{
if(a.flag==false||b.flag==false)
return a.flag>b.flag;
else
return a.data<b.data;
}
int main()
{
for(int i=0;i<maxn;i++)
node[i].flag=false;
int n,begin,address;
scanf("%d%d",&n,&begin);
for(int i=0;i<n;i++)
{
scanf("%d",&address);
scanf("%d%d",&node[address].data,&node[address].next);
node[address].address=address;
}
int cnt=0,p=begin;
while(p!=-1)
{
node[p].flag=true;
cnt++;
p=node[p].next;
}
if(cnt==0)
printf("0 -1");
else
{
sort(node,node+maxn,cmp);
printf("%d %05dn",cnt,node[0].address);
for(int i=0;i<cnt;i++)
{
if(i!=cnt-1)
printf("%05d %d %05dn",
node[i].address,node[i].data,node[i+1].address);
else
printf("%05d %d -1",node[i].address,node[i].data);
}
}
return 0;
}
|
PAT1074
参考PAT1074,题目的大意是给出一个静态链表,要求我们以k个元素为一组翻转链表中的元素,如果最后的几个元素不到k则无需进行处理
直接定义一个data和next数组用来存储地址的数据和next值,然后对链表进行遍历一遍(在遍历过程中通过cnt来记录链表的元素个数),之后就将一组末尾的数赋值到头部,这个步骤就参考他们的代码,然后理解.
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
|
int main()
{
int first,n,k,num=0,cnt=0;
scanf("%d %d %d",&first,&n,&k);
int data[100005],next[100005],list[100005],ans[100005];
for(int i=0;i<n;i++)
{
int temp;
scanf("%d",&temp);
scanf("%d %d",&data[temp],&next[temp]);
}
while(first!=-1)
{
list[num++]=first;
first=next[first];
cnt++;
}
for(int i=0;i<cnt;i++)
ans[i]=list[i];
for(int i=0;i<cnt-cnt%k;i++)
ans[i]=list[i/k*k+k-1-i%k];
for(int i=0;i<cnt-1;i++)
printf("%05d %d %05dn",ans[i],data[ans[i]],ans[i+1]);
printf("%05d %d -1",ans[cnt-1],data[ans[cnt-1]]);
return 0;
}
|
PAT1032
参考PAT1032,题目的大意就是给出两个链表,寻找第一个相同的节点,就先遍历第一个链表,将遍历到的节点的bool型flag置为true,第二个开始遍历,如果遍历到true的节点输出即可.如果没有相同的话则会一直遍历下去.如果找不到输出-1即可.
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
|
struct node
{
char key;
int next;
bool flag;
}node[100005];
int main()
{
int s1,s2,n;
scanf("%d %d %d",&s1,&s2,&n);
for(int i=0;i<n;i++)
{
char data;
int temp1,temp2;
scanf("%d %c %d",&temp1,&data,&temp2);
node[temp1]={data,temp2,false};
}
for(int i=s1;i!=-1;i=node[i].next)
node[i].flag=true;
for(int i=s2;i!=-1;i=node[i].next)
{
if(node[i].flag==true)
{
printf("%05d",i);
return 0;
}
}
printf("-1");
return 0;
}
|
PAT1097
参考PAT1097,题目的大意是然我们把链表中出现过(绝对值)的值单独形成一个新的链表.
定义结构体中设置一个num(一定要赋初试值)为了后面的排序使用.什么重复问题,开bool的散列表,然后如果没有出现过就放入第一个链表,出现过的话就放入第二个链表,其中给num赋较大值,通过排序处理之后输出两个链表即可
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
44
45
46
47
48
49
50
51
52
53
54
|
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100010;
bool exist[maxn]={false};
struct
{
int address,value,next,num=2*maxn;
}node[maxn];
bool cmp1(Node a, Node b)
{
return a.num < b.num;
}
int main()
{
int first,n,cnt1=0,cnt2=0;
scanf("%d %d",&first,&n);
for(int i=0;i<n;i++)
{
int temp;
scanf("%d",&temp);
scanf("%d %d",&node[temp].value,&node[temp].next);
node[temp].address=temp;
}
for(int i=first;i!=-1;i=node[i].next)
{
if(exist[abs(node[i].value)]==false)
{
exist[abs(node[i].value)]=true;
node[i].num=cnt1;
cnt1++;
}
else
{
node[i].num=maxn+cnt2;
cnt2++;
}
}
sort(node,node+maxn,cmp1);
int cnt=cnt1+cnt2;
for(int i=0;i<cnt;i++)
{
if(i!=cnt1-1&&i!=cnt-1)
printf("%05d %d %05dn",node[i].address,node[i].value,node[i+1].address);
else
printf("%05d %d -1n",node[i].address,node[i].value);
}
return 0;
}
|
近期评论