[数据结构与算法]数据结构编程题

数据结构编程题

2.2 线性表的顺序表示

注意线性表的顺序存储结构：

静态数组：

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList//静态分配数组顺序表的定义

动态数组：

#define MaxSize 50
typedef struct{
    ElemType *data;//数组的指针
    int MaxSize,length;
}SeqList;//动态分配数组顺序表的定义

1. 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

【注】有返回→bool

bool Del_Min(SqList &L, ElemType &value){
    //第一步必判空
    if(L.length==0){
        return false;
    }
    value=L.data[0];
    int pos=0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<value){
            value=L.data[i];
            pos=i;
		}
    }
    L.data[pos]=L.data[L.length-1];
    L.length--;//容易漏掉
    return true;
}

2. 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

【注】无返回→void

void Reverse(Sqlist &L){
    Elemtype temp;//逆置、交换这种最好借助辅助变量
    for(i=0;i<L.length;i++){
        temp=L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=temp;
	}
}

3. 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素

在这里插入代码片