博客

线性表与链表

  • Post author:
  • Post category:其他


一、线性表介绍

1、线性结构

2、线性表

二、线性表的顺序表示和实现：

三、线性表的链式表示和实现

1、不带头节点的单向链表

2、带头节点的单向链表

常考的笔试题：

1、逆序链表、反转链表。

2、找到环型链表的入口。

3、寻找Y型链表的入口。

4、访问链表的倒数第k个节点。

四、双向链表

五、双向循环链表

六、Linux内核链表

七、通用链表

一、线性表介绍

1、线性结构

在数据元素的非空有限集中：

  • 存在唯一的一个被称做“第一个”的数据元素

  • 存在唯一的一个被称做“最后一个”的数据元素

  • 除第一个之外，集合中的每个数据元素均只有一个前驱

  • 除最后一个之外，集合中的每个数据元素均只有一个后继

2、线性表

线性表是n个数据元素的有限序列，同一线性表中的元素必定具有相同特性，相阾的数据元素之间存在着序偶关系。

线性表中元素的个数n(n>=0)定义为线性表的长度，0==n时称为空表，在非空表中每个数据元素都有一个确定的位置(下标)。

线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。

二、线性表的顺序表示和实现：

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define TYPE int
​
// 设计数据结构
typedef struct Array
{
    TYPE* base; // 存储元素的基址
    size_t cnt; // 元素的数量
    size_t cap; // 表的容量
}Array;
​
// 创建线性表,调用者需要提供容量参数，成功返回线性表指针
Array* creat_array(size_t cap)
{
    // 为线性表创建内存空间
    Array* array = malloc(sizeof(Array));
    // 创建存储元素的内存空间
    array->base = malloc(sizeof(TYPE)*cap);
    // 初始化数量成员
    array->cnt = 0;
    // 备份线性表的容量
    array->cap = cap;
    // 返回线性表指针
    return array;
}
​
// 销毁线性表,调用者只需要提供线性表指针即可
void destory_array(Array* array)
{
    // 释放存储元素的内存空间
    free(array->base);
    // 释放线性表内存空间
    free(array);
}
​
// 清理所有元素
void clear_array(Array* array)
{
    array->cnt = 0;
}
​
// 判断线性表是否是空表
bool empty_array(Array* array)
{
    return 0 == array->cnt;
}
​
// 求线性表的长度
size_t length_array(Array* array)
{
    return array->cnt;
}
​
// 访问指定位置的元素
bool get_array(Array* array,int index,TYPE* elemp)
{
    if(index >= array->cnt)
        return false;
​
    *elemp = array->base[index];
    return true;
}
​
// 在末尾添加元素
void add_back_array(Array* array,TYPE elem)
{
    // 容量如果不够用
    if(array->cnt >= array->cap)
    {
        // 容量扩展两倍
        array->cap *= 2;
        // 元素存储空间扩展两倍
        array->base = realloc(array->base,sizeof(TYPE)*array->cap);
    }
​
    // 末尾添加元素
    array->base[array->cnt++] = elem;
}
​
// 插入元素
bool insert_array(Array* array,int index,TYPE elem)
{
    // 如果下标不合法则插入失败
    if(index >= array->cnt)
        return false;
​
    // 把最后一个元素添加到末尾
    add_back_array(array,array->base[array->cnt-1]);
​
    // 线性表的顺序存储才可以使用
    memmove(array->base+index+1,array->base+index,sizeof(TYPE)*(array->cnt-index-2));
    
    array->base[index] = elem;
    return true;
}
​
// 删除元素，按位置删除
bool delete_index_array(Array* array,int index)
{
    if(index >= array->cnt)
        return false;
​
    memmove(array->base+index,array->base+index+1,sizeof(TYPE)*(array->cnt-index-1));
    array->cnt--;
    return true;
}
​
// 查询元素
int query_array(Array* array,TYPE elem,int (*compare)(const void*,const void*))
{
    for(int i=array->cnt-1; i>=0; i--)
    {
        if(!compare(&elem,array->base+i))
            return i;
    }
    return -1;
}
​
// 删除元素，按值删除
bool delete_value_array(Array* array,TYPE elem,int (*compare)(const void*,const void*))
{
    return delete_index_array(array,query_array(array,elem,compare));
}
​
// 对线性表进行排序
void sort_array(Array* array,int (*compare)(const void*,const void*))
{
    bool flag = true;
    for(int i=array->cnt-1; flag && i>0; i--)
    {
        flag = false;
        for(int j=0; j<i; j++)
        {
            if(1 == compare(array->base+j,array->base+j+1))
            {
                TYPE tmp = array->base[j];
                array->base[j] = array->base[j+1];
                array->base[j+1] = tmp;
                flag = true;
            }
        }
    }
}
​
// 遍历线性表,只是为了测试
void show_array(Array* array)
{
    for(int i=0; i<array->cnt; i++)
    {
        printf("%d ",array->base[i]);
    }
    printf("\n");
}
​
int main(int argc,const char* argv[])
{
    Array* array = creat_array(10);
    for(int i=0; i<10; i++)
    {
        add_back_array(array,rand()%100);
    }
    
    show_array(array);
​
    int intcmp(const void* p1,const void* p2)
    {
        if(*(int*)p1 > *(int*)p2)
            return 1;
        if(*(int*)p1 < *(int*)p2)
            return -1;
        return 0;
​
    }
    
    delete_value_array(array,77,intcmp);
​
    sort_array(array,intcmp);
    
    show_array(array);
    destory_array(array);
    return 0;
}


