线性表

线性表

线性表的概念

线性表是n个类型相同数据元素的有限序列，通常记作（a1, a2, a3,…, an）。

特点：

• 必存在一个唯一的“第一元素”
• 必存在一个唯一的“最后元素”
• 除最后一个元素外，均有唯一的后继
• 除第一个元素外，均有唯一的前驱

线性表的顺序表示和实现

typedef struct {
    ElementType *elem;  // 存储空间基地址
    int length; // 当前长度
    int listSize;   // 当前分配的存储容量
} SqList;   // 顺序表

• 线性表的销毁：每一个结点都释放掉，该链表完全不可以再次使用；
• 线性表的清空：除头结点外的所有结点释放掉，该链表还可以继续使用。

线性表的链式表示和实现

单链表

结构特点：单链表的逻辑次序和物理次序不一定相同
在链式存储结构中以第一个结点的存储地址作为线性表的基地址，通常称它为头指针。

优缺点

优点：插入和删除操作不需要移动数据了
缺点：指针占用了存储空间，增加了内存负担；另外只能顺序查找。

循环链表

单链表的最后一个结点的指针域（尾指针）指向了头指针，构成循环，称作循环链表。
为了方便地在循环链表中进行头插、尾插，设置一个指向表尾的尾指针。

双向链表

单链表的每一个结点再增设一个指针域，用于指向该结点的前驱，即每一个结点有一个数据域和俩指针域。

一元多项式的表示

用顺序表存储

可能造成大量空间浪费

用链式表存储

一般选用链式表存储，更加节省内存