Score
0
Watch 4 Star 3 Fork 1

Konghy / seqlistC

Create your Gitee Account
Explore and code with more than 5 million developers,Free private repositories !:)
Sign up
This repository doesn't specify license. Without author's permission, this code is only for learning and cannot be used for other purposes.
Clone or download
seqlist.c 5.60 KB
Copy Edit Web IDE Raw Blame History
Konghy authored 2015-01-18 21:39 . first commit
/*============================================================================
# FileName: seqlist.c
# Author: Huoty
# Email: sudohuoty@163.com
# HomePage: http://konghy.blog.163.com/
# Version: 0.0.1
# CreateDate: 2014-12-19 15:02:18
# History:
# Description: 顺序存储序列实现
============================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"
/**
* @brief 初始化顺序存储序列结构
*
* @param seql -- 顺序存储序列结构指针
*
* @returns 成功返回0;失败返回-1
*/
int seqlist_init(SeqList *seql)
{
seql->max = 10;
seql->len = 0;
seql->slp = (DataType *)malloc(sizeof(DataType) * seql->max);
if (!seql->slp)
{
fprintf(stderr, "In function seqlist_init(): malloc fail.");
return -1;
}
return 0;
}
/**
* @brief 销毁顺序序列
*
* @param seql -- 顺序存储序列结构指针
*/
void seqlist_destroy(SeqList *seql)
{
int i;
if (seql->slp)
{
for(i = 0; i < seql->len; i++)
{
if (seql->slp[i].key)
{
free(seql->slp[i].key);
seql->slp[i].key = NULL;
}
if (seql->slp[i].val)
{
free(seql->slp[i].val);
seql->slp[i].val = NULL;
}
}
free(seql->slp);
seql->slp = NULL;
}
seql->max = 0;
seql->len = 0;
}
/**
* @brief 向顺序序列中添加数据
*
* @param seql -- 顺序存储序列结构指针
* @param key -- 键
* @param val -- 键所对应的值
*
* @returns
*/
int seqlist_add_data(SeqList *seql, char *key, char *val)
{
if (!key || !val)
{
return -1;
}
if (seql->len >= seql->max)
{
seql->max = (seql->len/10 + 1) * 10; //向上取10的倍数
seql->slp = (DataType *)realloc(seql->slp, sizeof(DataType) * seql->max);
if (seql->slp == NULL)
{
fprintf(stderr, "In function seqlist_add_data(): realloc fail.");
return -1;
}
}
seql->slp[seql->len].key = strdup(key);
seql->slp[seql->len].val = strdup(val);
seql->len++;
return 0;
}
/**
* @brief 合并两侧已排完序的序列
*
* @param seql -- 顺序存储序列结构指针
* @param start -- 序列起始坐标
* @param mid -- 序列中间坐标
* @param end -- 序列结尾坐标
*/
static void merge(SeqList *seql, int start, int mid, int end)
{
int i, j, k;
DataType b[end + 1];
for (i = start; i <= end; i++)
b[i] = seql->slp[i]; // init b[] = a[]
i = start;
j = mid + 1;
k = start;
while (i <= mid && j <= end)
{
if (strcmp(b[i].key, b[j].key) < 0)
seql->slp[k++] = b[i++];
else
seql->slp[k++] = b[j++];
}
while (i <= mid)
seql->slp[k++] = b[i++];
while (j <= end)
seql->slp[k++] = b[j++];
}
/**
* @brief 归并排序算法
*
* @param seql -- 顺序存储序列结构指针
* @param start -- 序列起始坐标
* @param end -- 序列结尾坐标
*/
static void sort(SeqList *seql, int start, int end)
{
int mid; // middle position
/* 序列只有一个元素时不必再排序 */
if (start >= end)
return;
/* 计算中间坐标 */
mid = (start + end) / 2;
/* 首先将左边的序列排序 */
sort(seql, start, mid);
/* 然后将右边的序列排序 */
sort(seql, mid+1, end);
/* 最后合并左右两侧都排完序的序列 */
merge(seql, start, mid, end);
}
/**
* @brief 整理序列中的数据,使其有序
*
* @param seql -- 顺序存储序列结构指针
*/
void seqlist_data_sort(SeqList *seql)
{
sort(seql, 0, seql->len - 1);
}
/**
* @brief 查找key所对应的值,折半查找实现
*
* @param seql -- 顺序存储序列结构指针
* @param key -- 要查找的键
*
* @returns 成功返回key所对应的值,失败返回NULL
*/
char *seqlist_data_search(SeqList *seql, const char *key)
{
int l, mid, r; // left, middle, right
l = 0;
r = seql->len - 1;
while (l <= r)
{
mid = (l+r) / 2;
if (strcmp(key, seql->slp[mid].key) < 0)
r = mid - 1; // 如果小于中间的值则在左边找
else if (strcmp(key, seql->slp[mid].key) > 0)
l = mid + 1; // 如果大于中间的值则在右边找
else
return seql->slp[mid].val; // 找到返回对应的值
}
return NULL; //没找到返回NULL
}
#ifdef DEBUG
int main(void)
{
int i;
SeqList seql;
/* 初始化顺序序列 */
seqlist_init(&seql);
/* 添加数据 */
seqlist_add_data(&seql, "d", "dxc");
seqlist_add_data(&seql, "c", "cxc");
seqlist_add_data(&seql, "b", "bxc");
seqlist_add_data(&seql, "k", "khy");
seqlist_add_data(&seql, "a", "axc");
seqlist_add_data(&seql, "y", "axc");
seqlist_add_data(&seql, "g", "axc");
seqlist_add_data(&seql, "h", "axc");
seqlist_add_data(&seql, "5", "axc");
seqlist_add_data(&seql, "0", "axc");
seqlist_add_data(&seql, "m", "axc");
seqlist_add_data(&seql, "9", "axc");
/* 排序整理,以供查找 */
seqlist_data_sort(&seql);
/* 打印序列中所有数据 */
printf("SeqList length: %d\n", seql.len);
printf("SeqList maximum: %d\n", seql.max);
for (i = 0; i < seql.len; i++)
{
printf("<%d> %s: %s\n", i+1, seql.slp[i].key, seql.slp[i].val);
}
printf("search k: %s\n", seqlist_data_search(&seql, "k"));
seqlist_destroy(&seql);
return 0;
}
#endif

Comment ( 0 )

Sign in for post a comment