文章目录
- 第1关：实现顺序表各种基本运算的算法
- 任务描述
- 编程要求
- 完整代码
- 第2关：实现单链表各种基本运算的算法
- 任务描述
- 编程要求
- 完整代码
- 第3关：移除顺序表中所有值等于x的元素
- 任务描述
- 编程要求
- 完整代码
- 第4关：逆置顺序表
- 任务描述
- 编程要求
- 完整代码
- 第5关：删除有序顺序表中的重复项
- 任务描述
- 编程要求
- 完整代码
- 第6关：拆分单链表
- 任务描述
- 相关知识
- 编程要求
- 完整代码
- 第7关：删除单链表中值最大的结点
- 任务描述
- 编程要求
- 测试说明
- 完整代码
- 第8关：单链表插入排序
- 任务描述
- 相关知识
- 编程要求
- 测试说明
- 完整代码
- 第9关：逆置单链表
- 任务描述
- 编程要求
- 测试说明
- 完整代码
- 第10关：移除链表元素
- 任务描述
- 编程要求
- 测试说明
- 完整代码
- 第11关：约瑟夫环
- 任务描述
- 编程要求
- 测试说明
- 完整代码
- 第12关：链表的中间结点
- 任务描述
- 编程要求
- 测试说明
- 完整代码
- 第13关：回文链表
- 编程要求
- 测试说明
- 完整代码
- 第14关：中位数
- 任务描述
- 编程要求
- 测试说明
- 完整代码
- 第15关：合并两个有序链表
- 任务描述
- 编程要求
- 测试说明
- 提示:
- 完整代码
第1关：实现顺序表各种基本运算的算法
任务描述
本关任务：实现顺序表各种基本运算的算法。
目的: 领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。
内容: 编写程序，实现顺序表的各种基本运算和整体建表算法(假设顺序表的元素类型ElemType 为char)，并在此基础上设计一个主程序，完成如下功能:
(1)初始化顺序表L。
(2)依次插入a、b、c、d、e元素。
(3)输出顺序表L。
(4)输出顺序表L长度。
(5)判断顺序表L是否为空。
(6)输出顺序表L的第3个元素。
(7)输出元素a的位置。
(8)在第4个元素位置上插入f元素。
(9)输出顺序表L。
(10)删除顺序表L的第3个元素。
(11)输出顺序表L。
(12)释放顺序表L。
编程要求
根据提示，在右侧编辑器补充代码，完成线性表基本运算算法实现。
测试说明
平台会对你编写的代码进行测试：
输入样例：
参见题目功能说明。
输出样例：
参见题目功能说明。
整体输出顺序表时，每个数据后面一个空格。
顺序表的基本运算如下:
(1)初始化顺序表L
(2)依次插入a,b,c,d,e元素
(3)输出顺序表L:a b c d e
(4)顺序表L长度:5
(5)顺序表L为非空
(6)顺序表L的第3个元素:c
(7)元素a的位置:1
(8)在第4个元素位置上插入f元素
(9)输出顺序表L:a b c f d e
(10)删除L的第3个元素
(11)输出顺序表L:a b f d e
(12)释放顺序表L
开始你的任务吧，祝你成功！
完整代码
//顺序表运算算法
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize]; //存放顺序表元素
int length; //存放顺序表的长度
} SqList; //声明顺序表的类型
/**
* 初始化顺序表L。
*/
void InitList(SqList * &L);
/**
* 释放顺序表L。
*/
void DestroyList(SqList * &L);
/**
* 判断顺序表L是否为空表。
* 空表返回true，非空表返回false。
*/
bool ListEmpty(SqList * L);
/**
* 返回顺序表L的元素个数。
*/
int ListLength(SqList * L);
/**
* 输出顺序表L。
*/
void DispList(SqList * L);
/**
* 获取顺序表L中第i(1≤i≤L->length)个元素，将其值存入e，然后返回true；
* 如果不能获取到第i个元素，返回false。
*/
bool GetElem(SqList * L, int i, ElemType &e);
/**
* 在顺序表L中查找元素e。
* 如果存在e，则返回e的逻辑序号，否则返回0。
*/
int LocateElem(SqList * L, ElemType e);
/**
* 在顺序表L中第ii(1≤i≤L->length)个位置上插入元素e。
* 插入成功，返回true。插入不成功，返回false。
*/
bool ListInsert(SqList * &L, int i, ElemType e);
/**
* 从顺序表L中删除第ii(1≤i≤L->length)个元素。
* 删除成功，返回true。删除不成功，返回false。
*/
bool ListDelete(SqList * &L, int i, ElemType &e);
int main()
{
SqList *L;
ElemType e;
printf("顺序表的基本运算如下:\n");
printf(" (1)初始化顺序表L\n");
InitList(L);
printf(" (2)依次插入a,b,c,d,e元素\n");
ListInsert(L, 1, 'a');
ListInsert(L, 2, 'b');
ListInsert(L, 3, 'c');
ListInsert(L, 4, 'd');
ListInsert(L, 5, 'e');
printf(" (3)输出顺序表L:");
DispList(L);
printf(" (4)顺序表L长度:%d\n", ListLength(L));
printf(" (5)顺序表L为%s\n", (ListEmpty(L) ? "空" : "非空"));
GetElem(L, 3, e);
printf(" (6)顺序表L的第3个元素:%c\n", e);
printf(" (7)元素a的位置:%d\n", LocateElem(L, 'a'));
printf(" (8)在第4个元素位置上插入f元素\n");
ListInsert(L, 4, 'f');
printf(" (9)输出顺序表L:");
DispList(L);
printf(" (10)删除L的第3个元素\n");
ListDelete(L, 3, e);
printf(" (11)输出顺序表L:");
DispList(L);
printf(" (12)释放顺序表L\n");
DestroyList(L);
return 0;
}
/* 请在下面填写代码 */
void InitList(SqList *&L) //初始化线性表
{
/****************Begin******************/
L = (SqList *)malloc(sizeof(SqList));
L->length = 0;
/******************End******************/
}
void DestroyList(SqList *&L) //销毁线性表
{
/****************Begin******************/
free(L);
/******************End******************/
}
bool ListEmpty(SqList *L) //判线性表是否为空表
{
/****************Begin******************/
return (L->length==0);
/******************End******************/
}
int ListLength(SqList *L) //求线性表的长度
{
/****************Begin******************/
return (L->length);
/******************End******************/
}
void DispList(SqList *L) //输出线性表
{
/****************Begin******************/
for(int i=0; i<L->length; i++) {
printf("%c ", L->data[i]);
}
printf("\n");
/******************End******************/
}
bool GetElem(SqList *L, int i, ElemType &e) //求线性表中第i个元素值
{
/****************Begin******************/
if(i<1 || i>L->length) {
return false;
}
e=L->data[i-1];
return true;
/******************End******************/
}
int LocateElem(SqList *L, ElemType e) //查找第一个值域为e的元素序号
{
/****************Begin******************/
int i = 0;
while(i<L->length && L->data[i]!=e) {
i++;
}
if(i>=L->length){
return 0;
}else{
return i+1;
}
/******************End******************/
}
bool ListInsert(SqList *&L, int i, ElemType e) //插入第i个元素
{
/****************Begin******************/
int j;
if(i<1 || i>((L->length)+1) || (L->length)==MaxSize) {
return false;
}
i--;
for(j=L->length; j>i; j--) {
L->data[j] = L->data[j-1];
}
L->data[i] = e;
L->length++;
return true;
/******************End******************/
}
bool ListDelete(SqList *&L, int i, ElemType &e) //删除第i个元素
{
/****************Begin******************/
int j;
if(i<1 || i>L->length) {
return false;
}
i--;
e = L->data[i];
for(j=i; j<L->length-1; j++) {
L->data[j] = L->data[j+1];
}
L->length--;
return true;
/******************End******************/
}
第2关：实现单链表各种基本运算的算法
任务描述
本关任务：实现单链表各种基本运算的算法。
目的: 领会单链表存储结构和掌握单链表中各种基本运算算法设计。
内容: 实现单链表的各种基本运算(假设单链表的元素类型ElemType为char)，并在此基础上设计一个程序，完成如下功能:
(1)初始化单链表h。
(2)依次采用尾插法插入a、b、c、d、e元素。
(3)输出单链表h。
(4)输出单链表h长度。
(5)判断单链表h是否为空。
(6)输出单链表h的第3个元素。
(7)输出元素a的位置。
(8)在第4个元素位置上插入f元素。
(9)输出单链表h。
(10)删除单链表h的第3个元素。
(11)输出单链表h。
(12)释放单链表h。
编程要求
根据提示，在右侧编辑器Begin…End之间补充代码，实现单链表基本运算算法。
测试说明
平台会对你编写的代码进行测试：
输入样例：
参见题目功能说明。
输出样例：
参见题目功能说明。
整体输出单链表表时，每个数据后面一个空格。
单链表的基本运算如下:
(1)初始化单链表h
(2)依次采用尾插法插入a,b,c,d,e元素
(3)输出单链表h:a b c d e
(4)单链表h长度:5
(5)单链表h为非空
(6)单链表h的第3个元素:c
(7)元素a的位置:1
(8)在第4个元素位置上插入f元素
(9)输出单链表h:a b c f d e
(10)删除h的第3个元素
(11)输出单链表h:a b f d e
(12)释放单链表h
开始你的任务吧，祝你成功！
完整代码
//单链表运算算法
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next; //指向后继结点
} LinkNode; //单链表结点类型
/**
* 头插法建立单链表
*/
void CreateListF(LinkNode *&L, ElemType a[], int n);
/**
* 尾插法建立单链表
*/
void CreateListR(LinkNode *&L, ElemType a[], int n);
/**
* 初始化线性表
*/
void InitList(LinkNode *&L);
/**
* 销毁线性表
*/
void DestroyList(LinkNode *&L);
/**
* 判线性表是否为空表。空表返回true，否则返回false。
*/
bool ListEmpty(LinkNode *L);
/**
* 求线性表的长度
*/
int ListLength(LinkNode *L);
/**
* 输出线性表: 每个数据后面一个空格
*/
void DispList(LinkNode *L);
/**
* 求线性表中第i个元素值。
* 存在第i个数据结点,其值存入e,然后返回true。
* 不存在第i个数据结点,返回false。
*/
bool GetElem(LinkNode *L, int i, ElemType &e);
/**
* 查找第一个值域为e的元素序号。
* 若存在，返回其逻辑序号；若不存在，返回0。
*/
int LocateElem(LinkNode *L, ElemType e);
/**
* 插入第i个元素。
* 插入成功，返回true；插入不成功，返回false。
*/
bool ListInsert(LinkNode *&L, int i, ElemType e);
/**
* 删除第i个元素。
* 如果第i个元素存在，其值存入e，返回true；
* 如果第i个元素不存在，返回false。
*/
bool ListDelete(LinkNode *&L, int i, ElemType &e) ;
int main() {
LinkNode *h;
ElemType e;
printf("单链表的基本运算如下:\n");
printf(" (1)初始化单链表h\n");
InitList(h);
printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(h, 1, 'a');
ListInsert(h, 2, 'b');
ListInsert(h, 3, 'c');
ListInsert(h, 4, 'd');
ListInsert(h, 5, 'e');
printf(" (3)输出单链表h:");
DispList(h);
printf(" (4)单链表h长度:%d\n", ListLength(h));
printf(" (5)单链表h为%s\n", (ListEmpty(h) ? "空" : "非空"));
GetElem(h, 3, e);
printf(" (6)单链表h的第3个元素:%c\n", e);
printf(" (7)元素a的位置:%d\n", LocateElem(h, 'a'));
printf(" (8)在第4个元素位置上插入f元素\n");
ListInsert(h, 4, 'f');
printf(" (9)输出单链表h:");
DispList(h);
printf(" (10)删除h的第3个元素\n");
ListDelete(h, 3, e);
printf(" (11)输出单链表h:");
DispList(h);
printf(" (12)释放单链表h\n");
DestroyList(h);
return 0;
}
/* 请在下面编写程序代码 */
/**
* 头插法建立单链表
*/
void CreateListF(LinkNode *&L, ElemType a[], int n) {
/**************************Begin***************************/
LinkNode *s;
L = (LinkNode *)malloc(sizeof(LinkNode)); //为链表L分配内存空间，创建头结点
L->next = NULL; // 先将指向的地址为空，相当于头指针为空
// 对数组处理
for(int i=0; i<n; i++) {
s = (LinkNode *)malloc(sizeof(LinkNode)); //为链表s分配内存空间
s->data = a[i]; // 存入数据
s->next = L->next; // 指向下一节点
L->next = s; // 指向s
}
/***************************End****************************/
}
/**
* 尾插法建立单链表
*/
void CreateListR(LinkNode *&L, ElemType a[], int n) {
/**************************Begin***************************/
LinkNode *s, *r;
r = NULL;
for(int i=0; i<n; i++) {
s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = a[i];
s->next = NULL;
if(r==NULL) {
L = s;
r = s;
}else{
r->next = s;
r = s;
}
}
r->next = NULL;
/***************************End****************************/
}
/**
* 初始化线性表
*/
void InitList(LinkNode *&L) {
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL; //单链表置为空表
}
/**
* 销毁线性表
*/
void DestroyList(LinkNode *&L) {
LinkNode *pre = L, *p;
while (p != NULL) {
p = pre->next;
free(pre);
pre = p;
}
L = NULL;
}
/**
* 判线性表是否为空表。空表返回true，否则返回false。
*/
bool ListEmpty(LinkNode *L) {
/**************************Begin***************************/
return (L == NULL);
/**************************End***************************/
}
/**
* 求线性表的长度
*/
int ListLength(LinkNode *L) {
/**************************Begin***************************/
int i;
LinkNode *p = L; // p指向头节点
for(i=0; p->next != NULL; i++) {
p = p->next;
}
return i;
/***************************End****************************/
}
/**
* 输出线性表: 每个数据后面一个空格
*/
void DispList(LinkNode *L) {
/**************************Begin***************************/
LinkNode *p = L; //p指向首结点
while (p != NULL&&p->next!=NULL) { //p不为NULL,输出p结点的data域
printf("%c ", p->data);
p = p->next; //p移向下一个结点
}
printf("\n");
/***************************End****************************/
}
/**
* 求线性表中第i个元素值。
* 存在第i个数据结点,其值存入e,然后返回true。
* 不存在第i个数据结点,返回false。
*/
bool GetElem(LinkNode *L, int i, ElemType &e) {
/**************************Begin***************************/
LinkNode *p=L; // 从头开始遍历
int count = 0; // 用于计数当前遍历到的结点序号
while (p != NULL) {
count++;
if (count == i) { // 如果当前结点序号等于i，则将该结点的数据域值存入e中
e = p->data;
return true;
}
p = p->next;
}
return false; // 遍历完整个链表仍然没有找到第i个元素，返回false
/***************************End****************************/
}
/**
* 查找第一个值域为e的元素序号。
* 若存在，返回其逻辑序号；若不存在，返回0。
*/
int LocateElem(LinkNode *L, ElemType e) {
/**************************Begin***************************/
int count = 1;
while (L != NULL) {
if(L->data == e) {
return count;
}
L = L->next;
count++;
}
return 0;
/***************************End****************************/
}
/**
* 插入第i个元素。
* 插入成功，返回true；插入不成功，返回false。
*/
bool ListInsert(LinkNode *&L, int i, ElemType e) {
/**************************Begin***************************/
if(i<1 || L==NULL) {
return false;
}
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = e;
s->next = NULL;
if(i==1) { // 如果插入到头部
s->next = L;
L = s;
} else { // 如果插入到中间或尾部
LinkNode *p = L; // 当前指针结点
int count = 1;
while(p!=NULL&&count<i-1) {
p = p->next;
count++;
}
if(p == NULL) {
return false; // 到达链表尾部，无法插入
}
s->next = p->next;
p->next = s;
}
return true; // 成功插入返回true
/***************************End****************************/
}
/**
* 删除第i个元素。
* 如果第i个元素存在，其值存入e，返回true；
* 如果第i个元素不存在，返回false。
*/
bool ListDelete(LinkNode *&L, int i, ElemType &e) {
/**************************Begin***************************/
if(L==NULL || i<1) {
return false;
}
int count = 1;
LinkNode *p = L;
while(p!=NULL && count<i-1) {
p = p->next;
count++;
}
if(p==NULL) {
return false;
}
e = p->data;
LinkNode *q = p->next;
p->next = q->next;
free(q);
return true;
/***************************End****************************/
}
第3关：移除顺序表中所有值等于x的元素
任务描述
本关任务：假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于x的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。
编程要求
根据提示，在右侧编辑器补充代码，完成函数removeElems(SqList* &L, ElemType x)。
测试说明
输入
输入包括3行。
第一行为顺序表中元素的个数n。
第二行为空格隔开的n个整数。
第三行为需要删除的元素x。
输出
输出包含2行。
第一行输出顺序表所有元素，每个元素后面一个空格。
第二行为删除x后顺序表所有元素，每个元素后面一个空格。
样例输入1
10
1 2 2 1 0 2 4 2 3 1
2
样例输出1
顺序表L中的元素为: 1 2 2 1 0 2 4 2 3 1
移除 2 后顺序表L中的元素为: 1 1 0 4 3 1
样例输入2
4
3 2 2 3
3
样例输出2
顺序表L中的元素为: 3 2 2 3
移除 3 后顺序表L中的元素为: 2 2
样例输入3
8
0 1 2 2 3 0 4 2
2
样例输出3
顺序表L中的元素为: 0 1 2 2 3 0 4 2
移除 2 后顺序表L中的元素为: 0 1 3 0 4
提示
1 <= 顺序表长度 <= 100
0 <= 元素值 <= 50
0 <= x <= 100
开始你的任务吧，祝你成功！
完整代码
#include "sqlist.h"
/**
* 移除顺序表中值为x的所有元素
*/
void removeElements(SqList *&L, ElemType x);
int main()
{
int n, *a, x;
scanf("%d", &n);
a = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
SqList *L;
CreateList(L, a, n);
printf("顺序表L中的元素为: "); DispList(L);
scanf("%d", &x); //输入需要移除的元素
removeElements(L, x);
printf("移除 %d 后顺序表L中的元素为: ", x); DispList(L);
return 0;
}
/**
* 移除顺序表中值为x的所有元素
*/
void removeElements(SqList *&L, ElemType x)
{
//请在下面编写代码
/***************************Begin**********************/
int i=0;
int j=0;
while(i<L->length) {
if(L->data[i]!=x) {
L->data[j] = L->data[i];
j++;
}
i++;
}
L->length = j;
/****************************End***********************/
}
第4关：逆置顺序表
任务描述
编程要求
根据提示，在右侧编辑器补充函数rev的代码，使用顺序表L的空间就地逆置L。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行为顺序表中元素个数n。
第二行为空格隔开的n个整数。
输出格式
输出包括两行。
第一行为顺序表逆置之前的元素。每个数据后一个空格。
第二行为顺序表逆置之后的元素。每个数据后一个空格。
样例输入
5
1 2 3 4 5
样例输出
1 2 3 4 5
5 4 3 2 1
开始你的任务吧，祝你成功！
完整代码
#include <stdio.h>
#include <stdlib.h>
#include "sqlist.h"
/**
* 就地逆置顺序表
*/
void rev(SqList* &L) {
//请在下面编写代码
/******************Begin******************/
int k;
int i=0;
int j=(L->length)-1;
while(i<L->length/2&&i<=j) {
k = L->data[i];
L->data[i] = L->data[j];
L->data[j] = k;
i++;
j--;
}
/*******************End*******************/
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
int *a = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
SqList* L;
InitList(L); //初始化顺序表
CreateList(L, a, n);//创建顺序表
DispList(L); //输出顺序表
rev(L); //逆置顺序表
DispList(L); //输出逆置后的顺序表
DestroyList(L); //销毁顺序表
free(a); //是否数组a
return 0;
}
第5关：删除有序顺序表中的重复项
任务描述
本关任务：编写一个效率尽可能高的算法，删除有序顺序表中的重复元素，重复的元素只保留一个。元素的 相对顺序 应该保持 一致 。
编程要求
根据提示，在右侧编辑器补充完成函数void remove_duplicates(SqList* &L)的代码，删除有序顺序表中的重复项。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行为顺序表中元素个数n。
第二行为空格隔开的n个整数。
输出格式
输出包括两行。
第一行为有序顺序表原有的元素。每个数据后一个空格。
第二行为删除有序顺序表重复项之后的元素。每个数据后一个空格。
样例输入1
3
1 1 2
样例输出1
1 1 2
1 2
样例输入2
10
0 0 1 1 1 2 2 3 3 4
样例输出2
0 0 1 1 1 2 2 3 3 4
0 1 2 3 4
开始你的任务吧，祝你成功！
完整代码
#include <stdio.h>
#include <stdlib.h>
#include "sqlist.h"
/**
* 删除有序顺序表中的重复项
*/
void remove_duplicates(SqList* &L) {
//请在下面编写代码
/******************Begin******************/
int k;
int j=0;
for(k=1; k<L->length; k++) { // 看是否有重复的项
if(L->data[j] != L->data[k]) {
j++;
L->data[j] = L->data[k];
}
}
L->length = j+1;
/*******************End*******************/
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
int *a = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
SqList* L;
InitList(L); //初始化顺序表
CreateList(L, a, n); //创建顺序表
DispList(L); //输出顺序表
remove_duplicates(L); //删除有序顺序表中的重复项
DispList(L); //输出顺序表
DestroyList(L); //销毁顺序表
free(a); //释放数组
return 0;
}
第6关：拆分单链表
任务描述
拆分单链表
相关知识
为了完成本关任务，你需要掌握：1.单链表的基本概念，2.如何创建、遍历单链表。
单链表的基本概念
单链表是线性表的链式存储结构实现。如下图所示：
单链表
单链表的头结点
为了操作方便，有时候会在单链表第一个元素结点的前面增加一个附加头结点，如下图所示：
带附加头结点的单链表
单链表增加一个头结点的优点如下：
首结点的操作和表中其他结点的操作相一致，无需进行特殊处理；
无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。
单链表结点类型定义
单链表中结点类型LinkNode的定义如下:
typedef struct LNode //定义单链表结点类型
{
ElemType data; //存储元素
struct LNode *next; //指向后继结点
} LinkNode;
单链表的特点
单链表的特点：当访问过一个结点 p 后，只能接着访问它的后继结点，而无法访问它的前驱结点。
单链表插入一个结点
插入操作：将值为x的新结点s插入到p结点之后。
特点：只需修改相关结点的指针域，不需要移动结点。
插入操作如下图所示：
单链表插入结点
单链表删除一个结点
删除操作：删除p结点之后的一个结点。
特点：只需修改相关结点的指针域，不需要移动结点。
删除操作如下图所示：
删除操作的语句如下：
p->next = p->next->next;
创建单链表
头插法建立单链表
从一个空表开始，创建一个头结点。
依次读取线性表中的元素，生成新结点s。
将新结点插入到当前链表的表头上，直到结束为止。
头插法建立单链表如下图所示：
建表语句如下：
void CreateListF(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
s->next = L->next; //将结点s插在原开始结点之前,头结点之后
L->next = s;
}
}
尾插法建立单链表
从一个空表开始，创建一个头结点。
依次读取线性表中的元素，生成新结点s
将新结点插入到当前链表的表尾上，直到结束为止。
尾插法建立单链表如下图所示：
建表语句如下：
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //终端结点next域置为NULL
}
输出单链表
逐一扫描单链表L的每个数据结点，并显示各结点的data域值。
编程要求
根据提示，在右侧编辑器补充代码，完成函数void split(LinkNode *&L, LinkNode *&L1, LinkNode *&L2)，将单链表L拆分为L1和L2。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行为单链表中元素个数n。
第二行为空格隔开的n个整数。
输出格式
输出包括四行。
第一行为单链表的元素。每个数据后一个空格。
第二行显示提示信息。
第三行显示单链表L1中的元素。每个数据后一个空格。
第四行显示单链表L2中的元素。每个数据后一个空格。
样例输入
6
1 2 3 4 5 6
样例输出
L: 1 2 3 4 5 6
L->L1,L2
L1: 1 3 5
L2: 6 4 2
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
//将单链表L拆分成两个单链表L1和L2。
void split(LinkNode *&L, LinkNode *&L1, LinkNode *&L2)
{
//请在下面编写代码
/**********************Begin**********************/
LinkNode *p = L->next, *q, *r1;
L1 = L;
r1 = L1; // r1指向L1的尾结点
L2 = (LinkNode *)malloc(sizeof(LinkNode));
L2->next = NULL;
while(p!=NULL) {
r1->next = p;
r1 = p;
p = p->next;
q = p->next;
p->next = L2->next;
L2->next = p;
p = q;
}
r1->next = NULL;
/***********************End***********************/
}
int main()
{
LinkNode *L, *L1, *L2;
int n;
scanf("%d", &n);
ElemType a[n];
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
InitList(L); //初始化单链表L
InitList(L1); //初始化单链表L1
InitList(L2); //初始化单链表L2
CreateListR(L, a, n); //创建单链表L
printf("L: "); DispList(L); //输出单链表L
printf("L->L1,L2\n");
split(L, L1, L2); //单链表L拆分为L1和L2
printf("L1: "); DispList(L1); //输出单链表L1
printf("L2: "); DispList(L2); //输出单链表L2
DestroyList(L1); //销毁单链表L1
DestroyList(L2); //销毁单链表L2
return 0;
}
第7关：删除单链表中值最大的结点
任务描述
本关任务：设计一个算法，删除一个单链表L中元素值最大的结点（假设最大值结点是唯一的）。
编程要求
根据提示，在右侧编辑器补充代码，完成函数void del_max_node(LinkNode *&L)，其中L为带头结点的单链表，函数功能是删除单链表L中值最大的结点。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行为单链表中元素个数n。
第二行为空格隔开的n个整数。
输出格式
输出包括两行。
第一行为单链表的元素。每个数据后一个空格。
第二行为删除值最大的元素之后的单链表。每个数据后一个空格。
样例输入1
6
3 0 2 7 8 6
样例输出1
L: 3 0 2 7 8 6
L: 3 0 2 7 6
样例输入2
1
3
样例输出2
L: 3
L: NULL
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 删除单链表中最大元素的结点。假定值最大的结点唯一。
*/
void del_max_node(LinkNode *&L)
{
//请在下面编写代码
/******************Begin******************/
LinkNode *p=L->next, *pre=L, *maxp=p, *maxpre=pre;
while(p!=NULL) {
if(maxp->data<p->data) {
maxp = p;
maxpre = pre;
}
pre = p;
p = p->next;
}
maxpre->next = maxp->next;
free(maxp);
/*******************End*******************/
}
int main()
{
LinkNode *L;
// int n = 10;
// ElemType a[] = {1, 3, 2, 9, 0, 4, 7, 6, 5, 8};
int n;
scanf("%d", &n);
int *a = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
CreateListR(L, a, n); //创建单链表
printf("L: "); DispList(L); //输出单链表
del_max_node(L); //删除单链表中最大值结点
printf("L: "); DispList(L); //输出单链表
DestroyList(L); //销毁单链表
free(a); //释放数组
return 0;
}
第8关：单链表插入排序
任务描述
本关任务：有一个带头结点的单链表L（至少有一个数据结点），设计一个算法使其元素递增有序排列。
相关知识
单链表结点类型定义：
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next; //指向后继结点
} LinkNode; //声明单链表结点类型
编程要求
根据提示，在右侧编辑器补充代码，完成函数void sort_list(LinkNode *&L)，该函数功能是对带头结点的单链表L进行插入排序，使其递增有序。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行为一个整数n。
第二行为空格隔开的n个整数。
输出格式
输出包括两行。
第一行为排序之前的单链表。每个数据后一个空格。
第二行为递增排序之后的单链表。每个数据后一个空格。
样例输入
10
1 3 2 9 0 4 7 6 5 8
样例输出
L: 1 3 2 9 0 4 7 6 5 8
L: 0 1 2 3 4 5 6 7 8 9
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 单链表L递增（插入）排序
*/
void sort_list(LinkNode *&L)
{
//请在下面编写代码
/******************Begin******************/
LinkNode *p, *pre, *q;
p = L->next->next;
L->next->next = NULL;
while(p!=NULL) {
q = p->next;
pre = L;
while(pre->next!=NULL && pre->next->data<p->data) {
pre = pre->next;
}
p->next = pre->next;
pre->next = p;
p =q;
}
/*******************End*******************/
}
int main()
{
LinkNode *L;
// int n = 10;
// ElemType a[] = {1, 3, 2, 9, 0, 4, 7, 6, 5, 8};
int n;
scanf("%d", &n);
int *a = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
CreateListR(L, a, n); //创建单链表
printf("L: "); DispList(L); //输出单链表
sort_list(L); //单链表递增排序
printf("L: "); DispList(L); //输出排序后的单链表
DestroyList(L); //销毁单链表
free(a); //释放数组
return 0;
}
第9关：逆置单链表
任务描述
编程要求
根据提示，在右侧编辑器补充代码，完成函数void rev_list(LinkNode *&L);该函数功能为对带头结点的单链表L进行逆置。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行为单链表中元素个数n。
第二行为空格隔开的n个整数。
输出格式
输出包括一行，为单链表逆置之后的元素。每个数据后一个空格。
样例输入
5
1 2 3 4 5
样例输出
L: 5 4 3 2 1
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 逆置单链表
*/
void rev_list(LinkNode *&L)
{
//请在下面编写代码
/******************Begin******************/
LinkNode *p, *q; // 尾插法
p = L->next;
L->next = NULL;
while(p!=NULL) {
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
/*******************End*******************/
}
//尾插法建立单链表
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //终端结点next域置为NULL
}
//初始化单链表
void InitList(LinkNode *&L)
{
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
}
//销毁单链表
void DestroyList(LinkNode *&L)
{
LinkNode *pre = L, *p = pre->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre); //此时p为NULL,pre指向尾结点,释放它
}
//输出单链表
void DispList(LinkNode *L)
{
LinkNode *p = L->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
第10关：移除链表元素
任务描述
本关任务：给你一个带附加头结点L的单链表和一个整数 val ，请你删除链表中所有值为 val 的结点。
例如，下图所示的单链表L，val=6，删除所有值为6的结点。
编程要求
根据提示，在右侧编辑器补充代码，完成函数void remove_elements(LinkNode *&L, ElemType val)，该函数功能为：删除L中所有值为val的结点。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入包括两行。
第一行有两个空格分隔的整数。第一个整数为单链表结点数量n，第二个数为需要删除的元素val。
第二行为空格隔开的n个整数。
输出格式
输出包括一行。为删除val后的单链表，每个数据后一个空格。
样例输入
7 6
1 2 6 3 4 5 6
样例输出
L->1 2 3 4 5
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 删除链表元素: 删除L中所有值为val的结点
*/
void remove_elements(LinkNode *&L, ElemType val)
{
//请在下面编写代码
/******************Begin******************/
LinkNode *cur = L, *prev=L, *p;
while(cur != NULL) { // 遍历链表
if(cur->data == val) {
p = cur->next; // 保存cur的下一个结点位置
if(L == cur) { // 判断cur是否是首结点
L = p;
}else{
prev->next = p; // 将cur上一节点和下一结点相连
}
free(cur); // 删除等于val的结点
cur = p;
}else if(cur->data != val){
prev = cur;
cur = prev->next; // 将cur上一结点和cur下一结点相连
}
}
/*******************End*******************/
}
//尾插法建立单链表
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //终端结点next域置为NULL
}
//初始化单链表
void InitList(LinkNode *&L)
{
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
}
//销毁单链表
void DestroyList(LinkNode *&L)
{
LinkNode *pre = L, *p = pre->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre); //此时p为NULL,pre指向尾结点,释放它
}
//输出单链表
void DispList(LinkNode *L)
{
if (L->next == NULL) {
printf("NULL\n");
return;
}
LinkNode *p = L->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
第11关：约瑟夫环
任务描述
本关任务：n个人围成一圈，按顺序从1到n进行编号，初始时从编号为1的人开始按1、2、3…顺序报数，报数到m（1≤m≤n）时该人退出到圈外，接着从出圈时的下一个位置开始从1开始重新进行报数，报数到m时的人再退出到圈外，以此类推。
请按退出顺序输出每个退出人的原编号。
编程要求
根据提示，在右侧编辑器补充代码，补充完成函数void Jesuphus(LinkNode *&L, int n, int m)，其中L为不带附加头结点的循环单链表的头指针，n为圈中人的个数，m为报数的值。
测试说明
平台会对你编写的代码进行测试：
输入格式
输入只有一行，为n和m。1≤n≤3000,1≤m≤n。
输出格式
输出包含一行，为退出到圈外的人的编号，编号之间以一个空格分隔。
样例输入1
10 3
样例输出1
3 6 9 2 7 1 8 5 10 4
样例输入2
7 4
样例输出1
4 1 6 5 7 3 2
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 约瑟夫环：L为不带附带头结点的循环单链表的头指针
*/
void Jesuphus(LinkNode *&L, int n, int m)
{
//请在下面编写代码
/******************Begin******************/
LinkNode *r, *p;
p = L;
while(p->next!=p){
for(int i=1; i<m; i++){
r = p;
p = p->next;
}
printf("%d ", p->data);
r->next = p->next;
p = p->next;
}
printf("%d", p->data);
/*******************End*******************/
}
//尾插法建立循环单链表
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->data = a[0];
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 1; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = L; //形成循环单链表
}
//输出循环单链表
void DispList(LinkNode *L)
{
LinkNode *p = L;
while (p->next != L)
{
printf("%d ", p->data);
p = p->next;
}
printf("%d\n", p->data); //打印最后一个结点的值
}
第12关：链表的中间结点
任务描述
本关任务：给定一个头结点为 L 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例一：
输入：1 2 3 4 5
输出：返回的结点值为 3 。
示例二：
输入：1 2 3 4 5 6
输出：返回的结点值为 4。
由于该链表有两个中间结点，值分别为 3 和 4，我们返回第二个结点 4。
编程要求
根据提示，在右侧编辑器补充代码，完成函数LinkNode* middleNode(LinkNode *L)，该函数的功能是返回链表的中间结点。其中L为不带附加头结点的单链表的头指针。
测试说明
平台会对你编写的代码进行测试：
测试输入：
1 2 3 4 5
预期输出：
3
测试输入：
1 2 3 4 5 6
预期输出：
4
提示：给定链表的结点数介于 1 和 100 之间。
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 返回链表的中间结点。L为不带附加头结点的单链表的头指针。
*/
LinkNode* middleNode(LinkNode *L)
{
//请在下面编写代码
/******************Begin******************/
if(L->next==NULL){
return L;
}
LinkNode *fast=L; // 走两步
LinkNode *slow=L; // 走一步
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
}
return slow;
/*******************End*******************/
}
//尾插法建立不带附加头结点的单链表
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->data = a[0];
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 1; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //单链表收尾
}
//输出单链表
void DispList(LinkNode *L)
{
LinkNode *p = L;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
第13关：回文链表
任务描述
本关任务：给你一个单链表的头结点 L ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例一：
输出：YES
示例二：
输出：NO
编程要求
根据提示，在右侧编辑器补充代码，完成函数bool isPalindrome(LinkNode *L)，该函数功能是判断链表是否为回文链表。如果是，返回 true ；否则，返回 false 。其中 L为不带附加头结点的单链表的头指针。
测试说明
平台会对你编写的代码进行测试：
测试输入：
1 2 2 1
预期输出：
YES
测试输入：
1 2
预期输出：
NO
提示：
链表中节点数目在范围[1,10^ 3 ] 内。
0 <= Node.val <= 9。
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 判断链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
* L为不带附加头结点的单链表的头指针。
*/
bool isPalindrome(LinkNode *L)
{
//请在下面编写代码
/******************Begin******************/
if (L == NULL || L->next == NULL) {
return true; // 空链表或只有一个节点的链表都是回文链表
}
// 使用快慢指针找到链表的中间节点
LinkNode *slow = L;
LinkNode *fast = L;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
// 反转链表的后半部分
LinkNode *prev = NULL;
LinkNode *curr = slow->next;
while (curr != NULL) {
LinkNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
// 比较前半部分和反转后的后半部分是否相等
LinkNode *p1 = L;
LinkNode *p2 = prev;
while (p1 != NULL && p2 != NULL) {
if (p1->data != p2->data) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
/*******************End*******************/
}
//尾插法建立不带附加头结点的单链表
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->data = a[0];
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 1; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //单链表收尾
}
//输出单链表
void DispList(LinkNode *L)
{
LinkNode *p = L;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
第14关：中位数
任务描述
本关任务：一个长度为L（L≥1）的升序序列S，处在第 ⌈L/2⌉个位置的数称为S的中位数。
例如：若序列S1=(11，13，15，17，19)，则S1的中位数是15。
两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。
现有两个等长的升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
编程要求
根据提示，在右侧编辑器补充代码，完成函数ElemType find_median(SqList *A, SqList *B)，该函数功能为求两个等长的有序顺序表的中位数并返回。
测试说明
平台会对你编写的代码进行测试：
测试输入：
5
11 13 15 17 19
2 4 6 8 20
预期输出：
11
开始你的任务吧，祝你成功！
完整代码
#include "sqlist.h"
/**
* 求两个等长的有序顺序表的中位数。
*/
ElemType find_median(SqList *A, SqList *B)
{
//请在下面编写代码
/******************Begin******************/
int i=0, j=0, k=0;
while(i<A->length && j<B->length){
k++;
if(A->data[i] < B->data[j]){
if(k==A->length)
return A->data[i];
i++;
}else{
if(k==B->length){
return B->data[j];
}
j++;
}
}
/*******************End*******************/
}
ElemType a[MaxSize];
ElemType b[MaxSize];
int main()
{
SqList *L1, *L2;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)scanf("%d", &a[i]);
for (int i = 0; i < n; i++)scanf("%d", &b[i]);
CreateList(L1, a, n);
CreateList(L2, b, n);
printf("L1,L2的中位数:%d\n", find_median(L1, L2));
return 0;
}
第15关：合并两个有序链表
任务描述
本关任务：将两个升序链表合并为一个新的 升序 链表。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
编程要求
根据提示，在右侧编辑器补充代码，完成函数void mergeTwoLists(LinkNode* &L, LinkNode* L1, LinkNode* L2)，该函数的功能是：合并两个有序链表。L1和L2为不带附加头结点的单链表的头指针。L为合并后的单链表的头指针。
测试说明
平台会对你编写的代码进行测试：
测试输入：
3 3
1 2 4
1 3 4
预期输出：
1 1 2 3 4 4
提示:
两个链表的节点数目范围是 [1, 1000]
L1 和 L2 均按 非递减顺序 排列。
开始你的任务吧，祝你成功！
完整代码
#include "linklist.h"
/**
* 合并两个有序链表。L1和L2为不带附加头结点的单链表的头指针。
* L为合并后的单链表的头指针。
*/
void mergeTwoLists(LinkNode* &L, LinkNode *L1, LinkNode* L2)
{
//请在下面编写代码
/******************Begin******************/
LinkNode *p1=L1,*p2=L2,*r,*s;
L=(LinkNode*)malloc(sizeof(LinkNode));
r=L;
while(p1!=NULL&&p2!=NULL)
{
if(p1->data<p2->data)
{
s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=p1->data;
r->next=s;
r=s;
p1=p1->next;
}
else
{
s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=p2->data;
r->next=s;
r=s;
p2=p2->next;
}
}
while(p1!=NULL)
{
s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=p1->data;
r->next=s;
r=s;
p1=p1->next;
}
while(p2!=NULL)
{
s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=p2->data;
r->next=s;
r=s;
p2=p2->next;
}
r->next=NULL;
L=L->next;
/*******************End*******************/
}
//尾插法建立不带附加头结点的单链表
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->data = a[0];
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 1; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //单链表收尾
}
//输出单链表
void DispList(LinkNode *L)
{
LinkNode *p = L;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
