数据结构考试速刷#
整理知识点以及配套视频，以及LeetCode刷题。 复习重点
单元 1 绪论#
单元 2 线性表#
线性表的插入#
#include <stdio.h>
#define MAX 100
int main()
{
int a[MAX];
// b 存放待插入的数据、i存放插入的位置、n存放操作线性表的长度
int i, j, b, n;
scanf("%d%d%d", &b, &i, &n);
for (j = 1; j <= n; j++)
{
scanf("%d", &a[j]);
}
a[0] = n;
for (j = n; j >= i; j--)
{
a[j + 1] = a[j];
}
a[i] = b;
a[0] = n + 1;
for (j = 1; j <= a[0]; j++)
{
printf("%5d \n", a[j]);
}
return 0;
}
在上述代码中，我们从后往前移动数组中的元素，使得插入位置及其后面的所有元素都向后移动一位，然后在指定的位置插入新的元素。这个过程的时间复杂度为 O(n)，其中 n 是线性表的长度。因为在最坏的情况下，我们可能需要移动线性表中的所有元素（当插入的位置是1时）。
删除元素#
#include <stdio.h>
#define MAX 100
int main()
{
int a[MAX];
// i存放要删除的数据元素的下标，n存放待操作的线性表的长度
int i, j, n;
scanf("%d%d", &i, &n);
for (j = 1; j <= n; j++)
{
scanf("%d", &a[j]);
}
a[0] = n;
for (j = i+1; j <= n; j++)
{
a[j-1] = a[j];
}
a[0] = a[0]-1;
for (j = 1; j <= a[0]; j++)
{
printf("%5d\n", a[j]);
}
return 0;
}
插入、删除操作的时间复杂度分析#
假设线性表的长度为n，就插入而言，舍插入位置在第i个元素之前，i共有1～(n+1)种可能的情况，最好情况是i=n+1，移动元素次数为0，最坏情况是i=1，移动元素次数为n，一般来说，对于插入位置为i，则移动元素次数为n-1+i