线性表的链式存储结构 :

链式存储表示 :

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).