【★★★★★ 第2章 线性表总结笔记 2022 9.12】

1.线性表的定义和基本操作

线性表：具有相同数据类型的n个数据元素的有限序列；
线性表的逻辑特性：除第一个元素外，每一个元素都有且仅有一个直接前驱，除最后一个元素外每个元素都有且仅有一个直接后继；
线性表的特点：

1. 表中元素个数有限
2. 表中元素具有逻辑上的顺序性，表中元素有先后次序
3. 表中元素都是数据元素，每个元素都是单个元素
4. 表中元素的数据类型相同，也就是说 占有相同大小的存储空间
   线性表为逻辑结构，表示元素之间一对一的相邻关系。
   顺序表和链表是指存储结构，两者是不同层面的概念；
   做题总结：

• 邻接表是存储结构
• 线性表要是相同类型 有限序列！

1.1 线性表的顺序表示

线性表的顺序存储称为顺序表； 顺序表用一组地址连续的存储单元依次存储线性表中的数据元素； 使得逻辑上相邻的元素在物理上也相邻；特点就是逻辑顺序与物理顺序相同；随机存取,O(1)的时间内找到指定元素

设第一个元素a0的存储位置为loc(a0) 每个元素占用k个存储单元，则任意个元素ai的内存地址为loc(ai)=loc(a0)+i*k

线性表的插入

#define ERROR 0
#define OK 1
int  Insert(SeqList *L,int i,int x){
  int j;
  if(i<-1||i>L->n-1)
  return ERROR;
  if(L->n==L->MaxSize)
  return ERROR;
  for(j=L->n-1;j>i;j--)
   L->data[j+1]=L->data[j];
   L->data[i+1]=x;
   L->n++;
   return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入的最好情况 在表尾不用移动元素，O(1)
最坏情况：表头 O(n)
平均情况：插入一个元素 需要移动 n-i-1个元素，在任意位置插入时相同的概率，即pi=1/(n+1); 平均次数为 求和：【1/(n+1) *（n-i-1）】=n/2

线性表的删除

int Delete(SeqList *L,int i){
   int j;
   if(i<0||i>L->n-1)
   return ERROR;
   if(!L->n)
   return ERROR;
   for(j=i+1;j<L->n;j++ )
   L->data[j-1]=L->data[j];
   L->n--;
   return OK;
}
1
2
3
4
5
6
7
8
9
10
11

删除最好情况：表尾 O(1)
最差情况：表头 o(n)
平均情况:（n-1）/2

线性表的查找

Status Find(SeqList L,int i,ElemType *x){
  if(i<0||i>L.n-1)
  return ERROR;
  *x=L.element[i];
  return OK;
}
1
2
3
4
5
6

查找的时间复杂度为O(n)
做题总结：