顺序表中插入元素

前言

用于个人学习过程记录

题目

设顺序表中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

输入格式: 首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据先在第一行输入数据个数n（n≤15）及n个递增有序的整数； 然后在第二行输入一个整数x。

输出格式: 对于每组测试，将插入x后保持该顺序表递增有序的顺序表中的整数输出，每两个整数间留一个空格。

输入样例:

2
5 1 2 4 5 6
3
5 1 2 3 4 5
6

输出样例:

1 2 3 4 5 6
1 2 3 4 5 6

代码

#include<iostream>
using namespace std;

struct LinkList{
	int *elem;
	int length;
	void Init(int n);
	void create(int n);
	void travarse();
};
void LinkList::Init(int n)      //定义一个动态的数组 
{
	elem =new int[n];
	length=0;
}
void LinkList::create(int n){   //创建动态数组 
	Init(n);
	for(int *i=elem;i<elem+n;i++){
		cin>>*i;
		length++;
	}
}
void LinkList::travarse(){		//遍历 
	for(int *i=elem;i<elem+length;i++){
		if(i!=elem) cout<<" ";
		cout<<*i;
	}
	cout<<endl;
}
void Addlist(LinkList &a,int x){//添加元素 
	int i;
	for(i=0;i<a.length;i++){	//从第一位开始，如果数组中某个元素比添加的元素大，则记录这个位置i，从这个位置添加 
		if(a.elem[i]>=x) break;
	}
	for(int j=a.length-1;j>=i;j--){//从末尾开始，到刚刚查询到的i，将这些元素全部往后移动一个元素 
		a.elem[j+1]=a.elem[j];
	}
	a.elem[i]=x;
	a.length++;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,x;
		LinkList a;
		cin>>n;
		a.create(n);
		cin>>x;
		Addlist(a,x);
		a.travarse();
	}
}