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

这篇具有很好参考价值的文章主要介绍了【数据结构】夯实基础|线性表刷题01。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】夯实基础|线性表刷题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--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;
}


【数据结构】夯实基础|线性表刷题01文章来源地址https://www.toymoban.com/news/detail-406960.html

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

到了这里,关于【数据结构】夯实基础|线性表刷题01的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:力扣刷题

      给你一个  升序排列  的数组  nums  ,请你  原地  删除重复出现的元素,使每个元素  只出现一次  ,返回删除后数组的新长度。元素的  相对顺序  应该保持  一致  。然后返回  nums  中唯一元素的个数。 考虑  nums  的唯一元素的数量为  k  ,你需要做以下事情确

    2024年02月13日
    浏览(43)
  • 数据结构刷题笔记

    通常从四个方面评价算法的质量: 可读性 、 正确性 、 健壮性 、 高效性 。 某算法时间复杂度为O(n*n),说明算法执行时间与n *n成正比,其中n是问题规模 逻辑结构主要从数据元素之间的 相邻关系 考虑。用B=(D,R)表示,其中B表示一种逻辑数据结构,D是数据元素的集合,R是所

    2024年01月25日
    浏览(40)
  • 【数据结构刷题】数组oj

    题目: https://leetcode.cn/problems/remove-element/ 写一段原地移除数组中所有的元素val,要求时间复杂度为O(N^2),空间复杂度为O(1)的代码实现: 思路:遇到这个val后面的元素往前面覆盖。 int main() { int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int val = 2; 写一段原地移

    2024年02月14日
    浏览(32)
  • 数据结构——线性数据结构(数组,链表,栈,队列)

    数组(Array) 是一种很常见的数据结构。它由相同类型的元素(element)组成,并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引(index)可以计算出该元素对应的存储地址。 数组的特点是: 提供随机访问 并且容量有限。 2.1. 链表简介 链表(LinkedList) 虽然是

    2024年02月11日
    浏览(44)
  • java数据结构刷题二期

    在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后的矩阵需要将原始矩阵

    2023年04月22日
    浏览(46)
  • 【数据结构刷题专题】—— 二叉树

    二叉树 二叉树刷题框架 二叉树的定义: 1 二叉树的遍历方式 【1】前序遍历 【2】后序遍历 【3】中序遍历 【4】层序遍历 2 二叉树的属性 【1】101. 对称二叉树 【2】104. 二叉树的最大深度 迭代法: 递归法: 【3】111.二叉树的最小深度 递归法: 迭代法: 【4】222. 完全二叉树的

    2024年04月10日
    浏览(42)
  • 【数据结构】线性结构 之 顺序表

    🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 顺序表概念及结构 静态代码实现: 动态代码实现: SeqList.h文件 SeqList.c文件 test.c文件 本章节博主将会带领大家了解数据结构的 线性结构的顺序表 。 提到线性

    2024年02月06日
    浏览(44)
  • 数据结构刷题训练:队列实现栈

    目录 前言 1. 题目:使用队列实现栈 2. 思路 3. 分析  3.1 创建栈 3.2入栈 3.3 出栈 3.4 栈顶数据 3.5 判空和 “ 栈 ” 的销毁  4. 题解 总结         我们已经学习了栈和队列,也都实现了它们各自的底层接口,那么接下我们就要开始栈和队列的专项刷题训练。 题目描述:  题

    2024年02月13日
    浏览(39)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(53)
  • 数据结构刷题训练——链表篇(二)

    目录 前言 1.题目一:链表分割 1.1 思路 1.2 分析  1.3 题解 2. 题目二:相交链表 2.1 思路 2.2 分析 2.3 题解 3. 题目三:环形链表 3.1 思路 3.2 分析 3.3 题解 总结         本期继续分享链表相关的OJ题目,在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步

    2024年02月14日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包