猫喵鱼 发表于 2022-3-21 23:28:37

求大神帮忙编程完成合并两循环单链表

用c语言

人造人 发表于 2022-3-22 03:26:19

估计你要的是单向循环链表，但是因为我不认真看题，我写完了双向循环链表后才发现这个问题
不管怎么说，双向循环链表也是循环链表
参考下面的这个代码自己完成单向循环链表吧

list.h
#ifndef _LIST_H_
#define _LIST_H_

#include <stddef.h>
#include <stdbool.h>

typedef struct list_node_tag {
    struct list_node_tag *prev;
    struct list_node_tag *next;
    void *data;
    size_t size;
} list_node_t;

typedef struct {
    list_node_t *node;
    size_t size;
} list_t;

list_t *list_init(void);
void list_deinit(list_t *list);
void list_clean(list_t *list);
bool list_insert(list_t *list, size_t index, const void *data, size_t size);
bool list_delete(list_t *list, size_t index);
bool list_set(list_t *list, size_t index, const void *data, size_t size);
bool list_get(const list_t *list, size_t index, void *data, size_t size);
bool list_append(list_t *list, const void *data, size_t size);
bool list_empty(const list_t *list);
size_t list_size(const list_t *list);

list_t *list_union(const list_t *a, const list_t *b);

#endif


list.c
#include "list.h"
#include <stdlib.h>
#include <string.h>

#define GET_NODE(list, index) ({ \
      const list_t *this_list = list; \
      size_t this_index = (index) + 1; \
      list_node_t *node = this_list->node; \
      while(this_index--) node = node->next; \
      node; \
    })

static list_node_t *new_node(size_t size) {
    list_node_t *node = malloc(sizeof(*node));
    if(!node) return node;
    node->data = malloc(size);
    if(size && !node->data) {free(node); return NULL;}
    node->size = size;
    node->next = node;
    node->prev = node;
    return node;
}

static void delete_node(list_node_t *node) {
    if(!node) return;
    free(node->data);
    free(node);
}

list_t *list_init(void) {
    list_t *list = malloc(sizeof(*list));
    if(!list) return list;
    list->node = new_node(0);
    if(!list->node) {free(list); return NULL;}
    list->size = 0;
    return list;
}

void list_deinit(list_t *list) {
    if(!list) return;
    list_clean(list);
    delete_node(list->node);
    free(list);
}

void list_clean(list_t *list) {
    if(!list) return;
    while(!list_empty(list)) list_delete(list, 0);
}

bool list_insert(list_t *list, size_t index, const void *data, size_t size) {
    if(!list) return false;
    if(index > list_size(list)) return false;
    list_node_t *node = new_node(size);
    if(!node) return false;
    memcpy(node->data, data, node->size);
    list_node_t *current = list->node;
    while(index--) current = current->next;
    node->next = current->next;
    node->prev = current;
    current->next = node;
    node->next->prev = node;
    ++list->size;
    return true;
}

bool list_delete(list_t *list, size_t index) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t *current = list->node;
    while(index--) current = current->next;
    list_node_t *temp = current->next;
    current->next = temp->next;
    temp->next->prev = current;
    delete_node(temp);
    --list->size;
    return true;
}

bool list_set(list_t *list, size_t index, const void *data, size_t size) {
    if(!list) return false;
    bool res = list_delete(list, index);
    if(!res) return res;
    return list_insert(list, index, data, size);
}

bool list_get(const list_t *list, size_t index, void *data, size_t size) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t *current = GET_NODE(list, index);
    if(!data) return false;
    if(size < current->size) return false;
    memcpy(data, current->data, current->size);
    return true;
}

bool list_append(list_t *list, const void *data, size_t size) {
    if(!list) return false;
    return list_insert(list, list_size(list), data, size);
}

bool list_empty(const list_t *list) {
    if(!list) return true;
    return list->size == 0;
}

size_t list_size(const list_t *list) {
    if(!list) return 0;
    return list->size;
}

list_t *list_union(const list_t *a, const list_t *b) {
    list_t *list = list_init();
    for(size_t i = 0; i < list_size(a); ++i) {
      list_node_t *current = GET_NODE(a, i);
      list_append(list, current->data, current->size);
    }
    for(size_t i = 0; i < list_size(b); ++i) {
      list_node_t *current = GET_NODE(b, i);
      list_append(list, current->data, current->size);
    }
    return list;
}


