# 工学1号馆

home

## 单链表

Wu Yudong    October 18, 2016     Data Structure   718

## 单链表的接口定义：

1、list_init

void list_init(List *list, void (*destroy)(void *data));

2、list_destroy

void list_destroy(List *list);

3、list_ins_next

int list_ins_next(List *list, ListElmt *element, const void *data);

4、list_rem_next

int list_rem_next(List *list, ListElmt *element, void **data);

5、list_size

int list_size(const List *list);

ListElmt *list_head(const List *list);

7、list_tail

ListElmt *list_tail(const List *list) ((list)->tail);

int list_is_head(const ListElmt *element);

9、list_is_tail

int list_is_tail(const ListElmt *element);

10、list_data

void *list_data(const ListElmt *element);

11、list_next

ListElmt *list_next(const ListElmt *element) ;

## 单链表的实现和分析

#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
//为单链表的结点定义一个结构体.
typedef struct ListElmt_ {
void               *data;   //数据域
struct ListElmt_   *next;    //指针域

} ListElmt;

//为单链表定义一个结构体.
typedef struct List_ {
int                size;     //容量
int                (*match)(const void *key1, const void *key2);    //匹配函数
void               (*destroy)(void *data);    //撤销操作
ListElmt           *tail;   //尾指针

} List;

//公共接口
void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_tail(list) ((list)->tail)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)

#endif

void list_init(List *list, void (*destroy)(void *data)) {  //初始化list
list->size = 0;
list->destroy = destroy;   //设置为定义的析构函数
list->tail = NULL;
return;
}

void list_destroy(List *list) {
//移除每一个元素
while (list_size(list) > 0) {
if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {  //不断地移除链表的头结点
list->destroy(data);  //调用一个用户定义的函数来释放动态分配的数据.
}
}
//现在没有操作了,释放结构体作为预防措施
memset(list, 0, sizeof(List));
return;
}

int list_ins_next(List *list, ListElmt *element, const void *data) {
ListElmt *new_element;     //为结点动态分配存储空间
if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)  //假如分配失败
return -1;
// 将元素插入链表
new_element->data = (void *)data;
if (element == NULL) {
//插入到链表的头部
if (list_size(list) == 0)
list->tail = new_element;
} else {
//插入到除了链表头部以外指定的其他地方
if (element->next == NULL)
list->tail = new_element;
new_element->next = element->next;
element->next = new_element;
}
list->size++; //表长增加
return 0;
}

int list_rem_next(List *list, ListElmt *element, void **data) {
ListElmt *old_element;
//不允许从一个空的list中移除元素.
if (list_size(list) == 0)
return -1;
// 从list中移除元素.
if (element == NULL) {
// 移除表头的结点.
if (list_size(list) == 1)   //如果list只有一个元素，则直接删除尾结点
list->tail = NULL;
} else {
// 移除非头结点.
if (element->next == NULL)
return -1;
*data = element->next->data;
old_element = element->next;
element->next = element->next->next;
if (element->next == NULL)  //移除指定结点后，后继为NULL，则用尾结点指向
list->tail = element;
}
//释放分配的抽象数据类型.
free(old_element);
//调整list的长度.           *
list->size--;
return 0;
}

// Completed on 2014.10.22 21:00
// Language: C99
//
// 版权所有（C）wuyudong
// 博客地址：http://www.wuyudong.com/
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

static void print_list(const List *list) {
ListElmt *element;
int *data, i;
fprintf(stdout, "List size is %d\n", list_size(list));
i = 0;
while (1) {
data = list_data(element);
fprintf(stdout, "list[%03d]=%03d\n", i, *data);
i++;
if (list_is_tail(element))
break;
else
element = list_next(element);
}
return;
}

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

List list;
ListElmt *element;
int *data, i;

//初始化list
list_init(&list, free);
for (i = 10; i > 0; i--) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = i;
if (list_ins_next(&list, NULL, data) != 0)  //逐个插入元素
return 1;

}
print_list(&list);    //打印初始list
for (i = 0; i < 7; i++)
element = list_next(element);

data = list_data(element);
fprintf(stdout, "Removing an element after the one containing %03d\n", *data);

if (list_rem_next(&list, element, (void **)&data) != 0)  //删除指定结点
return 1;
print_list(&list);
fprintf(stdout, "Inserting 011 at the tail of the list\n");
*data = 11;
if (list_ins_next(&list, list_tail(&list), data) != 0)   //插入指定结点
return 1;
print_list(&list);
fprintf(stdout, "Removing an element after the first element\n");

if (list_rem_next(&list, element, (void **)&data) != 0)
return 1;

print_list(&list);

fprintf(stdout, "Inserting 012 at the head of the list\n");

*data = 12;
if (list_ins_next(&list, NULL, data) != 0)
return 1;

print_list(&list);

fprintf(stdout, "Iterating and removing the fourth element\n");

element = list_next(element);
element = list_next(element);

if (list_rem_next(&list, element, (void **)&data) != 0)
return 1;

print_list(&list);

fprintf(stdout, "Inserting 013 after the first element\n");

*data = 13;
if (list_ins_next(&list, list_head(&list), data) != 0)
return 1;

print_list(&list);

i = list_is_tail(list_tail(&list));
fprintf(stdout, "Testing list_is_tail...Value=%d (1=OK)\n", i);
fprintf(stdout, "Testing list_is_tail...Value=%d (0=OK)\n", i);

fprintf(stdout, "Destroying the list\n");
list_destroy(&list);
return 0;

}