Linux C 数据结构->双向链表(阴阳在六，何以言九~)

0.  

 弄完了单链表，在看双向链表。怎么整？多写，多想，想不通画出来在想，再写，再模仿~

1.  没啥说的，敲代码~

 说点啥呢，注意自己的代码风格哦，要符合"潮流"，不要独树一帜

 1.1 

 DList.h

#ifndef _DLIST_H_
#define _DLIST_H_

typedef int data_t;

/*节点指针*/
typedef struct node_t * PNode; 

/*表示返回的是地址*/
typedef PNode Position;

/*定义节点类型*/
typedef struct node_t {
    data_t data;    // 数据域
    PNode  prev;    // 前驱指针
    PNode  next;    // 后继指针
}node_t;

/*定义链表类型*/
typedef struct DList {
    PNode head;     // 指向头节点
    PNode tail;     // 指向尾节点
    int size;
}DList;

/*分配值为i的节点 并返回节点地址*/
Position MakeNode(data_t i);

/*释放p所指的节点*/
void FreeNode(PNode p);

/*构建一个空的双向链表*/
DList * InitList();

/*销毁一个双向链表*/
void DestroyList(DList * plist);

/*将一个链表置为空 释放原链表节点空间*/
void ClearList(DList * plist);

/*返回头节点地址*/
Position GetHead(DList * plist);

/*返回尾节点地址*/
Position GetTail(DList * plist);

/*返回链表大小*/
int GetSize(DList * plist);

/*返回p的直接后继位置*/
Position GetNext(Position p);

/*返回p的直接前驱位置*/
Position GetPrev(Position p);

/*将pnode所指的节点插入第一个节点之前*/
PNode InsFirst(DList * plist, PNode pnode);

/*将链表第一个节点删除并返回其地址*/
PNode DelFirst(DList * plist);

/*返回节点的数据项*/
data_t GetData(Position p);

/*设置节点的数据项*/
void SetData(Position p, data_t i);

/*删除链表中的尾节点并返回其地址 改变链表的尾指针指向新的尾节点*/
PNode DelTail(DList * plist);

/*在链表中p位置之前插入节点s*/
PNode InsBefore(DList * plist, Position p, PNode s);

/*在链表中p位置之后插入节点s*/
PNode InsAfter(DList * plist, Position p, PNode s);

/*返回在链表中第i个节点的位置*/
PNode LocatePos(DList * plist, int i);

/*依次对链表中每个元素调用函数visit()*/
void ListTraverse(DList * plist, void (*visit)());

#endif // _DLIST_H_

 DList.c

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

#include "DList.h"

/*分配值为i的节点 并返回节点地址*/
Position 
MakeNode(data_t i)
{
    PNode p = NULL;
    p = (PNode)malloc(sizeof(node_t));  // 给节点分配内存
    if(p!=NULL) {
        p->data = i;
        p->prev = NULL;
        p->next = NULL;
    }
    return p;
}

/*释放p所指的节点*/
void 
FreeNode(PNode p)
{
    free(p);
}

/*构建一个空的双向链表*/
DList * 
InitList()
{
    DList *plist = (DList *)malloc(sizeof(DList));
    PNode head = MakeNode(0);
    if(plist!=NULL) {
        if(head!=NULL) {
            plist->head = head;
            plist->tail = head;
            plist->size = 0;
        } else
            return NULL;
    }
    return plist;
}

/*销毁一个双向链表*/
void 
DestroyList(DList * plist)
{
    ClearList(plist);
    free(GetHead(plist));
    free(plist);   
}

/*判断链表是否为空表*/
int
IsEmpty(DList *plist)
{
    if(GetSize(plist)==0 && GetTail(plist)==GetHead(plist))
        return 1;
    else
        return 0; 
}

/*将一个链表置为空 释放原链表节点空间*/
void 
ClearList(DList * plist)
{
    PNode temp, p;
    
    p = GetTail(plist);
    while(!IsEmpty(plist)) {
        temp = GetPrev(p);
        FreeNode(p);
        p = temp;
        plist->tail = temp;
        plist->size--;
    }
}

/*返回头节点地址*/
Position 
GetHead(DList * plist)
{
    return plist->head;
}

/*返回尾节点地址*/
Position
GetTail(DList * plist)
{
    return plist->tail;
}

/*返回链表大小*/
int 
GetSize(DList * plist)
{
    return plist->size;
}

/*返回p的直接后继位置*/
Position 
GetNext(Position p)
{
    return p->next;
}

/*返回p的直接前驱位置*/
Position 
GetPrev(Position p)
{
    return p->prev;
}

