c - 如何在c中创建一个双向链表

Question

我正在尝试制作一个循环链表来模拟旋转轮盘赌轮。我已经搜索了网络并在代码中运行了我的逻辑，但我似乎无法发现我的逻辑中的错误。我真正需要帮助的是了解如何使双向链表循环。预先感谢您的任何帮助。该程序的目标是生成一个随机数，然后使用该数字迭代循环双向链表。目前，当我运行程序时，会迭代到最后一个数字，然后重复该最后一个数字，剩余的迭代将不包含在随机数中。

/*
Roulette program
*/



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

struct node{
  int value;
  struct node * next;
  struct node * prev;
};


struct node * create_node( struct node *, int );
void print_forwards( struct node *, int );
void print_backwards( struct node * );
struct node * get_last_node( struct node * );


int main ( int argc, char * argv[] ) {

  printf("Welcome to the game of Roulette!\n");

  int rand_num;
  int i;


  srand( time(NULL) );
  rand_num = rand() % 400 + 1;

    printf("\nFowards Random #: %d\n", rand_num );
    // Numbers in order on a European Roulette wheel.
    //0-32-15-19-4-21-2-25-17-34-6-27-13-36-11-30-8-23-10-5-24-16-33-1-20-       
    //14-31-9-22-18-29-7-28-12-35-3-26

    struct node * the_list = NULL;
    the_list = create_node( the_list, 0 );
    the_list = create_node( the_list, 32 );
    the_list = create_node( the_list, 15 );
    the_list = create_node( the_list, 19 );
    the_list = create_node( the_list, 4 );
    the_list = create_node( the_list, 21 );
    the_list = create_node( the_list, 2 );
    the_list = create_node( the_list, 25 );
    the_list = create_node( the_list, 17 );
    the_list = create_node( the_list, 34 );
    the_list = create_node( the_list, 6 );
    the_list = create_node( the_list, 27 );
    the_list = create_node( the_list, 13 );
    the_list = create_node( the_list, 36 );
    the_list = create_node( the_list, 11 );
    the_list = create_node( the_list, 30 );
    the_list = create_node( the_list, 8 );
    the_list = create_node( the_list, 23 );
    the_list = create_node( the_list, 10 );
    the_list = create_node( the_list, 5 );
    the_list = create_node( the_list, 24 );
    the_list = create_node( the_list, 16 );
    the_list = create_node( the_list, 33 );
    the_list = create_node( the_list, 1 );
    the_list = create_node( the_list, 20 );
    the_list = create_node( the_list, 14 );
    the_list = create_node( the_list, 31 );
    the_list = create_node( the_list, 9 );
    the_list = create_node( the_list, 22 );
    the_list = create_node( the_list, 18 );
    the_list = create_node( the_list, 29 );
    the_list = create_node( the_list, 7 );
    the_list = create_node( the_list, 28 );
    the_list = create_node( the_list, 12 );
    the_list = create_node( the_list, 35 );
    the_list = create_node( the_list, 3 );
    the_list = create_node( the_list, 26 );



    print_forwards( the_list, rand_num );
    // print_backwards( the_list );

  getchar();
  return 0;
}

struct node * create_node( struct node * the_list, int new_value ){

    // Create the new node and set it value.
    // Also set the next and prev. pointers to NULL.
    struct node * head = (struct node *)malloc( sizeof( struct node ) );
    head->value = new_value;
  head->next = head;
    head->prev = head;

  struct node * temp;
  temp->prev = (struct node *)malloc( sizeof( struct node ) );
  temp = temp->prev;
  temp->prev = head;
  head->next = temp;

    // create the new node at the front of the list.
    if( the_list ){
        // Set the existing list's prev pointer
        // to point to our new node.
        the_list->prev = head;
    }
    // In any case, set our new node to the list.
    // This will work fine if the list is empty
    // because the "the_list" pointer is NULL.
    head->next = the_list;
    return head;

}


