假期连载之二
（线性表的基本运算算法分析，线性表的链式存储—单链表）
前面我们介绍了线性表的顺序存储中有关数据结构以及其常用运算，接下来我们将对其中涉及搜索、插入和删除部分的代码进行性能分析。
首先对于上节使用的伪码描述的Locate(L,e)搜索算法进行分析，该算法的核心思想是，从表L的开始位置起，根据给定的值e，逐个与各表项的值进行比较，若给定值与表中某个值相等，则算法报告搜索成功，并输入该表项的具体位置，如果查遍所有表项仍不符合要求，则返回null。通常衡量搜索代码的时间代价时使用数据比较次数的数值，在搜索成功的情况下，若要找的正好是表中的第一项，则搜索比较次数为1，若为最后的第n项，则比较次数为n，这是最坏的情况，因此若要计算平均数据比较次数，需要考虑到各个表项的搜索概率pi以及找到该表项时的数据比较次数ci。因此搜索的平均数据比较次数ACN(Average comparing number)为：
ACN=∑pi*ci (i=1,2,3,…,n)
通常我们仅考虑搜索项中相等概率的情形，即每个表项被选择的概率均为1/n，且搜索第一个表项的搜索比较次数为1，之后依次类推。则：
ACN=∑pi*ci=(1/n)(1+2+,…,+n)=(1/n)*(1+n)*n/2=(1+n)/2
即需要比较(1+n)/2个表项。
相反，如果搜索不成功即整个表都检测一遍，因此ACN将为n。
在执行顺序表的插入或删除运算时，需要注意，此时表的长度是会发生改变的，因此为了在执行这一类操作过程中不改变原表项的位置关系，通常需要成块移动表项。例如在插入运算中，必须先将第i个到第n个所有表项成块后移一位，以空出可供插入新表项的位置。而当删除操作时，在删除第i个表项后，需要将从i+1到n-1的所有表项向前移动一位，覆盖原位置。在这两种操作中，表项移动的方向是恰好相反的。
因此在分析顺序表的插入和删除操作时，其时间代价主要是以循环内表项的移动次数来衡量的。
例如InsList(L,i,e)插入运算，在插入数据之前，必须先从后往前循环，将第n项到n-i项均向后移动一位。因此最好的情形是在第n+1位插入新表项，此时表项移动个数为0。最差情况是在第1个位置插入新表项，即在0之后。移动表项个数为n。因此平均数据移动次数AMN(Average moving number)在各表项的插入概率相等时为：
AMN=(1/(n+1))* ∑(n-i)=(1/(n+1))*(n+…+1+0)=n/2(i=1,2,…,n+1)
因此就整体性能来说，插入时有i+1个插入位置，平均移动n/2个表项。
同时对于删除操作而言，当删除第i个表项时，需要移动第i+1到第n个总共n-1个表项。另外对于插入操作所不同的是，删除操作并不涉及到第n+1项的情况，因此上式AMN中i的情况应为1,2,…,n即可，所以：
AMN=(n-1)/2
当然在一些算法中并不要求插入时并不必须在表末进行，或者删除时可以将最后一个表项填到第i个空位中去，则此时的插入AMN固定为0，而删除AMN固定为1。
2、 线性表的链式存储(Linked List)
在线性表的顺序存储中，我们使用了基于数组的存储结构，即其物理位置上为邻接关系，这使得顺序表具有如下优点：
1） 无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率提高。
2） 可以方便地随机存取表中的任一结点，存取速度快。
但是，这也不可避免地带来的一些缺点：
1） 在表中插入新元素或删除无用元素时，为了保持其他元素的相对次序不变，平均需要移动一半元素，运行效率较低。
2） 由于顺序表要求占用连续空间，我们在Operating System中了解到，当内存空间使用Static allocation时，当表的长度变化较大，则难以确定合适的存储空间大小，容易造成内存空间的浪费或溢出。如果采用Dynamic allocation策略使用动态存储模式，则可以使用新数组替换原数组，尽管在空间上能够得到有效利用，但会造成较大的时间开销。
为了克服顺序表的缺点，在一些插入/删除操作频繁从而导致空间需求不定的情况中，我们采用链接方式来存储线性表。
从链表的实现角度来看，链表分为静态链表的动态链表两类。而从链接方式来看，链表分为单链表、循环链表、双向链表三类。
在链表结构中，其存储表项可以是物理连续的，也可以是非连续的，甚至呈零散分布，故其结点的逻辑次序和物理顺序不一定相同。为了正确表示出单链表的逻辑关系，我们必须在存储每个表项数据元素值的同时，存储指示其后继结点的地址信息，我们把这两部分信息组成的存储映像称为结点(Node)，通常也称为域(Field)。
结点包含了两个域：数据域和指针域，他们分别用来结点的值和直接后继结点的地址。在单链表Single linked list中，每一个结点中只有一个next指向其直接后继。
值得注意的是，我们在构建一个链表时，为了存放第一个结点的地址，因此通常设置一个头指针H指向第一个结点并作为其直接前驱，而最后一个结点的next指针直接设置为空null。
下面我们给出C语言方法描述的单链表存储结构：
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkList; //这里的LinkList和Node *等价，通常使用LinkList强调头指针，而Node*来定义指向任意结点的指针。
在C++的面向对象方法中，我们通常使用两个类即结点类和链表类来定义单链表。而其具体实现的方法又有4种。
1) 复合类，在LinkNode类中声明友元类List，从而使得LinkNode类和List类都能访问LinkNode类的私有数据成员。
2) 嵌套类，在List类定义的内部对LinkNode类进行定义，则必须将LinkNode类定义在其private部分，从而确保List类的外部对象和函数不能直接接触到LinkNode类的对象，但LinkNode类的数据成员则必须放在public部分，使得LinkNode类和List类的成员都能访问它们。
3) 基类和派生类，把LinkNode声明为基类，同时List类声明为派生类，建立继承关系，让List类继承其数据成员和某些成员函数，表示一种使用关系。此时LinkNode类的数据成员应为protected，以保证被子类使用。
4) 用struct定义LinkNode类，和C语言方法相似，但其失去了封装性，仅在需要简化描述时采用此类方法。
下面仅给出复合类的具体声明方法：
class List;
class LinkNode
{
friend class List;
private:
int data;
LinkNode *link;
};
class Link
{
public:
//链表公共操作
……
private:
LinkNode *first //链表头指针
};
单链表的基本运算
1）初始化单链表：
InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));
(*L)->next=NULL; //带头结点的链表，故L->next=NULL
}
这里明确malloc/free和new/delete的区别，我们知道，malloc/free是C++/C里的标准库函数，而new/delete是C++的运算符，两者都含有申请内存空间/释放的功能，但malloc/free仅仅能做到这一点。C++引入运算符new/delete的目的是，当我们需要动态地建立对象时，由于面向对象方法的限制，必须要利用到运算符的性质，而避免使用函数来操作。在分配内存空间后，还必须执行对象的构造方法，在释放空间时需要执行析构函数，这是malloc/free所不具备的，因此new/delete有其合理性，这一点在java中得到了继承和发展。
2）建立单链表
这里先介绍头结点的概念，我们知道，通常链表初始化过程中会产生一个头指针*L，此时L直接指向null，有时我们需要建立一个头结点以满足一些特殊操作，因此L->next被设置为null。
基于头结点的建表法，即头插法建表。头插法建表的思想是，在一个带头结点的链表L中，首先申请结点空间*s，并给其数据域赋值。由于L->next指向了表中下一个结点，故先s->next=L->next链接后继结点，同时L->=s完成链表的结点插入操作。其伪码表示为：
CreateFromHead(L)
flag=1;
while flag do
c=getchar();
if c!=’$’ then //用来确保’$’为输入结束符
s=(Node*)malloc(sizeof(Node));
s->data=c;
s->next=L->next;
L->next=s;
else then
flag=0;
头插法中输入元素与得到的单链表逻辑顺序相反，因此也被称作逆序建表法。如果需要链表顺序与输入顺序一致，可以直接采用尾插法建表解决。
CreateFromTail(L)
flag=1;
r=L; //r为尾指针，初始化时应指向头结点。
while flag do
c=getchar();
if c!=’$’ then
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
else then
flag=0;
r->next=NULL;
3）删除单链表
单链表删除操作的思想是，首先声明一个空指针r并使其指向要删除的结点，同时将要删除结点直接前驱的next指针指向其直接后继，然后释放r的空间即可。下面给出一个带头结点链表中删除第i个元素的伪码表示：
DelList(L,i,e)
pre=L,k=0;
while pre->next!=NULL&&k<i-1 do
pre=pre->next;
k=k+1;
if !(pre->next) then
error “删除位置不合理！”;
r=pre->next;
pre->next=pre->next->next;
e=r->data;
free(r);
return OK;
4)链表的前插操作，和头插法建表类似，但需要注意的是，由于插入操作可在链表尾部进行，因此其循环条件为pre!=NULL&&k<i-1，并非是pre->next!=NULL，如果在删除操作中忽略了这一点，则可能造成空指针操作，发生错误。
(未完待续)