|
|
发表于 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
$
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-3-21 23:28:37
置顶卡
千斤顶
显身卡
