Проблемы со связанным списком в C - PullRequest
Новая
       10

Проблемы со связанным списком в C

1 голос
/ 15 марта 2010

Я новичок в C и работаю над списком XOR для проекта. Я выполнил большую часть кода, но мне кажется, что функция удаления списка не работает должным образом. Кажется, в состоянии удалить некоторые числа, но не любое число, которое вы передаете в функцию. Может ли кто-нибудь, имеющий опыт работы с C, взглянуть и, возможно, указать, где я ошибся? Я работал над этим уже некоторое время и мне не повезло, и я начал более 3 раз :( Любая помощь очень ценится. Спасибо. Вы можете увидеть мою первую попытку кода здесь . Я могу опубликовать только одну ссылку, поэтому, если вы хотите увидеть мою вторую попытку, просто скажите мне об этом, и я могу отправить ее вам по электронной почте или что-то в этом роде. Спасибо за ваше время. 

#include <stdio.h>
#include <stdlib.h>
#include "rndm.h"

struct node {
       int data;
       unsigned long link;
};
struct node *head, *tail, *currN, *prevN, *nextN, *tmp;

void insert(struct node **headN, struct node **tailN, int n);
void delete(struct node **headN, struct node **tailN, int n);
void list(struct node *head, int i);
void nextNode();
void previNode();

//============================================================

void insert(struct node **headN, struct node **tailN, int numN) {
     struct node *newnode = malloc(sizeof(struct node));
     newnode->link =(unsigned long)(*headN);
     newnode->data = numN;

     //if empty list
     if (*headN == NULL){
          *headN = newnode;
          currN = *headN;
          (*headN)->link = 0;
     } else if ((*headN)->link == (unsigned long)NULL){
           if (numN <= (*headN)->data){
                newnode->link = (unsigned long) *headN;
                (*headN)->link = (unsigned long) newnode;
                tail = *headN;
                *headN = newnode;
                nextN = tail;
                prevN = NULL;
            } else {
                newnode->link = (unsigned long) *headN;
                (*headN)->link = (unsigned long) newnode;
                tail = newnode;
                nextN = NULL;
                currN = tail;
                prevN = *headN;
              }
     } else { 
          currN = *headN;
          prevN = NULL;
          nextN = (struct node *)(currN->link ^ (unsigned long) prevN);
          if (numN > tail->data){
               while (currN!=tail){
                     nextNode();
               }
               newnode->link = (unsigned long) currN;
               currN->link = (unsigned long) newnode ^ (unsigned long) prevN;
               tail = newnode;
          } else if (numN < head->data){
               currN->link = (unsigned long) newnode ^ (unsigned long) nextN;
               newnode->link = (unsigned long) currN;
               *headN = newnode;
               nextN = currN;
               currN = *headN;
          } else {
               while (numN > currN->data){
                     nextNode();
               }
               newnode->link = (unsigned long) prevN ^ (unsigned long) currN;
               prevN->link ^= (unsigned long) currN ^ (unsigned long) newnode;
               currN->link ^= (unsigned long) prevN ^ (unsigned long) newnode;
          }
     }
}  

void delete(struct node **headN, struct node **tailN, int numD){

     struct node *prevN = NULL;
     struct node *currN = *headN;

     while ( currN != NULL )
    {
        struct node *nextN = (struct node *) (currN->link ^ (unsigned long)prevN);  
        //if the number is found, then delete it
        if (currN->data == numD)
        {
          if(prevN) 
                  {
                     prevN->link ^= (unsigned long)currN ^ (unsigned long)nextN;
              }
                  else 
                     *headN = nextN;
              if(nextN) 
                  {
                     nextN->link ^= (unsigned long)currN ^ (unsigned long)prevN;
                  } 
                  else 
                     *tailN = prevN;
          free(currN);
          break;
        }
            prevN = currN;
        currN = nextN;
    }
}

void list(struct node *head, int i){

    if(i == 0){ 
     currN = head;
     prevN = NULL;
     int count = 1;
     nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
     printf("Linked List in ascending order\n");
     while(currN!=NULL){
          if(count <= 10){
               printf("%-5d", currN->data);
               nextNode();
               count++;
          } 
          else{
               printf("\n");
               count = 1;
          }
     }
    }
     printf("\n\n"); 

    if(i == 1){ 
     printf("Linked List in descending order\n");
     currN = tail;
     int count2 = 1;
     prevN = (struct node *) currN->link;
     nextN = NULL;
     while (currN!=NULL){
         if(count2 <= 10){
              printf("%-5d", currN->data);
              previNode();
              count2++;

          }else{
              printf("\n");
              count2 = 1;
          }
     } 
    }   
    printf("\n");         
}

void nextNode(){
    nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
    prevN = currN;
    currN = nextN;
}

void previNode(){
    prevN = (struct node *) (currN->link ^ (unsigned long) nextN);
    nextN = currN;
    currN = prevN;      
}

int main(){

    int i, num;
    float seed;
    head = NULL; tail = NULL; currN = NULL; prevN = NULL; nextN = NULL;

    init_seed(1234567);
    set_range(1,9999);
    //inserting data into the linked list
    for ( i=0; i<100; ++i){
        num = rndm();
        insert( &head, &tail, num );
    }

    list((struct node*)head, 0);
    //delete((struct node**)head, (struct node**)tail, 45);
    //delete((struct node**)head, (struct node**)tail, 4040);
    //delete((struct node**)head, (struct node**)tail, 9769);
    list((struct node*)head, 1);


    return 0;
}

Ответы [ 3 ]

5 голосов
/ 15 марта 2010

Похоже, вы взяли какой-то код в интернете и попытались его использовать.

Код работает просто отлично, вы просто не знаете, что такое указатель.

Вы делаете: 

delete((struct node**)head, (struct node**)tail, 45);

А вот определения переменных head и tail: 

struct node {
  int data;
  unsigned long link;
};
struct node *head, *tail, *currN, *prevN, *nextN, *tmp;

Прототипом функции delete() является void delete(struct node **headN, struct node **tailN, int numD);

«О, компилятор запрашивает struct node **, давайте его приведем». Это не так, как это работает.

Попробуйте это: 

delete(&head, &tail, 45);
0 голосов
/ 15 марта 2010

Глядя на функцию delete, я задаюсь вопросом об этой манипуляции с указателем, кстати, вы используете параметры address-of, так что на самом деле это должно быть delete(&head, &tail, 45);

переходя от этого .... 

void delete(struct node **headN, struct node **tailN, int numD)
{
   struct node *prevN = NULL;
   struct node *currN = *headN; 
   struct node *tempNode = NULL;

   while ( currN != NULL )
   {
      struct node *nextN = (struct node *) (currN->link ^ (unsigned long)prevN);  
      //if the number is found, then delete it
      if (currN->data == numD)
      {
          if(prevN)
             prevN->link ^= (unsigned long)currN ^ (unsigned long)nextN;
          else 
             *headN = nextN;
          if(nextN)
             nextN->link ^= (unsigned long)currN ^ (unsigned long)prevN;
          else
             *tailN = prevN;
          /* Sanity check here...you could be screwing up the list 
          ** by calling free(currN)
          */
          tempNode = currN;
          free(tempNode);
          /* free(currN); <-- That could be misleading... */
          break;
       }
       prevN = currN;
       currN = nextN;
   }
}

Эта поправка к коду состоит в том, чтобы обеспечить согласованность currN, глядя на манипуляции с указателем, что может быть сомнительным, поскольку список может быть в конечном итоге нарушен при выполнении free для currN ... просто чтобы быть в безопасности ...

0 голосов
/ 15 марта 2010

Примечание о вашем коде:

node.link не должно быть unsigned long, поскольку оно предполагает характеристики вашего компилятора / платформы.

РЕДАКТИРОВАТЬ: Может быть, я пропустил в связанном списке XOR, обсуждение.

РЕДАКТИРОВАТЬ 2: (как предложено @Matthew Flaschen) используйте intptr_t, чтобы сделать ваш код более переносимым.

...