main.c
#include "list.h"
#include <stdio.h>

typedef struct {
    char c;
    int i;
    double d;
} test_t;

int main(void) {
    list_t *list = list_init();
    {
      test_t t = {'x', 123, 3.14};
      list_append(list, &t.c, sizeof(t.c));
      list_append(list, &t.i, sizeof(t.i));
      list_append(list, &t.d, sizeof(t.d));
      list_append(list, &t, sizeof(t));
    }
    {
      test_t t;
      list_get(list, 0, &t.c, sizeof(t.c));
      list_get(list, 1, &t.i, sizeof(t.i));
      list_get(list, 2, &t.d, sizeof(t.d));
      printf("%c %d %lf\n", t.c, t.i, t.d);
    }
    {
      test_t t;
      list_get(list, 3, &t, sizeof(t));
      printf("%c %d %lf\n", t.c, t.i, t.d);
    }
    {
      double d;
      list_delete(list, 1);
      list_get(list, 1, &d, sizeof(d));
      printf("%lf\n", d);
    }
    {
      char c;
      list_delete(list, 1);
      list_get(list, 0, &c, sizeof(c));
      printf("%c\n", c);
    }
    {
      list_delete(list, 1);
      list_delete(list, 0);
      for(size_t i = 0; i < 10; ++i) {
            list_append(list, &i, sizeof(i));
      }
    }
    {
      size_t i;
      list_get(list, 9, &i, sizeof(i));
      printf("%lu\n", i);
    }
    list_deinit(list);
    {
      list_t *a = list_init();
      list_t *b = list_init();
      for(size_t i = 0; i < 10; ++i) {
            list_append(a, &i, sizeof(i));
      }
      for(size_t i = 100; i < 107; ++i) {
            list_append(b, &i, sizeof(i));
      }
      list_t *c = list_union(a, b);
      for(size_t i = 0; i < list_size(c); ++i) {
            size_t value;
            list_get(c, i, &value, sizeof(value));
            printf("%lu ", value);
      }
      puts("");
      list_deinit(c);
      list_deinit(b);
      list_deinit(a);
    }
    return 0;
}


$ gcc-debug -o main main.c list.c
$ ./main
x 123 3.140000
x 123 3.140000
3.140000
x
9
0 1 2 3 4 5 6 7 8 9 100 101 102 103 104 105 106
$



傻眼貓咪 发表于 2022-3-22 09:09:18

来学习学习

人造人 发表于 2022-3-22 11:32:55

单向循环链表

list.h
#ifndef _LIST_H_
#define _LIST_H_

#include <stddef.h>
#include <stdbool.h>

typedef struct list_node_tag {
    struct list_node_tag *next;
    void *data;
    size_t size;
} list_node_t;

typedef struct {
    list_node_t *node;
    size_t size;
} list_t;

list_t *list_init(void);
void list_deinit(list_t *list);
void list_clean(list_t *list);
bool list_insert(list_t *list, size_t index, const void *data, size_t size);
bool list_delete(list_t *list, size_t index);
bool list_set(list_t *list, size_t index, const void *data, size_t size);
bool list_get(const list_t *list, size_t index, void *data, size_t size);
bool list_append(list_t *list, const void *data, size_t size);
bool list_empty(const list_t *list);
size_t list_size(const list_t *list);

list_t *list_union(const list_t *a, const list_t *b);

#endif


list.c
#include "list.h"
#include <stdlib.h>
#include <string.h>

#define GET_NODE(list, index) ({ \
      const list_t *this_list = list; \
      size_t this_index = (index) + 1; \
      list_node_t *node = this_list->node; \
      while(this_index--) node = node->next; \
      node; \
    })

static list_node_t *new_node(size_t size) {
    list_node_t *node = malloc(sizeof(*node));
    if(!node) return node;
    node->data = malloc(size);
    if(size && !node->data) {free(node); return NULL;}
    node->size = size;
    node->next = node;
    return node;
}

static void delete_node(list_node_t *node) {
    if(!node) return;
    free(node->data);
    free(node);
}

list_t *list_init(void) {
    list_t *list = malloc(sizeof(*list));
    if(!list) return list;
    list->node = new_node(0);
    if(!list->node) {free(list); return NULL;}
    list->size = 0;
    return list;
}

