论坛 › 新手乐园 › 自己写的链表有点问题

w349695434051 发表于 2023-10-26 18:49:57

自己写的链表有点问题

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

typedef struct _node{                                                                        //定义链表节点
      int value;                                                                                        //每个节点中包含两个元素 他存储的值value 还有便于检索的下标index
      int index;
      struct _node* next;
}Node;

typedef struct _list{                                                                        //定义链表
      int number;                                                                                        //每个链表包含number 代表他一共含有几个节点
      Node* head;                                                                                        //链表的头
      Node* tail;                                                                                        //链表的tail 指向链表最后一个节点 用来延长链表的
}List;

Node* list_add(List* list, int number);                                        //定义链表延长函数
int list_print(List *list);                                                                //链表输出节点的值的函数
Node* list_at(List* list, int index);                                        //根据下标定位节点的函数
Node* list_insert(List* list, int index, int number);      //再链表中插入结点的函数
int list_retrieval(List* list);                                                      //插入或者删除节点后 对链表节点重新排下标的函数
int list_delete(List* list, int index);                                        //输出链表结点的函数
Node* list_found(List* list, int number);                              //根据链表的值输出节点地址的函数
void list_free(List* list);                                                                //free链表的函数

Node* list_add(List* list, int number)
{
      Node* p = (Node*)malloc(sizeof(Node));
      p -> value = number;
      p -> next = NULL;
      if(list -> head)                                                                        //判断链表是否为空链表
      {                                                                                                
                list -> tail -> next = p;                                                //不是的话让指向最后一个节点的tail的next指向新定义的节点
                p -> index = list -> tail -> index + 1;                        //他的下标就是最后节点下标加一
                list -> number++;                                                                //链表节点数量加一
      }else                                                                                                      
      {                                                                                                      //链表是空链表
                list -> head = p;                                                                //链表头指向新定义的节点
                p -> index = 0;                                                                        //下标为零
                list -> number = 1;                                                                //节点数量初始化为一
      }
      list -> tail = p;                                                                        //最后让tail指向新定义的节点 作为链表最后一个节点
}

int list_print(List *list)
{
      int ret = 0;
      if(list -> head)                                                                        //打印函数 如果为空链表不调用函数返回值为零
      {
                ret = 1;
                Node *p = NULL;
                for(p = list -> head; p; p = p -> next)
                {
                        printf("%d", p -> value);
                        if(p -> next)                                                                //链表除了最后一个节点都打印一个tab
                              printf("\t");
                }
                printf("\n");
      }
      return ret;
}

Node* list_at(List* list, int index)
{
      Node* p = NULL;
      if(index < list -> number && index >= 0)                        //输入有效下表进入函数 否则返回零地址
                for(p = list -> head; p; p = p -> next)
                        if(p -> index == index)
                              break;
      return p;
}

Node* list_insert(List* list, int index, int number)      //链表插入函数
{
      Node* p = NULL;
      
      if(index <= list -> number && index >= 0)                        //判断述如下表是否有效
      {
                p = (Node*)malloc(sizeof(Node));
                p -> value = number;
                p -> next = NULL;
               
                if(index <= list -> number && index)                        //当插入的位置 不为第一个时
                        list_at(list, index - 1) -> next = p;                //调用取址函数让插入的前一个节点指向新插入的节点
                else if(index == 0)                                                                //当插入位置 为第一个时
                        list -> head = p;                                                      //链表头指向新节点
                        
                if(index == list -> number)                                                //当插入位置为最后一个 相当于延长了一个节点
                        p -> next = NULL;                                                      //新节点next指向null
                else
                        p -> next = list_at(list, index);                        //否则的话 next指向被插入的节点
                        
                list_retrieval(list);                                                      //调用排序函数对链表下标在排序
      }
}

int list_retrieval(List* list)
{
      int ret = 0;
      int reindex = 0;
      Node* rep = NULL;
      if(list -> head)
      {
                ret = 1;
                for(rep = list -> head; rep ！= NULL; rep = rep -> next)                //重点就是这个排序函数 进到for循环之后就死循环了 但我看着也没有问题啊 ！！
                {
                        int a;
                        rep -> index = reindex++;
                }
      }
      return ret;
}

