论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2009-02-02 11:30 |只看该作者 |倒序浏览

如题，用静态数组扩展的方法来实现一个静态链表，感觉链表大了以后很难有高效的方法得到"下一个可用节点的位置"。

(1)是不是可以考虑用多块内存拼接，双层查找呢? 就像文件系统里面的inode节点算法那样，有个bit图? 还有什么好的办法吗?
(2)还有就是，链表的实现如果有了一个数据域为空的"头"指针的话，操作起来会方便的多，否则会有很多麻烦的判断。大家觉得呢?

下面是我写的一个小程序可以无误运行。我发现如果省略了"头"指针的话，代码会变复杂。
------------------------------------------------------------------------------------------------------------------------
#define MAX 5
#include<stdio.h>
#include<stdlib.h>
struct e{//静态链表的元素
int d;//data
int i;//index
};
class L{
int c;//capacity, 容器大小
int s;//size实际使用的大小
e* pe;//数据域
int h;//头位置
int t;//尾位置
public:
L():c(MAX),s(0),h(0),t(0){
   pe=new e[MAX];
   for(int a=0;a<MAX;++a)
   pe[a].i=0;
}
~L(){delete [] pe;}
int avalible(){//返回可以用的空间，有没有提高效率的方法
   for(int a=0;a<c;++a){
   if(pe[a].i==0 && a!=t)return a;//效率很低
   }
   return -1;
}
void app(int data){//添加
   if(s==0){//空表，添加第一个元素
      h=t=0;
      pe[0].d=data;
      pe[0].i=0;
      ++s;
      return;
   }
   if(s==c){
      pe=static_cast<e*>( realloc(pe,(c+MAX)*sizeof(e) ) );//链表已经满了
      for(int c1=c;c1<c+MAX;++c1)pe[c1].i=0;
      c=c+MAX;
   }
   ++s;
   int next=avalible();
   if(next==-1)return;
   pe[t].i=next;
   t=next;
   pe[t].i=0;//末尾置0
   pe[t].d=data;
}
bool del(int data){//删除
   if(pe[h].d==data){//删除头数据
   int tmp=h;
   h=pe[h].i;
   pe[tmp].i=0;
   --s;
   return true;
   }
   int p=h;//数据匹配的位置
   int f;//匹配
   while(pe[p].i){
   f=p;
   p=pe[p].i;
   if(pe[p].d==data){//找到了
      pe[f].i=pe[p].i;
      pe[p].i=0;//标记为可用
      --s;
      return true;
   }
   }
   printf("删除失败\n");
   return false;
}
void print(){//打印全部信息
   if(s==0){
   printf("空链\n");
   return;
   }
   int p=h;
   for(int j=0;j<s;++j){
   printf("pe[%d].d=%d,i=%d\n",p,pe[p].d,pe[p].i);
   p=pe[p].i;
   }
}
};
int main(int argc, char *argv[]){
   L list;
   list.app(2);
   list.app(3);
   list.app(4);
   list.app(7);
   list.app(20);
   list.del(4);//删除一个
list.app(9);
   list.app(30);//应该realloc
   list.print();
   list.del(2);//删除头
list.del(4);//应失败
list.del(3);
   list.del(20);
   list.del(7);
   list.print();
   list.del(9);
   list.print();
   list.del(30);
   list.print();//空表*/
//system("PAUSE");
return EXIT_SUCCESS;
}