数据结构-3（链式存储顺序表）

概念

通常用一个tmp指针来标记定位

头文件

#ifndef _DOUBLE_LINK_LIST
#define _DOUBLE_LINK_LIST

typedef struct preson{
    char name[32];
    char sex;
    int age;
    int score;
}DATATYPE;

typedef enum{
    FORWARD,
    BACKWARD,
}DIRECT;

typedef struct dou_node{
    DATATYPE data;
    struct dou_node *next, *prev;
}double_link_node;

typedef struct list{
    double_link_node *head;
    int clen;
}double_link_list;

typedef int (*pfun)(DATATYPE *data, void *arg);

double_link_list *create_link_list(void);
int insert_head_link_list(double_link_list *list, DATATYPE *data);
int show_link_list(double_link_list *list, DIRECT dire);
double_link_node *find_link_list(double_link_list *list, pfun fun, void *arg);
int delete_link_list(double_link_list *list, pfun fun, void *arg);
int revise_link_list(double_link_list *list, char *name, DATATYPE data);
int destroy_link_list(double_link_list *list);
int insert_tail_link_list(double_link_list *list, DATATYPE *data);
int modify_link_list(double_link_list *list, pfun, void *arg, DATATYPE *data);
int getsize_double_link_list(double_link_list *list);
int insert_pos_link_list(double_link_list *list, DATATYPE *data, int pos);
int isempty_link_list(double_link_list *list);
int clear_link_list(double_link_list *list);
int inverse_link_list(double_link_list *list);

#endif

.c文件

#include <stdio.h>
#include "double_link_list.h"
#include <string.h>
#include <stdlib.h>

double_link_list *create_link_list(void)
{
    double_link_list *link = (double_link_list *)malloc(sizeof(double_link_list));
    if(NULL == link)
    {
        perror("double_link_list fail");
        return NULL;
    }

    link->head = NULL;
    link->clen = 0;
    return link;
}

int insert_head_link_list(double_link_list *list, DATATYPE *data)
{
    double_link_node *newnode = (double_link_node *)malloc(sizeof(double_link_node));
    if(NULL == newnode)
    {
        perror("create newnode fail");
        return -1;
    }
    memcpy(&newnode->data, data, sizeof(DATATYPE));
    newnode->next = NULL;
    newnode->prev = NULL;
    if(NULL == list->head)
    {
        list->head = newnode;
    }
    else
    {
        newnode->next = list->head;
        list->head->prev = newnode;
        list->head = newnode;
    }
    list->clen++;
    return 0;
}

int getsize_double_link_list(double_link_list *list)
{
    return list->clen;
}

