第二章：线性表
2.1线性表的类型定义
2.2线性表的顺序表示和实现
2.3线性表的链式表示和实
2.4一元多项式的表示及相加
线性结构
线性结构的特点是：在数据元素的非空有限集中.
(1)存在唯一的一个被称为“第一个”的数据元素；
(2)存在唯一的一个被称做“最后一个”的数据元素；
(3)除第一个之外，集合中的每个数据元素均只有一个前驱；
(4)除最后一个之外，集合中每个元素均只有一个后继
2.1线性表的类型定义
线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。例如，26个英文字母的字母表:
(A,B,C,D,……,Z)
是一个线性表，表中的数据元素是单个字母字符。
在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。
例如，一个学校的学生健康情况登记表，表中每个学生的情况为一个记录，它有姓名、学号、性别、年龄、班级和健康等6个数据项组成。
线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。若将线性表记为:
则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,3,……,n-1， ai有且仅有一个直接后继，当i=2,3,4,……,n时，ai有且仅有一个直接前驱。
线性表中元素的个数n(n≥0)定义为线性表的长度，n=0时称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素,an是 最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可进行插入和删除等。
2.2线性表的顺序表示和实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个元素的存储位置LOC(ai)之间满足下列关系:
一般来说，线性表的第i个数据元素ai的存储位置为：
式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。
线性表的这种机内表示称做线性表的顺序存储或顺序映像，通常，称这种存储结构的线性表为顺序表。它的特点是，为表中相邻的元素ai和ai+1相邻的存储位置LOC(ai)和LOC(ai+1).换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每个数据元素的存储位置都和线性表的其实位置相差一个和数据元素在线性表中的位序成正比的常数。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常用可变长数组来描述数据结构中的顺序存储结构。
2.3线性表的链式表示和实现
线性链表
线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表示任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也铸成了这种存储结构的弱点：在作插入或删除操作时，需要移动大量元素。本节我们将讨论线性表的另一种表示方法——链式存储结构，由于它不要求逻辑上相邻的元素在物理地址上也相邻， 因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映射，称为结点(node)。它包括两个域，其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。N个节点((ai(1≤i≤n)的存储映像)链接成一个链表，即为线性表:
的链式存储结构，又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。
例如线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的线性链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点(即第一个元素的存储映像)的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”(NULL)。
用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中指针。这是因为在使用链表时，我们只需要关系数据元素之间的逻辑顺序，而不需要关心其在存储器中的实际位置。
循环链表
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针指向头结点，而不是“空”(NULL)，整个链表形成一个环，由此，从表中任一结点出发均可找到表中其他结点。
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。
双向链表
在上述的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针往后查询其他结点。如果要寻查结点的直接前驱，则需要从表头指针出发。换句话说，在单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O(n)为了克服单链表这种单向性的缺点们可以利用双向链表。
在双向链表的结点中有两个指针域，一个指向其直接前驱，一个指向其直接后驱。
双向链表也可以有循环表如：
2.4一元多项式的表示及相加
在数学上，一个一元多项式Pn按升幂可写成:
我们可以把其系数项和指数项作为数据项设计成一个线性表，如：
如何实现两个多项式相加？
可以自己探索算法进行实现。
Js实现一个单链表:
function Node(element){
this.element = element;//节点存储的元素
this.next = null;//节点指向的下一个节点，这里先设置为空
}
function LList(){
this.head = new Node("head");//生成一个头节点
this.find = find;//在链表中找到某个节点
this.insert = insert;//在链表中某个元素后面插入某个节点元素
this.display = display;//链表遍历
}
function find(item) {
var currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
function display() {
var currNode = this.head;
var nodestr = "";
while (currNode.next !== null) {
nodestr +=" "+currNode.next.element;
currNode = currNode.next;
}
console.log(nodestr);
}
/测试例子/
var num = new LList();
num.insert("a1", "head");
num.insert("b1", "a1");
num.insert("c1", "b1");
num.display();// a1 b1 c1
