- 作者：努力学习的大一在校计算机专业学生，热爱学习和创作。目前在学习和分享：算法、数据结构、Java等相关知识。
- 博主主页： @是瑶瑶子啦
- 所属专栏: 【数据结构|刷题专栏】：该专栏专注于数据结构知识，持续更新，每一篇内容优质，浅显易懂，不失深度！该专栏题目较为基础和经典，旨在帮助学习数据结构的同学更好地、熟练地掌握如何使用相应的数据结构进行相关操作和解题
- 近期目标：写好专栏的每一篇文章
前言
不要被代码长度劝退了！都是很简单的操作，目的在于熟练掌握和使用数据结构！下面是用C语言描述的数据结构。严格意义上来说数据结构是门单独的课，用什么语言描述不是很重要，主要是学习如何构造相应的数据结构并且实现其相应操作。
题目后面的⭐对应相应的难度（三个星其实也不是很难）
一、顺序表的合并（⭐）
【习题描述】
已知顺序表A中的元素按值递增存放，而顺序表B中的元素按值递减存放。试设计一个高效算法，将B中的所有元素插入到A中（假设A中的空间足够大），仍使A为递增顺序表。基本要求及提示
（1） 首先创建两个顺序表A,B。
（2） 设计一个符合上述要求的MergeSeqList(A, B)函数。
（3） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
#define _CRT_SECURE_NO_WARNINGS 1
//常用系统头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
//常用的宏定义符号常量
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
#define MAXSIZE 100
int resultArray[MAXSIZE];
typedef struct {
int data[MAXSIZE];
int length;
} Seqlist;
int menu_select() // 菜单驱动程序
{
int sn; // sn用于接收菜单选项
printf("\n按任意键进入主菜单！\n");
printf("\n *** 顺序表合并系统 ***\n"); // 显示菜单
printf("==============================\n");
printf(" 1、创建A顺序表\n");
printf(" 2、创建B顺序表\n");
printf(" 3、合并并输出该顺序表\n");
printf(" 0、退出\n");
printf("==============================\n");
printf(" 请选择0--3: ");
for (;;) // 菜单功能选择
{
scanf("%d", &sn);
getchar();
if (sn < 0 || sn > 3) // 判断菜单选项是否属于合理范围：0--3
printf("\n\t 输入选择错误，请重新选择 0--3： ");
else
break;
}
return sn;
}
void SetA(Seqlist* A) {
int a, i;
A->length = 0;
printf("请输入要创建的元素的个数:");
scanf("%d", &a);
for (i = 0; i < a; i++) {
printf("请输入第%d个元素", i + 1);
scanf("%d", &A->data[i]);
A->length++;
}
}
void SetB(Seqlist* B) {
int a, i;
B->length = 0;
printf("请输入要创建的元素的个数:");
scanf("%d", &a);
for (i = 0; i < a; i++) {
printf("请输入第%d个元素", i + 1);
scanf("%d", &B->data[i]);
B->length++;
}
}
void reverse(Seqlist* B) {
int left = 0, right = B->length - 1;
while (left < right) {
int t = B->data[right];
B->data[right] = B->data[left];
B->data[left] = t;
left++;
right--;
}
}
void merge(Seqlist* A, Seqlist* B) {
//先把B逆序
reverse(B);
int i = 0, j = 0, x = 0;;
while (i < A->length && j < B->length) {
if (A->data[i] < B->data[j]) {
resultArray[x++] = A->data[i++];
}
else {
resultArray[x++] = B->data[j++];
}
}
while (i < A->length) {
resultArray[x++] = A->data[i++];
}
while (j < B->length) {
resultArray[x++] = B->data[j++];
}
for (int m = 0; m < A->length + B->length; m++) {
A->data[m] = resultArray[m];
}
A->length = A->length + B->length;
}
void main() {
Seqlist A;
Seqlist B;
for (;;) // 菜单驱动程序：无限循环菜单功能选择与调用相应功能函数,直到选择0 退出
{
switch (menu_select()) // 调用菜单函数，按返回值选择功能函数
{
case 1:
printf(" 创建A表\n");
SetA(&A);
break;
case 2:
printf(" 创建B表\n");
SetB(&B);
break;
case 3:
printf(" 合并A、B表\n");
merge(&A, &B);
printf("合并后的A顺序表如下\n");
for (int i = 0; i < A.length; i++) {
printf("%d", A.data[i]);
printf("\n");
}
break;
case 0:
printf(" 再见！\n"); // 退出系统
return;
} // switch语句结束
} // for循环结束
} // main()函数结束
二、城市定位（⭐⭐⭐）
【习题描述】
将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。（1） 给定一个城市名，返回其位置坐标；
（2） 给定一个位置坐标P和一个距离D，返回所有与P的 距离小于等于D的城市。
（3） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
//常用的宏定义符号常量
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
//请在此填写数据类型说明
typedef struct City_List {
char name[10];
float x;
float y;
struct City_List* next;
} City_List, * Lhead;
int menu_select() //菜单驱动程序
{
int sn; //sn用于接收菜单选项
printf("城市管理系统\n"); //显示菜单
printf("==============================\n");
printf("1、创建城市链表\n");
printf("2、根据城市名查询城市\n");
printf("3、根据中心坐标距离查询城市\n");
printf("0、退出\n");
printf("==============================\n");
printf("请选择0--3:");
for (;;) //菜单功能选择
{
scanf("%d", &sn);
getchar();
if (sn < 0 || sn > 3) //判断菜单选项是否属于合理范围：0--4
printf("输入选择错误，请重新选择 0--5:");
else
break;
}
return sn;
}
/*
TODO：添加城市信息
功能：添加城市信息到链表中，城市信息分为城市名称和城市坐标
城市名称对应结构体City_List 的name，坐标对应结构体City_List 的x，y
printf("请输入城市名\n") 输入一个字符串，作为城市名;
printf("请输入城市坐标\n") 输入两个浮点型f数字，中间用一个字符隔开;
与Create_List函数联动之后的效果如下：
输入END推出，输入其余值继续
1
请输入城市名
LA
请输入城市坐标
1.00 2.00
输入END推出，输入其余值继续
1
请输入城市名
BA
请输入城市坐标
1.00 3.00
输入END推出，输入其余值继续
END
参数：City_List *Lhead 是需要操作的链表
返回值： 无
*/
void Insert(City_List* Lhead) {
//创造新节点
City_List* newNode = (City_List*)malloc(sizeof(City_List));
printf("请输入城市名\n");
scanf("%s", newNode->name);
printf("请输入城市坐标\n");
scanf("%f %f", &newNode->x, &newNode->y);
//使用头插法，把该新节点插入到链表中
newNode->next = Lhead->next;
Lhead->next = newNode;
}
/*
TODO：创建链表
功能：创建链表，添加元素时提示：printf("输入END推出，输入其余值继续\n");
如果录入END，停止添加；录入其他字符，则调用Insert方法，插入元素
参数：City_List *Lhead 是需要操作的链表
返回值： 无
*/
void Create_List(City_List* Lhead) {
while (1) {
printf("输入END推出，输入其余值继续\n");
char name[10];
const char* t = "END";
scanf("%s", name);
if (!strcmp(name, t)) {
break;
}
else {
Insert(Lhead);
}
}
}
/*
TODO：搜索城市信息
功能：通过城市姓名，搜索城市信息，提示：printf("请输入您要搜索的城市名\n");
如果如果找到对应的城市信息，则打印城市坐标printf("城市坐标为%.2f,%.2f\n")
未找到城市信息，提示printf("你要搜索的城市不存在\n");
比如：
请输入您要搜索的城市名
AA
城市坐标为1.00,2.00
请输入您要搜索的城市名
BA
你要搜索的城市不存在
参数：City_List *Lhead 是需要操作的链表
返回值： 无
*/
void Find_City(City_List* Lhead) {
printf("请输入您要搜索的城市名\n");
//临时存储用户输入的城市名
char name[10];
scanf("%s", name);
City_List* p = Lhead;//指针，负责遍历该单链表
int flag = 0;//标记变量
while ((p = p->next) != NULL) {
if (!strcmp(p->name, name)) {
flag = 1;
printf("城市坐标为%.2f,%.2f\n", p->x, p->y);
}
}
if (flag == 0) {
printf("你要搜索的城市不存在\n");
}
}
/*
TODO：查询距离范围内城市
功能：给定一个位置坐标P和一个距离D，返回所有与P的 距离小于等于D的城市。
printf("请输入中心坐标\n");
printf("请输入距离\n");
计算距离判断：((x-Lhead->x)*(x-Lhead->x)+(y-Lhead->y)*(y-Lhead->y)<=distance*distance)
如果找到符合要求的城市，打印出所有城市信息
printf("城市名为%s\n");
printf("城市坐标为%.2f,%.2f\n");
如已有三座城市：LA（1.00,2.00） BA（1.00,3.00） CA（10.00,83.00），市中心（10.00,8.00）
想查询距离市中心距离12以内的城市：
请输入中心坐标
10.00 8.00
请输入距离
12
城市名为LA
城市坐标为1.00,2.00
城市名为BA
城市坐标为1.00,3.00
参数：City_List *Lhead 是需要操作的链表
返回值： 无
*/
void Find_City_Distance(City_List* Lhead) {
//临时存储用户输入的中心坐标和距离
float x = 0, y = 0;
int d = 0;
printf("请输入中心坐标\n");
scanf("%f %f", &x, &y);
printf("请输入距离\n");
scanf("%d", &d);
City_List* p = Lhead;//指针，负责遍历该单链表
while ((p = p->next) != NULL) {
if ((x - p->x) * (x - p->x) + (y - p->y) * (y - p->y) <= d * d) {
printf("城市名为%s\n",p->name);
printf("城市坐标为%.2f,%.2f\n",p->x,p->y);
}
}
}
int main() {
//声明一个全局数据变量，并将其初始化
City_List* Lhead;
Lhead = (City_List*)malloc(sizeof(City_List));
Lhead->next = NULL;
for (;;) // 菜单驱动程序：无限循环菜单功能选择与调用相应功能函数,直到选择0 退出
{
switch (menu_select()) // 调用菜单函数，按返回值选择功能函数
{
case 1:
printf("创建城市链表\n");
//功能1的函数调用
Create_List(Lhead);
break;
case 2:
printf("根据城市名查询城市\n");
//功能2的函数调用
Find_City(Lhead);
break;
case 3:
printf("根据中心坐标距离查询城市\n");
//功能3的函数调用
Find_City_Distance(Lhead);
break;
case 0:
printf("再见!\n"); //退出系统
return 0;
} // switch语句结束
} // for循环结束
return 0;
} // main()函数结束
三、线性表的减法（⭐⭐⭐）
【习题描述】 问题描述：
利用线性表的基本操作，实现在线性表A中删除线性表B中出现的元素。
基本要求及提示：
（1） 首先创建两个线性表表。
（2） 依次检查线性表B中的每个元素看它是否在线性表A中，若在，则将其删除。
（3） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
难度：⭐⭐⭐
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define TURE 1
#define FAULE -1
#define Max_size 100
#define ElemType int
//结构体定义
typedef struct {
ElemType elem[Max_size];
ElemType last;
} Seqlist;
//函数声明
int menu_select();
int Add_A_List(Seqlist *);
int Del_A_List(Seqlist *);
int Add_B_List(Seqlist *);
int Del_B_List(Seqlist *);
int Auto_Del_List(Seqlist *, Seqlist *);
int printA(Seqlist *);
int printB(Seqlist);
// main()函数
int main() {
Seqlist ListA, ListB;
ListA.last = -1; //注意应提前赋值
ListB.last = -1;
for (;;) {
switch (menu_select()) {
case 1:
printf("增加线性表A中的元素\n");
Add_A_List(&ListA);
break;
case 2:
printf("删除线性表A中的元素\n");
Del_A_List(&ListA);
break;
case 3:
printf("增加线性表B中的元素\n");
Add_B_List(&ListB);
break;
case 4:
printf("删除线性表B中的元素\n");
Del_B_List(&ListB);
break;
case 5:
printf("计算机自动删除A中存在B中的元素\n");
Auto_Del_List(&ListA, &ListB);
break;
case 6:
printf("显示出A中的元素\n");
printA(&ListA);
break;
case 7:
printf("显示出B中的元素\n");
printB(ListB);
break;
case 0:
printf("欢迎下次使用\n");
return 0;
}
}
} // main()函数结束
//菜单驱动程序
int menu_select() {
int sn;
printf("===============================\n");
printf("1、增加线性表A中的元素\n");
printf("2、删除线性表A中的元素\n");
printf("3、增加线性表B中的元素\n");
printf("4、删除线性表B中的元素\n");
printf("5、计算机自动删除A中存在B中的元素\n");
printf("6、显示出A中的元素\n");
printf("7、显示出B中的元素\n");
printf("0、退出程序\n");
printf("=================================\n");
printf("输入0--7\n");
for (;;) {
scanf("%d", &sn);
getchar();
if (sn < 0 || sn > 7)
printf("\n 输入错误，重新选择 0--7S： ");
else
break;
}
return sn;
}
//增加线性表A中的元素
int Add_A_List(Seqlist *ListA) {
char flag = 'Y';
while (flag == 'y' || flag == 'Y') {
if (ListA->last >= Max_size - 1) {
printf("线性表A空间已满！\n\n");
return ERROR;
} else
ListA->last++;
printf("需要加入的数字为:\n");
scanf("%d", &ListA->elem[ListA->last]);
printf("\n");
printf("继续输入吗？(y/n)");
getchar();
scanf("%c", &flag);
printf("\n");
}
return OK;
}
//增加线性表B中的元素
int Add_B_List(Seqlist *ListB) {
char flag = 'Y';
while (flag == 'y' || flag == 'Y') {
if (ListB->last >= Max_size - 1) {
printf("线性表B空间已满！\n\n");
return ERROR;
} else
ListB->last++;
printf("需要加入的数字为:\n");
scanf("%d", &ListB->elem[ListB->last]);
printf("\n");
printf("继续输入吗？(y/n)");
getchar();
scanf("%c", &flag);
printf("\n");
}
return OK;
}
//删除线性表A中的元素
int Del_A_List(Seqlist *ListA) {
int i = 0, n;
char flag = 'Y';
if (ListA->last == -1) {
printf("线性表为空！\n\n");
return FAULE;
} else {
printf("请输入你要删除的元素\n");
scanf("%d", &n);
while (n != ListA->elem[i] && i <= ListA->last)
i++;
if (i <= ListA->last) {
printf("要删除的数字为%d\n", ListA->elem[i]);
printf("你确定要删除这个通讯者的信息吗？(y/n) ");
getchar();
scanf("%c", &flag);
if (flag == 'y' || flag == 'Y')
for (i = i + 1; i <= ListA->last; i++)
ListA->elem[i - 1] = ListA->elem[i];
ListA->last--;
return OK;
} else {
printf("元素不存在！\n\n");
return FAULE;
}
}
}
//删除线性表B中的元素
int Del_B_List(Seqlist *ListB) {
int i, n;
char flag;
if (ListB->last == -1) {
printf("线性表为空！\n\n");
return FAULE;
} else {
printf("请输入你要删除的元素\n");
scanf("%d", &n);
while (n != ListB->elem[i] && i <= ListB->last)
i++;
if (i <= ListB->last) {
printf("要删除的数字为%d\n", ListB->elem[i]);
printf("你确定要删除这个通讯者的信息吗？(y/n) ");
getchar();
scanf("%c", &flag);
if (flag == 'y' || flag == 'Y')
for (i = n + 1; i <= ListB->last; i++)
ListB->elem[i - 1] = ListB->elem[i];
ListB->last--;
return OK;
} else {
printf("元素不存在！\n\n");
return FAULE;
}
}
}
//计算机自动删除A中存在B中的元素
/*
TODO：性表B中的每个元素看它是否在线性表A中，若在，则将线性表A中的元素删除。
！注意：禁止在验证时使用输出函数显示
*/
int Auto_Del_List(Seqlist *ListA, Seqlist *ListB) {
//TODO：
for (int i = 0; i <= ListB->last; i++) {
for (int j = 0; j <= ListA->last; j++) {
if (ListA->elem[j] == ListB->elem[i]) {
for (int x = j; x <= ListA->last - 1; x++) {
ListA->elem[x] = ListA->elem[x + 1];
}
ListA->last--;
}
}
}
return 1;
}
//打印
int printA(Seqlist *ListA) {
int i;
if (ListA->last == -1) {
printf("线性表A为空\n");
return ERROR;
}
for (i = 0; i <= ListA->last; i++) {
printf("%4d", ListA->elem[i]);
}
printf("\n");
return OK;
}
//打印
int printB(Seqlist ListB) {
int j;
if (ListB.last == -1) {
printf("线性表B为空\n");
return ERROR;
}
for (j = 0; j <= ListB.last; j++) {
printf("%4d", ListB.elem[j]);
}
printf("\n");
return OK;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/142445.html