int show_link_list(double_link_list *list, DIRECT dire)
{
    int len = getsize_double_link_list(list);
    double_link_node *tmp = list->head;
    int i = 0;
    if(FORWARD == dire)
    {
        for(i = 0; i < len; ++i)
        {
            printf("%s %c %d %d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);
            tmp = tmp->next;
        }
    }
    else
    {
        while(tmp->next)
        {
            tmp=tmp->next;
        }
        for(i = 0; i < len; ++i)
        {
            printf("%s %c %d %d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);
            tmp = tmp->prev;
        }
    }
    return 0;
}

double_link_node *find_link_list(double_link_list *list, pfun fun, void *arg)
{
    int len = getsize_double_link_list(list);
    double_link_node *tmp = list->head;

    int i = 0;
    for(i = 0; i < len; ++i)
    {
        if(fun(&tmp->data,arg))
        {
            return tmp;
        }
        tmp = tmp->next;
    }
    return NULL;
}

int isempty_link_list(double_link_list *list)
{
    return 0 == list->clen;
}

int insert_tail_link_list(double_link_list *list, DATATYPE *data)
{
    double_link_node *tmp = list->head;
    if(isempty_link_list(list))
    {
        return insert_head_link_list(list,data);
    }
    else
    {
        double_link_node *newnode = (double_link_node *)malloc(sizeof(double_link_node));
        if(NULL == newnode)
        {
            perror("create newnode_2 fail");
            return -1;
        }

        memcpy(&newnode->data, data, sizeof(DATATYPE));
        newnode->next = NULL;
        newnode->prev = NULL;
        while(tmp->next)
        {
            tmp = tmp->next;
        }
        newnode->prev = tmp;
        tmp->next = newnode;
    }
    list->clen++;

    return 0;
}

int insert_pos_link_list(double_link_list *list, DATATYPE *data, int pos)
{
    double_link_node *newnode = (double_link_node *)malloc(sizeof(double_link_node));
    if(NULL == newnode)
    {
        perror("creat newnode_3 fail");
        return -1;
    }

    memcpy(&newnode->data, data, sizeof(DATATYPE));
    newnode->next = NULL;
    newnode->prev = NULL;

    double_link_node *tmp = list->head;
    int i = 0;
    for(i = 0; i < pos; ++i)
    {
        tmp = tmp->next;
    }

    newnode->next = tmp;
    newnode->prev = tmp->prev;
    tmp->prev = newnode;
    if(newnode->prev)
    {
        newnode->prev->next = newnode;
    }
    else
    {
        list->head = newnode;
    }

    list->clen++;

    return 0;
}

int delete_link_list(double_link_list *list, pfun fun, void *arg)
{
    double_link_node *tmp = find_link_list(list, fun, arg);
    if(NULL == tmp)
    {
        return -1;
    }

    if(tmp->next)
    {
        tmp->next->prev = tmp->prev;
    }
    if(tmp->prev)
    {
        tmp->prev->next = tmp->next;
    }
    else
    {
        list->head = tmp->next;
    }

    list->clen--;
    free(tmp);

    return 0;
}

int modify_link_list(double_link_list *list, pfun fun, void *arg, DATATYPE *data)
{
    double_link_node *tmp = find_link_list(list, fun, arg);
    if(NULL == tmp)
    {
        return -1;
    }
    memcpy(&tmp->data, data, sizeof(DATATYPE));
    return 0;

}

int clear_link_list(double_link_list *list)
{
    double_link_node *tmp = list->head;
    int len = getsize_double_link_list(list);
    int i = 0;
    for(i = 0; i < len-1; ++i)
    {
        tmp = tmp->next;
        free(tmp->prev);
    }
    free(tmp);
}

int inverse_link_list(double_link_list *list)
{
    double_link_node *tmp = NULL;
    int len = getsize_double_link_list(list);
    int i = 0;
    if(len > 2)
    {
        double_link_node *q;
        for(i = 0; i < len; ++i)
        {
            tmp = list->head;
            list->head = list->head->next;

            q = tmp->prev;
            tmp->prev = tmp->next;
            tmp->next = q;
        }
        list->head = tmp;
    }
    else
    {
        printf("it's not need\n");
    }
    return 0;
}

主函数

#include <stdio.h>
#include "double_link_list.h"
#include <string.h>

int find_name(DATATYPE *data, void *arg)
{
    return 0 == strcmp(data->name, (char *)arg);
}
int main()
{
    double_link_list* link = create_link_list();

    DATATYPE data[]={
        {"zhansan",'m',20,90},
        {"lisi",'f',22,87},
        {"wangmazi",'m',21,93},
        {"guanerge",'m',40,60},
        {"liuei",'m',42,83},
    };

    insert_head_link_list(link, &data[0]);
    insert_head_link_list(link, &data[1]);
    insert_head_link_list(link, &data[2]);

    show_link_list(link, FORWARD);
    printf("----------------------------\n");
    show_link_list(link, BACKWARD);

    double_link_node *ret = find_link_list(link, find_name, "lisi");
    if(NULL == ret)
    {
        printf("can't find\n");
    }
    else
    {
        printf("find it, %s %d\n", ret->data.name, ret->data.score);
    }
    printf("----------------------------\n");
    insert_pos_link_list(link, &data[3], 2);
    show_link_list(link, BACKWARD);
    printf("----------------------------\n");
    
    delete_link_list(link, find_name, "lisi");
    show_link_list(link, BACKWARD);
    printf("------------modify----------------\n");
    
    modify_link_list(link, find_name, "zhansan", &data[4]);
    show_link_list(link, BACKWARD);
    printf("------------inverse----------------\n");
   
    inverse_link_list(link);
    show_link_list(link, BACKWARD);
    printf("------------ii----------------\n");
    clear_link_list(link);
    return 0;
}