开源数据结构与算法库StoneValley

usr

第一次在x64论坛发帖，请多关照。
StoneValley是由纯C写成的一个数据结构和算法库。它遵循Public Domain协议开源，大家可以放心下载使用。

因为纯C无法使用C++的STL，StoneValley可以满足C程序员对STL的需求。
StoneValley库的github链接
以下我将StoneValley项目的Readme文件部分翻译出来，供大家参考：

iv  概览

      StoneValley是一个用纯C语言写成的程序库，它旨在为使用者提供一套拥有多重算法的函数来管理多种数据结构。这份Readme文件简要得以用户视角介绍了这个库。这份Readme文件的内容以它是什么，怎样使用它和怎样重开发它切入指导用户使用该库。想要改进或者熟练使用该库需要使用者练习使用它。

      StoneValley被分成了线性表、栈、队列、树、哈希表、图和集合几大部分。

      与其阐明函数之间的复杂调用关系，用一张将函数分成几大部分的图来说明StoneValley的实况更合人意。用户始终可以给StoneValley添加上其未实现的部分。

      深入StoneValley的内部，线性表/串是一个线性数据结构的集合，它收藏了数组、单链表、双链表、比特流、一般的矩阵，比特矩阵和稀疏矩阵。这些操作线性数据结构的函数被分布在文件“svstring.h”里边。更进一步，文件“svatom.c”、“svarray.c”、“svlist.c”、“svmatrix.c”和“svmisc.c”存放了这些函数的定义。

      文件“svstack.c”实现了栈并且“svstack.h”存放了其声明。本库以两种方式实现了栈，它们分别被设计成定长数组型和单链表型。对于用户来说，定长数组型适合被用在需要考虑内存用量大小的情况下。单链表型栈在允许使用动态内存分配的情况下很好使用。

      关于队列的函数被分配到了“svqueue.h”中，与此同时他们的实现被写在“svqueue.c”中。3种队列被写进了StoneValley。定长数组写成的循环队列和单链表实现的队列都在库里。一个双链表实现的双向结尾队列是另一参与者。像栈一样，用户可以使用定长数组型队列来严格控制内存使用空间。如果用户想要动态申请内存空间，链表型队列则可以被使用。

               世界上有太多树型的数据结构了，StoneValley不能一一实现它们，仅有一部分重要的树型数据结构被实现出来了。双指针节点形成的二叉树被种植在StoneValley中。常规树利用了数组来实现。堆使用了定长数组，二分搜索树实现了AA树。库中的另一组搜索树是AVL树，B+树和数组实现的Trie。最后，“svctree.c”中种植了一颗霍夫曼编码树。同样，关于树的函数被导出在了“svtree.h”头文件中。不同的源文件实现了不同的树。这些源文件是“svbtree.c”、“svgtree.c”、“svhtree.c”、“svstree.c”和“svctree.c”因为b表明二叉，g说明通用，h说明堆，s说明查找，c说明编码。

               头文件“svhash.h”中存放有哈希表函数的声明。哈希表函数的函数体被写在“svhash.c”中。就细节来说，分离链式哈希表使用链表做桶，开地址哈希表使用定长数组来分隔项目。在文件“svhash.h”中，CBF_HASH定义了哈希函数的原型。当用户在使用哈希表的时候，他们需要撰写自己的哈希回调函数定义以便StoneValley库的哈希函数调用他们来散列数据。这份头文件和源文件的内容将进一步告知用户如何散列。

      集合是StoneValley库所提供的另一项功能。集合使用了散列表和二分搜索树来管理它的元素。StoneValley将集合的接口写在文件“svset.h”中。与此同时函数实现被写在“svset.c”中。用户可以使用这些函数给集合添加删除元素，或者生成集合之间的并集，交集和差集。

      至于图，文件“svgraph.c”实现了数据结构图并且接口于文件“svgraph.h”中。由单指针节点做成的邻接表将一个图的边连接起来而非使用矩阵来表示边的连接关系。许多函数定义的操作可以被用来管理图结构比如计算最短路径和生成最小生成树。

      最后文件“svmisc.c”给剩余的算法和数据结构腾出了空间。除了已经完成的比特流的函数，常用算法例如快速排序和二分查找也被安排在此文件中来处理相邻数据。

以后我还会贴出一些基于StoneValley库的应用代码。

usr

这是调用StoneValley库的集合功能写的一段判断两个集合是否相等的程序：

