第一节、线性表
-
线性表的特点
- 元素个数有限
- 元素具有逻辑上的顺序性
- 都是数据元素
- 数据类型相同
- 只讨论逻辑关系
可以使用的操作：求表长 Length（List）
第二节、顺序表
- 顺序表
- 顺序表的3特点
- 随机访问，
- 存储密度高
- 逻辑上相邻的元素物理上也相邻
- 2分配方式
- 静态分配，SqList
- 动态分配，SeqList
- 顺序表的3特点
- 顺序表算法题型
- 逆置
- 删除所有值为x的数据元素
- 有序表删除值重复的元素，当作直接插入排序，
- 合并两个有序顺序表
- AB = (BA)^
//设计一个高效算法， 将顺序表 L 的所有元素逆直，要求算法的空间复杂度为 0(1）。
//算法思想: 头对尾互换
bool reverse(SqList &seqList) {
if (seqList.length <=0) {
return false;
}
ElemType tmp;
for (int i = 0; i < (seqList.length/2); i++) {
tmp = seqList.data[i];
seqList.data[i] = seqList.data[seqList.length-1-i);
seqList.data[seqList.length-1-i] = tmp;
}
return true;
}
//从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同 。
// 算法思想：有序顺序表，从第二个元素开始与前面最后一个元素比较，若相同则删除
bool del(SqList &l) {
if (l.length == 0) {
return false;
}
int i=0；
int j=1;
for (; i < l.length; j++) {
if (l.data[i] != l.data[j]) {
l.data[++i] = l.data[j];
}
}
l.length = i + 1;
}
//对长度为 n 的顺序表 L，编写一个时间复杂度为 O(n）、空间复杂度为 0(1）的算法
//， 该算法删除线性表中所有值为 x 的数据元素。
// 算法思想：删除一个前移1位 删除2个前移2位，根据删除个数往前移动
bool delX(SqList &l) {
int i=0; //循环指针
int tmp=0; //删除的x的个数，前移位数
while (i < l.length) {
if (l.data[i] == x) {
tmp++;
} else {
l.data[i-tmp] = l.data[i];
}
}
l.length = l.length-tmp;
return true;
}
//将两个有序顺序表合并为一个新的有序顺序表，并由 函数返回结果顺序表。
// 两个指针
void merge(SqList &la, SqList &lb, SqList &lc) {
if (la.length + lb.length > lc.length) {
return false;
}
int i,j,k=0;
while (i < la.length && j < lb.length) {
if (la.data[i] < lb.data[j]) {
lc.data[k++] = la.data[i++];
} else {
lc.data[k++] = lb.data[j++];
}
}
while (i < la.length) {
lc.data[k] = la.data[i++];
}
while (j != lb.length) {
lc.data[k++] = la.data[j++];
}
lc.length = la.length + lb.length;
return true;
}
// 已知在一维数组 A[m + n］ 中依次存放两个线性表（a1-am）、（b1-bn）。 试编写一个函数，将数组中两个顺序表的位置互换，
// 算法思想：通过多次逆置实现
bool swapPostion(DataType A[], int m, int n, int arraySize) {
reverse(A, 0, m-1, arraySize);
reverse(A, m, m+n-1, arraySize);
reverse(A, 0, m+n-1, arraySize);
}
bool reverse(DataType A[], int left, int right, int arraySize) {
if (left >= right || right >= arraySize) {
return false;
}
int tmp;
int mid = (left + right) / 2;
for (int i = 0; i < mid -left; i++ ) {
tmp = A[right-i];
A[right-i] = A[left+i];
A[left+i] = tmp;
}
}
第三节、链表
-
单链表的特点
- 顺序存取
- 存储密度小，每个节点内还要存指向下个结点的指针
- 结点内存储单元连续
-
头结点的优点
- 结点操作方便，链表第一个位置和其他位置的操作一致
- 空表和非空表的处理得到了统一，无论链表是否为空，头指针都指向了头结点的非空指针
-
建立单链表的两种方式
- 头插法
- 尾插法：需要设置标为指针
-
双向链表
-
循环单链表
判空条件为 L->next == L
-
循环双链表
L->prior == L && L->next == L
-
静态链表
一块连续的存储空间
-
链表算法题型
- 逆置：头插法
- 求公共结点：求长度，长链表走长度之差，再共同走
- 删除所有值相同的结点
- 使一个链表元素顺序有序，直接插入排序
- 有序顺序输出链表元素，每次检索最小值或最大值
- 链表根据奇偶顺序分为两个链表，尾插法
- 递增有序顺序表，去重复元素，使表中不再有重复元素，直接插入排序
- 求交集 并集 差集
第四节、数组与矩阵
- 数组映射方法：按行优先 按列优先
- 矩阵的压缩存储
- 对称矩阵
- 三角矩阵
- 三对角矩阵
- 稀疏矩阵