1

大家好,我是新人,所以我相信你会帮助我在跳过列表时遇到一些麻烦这里是代码

#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <string.h>
#define P 0.5
#define MAX_LEVEL 6
 struct sn{
          int value;
        struct sn **forward;
         };
 typedef struct sn skipnode;
 typedef struct{
     skipnode * header;
      int level;
      }skipset;
 float frand(){

     return (float) rand()/RAND_MAX;

 }
 int random_level(){
     static int first=1;
     int lvl=0;
        if (first) {
             srand((unsigned) time(NULL));
             first=0;
        }
          while (frand()<P && lvl <MAX_LEVEL)
               lvl++;
          return lvl;
 }
 skipnode* make_node( int level,int value){
      skipnode *sn=(skipnode*)malloc(sizeof(skipnode));
      sn->forward=(skipnode**) calloc(level+1,sizeof(skipnode));
      sn->value=value;
      return sn;
 }


 skipset *makeskipset(){
      skipset *ss=(skipset*)malloc(sizeof(skipset));
      ss->header=make_node(MAX_LEVEL,0);
      ss->level=0;
       return ss;

 }
 void print_skipset(skipset *ss){

     skipnode *x=ss->header->forward[0];
     printf("(");
      while (x!=NULL){
          printf("%d",x->value);
          x=x->forward[0];
            if (x!=NULL)
                printf(",");



      }
      printf("}\n");

 }
 int contains(skipset *ss,int search_value){
      int i;
      skipnode *x=ss->header;
      for (i=ss->level;i>=0;i--){
          while (x->forward[i]!=NULL && x->forward[i]->value<search_value){

              x=x->forward[i];
          }
          }
      x=x->forward[0];
      if (x!=NULL && x->value==search_value)
           return 1;
       return 0;
 }

 void insert(skipset *ss,int value){
     int i;
     skipnode *x=ss->header;
     skipnode* update[MAX_LEVEL+1];
      memset (update,0,MAX_LEVEL+1);
      for (i=ss->level;i>=0;i--){
          while ( x->forward[i]!=NULL && x->forward[i]->value<value){
              x=x->forward[i];
          }

          update[i]=x;


      }
      x=x->forward[0];
      if ( x==NULL && x->value!=value){
          int lvl=random_level();
          if (lvl>ss->level){
              for (i=ss->level+1;i<=lvl;i++){
                  update[i]=ss->header;
          }
              ss->level=lvl;

      }
          x=make_node(lvl,value);
            for (i=0;i<=lvl;i++){
                x->forward[i]=update[i]->forward[i];
                update[i]->forward[i]=x;

            }

 }
 }

 void Delete( skipset *ss,int value){

     int i;
     skipnode *x=ss->header;
     skipnode *update[MAX_LEVEL+1];
     memset(update,0,MAX_LEVEL+1);
     for (i=ss->level;i>=0;i--){

         while (x->forward[i] !=NULL && x->forward[i]->value<value){
             x=x->forward[i];
         }
         update[i]=x;
     }
     x=x->forward[0];
     if (x->value==value){

         for (i=0;i<ss->level;i++){
             if (update[i]->forward[i]!=x)
                  break;
             update[i]->forward[i]=x->forward[i];
         }
          free(x);
          while (ss->level>0 &&ss->header->forward[ss->level]==NULL){
              ss->level--;

     }
 }
 }
     int main(){

          skipset *ss=makeskipset();
           print_skipset(ss);

            insert(ss,3);
            insert(ss,10);
            insert(ss,7);
            insert(ss,11);
            insert(ss,20);
            insert(ss,34);
              if (contains(ss,7)){
                  printf(" 7 is in the list\n");
              }
              print_skipset(ss);
              Delete(ss,7);
              print_skipset(ss);
              return 0;
     }

我编译得很好但是当我运行执行它突然停止工作请帮助我

4

2 回答 2

4

当我在 中运行您的代码时gdb,我看到您的方法崩溃了insert

if ( x==NULL && x->value!=value){

这显然是错误的。当 x 是NULL你试图取消引用它。将其更改为

if ( x!=NULL && x->value!=value){
于 2010-09-10T11:34:01.360 回答
4

这一行在这里:

if ( x==NULL && x->value!=value){ 

在插入功能中-不应该x != NULL-假设您想要进行短路安全测试。这就是它爆炸的地方。

于 2010-09-10T11:34:06.150 回答