王道数据结构线性表的顺序表示(课后算法题)

线性表

字数统计: 1.6k阅读时长: 7 min

 2020/05/03   Share

从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

代码如下：

#include <iostream>
#include <vector>
using namespace std;

bool EraseMindata(int& value, vector<int> &data) {

    if (data.size() == 0)
        return false;

    value = data[0];
    int pos = 0;

    for (int i = 1; i < data.size(); i++) {

        if (data[i] < value) {

            value = data[i];
            pos = i;
        }
    }

    data[pos] = data[data.size() - 1];
    return true;
}

int main()
{
    vector<int>data = { 1,2,3,4,5 };
    int value;

    EraseMindata(value, data);

    for (int i = 0; i < data.size(); i++) {

        cout << data[i] << " ";
    }

    cout << endl << value;
}

设计一个高效算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1)。

思路：将数组一分为二，互相交换即可。

代码如下：

#include <iostream>
using namespace std;

void Reverse(int*& data, int size) {

	int temp;

	for (int i = 0; i < size / 2; i++) {

		temp = data[i];
		data[i] = data[size - i - 1];
		data[size - i - 1] = temp;
	}
}

int main()
{
	int* data = new int[5];

	for (int i = 0; i < 5; i++) {
		data[i] = i + 1;
	}

	Reverse(data, 5);

	for (int i = 0; i < 5; i++) {

		cout << data[i] << " ";
	}
	cout << endl;
}

对长度为n的顺序表，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

思路：定义一个num，表示不是x的值的数量。每次将不为x的值赋给data[num]，即删除了值为x的数据。

代码如下：

#include <iostream>
using namespace std;

void DeleteX(int x, int*& data, int &size) {

	int num = 0;
	for (int i = 0; i < size; i++) {

		if (data[i] != x) {

			data[num] = data[i];
			num++;
		}
	}

	size = num;
}

int main()
{
	int size = 5;
	int* data = new int[size];

	for (int i = 0; i < 4; i++) {
		data[i] = 6;
	}
	data[4] = 5;

	DeleteX(6, data, size);

	for (int i = 0; i < size; i++) {

		cout << data[i] << " ";
	}

	cout << endl;

}

从有序顺序表中删除其值在给定值s和t之间（要求s < t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行。

思路：先找出需要删除的区间，再将 > t 的值赋值给data[i]（s <= data[i] <= t），即实现前移填补。

代码如下：

#include <iostream>
using namespace std;

bool Delete_s_t(int s, int t, int*& data, int& size) {

	//以升序顺序表为例

	if (s >= t || size <= 0)
		return false;


	int i, j;
	for (i = 0; i < size && data[i] < s; i++) {

	}

	if (i >= size)
		return false;	//所有值均小于s

	for (j = i; j < size && data[j] <= t; j++) {

	}

	if (j == i)
		return false;	//所有值均大于t

	for (; j < size; j++, i++) {

		data[i] = data[j];	//前移，填补被删数据
	}

	size = i;
	return true;
}

int main()
{
	int size = 5;
	int* data = new int[size];

	for (int i = 0; i < 4; i++) {
		data[i] = 5;
	}
	data[4] = 6;

	Delete_s_t(1, 5, data, size);

	for (int i = 0; i < size; i++) {

		cout << data[i] << " ";
	}

	cout << endl;

}

从顺序表中删除其值在给定值s与t之间（包含s和t，要求 s < t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行。

思路：用num来表示在s和t之间的值的个数，遇到不符合要求的元素，将其往前移动num值，即填补删除的元素，遇到符合的元素，即num++。

代码如下：

#include <iostream>
using namespace std;

bool Delete_s_t(int s, int t, int*& data, int& size) {

	//非顺序表
	if (s >= t || size <= 0)
		return false;

	int num = 0;	//表示在s和t之间的值的个数
	for (int i = 0; i < size; i++) {

		if (data[i] >= s && data[i] <= t)
			num++;
		else
			data[i - num] = data[i];	//将当前元素往前移动num值，即填补删除的元素
	}

	size = size - num;
	return true;
}

int main()
{
	int size = 5;
	int* data = new int[size];

	for (int i = 0; i < 4; i++) {
		data[i] = i + 1;
	}
	data[4] = 0;

	Delete_s_t(0, 2, data, size);

	for (int i = 0; i < size; i++) {

		cout << data[i] << " ";
	}

	cout << endl;
}

从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不同。

思路：与前一题差不多，遇到重复数据，num++，不同数据时，前移填补。

代码如下：

#include <iostream>
using namespace std;

void DeleteSame(int*& data, int& size) {

	int same_num = 0;
	for (int i = 1; i < size; i++) {

		if (data[i] == data[i - 1])
			same_num++;
		else
			data[i - same_num] = data[i];	//前移删除相同的数据
	}

	size = size - same_num;
}

int main()
{
	int size = 10;
	int* data = new int[size];

	for (int i = 0; i < 4; i++) {
		data[i] = 3;
	}
	for (int i = 4; i < size - 1; i++) {

		data[i] = i + 1;
	}

	data[size - 1] = 9;

	cout << "删除前：";
	for (int i = 0; i < size; i++) {

		cout << data[i] << " ";
	}

	cout << endl;

	DeleteSame(data, size);

	cout << "删除后：";
	for (int i = 0; i < size; i++) {

		cout << data[i] << " ";
	}

	cout << endl;
}

将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

思路：每次赋两者小的值，小的表向后移动一位，大的不动，再将有剩余的表赋值即可。

代码如下：

#include <iostream>
using namespace std;

void Merge(int*& data1, int& size1, int*& data2, int& size2, int*& res, int& size3) {

	//合并两个升序顺序表
	int i = 0;
	int j = 0;
	size3 = 0;

	while (i < size1 && j < size2) {

		if (data1[i] < data2[j]) {
			res[size3] = data1[i];
			i++;
		}

		else {
			res[size3] = data2[j];
			j++;
		}
		size3++;
	}

	//将剩余的赋值
	if (i < size1) {

		for (int k = size3; i < size1; k++, i++) {

			res[k] = data1[i];
		}
	}
	else if(j < size2) {
		for (int k = size3; j < size2; k++, j++) {

			res[k] = data1[j];
		}
	}

	size3 = size1 + size2;
}

int main()
{
	int size = 5;
	int size2 = size * 2;
	int* data1 = new int[size];
	int* data2 = new int[size]; 
	int* res = new int[size2];

	for (int i = 0; i < size; i++) {
		data1[i] = i + 1;
	}
	for (int i = 0; i < size; i++) {

		data2[i] = i - 1;
	}

	cout << endl;

	Merge(data1, size, data2, size, res, size2);

	for (int i = 0; i < size2; i++) {

		cout << res[i] << " ";
	}

	cout << endl;
}

Next Post

Leetcode 45. 跳跃游戏 II
Previous Post

Leetcode 53. 最大子序和

CATALOG



Total : 424

2023

2022

2021

2020

2019

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true

王道数据结构 线性表的顺序表示(课后算法题)

王道数据结构线性表的顺序表示(课后算法题)