作业：

把顺序线性表的成员指针实现方式改为柔性数组。 

// 设计数据结构
typedef struct Array
{
    size_t cnt;     // 元素的数量
    size_t cap;     // 表的容量
    TYPE base[];    // 存储元素的柔性数组
}Array;
​
// 创建线性表,调用者需要提供容量参数，成功返回线性表指针
Array* creat_array(size_t cap)
{
    // 为线性表创建内存空间
    Array* array = malloc(sizeof(Array)+sizeof(TYPE)*cap);
    // 初始化数量成员
    array->cnt = 0;
    // 备份线性表的容量
    array->cap = cap;
    // 返回线性表指针
    return array;
}
​
// 销毁线性表,调用者只需要提供线性表指针即可
void destory_array(Array* array)
{
    // 释放线性表内存空间
    free(array);
}
​
// 在末尾添加元素
void add_back_array(Array* array,TYPE elem)
{
    // 容量如果不够用
    if(array->cnt >= array->cap)
    {
        // 容量扩展两倍
        array->cap *= 2;
        // 元素存储空间扩展两倍
        array = realloc(array,sizeof(Array)+sizeof(TYPE)*array->cap);
    }
​
    // 末尾添加元素
    array->base[array->cnt++] = elem;
}

三、线性表的链式表示和实现

线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中的任一元素，它的存储位置可以用一个简单、直观的公式来表示。

这个特点也铸成了这种存储结构的缺点：在插入、删除操作时，需要移动大量的元素。而线性表的另一种表示方法——链存储结构刚好弥补了它的缺点。

链存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所有具有的缺点，但同时也失去了顺序存储结构可随机存取的优点。

链存储结构的特点是元素可以使用存储内存中的任何位置（可以是连续的，也可以不连续），元素a[i]和a[i+1]的逻辑关系不依靠相对位置，而是元素中增加一个指示其后继元素的数据（元素指针），元素本身的数据+后继信息构成了存储映像，俗称节点(node)。 

typedef struct Node
{
    TYPE data;  // 数据域
    struct Node* next;  // 指针域
}Node;

若干个元素节点通过指针域连接起来，形成的线性表结构称为链式表，简称链表，节点中只有一个指向后继元素的指针域，这种链表也被称为单向链表。

单向链表必须有一个指向第一个节点的指针，被称为头指针，被它指向的节点也被称为头节点，头节点可以不存储数据，单纯的作为一个占位节点，最后一个节点指向空，作为结束标志。

