2.3.3 单链表其它算法举例

例题 例2-7 逆序创建链表

　　假设线性表( ，，…， )的数据元素存储在一维数组 A[n]中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为"空"的链表中。
　		  

　解题分析：
　　由于链表是一种动态存储管理的结构，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统应需求即时生成，因此，建立链表的过程是一个动态生成的过程。即从 "空表"起，依次建立结点，并逐个插入链表。所谓"逆序"创建链表指的是，依和线性表的逻辑顺序相"逆"的次序输入元素。例如动画演示了线性表 (a,b,c,d,e) 的逆序创建的过程。动画

　　由于链表的生成是从最后一个结点起逐个插入，因此每个新生成的结点都是插入在链表的"第一个"结点之前，即头结点之后，使新插入的结点成为插入之后的链表中的第一个结点。		  
  算法 算法2.19
　　void CreateList_L(SLink &L, int n, ElemType A[])
　{
　　// 已知数组 A 中存有线性表的 n 个数据元素，
　　// 逆序建立带头结点的单链表。
　　L = new LNode;
　　if (!L) exit(1); 　　　　// 存储空间分配失败
　　L->next = NULL;　　// 先建立一个带头结点的空的单链表
　　for (i = n; i > 0; --i)
　　{ p = new LNode;
　　　if (!p) exit(1); 　　　　// 存储空间分配失败
　　　　p->data = A[i-1]; 　　　　　 　// 赋元素值
　　　　p->next = L->next; L->next = p; // 插入在头结点之后
　　} // for
　} // CreateList_L

　　容易看出，算法的时间复杂度为O (ListLength(L))。

  



　



　　控制结构只有一个单循环，循环次数和表长相同。

  思考题 如果是"顺序"创建单链表，那么算法该如何写呢？