【数据结构】夯实基础|线性表刷题01

• 作者：努力学习的大一在校计算机专业学生，热爱学习和创作。目前在学习和分享：算法、数据结构、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--3printf("\n\t 输入选择错误，请重新选择 0--3： ");elsebreak;}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--4printf("输入选择错误，请重新选择 0--5:");elsebreak;}return sn;
}/*TODO：添加城市信息功能：添加城市信息到链表中，城市信息分为城市名称和城市坐标城市名称对应结构体City_List 的name，坐标对应结构体City_List 的x，yprintf("请输入城市名\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： ");elsebreak;}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;} elseListA->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;} elseListB->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;
}

---

• Java岛冒险记【从小白到大佬之路】
  
• LeetCode每日一题–进击大厂
• 算法
• 数据结构|刷题专栏