使用C实现Skiplist

Question

下面是我的跳过的实现，代码运行良好，但我需要这样做:当键与现有的键值匹配时，值将用新值进行更新，但在我的示例中，项目插入了两次，数据没有被替换。我想在更新时实现这一点，这样我就不必搜索整个列表了。

我们非常感谢在这方面提供的任何帮助。

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

#ifndef EQ
#define EQ(a, b) (a == b)
#endif

#ifndef LTE
#define LTE(a, b) (a < b)
#endif

struct skipLink
{
    int key;
    int value;
    struct skipLink *next;
    struct skipLink *down;
};

struct skipList
{
    struct skipLink *topSentinel;
    int size;
};

/* the public interface */
void test(void);
void initSkipList(struct skipList *slst);
int containsSkipList(struct skipList *slst, int key);
void removeSkipList(struct skipList *slst, int key);
void addSkipList(struct skipList *slst, int key, int value);
int sizeSkipList(struct skipList *slst);
void printSkipList(struct skipList *slst);

/* internal routines */
int flipSkipLink();
struct skipLink *slideRightSkipList(struct skipLink *current, int key);
struct skipLink *skipLinkAdd(struct skipLink *current, int key, int value);
struct skipLink *newSkipLink(int key, int value, struct skipLink *nextLnk, struct skipLink *downLnk);

/* ************************************************************************
Main Function
 ************************************************************************ */
/* Test function:
 param: no parameters
 pre:   no parameres
 post: prints out the contents of the skip list */

int main()
{
    int i = 0;
    /*srand(time(NULL));*/

    /*  Initialize the skip list */
    struct skipList *sl1 = (struct skipList *)malloc(sizeof(struct skipList));
    initSkipList(sl1);

    /*  Add to the skip list  M = 20 random integers in [0,100] */
    for (i = 0; i < 20; i++)
    {
        addSkipList(sl1, rand() % 101, i + 5);
    }
    addSkipList(sl1, 1, 9);

    /*  Print out the contents of the skip list in the breadth-first order, starting from top.
     While printing the elements, move to a new line every time you reach the end of one level,
     and move down to the lower level of the skip list.
     For example, the print out of a skip list with 5 elements should look like

     7
     7 14 29
     3 7 9 14 20

     */
    printf("---------- skipList 1 -----");
    printf("----- size %d -----\n", sizeSkipList(sl1));
    printSkipList(sl1);
    printf("---------- removed %d from skipList -----", sl1->topSentinel->next->key);
    removeSkipList(sl1, sl1->topSentinel->next->key);
    printf("----- size %d -----\n", sizeSkipList(sl1));
    printSkipList(sl1);

    return 0;
}

/* ************************************************************************
Internal Functions
 ************************************************************************ */

/* Coin toss function:
 param:     no parameters
 pre:   no parameres
 post: output is a random intiger number in {0,1} */
int flipSkipLink(void)
{
    return (rand() % 2);
}

/* Move to the right as long as the next element is smaller than the input key:
 param:     current -- pointer to a place in the list from where we need to slide to the right
 param: key --  input key
 pre:   current is not NULL
 post: returns one link before the link that contains the input key key */
struct skipLink *slideRightSkipList(struct skipLink *current, int key)
{
    while ((current->next != 0) && LTE(current->next->key, key))
        current = current->next;
    return current;
}

/* Create a new skip link for a key
    param: key   -- the key to create a link for
    param: nextLnk   -- the new link's next should point to nextLnk
    param: downLnk -- the new link's down should point to downLnk
    pre:    none
    post:   a link to store the key */
struct skipLink *newSkipLink(int key, int value, struct skipLink *nextLnk, struct skipLink *downLnk)
{
    struct skipLink *tmp = (struct skipLink *)malloc(sizeof(struct skipLink));
    assert(tmp != 0);
    tmp->key = key;
    tmp->value = value;
    tmp->next = nextLnk;
    tmp->down = downLnk;
    return tmp;
}

/* Add a new skip link recursively
 param: current -- pointer to a place in the list where the new element should be inserted
 param: key  -- the key to create a link for
 pre:   current is not NULL
 post: a link to store the key */
