0

您好我正在尝试实现一个通用链表。我已经使用以下代码进行了一些工作，但是我看不到一种明显而简洁的方法来消除对全局指针（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;
}
4

5 回答 5

3

创建 Node * root 和 Node * curr 的结构

struct LinkedList{
struct Node * curr;
struct Node * next;
};
于 2013-07-10T17:24:29.443 回答
2

您可以创建另一个struct来保存currand root。这个结构将像一个“链表对象”前端一样工作，而您的node结构将是后端。作为一个额外的好处，您可以存储有关链接列表的其他属性，例如列表中元素的数量。

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

你可以修改你的函数来使用这个结构，一旦你完成了，好处是最终用户可以创建许多链表，他们所要做的就是调用函数并将它们的指针传递给LinkedList结构.

于 2013-07-10T17:24:19.113 回答
1

通常这样做的方法是给每个函数一个链表指针的参数。像这样：

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
}

这消除了对全局指针的任何需求，并允许任意数量的列表。事实上，我强烈建议您避免在这种情况下使用全局变量。

我已经提交了一个链接列表实现的评论，你可以查看。您可能想要检查对您自己的实现可能适用的批评。

于 2013-07-10T17:28:00.517 回答
1

我在 C 中实现了一个通用列表。

它旨在用作静态库。列表操作（对通用数据）从列表服务公开。如你所问，

  1. 消除对全局指针（头）依赖的巧妙方法
  2. 定义多个链表。

此列表服务通过以下方式完成这两个功能，

在创建一个新的链表时，该服务返回一个代表它的唯一标识符，而不是传统的链表头指针。这样客户端代码就不能直接破坏链表。此列表服务允许创建多个链接列表。每个都有唯一的 id。完成后由客户端释放列表，并且服务可以稍后在创建新列表时重新使用该插槽。在任何方法中都必须为每个列表维护全局头指针，但它隐藏在列表服务中。

以下是我的实现：

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

于 2014-01-02T10:40:50.643 回答
0

查看 Berkeley 派生的通用实现，了解有关如何执行此操作的其他一些想法。

于 2013-07-10T17:32:16.267 回答