1、不带头节点的单向链表 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
​
typedef struct Node
{
    TYPE data;
    struct Node* next;
}Node;
​
// 创建节点
Node* create_node(TYPE data)
{
    // 创建节点内存
    Node* node = malloc(sizeof(Node));
    // 赋值数据域
    node->data = data;
    // 初始化指针域
    node->next = NULL;
    return node;
}
​
// 头添加元素
void front_list(Node** head,TYPE data)
{
    // 创建节点
    Node* node = create_node(data);
    node->next = *head;
    *head = node;
}
​
// 删除元素
bool delete_index_list(Node** head,int index)
{
    // 删除每个节点，因为第一个节点没有前驱
    if(0 == index)
    {
        Node* node = *head;
        *head = (*head)->next;
        free(node);
        return true;
    }
​
    // 找到要删除的节点的前驱
    Node* prev = *head;
    while(NULL!=prev->next && index-->1)
            prev = prev->next;
​
    if(NULL != prev->next)
    {
        // 备份要删除的节点
        Node* node = prev->next;
        // 前驱节点的指针域指向后继节点
        prev->next = prev->next->next;
        free(node);
        return true;
    }
​
    return false;
}
​
// 插入元素
bool insert_list(Node** head,int index,TYPE data)
{
    Node* node = create_node(data);
    if(0 == index)
    {
        node->next = *head;
        *head = node;
        return true;
    }
​
    Node* prev = *head;
    while(NULL!=prev->next && index-->1)
            prev = prev->next;
​
    if(NULL != prev->next)
    {
        node->next = prev->next;
        prev->next = node;
        return true;
    }
​
    return false;
}
​
// 遍历链表
void show_list(Node* head)
{
    for(Node* n=head; NULL!=n; n=n->next)
    {
        printf("%d ",n->data);
    }
    printf("\n");
}
​
int main(int argc,const char* argv[])
{
    // 创建头指针
    Node* head = NULL;
    for(int i=0; i<10; i++)
    {
        front_list(&head,i);
    }
    show_list(head);
    delete_index_list(&head,9);
    insert_list(&head,9,100);
    show_list(head);
    return 0;
}

2、带头节点的单向链表

在执行链表的插入、删除操作时，需要被操作节点的前驱节点和后继节点，如果被操作节点是头节点，则它没有前驱节点，需要额外特殊处理，因此为了方便插入和删除操作所以给单链表增加一个空的头节点。 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
​
#define TYPE int
​
typedef struct Node
{
    TYPE data;
    struct Node* next;
}Node;
​
// 创建节点
Node* create_node(TYPE data)
{
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}
​
​
static bool _insert_list(Node* prev,TYPE data)
{
    if(NULL == prev)
        return false;
        
    Node* node = create_node(data);
    node->next = prev->next;
    prev->next = node;
    return true;
}
​
// 根据前驱节点删除节点
static bool _delete_list(Node* prev)
{
    if(NULL == prev || NULL == prev->next)
        return false;
​
    Node* node = prev->next;
    prev->next = node->next;
    free(node);
    return true;
}
​
// 返回index下标的前驱节点
static Node* _index_list(Node* head,int index)
{
    // 找下标为i的节点的前驱
    Node* prev = head;
    while(NULL != prev->next && index-- >= 1)
        prev = prev->next;
​
    // index 非法，超出了节点的数量
    if(NULL == prev->next || index < -1)
        return NULL;
​
    return prev;
}
​
// 查询出值为data的前驱节点
static Node* _query_list(Node* head,TYPE data)
{
    Node* prev = head;
    while(NULL != prev->next && data != prev->next->data)
        prev = prev->next;
​
    if(NULL == prev->next)
        return NULL;
​
    return prev;
}
​
// 创建带头的空链表
Node* create_list(void)
{
    Node* node = malloc(sizeof(Node));
    node->next = NULL;
    return node;
}
​
// 销毁链表
void destory_list(Node* head)
{
    while(NULL != head)
    {
        Node* node = head;
        head = head->next;
        free(node);
    }
}
​
// 在头部添加元素
void front_list(Node* head,TYPE data)
{
    _insert_list(head,data);
}
​
// 在指定位置插入元素
bool insert_list(Node* head,int index,TYPE data)
{
    return _insert_list(_index_list(head,index),data);
}
​
// 删除指定位置的元素
bool delete_index_list(Node* head,int index)
{
    return _delete_list(_index_list(head,index));
}
​
// 按值删除元素
bool delete_value_list(Node* head,TYPE data)
{
    return _delete_list(_query_list(head,data));
}
​
// 按值修改
bool modify_value_list(Node* head,TYPE old,TYPE new)
{
    Node* prev = _query_list(head,old);
    if(NULL == prev)
        return false;
​
    prev->next->data = new;
    return true;
}
​
// 按位置修改
bool modify_index_list(Node* head,int index,TYPE new)
{
    Node* prev = _index_list(head,index);
    if(NULL == prev)
        return false;
​
    prev->next->data = new;
    return true;
}
​
// 访问指定位置的元素
bool get_list(Node* head,int index,TYPE* data)
{
    Node* prev = _index_list(head,index);
    if(NULL == prev)
        return false;
​
    *data = prev->next->data;
    return true;
}
​
// 查询元素
int query_list(Node* head,TYPE key)
{
    int index = 0;
    for(Node* n=head->next; NULL!=n; n=n->next)
    {
        if(n->data == key)
            return index;
        index++;
    }
    
    return -1;
}
​
// 经典排序
void sort_list(Node* head)
{
    for(Node* i=head->next; NULL!=i->next; i=i->next)
    {
        for(Node* j=i->next; NULL!=j; j=j->next)
        {
            if(i->data > j->data)
            {
                TYPE tmp = i->data;
                i->data = j->data;
                j->data = tmp;
            }
        }
    }
}
​
void show_list(Node* head)
{
    // 要跳过头节点
    for(Node* n=head->next; NULL!=n; n=n->next)
    {
        printf("%d ",n->data);
    }
    printf("\n");
}
​
int main(int argc,const char* argv[])
{
    Node* list = create_list();
    for(int i=0; i<10; i++)
    {
        front_list(list,rand()%100);
    }
    show_list(list);
    //delete_index_list(list,-1);
    //delete_value_list(list,9);
    insert_list(list,9,100);
    sort_list(list);
    show_list(list);
    return 0;
}

