Если я понимаю, что вы хотите удалить узел k th из двусвязного кругового связанного списка, то, как показано в вашем вопросе, например, если список содержал:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
С k=2 вы хотите удалить 2, 4, 6, 8, 10, 3, ..., пока список не станет пустым. Это что-то вроде проблемы из двух частей. (1) удалить узел k th и (2) увеличить позицию k th , чтобы она теперь указывала на узел k th после того, который вы только что удалил. Это может быть реализовано несколькими способами. Вероятно, наиболее прагматичным является c - реализовать функцию удаления узла k th , а затем написать функцию-обертку, если необходимо обновить счетчик, чтобы он удалял следующий узел в последовательности.
С указателем на указатель на узел 1 st в списке l и узлом k th , который нужно удалить, вы можете сделать что-то похожее на:
/** delete kth node in doubly-linked circular list from node *l
* returns pointer to new node at address of deleted node or NULL if
* list now empty.
*/
node_t *delkthnode (node_t **l, size_t kth)
{
node_t **ppn = l, /* pointer to pointer to node */
*pn = *l; /* pointer to node */
size_t n = kth ? kth - 1 : 1; /* set no. to advance (1-based index) */
if (pn == pn->next) { /* last node left in list? */
free (pn); /* free node */
return *ppn = NULL; /* set address for node to NULL */
}
while (n--) { /* loop to kth node */
ppn = &pn->next; /* update current address to next */
pn = pn->next; /* update current node to next */
}
*ppn = pn->next; /* set current address to next node */
(*ppn)->prev = pn->prev; /* set current->prev to next->prev */
if (pn->next == *l) /* deleting tail node? */
(*ppn)->prev->next = *l; /* set new end->next to head */
if (pn == *l) /* if current node is head */
*l = *ppn; /* update list adddress to current */
free (pn); /* free node memory */
return *ppn; /* return pointer to new node at address of removed node */
}
( примечание: вышеизложенное использует и указатель на узел, и адрес текущего указателя для итерации и замены узла по адресу, который должен быть удален, следующим узлом в список см. Линус о понимании указателей )
Полу-короткий пример реализации, который проверяет лог c, может быть:
#include <stdio.h>
#include <stdlib.h>
#ifndef NNODES
#define NNODES 10
#endif
typedef struct node_t { /* list node */
int data;
struct node_t *prev, *next;
} node_t;
/** create new node initialize all members */
node_t *createnode (int v)
{
node_t *node = malloc (sizeof *node); /* allocate node */
if (!node) { /* validate allocation */
perror ("malloc-node");
return NULL;
}
node->data = v; /* initialize members values */
node->prev = node->next = NULL;
return node; /* return new node */
}
/** add node at end of list */
node_t *add (node_t **l, int v)
{
node_t *node = createnode (v); /* allocate node */
if (!node) /* validate allocation */
return NULL;
if (!*l) { /* 1st node is self-referencing */
*l = node; /* set head to node */
(*l)->prev = (*l)->next = node; /* set prev & next to node */
}
else { /* otherwise - insert as new tail */
node->prev = (*l)->prev; /* node->prev is list->prev */
node->next = *l; /* node->next is head */
(*l)->prev->next = node; /* tail-next is node */
(*l)->prev = node; /* head->prev is node */
}
return node; /* return new node */
}
/** delete kth node in doubly-linked circular list from node *l
* returns pointer to new node at address of deleted node or NULL if
* list now empty.
*/
node_t *delkthnode (node_t **l, size_t kth)
{
node_t **ppn = l, /* pointer to pointer to node */
*pn = *l; /* pointer to node */
size_t n = kth ? kth - 1 : 1; /* set no. to advance (1-based index) */
if (pn == pn->next) { /* last node left in list? */
free (pn); /* free node */
return *ppn = NULL; /* set address for node to NULL */
}
while (n--) { /* loop to kth node */
ppn = &pn->next; /* update current address to next */
pn = pn->next; /* update current node to next */
}
*ppn = pn->next; /* set current address to next node */
(*ppn)->prev = pn->prev; /* set current->prev to next->prev */
if (pn->next == *l) /* deleting tail node? */
(*ppn)->prev->next = *l; /* set new end->next to head */
if (pn == *l) /* if current node is head */
*l = *ppn; /* update list adddress to current */
free (pn); /* free node memory */
return *ppn; /* return pointer to new node at address of removed node */
}
void dellist (node_t *l)
{
if (!l) {
puts ("list-empty");
return;
}
node_t *iter = l->next;
do {
node_t *victim = iter;
iter = iter->next;
free (victim);
} while (iter != l);
free (l);
}
void prnlist_fwd (node_t *l)
{
node_t *iter = l;
if (!l) {
puts ("list-empty");
return;
}
do {
printf (" %d", iter->data);
iter = iter->next;
} while (iter != l);
putchar ('\n');
}
void prnlist_rev (node_t *l)
{
if (!l) {
puts ("list-empty");
return;
}
node_t *iter = l->prev;
do {
printf (" %d", iter->data);
iter = iter->prev;
} while (iter != l->prev);
putchar ('\n');
}
int main (void) {
node_t *list = NULL;
int kth = 2;
for (int i = 0; i < NNODES; i++) /* loop NNODES times */
add (&list, i+1); /* add node with i+1 value to list */
prnlist_fwd (list); /* print original list fwd/rev */
prnlist_rev (list);
putchar ('\n');
while (delkthnode (&list, kth++)) {
prnlist_fwd (list); /* print updated list fwd/rev */
prnlist_rev (list);
putchar ('\n');
}
dellist (list);
}
Где над вами просто создайте список с целочисленными значениями 1-10 для значений узлов, а затем вызовите:
int kth = 2;
...
while (delkthnode (&list, kth++)) {
prnlist_fwd (list); /* print updated list fwd/rev */
prnlist_rev (list);
putchar ('\n');
}
, который действует как обертка для постоянного удаления всех остальных узлов в списке до тех пор, пока список не станет пустым (что является цель иметь фу nction возвращает указатель на узел, который остается по адресу, где был удален узел, или NULL, если список теперь пуст)
Пример использования / Вывод
Печать исходного списка (как прямого, так и обратного), а затем печать обновленного списка (прямого и обратного) до тех пор, пока все вторые узлы в списке не будут удалены, приведет к:
$ ./bin/lldcir_del_kthnode
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 1
1 3 5 6 7 8 9 10
10 9 8 7 6 5 3 1
1 3 5 7 8 9 10
10 9 8 7 5 3 1
1 3 5 7 9 10
10 9 7 5 3 1
1 3 5 7 9
9 7 5 3 1
1 5 7 9
9 7 5 1
1 5 7
7 5 1
1 5
5 1
1
1
list-empty
Или в вашем Точный случай со списком, как 1, 2, 3, 4, 5:
$ ./bin/lldcir_del_kthnode
1 2 3 4 5
5 4 3 2 1
1 3 4 5
5 4 3 1
1 3 5
5 3 1
3 5
5 3
5
5
list-empty
Надеюсь, это то, что вы хотели. Посмотрите вещи и дайте мне знать, если у вас есть дополнительные вопросы. (примечание: вам, возможно, придется скорректировать тесты и добавить дополнительные проверки, чтобы отследить все угловые случаи - это вам остается)