struct skipLink *skipLinkAdd(struct skipLink *current, int key, int value)
{
    struct skipLink *newLink, *downLink;
    newLink = 0;
    if (current->down == 0)
    {
        newLink = newSkipLink(key, value, current->next, 0);
        current->next = newLink;
    }
    else
    {
        downLink = skipLinkAdd(slideRightSkipList(current->down, key), key, value);
        if (downLink != 0 && flipSkipLink())
        {
            newLink = newSkipLink(key, value, current->next, downLink);
            current->next = newLink;
        }
    }
    return newLink;
}

/* ************************************************************************
Public Functions
 ************************************************************************ */

/* Initialize skip list:
 param:  slst -- pointer to the skip list
 pre:   slst is not null
 post: the sentinels are allocated, the pointers are set, and the list size equals zero */
void initSkipList(struct skipList *slst)
{
    assert(slst != NULL);
    slst->topSentinel = (struct skipLink *)malloc(sizeof(struct skipLink));
    slst->topSentinel->next = 0;
    slst->topSentinel->down = 0;
    slst->size = 0;
}

/* Checks if an element is in the skip list:
 param: slst -- pointer to the skip list
 param: key -- element to be checked
 pre:   slst is not null
 post: returns true or false  */
int containsSkipList(struct skipList *slst, int key)
{
    struct skipLink *current = slst->topSentinel;
    while (current)
    {
        current = slideRightSkipList(current, key);
        if ((current->next != 0) && EQ(current->next->key, key))
            return 1;
        current = current->down;
    }
    return 0;
}

/* Remove an element from the skip list:
 param: slst -- pointer to the skip list
 param: key -- element to be removed
 pre:   slst is not null
 post: the new element is removed from all internal sorted lists */
void removeSkipList(struct skipList *slst, int key)
{
    struct skipLink *current, *temp;
    current = slst->topSentinel;

    while (current)
    {
        current = slideRightSkipList(current, key);
        if ((current->next != 0) && EQ(current->next->key, key))
        {
            temp = current->next;
            current->next = current->next->next;
            free(temp);
            if (current->down == NULL)
                slst->size--;
        }
        current = current->down;
    }
}

/* Add a new element to the skip list:
    param: slst -- pointer to the skip list
    param: key -- element to be added
    pre:    slst is not null
    post:   the new element is added to the lowest list and randomly to higher-level lists */
void addSkipList(struct skipList *slst, int key, int value)
{
    struct skipLink *downLink, *newLink;
    downLink = skipLinkAdd(slideRightSkipList(slst->topSentinel, key), key, value);
    if (downLink != 0 && flipSkipLink())
    {
        struct skipLink *newTopSentinel = (struct skipLink *)malloc(sizeof(struct skipLink));
        newLink = newSkipLink(key, value, 0, downLink);
        newTopSentinel->next = newLink;
        newTopSentinel->down = slst->topSentinel;
        slst->topSentinel = newTopSentinel;
    }
    slst->size++;
}

/* Find the number of elements in the skip list:
 param: slst -- pointer to the skip list
 pre:   slst is not null
 post: the number of elements */
int sizeSkipList(struct skipList *slst)
{
    return slst->size;
}

/* Print the links in the skip list:
    param: slst -- pointer to the skip list
    pre:    slst is not null and slst is not empty
    post: the links in the skip list are printed breadth-first, top-down */
void printSkipList(struct skipList *slst)
{
    struct skipLink *currentlist = slst->topSentinel;
    struct skipLink *currentlink;
    while (currentlist != NULL)
    {
        currentlink = currentlist->next;
        while (currentlink != NULL)
        {
            printf("{%d, %d}", currentlink->key, currentlink->value);
            currentlink = currentlink->next;
        }
        currentlist = currentlist->down;
        printf("\n");
        printf("\n");
    }
}

Answer 1

更新现有元素

如果希望代码能够在插入新值时更新现有元素，则必须将在containsSkipList()中进行的搜索与新skipLink的创建结合起来。所以：