常考的笔试题：

1、逆序链表、反转链表。 

void reverse_list(Node* head)
{
    Node *n1 = NULL , *n2 = head->next;
    while(NULL != n2)
    {
        Node* n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
​
    head->next = n1;
}

2、找到环型链表的入口。 

Node* in_ring_list(Node* head)
{
    Node* n1 = head->next;
    Node* n2 = head->next;
​
    while(NULL != n2 && NULL != n2->next)
    {
        n1 = n1->next;
        n2 = n2->next->next;
        if(n1 == n2)
            break;
    }
​
    if(NULL == n2 || NULL == n2->next)
        return NULL;
​
    n1 = head->next;
    while(n1 != n2)
    {
        n1 = n1->next;
        n2 = n2->next;
    }
​
    return n1;
}
​
Node* in_ring_list(Node* head)
{
    Node* node = head->next->next;
​
    while(NULL != node)
    {
        Node* in = head->next;
​
        do{
            if(in == node->next)
                return in;
            in = in->next;
        }while(in != node);
​
        node = node->next;
    }
​
    return NULL;
}

3、寻找Y型链表的入口。 

Node* in_y_list(Node* head1,Node* head2)
{
    int len1 = length_list(head1);
    int len2 = length_list(head2);
​
    int n = abs(len1-len2);
    while(n--)
    {
        if(len1 > len2)
            head1 = head1->next;
        else
            head2 = head2->next;
    }
​
    while(NULL!=head1 && NULL!=head2)
    {
        if(head1 == head2)
            return head1;
​
        head1 = head1->next;
        head2 = head2->next;
    }
​
    return NULL;
}
​
Node* in_y_list(Node* head1,Node* head2)
{
    Node *n1 = head1->next , *n2 = head2->next;
    while(n1 != n2)
    {
        n1 = NULL==n1 ? head2->next : n1->next;
        n2 = NULL==n2 ? head1->next : n2->next;
    }
​
    return n1;
}

4、访问链表的倒数第k个节点。 

Node* get_tail_k(Node* head,int k)
{
    size_t len = length_list(head);
    if(k > len)
        return NULL;

    Node* node = head->next;
    for(int i=0; i<len-k; i++)
    {   
        node = node->next;
    }   

    return node;
}

Node* get_tail_k(Node* head,int k)
{
    Node* n1 = head->next;
    for(int i=0; i<k; i++)
    {
        if(NULL == n1)
            return NULL;
        n1 = n1->next;
    }

    Node* n2 = head->next;
    while(NULL!=n1 && NULL!=n2)
    {
        n1 = n1->next;
        n2 = n2->next;
    }
    return n2;
}

四、双向链表

所谓的双向链表就是链表节点中有两个指针域，一个指向前一个节点，叫前驱指针一般取名为prev，另一个指向后一个节点，叫后继指针，一般取名为next，双向链表的优点是可以从后向前遍历链表，对于链表后半部分的节点的访问效率大大提升。

根据之前的经验，当从前往后操作链表时，有一个空的头节点，方便操作，但现在我们需要从后往前操作链表，所以也需要一个空的尾节点。 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

// 双向链表节点
typedef struct Node
{
	struct Node* prev;	// 前驱指针域
	TYPE data;			// 数据域
	struct Node* next;	// 后继指针域
}Node;

// 创建节点
Node* create_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data = data;
	node->prev = NULL;
	node->next = NULL;
	return node;
}

