1、顺序表:线性表的顺序存储,用一组地址连续的存储单元存储线性表中的数据元素。
1) 特点:随机访问,即通过首地址和元素序号可在时间O(1)内找到指定元素。
表中元素的逻辑顺序与其物理顺序相同,线性表中元素的位序是从1开始的。
2)存储位置的关系:假设线性表的每个元素占用l个存储单元
LOC(ai+1)=LOC(ai)+l、LOC(ai)=LOC(a1)+(i-1)*l,其中LOC(a1)为线性表的起始位置或基地址。
2、顺序表的空间分配方式:
1)静态分配:
#define MaxSize 50
typedef struct {
int data[MaxSize];
int length;
}Sqlist;
2)动态分配:
#define InitSize 100//表长度的初始定义
typedef struct {
int *data;//指示动态分配数组的指针
int maxsize, length;//数组的最大容量和当前个数
}SeqList;
3、插入操作:假设线性表中有n个元素,将元素e插入到顺序表L中第i个位置。
bool ListInsert(Sqlist &L, int i, int e)
if (iL.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;
最好情况:在表尾插入数据,元素后移语句将不执行,时间复杂度为O(1)。
最坏情况:在表头插入数据,元素后移语句将执行n次,时间复杂度为O(n)。
平均情况:元素平均移动次数为n/2,平均时间复杂度为O(n)。
4、删除操作:假设线性表中有n个元素,删除顺序表L中第i个位置的元素,并用e返回其值。
bool ListDelete(Sqlist &L, int i, int &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(1)。
最坏情况:删除表头数据,需移动除第一个元素外的所有元素,时间复杂度为O(n)。
平均情况:元素平均移动次数为(n-1)/2,平均时间复杂度为O(n)。
5、按值查找(顺序查找):假设线性表中有n个元素,在顺序表L中查找第一个元素值等于e的元素,并返回位序。
int LocateElem(Sqlist L, int e)
int i;
for (i = 0; i < L.length; i++)
if (L.data[i] == e)
return i + 1;
return 0;
最好情况:查找的元素在表头,仅比较一次,时间复杂度为O(1)。
最坏情况:查找的元素在表尾,需比较n次,时间复杂度为O(n)。
平均情况:元素平均移动次数为(n+1)/2,平均时间复杂度为O(n)。
6、逆置顺序表L
void Reverse(Sqlist &L)
int temp;
for (int i = 0; i < L.length / 2; i++)
temp = L.data[i];
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1] = temp;
7、将线性表(a1,a2,...,am,b1,b2,...,bn)换成(b1,b2,...,bn,a1,a2,...,am)
void reverse(int A[], int left, int right, int arraysize)
if (left >= right || right >= arraysize)
return;
int mid = (left + right) / 2;
for (int i = 0; i = t)
return false;
for (i = 0; i < L.length; i++)
if (L.data[i] >= s && L.data[i] = t || L.length == 0)
return false;
for (i = 0; i < L.length&&L.data[i] < s; i++);//值大于s的第一个元素
if (i >= L.length)
return false;
for (j = i; j < L.length&&L.data[j] MaxSize)
return false;
int i = 0, j = 0, k = 0;
while (i < A.length&&j < B.length)
if (A.data[i]
评论留言