数据结构

　2.3.2 单链表中基本操作的实现

　三、存取元素操作

　　单链表是一种"顺序存取"的结构，即：为取第 i 元素，首先必须先找到第 i-1 个元素。因此不论 i 值为多少，都必须从头结点开始起"点数"，直数到第 i 个为止。头结点可看成是第0个结点。
　

　　可见算法中应设一个指针变量p和一个整数变量 j，并使 p 和 j 同步变化，始终保持指针 p 指向第j的结点的状态。

算法2.15
　　bool GetElem ( SLink L, int pos, ElemType &e )
　{
　　// 若1≤pos≤LengthList(L)，则用 e 带回指针L指向头结点的单链表
　　// 中第 pos 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE
　　p = L->next; j =1; 　　　　// 变量初始化，p 指向第一个结点
　　while ( p && j< pos )
　　{ 　　　// 顺结点的指针向后查找，直至 p 指到第pos个结点或 p 为空止
　　　p = p->next; ++j;
　　} // while
　　if ( !p || j>pos ) return FALSE; // 链表中不存在第 pos 个结点
　　e = p->data; 　　　　　　　　　　 // 取到第 pos 个元素
　　return TRUE;
　} // GetElem

　　算法的时间复杂度为O (ListLength(L))。

　　由于链表的长度是个隐含值，因此无法预先判别参数 pos 是否超过表长，只能在"数结点" 过程中，j还没有达到 pos 时而指针变为空时才能判断出参数不合法。

什么情况下会出现 j>pos 的情况？

　j>pos 的情况即为 pos<1 的情况，注意：因算法中j的初值为"1"，若 pos=1，则 while 循环一次也不执行。　　

能否将变量初始化改为"p=L; j=0;"?

　对 pos 为正常值的情况没有影响，只是使 while 循环多执行一次吧了。但此时无法用 j>pos 判别出 pos<1 的错误，当然也可以在函数一开始就加上 pos 是否大于0的判别？

算法时间复杂度的分析：
　　控制结构只有 while 一个单循环，基本操作为"移动指针"，最坏情况是 pos>=表长的情况，指针需从头移到尾。