int list_delete(List* list, int index)                                                //节点删除函数
{
      int ret = 0;
      if(list -> head && list -> number > index && index >= 0)      //如果链表为空链表并且下标无效的话不调用函数
      {
                ret = 1;
                Node* p = NULL;
                if(index > 0)                                                                              //删除的节点不是第一个节点
                        list_at(list, index - 1) -> next =list_at(list, index)-> next;      //调用取址函数
                else
                        list -> head = list_at(list, index) -> next;      //删除的是第一个节点
                free(p);
                list_retrieval(list);                                                                              //对删除之后的链表下标排序
      }
      return ret;
}

Node* list_found(List* list, int number)                                        //根据链表的值输出节点地址的函数
{
      Node* p = NULL;
      for(p = list -> head; p; p = p -> next)
                if(p -> value == number)
                        break;
      return p;
}

void list_free(List* list)                                                                        //free链表的函数
{
      Node* p = list -> head;
      Node* q = NULL;
      while(p)
      {
                q = p -> next;
                free(p);
                p = q;
      }
}

int main()
{
      List list;
      list.head = NULL;
      list.tail = NULL;
      
      list_add(&list, 1);
      list_add(&list, 2);
      list_add(&list, 3);
      
      list_print(&list);
      
      list_insert(&list, 0, 4);
      list_insert(&list, 4, 5);
      
      list_delete(&list, 0);
      list_print(&list);
      list_delete(&list, 1);
      list_print(&list);
      list_delete(&list, 0);
      list_print(&list);
      
      list_print(&list);
      
      list_free(&list);
      
      return 0;
}
调用insert函数还有delete函数
进入retrieval的for语句就死循环了
链表这几天刚学的
求大佬指点一下
我看着逻辑没啥问题但怎么改都是死循环
真是要崩溃了
求助

小甲鱼的二师兄 发表于 2023-12-1 05:31:41

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

typedef struct _node{                                                                        //定义链表节点
      int value;                                                                                        //每个节点中包含两个元素 他存储的值value 还有便于检索的下标index
      int index;
      struct _node* next;
}Node;

typedef struct _list{                                                                        //定义链表
      int number;                                                                                        //每个链表包含number 代表他一共含有几个节点
      Node* head;                                                                                        //链表的头
      Node* tail;                                                                                        //链表的tail 指向链表最后一个节点 用来延长链表的
}List;

Node* list_add(List* list, int number);                                        //定义链表延长函数
int list_print(List *list);                                                                //链表输出节点的值的函数
Node* list_at(List* list, int index);                                        //根据下标定位节点的函数
Node* list_insert(List* list, int index, int number);      //再链表中插入结点的函数
int list_retrieval(List* list);                                                      //插入或者删除节点后 对链表节点重新排下标的函数
int list_delete(List* list, int index);                                        //输出链表结点的函数
Node* list_found(List* list, int number);                              //根据链表的值输出节点地址的函数
void list_free(List* list);                                                                //free链表的函数

Node* list_add(List* list, int number)
{
      Node* p = (Node*)malloc(sizeof(Node));
      p -> value = number;
      p -> next = NULL;
      if(list -> head)                                                                        //判断链表是否为空链表
      {                                                                                                
                list -> tail -> next = p;                                                //不是的话让指向最后一个节点的tail的next指向新定义的节点
                p -> index = list -> tail -> index + 1;                        //他的下标就是最后节点下标加一
                list -> number++;                                                                //链表节点数量加一
      }else                                                                                                      
      {                                                                                                      //链表是空链表
                list -> head = p;                                                                //链表头指向新定义的节点
                p -> index = 0;                                                                        //下标为零
                list -> number = 1;                                                                //节点数量初始化为一
      }
      list -> tail = p;                                                                        //最后让tail指向新定义的节点 作为链表最后一个节点
}

int list_print(List *list)
{
      int ret = 0;
      if(list -> head)                                                                        //打印函数 如果为空链表不调用函数返回值为零
      {
                ret = 1;
                Node *p = NULL;
                for(p = list -> head; p; p = p -> next)
                {
                        printf("%d", p -> value);
                        if(p -> next)                                                                //链表除了最后一个节点都打印一个tab
                              printf("\t");
                }
                printf("\n");
      }
      return ret;
}

