结构体
#define MAXSIZE 50
typedef struct{
ElemType data[MAXSIZE];
int length;
} SqList;
动态分配结构体
#define InitSize 100
typedef struct{
ElemType *data; // 动态分配的数组的头指针
int MAXSIZE, length;// 表示最大容量和当前容量
} SeqList;
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
插入操作
判断插入位置的合法性判断数组存储空间后移空位length++
bool ListInsert(SqList &L, int i, ElemType e) {
if (i < 1 || i > L.length + 1)
return false;
if (L.length >= MAXSIZE)
return false;
for (int j = L.length; j >= i; j--)
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.length++;
return true;
}
删除操作
判断删除元素是否存在保存被删值前移元素L.length–
bool ListInsert(SqList &L, int i, ElemType &e) {
if (i < 1 || i > L.length)
return false;
e = L.data[i - 1];
for (int j = i; j < L.length; j++)
L.data[j - 1] = L.data[j];
L.length--;
return true;
}
按值查找/顺序查找
按值查找时间复杂度为O（n），按位查找时间复杂度为O（1）
int locateElem(SqList L) {
int i = 0;
while (L.data[i] == e && i < L.length)
i++;
return i + 1;// 女朋友说看着不顺眼，应该用逻辑序号表达
}
查找并返回最小值位置
int minValue(SqList L) {
if (L.length < 1)
return false;
int value = L.data[0];
int minP = 0;
for (int i = 1; i < L.length; i++)
if (L.data[i] < value) {
value = L.data[i];
minp = i;
}
return minP;
}
两部分位置互换
整体逆置 (AB)
-1 结果为B
-1 A
-1分别逆置(B
-1)
-1(A
-1)
-1得到BA
bool reverse(SqList &L, int left, int right) {
if (left >= right ||left < 1 || right > L.length)
return false;
int mid = (left + right) / 2;
for (int i =0; i < mid - left; i++) {
ElemType temp = L.data[left + i];
L.data[left + i] = L.data[right - i];
L.data[right - i] = temp;
}
}
void exchange(SqList &L, int m, int n) {
reverse(L, 0, m + n - 1);
reverse(L, 0, n - 1);
reverse(L, n, m + n - 1);
}
使有序表中值均不相同
遇见每一个不同的覆盖前边相同
bool DelSame(SepList &L) {
if (L.length < 1)
return false;
int i, j;
for (i = 0, j = 1;j < L.length; j++)
if (L.data[i] != L.data[j])
L.data[++i] = L.data[j];
L.length = i + 1;
return true;
}
折半查找（有序表）
ElemType BinarySearch(SqList L,ElemType key)//二分查找
{
int low = 0; //定义初始最小
int high = L.length-1; //定义初始最大
int mid; //定义中间位置
while(low <= high)
{
mid = (low + high) / 2;
if(key == L.data[mid])
return mid;
else if(key > arr[mid])
low=mid+1;
else
high=mid-1;
}
return -1; //查找失败
}
两个等长升序序列合并求中位数
算法思想:
设两个升序序列A和B的中位数，设为a和b，则
若a = b，则其就是所求的中位数，算法结束若a < b,则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半若a > b,则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半
重复该过程，序列中只含一个元素时，即为中位数。
统计次数
算法思想：
新建一个结构体，保存值及其出现次数遍历顺序表统计
typedef struct{
ElemType key;
int count = 0;//c++可以在结构体内赋初值
} number;
bool traversalStatistic(SeqList L) {
number n[100];
for(int i =0; i < L.length; i++) {
}
}
