3

私は CS の学生ですが、ハロウィーンの週末は、デバッグできないプログラミングの課題によって台無しになりました。これは、ここですぐに「重複」とマークされない数少ない質問の 1 つかもしれません。

割り当ては、「スキップ リスト」、またはランダムな「コイン」トスによって決定されるポインタの可変サイズ配列が各ノードにある単一リンク リスト (C でプログラム) です。トスが 3 回成功すると、高さは 3 などになります。次に、各配列は同様の高さの他の配列にリンクされます。7 番目のレベルは次の 7 番目のレベルにリンクされ、6 番目から次の 6 番目のレベルにリンクされ、最初のレベルまで、または配列要素にリンクされます。 0 は、リスト内の次の項目に自然にリンクされます。

ほとんどのアイテムにはより高いレベルがないため、これは単純に n ではなく log(n) 時間で検索するための優れた方法として機能します。挿入、削除、および検索が劇的に高速になりますが、メモリのコストが高くなります。これは単なる理論です - ここに写真があります:スキップリスト

皆さんの多くはすでにこのことを知っているでしょうが、少し説明して、ここで起こっていることの基本を実際に理解していることを示したかっただけです.

この問題は、提供されたすべてのテストを "CODE 6 - ABORT" メッセージで台無しにするランダムなセグメンテーション違反です。メイン ファイルを実行すると、コード内の指定された場所 (<-----Segfaults) でランダムに segfaults が発生します。これは約半分の時間で発生し、いずれかの行で発生する可能性があります。テストでは、多くの「不良ポインター」および「minmap チャンク エラー」メッセージも表示されます。

私はこれで頭がいっぱいです。私はクラスで 93 を持っていますが、この忌まわしいことを終わらせることができなければ、それは 87 に落ちます。

コードは次のとおりです。

定義

typedef int data_t;

typedef struct skip_node {
    data_t data;
    size_t height;
    struct skip_node **next;
} skip_node_t;

typedef struct skip_set {
    skip_node_t *head;
    size_t max_height;
    size_t size;
} skip_set_t;

ランダムフォルトの主な原因 

skip_set_t set;
skip_set_init(&set);
skip_set_add(&set, 4);
skip_set_add(&set, 3);
skip_set_clear(&set);
skip_set_t set2;
skip_set_init(&set2);
skip_set_add(&set2, 1); //faults here

...そして最後に、悪魔のデータ構造:

    #include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "skip_set.h"

/***********************
        PART 1
***********************/

//Initialize
void skip_set_init(skip_set_t *set)
{
   //Set
   set->size = 0;
   set->max_height = 1;
   set->head = malloc(sizeof(skip_node_t));

   //Sentinel
   set->head->data = 0; 
   set->head->height = set->max_height;
   set->head->next = malloc(sizeof(skip_node_t*) * set->max_height); 
}

//Clear
void skip_set_clear(skip_set_t *set)
{   
   if (set->head == NULL)
      return;

   skip_node_t* this;
   skip_node_t* nex;
   this = set->head->next[0];
   while(this != NULL)
   {
      nex = this->next[0];
      free(this->next);
      this->next = NULL;
      free(this);
      this = nex;
   } 
   set->size = 0;

   for (int ii = 0; ii < set->max_height; ii++)
      set->head->next[ii] = NULL; 
}

//Size
size_t skip_set_size(skip_set_t *set)
{
   return set->size;
}

//Free
void skip_set_free(skip_set_t *set)
{
   skip_set_clear(set);

   free(set->head->next);
   set->head->next = NULL;

   free(set->head);
   set->head = NULL;
}

