链表

首先是对链表的介绍（由chatgpt3.5生成）

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表中的节点可以在内存中的任何位置，它们通过指针连接在一起，形成一个链式结构。

链表可以分为单向链表和双向链表两种类型。在单向链表中，每个节点只有一个指针，指向下一个节点；而在双向链表中，每个节点有两个指针，分别指向前一个节点和后一个节点。

链表相对于数组的优势在于插入和删除操作的效率较高。由于链表中的节点可以在内存中的任何位置，因此在插入和删除节点时，只需要修改相邻节点的指针，而不需要移动其他节点。这使得链表在需要频繁插入和删除操作的场景中更加高效。

然而，链表的缺点是访问节点的效率较低。由于链表中的节点不是连续存储的，因此无法通过下标直接访问节点，而是需要从头节点开始遍历链表，直到找到目标节点。这使得链表在需要频繁访问节点的场景中效率较低。

总结起来，链表是一种常见的数据结构，适用于需要频繁插入和删除操作的场景。它的优势在于插入和删除操作的效率较高，但访问节点的效率较低。

啊，gpt老师说得好（鼓掌）

那么就从实际体验中来体会链表吧！

首先是作业里的第一道题

有序集合的交运算

假设以两个元素依次递增有序排序排列的线性表 A 和 B 分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表 C，其元素为 A 和 B 中的元素的交集，且表 C 中的元素也依值递增有序排列。试对顺序表编写求 C 的算法。

输入格式

输入一共有 4 行，每两行描述一个线性表。

第一行为线性表长度 n（0≤ni​<50）。

第二行为线性表的 n 个元素 ai​（0≤ai​<200）。

输出格式

输出一共有两行，第一行为线性表 C 的元素个数。

第二行为线性表 C 的元素顺序输出的结果，按从小到大的顺序输出，每两个整数之间一个空格，最后一个整数后面没有空格。

以下是实现所用的代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node//链表的节点
{
	int data;
	struct node* next;
}Node,*link;//方便后续直接使用link来定义用于指向节点的指针
link Crealist(int n)//创建链表的函数，链表节点数为n
{
	int num[201];//利用数组暂存输入的数据，后来发现并不需要这么麻烦，直接在后面添加节点的循环里的每一个循环里输入一个数就可以了；
	for(int i=0;i<n;++i)
		cin>>num[i];
	link H,P,r;
	H=(link)malloc(sizeof(Node));//开辟地址，使头指针指向一个地址。
	H->next=NULL;
	r=H;//总是指向P节点（新节点）前一个节点的一个指针。
	for(int i=0;i<n;++i)//每一次循环加一个节点
	{
		P=(link)malloc(sizeof(Node));//新的节点
		P->data=num[i];//新节点里存的数据
		r->next=P;//新节点的前一个节点的next指向新节点，使节点之间被连起来。
		r=P;//更新r指针
	}
	return H;//返回头节点
}
link Creaemptylist()//创建一个空链表
{
	link H;
	H=(link)malloc(sizeof(Node));
	H->next=NULL;
	return H;
}
bool findit(int a,link h,int m)//检测能够在链表的前m个节点中找到data为a的节点，如果有，返回true。
{
	link p=h->next;
	for(int i=0;i<m;++i)
	{
		if(p->data==a) return 1;
		p=p->next;
	}
	return 0;
}
int main()
{
	int n,m,nc=0;
	cin>>n; //线性表长度
	link ha=Crealist(n);
	cin>>m;//第二个线性表的长度
	link hb=Crealist(m);
	link hc=Creaemptylist();//合并后的线性表
	link pa,pb,pc,r;//可移动的指针，确保头节点始终能够访问
	pa=ha->next;
	pb=hb->next;
	r=hc;
	for(int i=0;i<n;++i)
	{
		if(findit(pa->data,hb,m))//如果在第二个链表中能够找到和第一个链表第i+1个数相等的数
		{
			nc++;//链表长度+1
			pc=(link)malloc(sizeof(Node));//增加节点
			pc->data=pa->data;
			r->next=pc;
			r=pc;
		}	
		if(i!=n-1) pa=pa->next;//如果没有遍历到最后一个元素
	}
	cout<<nc<<endl;
	link pk=hc->next;
	for(int i=0;i<nc;++i)//输出新链表
	{
		cout<<pk->data;
		pk=pk->next;
		if(i<nc-1) cout<<" ";
	}
	return 0;
}

