c : Free function

Question

当我想删除列表(释放内存)时遇到问题。如果是序列，则代码是列表的快捷方式。数列=相同的数字，最多三个数字相等。找到序列后返回新的长度

示例:

Before: 3,3,3,3,2
After: -4,3,2
New length : 3

我编写的代码给出了良好的结果，但是当我使用 Delete_List 函数时，程序崩溃了。

node *Find_Sequence(node *L) {
    node *headSeq = NULL, *tailSeq = NULL, *currL = L;
    int flag = 0, cnt = 3;
    while (currL != NULL) {
        if (currL->next != NULL && currL->data == currL->next->data) {
            if (currL->next->data == currL->next->next->data) {
                flag = 1; // if flag = 1 it means that have a sequence, 
                          // sequence: same number up and equal to 3.
                headSeq = currL;
                tailSeq = currL->next->next;
                break;
            }   
        }
        currL = currL->next;
    }

    while (tailSeq != NULL) { // to find if hace more then 3 in the sequence and to know how many nodes to delete
        if (tailSeq->next != NULL && tailSeq->data == tailSeq->next->data)
            cnt++;
        else {
            //tailSeq->next = NULL;
            break;
        }
        tailSeq = tailSeq->next;
    }

    if (headSeq != NULL) {
        headSeq = Delete_Node(headSeq, tailSeq, cnt - 2);  // cnt-2 because i want to stay a place for the head(-k) and for the tail (x)
        headSeq->data = -1 * cnt;
        if (headSeq != NULL)
            headSeq = tailSeq;
    }
    return L;
}

node *Delete_Node(node *head, node *tail, int length) {
    node *h = head, *t = tail, *curr = head, *temp = NULL;
    int i;

    for (i = 0; i < length; i++) {
        temp = h;
        h = h->next;
        free(temp);
    }

    if (head != NULL)
        head->next = tail;

    return head;
}

int new_length(node *L) {
    node *new_list = Find_Sequence(L);
    int counter = 0;
    while (new_list != NULL) {
        counter++;
        new_list = new_list->next;
    }
    return counter;
}

node *Delete_List(node *L) {
    node *next;
    while (L != NULL) {
        next = L;
        L = L->next;
        free(next);
    }
    return L;
}

int main() {
    node *list1 = NULLL;   // empty lists
    int len;

    list1 = Creat_List(list1, 3);
    list1 = Creat_List(list1, 3);
    list1 = Creat_List(list1, 3);
    list1 = Creat_List(list1, 5);
    list1 = Creat_List(list1, 4);

    printf("Before:");
    Print_List(list1);
    len = new_length(list1);
    printf("The new length is: %d\n", len);
    printf("After:");
    Print_List(list1);
    printf("\n");

    Delete_List(list1);
}

Answer 1

问题(1)

Delete_Node 返回已经释放的节点作为head。
例如，更改为保留第一个元素，如下所示。

node *Delete_Node(node * head, node * tail , int length){
    node *h = head->next, *temp;
    int i;

    for (i = 0; h &&  i < length; i++){
        temp = h;
        h = h->next;
        free(temp);
    }

    head->next = tail;

    return head;
}

问题(2)

在Find_Sequence if (currL->next->data == currL->next->next->data)
currL->next->next 不能保证它不是 NULL。
此外，仅处理最先找到的列表。
简化后写成如下。

试试这个:

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

typedef struct node {
    int data;
    struct node *next;
} node;

node *Creat_List(node *L, int value){
    node *current = L , *new_node = malloc(sizeof(node));
    new_node->data = value;
    new_node->next = NULL;

    if (L == NULL) {
        L = new_node;
    } else {
        while (current->next != NULL)
            current = current->next;
        current = current->next = new_node;
    }
    return L;
}

node *Delete_Node(node *head, node *end){
    //top node not delete
    node *curr = head->next;

    while(curr != end){
        node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    head->next = end;

    return head;
}

int sameLength(node *L, node **next){
    node *curr = L;
    int count = 0;
    while(curr && curr->data == L->data){
        ++count;
        curr = curr->next;
    }
    *next = curr;
    return count;
}

node *Find_Sequence(node *L){
    node *curr = L, *next = NULL;
    int cnt;

    while (curr){
        cnt = sameLength(curr, &next);
        if(cnt > 2){
            Delete_Node(curr->next, next);//Leave curr->next
            curr->data = -cnt;
        }
        curr = next;
    }

    return L;
}

int new_length(node *L){
    node *new_list = Find_Sequence(L);
    int counter = 0;
    while (new_list){
        counter++;
        new_list = new_list->next;
    }

    return counter;
}

node *Delete_List(node * L){
    node *temp;
    while (L != NULL){
        temp = L;
        L = L->next;
        free(temp);
    }

    return NULL;
}

void Print_List(node * head){
    while (head != NULL){
        printf("%4d", head->data);
        head = head->next;
    }
}

int main(void){
    node *list1=NULL, *list2=NULL , *list3=NULL;
    int len;
    list1 = Creat_List(list1, 3);
    list1 = Creat_List(list1, 3);
    list1 = Creat_List(list1, 3);
    list1 = Creat_List(list1, 5);
    list1 = Creat_List(list1, 4);

    printf("Before:");
    Print_List(list1);
    len = new_length(list1);
    printf("\nThe new length is: %d\n", len);
    printf("After:");
    Print_List(list1);
    printf("\n");
    Delete_List(list1);

    list2 = Creat_List(list2, 2);
    list2 = Creat_List(list2, 3);
    list2 = Creat_List(list2, 3);
    list2 = Creat_List(list2, 3);
    list2 = Creat_List(list2, 3);
    list2 = Creat_List(list2, 4);

    printf("Before:");
    Print_List(list2);
    len = new_length(list2);
    printf("\nThe new length is: %d\n", len);
    printf("After:");
    Print_List(list2);
    printf("\n");

    list3 = Creat_List(list3, 3);
    list3 = Creat_List(list3, 3);
    list3 = Creat_List(list3, 5);
    list3 = Creat_List(list3, 5);
    list3 = Creat_List(list3, 5);
    list3 = Creat_List(list3, 5);
    list3 = Creat_List(list3, 5);

    printf("Before:");
    Print_List(list3);
    len = new_length(list3);
    printf("\nThe new length is: %d\n", len);
    printf("After:");
    Print_List(list3);
    printf("\n");
}