[C] 纯文本查看 复制代码

#include <stdio.h>
#include "./StoneValley/src/svset.h"

int cbfcmpint(void * px, void * py)
{
    return *(int *)px - *(int *)py;
}

int main(void)
{
    P_SET_T pa, pb;
    int i;
    BOOL j, k;
    /* Create two sets. */
    pa = setCreateT();
    pb = setCreateT();
    
    do
    {
        printf("Input set A:");
        scanf("%d", &i);
        setInsertT(pa, &i, sizeof i, cbfcmpint);

    } while (i != 0);
    do
    {
        printf("Input set B:");
        scanf("%d", &i);
        setInsertT(pb, &i, sizeof i, cbfcmpint);

    } while (i != 0);
    j = setIsSubsetT(pa, pb, cbfcmpint);
    k = setIsSubsetT(pb, pa, cbfcmpint);
    if (j && k)
        printf("A==B!\n");
    else if (k)
        printf("A>B\n");
    else
        printf("Other Case!\n");
    /* Destory two sets. */
    setDeleteT(pa);
    setDeleteT(pb);
    return 0;
}

usr

这是使用了StoneValley库里的Trie来统计单词出现次数的程序：

[C] 纯文本查看 复制代码

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "svtree.h"
#include "svstring.h"
 
typedef struct st_VOCABULARY
{
    long freq; /* 单词频率 */
    char * pword; /* malloc申请的单词字符串 */
} VOCABULARY, * P_VOCABULARY;
 
P_VOCABULARY CreateWord()
{
    P_VOCABULARY pvol = malloc(sizeof(VOCABULARY));
    if (NULL != pvol)
    {
        pvol->freq = 1;
        pvol->pword = NULL;
    }
    return pvol;
}
 
void DeleteWord(P_VOCABULARY pvol)
{
    free(pvol->pword);
    free(pvol);
}
 
void DestoryArray(P_ARRAY_Z parrz)
{
    size_t i = 0;
    for (; i < parrz->num; ++i)
    {
        P_VOCABULARY pvol = *(((P_VOCABULARY *)parrz->pdata) + i);
        DeleteWord(pvol);
    }
    strFreeArrayZ(parrz);
}
 
int CbfPrintResult(void * pitem, size_t param)
{
    printf("%s %lu\n", (*((P_VOCABULARY *)pitem))->pword, (*((P_VOCABULARY *)pitem))->freq);
    DWC4100(param);
    return CBF_CONTINUE;
}
 
int cbfcmpchar(const void * px, const void * py)
{
    return *(char *)px - *(char *)py;
}
 
int cbfcmpfreq(const void * px, const void * py)
{
    return (*(P_VOCABULARY *)py)->freq - (*(P_VOCABULARY *)px)->freq;
}
 
