Кольцевой список

[Jigedara]

есть кольцевой список вида:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef struct NODE {
    int value;
    struct NODE * next;
} node_t;
 
void push(node_t ** pRing, int nValue) {
    node_t * pNode = malloc(sizeof(node_t));
    assert ( pNode );
    pNode->value = nValue;
    if ( ! *pRing ) {
        pNode->next = pNode;
        *pRing = pNode;
    }
    else {
        pNode->next = (*pRing)->next;
        (*pRing)->next = pNode;
        *pRing = pNode;
    }
}
 
void rotate(node_t ** pRing, int steps) {
    assert ( *pRing && steps > 0 );
    while ( steps-- )
        *pRing = (*pRing)->next;
}
 
 
int top(const node_t * ring) {
    return ring->value;
}
 
int is_empty(const node_t * ring) {
    return ( ! ring );
}
 
int shift(node_t ** pRing) {
    int ret;
    assert ( *pRing );
    ret = (*pRing)->value;
 
    if ( (*pRing)->next == *pRing ) {
        free(*pRing);
        *pRing = NULL;
    }
    else {
        node_t * pPrev = (*pRing)->next;
        while ( pPrev->next != *pRing )
            pPrev = pPrev->next;
        pPrev->next = (*pRing)->next;
        free(*pRing);
        *pRing = pPrev->next;
    }
 
    return ret;
}

int main(void) {
    node_t * ring = NULL;
    int count, i, value;
    
    printf("Number of elements: ");
    assert ( scanf("%d", &count) == 1 && count > 0 );
    for ( i = 0; i < count; ++i ) {
        printf("Value #%d: ", i + 1);
        assert( scanf("%d", &value) == 1 );
        push(&ring, value);
    }
    
    rotate(&ring, 1);
    
    while ( ! is_empty(ring) )
        printf("%d ", shift(&ring));
 
    return 0;
}

как добавить к этому поиск и удаление N-ого элемента?

[s-andriano]

В кольцевом списке не может быть N-го элемента.

[Stilet]

Поиск

node_t* find(node_t* n, int val) {
    for(node_t *i=n;;){
     if(i->value==val){ return i;}
     i=i->next;
     if(i==n){return 0;}
    }
}

Удаление

bool dele(node_t* n, int N) {
    for(node_t *i=n,node_t *j=n;;){
     if(N==0){ 
        j->next=i->next;
        delete i;
        return true;
     }
     j=i;
     i=i->next;
     N--;
     if(i==n){return false;}
    }
}

Это в качестве идеи.

[Jigedara]

хм, идею я приблизительно понял...
в поиске поворнуть список на N шагов. Посчитать количество элементов в списке можно запомнив адрес текущего элемента, поворачивая список на 1 шаг и увеличивая счётчик, пока адрес элемента "на верху" не совпадёт с запомненным.
а в удалении удалить элемент и переписать указатели: указатель (N-1)-ого элемента сделать указывающим на (N+1)-й элемент, а указатель соответствующего значения обнулить.
Но как всё это реализовать на Си?

[Stilet]

Но как всё это реализовать на Си?

Да это хороший вопрос...
Я и сам над этим задумывался. )

[Jigedara]

добавил для поиска:

node_t * find(const node_t * ring, const int value) {
const node_t * current = ring;
do {
if ( current->value == value )
return (node_t*)current;
current = current->next;
} while ( current != ring );
return NULL;
}

как в функции main() организовать цикл который находит N-й элемент, удаляет его, с (N+1)-ого элемента снова отсчитывает N-й элемент, удаляет его и т.д. пока не останется 1 элемент, затем вывести его на экран. Цикл должен пройти n-1 раз, где n - количество элементов