原创：C++实现的可排序的双向链表

学习C++有一周了，今天用C++设计了一个双向链表，这个链表有排序功能，默认按升序排列，接受的参数可以是数字，也可以是字符串。现在把自己写的代码，分享出来。如果链表中接受的对象为Lexeme，可以用于存储中文分词机械化分词后的结果集。

QuickSortSet.h

#ifndef DOUBLE_LINK_H_INCLUDED
#define DOUBLE_LINK_H_INCLUDED
#include<iostream>
class QuickSortSet
{

//双向链表节点
public: class Node
{
public:
Node* next;
public:
Node* pre;
const void* value;
Node(const void* val)
{
value = val;
next = pre = nullptr;
}
};
public:

//constructor
QuickSortSet(int qs = CAPACITY);
//析构函数
~QuickSortSet();
//赋值运算符
QuickSortSet& operator=(const QuickSortSet& qs)
{
return *this;
}

//链表的大小
int size();

//比较节点值的大小,仅限于数字和字符串
int compare(const void* a,const void* b);

//将"value"插入到链表,成功返回0,否则返回-1
int insert(const void *pval);

//返回链表的第一个元素
const void* peekFirst();
//返回链表的最后一个元素
const void* peekLast();

//取出链表的第一个元素
const void* pollFirst();
//取出链表的最后一个元素
const void* pollLast();

bool isEmpty()
{
return count == 0;
}
bool isFull()
{
return count == qSize;
}

Node* getHead()
{
return head;
}
Node* getTail()
{
return tail;
}

private:
enum {CAPACITY = 1 << 30 -1};
const int qSize;
int count;

//链表头部和尾部
Node* head;
Node* tail;
};
#endif // DOUBLE_LINK_H_INCLUDED

QuickSortSet实现：

#include<iostream>
#include<cctype>
#include<cstring>
#include "double_link.h"
using namespace std;

/**
* 构造函数，默认容量为CAPACITY
*/
QuickSortSet::QuickSortSet(int qs):qSize(qs){
head = tail = nullptr;
count = 0;
}
/**
* 析构函数，默认容量为CAPACITY
*/
QuickSortSet::~QuickSortSet(){
QuickSortSet::Node* temp;
while(head){
temp = head;
head = head->next;
delete temp->value;
delete temp;
}
}

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

}

/**
* 将"value"插入到链表,成功返回0,否则返回-1
*/
int QuickSortSet::insert(const void *pval)
{
Node* n;
//1.链表为空时
if (isEmpty())
{
n = new Node(pval);

head = tail = n;
count ++;
return 1;
}
if (isFull()) {return -1;}

//2.如果链表不为空，进行比较，确定位置
if (compare(head->value,pval) > 0) //在head前面
{
n = new Node(pval);
n->next = head;
head->pre = n;
head = n;
count++;
return 1;
}
else if (compare(tail->value,pval) < 0) //tail后面
{
n = new Node(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 = new Node(pval);

n->pre = index;
n->next = index->next;
index->next->pre = n;
index->next = n;

count++;
return 1;
}
return -1;
}
/**
* 返回链表的第一个元素
*/
const void* QuickSortSet::peekFirst()
{
return head == NULL ? NULL : head->value;
}
/**
* 取出链表的第一个元素
*/
const void* QuickSortSet::pollFirst()
{
Node* temp = head;
const void* value = temp->value;
head = head->next;
delete temp->value;
delete temp;
return value;
}

/**
* 返回链表的最后一个元素
*/
const void* QuickSortSet::peekLast(){
return tail == nullptr ? nullptr : tail->value;
}

/**
* 取出链表的最后一个元素
*/
const void* QuickSortSet::pollLast(){
Node* temp = tail;
const void* value = temp->value;
tail = tail->pre;
delete temp->value;
delete temp;
return value;
}

测试类：

#include<cstdlib>
#include<iostream>
#include "heap.h"
#include "double_link.h"
#include "time.h"
#include<fstream>
#define DEBUG 1
#define SIZE 5
#define LINE 10000000
using namespace std;
void testNum();
void testStr();
//void testHeap();
//void createFile();
int main()
{
#if DEBUG
//testNum();
testStr();
#endif // DEBUG
//createFile(); //生成随机数文件
// testHeap();
}
#if DEBUG
void testNum()
{
QuickSortSet q = QuickSortSet();

int num = 12;
q.insert(&num);

const int num1 = 3;
q.insert(&num1);

const int num2 = 9;
q.insert(&num2);

QuickSortSet::Node* node = q.getHead();
while(node){
cout << *((int*)node->value) << endl;
node = node->next;
}
}
void testStr()
{
QuickSortSet q = QuickSortSet();

q.insert("abc");
q.insert("abce");
q.insert("abcd");
q.insert("abcf");

QuickSortSet::Node* node = q.getHead();

while(node){
cout << (const char*)node->value << endl;
node = node->next;
}
}
#endif // DEBUG

/**
* 1.生成随机数文件;
* 2.读取前SIZE行，构造小根堆;
* 3.依次读取剩余的行,对读到的每行数据，如果比堆顶元素大，替换之，然后调整小根堆;
* 4.读取结束后，执行堆排序。
*/
void testHeap()
{

clock_t start,finish;
double duration;//耗时时间
start = clock();

ifstream inFile;
inFile.open("E:\\var\\logs\\nums.txt");

int nums[SIZE];
int index = 0;
char num[1024] = {0};
while (inFile.getline(num,sizeof(num)))
{
nums[index++] = atoi(num);
if (index == SIZE)
{
break;
}
}
createMinHeap(nums,SIZE);//读取前SIZE行，构造小根堆

int temp;
while (inFile.getline(num,sizeof(num)))
{
temp = atoi(num);
if (temp > nums[0])
{
nums[0] = temp;
adjustment(0);
}
}//依次读取剩余的行,对读到的每行数据，如果比堆顶元素大，替换之，然后调整小根堆

heapSort();//读取结束后，执行堆排序

finish = clock();
duration = (double)((finish - start) / CLOCKS_PER_SEC);
cout << "耗时 " << duration << "s." << endl;
for (int i = 0; i < SIZE; i++)
{
cout << nums[i] << " ";
}
}
/**
* 产生随机数文件
*/
void createFile()
{
ofstream outFile;
outFile.open("E:\\var\\logs\\nums.txt");
srand((unsigned)time(NULL));
for (int i = 0; i <= LINE; i++)
{
outFile << rand() << endl;
}
}
void safeDelete(){

}

输出结果：

abcd

abce

abcf

abc

巴特西

原创：C++实现的可排序的双向链表

最新文章

热门文章