随笔-14  评论-142  文章-0  trackbacks-0

线性表的链式存储结构 :

链式存储表示 :

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


posted on 2006-06-16 01:04 liulang 阅读(939) 评论(3)  编辑  收藏

评论:
# re: 单链表学习笔记 2006-06-24 16:18 | leilei
怎么使用c写的??  回复  更多评论
  
# re: 单链表学习笔记 2006-06-24 16:20 | liulang
我现在也在同步学习C!!  回复  更多评论
  
# re: 单链表学习笔记 2006-10-31 18:20 | lovekker
谢谢,正在学习 非常需要!!!   回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: