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

曾经终败给现在 2023-09-25 18:04 24阅读 0赞

![在这里插入图片描述][b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]

>  *  **作者：努力学习的大一在校计算机专业学生，热爱学习和创作。目前在学习和分享：算法、数据结构、Java等相关知识。**
>  *  **博主主页： [@是瑶瑶子啦][Link 1]**
>  *  **所属专栏: [【数据结构|刷题专栏】][Link 2]：该专栏专注于数据结构知识，持续更新，每一篇内容优质，浅显易懂，不失深度！该专栏题目较为基础和经典，旨在帮助学习数据结构的同学更好地、熟练地掌握如何使用相应的数据结构进行相关操作和解题**
>  *  **近期目标：写好专栏的每一篇文章**

## 前言 ##

不要被代码长度劝退了！都是很简单的操作，目的在于熟练掌握和使用数据结构！下面是用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;
    }

--------------------

![在这里插入图片描述][dd52615e6d4d419bb71365add1e3c7ac.png_pic_center]

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

[b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]: https://img-blog.csdnimg.cn/b88c49c5b7e04dacaaed7cf2fc928687.gif#pic_center
[Link 1]: https://blog.csdn.net/Yaoyao2024?spm=1011.2559.3001.5343
[Link 2]: https://blog.csdn.net/yaoyao2024/category_12256535.html
[dd52615e6d4d419bb71365add1e3c7ac.png_pic_center]: https://img-blog.csdnimg.cn/dd52615e6d4d419bb71365add1e3c7ac.png#pic_center
[Java_]: https://blog.csdn.net/yaoyao2024/category_12168376.html
[LeetCode]: https://blog.csdn.net/yaoyao2024/category_12115665.html
[Link 3]: https://blog.csdn.net/yaoyao2024/category_12251293.html