/*将pnode所指的节点插入第一个节点之前*/
PNode 
InsFirst(DList * plist, PNode pnode)
{
    Position head = GetHead(plist);
    
    if(IsEmpty(plist))
        plist->tail = pnode;
    plist->size++;
    
    pnode->next = head->next;
    pnode->prev = head;
    
    if(head->next!=NULL) // 
        head->next->prev = pnode;
    head->next = pnode;
    
    return pnode;
}

/*将链表第一个节点删除并返回其地址*/
PNode 
DelFirst(DList * plist)
{
    Position head = GetHead(plist);
    Position p = head->next;
    
    if(p!=NULL) {
        if(p==GetTail(plist))
            plist->tail = p->prev;
        head->next = p->next;
        head->next->prev = head;
        plist->size--;
    }
        
    return p;
}

/*返回节点的数据项*/
data_t 
GetData(Position p)
{
    return p->data;   
}

/*设置节点的数据项*/
void 
SetData(Position p, data_t i)
{
    p->data = i;
}

/*删除链表中的尾节点并返回其地址 改变链表的尾指针指向新的尾节点*/
PNode 
DelTail(DList * plist)
{
    Position p = NULL;
    if(IsEmpty(plist))
        return NULL;
    else {
        p = GetTail(plist);
        p->prev->next = p->next;
        plist->tail = p->prev;
        plist->size--;
        
        return p;
    }    
}

/*在链表中p位置之前插入节点s*/
PNode 
InsBefore(DList * plist, Position p, PNode s)
{
    s->prev = p->prev;
    s->next = p;
    p->prev->next = s;
    p->prev = s;
    
    plist->size++;
    
    return s;
}

/*在链表中p位置之后插入节点s*/
PNode 
InsAfter(DList * plist, Position p, PNode s)
{
    s->next = p->next;
    s->prev = p;
    
    if(p->next!=NULL)
        p->next->prev = s;
    p->next = s;
    
    if(p == (GetTail(plist)))
        plist->tail = s;
    
    plist->size++;
    return s;
}

/*返回在链表中第i个节点的位置*/
PNode 
LocatePos(DList * plist, int i)
{
    int cnt = 0;
    Position p = GetHead(plist);
    if(i>GetSize(plist) || i<1)
        return 0;
    
    while(++cnt<=i)
        p = p->next;
    
    return p;
}

/*依次对链表中每个元素调用函数visit()*/
void 
ListTraverse(DList * plist, void (*visit)())
{
    Position p = GetHead(plist);
    if(IsEmpty(plist))
        exit(0);
    else {
        while(p->next!=NULL) {
            p = p->next;
            visit(p->data);
        }
    }
    
}

 test.c

#include <stdio.h>
#include "Dlist.h"