typedef struct DoubleList
{
	Node* head;
	Node* tail;
	size_t size;
}DoubleList;

void _insert_list(Node* prev,Node* next,TYPE data)
{
	Node* node = create_node(data);
	node->next = next;
	node->prev = prev;
	prev->next = node;
	next->prev = node;
}

// 创建链表
DoubleList* create_list(void)
{
	DoubleList* list = malloc(sizeof(DoubleList));
	list->head = malloc(sizeof(Node));
	list->tail = malloc(sizeof(Node));
	list->head->prev = list->tail->next = NULL;
	list->head->next = list->tail;
	list->tail->prev = list->head;
	list->size = 0;
	return list;
}

// 销毁链表
void destroy_list(DoubleList* list)
{
	Node* node = list->tail;
	while(NULL!=node)
	{
		Node* temp = node;
		node = node->prev;
		free(temp);
	}
}

// 头添加
void add_head_list(DoubleList* list,TYPE data)
{
	_insert_list(list->head,list->head->next,data);
	list->size++;
}

// 尾添加
void add_tail_list(DoubleList* list,TYPE data)
{
	_insert_list(list->tail->prev,list->tail,data);
	list->size++;
}

// 遍历
void show_list(DoubleList* list)
{
	for(Node* n=list->head->next; n!=list->tail; n=n->next)
	{
		printf("%d ",n->data);
	}
	printf("\n");
	for(Node* n=list->tail->prev; n!=list->head; n=n->prev)
	{
		printf("%d ",n->data);
	}
	printf("\n");
}

// 判断链表是否是空表
bool empty_list(DoubleList* list)
{
	return 0 == list->size;
}

void _del_list(Node* node)
{
	Node* prev = node->prev;
	Node* next = node->next;
	prev->next = next;
	next->prev = prev;
	free(node);
}

// 头删除
bool del_head_list(DoubleList* list)
{
	if(empty_list(list))
		return false;

	_del_list(list->head->next);
	list->size--;
	return true;
}

// 尾删除
bool del_tail_list(DoubleList* list)
{
	if(empty_list(list))
		return false;
	
	_del_list(list->tail->prev);
	list->size--;
	return true;
}

Node* _index_list(DoubleList* list,int index)
{
	if(index >= list->size)
		return NULL;
	
	if(index < list->size/2)
	{
		Node* node = list->head->next;
		while(index--)
			node = node->next;
		return node;
	}
	else
	{
		Node* node = list->tail->prev;
		while(list->size > ++index)
			node = node->prev;
		return node;
	}
}

// 指定位置插入
bool insert_index_list(DoubleList* list,int index,TYPE data)
{
	Node* node = _index_list(list,index);
	if(NULL == node)
		return false;

	_insert_list(node->prev,node,data);
	list->size++;
	return true;
}

