数据结构——基础6

2022-09-07 23:09 作者:技术龙的传人 0人读过 | 我要投稿

线性表

基本操作——创建、判空、增删改查、求表长、输出

顺序表

线性表的顺序存储又称为顺序表，逻辑顺序与物理顺序相同

静态分配空间

动态分配空间

注意：动态分配不是链式存储，同样属于顺序存储，只是分配的空间大小可以在运行时动态决定。

插入

删除

查找

例题1：给定一个含n（ n>=1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5， 3， 2， 3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4.要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

答：1）n=4时，最小正整数有哪些可能？1、2、3、4

n=6时，最小正整数有哪些可能？1、2、3、4、5、6

算法思想：先遍历数组a，找出1~n范围内的数字，将b数组对应下标位标记，遍历b数组，找到第一个未标记位返回，此位就是未出现的最小值。

2）//查找a数组长度为n

int find(int a[], int n){

int i,*b;//动态分配

b = (int *)malloc(sizeof(int));//为标记数组申请空间

memset(b,0,sizeof(int)*n);//赋初值为0

for(i = 0; i < n; i++){//找出a数组中值介于1~n之间的元素，将标记数组b置1

if(a[i] >= 1 && a[i] <= n) b[a[i] - 1] = 1;

}

for(i = 0; i < n; i++){//遍历b数组，找出第一个0，即为最小未出现值

if(b[i] == 0) break;

}

free(b);

return i+1;

}

3）时间复杂度O(n),空间复杂度O(n)

例题2：定义三元组（ a， b， c）（ a、 b、 c均为正数）的距离D=|a-b| + |b-c| + |c-a|。给定3个非空整数集合S1、 S2、 S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组（ a， b， c）（ ܽ ∈ ܵ1, ܾ ∈ ܵ2, ܿ ∈ ܵ3）中的最小距离。例如S1={-1， 0， 9}， S2={-25,-10,10,11}, S3={2,9,17,30,41}，则最小距离为2，相应的三元组为（ 9,10,9）。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

答：1）算法思想：将集合分别放入a、b、c当中，对应下标i=j=k=0，三个数组均未遍历完成时进入循环，计算ijk下标值的距离，与最小距离判断并进行更新；在a、b、c数组中找出最小值将其下标加1，继续循环遍历直到有一个数组遍历完成时退出循环。

2）

//求绝对值

int abs_(int a){

if(a>0) return -a;

return a;

}

//判断a是否是三元素中的最小值

bool min_(int a, int b, int c){

if(a <= b && a<= c) return true;

return false;

}