最直接的算法，做完这道题后算是理解了链表是怎么运行的了。
接下来是后面三道题

哪位同学最优秀

蒜头君想把计算机专业相关的课程都写一遍，放到计蒜客上面帮助同学们学习。但是蒜头君意识到要写的课程有很多很多，蒜头君实在忙不过来，于是他想招几位实习生帮助一块写课程。招聘广告一发，吸引了好多大牛前来应聘，于是蒜头君每天都要安排面试。

有一天，结束了一天面试后，boss 跑来问蒜头君：“小蒜，你觉得今天面试的同学里面，谁最优秀呀，谁最适合写课程呀？”蒜头君递给 boss 一沓简历，回答到：“这里有 N 份简历，boss 你猜猜哪位同学最优秀。”

每份简历都有一个对应的 id，编号从 11 开始，依次从第一份简历到最后一份简历。boss 会从简历里抽掉 M 份简历，每次他随机念一个数字 numi​，然后从第一份简历开始数，数到第 numi​ 份时，就会把对应的简历抽掉，接着念下一个数字。抽掉 M 份简历后，boss 从剩余的简历中，取出最中间的一份简历，然后点点头念道：“我相信这位同学一定最优秀，哈哈”。

现在蒜头君想知道这份简历的 id 是多少，聪明的你能帮他算出来吗？

输入格式

第一行输入两个正整数 N 和 M（1≤M<N≤1000）。

第二行输入 M 个整数 numi​（1≤numi​≤1000），表示 boss 依次念出来的数字。

保证 N−M 是奇数，输入的 numi​ 小于等于当前剩余简历数量。

输出格式

输出为一行，输出 boss 认为最优秀的同学的 id 是多少。

以下是实现代码，和上面操作差不多的就不进行注释了

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
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct Node
{
    int id;
    Node* next;
}node,*link;
link crealist(int n)
{
    link H,p,r;
    H=(link)malloc(sizeof(node));
    H->next =NULL;
    r=H;
    for(int i=1;i<=n;++i)
    {
    	p=(link)malloc(sizeof(node));
    	p->id =i;
    	r->next =p;
    	r=p;
	}
	return H; 
}
link getelem(link H,int i)//找第i个元素
{
	int j=0;
	link p=H;
	if(i<0) return NULL;
	while(p->next&&j<i)
	{
		p=p->next ;
		j++;
	}
	if(i==j) return p;
	else return NULL;
}
void delnum(link H,int i)//删掉第i个元素
{
	link p,q;
	if(i==1) p=H;
	else p=getelem(H,i-1);//取第i-1个元素，方便后续操作
	if(p&&p->next)
	{
		q=p->next ;
		p->next =q->next ;//第i-1个节点的next直接指向第i+1个节点，“孤立”第i个元素
	}
	free(q); //释放已经被孤立的节点，完成删除
}
int main()
{
	int N,M,num;
	cin>>N>>M;
	link h=crealist(N);
	link p;
	p=h;
	int n[1001];
	for(int i=0;i<M;++i)
	{
		cin>>n[i];
		delnum(p,n[i]);//删掉被叫到的那个人
	}
	int great=(N-M+1)/2;//优秀的那个人是第great个人
	cout<<getelem(p,great)->id <<endl;
	return 0;
}

以上代码有“寻找第i个元素”和“删掉第i个元素”的函数

接下来是第三道题

单向链表变双向

已知有一个单向循环链表，其每个结点中含三个域：prior，data 和 next，其中 data 域为数据域，next 为指向后继结点的指针域，prior 也为指针域，但它的值为空 (NULL) ，试编写算法将此单向循环链表改为双向循环链表，即使prior 成为指向前驱结点的指针域。

输入格式

输入共有三行，第一行为该单向循环链表的长度 n（1≤n≤60）。

第二行为该单向循环链表的各个元素 ai​（1≤ai​≤2000），它们各不相同且都为数字。

第三行为一个数字 m，表示链表中的一个元素值，要求输出时以该元素为起点反向输出整个双向链表。

输出格式

输出为一行，即完成双向链表后以反向顺序输出该链表，每两个整数之间一个空格，最后一个整数后面没有空格。