int main(int argc, char * argv[])
{
    int c;
    long i, j = 0, k = 0, sizeBuffer = 1024, sizeArray = 1024;
    BOOL bCase = FALSE, bSort = FALSE;
    char * buffer = NULL;
    P_TRIE_A ptrie;
    ARRAY_Z arrz;
 
    if (NULL == (buffer = (char *) malloc(sizeBuffer)))
        return 1;
    *buffer = '\0';
    if (NULL == (ptrie = treCreateTrieA()))
        return 2;
    if (NULL == strInitArrayZ(&arrz, sizeArray, sizeof(P_VOCABULARY)))
        return 3;
 
    for (i = 1; i < argc; ++i)
    {
        if (0 == strcmp("-s", argv[i])) /* 排序开关 */
            bSort = TRUE;
        else if (0 == strcmp("-c", argv[i])) /* 大小写开关 */
            bCase = TRUE;
        else
            return 4;
    }
    while (EOF != (c = fgetc(stdin)))
    {
        if (j >= sizeBuffer)
        {
            char * tempBuffer;
            sizeBuffer += 1024;
            if (NULL == (tempBuffer = realloc(buffer, sizeBuffer)))
                return 5;
            buffer = tempBuffer;
        }
        if (c >= 'A' && c <= 'Z')
        {
            *(buffer + j++) = bCase ? (char)c : (char)tolower(c);
        }
        else if (c >= 'a' && c <= 'z')
        {
            *(buffer + j++) = (char)c;
        }
        else
        {
            *(buffer + j) = '\0';
            if (0 != j)
            {
                size_t * presult;
                P_VOCABULARY pvol;
                size_t bufferLen = strlen(buffer);
                /* 在Trie里查询buffer所包含的单词 */
                if (NULL == (presult = treSearchTrieA(ptrie, buffer, bufferLen, sizeof(char), cbfcmpchar)))
                {
                    if (k >= sizeArray)
                    {
                        sizeArray += 1024;
                        strResizeArrayZ(&arrz, sizeArray, sizeof(P_VOCABULARY));
                    }
                    /* 如果没找到就创建一个新单词 */
                    pvol = CreateWord();
                    /* 将新单词插入Trie */
                    treInsertTrieA(ptrie, buffer, bufferLen, sizeof(char), (size_t)pvol, cbfcmpchar);
                    if (NULL == (pvol->pword = malloc(bufferLen + 1)))
                        return 6;
                    memcpy(pvol->pword, buffer, bufferLen + 1);
                    /* 将新单词的指针存储在数组里 */
                    *(((P_VOCABULARY *)arrz.pdata) + k++) = pvol;
                }
                else
                {   /* 如果找到单词，就把Trie里存储的Appendix拿出来转换为P_VOCABULARY指针，并且把频率+1 */
                    pvol = (P_VOCABULARY)*presult;
                    ++pvol->freq;
                }
            }
            j = 0;
 
        }
    }
    strResizeArrayZ(&arrz, k, sizeof(P_VOCABULARY));
    if (bSort)
        strSortArrayZ(&arrz, sizeof(P_VOCABULARY), cbfcmpfreq);
    strTraverseArrayZ(&arrz, sizeof(P_VOCABULARY), CbfPrintResult, 0, FALSE);
    DestoryArray(&arrz);
    treDeleteTrieA(ptrie, sizeof(char));
    free(buffer);
    return 0;
}

使用的时候，先编译所有文件：
$ cc *.c -o freq
编译后生成可执行体freq.
然后使用cat和管道符将文本文件输入freq的stdin：
$ cat new2.txt | ./freq -c

usr

这次发一个压缩解压缩功能的代码，它使用了StoneValley库里边的Huffman Coding Tree。

源码由三部分组成：

1.svcompress.c

[C] 纯文本查看 复制代码

/*
 * Name:        svcompress.c
 * Description: Compress files.
 * Author:      cosh.cage#hotmail.com
 * File ID:     0120211637B0120211637L00208
 * License:     Public Domain.
 */

#include <stdlib.h>
#include <string.h>
#include "svcompress.h"
#include "svtree.h"

/* Buffer size incremental. */
#define INITIAL_BUFFER_SIZE (1024)

/* Magical number that used to distinguish file type. */
UCHART magicNumber[] = { 'S', 'V', 'C', 'F' };

/* SVCF_File_structure:_________________
 * |Length:  |Name:                    |
 * |---------|-------------------------|
 * |UCHART[4]|Magical number.          |
 * |UCHART   |Platform integer length. |
 * |UCHART   |Symbol table length.     |
 * |N/A      |Symbol table.            |
 * |         |                         |
 * |size_t   |Compressed data length.  |
 * |UCHART   |Remaining bits.          |
 * |N/A      |Compressed data.         |
 * |_________|_________________________|
 */

 /* Function name: svcCompressFile
  * Description:   Compress a file to a file.
  * Parameters:
  *      fpout Pointer to the output file.
  *       fpin Pointer to the input file.
  * Return value:  Error code.
  *                Please refer to the SVCERROR enumeration at file 'svcompress.h'.
  */
