Ошибка Сегментации в C

Question

Привет, я новый программист на C, у меня ошибка сегментации в моей программе связанных списков, мне было интересно, может ли кто-нибудь помочь мне. Я разместил свой код ниже ... Если вам нужна дополнительная информация, я опубликую ее. Спасибо.

#include "list.h"

//+-------------------------------------------------------------
//+ CREATE NODE
//+
//+ Allocate memory for a node of type struct node and 
//+ initialize it with d. Return a pointer to the new node.
//+-------------------------------------------------------------
struct node* createNode(int d){
  struct node* newNode = malloc(sizeof(struct node)); //create and allocate space in memory for a new node called newNode

  newNode->item = d; //newNode's data is the value stored in 'd'
  newNode->next = NULL; //sets the pointer to the next node to NULL

  return newNode; //return the new node created
}

//+-------------------------------------------------------------
//+ INSERT HEAD NODE
//+
//+ Insert Node n in front of the head of the list, and set
//+ n to be the new head of the list.
//+-------------------------------------------------------------
void insertHead(struct node **headRef, struct node *n){
  struct node* newNode = malloc(sizeof(struct node)); //create and allocate space in memory for a new node called newNode

  newNode->item = n->item; //newNode's data is assigned the value of the parameter node n''
  newNode->next = *headRef; //since we are inserting the node at the head we set the next node to be the head reference
  *headRef = newNode;   //and then we assign the head reference to the new node created, thus, inserting the head node
}

//+-------------------------------------------------------------
//+ INSERT TAIL NODE
//+
//+ Insert Node n at the tail of the LinkedList.
//+-------------------------------------------------------------
void insertTail(struct node **headRef, struct node *n){
  struct node* newNode = malloc(sizeof(struct node)); //create and allocate space in memory for a new node called newNode
  newNode = *headRef;   //the new node is now the head reference

  while(newNode->next != NULL)  //while the next node is not equal NULL
 newNode = newNode->next; //set the newNode to the next node (this finds the last node)

  struct node* tmp = malloc(sizeof(struct node)); //create and allocate space in memory for a new node called tmp

  tmp->item = n->item;   //the data of tmp is assigned the data of the parameter node 'n'
  tmp->next = NULL;   //the node following tmp is set to NULL
  newNode->next = tmp;   //tmp is now set to the next node, thus, becoming the last node i.e. the tail
}

//+-------------------------------------------------------------
//+ COUNT NODES IN LINKED LIST
//+
//+ Count the # of nodes that are part of the LinkedList.
//+-------------------------------------------------------------
int countNodes(struct node *headRef){
  int counter = 0; //create a counter variable to store the number of nodes

  struct node* current = headRef; //create a new node and assign it the reference to the head node

  if(headRef = NULL) return 0;  //if the head is NULL, return 0 (no nodes if no head)

  while(current != NULL){  //while the current node is not NULL
 counter++;   //increment the counter
 current = current->next; //and move on to the next node, thus, adding 1 to the counter with each node passed
  }
  return counter; //return the total number of nodes, stored in counter
}

//+-------------------------------------------------------------
//+ FIND NODE
//+
//+ Return the first node that has item = val, return NULL 
//+ otherwise.
//+-------------------------------------------------------------
struct node* findNode(struct node *head, int val){
  struct node* tmp = malloc(sizeof(struct node)); //create and allocate space in memory for a new node called tmp

  *tmp = *head;   //node tmp is now referring to the head node of the list

  while(tmp != NULL)  //while the tmp node is not equal to NULL
  {
 if(tmp->item == val){ //if the data of the tmp node is equal to the value sent as parameter 
  return tmp; //return the tmp node
 }else{
  return NULL; //otherwise, return NULL
 }  
   tmp = tmp->next; //set the tmp node to the next node in the list (traversing)
  }
}

//+-------------------------------------------------------------
//+ DELETE NODE
//+
//+ Delete node n from the list and free memory allocated to n.
//+-------------------------------------------------------------
void deleteNode(struct node **headRef, struct node *n){
 struct node* toBeDeletedNode = malloc(sizeof(struct node)); //create and allocate space in memory for a new node called toBeDeletedNode

 toBeDeletedNode = findNode(*headRef, n->item); //toBeDeletedNode is set to equal the node findNode() returns
       //this node should be the node with its data = to the data of the parameter node n
 free(toBeDeletedNode); //delete node toBeDeletedNode references and free the space allocated it
}

Вот тестовый файл ....

#include "list.h"
#include <assert.h>
#include <sys/types.h>
#include <stdio.h>

// create and insertHead
void test1() 
{
 struct node *headRef=NULL;
    struct node *nptr = NULL;
 int h=0;

 while(h<5)
      insertHead(&headRef,createNode(h++));
 h = 0;
 for (nptr = headRef; nptr != NULL; nptr = nptr->next, h++) 
  assert(nptr->item == (4 - h) );
 assert(h==5);

 printf("HAHA");
}

// create and insertTail
void test2() 
{
 struct node *headRef=NULL;
    struct node *nptr = NULL;
 int h=0, t=0;

 while(h<5)
      insertTail(&headRef,createNode(h++));

 h = 0;
 for (nptr = headRef; nptr != NULL; nptr = nptr->next, h++) 
  assert(nptr->item ==  h);
 assert(h==5);
 printf("HAHA");
}

