在有序表中插入两个元素

题目描述

  思路：从题目可以想出这是要用到数据结构算法的线性表的插入，但是插入之前我们需要知道插入的位置，之后从该位置后的每一个数组单元进行后移一个位置，再把值插入即可。

知道思路之后开始做第一步：先创建一个类用来做线性表

class SeqList
{
	public:
		//无参构造函数
		SeqList()
		{
			length = 0;
			int data[100] = {0};
		} 
		//保存数据
		void SaveData(int n);
		//定位（按值大小进行查找）
		int Locate(int Data); 
		//插入
		void Insert(int location,int Data);
		//输出数据
		void Show();

	private:
		int data[100];
		int length;
		
};

主要算法   第一个 定位（Locate）类方法    代码如下：

int SeqList::Locate(int Data)
{
	int i;
	int k = 0;;
	int location = 0;

	for(i = 0; i < length; i++)
	{
		if(Data < data[i])
		{
			location = i+1;	
			return location;		
		}else
		{
			k++;
		}
	}
	if( k == length)
	{
		location = length+1;
	}
	return location;
}

这里我为啥会用到int型类方法的主要原因是我需要把该定位到的位置传到插入（Insert）类方法

这里的for循环是遍历数组的同时找到比某一个数组单元数值小的位置，然后直接return location，如找不到则k++（如果遍历整个数组找不到则表示找的那个数比所有数组里的数都要大，所以k++最后是整个数组的长度 所以这时候location返回的值是length+1），这样位置就找到了  这里所指的location是指它应该插入的位置（而不是下标）

第二个算法    插入（Insert）类方法    代码如下：

void SeqList::Insert(int location, int Data)
{
	int i; 
	if(location > length)
	{
		data[location-1]= Data;
	}
	else 
	{
		for( i =length; i>= location; i--)
		{
			data[i] = data[i-1];
		}
		data[location-1] = Data;
	}
	length++;
}

这一步比较简单   把从Locate返回的location 和 插入的数Data传进去

然后从该位置后的往后移出一个数组单位（移的时候千万要注意  从最后面依次往后移）再把值插入空出来的数组单元，然后长度+1。

整体代码如下:

#include <iostream>
using namespace std;
class SeqList
{
	public:
		//构造函数
		SeqList()
		{
			length = 0;
			int data[100] = {0};
		} 
		//存数据
		void SaveData(int n);
		//定位（按值查找）
		int Locate(int Data); 
		//插入
		void Insert(int location,int Data);
		//输出数据
		void Show();

	private:
		int data[100];
		int length;
		
};
void SeqList::SaveData(int n)
{
	int i;
	for(i = 0; i < n; i++)
	{
		cin >> data[i];
	}
	length = n;
}
void SeqList::Show()
{
	int i;
	for(i = 0; i < length; i++)
	{
		cout << data[i] << ' ';
	} 
}
int SeqList::Locate(int Data)
{
	int i;
	int k = 0;;
	int location = 0;

	for(i = 0; i < length; i++)
	{
		if(Data < data[i])
		{
			location = i+1;	
			return location;		
		}else
		{
			k++;
		}
	}
	if( k == length)
	{
		location = length+1;
	}
	return location;
}
void SeqList::Insert(int location, int Data)
{
	int i; 
	if(location > length)
	{
		data[location-1]= Data;
	}
	else 
	{
		for( i =length; i>= location; i--)
		{
			data[i] = data[i-1];
		}
		data[location-1] = Data;
	}
	length++;
}

int main(int argc, char** argv) {
	
	SeqList D;
	int n;
	int Data1;
	int Data2;
	int location;
	
	cin >> n; 
	
	D.SaveData(n); 
	
	cin >> Data1;
	cin >> Data2;
	
	location = D.Locate(Data1);
	D.Insert(location,Data1);
	
	location = D.Locate(Data2);
	D.Insert(location,Data2);
	
	D.Show(); 
	
	return 0;
}

如有错误 欢迎大家指出来   谢谢大家观看。