void print_backwards( struct node * the_list ){
    printf( "\n-- Printing Backwards --\n" );
    while( the_list ){
        printf( "%d\n",
            the_list->value
        );
        the_list = the_list->next;
    }
}

void print_forwards( struct node * the_list, int rand_num ){
    printf( "\n-- Printing Forwards --\n" );
  int i;
  struct node * end = get_last_node( the_list );
  for( i = 0; i < rand_num; i++ ){
    printf( "%d ",
      end->value
    );
    end = end->prev;
  }
}

struct node * get_last_node( struct node * the_list ){
    while( the_list ){
        if( the_list->next == NULL ){
            break;
        }else{
            the_list = the_list->next;
        }
    }
    return the_list;
}

Answer 1

警告:正如其他人所提到的，使用固定长度数组而不是循环列表可能更容易，并将索引包装到以数组大小为模的数组中。

但是，话虽如此，回答你的问题......

为了说明如何将双向链表转换为循环链表，我提供了这两种类型的函数。您可以通过在命令行上指定-c来选择循环。

我从你的代码开始，但我必须进行相当多的重组(例如一些错误修复和添加一些缺失的代码)才能使事情正常工作[请原谅无偿的风格清理]:

/*
Roulette program
*/

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

struct node {
    int value;
    struct node *next;
    struct node *prev;
};

int circflg;
int opt_d;

struct node *create_node(struct node *, int);
void print_forwards(struct node *, int);
void print_backwards(struct node *);

// main -- main program
int
main(int argc,char **argv)
{
    char *cp;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 'c':
            circflg = ! circflg;
            break;

        case 'd':
            opt_d = ! opt_d;
            break;

        default:
            break;
        }
    }

    printf("Welcome to the game of Roulette!\n");

    int rand_num;

    srand(time(NULL));
    rand_num = rand() % 400 + 1;
    printf("\nFowards Random #: %d\n", rand_num);

    // Numbers in order on a European Roulette wheel.
    // 0-32-15-19-4-21-2-25-17-34-6-27-13-36-11-30-8-23-10-5-24-16-33-1-20-
    // 14-31-9-22-18-29-7-28-12-35-3-26

    struct node *the_list = NULL;

    the_list = create_node(the_list, 0);
    the_list = create_node(the_list, 32);
    the_list = create_node(the_list, 15);
    the_list = create_node(the_list, 19);
    the_list = create_node(the_list, 4);
    the_list = create_node(the_list, 21);
    the_list = create_node(the_list, 2);
    the_list = create_node(the_list, 25);
    the_list = create_node(the_list, 17);
    the_list = create_node(the_list, 34);
    the_list = create_node(the_list, 6);
    the_list = create_node(the_list, 27);
    the_list = create_node(the_list, 13);
    the_list = create_node(the_list, 36);
    the_list = create_node(the_list, 11);
    the_list = create_node(the_list, 30);
    the_list = create_node(the_list, 8);
    the_list = create_node(the_list, 23);
    the_list = create_node(the_list, 10);
    the_list = create_node(the_list, 5);
    the_list = create_node(the_list, 24);
    the_list = create_node(the_list, 16);
    the_list = create_node(the_list, 33);
    the_list = create_node(the_list, 1);
    the_list = create_node(the_list, 20);
    the_list = create_node(the_list, 14);
    the_list = create_node(the_list, 31);
    the_list = create_node(the_list, 9);
    the_list = create_node(the_list, 22);
    the_list = create_node(the_list, 18);
    the_list = create_node(the_list, 29);
    the_list = create_node(the_list, 7);
    the_list = create_node(the_list, 28);
    the_list = create_node(the_list, 12);
    the_list = create_node(the_list, 35);
    the_list = create_node(the_list, 3);
    the_list = create_node(the_list, 26);

    print_forwards(the_list, rand_num);
    print_backwards(the_list);

    //getchar();

    return 0;
}