void list_deinit(list_t *list) {
    if(!list) return;
    list_clean(list);
    delete_node(list->node);
    free(list);
}

void list_clean(list_t *list) {
    if(!list) return;
    while(!list_empty(list)) list_delete(list, 0);
}

bool list_insert(list_t *list, size_t index, const void *data, size_t size) {
    if(!list) return false;
    if(index > list_size(list)) return false;
    list_node_t *node = new_node(size);
    if(!node) return false;
    memcpy(node->data, data, node->size);
    list_node_t *current = list->node;
    while(index--) current = current->next;
    node->next = current->next;
    current->next = node;
    ++list->size;
    return true;
}

bool list_delete(list_t *list, size_t index) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t *current = list->node;
    while(index--) current = current->next;
    list_node_t *temp = current->next;
    current->next = temp->next;
    delete_node(temp);
    --list->size;
    return true;
}

bool list_set(list_t *list, size_t index, const void *data, size_t size) {
    if(!list) return false;
    bool res = list_delete(list, index);
    if(!res) return res;
    return list_insert(list, index, data, size);
}

bool list_get(const list_t *list, size_t index, void *data, size_t size) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t *current = GET_NODE(list, index);
    if(!data) return false;
    if(size < current->size) return false;
    memcpy(data, current->data, current->size);
    return true;
}

bool list_append(list_t *list, const void *data, size_t size) {
    if(!list) return false;
    return list_insert(list, list_size(list), data, size);
}

bool list_empty(const list_t *list) {
    if(!list) return true;
    return list->size == 0;
}

size_t list_size(const list_t *list) {
    if(!list) return 0;
    return list->size;
}

list_t *list_union(const list_t *a, const list_t *b) {
    list_t *list = list_init();
    for(size_t i = 0; i < list_size(a); ++i) {
      list_node_t *current = GET_NODE(a, i);
      list_append(list, current->data, current->size);
    }
    for(size_t i = 0; i < list_size(b); ++i) {
      list_node_t *current = GET_NODE(b, i);
      list_append(list, current->data, current->size);
    }
    return list;
}


main.c
#include "list.h"
#include <stdio.h>

typedef struct {
    char c;
    int i;
    double d;
} test_t;

int main(void) {
    list_t *list = list_init();
    {
      test_t t = {'x', 123, 3.14};
      list_append(list, &t.c, sizeof(t.c));
      list_append(list, &t.i, sizeof(t.i));
      list_append(list, &t.d, sizeof(t.d));
      list_append(list, &t, sizeof(t));
    }
    {
      test_t t;
      list_get(list, 0, &t.c, sizeof(t.c));
      list_get(list, 1, &t.i, sizeof(t.i));
      list_get(list, 2, &t.d, sizeof(t.d));
      printf("%c %d %lf\n", t.c, t.i, t.d);
    }
    {
      test_t t;
      list_get(list, 3, &t, sizeof(t));
      printf("%c %d %lf\n", t.c, t.i, t.d);
    }
    {
      double d;
      list_delete(list, 1);
      list_get(list, 1, &d, sizeof(d));
      printf("%lf\n", d);
    }
    {
      char c;
      list_delete(list, 1);
      list_get(list, 0, &c, sizeof(c));
      printf("%c\n", c);
    }
    {
      list_delete(list, 1);
      list_delete(list, 0);
      for(size_t i = 0; i < 10; ++i) {
            list_append(list, &i, sizeof(i));
      }
    }
    {
      size_t i;
      list_get(list, 9, &i, sizeof(i));
      printf("%lu\n", i);
    }
    list_deinit(list);
    {
      list_t *a = list_init();
      list_t *b = list_init();
      for(size_t i = 0; i < 10; ++i) {
            list_append(a, &i, sizeof(i));
      }
      for(size_t i = 100; i < 107; ++i) {
            list_append(b, &i, sizeof(i));
      }
      list_t *c = list_union(a, b);
      for(size_t i = 0; i < list_size(c); ++i) {
            size_t value;
            list_get(c, i, &value, sizeof(value));
            printf("%lu ", value);
      }
      puts("");
      list_deinit(c);
      list_deinit(b);
      list_deinit(a);
    }
    return 0;
}



页: [1]
查看完整版本: 求大神帮忙编程完成合并两循环单链表