最近参加校园招聘，笔试是必要的。先热身，把数据结构的基础东东拿出来 Review 一下。
线性表的链式存储结构:
链式存储表示:

typedef struct LNode{
  ElemType   data;
  Struct LNode *next;
}LNode,*LinkList;

基本操作在链表上的实现:
(1) 单链表的取元素算法（经典）

Status GetElem_L(LinkList L, int i,ElemType &e)
{
p=L->next; j=1;
while(p && j<i)
{
      p=p->next;++j;
}
if(!p || j>i) return ERROR;
e=p->data;
return OK;
}

算法分析:
基本操作是: 比较 j 和 I, 并把指针后移 , 循环体执行的次数 , 与被查元素的位置有关 . 假设表长为 n, 如果 1<=i<=n, 那么循环体中语句的执行次数为 i-1. 否则次数为 n 所以时间复杂度为 O(n).

(2)  插入元素算法

Status ListInsert_L(LinkList &L, int i,ElemType e)
{
   p=L;j=0;
   while(p&&j<i-1)
      { p=p->next;++j}
   if(!p || j>i-1)
      return ERROR;
   s = (LinkList)malloc(sizeof(LNode));
   s->data = e;
   s->next = p->next;
   p->next =s;
   return OK;
}

(3) 删除元素算法

Status ListDelete_L(LinkList &L, int i,ElemType &e)
{
   p=L;j=0;
while(p &&j<i-1)
   {p=p->next;++j}
if(!p ||j>i-1)
      return  ERROR;
q=p->next;
   p->next =q->next;
   e =q->data;
   free(q);
   return OK;
}

算法分析 :
插入和删除算法 , 都要先找到第 i-1 个节点 , 所以时间复杂度为 O(n);
(4) 单链表的建立算法

void CreateList_L(LinkList &L,int n){
L =(LinkList)malloc(sizeof(LNode));
L->next = null;
  for(i = n;i>0;--i){
  p =(LinkList)malloc(sizeof(LNode));
  scanf(&p->data);
  p->next = L->next;
  L->next =p;
  }
}

算法分析 :
按照逆序循环输入 n 个数据元素的值 , 建立新节点 . 并插入 . 因此算法的时间复杂度为 O(n).