Реализованная реализация связанных списков

Question

Привет Я пытаюсь реализовать общий связанный список. У меня есть что-то работающее с использованием следующего кода, но я не вижу очевидного и аккуратного способа удалить зависимость от глобальных указателей (curr и root) и, таким образом, разрешить определение нескольких связанных списков. Если бы я использовал C++, я бы, вероятно, просто обернул все это в классе, но поскольку я могу видеть только одно решение, которое обрабатывает вручную и передает root и curr в функции, которые в них нуждаются. Я уверен, что есть лучший способ, чем это, так как бы вы это сделали. Благодаря

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

struct Node{ 
     int value; 
     struct Node *next; 
}; 

struct Node * curr = NULL; 
struct Node * root = NULL; 

struct Node * createList(int val){ 
    struct Node *n = malloc(sizeof(struct Node)); 

    if(n==NULL){ 
     printf("Node creation failed\n"); 
     return NULL; 
    } 

    n->value = val; 
    n->next = NULL; 

    root=curr=n; 
    return n; 
} 

struct Node * extendList(int val, bool end){ 

    if(curr == NULL){ 
     return createList(val); 
    } 

    struct Node * newNode = malloc(sizeof(struct Node)); 
    if(newNode==NULL){ 
     printf("Node creation failed\n"); 
     return NULL; 
    } 
    newNode->value = val; 
    newNode->next = NULL; 

    if(end){ 
     curr->next = newNode; 
     curr = newNode; 
    } 
    else{ 
     newNode->next = root; 
     root=newNode; 
    } 
    return curr; 
} 

void printList(void){ 
    struct Node *ptr = root; 
    while(ptr!=NULL){ 
     printf("%d\n",ptr->value); 
     ptr = ptr->next; 
    } 
    return; 
} 

struct Node * pos_in_list(unsigned int pos, struct Node **prev){ 
    struct Node * ptr = root; 
    struct Node * tmp = NULL; 
    unsigned int i = 0; 
    while(ptr!=NULL){ 
     if(i == pos){ 
      break; 
     } 
     tmp = ptr; 
     ptr=ptr->next; 
     i++; 
    } 

    *prev = tmp; 
    return ptr; 
} 

void deletefromlist(int pos){ 
    struct Node * del = NULL; 
    struct Node * prev = NULL; 

    del = pos_in_list(pos,&prev); 
    if(del == NULL) 
    { 
     printf("Out of range\n"); 
    } 
    else 
    { 
     if(prev != NULL) 
      prev->next = del->next; 

     if(del == curr) 
     { 
      curr = prev; 
     } 
     else if(del == root) 
     { 
      root = del->next; 
     } 
    } 

    free(del); 
    del = NULL; 
} 

void deleteList(){ 
    struct Node * del = root; 
    while(curr!=NULL){ 
     curr = del->next; 
     free(del); 
     del=curr; 
    } 
    root = NULL; 
    curr = NULL; 
} 

int main(void) 
{ 
    int i; 

    for(i=0;i<10;i++){ 
     extendList(i,true); 
    } 

    for(i=10;i>0;i--){ 
     extendList(i,false); 
    } 

    printList(); 

    deletefromlist(5); 

    printList(); 

    deleteList(); 

    return 0; 
} 

Answer 1

Создание структуры узла * корень и Node * ТОК

struct LinkedList{ 
struct Node * curr; 
struct Node * next; 
}; 

Answer 2

Вы можете создать еще один struct провести curr и root. Эта структура будет функционировать как внешний интерфейс «связанного списка», а ваши структуры node будут бэкэнд. В качестве дополнительного преимущества вы можете сохранить другие атрибуты связанного списка, например количество элементов в списке.

struct LinkedList { 
    int numElements; 
    struct Node * curr; 
    struct Node * root; 
}; 

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

Answer 3

Как это обычно делается, давая каждой функции аргумент для связанного указателя списка. Пример:

struct Node * extendList(struct Node * head, int val, bool end){ 

    if(head == NULL){ 
     return createList(val); 
    } 

    struct Node * newNode = malloc(sizeof(struct Node)); 
    if(newNode==NULL){ 
     printf("Node creation failed\n"); 
     return NULL; 
    } 
    newNode->value = val; 
    newNode->next = NULL; 

    struct Node * tail = head; 

    while (tail->next) tail = tail->next; 

    tail->next = newNode; 
    tail = newNode; 
    return newNode; // return the new node 
} 

Отключает любые потребности в глобальном указателе и допускает произвольное количество списков. На самом деле я настоятельно рекомендую вам избегать использования глобальных переменных в этом контексте.

Я представил обзор для реализации связанного списка, вы можете check out. Вы можете проверить критику, те, которые могут применяться к вашей собственной реализации.

Answer 4

Ознакомьтесь с обобщенными реализациями, полученными в Беркли, для некоторых других идей о том, как это сделать.

• Документация queue(3)
• Источник OpenBSD, Linux libc

Answer 5

Я реализовал общий список в С.

Он предназначен для использования в качестве статической библиотеки. Операции списка (по общим данным) отображаются из службы списка. Как вы просили,

1. аккуратный способ удалить Dependance на глобальных указателей (голова)
2. Определение нескольких связанных списков.

Этот список услуг выполнять обе эти функции в следующим образом,

При создании нового списка Linked этот сервис возвращает уникальный идентификатор, представляющий его вместо традиционного Linked списка указатель головы. Таким образом, клиентский код не может напрямую коррумпировать связанный список.эта служба списка позволяет создавать несколько связанных списков. Каждый из них имеет уникальный идентификатор. Это до клиента для бесплатных списков, когда они сделаны, и служба может повторно использовать этот слот позже при создании нового. Поддержание глобального указателя заголовка для каждого списка является обязательным в любом подходе, но здесь оно скрыто внутри службы списка.

Ниже моя реализация:

https://github.com/rajan-goswami/glist/wiki