C: Удаление узла

Я должен был написать код на основе вашего текущего кода для лучшего общение, но я подумал, что будет проще не использовать рекурсию. Не могли бы вы попробовать:

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

typedef struct LinkedNode {
    char data;
    struct LinkedNode *next;
} LinkedNode;

/*
 * append the node with data at the end of the list
 */
void append(LinkedNode *head, char data)
{
    LinkedNode *newNode = malloc(sizeof(LinkedNode));
    newNode->data = data;
    newNode->next = NULL;

    LinkedNode *temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

/*
 * dump the data of the list
 */
void dump(LinkedNode *head)
{
    for (head = head->next; head != NULL; head = head->next) {
        printf("%c ", head->data);
    }
    printf("\n");
}

/*
 * generate another list of complimentary sequence
 */
void gencomp(LinkedNode *dest, LinkedNode *src)
{
    char s_data, d_data;
    for (src = src->next; src != NULL; src = src->next) {
        s_data = src->data;
        switch(s_data) {
            case 'A':
                d_data = 'T';
                break;
            case 'T':
                d_data = 'A';
                break;
            case 'C':
                d_data = 'G';
                break;
            case 'G':
                d_data = 'C';
                break;
            default:
                fprintf(stderr, "unknown base: %c\n", s_data);
                exit(1);
        }
        append(dest, d_data);
    }
}

/*
 * return the pointer to the last element if the subsequences match
 */
LinkedNode *match(LinkedNode *head, LinkedNode *comp)
{
    for (; head != NULL; head = head->next, comp = comp->next) {
        if (head->data != comp->data) {
            return NULL;
        } else if (comp->next == NULL) {
            return head;
        }
    }
    return NULL;
}

/*
 * search "head" for "comp". If matched, the matched portion is skipped
 * (not freed)
 */
void edit(LinkedNode *head, LinkedNode *comp)
{
    LinkedNode *matched;

    for (; head != NULL; head = head->next) {
        if ((matched = match(head->next, comp->next))) {
            head->next = matched->next;         // skip matched sequence
        }
    }
}

int main()
{
    char dna_orig[] = "ACGTAGACGTTCTA";
    char dna_bond[] = "GCA";
    int i;

    // generate list of original sequence
    LinkedNode *head = malloc(sizeof(LinkedNode));
    head->next = NULL;
    for (i = 0; dna_orig[i] != 0; i++) {
        append(head, dna_orig[i]);
    }

    // generate list of bonding sequence
    LinkedNode *bond = malloc(sizeof(LinkedNode));
    bond->next = NULL;
    for (i = 0; dna_bond[i] != 0; i++) {
        append(bond, dna_bond[i]);
    }

    // generate list of complementary sequence of bond
    LinkedNode *comp = malloc(sizeof(LinkedNode));
    comp->next = NULL;
    gencomp(comp, bond);

    // edit the original sequence and see the result
    edit(head, comp);
    dump(head);

    return 0;
}

Выход:

A A G A T C T A 

• Я создал список комплементарной последовательности связующей последовательности чтобы облегчить поиск.
• Код пока неэффективен, так как использует повторный линейный поиск в списке.
• Мне пришлось включить <stdio.h> для печати.

[Редактировать]
При освобождении пропущенных узлов мы не можем освободить их в прямом порядке от головы к хвосту, потому что связь со следующим узлом теряется, как только первый узел освобождается. Затем мы можем использовать рекурсия, чтобы освободить их. в обратном порядке. Вот функция для освобождения пропущенных узлов:

void freenodes(LinkedNode *head, LinkedNode *tail)
{
    if (head->next == tail) {                   // the last node to remove
        free(head);
        return;
    }
    freenodes(head->next, tail);                // free nodes recursively
    free(head);
}

Первый аргумент функции продвигается один за другим, пока не достигнет последний узел совпадающей последовательности. Затем функция возвращается к вызывающей стороне вернуться к первому узлу совпадающей последовательности, освобождая при этом узлы. Вот обновленный полный код, включая модификацию функции edit. чтобы вернуть голову редактируемого списка.

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

typedef struct LinkedNode {
    char data;
    struct LinkedNode *next;
} LinkedNode;

/*
 * append the node with data at the end of the list
 */
void append(LinkedNode *head, char data)
{
    LinkedNode *newNode = malloc(sizeof(LinkedNode));
    newNode->data = data;
    newNode->next = NULL;

    LinkedNode *temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

/*
 * dump the data of the list
 */
void dump(LinkedNode *head)
{
    for (head = head->next; head != NULL; head = head->next) {
        printf("%c ", head->data);
    }
    printf("\n");
}

/*
 * compare characters complementarily
 * return 1 for matching pairs as A<=>T or C<=>G
 */
int compcomp(char a, char b)
{
    if ((a == 'A' && b == 'T') || (a == 'T' && b == 'A')
        || (a == 'C' && b == 'G') || (a == 'G' && b == 'C'))
        return 1;
    else
        return 0;
}

/*
 * return the pointer to the last node if the subsequences match complementarily
 */
LinkedNode *match(LinkedNode *head, LinkedNode *bond)
{
    for (; head != NULL; head = head->next, bond = bond->next) {
        if (! compcomp(head->data, bond->data)) {
            return NULL;
        } else if (bond->next == NULL) {
            return head;
        }
    }
    return NULL;
}

/*
 * free skipped nodes
 */
void freenodes(LinkedNode *head, LinkedNode *tail)
{
    if (head->next == tail) {                   // the last node to remove
        // printf("> %c\n", head->data);        // for debugging
        free(head);
        return;
    }
    freenodes(head->next, tail);                // free nodes recursively
    // printf("> %c\n", head->data);            // for debugging
    free(head);
}

/*
 * search "head" for the sequence of complementary of "bond". If matched,
 * the matched portion is skipped and skipped nodes are freed
 */
LinkedNode *edit(LinkedNode *head, LinkedNode *bond)
{
    LinkedNode *matched;                        // last node of matched sequence
    LinkedNode *matchednext;
    LinkedNode *tmp;                            // copy of head to traverse the list

    for (tmp = head; tmp != NULL; tmp = tmp->next) {
        if ((matched = match(tmp->next, bond->next))) {
            matchednext = matched->next;        // backup matched->next
            freenodes(tmp->next, matched->next);
            tmp->next = matchednext;            // skip matched sequence
        }
    }

    return head;
}

int main()
{
    char dna_orig[] = "ACGTAGACGTTCTA";
    char dna_bond[] = "GCA";
    int i;

    // generate list of original sequence
    LinkedNode *head = malloc(sizeof(LinkedNode));
    head->next = NULL;
    for (i = 0; dna_orig[i] != 0; i++) {
        append(head, dna_orig[i]);
    }

    // generate list of bonding sequence
    LinkedNode *bond = malloc(sizeof(LinkedNode));
    bond->next = NULL;
    for (i = 0; dna_bond[i] != 0; i++) {
        append(bond, dna_bond[i]);
    }

    // edit the original sequence and see the result
    dump(edit(head, bond));

    return 0;
}

Кстати, вы можете опустить #include <stdio.h>, отбросив функции printf() и fprintf(), которые используются только для целей отчетности.

[EDIT2]
Основное различие между вашим кодом и моим заключается в структуре данных связанный список. head моего списка имеет пустые данные и является вход к первому узлу, в то время как ваш dna_original напрямую начинается с узла который содержит данные. То же самое с bond и sequencia. У обоих есть свои преимущества, но мы не можем их смешивать. Тогда, пожалуйста, измените свой editar_dna как:

LinkedNode *editar_dna(LinkedNode *dna_original, LinkedNode *seq_edicao){
    LinkedNode *matched, *matchednext, *tmp;

    for (tmp = dna_original; tmp != NULL; tmp = tmp->next) {
        if ((matched = match(tmp->next, seq_edicao))) {
            matchednext = matched->next;
            liberar_nos(tmp->next, matched->next);
            tmp->next = matchednext;
        }
    }

    return dna_original;
}

изменение seq_edicao->next на seq_edicao в функции match(). Затем он выведет A A A.
Потенциальная проблема вашей структуры данных заключается в том, что мы не можем удалить начальная подпоследовательность, такая как: "CGTACGTA". это технически можно исправить, но могут потребоваться дополнительные огромные модификации.

Теперь у вас есть три варианта:

1. Пренебрегайте пограничным случаем, начинающимся с совпадающей подпоследовательности.
2. Измените структуру связанного списка (просто, но я не уверен, что это приемлемо).
3. Найдите контрмеру, сохраняющую текущую структуру данных.

Тебе решать. :)

[EDIT3]
Вот версия, применяющая вариант 3 (без изменения основного) к вашему коду (к вашему сведению):

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

typedef struct LinkedNode LinkedNode;
struct LinkedNode {
   char data;
   LinkedNode *next;
};

void imprimir1(LinkedNode *inicio){
    if (inicio == NULL){
    return;
    }

    printf("%c", inicio->data);
    if (inicio->next!=NULL) printf(" ");
    else printf("\n");
    imprimir1(inicio->next);
    return;
}

void liberar_lista(LinkedNode *inicio){
    if (inicio == NULL) return;
    liberar_lista(inicio->next);
    free(inicio);
}

LinkedNode *inserir_final_r(LinkedNode *inicio, char valor) {
    if (inicio == NULL) {
        LinkedNode *novo = malloc(sizeof(LinkedNode));
        if (novo == NULL) return inicio;
        novo->data = valor;
        novo->next = NULL;
        return novo;
    }
    inicio->next = inserir_final_r(inicio->next, valor);
    return inicio;
}

void liberar_nos(LinkedNode *head, LinkedNode *tail) {
    if (head == tail) {
        return;
    }
    liberar_nos(head->next, tail);
    free(head);
}

int compare(char a, char b) {
    if ((a == 'A' && b == 'T') || (a == 'T' && b == 'A')
        || (a == 'C' && b == 'G') || (a == 'G' && b == 'C'))
        return 1;
    else
        return 0;
}

LinkedNode *match(LinkedNode *head, LinkedNode *bond) {
    for (; head != NULL; head = head->next, bond = bond->next) {
        if (! compare(head->data, bond->data)) {
            return NULL;
        } else if (bond->next == NULL) {
            return head;
        }
    }
    return NULL;
}

LinkedNode *editar_dna(LinkedNode *dna_original, LinkedNode *seq_edicao){
    LinkedNode *matched, *matchednext, *tmp;

    // remove leading matched subsequence(s) as a preproces
    while ((matched = match(dna_original, seq_edicao))) {
        matchednext = matched->next;
        liberar_nos(dna_original->next, matched->next); // note we cannot free the 1st node
        dna_original->data = matchednext->data;
        dna_original->next = matchednext->next;
        liberar_nos(matchednext, matchednext->next);    // free the copied node which is no longer used
    }
/*
    for (tmp = dna_original; tmp != NULL; tmp = tmp->next) {
        if ((matched = match(tmp->next, seq_edicao))) {
            matchednext = matched->next;
            liberar_nos(tmp->next, matched->next);
            tmp->next = matchednext;
        }
    }
*/
    for (tmp = dna_original; tmp != NULL; ) {
        if ((matched = match(tmp->next, seq_edicao))) {
            matchednext = matched->next;
            liberar_nos(tmp->next, matched->next);
            tmp->next = matchednext;                    // skip matched sequence
        } else {
            tmp = tmp->next;                            // proceed to next node
        }
    }

    return dna_original;
}

int main(){

    //Creating empty nodes
    LinkedNode *dna_original = NULL;
    LinkedNode *sequencia = NULL;

    //Populating test data into the original sequence
//    dna_original = inserir_final_r(dna_original, 'A');        // dropped just for the test
    dna_original = inserir_final_r(dna_original, 'C');
    dna_original = inserir_final_r(dna_original, 'G');
    dna_original = inserir_final_r(dna_original, 'T');
    dna_original = inserir_final_r(dna_original, 'C');
    dna_original = inserir_final_r(dna_original, 'G');
    dna_original = inserir_final_r(dna_original, 'T');
    dna_original = inserir_final_r(dna_original, 'A');
    dna_original = inserir_final_r(dna_original, 'C');
    dna_original = inserir_final_r(dna_original, 'G');
    dna_original = inserir_final_r(dna_original, 'T');
    dna_original = inserir_final_r(dna_original, 'A');

    //Populating test data into the second sequence
    sequencia = inserir_final_r(sequencia, 'G');
    sequencia = inserir_final_r(sequencia, 'C');
    sequencia = inserir_final_r(sequencia, 'A');

    //Printing the original sequence before change
    imprimir1(dna_original);

    //Changing the sequence
    editar_dna(dna_original, sequencia);

    //Printing the original sequence after change
    imprimir1(dna_original);

    //Freeing allocated memory
    liberar_lista(dna_original);
    liberar_lista(sequencia);

    return 0;
}

Обратите внимание, что инициализация списка в main() изменена для целей отладки и демонстрации.

Из заголовка и обсуждения я предполагаю, что применение редактирования должно изменить входной список, удалив совпадающие подпоследовательности. Если первый узел списка удален, вам нужно будет вернуть указатель на какой-нибудь более поздний узел. В противном случае возвращается первый узел.

Наивный способ справиться с этими двумя случаями — это специальные проверки. Но есть хорошо известный шаблон обработки обоих случаев как одного. Это предварительно ожидает «фиктивный» головной узел, который никогда не удаляется. Вместо того, чтобы пытаться объяснить дальше, я добавлю код. Смотрите apply_edit.

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

typedef struct node_s {
  struct node_s *next;
  char base;
} Node;

void print(Node *seq) {
  for (Node *p = seq; p; p = p->next) printf("%c", p->base);
  printf("\n");
}

bool base_match(char x, char y) {
  switch (x) {
    case 'A': return y == 'T';
    case 'C': return y == 'G';
    case 'G': return y == 'C';
    case 'T': return y == 'A';
  }
  exit(42); // input error
}

// If the prefix of seq is as given, return the following seq node, else seq.
Node *remove_prefix(Node *prefix, Node *seq) {
  Node *p, *s;
  for (p = prefix, s = seq; p && s; p = p->next, s = s->next)
    if (!base_match(p->base, s->base))
      return seq;
  return p ? seq : s;
}

Node *apply_edit(Node *edit, Node *seq) {
  Node head[1] = {{ seq }};
  for (Node *p = head; p && p->next; ) {
    Node *next = remove_prefix(edit, p->next);
    if (next == p->next) p = next;  // No match; advance one.
    else p->next = next;  // Remove the match; don't advance.
  }
  return head->next;
}

Node *build_seq(char *gene) {
  Node *seq = NULL;
  for (int i = strlen(gene) - 1; i >= 0; --i) {
    Node *node = malloc(sizeof *node);
    node->base = gene[i];
    node->next = seq;
    seq = node;
  }
  return seq;
}

int main(void) {
  // Provided test case. Expect AAGATCTA.
  print(apply_edit(build_seq("GCA"), build_seq("ACGTAGACGTTCTA")));
  // Remove from head. Expect A.
  print(apply_edit(build_seq("GCA"), build_seq("CGTA")));
  // Remove from tail. Expect A.
  print(apply_edit(build_seq("GCA"), build_seq("ACGT")));
  // Incomplete match at tail. Expect ACG
  print(apply_edit(build_seq("GCA"), build_seq("ACG")));
  // Remove all. Expect empty string.
  print(apply_edit(build_seq("GCA"), build_seq("CGTCGT")));
  // Remove creates new match, which is ignored. Expect CGT.
  print(apply_edit(build_seq("GCA"), build_seq("CCGTGT")));

  return 0;
}

Хотя это усложняет чтение кода, вы можете встроить вспомогательную функцию в то место, где она вызывается в apply_edit, и получить что-то очень лаконичное:

Node *apply_edit(Node *edit, Node *seq) {
  Node *e, *s, head[1] = {{ seq }};
  for (Node *p = head; p && p->next; ) {
    for (e = edit, s = p->next; e && s; e = e->next, s = s->next)
      if (!base_match(e->base, s->base)) break;
    if (e) p = s;  // No match; advance one.
    else p->next = s;  // Remove the match; don't advance.
  }
  return head->next;
}

Я также укажу, что обход списков с помощью рекурсии — это то, что вы не стали бы делать в производственном коде. Хотя хороший компилятор с включенными оптимизациями преобразует хвостовую рекурсию (например, вашу) в итерацию, это может быть привередливая оптимизация ... поскольку компилятор пропустит ее при неочевидных обстоятельствах. Если это произойдет, вашей программе потребуется пространство стека, пропорциональное длине списков, которые вы просматриваете, в то время как итеративный код будет нормально работать в одном кадре стека. Это очень важно, если ваша программа должна быть надежной.