顺序表题目 - wolai 笔记
1、从顺序表从删除具有最小的元素(假设唯一)并由函数返回,空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出。
算法思想:搜索整个顺序表,查找最小元素并记住其位置,搜索结束后用最后一个元素填补空出的原最小元素的位置。
2、顺序表元素逆置,算法空间复杂度为O(1)
算法思想:扫描顺序表L的前半部分元素,对于元素L.data[i](0<= i < L.length/2),将其与后半部分的对应元素L.data[L.length- i - 1]进行交换。
3、对于长度为n的顺序表,删除线性表中所有值为x的数据元素
算法思想:k记录顺序表L中等于x的元素个数,边扫描L边统计k,并将不等于x的元素前移k个位置,最后修改L的长度。
4、从有序顺序表中删除其值在给定值st之间(要求s<t)的所有元素,
算法思想:因为是有序表,所以删除的元素时相连的。
5、从顺序表中删除其值在给定值st之间(包含st,要求s<t)的所有元素
算法思想:从前向后扫描顺序表L,用k记录下元素值在st元素的个数(初始k=0)。对于当前扫描的元素,若其值不在st之间,则前移k个位置;否则执行k++。由于每个不在st之间的元素仅移动一次,算法效率高。
6、从有序顺序表中删除所有其值重复的元素
算法思想:有序顺序表,值相同的元素一定在连续位置上,用类似插入排序的思想,初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同。若相同,则继续向后判断,若不同,则插入前面的非重复有序表的最后,直至判断到表尾为止。
7、将两个有序顺序表合并为一个新的有序顺序表
算法思想:首先,按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后,看那个表还有剩余,将剩下的部分加到新的顺序表后面。
8、已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3…am)和(b1,b2,…,bn)。将数组中两个顺序表的位置互换,即将(b1,b2,…,bn)放在(a1,a2,a3…am)前面
算法思想:先将数组A[m+n]中的全部元素(a1,a2,a3…am,b1,b2,…,bn)原地逆置,在对前n个元素和后m个元素分别使用逆置算法,从而实现顺序表位置的互换。
9、线性表元素递增有序且顺序存储,用最少时间在表中查找数值为x的元素,找到则与其后继元素位置互换;找不到,则插入顺序表使其递增
算法思想:顺序表递增,使用折半查找。

Comment
avatar
Dongnian
A salty fish swimming in the sea of deep learning!
Follow Me
Announcement
Welcome to My Personal Blog!
If Not, Please Visit Gitee Mirror.