//Add
void skip_set_add(skip_set_t *set, data_t value)
{
   printf("Add Start\n");
   if (skip_set_contains(set, value))
      return;

   int new_height = 1;    

   while(rand() % 2 == 0)
   {
      new_height++;
   }
   printf("Add One\n");
   if (set->max_height < new_height)
   {
      skip_node_t** arr = malloc(sizeof(skip_node_t*) * new_height);

      for (int ii = 0; ii < set->max_height; ii++)
         arr[ii] = set->head->next[ii];

      for (int jj = set->max_height; jj < new_height; jj++)
         arr[jj] = NULL; 
      printf("Add Two\n");
      free(set->head->next);
      set->head->next = NULL;  
      set->head->next = arr;
      set->max_height = new_height;
      set->head->height = new_height; 
      printf("Add Three\n");  
   } 

   skip_node_t* new_node = (skip_node_t*)malloc(sizeof(skip_node_t));

   skip_node_t** arr = calloc(new_height, sizeof(skip_node_t*));
   new_node->next = arr;
   new_node->height = new_height;
   new_node->data = value;

   skip_node_t* cur_node = set->head; 
   int cur_level = set->max_height - 1; 
   printf("Add Four\n");
   while (cur_level >= 0)
   {
      printf("ABreak 1\n");
      while ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data < value))//<-----Segfaults
      {
         printf("ABreak 2\n");
         cur_node = cur_node->next[cur_level];
         printf("ABreak 3\n");
      }
      printf("ABreak 4\n");
      if (cur_level < new_height)
      {
         printf("ABreak 5\n");
         new_node->next[cur_level] = cur_node->next[cur_level];
         cur_node->next[cur_level] = new_node;
         printf("ABreak 6\n");
      }
      printf("ABreak 7\n");
      cur_level--;       
   }

   set->size++;
   printf("Add End\n");   
}

//Remove
void skip_set_remove(skip_set_t *set, data_t value)
{
   printf("Remove Start\n");
   if (!skip_set_contains(set, value))
      return;

   skip_node_t* tbf;
   skip_node_t* cur_node = set->head;

   int cur_level = set->max_height - 1;
   printf("Remove 1\n");
   while (cur_level >= 0)
   {
      while ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data < value))
      {
         cur_node = cur_node->next[cur_level];
      }

      if ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data == value))
      {
         tbf = cur_node->next[0];
         cur_node->next[cur_level] = cur_node->next[cur_level]->next[cur_level];
         if (cur_node == NULL && cur_node->next[cur_level] == NULL)
            set->max_height--;
      }      
      cur_level--;       
   }
   printf("Remove 2\n");
   free(tbf->next);
   printf("Remove 3\n");
   free(tbf);
   set->size--;   
   printf("Remove End\n");
}

//Pop
data_t skip_set_pop(skip_set_t *set)
{
   printf("Pop Start\n");
   data_t lazyCSstudent = set->head->next[0]->data;
   skip_set_remove(set, lazyCSstudent);
   printf("Pop End\n");
   return lazyCSstudent;
}

//Contains
bool skip_set_contains(skip_set_t *set, data_t value)
{ 
   printf("Contains Start\n");
   skip_node_t* this = set->head;
   int i = set->max_height - 1;
   printf("Contains Mid\n");
   while(i >= 0)
   {
      printf("CBreak One\n");
      while((this->next[i] != NULL) && (this->next[i]->data < value)) ///<-----Segfaults
      {
         printf("CBreak Two\n");
         this = this->next[i];
         printf("CBreak Three\n");
      }
      i--;
      printf("CBreak Four\n");
   }
   printf("Contains End\n");
   return (this->next[0] != NULL) && (this->next[0]->data == value);   
}

他のものもあるかもしれませんが、Contains と Add が問題です。奇妙なことに、これは通常、別のリストを解放した後に発生しますが、コード内にそのリストからのアーティファクトが見つかりません。

あなたがこれを解決してくれたら、20 ドルと 1 皿のクッキーをあなたの選んだ住所に郵送します。

4

3 に答える 3

1

skip_set_init()ポインタ配列にメモリを設定max_heightして割り当てます1

set->max_height = 1;
...
set->head->next = malloc(sizeof(skip_node_t*) * set->max_height);

ただし、配列の要素は初期化しませんnext。次にskip_set_add()

for (int ii = 0; ii < set->max_height; ii++)
    arr[ii] = set->head->next[ii];

for (int jj = set->max_height; jj < new_height; jj++)
    arr[jj] = NULL;

最初の要素は初期化されていない配列からコピーされ、他の要素 [1..] は に設定されNULLます。

したがって、最初の要素arr[0]は初期化されていない値です。

私はこれ以上見ていません。

于 2015-10-31T18:04:55.297 に答える