Linux下学C语言——第二十节 数据结构

数据结构"/>

Linux下学C语言——第二十节 数据结构

双向循环链表的实现：

llist.h:

#ifndef LLIST_H__
#define LLIST_H__#define FORWARD 1
#define BACKWARD 2typedef void llist_op(const void *);typedef int llist_cmp(const void *,const void *);struct llist_node_st
{void *data;struct llist_node_st *prev;struct llist_node_st *next;};typedef struct 
{int size;struct llist_node_st head;
}llist;llist *llist_creat(int initsize);int llist_insert(llist *,const void *data , int mode);void llist_travel(llist *, llist_op *);void *llist_find(llist * , const void *key , llist_cmp *);int llist_delete(llist *,const void *key,llist_cmp *);int llist_fetch(llist *,const void *key,llist_cmp *,void *data);void llist_destroy(llist *);#endif

llist.c 

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "llist.h"llist *llist_creat(int initsize)
{llist *new;new = malloc (sizeof(*new));if(new == NULL)return NULL;new ->size = initsize;new ->head.data = NULL;new ->head.prev = &new ->head;new ->head.next = &new ->head;return new; 
}int llist_insert(llist *ptr,const void *data , int mode)
{struct llist_node_st *new;new = malloc(sizeof(*new));if(new == NULL)return -1;new -> data = malloc (ptr->size);if(new -> data == NULL)return -2;memcpy(new->data,data,ptr->size);//*if(mode == FORWARD){new -> prev = &ptr->head;new -> next = ptr ->head.next;}else if(mode == BACKWARD){new ->prev = ptr->head.prev;new ->next = &ptr -> head;}else{return -3;}new ->prev->next = new;new ->next ->prev = new;return 0;
}void llist_travel(llist *ptr,llist_op *op)
{struct llist_node_st *cur;for(cur = ptr ->head.next; cur != &ptr ->head;cur = cur ->next)op(cur ->data);
}static struct llist_node_st * find_(llist *ptr , const void *key ,llist_cmp *cmp)
{struct llist_node_st *cur;for(cur = ptr->head.next;cur != &ptr->head;cur = cur->next){if(cmp(key,cur->data)== 0)break;}return cur;
}void *llist_find(llist * ptr, const void *key , llist_cmp *cmp)
{return find_(ptr,key,cmp)->data;
}int llist_delete(llist *ptr,const void *key,llist_cmp *cmp)
{struct llist_node_st *node;node = find_(ptr, key,cmp);if(node == &ptr->head)return -1;node->prev ->next = node ->next;node->next ->prev = node ->prev;free(node->data);free(node);return 0;
}int llist_fetch(llist *ptr,const void *key,llist_cmp *cmp,void *data)
{struct llist_node_st *node;node = find_(ptr, key , cmp);if(node == &ptr->head)return -1;node->prev ->next = node ->next;node ->next ->prev = node ->prev;if(data != NULL)memcpy(data,node->data,ptr->size);free(node -> data);free(node);return 0;
}void llist_destroy(llist *ptr)
{struct llist_node_st *cur,*next;for(cur = ptr->head.next;cur != &ptr->head; cur = next){next = cur ->next;free(cur ->data);free(cur);}free(ptr);
}

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "llist.h"#define NAME 32
struct score_st 
{int id;char name[NAME];int math;int chinese;
};static void print_s(const void *record)
{const struct score_st *r = record;printf("%d %s %d %d\n",r->id,r->name,r->math,r->chinese);
}static int id_cmp(const void *key,const void *record)
{const int *k = key;const struct score_st *r = record;return (*k - r->id);
}static int name_cmp(const void *key,const void *record)
{const char *k = key;const struct score_st *r = record;return stecmp(*k , r->name);
}int main()
{llist *handler;struct score_st tmp;int i, ret;handler = llist_creat(sizeof(struct score_st));if(handler ==NULL)exit(1);for (i = 0;i < 7;i++){tmp.id = i;snprintf(tmp.name ,NAME ,"std%d",i);tmp.math = rand()%100;tmp.chinese = rand()%100;ret = llist_insert(handler , &tmp, FORWARD);if(ret)exit(1);}llist_travel(handler,print_s);printf("\n\n");int id =3;ret = llist_delete(handler , &id, id_cmp);if(ret)printf("failed\n");llist_travel(handler,print_s);#if 0int id = 3;struct score *data;data = llist_find (handler, &id,id_cmp);if(data == NULL)printf("Can not find\n");elseprint_s(data);
#endifllist_destroy(handler);exit(0);
}

makefile:

all:llist

llist:llist.o main.o
    $(CC) $^ -o $@

clean:
    rm llist *.o -rf

 执行：

[tom@CentOS7 lib1]$ ./llist 
6 std6 90 59
5 std5 62 27
4 std4 49 21
3 std3 86 92
2 std2 93 35
1 std1 77 15
0 std0 83 86

6 std6 90 59
5 std5 62 27
4 std4 49 21
2 std2 93 35
1 std1 77 15
0 std0 83 86

结构体更改：

通用性较强的循环链表的结构体

结构体1：

struct list_node_st

{

    void *data; //指向用户自定义的结构体的空间

    struct llist_node_st *prev;

    struct llist_node_st *next;

}；

结构体2：

struct list_node_st

{

    struct llist_node_st *prev;

    struct llist_node_st *next;

    char data[0];//剩余空间的起始位置

}；

面向对象的实现：

#ifndef LLIST_H__
#define LLIST_H__

#define FORWARD 1
#define BACKWARD 2

typedef void llist_op(const void *);

typedef int llist_cmp(const void *,const void *);

struct llist_node_st
{
    
    struct llist_node_st *prev;
    struct llist_node_st *next;
    char data[0];
};

typedef struct llist_head 
{
    int size;
    struct llist_node_st head;

    int(*insert)(struct llist_head *,const void *,int);
    void *(*find)(struct llist_head *,const void *,llist_cmp *);
    int (*delete)(struct llist_head *,const void *, llist_cmp *);
    int (*fetch)(struct llist_head *,const void *,llist_cmp *,void *);
    void (*travel)(struct llist_head *,llist_op *);
}llist;

llist *llist_creat(int initsize);

void llist_destroy(llist *);

#endif

封装：将结构体写在.c文件中

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#include "llist.h"

struct llist_node_st

{

   

    struct llist_node_st *prev;

    struct llist_node_st *next;

    char data[0];

};

 struct head_st

{

    int size;

    struct llist_node_st head;

};