// countNodes 
void test3() 
{
 struct node *headRef=NULL;
    struct node *nptr = NULL;
 int h=0, t=0;

 while(h<50)
      insertTail(&headRef,createNode(h++));
 h = 0;
 for (nptr = headRef; nptr != NULL; nptr = nptr->next, h++) 
  assert(nptr->item ==  h);
 assert(countNodes(headRef) == 50);
}

// findNode 
void test4() 
{
 struct node *headRef=NULL;
    struct node *nptr = NULL;
 int h=0;

 nptr = findNode(headRef, 1);
 assert(nptr == NULL);

 while(h<50)
      insertTail(&headRef,createNode(h++));


 nptr = findNode(headRef, 10);
 assert(nptr != NULL);
 assert (nptr->item = 10);

 nptr = findNode(headRef, -10);
 assert(nptr == NULL);
}

// deleteNode 
void test5() 
{
 struct node *headRef=NULL;
    struct node *nptr = NULL;
 int h=0;

 while(h<5)
      insertTail(&headRef,createNode(h++));

 h = 0;
 while(h<5) {
  nptr = findNode(headRef, h);
  assert(nptr != NULL);
  deleteNode(&headRef, nptr);
  assert(findNode(headRef, h) == NULL);
  assert(countNodes(headRef) == (4 - h));
  h++;
 }
}

/*// sort
void test6() 
{
 struct node *headRef=NULL;
    struct node *nptr = NULL;
 int h=0;
 int d[5] = {1, 0, -1, 5, 100};
 int ds[5] = {-1, 0, 1, 5, 100};

 while(h<5)
      insertTail(&headRef,createNode(d[h++]));

   sort(&headRef);

 h = 0;
 for (nptr = headRef; nptr != NULL; nptr = nptr->next, h++) 
  assert(nptr->item ==  ds[h]);
}*/

int main( int argc, char ** argv )
{
    int testNum = 0;

    if ( argc < 2 ) {
        fprintf(stderr, "\n usage: %s test-num\n", argv[0]);
        return 1;
    }

   testNum = atoi(argv[1]);
   switch(testNum){
        case 1:
                test1();
                break;
        case 2:
                test2();
                break;
        case 3:
                test3();
                break;
        case 4:
                test4();
                break;
        case 5:
                test5();
                break;
        case 6:
                //test6();
                break;

        default:
                fprintf(stderr, "\n usage: %s 1 .. 8\n", argv[0]);
                 return 1;
   }
   return 0;
}

Answer 1

Я не знаю, является ли это ошибкой, но эта строка почти наверняка неверна:

  if(headRef = NULL) return 0;  //if the head is NULL, return 0 (no nodes if no head)

и должно быть

  if(headRef == NULL) return 0;  //if the head is NULL, return 0 (no nodes if no head)

Это в countNodes().

Answer 2

Здесь довольно много проблем.

Вы выделяете новые узлы, когда вас почти наверняка не должно быть, в insertHead, insertTail, findNode и deleteNode.Ни одна из этих функций не должна выделять что-либо (кроме случаев, когда вы действительно хотите скопировать узлы вызывающей стороны, что, я сомневаюсь, в этом случае вы должны размещать в insertHead и insertTail, но не в двух других, и вы должны использовать свою собственную функцию createNode для этого).Обычно я ожидал бы, например, что функция insertHead просто возьмет переданный узел и вставит его в начало списка;обычно он не выделяет новый узел и не копирует содержимое переданного узла.

Функция insertTail требует некоторой работы.Он пропускает узел каждый раз, и, я думаю, он падает, если вы добавляете в пустой список (случай, когда новый хвост - это также новая голова).Попробуйте что-то вроде:

void insertTail(struct node **head, struct node *n)
{
  struct node **tmp = head;

  while (*tmp != NULL)
  {
    tmp = &((*tmp)->next);
  }

  *tmp = n;
  n->next = NULL;
}

В countNodes у вас есть if (headRef = NULL), но это должно быть ==, а не =.

Тестирование ошибок отказов не проводится (хотя это маловероятнобыть причиной вашего segfault).

Лично я бы использовал calloc, а не malloc, чтобы ваши новые узлы имели нулевое содержимое.

Ваша функция deleteNode будет seqfault, если ее вызов findNode вернетNULL.

Я бы рекомендовал добавить некоторые утверждения, например:

void insertHead(struct node **head, struct node *n)
{
  assert(head != NULL);
  assert(n != NULL);
  assert(n->next == NULL);

  n->next = *head;
  *head = n;
}

Я бы порекомендовал добавить некоторые средства отладки, например:

void printNodes(struct node *head)
{
  int count = 0;

  while (head != NULL)
  {
    printf("Item[%d] at %p = %d\n", ++count, head, head->item);
    head = head->next;
  }
}

Answer 3

struct node* tmp = malloc(sizeof(struct node));

где бы вы ни использовали это, вы создаете ошибку, malloc в соответствии со спецификацией ANSI возвращает указатель на выделенный адрес, и вы должны вручную типизировать его в соответствии с желаемым типом,правильный синтаксис:

struct node* tmp = (struct node*)malloc(sizeof(struct node));

вы также делаете это

*tmp = *head;

вам нужно присвоить указателям НЕ фактические значения, содержащиеся в соответствующих ячейках памяти, поэтому пишите tmp=head, потому что согласнопо стандартам, * p обозначает значение местоположения, на которое указывает указатель

также плохой стиль программирования, вы выделяете память для каждой функции, вы можете создать один указатель и выделить память только один раз в основнойфункции, а затем использовать ее в своих функциях

хороший учебник по ошибкам сегментации здесь