int
print_entry(int totlen,int val)
{
    int curlen;
    char buf[100];

    curlen = sprintf(buf," %2d",val);

    if ((totlen + curlen) > 78) {
        printf("\n");
        totlen = 0;
    }

    fputs(buf,stdout);
    totlen += curlen;

    return totlen;
}

struct node *
list_last_node(struct node *the_list)
{
    struct node *cur;
    struct node *end;

    end = the_list;

    for (cur = the_list;  cur != NULL;  cur = cur->next)
        end = cur;

    return end;
}

struct node *
list_create_node(struct node *the_list, int new_value)
{
    struct node *prev;

    // Create the new node and set it value.
    struct node *temp = (struct node *) malloc(sizeof(struct node));

    // set the new value
    temp->value = new_value;

    // create the new node at the front of the list.
    if (the_list == NULL) {
        the_list = temp;
        temp->next = NULL;
        temp->prev = NULL;
    }

    // append to end
    else {
        prev = list_last_node(the_list);
        temp->next = NULL;
        temp->prev = prev;
        prev->next = temp;
    }

    return the_list;
}

void
list_print_backwards(struct node *the_list)
{
    struct node *cur;
    struct node *end;
    struct node *prev;
    int len;

    printf("\n-- Printing Backwards --\n");

    cur = list_last_node(the_list);

    len = 0;

    for (;  cur != NULL;  cur = prev) {
        len = print_entry(len,cur->value);
        prev = cur->prev;
    }

    printf("\n");
}

void
list_print_forwards(struct node *the_list, int rand_num)
{
    int i;
    struct node *cur;
    struct node *next;
    int len;

    printf("\n-- Printing Forwards --\n");

    len = 0;
    i = 0;
    for (cur = the_list;  cur != NULL;  cur = next, ++i) {
        if (i >= rand_num)
            break;

        next = cur->next;

        len = print_entry(len,cur->value);
    }

    printf("\n");
}

struct node *
circ_create_node(struct node *the_list, int new_value)
{
    struct node *prev;

    // Create the new node and set it value.
    struct node *temp = (struct node *) malloc(sizeof(struct node));

    // set the new value
    temp->value = new_value;

    do {
        // create the new node at the front of the list.
        if (the_list == NULL) {
            the_list = temp;
            temp->next = temp;
            temp->prev = temp;
            break;
        }

        // append to end
        prev = the_list->prev;
        temp->next = the_list;
        temp->prev = prev;
        prev->next = temp;

        the_list->prev = temp;
    } while (0);

    return the_list;
}

void
circ_print_backwards(struct node *the_list)
{
    struct node *cur;
    struct node *prev;
    int len;

    printf("\n-- Printing Backwards --\n");

    len = 0;
    for (cur = the_list;  cur != NULL;  cur = prev) {
        len = print_entry(len,cur->value);
        prev = cur->prev;
        if (prev == the_list)
            break;
    }

    printf("\n");
}

void
circ_print_forwards(struct node *the_list, int rand_num)
{
    int i;
    struct node *cur;
    struct node *next;
    int len;

    printf("\n-- Printing Forwards --\n");

    i = 0;
    len = 0;
    for (cur = the_list;  cur != NULL;  cur = next, ++i) {
        if (i >= rand_num)
            break;

        next = cur->next;

        len = print_entry(len,cur->value);

        if (next == the_list)
            break;
    }

    printf("\n");
}

struct node *
create_node(struct node *the_list, int new_value)
{

    if (circflg)
        the_list = circ_create_node(the_list,new_value);
    else
        the_list = list_create_node(the_list,new_value);

    if (opt_d) {
        printf("create_node: added %d\n",new_value);
        print_forwards(the_list,-1);
        print_backwards(the_list);
    }

    return the_list;
}

void
print_backwards(struct node *the_list)
{

    if (circflg)
        circ_print_backwards(the_list);
    else
        list_print_backwards(the_list);
}

void
print_forwards(struct node *the_list,int rand_num)
{

    if (circflg)
        circ_print_forwards(the_list,rand_num);
    else
        list_print_forwards(the_list,rand_num);
}