SVCERROR svcCompressFile(FILE * fpout, FILE * fpin)
{
	int c;
	UCHART uc;
	size_t i = 0, j, k;
	P_BITSTREAM pbstm;
	ARRAY_Z arrInBuffer, * parrTable = NULL;
	SVCERROR rtn = SVC_NONE;

	if (NULL == fpin || NULL == fpout)
		return SVC_FILE_OPEN;
	if (NULL == strInitArrayZ(&arrInBuffer, INITIAL_BUFFER_SIZE, sizeof(UCHART)))
		return SVC_ALLOCATION;
	/* Read fpin into buffer in the memory. */
	while ((c = fgetc(fpin)) != EOF)
	{
		arrInBuffer.pdata[i] = (UCHART)c;
		if (++i >= strLevelArrayZ(&arrInBuffer))
			if (NULL == strResizeArrayZ(&arrInBuffer, strLevelArrayZ(&arrInBuffer) + INITIAL_BUFFER_SIZE, sizeof(UCHART)))
			{
				rtn = SVC_ALLOCATION;
				goto Lbl_Compress_Error;
			}
	}
	if (NULL == strResizeArrayZ(&arrInBuffer, i, sizeof(UCHART)))
	{
		rtn = SVC_ALLOCATION;
		goto Lbl_Compress_Error;
	}

	/* Compress data. */
	if (NULL == (pbstm = treHuffmanEncoding(&parrTable, arrInBuffer.pdata, i)))
	{
		rtn = SVC_COMPRESS;
		goto Lbl_Compress_Error;
	}
	if (NULL == parrTable)
	{	/* Can not output symbol table. */
		strDeleteBitStream(pbstm);
		rtn = SVC_COMPRESS;
		goto Lbl_Compress_Error;
	}
	/* Free in-buffer-array. */
	strFreeArrayZ(&arrInBuffer);

	/*
	{
		P_BITSTREAM pbsout;
		pbsout = treHuffmanDecoding(parrTable, pbstm);
		strDeleteBitStream(pbsout);
	}
	*/

	/* Write magical number. */
	fwrite(magicNumber, sizeof magicNumber / sizeof magicNumber[0], sizeof magicNumber[0], fpout);
	/* Write file header which is a UCHART variable that indicates platform integer length. */
	uc = sizeof(size_t);
	fwrite(&uc, sizeof uc, 1, fpout);
	/* Write symbol table length. */
	uc = (UCHART)parrTable->num;
	fwrite(&uc, sizeof uc, 1, fpout);
	/* Write symbol table. */
	k = strLevelArrayZ(parrTable) * sizeof(HFM_SYMBOL);
	for (j = 0; j < k; ++j)
		fputc(parrTable->pdata[j], fpout);
	/* Delete symbol table. */
	strDeleteArrayZ(parrTable);
	/* Write compressed data length. */
	j = strLevelArrayZ(&(pbstm->arrz));
	fwrite(&j, sizeof j, 1, fpout);
	/* Write remaining bits. */
	uc = (UCHART)pbstm->bilc;
	fwrite(&uc, sizeof uc, 1, fpout);
	/* Write compressed data. */
	for (j = 0; j < strLevelArrayZ(&(pbstm->arrz)); ++j)
		fputc(pbstm->arrz.pdata[j], fpout);
	/* Cleanup. */
	strDeleteBitStream(pbstm);
	return SVC_NONE;

Lbl_Compress_Error:
	fclose(fpin);
	fclose(fpout);
	strFreeArrayZ(&arrInBuffer);
	return rtn;
}

/* Function name: svcDecompressFile
 * Description:   Decompress a file to a file.
 * Parameters:
 *      fpout Pointer to the output file.
 *       fpin Pointer to the input file.
 * Return value:  Error code.
 *                Please refer to the SVCERROR enumeration at file 'svcompress.h'.
 */
