博客

题目：实现顺序表各种基本运算的算法

要求：

1、建立一个顺序表，输入n个元素并输出；

2、查找线性表中的最大元素并输出；

3、在线性表的第i个元素前插入一个正整数x；

4、删除线性表中的第j个元素；

5、将线性表中的元素按升序排列；

6、将线性表中的元素就地逆序（只允许用一个暂存单元）；

#include<iostream>
#define SIZE 1000
using namespace std;

typedef struct
{
	int *a; // 该线性表存储整型数据  a为存储空间的基地址
	int length;  // 线性表的长度
}Sqlist;

void InitList(Sqlist &L) // 初始化 构造一个空的顺序表
{
	L.a = new int[SIZE]; // 为空顺序表分配一个大小为SIZE的连续空间
	if (!L.a) // 存储分配是否成功
		exit(0);
	L.length = 0; // 初始长度为0
}

bool ListInsert(Sqlist& L, int i, int x) // 在线性表 L 中的第 i 个位置插入数据 x
{
	if (i < 0 || i > L.length + 1 ) // 判断i是否符合条件
	{
		cout << " i 值不符合题意" << endl;
		return false; // 若不符合条件 则退出程序并返回false
	}
	if (L.length == SIZE) // 判断线性表是否已满
	{
		cout << "该线性表已满！" << endl;
		return false;
	}
	for (int j = L.length ; j > i-1 ;j--) // 将插入位置及其后的内容 向后移动一个单元
		L.a[j + 1] = L.a[j];
	L.a[i] = x; // 将元素插入相应位置
	L.length++; // 线性表的长度增加1
	return true;
}

void LocateMAX(Sqlist L) // 查找最大元素并输出
{
	int temp = L.a[0]; // 定义一个临时存储最大元素的单元 并将其初始化
	for (int i = 1; i < L.length ;i++) // 遍历线性表 找到最大元素
	{
		if (temp < L.a[i])
		{
			temp = L.a[i];
		}
	}
	cout << "最大元素为：" << temp << endl; // 输出最大元素
}

void DeleteList(Sqlist& L, int j) // 在线性表L中 删除第j个元素
{
	if (j < 0 || j > L.length + 1) // 判断j是否符合条件
	{
		cout << " j 值不符合题意" << endl;
		return ;
	}
	for (int i = j-1; i < L.length; i++) // 将删除位置后的所有元素全部向前移动一个单位
		L.a[i] = L.a[i+1];
	L.length--; // 线性表长度减1
	return ;
}

void SortList(Sqlist& L) // 将线性表中的元素按升序排列
{
	// 通过冒泡排序 将线性表的元素按照升序排列
	for (int i = 1 ; i <= L.length - 1 ;i++)
	{
		for (int j = 0 ; j <= L.length - i - 1 ; j++)
		{
			if (L.a[j] > L.a[j + 1])
			{
				int temp = L.a[j];
				L.a[j] = L.a[j + 1];
				L.a[j + 1] = temp;
			}
		}
	}
}

void unSortList(Sqlist &L) // 将线性表中的元素就地逆序
{
	int temp; // 定义一个暂存单元
	for (int i = 0 ; i < L.length/2;i++) // 将线性表中的元素就地逆序
	{
		temp = L.a[i];
		L.a[i] = L.a[L.length - i-1];
		L.a[L.length - i-1] = temp;
	}
}

void input(Sqlist &L) // 输入线性表的n个元素
{
	int n;
	cout << "请输入线性表长度：";
	cin >> n;
	for (int i = 0; i < n; i++) // 在for循环中输入每个元素
	{
		int x;
		cout << "第" << i + 1 << "个数: ";
		cin >> x;
		// 调用ListInsert()函数输入
		if (!ListInsert(L, i, x)) // 若输入失败 跳出循环
			break;
	}
}

void output(Sqlist L) // 遍历输出线性表中的元素
{
	cout << "线性表中的元素如下：" << endl;
	for (int i = 0; i < L.length; i++)
	{
		cout << "第" << i + 1 << "个元素为: " << L.a[i] << endl;
	}
}

void achieve()
{
	Sqlist L; // 定义一个线性表
	InitList(L); // 初始化线性表
	while (1)
	{
		int select; 
		cout << "-------------------------------------" << endl;
		cout << "  1.输入n个元素并输出  " << endl;
		cout << "  2.查找线性表中最大元素" << endl;
		cout << "  3.在线性表的某元素前插入一个正整数" << endl;
		cout << "  4.删除线性表中的某个元素" << endl;
		cout << "  5.将线性表中的元素按升序排列" << endl;
		cout << "  6.将线性表中的元素就地逆序" << endl;
		cout << "-------------------------------------" << endl;
		cout << "请输入您的选择：";
		cin >> select;
		switch (select)
		{
			case 1:
				input(L); // 输入n个元素
				output(L); // 输出线性表中的元素
				break;
			case 2:
				LocateMAX(L); // 查找最大元素并输出
				break;
			case 3:
				int i, x;
				cout << "请输入在第几个位置插入：";
				cin >> i;
				cout << "请输入要插入的元素：";
				cin >> x;
				ListInsert(L, i-1, x); // 在线性表的某元素前插入一个正整数
				output(L); // 输出变化后的线性表
				break;
			case 4:
				int j;
				cout << "请输入要删除元素的位置:";
				cin >> j;
				DeleteList(L, j); // 删除线性表中的某个元素
				output(L); // 输出变化后的线性表
				break;
			case 5:	
				SortList(L); // 将线性表中的元素按升序排列
				output(L); // 输出变化后的线性表
				break;
			case 6:
				unSortList(L); // 将线性表中的元素就地逆序
				output(L); // 输出变化后的线性表
				break;
			default:
				cout <<"请输入正确的选项："<< endl; 
		}
		cout << "是否继续操作 ? " << endl;
		cout << "1.是" << endl << "2.否" << endl;
		cin >> select;
		if(select == 2)
			break;
		system("cls"); // 清屏操作
	}	
}

int main()
{
	achieve();
	return 0;
}