Question

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

Answer 1

if(array[i]<=x&&array[i+1]>=x) {k[j++]=array[i];k[j++]=x;}

• 定义一个指向L头结点的指针，然后挨个的比较，如果这个插入的元素大于第i个且小于第i+1个，则分配一个新空间，使第i+1个元素到末尾都一次向后平移一个单位，然后把插入的元素赋值给第i+1个元素。

• 原来第9个位置的元素后移到了第10个位置上，第8个位置的元素后移到了第9个位置上，这样第8个位置就空了出来，从而可以在这个位置上插入新元素。
  

• 由于是递增的单链表：0->0->0->0 这种结构不能逆向反问；所以直接做操作是很不好实现的； 所以我第一步是将两链表的指针反转，这样就使原来两链表由递增序列变成了递减序列；第二步在根据 合并排序的思想，将两个链合并。
  

Answer 2

定义一个指向L头结点的指针，然后挨个的比较，如果这个插入的元素大于第i个且小于第i+1个，则分配一个新空间，使第i+1个元素到末尾都一次向后平移一个单位，然后把插入的元素赋值给第i+1个元素；

Answer 3

struct list *p, *q, *s, *head;
p = head;
while(p != NULL)
{
if(x > p->data)
{
q = p;
p = p->next;
}
else
{
s = (struct list*)malloc(sizeof(struct list));
s->data = x;
q->next = s;
s->next = p;
}
}

Answer 4

if(array[i]<=x&&array[i+1]>=x) {k[j++]=array[i];k[j++]=x;}
else k[j++]=array[i];