静态单链表 :

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

#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;

    }

}

}