线性表地址计算方法

顺序存储结构

loc(ai) = loc(a1) + (i-1)*c 所以存储时间性能为O(1),即称为随机存储结构 插入和删除的时间复杂度：最坏O(n),最好O(1),平均是O(n)

链式存储结构

• 通常把链表的第一个结点存储位置叫做头指针，最后一个结点指针域为NULL
• 有时，我们在单链表的第一个结点之前附设一个结点，称为头结点。 头结点的数据域不存储任何信息（也可以存储诸如线性表长度等类的附加信息），此时头指针指向头结点
• 头指针时必要的，头结点则不是必要的 插入和删除的时间复杂度：O(n)

对于插入或删除数据越频繁的操作，单链表的效率就越明显 比如： 我们从第i个位置开始连续插入10个元素

• 顺序表每一次都是O(n)
• 链式表第一次为O(n),其他9次为O(1)

静态链表

用数组进行描述的链表叫做静态链表 C语言描述

#define MAXSIZE 1000

typedef struct {
    ElemType  data ;
    int cur;
}component,SLinkList[MAXSIZE]; //component 代表这种结构体类型
//SLinkList[MAXSIZE] 代表这种结构体类型的数组

typedef 的功能，它用来建立新的数据类型名，例如， 声明：typedef int Length; 将 Length 定义为与 int 具有同等意义的名字。类型 Length 可用于类型声明、类型转换等，它和类型 int 完全相同，相当于GO 语言的别名