静态单链表 :

线性表的静态单链表存储结构 :

#define MAXSIZE 100;

 

typedef struct{

 

  ElemType data;

  int cur;

 

}component,SLinkList[MAXSIZE];

 

分析 :

这种描述方法便于在不设 ” 指针 ” 类型的高级程序设计语言中 , 使用的链表结构 . 数组的零分量可看成头节点 . 这种结构仍然需要预先分配一个较大的空间 . 但在插入和删除的时候 , 不需要移动元素 . 仅需要修改指针 . 所以仍然具有链式存储结构的主要优点 .

 

基本操作 :

(1)    在静态单链表中 , 查找第一个值为 e 的元素 .

int LocateElem_L(SLinkList S, ElemType e)

{

 

   i = S[0].cur;

   while(i && S[i].data != e) i=S[i].cur;

   return i;

 

}

分析 :

如果找不到相应的元素 , 返回值为 0.

(2)      将一维数组 space 中的各个分量 , 链成一个备用的链表 .

space[0].cur 为头指针 .

 

void InitSpace(SLinkList &space){

 

 

   for(i =0;i<MAXSIZE-1;++i)

      space[i].cur = i+1;

   space[MAXSIZE-1].cur =0;

 

}

 

(3)    如果备用空间的链表非空 , 则返回分配的节点下标 ,

否则 , 返回 0;

 

int Malloc_SL(SLinkList &space){

 

   i=space[0].cur;

   if(space[0].cur)

      space[0].cur =space[i].cur;

   return i;

}

(4) 将下标为 k 的空闲节点回收到备用链表 .

void Free_SL(SLinkList &space,int k)

{

space[k].cur =space[0].cur;

space[0].cur = k;

}

(4)    计算集合运算 (A-B ) ∪ (B-A)

假设由终端输入集合元素 , 先建立表示集合 A 的静态链表 S, 然后在输入集合 B 的元素的同时查找 S 表 , 如果存在相同的元素 , 则从 S 表中删除 , 否则将其插入到 S 表中 .

具体代码如下 :

void difference(SLinkList &space , int &s)

{

 

      InitSpace_SL(space);

      s = Malloc_SL(space);

      r=s;

      scanf(m,n);

      for(j=1;j<=m;++j)

{     i =Malloc_SL(space);

           scanf(space[i].data);

           space[r].cur =i;

           r=i;

      }  space[r].cur=0;

for (j=1;j<=n;++j){

    scanf(b);

    p=s;k=space[s].cur;

    while(k!=space[r].cur && space[k].data !=b)

    { p=k;k=space[k].cur;}

if (k==space[r].cur)

{

       i = Malloc_SL(space);

       space[i].data = b;

       space[i].cur = space[r].cur;

       space[r].cur = i;

       r=i;

    }

    else{

      space[p].cur =space[k].cur;

      Free_SL(space,k);

      if(r==k)

      r=p;

    }

}

}

线性表的链式存储结构 :

链式存储表示 :

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