c 语言双向链表排序,C实现的可排序的双向链表

今天用C实现了一个双向链表，这个链表有排序功能，默认按升序排列，接受的参数可以是数字，也可以是字符串。现在把自己写的代码，分享出来。

头文件：

#define DOUBLE_LINK_H_INCLUDED

//双向链表节点

typedef struct Double_Node

{

struct Double_Node* next;

struct Double_Node* pre;

const void* value;//注意，此处声明为const,是考虑到了字符常量

} node;

//判断链表是否为空

extern bool dlink_is_empty();

//链表的大小

extern int dlink_size();

//比较节点值的大小,仅限于数字和字符串

extern int compare(const void* a,const void* b);

//将"value"插入到链表,成功返回0,否则返回-1

extern int dlink_insert(const void *pval);

//返回链表的第一个元素

extern node* peek();

//取出链表的第一个元素,free操作，在poll方法后，不能忘记，否则，会内存泄漏

extern node* poll();

#endif // DOUBLE_LINK_H_INCLUDED

#include #include #include #include #include #include #include "double_link.h" using namespace std;

//链表头部 static node* head = NULL; static node* tail = NULL; //节点数量 static int count = 0;

/**  * 创建节点，成功后返回节点指针  * param  void* value 传入的指针  * return node*  */ static node* createNode(const void* value) {     node* n = (node*)malloc(sizeof(node));     if (!n)     {         cout << "failed in createNode!" << endl;         return NULL;     }     //为节点赋值     n->value = value;     //维护自身的指针     n->next = n->pre = n;     return n; }

/**  * 判断链表是否为空  * return  */ bool dlink_is_empty() {     return count == 0; }

/**  * 返回链表的大小  * return count  */ int dlink_size() {     return count; } /**  * 比较节点值的大小,仅限于数字和字符串  */ int compare(const void* a,const void* b) {     if (isdigit(*(int*)a))     {         return (*(int*)a) - (*(int*)b);     }     else     {         int i = 0,j = 0;         while (((char*)a)[i] && ((char*)b)[j])         {             if (((char*)a)[i] - ((char*)b)[j] != 0)             {                 return ((char*)a)[i] - ((char*)b)[j];             }             i++,j++;         }         if (strlen((char*)a) == i && strlen((char*)b) == j)         {             return 0;         }         else if (strlen((char*)a) == i)         {             return 1;         }         else         {             return -1;         }

}

}

/** * 将"value"插入到链表,成功返回0,否则返回-1 */ int dlink_insert(const void *pval) {     node* n;     //1.链表为空时     if(count == 0)     {         n = createNode(pval);         head = tail = n;         count ++;         return 1;     }     //2.如果链表不为空，进行比较，确定位置     if (compare(head->value,pval) > 0)  //在head前面     {         n = createNode(pval);         n->next = head;         head->pre = n;         head = n;         count++;         return 1;     }     else if (compare(tail->value,pval) < 0)    //tail后面     {         n = createNode(pval);         tail->next = n;         n->pre = tail;         tail = n;         count++;         return 1;     }     else    //位于head和tail之间的某一个位置     {         node* index = tail;         while(compare(index->value,pval) > 0)         {             index = index->pre;         }         n = createNode(pval);

index->next = n;         n->pre = index;         n->next = index->next;         index->next->pre = n;         count++;         return 1;     }     return -1; } /**  * 返回链表的第一个元素  */ node* peek() {     return head == NULL ? NULL : head; } /**  * 取出链表的第一个元素,free操作，在poll方法后，不能忘记，否则，会内存泄漏  */ node* poll() {     node* n = head;     head = head->next;     return n; }

测试：

#include

#include

#include

#include "double_link.h"

using namespace std;

void testNum();

void testStr();

int main(){

testStr();

}

void testNum(){

int num = 12;

void* value = &num;

dlink_insert(value);

int num1 = 3;

void* value1 = &num1;

dlink_insert(value1);

node* n = poll();

cout << *((int*)(n->value)) << endl;

free(n);

node* no = peek();

cout << *((int*)(no->value)) << endl;

}

void testStr(){

const void* str = "abc";

dlink_insert(str);

const void* str1 = "abcd";

dlink_insert(str1);

node* n = poll();

cout << (char*)(n->value) << endl;

free(n);

node* no = peek();

cout << (char*)(no->value) << endl;

}

输出结果：

3 12

abcd abc