SVCERROR svcDecompressFile(FILE * fpout, FILE * fpin)
{
	int c;
	UCHART uc;
	size_t i, j, k;
	P_ARRAY_Z parrTable;
	BITSTREAM bsin, * pbsout;
	UCHART magicBuffer[sizeof magicNumber / sizeof magicNumber[0]];

	if (NULL == fpin || NULL == fpout)
		return SVC_FILE_OPEN;
	/* Read magical number. */
	fread(magicBuffer, sizeof magicNumber[0], sizeof magicNumber / sizeof magicNumber[0], fpin);
	if (0 != memcmp(magicBuffer, magicNumber, sizeof magicNumber))
		return SVC_FILE_TYPE;
	/* Read platform length. */
	fread(&uc, sizeof(UCHART), 1, fpin);
	if (sizeof(size_t) != (size_t)uc)
		return SVC_PLATFORM;
	/* Read symbol table length. */
	fread(&uc, sizeof(UCHART), 1, fpin);
	j = uc * sizeof(HFM_SYMBOL);
	/* Read symbol table. */
	parrTable = strCreateArrayZ(uc, sizeof(HFM_SYMBOL));
	for (i = 0; i < j; ++i)
	{
		if ((c = fgetc(fpin)) == EOF)
		{
			strDeleteArrayZ(parrTable);
			return SVC_FILE_TYPE;
		}
		parrTable->pdata[i] = (UCHART)c;
	}
	/* Read compressed data length. */
	fread(&k, sizeof(size_t), 1, fpin);
	/* Read remaining bits. */
	fread(&uc, sizeof uc, 1, fpin);
	bsin.bilc = (size_t)uc;
	if (NULL == strInitArrayZ(&bsin.arrz, k, sizeof(UCHART)))
	{
		strDeleteArrayZ(parrTable);
		return SVC_ALLOCATION;
	}
	/* Read compressed data. */
	for (i = 0; i < k; ++i)
	{
		if ((c = fgetc(fpin)) == EOF)
		{
			strDeleteArrayZ(parrTable);
			strFreeBitStream(&bsin);
			return SVC_FILE_TYPE;
		}
		bsin.arrz.pdata[i] = (UCHART)c;
	}
	/* Decompress. */
	if (NULL == (pbsout = treHuffmanDecoding(parrTable, &bsin)))
	{
		strDeleteArrayZ(parrTable);
		strFreeBitStream(&bsin);
		return SVC_DECOMPRESS;
	}
	/* Cleanup. */
	strDeleteArrayZ(parrTable);
	strFreeBitStream(&bsin);
	/* Output result. */
	for (i = 0; i < pbsout->arrz.num; ++i)
		fputc(pbsout->arrz.pdata[i], fpout);
	/* Cleanup. */
	strDeleteBitStream(pbsout);
	return SVC_NONE;
}

2.svcompress.h

[C] 纯文本查看 复制代码

/*
 * Name:        svcompress.h
 * Description: Compress files.
 * Author:      cosh.cage#hotmail.com
 * File ID:     0120211637A0120211640L00028
 * License:     Public Domain.
 */

#ifndef _SVCOMPRESS_H_
#define _SVCOMPRESS_H_

#include <stdio.h>

typedef enum en_SVCERROR {
	SVC_NONE,       /* No error. */
	SVC_FILE_OPEN,  /* File pointer is NULL. */
	SVC_ALLOCATION, /* Allocation failure. */
	SVC_COMPRESS,   /* Compressing error. */
	SVC_FILE_TYPE,  /* Data file error. */
	SVC_PLATFORM,   /* Platform intger length mismatch. */
	SVC_DECOMPRESS  /* Decompressing error. */
} SVCERROR;

SVCERROR svcCompressFile  (FILE * fpout, FILE * fpin);
SVCERROR svcDecompressFile(FILE * fpout, FILE * fpin);

#endif

3.test_svcf.c

[C] 纯文本查看 复制代码

/*
 * Name:        test_svcf.c
 * Description: Launcher of compress/Decompress files.
 * Author:      cosh.cage#hotmail.com
 * File ID:     0120211637C0120211656L00034
 * License:     Public Domain.
 */

#include <stdio.h>
#include <string.h>
#include "svcompress.h"

int main(int argc, char ** argv)
{
	int i;
	for (i = 0; i < argc; ++i)
	{
		if (0 == strcmp(argv[i], "-c") || 0 == strcmp(argv[i], "--compress"))
		{
			return svcCompressFile(stdout, stdin);
		}
		if (0 == strcmp(argv[i], "-d") || 0 == strcmp(argv[i], "--decompress"))
		{
			return svcDecompressFile(stdout, stdin);
		}
		if (0 == strcmp(argv[i], "-?") || 0 == strcmp(argv[i], "--help") || 0 == strcmp(argv[i], "-h"))
		{
			printf("Usage:\n\tsvcf [-c|--compress] Compress stdin.\n\tsvcf [-d|--decompress] Decompress stdin as a svcf file.\n\tsvcf [-?|-h|--help] Show this help content.\n");
			break;
		}
	}
	return 0;
}

使用的时候将文件全部添加到StoneValley库内的src目录下，编译即可。
使用svcf -?命令查看svcf的使用方法。（注：svcf是StoneValley compress file的意思。）
在Linux/Unix平台下编译使用效果更佳。

JimmyzZZ

usr 发表于 2023-1-13 02:53
这次发一个压缩解压缩功能的代码，它使用了StoneValley库里边的Huffman Coding Tree。

源码由三部分组成： ...

谢谢分享，正好需要这方面的功能

usr

JimmyzZZ 发表于 2023-1-15 07:44
谢谢分享，正好需要这方面的功能

感谢回复。能帮到别人说明源代码还是有用的。