以下是实现代码，和上面操作差不多的就不进行注释了

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct dualnode//节点多了一个指向上一个元素的指针 
{
	int data;
	dualnode* prior;
	dualnode* next;
}node,*link; 
link crealist(int n)
{
	link H,p,r;
	H=(link)malloc(sizeof(node));
	H->next =NULL;
	r=H;
	int num[2001];
	for(int i=0;i<n;++i)
		cin>>num[i];
	for(int i=0;i<n;++i)
	{
		p=(link)malloc(sizeof(node));
		p->data =num[i];
		p->prior=NULL;
		r->next =p;
		r=p;
	}
	return H;
}
void turndual(link H,int n)//对prior指针进行填充 
{
	link p=H->next ;
	link r=H;
	for(int i=0;i<n-1&&p!=NULL;++i)
	{
		p->prior=r;
		r=r->next;
		p=p->next;
	}
	p->prior=r;
}
link otherside(link H,int n)//搜寻链表最后一个节点并返回 
{
	link p;
	p=H;
	for(int i=0;i<n;++i)
		p=p->next;
	return p;
}
link gachat(link H,int a)//元素a在哪个位置 
{
	link p=H;
	while(p->next&&p->next->data !=a)
		p=p->next;
	if(p->next->data==a) return p->next;
	else return NULL;
}
int main()
{
	int n,m;
	cin>>n;
	link H=crealist(n);
	turndual(H,n);  //变双向！ 
	link E=otherside(H,n);    //E是链表最后一个元素 
	cin>>m;    //以哪个元素为起点 
	link changnum=gachat(H,m);  //元素m在第几个位置         
	link p=changnum;
	while(p!=H)//按照要求进行输出 
	{
		cout<<p->data <<" ";
		p=p->prior ;
	}
	while(E!=changnum)
	{
		cout<<E->data<<" ";
		E=E->prior;
	}
	return 0;
}

接下来是最后一道题

蜗牛旅行

蜗牛在制定今天的旅游计划，有 n 个景点可选，它已经把这些景点按照顺路游览的顺序排成一排了，每个地方有相应的景观，这里用一个整数表示。

蜗牛希望选取连续的一段景点，还要选出来的每一个景点的景观都不同，问它最多能选出多少个景点进行旅游。

输入格式

第一行，一个正整数 n(1≤n≤10的5次方)。

第二行，包含 n 个正整数 ai​(1≤ai​≤10的6次方) ，第 i 个整数表示第 i 个景点的景观。

输出格式

输出一行，包含一个整数，表示蜗牛最多能选出的景点数。

数据范围

对于 60% 的数据，1≤n≤10的3次方

对于 100% 的数据，1≤n≤10的5次方,1≤ai​≤10的6次方

以下是实现代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct Node
{
	int data;
	Node* next;
}node,*link;
link crealist(int n)
{
	link p,H,r;
	H=(link)malloc(sizeof(node));
	H->next =NULL;
	r=H;
	int *num=new int[n];
	for(int i=0;i<n;++i)
	{
		cin>>num[i];
		p=(link)malloc(sizeof(node));
		p->data=num[i];
		r->next =p;
		r=p;
	}
	r->next =NULL;
	delete []num;
	return H;
}
link getit(link s,link e)//查找从s到e两个指针之间有没有和e指向的数据相同的数据 
{
	while(s!=e)
	{
		if(s->data ==e->data ) return s;
		else s=s->next ;
	}
	return NULL;
} 
int hm(link s,link it)//s指针和it指针之间有几个节点 
{
	int l=0;
	while(s!=it)
	{
		l++;
		s=s->next;
	}
	return l;
}
int main()
{
	int n,m[1001]={1},i=0;
	cin>>n;
	link H=crealist(n);
	link s=H->next ;
	link e=H->next ;
	while(true)
	{
		if(e->next ==NULL) break;//e遍历到最后时及时退出循环 
		e=e->next;
		link it;
		it=getit(s,e);
		if(it!=NULL) //如果说有重复的景点…… 
		{
			i++;//连续不重复的选择个数+1 
			m[i]=m[i-1]-hm(s,it);//开始数下一个可能的选择有多少景点 
			s=it->next;//重置起点 
		}
		else m[i]++;
	}
	int f=0;
	for(int j=0;j<=i;++j)
		if(m[j]>=f) f=m[j];
	cout<<f;
	return 0;
}

啊，这篇博客到此就结束了，只是记录一下自己的学习。

收藏Shaw的博客谢谢喵~