1.单链表的创建(结构体+链表)(查找数值）
题目描述
1.问题描述
给出初始数据，实现单链表的定义、创建、输出。
2.算法
单链表结点的存储结构包含两部分：数据、下一结点指针。
单链表的创建：输入n个数据e，若数据e不在单链表中，为数据e分配结点，并插入在单链表的尾部；若单链表中已有数据e，则不做任何操作。
单链表的输出：从头至尾遍历单链表，输出每个结点的元素值。
注:程序不可定义任何数组，否则不计成绩。
要求：查找定义子函数：int Find(Node *H,int e) //找到e返回1，找不到返回0。其中Node为链表结点结构体名，H为链表头指针。
输入
第一行：测试次数t
对每组测试数据，格式如下:
数据个数n 数据1 数据2 数据3 … 数据n
输出
对每组测试数据，输出链表中元素个数和单链表中的全部数据。
输入样例
2
5 2 3 5 7 3
6 1 2 10 0 1 5
输出样例
4 2 3 5 7
5 1 2 10 0 5
AC代码
#include<iostream>
using namespace std;
struct node
{
int num;
node* next;
};
//在链表中查找某个元素
int find(node* h, int x)
{
while (h->next != NULL)//当h不是最后一个且h不是空指针
{
h = h->next;//若h为头，h赋值为头后面的首个；若h为倒数第二个，h赋值为最后一个
if (h->num == x)
return 1;
}
return 0;
}
//创建链表同时不出现重复元素
void create(node* h, int& n)//直接引用n，对n进行修改
{
h->next = NULL;
//头指针指向下一个一定要赋值为NULL，防止野指针的出现
node* pp = h, * p2;
int x;
int len = 0;//统计重复的数字
for (int i = 0; i < n; i++)//n次输入
{
cin >> x;
if (find(h, x) == 0)
{
p2 = new node;
p2->next = NULL;
//对临时变量p2赋值,p2也为末尾指针
p2->num = x;
pp->next = p2;
pp = p2;
//pp移动到末尾来进行下次添加元素
}
else
len++;//重复元素
}
n = n - len;//最后所剩元素个数
}
int main()
{
int t, n;
cin >> t;
while (t--)
{
node* h = new node;
cin >> n;
create(h, n);
cout << n << " ";
//链表输出
while (h->next != NULL)
{
h = h->next;
//此步要先进行，因为h->num里面没有输入的值
cout << h->num << " ";
}
cout << endl;
}
return 0;
}2.链表的逆序输出（链表）
题目描述
按数字输入顺序创建单链表。不可借助数组、容器，不可改变原链表、不可开辟新结点空间。编程实现单链表的逆序输出。
输入
测试次数t
每组测试数据一行，格式如下：
数据个数n，后跟n个整数
输出
对每组测试数据，逆序输出单链表。
输入样例
2
10 1 2 3 4 5 6 7 8 9 10
4 19 20 15 -10
输出样例
10 9 8 7 6 5 4 3 2 1
-10 15 20 19
AC代码
#include<iostream>
using namespace std;
struct node
{
int num;
node* next;
};
void create(node* h, int n)
{
h->next = NULL;
int x;
node* pp = h, * p2;
for (int i = 0; i < n; i++)
{
cin >> x;
p2 = new node;
p2->next = NULL;
p2->num = x;
pp->next = p2;
pp = p2;
}
pp->next = NULL;
}
//逆序输出链表采用递归的方法
void reverse(node* h)
{
if (h->next == NULL)//如果到链表的最后一个
{
cout << h->num << " ";
return;//一定要记得return
}
else if (h->next)reverse(h->next);
//先进行reverse后再输出（也就是先去到尾部再往前一个一个输出）
cout << h->num << " ";
return;
//这里同样要return;
//因为已经输出一个数要返回到上一个节点继续输出
}
int main()
{
int t,n;
cin >> t;
while (t--)
{
cin >> n;
node* h = new node;
create(h, n);
reverse(h);
cout << endl;
}
return 0;
}3.单链表的查找（查找下标）(结构体+链表)
题目描述
1.问题描述
给出初始数据，实现单链表的定义、创建、查找。假设单链表中的结点计数从1开始。
2.算法
单链表结点的存储结构包含两部分：数据、下一结点指针。
单链表的创建：依次为输入的数据分配结点，并按序链接起来。
单链表结点个数L(也称单链表表长L)：从头至尾遍历单链表，对结点进行计数。
单链表的查找：给出位置i,若第i个结点存在(1<=i<=L)，返回结点地址；否则，返回NULL。
要求查找子函数定义为：Node *Find(Node *H,int i)
//若i的值在1…单链表长L之间，返回第i个结点的地址；否则返回空指针NULL。其中Node为链表结点结构体名，H为链表头指针。
输入
每个样本分2行：
第一行：第一个数字n表示样本数目，其后跟n个样本。
第二行：查找测试次数m 后跟m个待查找的位置。
输出
第一行：单链表创建后，输出链表中元素个数和单链表中的全部数据。
第二行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error。
输入样例
6 1 2 3 4 5 8
4 0 2 10 6
输出样例
6 1 2 3 4 5 8
error
2
error
8
AC代码
#include<iostream>
using namespace std;
struct node
{
int num;
node* next;
};
void create(node* h, int n)
{
h->next = NULL;
int x;
node* pp = h, * p2;
for (int i = 0; i < n; i++)
{
cin >> x;
p2 = new node;
p2->next = NULL;
p2->num = x;
pp->next = p2;
pp = p2;
}
}
node* find(node* h, int x)//返回一个结点node*型，注意x为下标
{
if (x <= 0)return NULL;
//特判，因为x从1开始
node* p = h;
int j = 1;
while (p != NULL && j <= x)//不用p->next!=NULL是因为p可以为最后一个,注意j能为x,注意p才会是第x个结点
{
p = p->next;//j==1时p为链表的首元素
j++;
}
return p;
//返回结点
}
int main()
{
int n;
cin >> n;
node* h = new node;
create(h, n);
//输出链表
cout << n << " ";
node* p = h;//保留h不变
while (p->next != NULL)
{
p = p->next;
cout << p->num << " ";
}
cout << endl;
//开始询问
int q;
cin >> q;
while (q--)
{
int x;
cin >> x;
if (find(h, x) != NULL)cout << find(h, x)->num << endl;
else cout << "error" << endl;
}
return 0;
}4.单链表的插入（指定某位置插入某元素）(结构体+链表)
题目描述
1.问题描述
单链表初始为空，给定插入位置和数据，插入结点实现单链表的创建。假设单链表中的结点计数从1开始。
2.算法
单链表结点的存储结构包含两部分：数据、下一结点指针
单链表的查找：给出位置i，若第i个结点存在(1<=i<=表中结点数L)，返回结点地址；否则，返回NULL。
单链表的插入：给出位置i和数据e，在单链表第i(1<=i<=L+1)个结点位置插入新结点，数据为e。
输入
测试次数n
每行一组测试数据,格式如下：
位置i 数据e
输出
对每组测试数据，调用插入函数在位置i插入数据e，若插入成功，输出当前链表中的数据；若插入不成功，输出error。
输入样例
8
0 10
1 10
2 20
3 30
1 40
6 60
5 50
9 100
输出样例
error
10
10 20
10 20 30
40 10 20 30
error
40 10 20 30 50
error
AC代码
#include<iostream>
using namespace std;
struct node
{
int num;
node* next;
};
bool insert(node* h, int idx, int val)//返回能否插入成功
{
if (idx<1 || idx>h->num)//若下标不满足条件，无法插入
return false;
node* p = new node;
node* q = h;
p->num = val;
//先找到idx-1的位置
for (int i = 1; i < idx; i++)
{
q = q->next;
}
p->next = q->next;//这条语句一定要在前面
q->next = p;
h->num++;
//h->num表示可插入的最大坐标！！（那一位是无元素的）
return true;
}
int main()
{
int n;
cin >> n;
node* h = new node;
h->next = NULL;
//头指针要初始好
h->num = 1;//要初始为1,因为当idx==1时，可以插入，且h->num表示可插入的最大坐标！！
while (n--)
{
int i, e;
cin >> i >> e;
int d = insert(h, i, e);
//插入成功后h已经改变了
node* p = h;
if (d == 0)
cout << "error" << endl;
else
{
//注意这里输出与前面不太一样
//最后一个元素后面直接换行没有空格
//这也是为什么要用h->num储存元素个数的原因
for (int i = 1; i <= h->num; i++)
{
if (p->next != NULL)//不能为最后一位，因为最后一位没有元素
{
p = p->next;
cout << p->num;
if (i != h->num-1)//不是最后一个元素时，输出空格
{
cout << " ";
}
}
}
cout << endl;
}
}
return 0;
}5.单链表的删除(结构体+链表)
题目描述
1.问题描述
给出初始数据，实现单链表的定义、创建、查找和删除。假设单链表中的结点计数从1开始。
2.算法
单链表结点的存储结构包含两部分：数据、下一结点指针。
单链表的创建：依次为输入的数据分配结点，并按序链接起来。
单链表的查找：给出位置i，若第i个结点存在(1<=i<=表中结点数L)，返回结点地址；否则，返回NULL。
单链表的删除：给出位置i，删除第i个结点(1<=i<=L)。
要求定义删除函数：int DeleteList(Node *H,int i) //删除第i个结点成功，返回1；第i个结点不存在，删除不成功，返回0。其中Node是链表结点结构体名，H是链表头指针。
输入
每个样本分2行：
第一行：第一个数字n表示样本数目，其后跟n个样本
第二行：删除测试次数m 后跟m个删除位置
输出
第一行：单链表创建后，输出链表中元素个数和单链表中的全部数据。
第二行至第m+1行：若删除指定位置的数据成功，输出链表中元素个数和单链表中的全部数据；若删除不成功，输出error。
输入样例
5 2 4 3 5 7
3 0 2 4
输出样例
5 2 4 3 5 7
error
4 2 3 5 7
3 2 3 5
AC代码
#include<iostream>
using namespace std;
struct node
{
int num;
node* next;
};
void create(node* h, int n)
{
h->next = NULL;
node* pp = h, * p2;
int x;
for (int i = 0; i < n; i++)
{
cin >> x;
p2 = new node;
p2->next = NULL;
p2->num = x;
pp->next = p2;
pp = p2;
}
}
bool ddelete(node* h, int dix,int &n)//返回能不能删除成功
{
if (dix<1 || dix>n)
return 0;
n--;
node* pre = h;//为p的前一个结点
node* p = h->next;//初始为链表首元素
int count = 1;//统计下标(p的结点下标）
while (p != NULL)
{
if (count == dix)
{
pre->next = p->next;
//delete(p);
p = NULL;
return true;
}
count++;
pre = pre->next;
p = p->next;
}
return false;
}
//这里要多次输出链表使用函数方便
void show(node* h,int n)
{
cout << n;
node* p = h;
while (p->next != NULL)
{
p = p->next;
cout << " " << p->num;
//这样最后一个不会输出空格（前提是要输出总数）
}
cout << endl;
}
int main()
{
int q, n;
cin >> n;
node* h = new node;
create(h, n);
show(h,n);
cin >> q;
while (q--)
{
int x;
cin >> x;
if (ddelete(h, x, n))
show(h, n);
else
cout << "error" << endl;
}
return 0;
}