// 指定位置删除
bool del_index_list(DoubleList* list,int index)
{
	Node* node = _index_list(list,index);
	if(NULL == node)
		return false;

	_del_list(node);
	list->size--;
	return true;

}

// 查询
Node* query_list(DoubleList* list,TYPE data)
{
	Node* left = list->head , *right = list->tail;
	do{
		left = left->next;
		right = right->prev;
		if(data == left->data)
			return left;
		if(data == right->data)
			return right;
	}while(left != right && left->next != right);
	return NULL;
}

// 指定值删除
bool del_value_list(DoubleList* list,TYPE data)
{
	Node* node = query_list(list,data);
	if(NULL == node)
		return false;
	
	_del_list(node);
	list->size--;
	return true;
}

// 修改指定位置的值
bool modify_index_list(DoubleList* list,int index,TYPE data)
{
	Node* node = _index_list(list,index);
	if(NULL == node)
		return false;

	node->data = data;
	return true;
}

// 修改指定值的值
bool modify_value_list(DoubleList* list,TYPE old,TYPE data)
{
	Node* node = query_list(list,old);
	if(NULL == node)
		return false;
	
	node->data = data;
	return true;
}


// 排序
void sort_list(DoubleList* list)
{
	/* 
	// 冒泡排序
	bool flag = true;
	for(Node* r=list->tail->prev; flag && r!=list->head->next; r=r->prev)
	{
		flag = false;
		for(Node* l=list->head->next; l!=r; l=l->next)
		{
			if(l->data > l->next->data)
			{
				TYPE temp = l->data;
				l->data = l->next->data;
				l->next->data = temp;
				flag = true;
			}
		}
	}*/

	// 插入排序
	for(Node* i=list->head->next->next,*j; i!=list->tail; i=i->next)
	{
		TYPE data = i->data;
		for(j=i; j!=list->head->next && data < j->prev->data; j=j->prev)
		{
			j->data = j->prev->data;
		}
		j->data = data;
	}
}

int main(int argc,const char* argv[])
{
	DoubleList* list = create_list();
	for(int i=0; i<10; i++)
	{
		add_head_list(list,rand()%100);
	}
	sort_list(list);
	show_list(list);
	/*
	show_list(list);
	del_head_list(list);
	show_list(list);
	del_tail_list(list);
	show_list(list);
	*/
	return 0;
}

五、双向循环链表

所谓的双向循环链表就是头节点的前驱是尾节点，头节点是尾节点的后继，这样的好处是可以让头节点、尾节点共用一个空白节点，有些奇怪的是当链表空时，空白节点的前驱和后继指针都指向自己，操作双向循环链表时，不存在空指针，以下是有修改代码，其它代码与双向链表没有区别。 

// 创建节点
Node* create_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data = data;
	node->prev = node;
	node->next = node;
	return node;
}

typedef struct DoubleList
{
	Node* head;
	Node* tail;
	size_t size;
}DoubleList;

// 创建链表
DoubleList* create_list(void)
{
	TYPE data;
	DoubleList* list = malloc(sizeof(DoubleList));
	list->head = list->tail = create_node(data);
	list->size = 0;
	return list;
}

// 销毁链表
void destroy_list(DoubleList* list)
{
	Node* node = list->tail;
	do{
		Node* temp = node;
		node = node->prev;
		free(temp);
	}while(node!=list->head);
}

六、Linux内核链表

在Linux 内核中有一种通用的双向循环链表，链表要想做到通用，就无法知道节点中存储什么类型数据，所以就无法明确链表的节点。而面对这 样的问题Linux 内核中的链表的节点struct list_head只设计指针域，也就是节点中只有前驱、后续指针，Linux 内核中的链表只负责这些节点连接起来。

链表的使用者自己设计结构体，结构体中要包含struct list_head类型的节点成员，在链表接口时只需要提供节点成员的地址即可。 

struct list_head {
	struct list_head *next, *prev;
};

typedef struct Student
{
    int id; 
    char name[20];
    char sex;
    float score;
    struct list_head node;
}Student;

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

