【数据结构】第二章 线性表

§2.1线性表的定义

§2.2线性表的顺序表示和实现

优点：随机存储

§2.3线性表的链式表示和实现

?链式表示优点：灵活 ? ? 缺点：不随机存储

?2.3.1线性链表：储存单元可以是连续的 也可以是不连续的。

?对于数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后续的信息 ?(即直接后继的储存位置)每个结点包括数据域和指针域，线性链表每个结点只包含一个指 ?针域。

?头指针指向第一个结点 最后一个结点指向空指针(NULL)

?用结构体数组描述的链表为静态链表，用游标代替指针指示结点在数组中的相对位置。 ?(?i = S[i].cur 即为指针后移)

?2.3.2 循环链表：表中最后一个结点的指针指向头结点，整个链表形成一个环。从表中 ?任意一个结点出发均可以找到表中其他结点。

?2.3.3 双向链表：在双向链表的结点中有两个指针域，一指向后继，一指向前赴。

§2.4 一元多项式的表示与相加

①顺序储存结构(数组)实现

? ? ? ?第一种表示方式：a[i] = A ?表示 Ax^i ? ? ? (缺点：如果系数为0的项比较多，这样表示比较浪费空间)

? ? ? ?第二种表示方式：用每个元素都为两个数据的数组，数组每对(p1,e1)表示p1x^e1(p1=0的不用存起来) ? ? ? ? ? ? ? ? ? ? ? ? ? (优点：节省空间)

②链式储存结构实现

2.4节可以参考noj 1005 1006两题.

http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1005

http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1006

（编辑：ASP站长网）