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

Question

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

Answer 1

#include <stdio.h>

// a 顺序表  x 将要插入值  len 顺序表长度

// 返回值为表a的新长度

int insert(int x, int * a, int len)

{

printf("%3d ins ", x); // 这句为了演示用,显示插入的数值

int l, r, m;

// 查找插入位置

l = -1;

r = len;

m = (l + r) / 2;

while(r - l > 1)

{

if(a[m] < x) l = m;

else r = m;

m = l + (r - l) / 2;

}

if(r == len) a[r] = x;

else

{

for(l = len; l > r; l--) a[l] = a[l-1];

a[l] = x;

}

return ++len;

}

void print(int *a, int l)

{

int i;

for(i=0; i<l; i++) printf("%4d", a[i]);

printf("\n");

}

void main()

{

int a[20] = {1,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,0,0};

int len = 10;

print(a, len);

len = insert(20, a, len);

print(a, len);

len = insert(11, a, len);

print(a, len);

len = insert(10, a, len);

print(a, len);

len = insert(-1, a, len);

print(a, len);

len = insert(0, a, len);

print(a, len);

len = insert(1, a, len);

print(a, len);

len = insert(2, a, len);

print(a, len);

len = insert(55, a, len);

print(a, len);

}

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。

采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存储单元的长度。

顺序表的结构定义：

#define maxlen 50 //定义顺序表中元素个数最多有几个

typedef struct

{

elementtype data[maxlen]; //elementtype是元素的类型 依具体情况而定

int listlen; //便于时刻了解顺序表里元素的个数

}seqlist; //顺序表的名称 不妨为seqlist

声明顺序表类型变量：

seqlist L,L1;

如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +len

location (ki) = location(k1) + (i-1)len

存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

Answer 2

设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
void inList(SqlList L,int x){
if(L.length>=L.listsize)

newbase=(ElemType *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=LISTINCREMENT;

for(i=1;i<=L.length;i++){

if(x<=L.elem[i]){
for(q=L.length;q>=i;q++)L.elem[q+1]=L.elem[q];
L.elem[i]=x;
break;
}
else {L.elem[L.length+1]=x;break;}
}
L.length++;
}本回答被提问者采纳