void addSkipList(struct skipList *slst, int key, int value)
{
    
    struct skipLink *current = slst->topSentinel;

    while (current)
    {
        /* Search as usual */
        current = slideRightSkipList(current, key);
        if (current->next != NULL && current->next->key == key)
        {
            /* If found, update the value */
            current->next->value = value;

            /* Also update all the skipLinks downwards from this point */
            ...
            return;
        }

        if (current->down == NULL)
            break;

        current = current->down;
    }

    /* current now points to the closest smaller item to key,
     * add the new item right after it */
    ...

    if (flipSkipLink())
    {
        /* Add to higher level-list as well */
    }
}

避免编写宏

您定义了两个不太有用的宏，但更糟糕的是它们是不正确的。问题是，这些论点会被逐字逐句地展开，这可能是一个问题。考虑这个例子，我想比较一个值是否具有给定的位集：

int value = 0x01;
int mask = 0x10;
int required = 0x10;

printf("%d\n", EQ(value & mask, required));

您可能期望value & mask为零，这并不等于required，因此您希望它打印0。但是，它打印1，因为在宏扩展之后，它说：

printf("%d\n", (value & mask == required));

由于==的优先比&高，所以它相当于(value & (mask == required))。您要么必须修复宏：

#define EQ(a, b) ((a) == (b))

或者编写一个函数，如果您知道参数的类型：

bool EQ(int a, int b) { return a == b; }

但是在这种情况下，宏根本没用，只需在代码中直接使用==和<即可。例如，而不是：

while ((current->next != 0) && LTE(current->next->key, key))

只需写：

while (current->next != NULL && current->next->key < key)

对指针使用NULL而不是0

虽然可以将指针与0进行比较，但最好显式地编写NULL。这有助于捕获错误，如果您想要检查一个空指针，但您不小心比较一个非指针变量和0。这将在没有任何警告的情况下编译，但是如果您编写了NULL，那么编译器将给您一个警告，这是一个潜在的错误。

避免前向声明

通过更改源文件中定义函数的顺序，可以避免编写前向声明。这样就避免了重复，减少了潜在的错误。

使内部例程static

仅在同一.c文件中使用且在其他文件中不可见的函数可以成为static。这避免了名称空间的污染，也可能帮助编译器生成更好的代码。

在适当情况下使用const指针

如果一个函数接受指向skipList的指针，但是您不打算修改该跳过，那么就创建指针const。这允许编译器在无意中向跳过者写入时生成错误，而且它还可能生成更优化的代码。

对公共接口使用一致的前缀。

为了避免名称空间冲突，如果所有公共接口函数都有一个公共前缀，则会有所帮助。使用他们操作的struct的名称是一个很好的选择。目前，在大多数情况下，您都是将其用作后缀，但并不总是如此。所以：

• skipList_init()
• skipList_contains()
• ..。

我建议您也将其用于内部例程，因此：

- `skipLink_add()`
- `skipLink_new()`
- ...

避免重复类型名称

在这一行中，重复类型的名称三次：

struct skipList *sl1 = (struct skipList *)malloc(sizeof(struct skipList));

您可以将其重写为：

struct skipList *sl1 = malloc(sizeof *sl1);

符合标准的编译器应该在没有任何警告的情况下接受此操作。如果用C++编译器编译它，则可能需要强制转换。

创建构造函数和析构函数

让跳过者的用户为struct skipList分配内存，然后让它调用initSkipList()。虽然这在某些情况下可能是有意义的，但在您完成skipList之后，还有一个问题。用户只是在free()变量上调用skipList吗？但是，分配的所有skipLink怎么办？创建一个构造函数和一个析构函数，负责内存分配、初始化和释放：

struct skipList *skipList_new(void) {
    struct skipList *list = malloc(sizeof *list);
    skipList_init(list);
    return list;
}

void skipList_delete(struct skipList *list) {
    for (/* each skipLink in the list */)
         skipLink_delete(link);

    free(list);
}

酌情使用bool

当某物返回一个真/假值时，使用来自<stdbool.h>的<stdbool.h>类型。例如：

bool skipList_contains(const struct skipList *slst, int key)
{
    const struct skipLink *current = slst->topSentinel;
    while (current)
    {
        current = skipList_slideRight(current, key);
        if (current->next != NULL && current->next->key == key)
            return true;
        current = current->down;
    }
    return false;
}