int main(int argc,const char* argv[])
{
    struct list_head* list = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(list);

    for(int i=0; i<10; i++)
    {
        Student* stup = malloc(sizeof(Student));
        stup->id = 10011+i;
        sprintf(stup->name,"hehe%d",i+1);
        stup->sex = rand()%2 ? 'w' :'m';
        stup->score = rand()%100;
        
        list_add(&stup->node,list);
    }
}

遍历链表时只能使用节点成员指针遍历，所以必须有一个工具，可以根据节点成员地址访问到它所在的结构体。 

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

//1、假定0地址是结构体变量的地址，然后使用 -> 访问 struct list_head类型的成员，然后使用&地址计算出struct list_head类型的成员在结构体中的第几个字节，然后把地址转换成整数。
(unsigned long)(&((type *)0)->member)

//2、把struct list_head类型的成员的地址转换成进步值为1的char*类型，然后再减去struct list_head类型的成员到结构体开头的距离，就计算出结构变量首地址，然后再强制转换成结构体类型的地址
(char *)(ptr)

七、通用链表

Linux内核链表设计的很好，但是不利于初学者使用，另一种通用的设计思路就是借助void*兼容性，设计一种通用链表，但需要使用到回调函数。 

#ifndef LIST_H
#define LIST_H
#include <stdio.h>
#include <stdbool.h>

// 链表节点结构体
typedef struct Node
{
	void* ptr;
	struct Node* prev;
	struct Node* next;
}Node;


// 链表结构体
typedef struct List
{
	Node* head;
	size_t size;
}List;

// 创建节点
Node* create_node(void* ptr);

// 创建链表
List* create_list(void);

// 销毁链表
void destroy_list(List* list);

// 清理链表所有节点
void clear_list(List* list);

// 头添加
void add_list(List* list,void* ptr);

// 尾添加
void add_tail_list(List* list,void* ptr);

// 判断是否是空表
bool empty_list(List* list);

// 头删除
bool del_list(List* list);

// 尾删除
bool del_tail_list(List* list);

// 指定位置添加
bool inset_list(List* list,int index,void* ptr);

// 指定位置删除
bool del_index_list(List* list,int index);

// 访问指定位置的节点
void* get_list(List* list,int index);

// 指定值删除
bool del_value_list(List* list,void* ptr,int (*comper)(const void*,const void*));

// 查询
void* query_list(List* list,void* ptr,int (*comper)(const void*,const void*));
// 排序
void sort_list(List* list,void* ptr,int (*comper)(const void*,const void*));
// 遍历
void fput_list(List* list,void (*fput_ptr)(FILE*,const void*),FILE* fp);

#endif//LIST_H
#include "list.h"
#include <stdlib.h>

static void _add_list(Node* node,Node* prev,Node* next)
{
	next->prev = node;
	node->next = next;
	node->prev = prev;
	prev->next = node;
}

static void _del_list(Node* node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;
	free(node);
}

static Node* _index_list(List* list,int index)
{
	if(index < list->size/2)
	{
		Node* node = list->head->next;
		for(int i=0; i<index; i++)
			node = node->next;
		return node;
	}
	
	Node* node = list->head->prev;
	for(int i=index; i<list->size-1; i++)
		node = node->prev;
	return node;
}

// 创建节点
Node* create_node(void* ptr)
{
	Node* node = malloc(sizeof(Node));
	node->ptr = ptr;
	node->next = node;
	node->prev = node;
	return node;
}

// 创建链表
List* create_list(void)
{
	List* list = malloc(sizeof(List));
	list->head = create_node(NULL);
	list->size = 0;
	return list;
}

// 销毁链表
void destroy_list(List* list)
{
	Node* node = list->head;
	do{
		Node* temp = node;
		node = node->next;
		free(temp);
	}while(node != list->head);
	
	free(list);
}

// 清理链表所有节点
void clear_list(List* list)
{
	Node* node = list->head->next;
	do{
		Node* temp = node;
		node = node->next;
		free(temp);
	}while(node != list->head);
	
	list->head->next = list->head;
	list->head->prev = list->head;
	list->size = 0;
}

