Question

设计一个算法,将X插入到一个有序(从小到的排序)的线性表(顺序存储结果)的适当位置上,以保持线性表的有序性

设计一个算法,将X插入到一个有序(从小到的排序)的线性表(顺序存储结果)的适当位置上,以保持线性表的有序性
数据结构的题目，初学不懂
最好是帮写出程序来

Answer 1

将X在有序表二分查找，找到X要在有序表里要插入的位置，进行移位操作即可。
// 将一个数X插入一个依次递增的有序表里，并返回新生成的数组
public static int[] Insert(int x, int[] a) {
int[] temp = new int[a.length + 1];
for (int i = 0; i < a.length; i++) {
temp[i] = a[i];
}

int low, high, mid;
low = 0;
high = a.length - 1;

while (high - low > 1) {
mid = (low + high) / 2;
if (x == a[mid])
break;
else if (x < a[mid]) {
high = mid;
} else if (x > a[mid]) {
low = mid;
}
}
int j;
for (j = temp.length - 1; j > low; j--) {
temp[j] = temp[j - 1];
}
temp[j + 1] = x;
return temp;

}

Answer 2

既然要保持它的有序性，那你必须得前后大小保持了。
那你就用你要插入的数据和前后的数据进行比较！
..
找到了合适的位置，就插入就行了。

Answer 3

void ListInsert(LinkList *&L,ElemType x)
{
LinkList *P=L->next, *s, *q;
while(p!=NULL&&p->data<x)
{
q=p;
p=p->next;
}
if(p->data==x)
return 0 ;
s=(LinkList *)malloc(sizeof(LinkList));
s->data=x;
s->next=q->next;
q->next=s->next;
return 1;
}