Node* list_at(List* list, int index)
{
      Node* p = NULL;
      if(index < list -> number && index >= 0)                        //输入有效下表进入函数 否则返回零地址
                for(p = list -> head; p; p = p -> next)
                        if(p -> index == index)
                              break;
      return p;
}

Node* list_insert(List* list, int index, int number)      //链表插入函数
{
      Node* p = NULL;
      
      if(index <= list -> number && index >= 0)                        //判断述如下表是否有效
      {
                p = (Node*)malloc(sizeof(Node));
                p -> value = number;
                p -> next = NULL;
               
                if(index <= list -> number && index)                        //当插入的位置 不为第一个时
                        list_at(list, index - 1) -> next = p;                //调用取址函数让插入的前一个节点指向新插入的节点
                else if(index == 0)                                                                //当插入位置 为第一个时
                        list -> head = p;                                                      //链表头指向新节点
                        
                if(index == list -> number)                                                //当插入位置为最后一个 相当于延长了一个节点
                        p -> next = NULL;                                                      //新节点next指向null
                else
                        p -> next = list_at(list, index);                        //否则的话 next指向被插入的节点
                        
                list_retrieval(list);                                                      //调用排序函数对链表下标在排序
      }
}

int list_retrieval(List* list)
{
      int ret = 0;
      int reindex = 0;
      Node* rep = NULL;
      if(list -> head)
      {
                ret = 1;
                for(rep = list -> head; rep ！= NULL; rep = rep -> next)                //重点就是这个排序函数 进到for循环之后就死循环了 但我看着也没有问题啊 ！！
                {
                        int a;
                        rep -> index = reindex++;
                }
      }
      return ret;
}

int list_delete(List* list, int index)                                                //节点删除函数
{
      int ret = 0;
      if(list -> head && list -> number > index && index >= 0)      //如果链表为空链表并且下标无效的话不调用函数
      {
                ret = 1;
                Node* p = NULL;
                if(index > 0)                                                                              //删除的节点不是第一个节点
                        list_at(list, index - 1) -> next =list_at(list, index)-> next;      //调用取址函数
                else
                        list -> head = list_at(list, index) -> next;      //删除的是第一个节点
                free(p);
                list_retrieval(list);                                                                              //对删除之后的链表下标排序
      }
      return ret;
}

Node* list_found(List* list, int number)                                        //根据链表的值输出节点地址的函数
{
      Node* p = NULL;
      for(p = list -> head; p; p = p -> next)
                if(p -> value == number)
                        break;
      return p;
}

void list_free(List* list)                                                                        //free链表的函数
{
      Node* p = list -> head;
      Node* q = NULL;
      while(p)
      {
                q = p -> next;
                free(p);
                p = q;
      }
}

int main()
{
      List list;
      list.head = NULL;
      list.tail = NULL;
      
      list_add(&list, 1);
      list_add(&list, 2);
      list_add(&list, 3);
      
      list_print(&list);
      
      list_insert(&list, 0, 4);
      list_insert(&list, 4, 5);
      
      list_delete(&list, 0);
      list_print(&list);
      list_delete(&list, 1);
      list_print(&list);
      list_delete(&list, 0);
      list_print(&list);
      
      list_print(&list);
      
      list_free(&list);
      
      return 0;
}
调用insert函数还有delete函数
进入retrieval的for语句就死循环了
@FishC_GPT

FishC_GPT 发表于 2023-12-1 05:32:16

小甲鱼的二师兄 发表于 2023-12-01 05:31
#include
#include