// 头添加
void add_list(List* list,void* ptr)
{
	_add_list(create_node(ptr),list->head,list->head->next);
	list->size++;
}

// 尾添加
void add_tail_list(List* list,void* ptr)
{
	_add_list(create_node(ptr),list->head->prev,list->head);
	list->size++;
}

// 判断是否是空表
bool empty_list(List* list)
{
	return list->head->next == list->head;
}

// 头删除
bool del_list(List* list)
{
	if(empty_list(list))
		return false;
	
	_del_list(list->head->next);
	list->size--;
	return true;
}

// 尾删除
bool del_tail_list(List* list)
{
	if(empty_list(list))
		return false;
	
	_del_list(list->head->prev);
	list->size--;
	return true;
}

// 指定位置添加
bool inset_list(List* list,int index,void* ptr)
{
	if(index >= list->size)
		return false;

	Node* node = _index_list(list,index);
	_add_list(create_node(ptr),node->prev,node);
	list->size++;
	return true;
}

// 指定位置删除
bool del_index_list(List* list,int index)
{
	if(index >= list->size)
		return false;

	_del_list(_index_list(list,index));
	list->size--;
	return true;
}

// 指定值删除
bool del_value_list(List* list,void* ptr,int (*comper)(const void*,const void*))
{
	Node* node = list->head->next;
	while(node != list->head)
	{
		if(0 == comper(node->ptr,ptr))
		{
			_del_list(node);
			list->size--;
			return true;
		}
		node = node->next;
	}
	return false;
}

// 访问指定位置的节点
void* get_list(List* list,int index)
{
	if(index >= list->size)
		return NULL;

	return _index_list(list,index)->ptr;
}

// 查询
void* query_list(List* list,void* ptr,int (*comper)(const void*,const void*))
{
	Node* node = list->head->next;
	while(node != list->head)
	{
		if(0 == comper(node->ptr,ptr))
			return node->ptr;
		node = node->next;
	}
}

// 排序
void sort_list(List* list,void* ptr,int (*comper)(const void*,const void*))
{
	bool flag = true;
	for(Node* r=list->head->prev; flag && r!=list->head->next; r=r->prev)
	{
		flag = false;
		for(Node* l=list->head->next; l!=r; l=l->next)
		{
			if(1 == comper(l->ptr,l->next->ptr))
			{
				void* tmp = l->ptr;
				l->ptr = l->next->ptr;
				l->next->ptr = tmp;
				flag = true;
			}
		}
	}
}

// 遍历
void fput_list(List* list,void (*fput_ptr)(FILE*,const void*),FILE* fp)
{
	Node* node = list->head->next;
	while(node != list->head)
	{
		fput_ptr(fp,node->ptr);
		node = node->next;
	}
}

#include <string.h>
typedef struct Admin{
	int id;
	char pwd[7];
}Admin;

int admin_login(const void* p1,const void* p2)
{
	Admin *a1 = (Admin*)p1,*a2 = (Admin*)p2;
	if(a1->id == a2->id && strcmp(a1->pwd,a2->pwd))
		return 0;
	return -1;
}

int admin_del(const void* p1,const void* p2)
{
	Admin *a1 = (Admin*)p1,*a2 = (Admin*)p2;
	if(a1->id > a2->id)
		return 1;
	if(a1->id < a2->id)
		return -1;
	return 0;
}

void put_admin(FILE* fp,const void* ptr)
{
	Admin *admin = (Admin*)ptr;
	fprintf(fp,"%d %s\n",admin->id,admin->pwd);
}

int main()
{
	List* list = create_list();
	for(int i=0; i<10; i++)
	{
		Admin* admin = malloc(sizeof(Admin));
		admin->id = 10010+i;
		sprintf(admin->pwd,"123456");
		add_tail_list(list,admin);
	}

	Admin m = {10017,"123456"};
	del_value_list(list,&m,admin_del);

	/*
	Admin m = {10017,"123456"};
	if(NULL == query_list(list,&m,admin_login))
		printf("用户名或密码错误\n");
	else
		printf("登录成功!\n");
	*/
	fput_list(list,put_admin,fopen("admin.txt","w"));
}


版权声明：本文为weixin_52744725原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。