void 
print(data_t i)
{
    printf("数据项为 %d
", i);
}

int main(int argc, char * argv[])
{
    DList * plist = NULL;
    PNode p = NULL;
    
    plist = InitList();
    p = InsFirst(plist, MakeNode(1));
    InsBefore(plist, p, MakeNode(2));
    InsAfter(plist, p, MakeNode(3));
    InsAfter(plist, p, MakeNode(11));
    
    printf("p前驱位置的值为 %d
", GetData(GetPrev(p)));
    printf("p位置的值为 %d
", GetData(p));
    printf("p后继位置的值为 %d
", GetData(GetNext(p)));
    
    printf("遍历输出各节点数据项:
");
    ListTraverse(plist, print);
    
    printf("除了头节点该链表共有 %d 个节点
", GetSize(plist));
    
    FreeNode(DelFirst(plist));
    printf("删除了头节点该链表共有 %d 个节点
", GetSize(plist));
    
    printf("删除第一个节点后重新遍历输出为:
");
    ListTraverse(plist, print);
    
    printf("删除了第一个节点后该链表共有 %d 个节点
", GetSize(plist));
    
    printf("销毁链表...
");
    DestroyList(plist);
   
    return 0;
}

 Demo1：Makefile 文件

CC = gcc
CFLAGS = -g -Wall -o2

RUNE = $(CC) $(CFLAGS) $(object) -o $(exe)
RUNO = $(CC) $(CFLAGS) -c $< -o $@ 

.RHONY:clean


object = test.o Dlist.o
exe = Dlist

$(exe):$(object)
    $(RUNE)

%.o:%.c Dlist.h
    $(RUNO)
%.o:%.c
    $(RUNO)


clean:
    -rm -rf *.o Dlist *~~

 运行

1.2  

 double_link.h 

#ifndef _DOUBLE_LINK_H_
#define _DOUBLE_LINK_H_

// 节点类型
typedef struct node_t {
    struct node_t * prev;
    struct node_t * next;
    void * data;
}node_t;


// 新建 双向循环链表.成功,返回0;否则,返回-1
extern int create_dlink();

// 销毁 双向循环链表.成功,返回0;否则,返回-1
extern int destroy_dlink();

// 双向链表是否为空.为空的话返回1;否则，返回0
extern int dlink_is_empty();

// 返回 双向链表的大小
extern int dlink_size();

// 获取 双向链表中第index位置的元素.成功,返回节点指针;否则,返回NULL
extern void * dlink_get(int index);

// 获取 双向链表中第1个元素.成功,返回节点指针;否则,返回NULL
extern void * dlink_get_first();

// 获取 双向链表中最后1个元素.成功,返回节点指针;否则,返回NULL
extern void * dlink_get_last();

// 将value插入到index位置.成功,返回0;否则,返回-1
extern int dlink_insert(int index, void * pval);

// 将value插入到表头位置.成功,返回0;否则,返回-1
extern int dlink_insert_first(void * pval);

// 将value插入到末尾位置.成功,返回0;否则,返回-1
extern int dlink_append_last(void * pval);

// 删除 双向链表中index位置的节点.成功,返回0;否则,返回-1
extern int dlink_delete(int index);

// 删除 第一个节点.成功,返回0;否则,返回-1
extern int dlink_delete_first();

// 删除 最后一个节点.成功,返回0;否则,返回-1
extern int dlink_delete_last();

#endif //_DOUBLE_LINK_H_

 double_link.c

/*******************
 *
 * 双向循环链表实现
 *
 ******************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#include "double_link.h"

// 表头，不存放元素值
static node_t * phead = NULL;

// 节点个数
static int count = 0;



// 创建节点
static node_t * 
create_node(void * pval)
{
    node_t * pnode = NULL;
    pnode = (node_t *)malloc(sizeof(node_t));
    if(NULL == pnode) 
        return NULL;
    // 默认pnode的前一个节点和后一节点都指向它自身
    // 双向循环链表,这里不能将pnode->prev = NULL;pnode->next = NULL;
    pnode->prev = pnode->next = pnode;
    pnode->data = pval;
    
    return pnode;
}


// 新建 双向循环链表。成功，返回0；否则，返回-1
int 
create_dlink()
{
    // 创建头
    phead = create_node(NULL); // 头节点数据域为NULL
    if(!phead)
        return -1;
    // 节点个数为0
    count = 0;
    
    return 0;
}

// 双向链表是否为空 。为空的话返回1；否则，返回0。
int 
dlink_is_empty()
{
    if(count == 0)
        return 1;
    return 0;
}

// 返回 双向链表的大小
int dlink_size()
{
    return count;
}

// 获取 双向链表中第 index 位置的节点
static 
node_t * get_node(int index)
{
    if(index < 0 || index >= count)
        return NULL;
    
    // 正向查找
    if(index <= (count/2)) {
        int i = 0;
        node_t * pnode = phead->next;
        while((i++)<index)
            pnode = pnode->next;
        
        return pnode;
    }
    
    // 反向查找
    int j = 0;
    int rindex = count - index -1;
    node_t * rnode = phead->prev;
    while((j++) < rindex)
        rnode = rnode->prev;
    
    return rnode;
}


// 获取 双向链表中第index位置的元素。成功，返回节点指针；否则，返回NULL。
void * dlink_get(int index)
{
    node_t * pindex = get_node(index);
    if(!pindex)
        return NULL;
    
    return pindex->data;
}

// 获取 双向链表中第1个元素 。成功，返回节点指针；否则，返回NULL。
void * dlink_get_first()
{
    return dlink_get(0);
}

// 获取“双向链表中最后1个元素”。成功，返回节点指针；否则，返回NULL。
void * 
dlink_get_last()
{
    return dlink_get(count-1);
}

// 将“value”插入到index位置。成功，返回0；否则，返回-1。
int 
dlink_insert(int index, void * pval)
{
    // 插入表头
    if(index == 0)
        return dlink_insert_first(pval);
    
    // 获取插入的位置对应的节点
    node_t * pindex = get_node(index);
    if(!pindex)
        return -1;
    
    // 创建 节点
    node_t * pnode = create_node(pval);
    if(!pnode)
        return -1;
    
    pnode->prev = pindex->prev;
    pnode->next = pindex;
    pindex->prev->next = pnode; // pindex 前一个节点的后继指针指向新节点
    pindex->prev = pnode;
    
    count++;
    
    return 0;
}

// 将value 插入到表头位置。成功，返回0；否则，返回-1。
int 
dlink_insert_first(void * pval)
{
    node_t * pnode = create_node(pval);
    if(!pnode)
        return -1;
    
    pnode->prev = phead;
    pnode->next = phead->next;
    phead->next->prev = pnode;
    phead->next = pnode;
    
    count++;
    
    return 0;
}

// 将value 插入到末尾位置。成功，返回0；否则，返回-1。
int 
dlink_append_last(void * pval)
{
    node_t * pnode = create_node(pval);
    if(!pnode)
        return -1;
    
    pnode->prev= phead->prev;
    pnode->next = phead;
    phead->prev->next = pnode;
    phead->prev = pnode;
    
    count++;
    
    return 0;
}

// 删除 双向链表中index位置的节点 。成功，返回0；否则，返回-1
int 
dlink_delete(int index)
{
    node_t * pindex = get_node(index);
    if(!pindex)
        return -1;
    
    pindex->next->prev = pindex->prev;
    pindex->prev->next = pindex->next;
    
    free(pindex);
    count--;
    
    return 0;
}

// 删除第一个节点。成功，返回0；否则，返回-1
int 
dlink_delete_first()
{
    return dlink_delete(0);
}


// 删除 最后一个节点。成功，返回0；否则，返回-1
int
dlink_delete_last()
{
    return dlink_delete(count-1);
}

// 撤销 双向链表 。成功，返回0；否则，返回-1
int 
destroy_dlink()
{
    if(!phead)
        return -1;
    
    node_t * pnode = phead->next;
    node_t * ptmp = NULL;
    
    //遍历节点
    while(pnode!=phead) {
        ptmp = pnode;
        pnode = pnode->next;
        free(ptmp);
    }
    
    free(phead);
    phead = NULL;
    
    count = 0;
    
    return 0;
}

Makefile 套路走起，（代码临摹别人的，makefile要原创的哦，上下长得一样，俗称 套路）

CC = gcc
CFLAGS = -g -Wall -o2

RUNE = $(CC) $(CFLAGS) $(object) -o $(exe)
RUNO = $(CC) $(CFLAGS) -c $< -o $@ 

.RHONY:clean


object = test.o double_link.o
exe = DlinkLoop

$(exe):$(object)
    $(RUNE)

%.o:%.c double_link.h
    $(RUNO)
%.o:%.c
    $(RUNO)


clean:
    -rm -rf *.o DlinkLoop *~~

execute

2. 鸣谢

惯例，感谢二位少侠，Cheers！！！
https://blog.csdn.net/zqixiao_09/article/details/50145661
http://www.cnblogs.com/skywang12345/p/3561803.html

3. 后记

九阴真经 - 总纲-2

五脏六腑之精气，皆上注于目而为之精。精之案为眼，骨之精为瞳子，筋之精为络，其案气之精为白眼，

肌肉之为精为约束，裹撷筋骨血气之精而与脉并为系，上属于脑，后出于项中。故邪中与项，因逢其身

之虚，其人深，则随眼系以入于脑，入手面腼则脑转，脑转则引目系急，目系急则目眩以转矣。邪其精

，其精所中不相比亦则精散，精散则视歧，视歧见两物。

阴阳在六，何以言九。太极生两仪，天地初刨判。六阴已机，逢七归元太素，太素西方金德，阴之清纯

，寒值渊源。

内功心法

第一重诀曰：子午卯酉四正时，归气丹田掌前推。面北背南朝天盘，意随两掌行当中。意注丹田一阳动，

左右回收对两穴。拜佛合什当胸作，真气旋转贯其中。气行任督小周天，温养丹田一柱香。快慢合乎三

十六，九阴神功第一重。

注解：每日子、午、卯、酉四正时，找一阴气重的地方，最好为四高中低。面北而坐，五心朝天，静心

绝虑，意守丹田，到一阳初动之时，双手在胸前合什，指尖朝前。引丹田之气沿督脉上行，任脉下归丹

田。如此待小周天三十六圈。由慢至快。气归丹田后，双掌前推，掌心向前，掌指朝天，气行两掌。双

掌指下垂，掌指朝下，掌心朝下，迅速收回，左手掌心对准气海穴，右手掌心对准命门穴，真气随手式

成螺旋状贯入气海、命门两穴。汇于丹田内。如此意守下丹田一柱香的时间。待此功练有一定功力，能

收发自如，有抗寒之功时可修第二重。