顺序表练习题

​1. 设顺序表中的元素递增有序，编写一个算法，将元素x插入顺序表L中的适当位置，以保持该顺序表的有序性。

void sortInsert(List *l,int x){
	//假设表是有序的
	if(l->length==MAXSIZE)
		exit(1);//表已满，无法插入
	
	for(int i=0;i<l->length;i++){
		if(l->data[i]>=x){ //合适的位置
			//执行后移操作
			for(int j=l->length-1; j>i;j--){
				l->data[j+1]=l->data[j];
			}
			//插入
			l->data[i]=x;
			l->length++;
			return; //跳出
		}
	}
	//如果循环结束了都还没有插入，则代表它比所有元素都要大，位置放在最后一个
	l->data[l->length++]=x;
}

​ 优化版：

void sortInsert(List *l, int x) {
    if (l->length == MAXSIZE) {
        fprintf(stderr, "错误：表已满，无法插入！\n");
        exit(EXIT_FAILURE);
    }

    int i;
    // 找插入位置（从后往前找更高效）
    for (i = l->length - 1; i >= 0 && l->data[i] > x; i--) {
        l->data[i + 1] = l->data[i];
    }

    // 插入到合适位置
    l->data[i + 1] = x;
    l->length++;
}

2. 编写算法实现顺序表的的就地逆置。

void ReverseList(List *l){
	if(l->length==0)
		return;
	
	for(int i=0,j=l->length-1; i<j;i++,j--){
		int temp = l->data[i];
		l->data[i]=l->data[j];
		l->data[j]=temp;
	}
}