typedef struct _node{      ...

你的代码中，在排序函数 `list_retrieval()` 的 for 循环中，有一个问题导致了死循环。问题出在循环条件上（`rep ！= NULL`），你使用了中文的感叹号，但实际应该使用英文的感叹号 `!=` 。

修复这个问题后，可以将循环条件修改为 `rep != NULL`，就可以避免死循环了。这样，每次循环时，`rep` 都会指向下一个节点，直到链表末尾为止。

同时，我还注意到你在删除节点的代码中，没有正确释放内存。在 `list_delete()` 函数中，你定义了一个指针 `p` 来指向要删除的节点，但在释放内存之前，你没有将 `p` 更新为要删除节点的下一个节点，导致内存泄漏。

以下是修改后的代码：

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

typedef struct _node {
    int value;
    int index;
    struct _node* next;
} Node;

typedef struct _list {
    int number;
    Node* head;
    Node* tail;
} List;

Node* list_add(List* list, int number);
int list_print(List *list);
Node* list_at(List* list, int index);
Node* list_insert(List* list, int index, int number);
int list_retrieval(List* list);
int list_delete(List* list, int index);
Node* list_found(List* list, int number);
void list_free(List* list);

Node* list_add(List* list, int number) {
    Node* p = (Node*)malloc(sizeof(Node));
    p->value = number;
    p->next = NULL;

    if (list->head) {
      list->tail->next = p;
      p->index = list->tail->index + 1;
      list->number++;
    } else {
      list->head = p;
      p->index = 0;
      list->number = 1;
    }

    list->tail = p;
    return p;
}

int list_print(List *list) {
    if (!list->head) {
      return 0;
    }

    Node *p = NULL;
    for (p = list->head; p; p = p->next) {
      printf("%d", p->value);
      if (p->next) {
            printf("\t");
      }
    }
    printf("\n");

    return 1;
}

Node* list_at(List* list, int index) {
    Node* p = NULL;
    if (index < list->number && index >= 0) {
      for (p = list->head; p; p = p->next) {
            if (p->index == index) {
                break;
            }
      }
    }
    return p;
}

Node* list_insert(List* list, int index, int number) {
    if (index < 0 || index > list->number) {
      return NULL; // 非法的下标
    }

    Node* p = (Node*)malloc(sizeof(Node));
    p->value = number;

    if (index == 0) {
      p->next = list->head;
      list->head = p;
      if (list->number == 0) {
            list->tail = p;
      }
    } else {
      Node* prev = list_at(list, index-1);
      p->next = prev->next;
      prev->next = p;
      if (index == list->number) {
            list->tail = p;
      }
    }

    list_retrieval(list);
    return p;
}

int list_retrieval(List* list) {
    if (!list->head) {
      return 0;
    }

    int reindex = 0;
    Node* rep = NULL;
    for (rep = list->head; rep != NULL; rep = rep->next) {
      rep->index = reindex++;
    }
    return 1;
}

int list_delete(List* list, int index) {
    if (!list->head || index < 0 || index >= list->number) {
      return 0;
    }

    Node* p = NULL;
    if (index == 0) {
      p = list->head;
      list->head = list->head->next;
      if (list->number == 1) {
            list->tail = NULL;
      }
    } else {
      Node* prev = list_at(list, index-1);
      p = prev->next;
      prev->next = p->next;
      if (index == list->number - 1) {
            list->tail = prev;
      }
    }

    free(p);
    list_retrieval(list);
    return 1;
}

Node* list_found(List* list, int number) {
    Node* p = NULL;
    for (p = list->head; p; p = p->next) {
      if (p->value == number) {
            break;
      }
    }
    return p;
}

void list_free(List* list) {
    Node* p = list->head;
    Node* q = NULL;
    while (p) {
      q = p->next;
      free(p);
      p = q;
    }
}

int main() {
    List list;
    list.head = NULL;
    list.tail = NULL;
   
    list_add(&list, 1);
    list_add(&list, 2);
    list_add(&list, 3);

    list_print(&list);
   
    list_insert(&list, 0, 4);
    list_insert(&list, 4, 5);
   
    list_delete(&list, 0);
    list_print(&list);

    list_delete(&list, 1);
    list_print(&list);

    list_delete(&list, 0);
    list_print(&list);

    list_free(&list);

    return 0;
}

现在，你的插入和删除操作应该能够正常运行，并且循环也会正确退出。希望这对你有帮助！如果还有其他问题，请随时提问。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

查看完整版本: 自己写的链表有点问题