简单HashTable(取模法)

在 2016年7月21日2016年8月12日上张贴由 BestLove

//参考：http://www.php-internals.com/book/?p=chapt03/03-01-01-hashtable
//http://www.cunmou.com/phpbook/preface.md
//http://wiki.swoole.com/wiki/index/prid-7
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"

int main(int argc, char const *argv[])
{
    HashTable *h = (HashTable *)malloc(sizeof(HashTable));
    hash_init(h);

    char * str1 = "key1";
    char * str2 = "key2";
    char * str3 = "key3";
    char * str4 = "key4";
    char * str5 = "key5";
    char * str6 = "key6";
    char * str7 = "key7";
    char * str8 = "key8";

    int num1 = 1;
    int num2 = 2;
    int num3 = 3;
    int num4 = 4;
    int num5 = 5;
    int num6 = 6;
    int num7 = 7;
    int num8 = 8;

    hash_insert(h, str1, &num1);
    hash_insert(h, str2, &num2);
    hash_insert(h, str3, &num3);
    hash_insert(h, str4, &num4);
    hash_insert(h, str5, &num5);
    hash_insert(h, str6, &num6);
    hash_insert(h, str7, &num7);
    hash_insert(h, str8, &num8);

    int *num11 = NULL;
    int *num22 = NULL;
    int *num33 = NULL;
    int *num44 = NULL;
    int *num55 = NULL;
    int *num66 = NULL;
    int *num77 = NULL;
    int *num88 = NULL;

    hash_lookup(h, str1, (void **)&num11);
    hash_lookup(h, str2, (void **)&num22);
    hash_lookup(h, str3, (void **)&num33);
    hash_lookup(h, str4, (void **)&num44);
    hash_lookup(h, str5, (void **)&num55);
    hash_lookup(h, str6, (void **)&num66);
    hash_lookup(h, str7, (void **)&num77);
    hash_lookup(h, str8, (void **)&num88);

    printf("find result key=%s value=%d \n", str1, *num11);
    printf("find result key=%s value=%d \n", str2, *num22);
    printf("find result key=%s value=%d \n", str3, *num33);
    printf("find result key=%s value=%d \n", str4, *num44);
    printf("find result key=%s value=%d \n", str5, *num55);
    printf("find result key=%s value=%d \n", str6, *num66);
    printf("find result key=%s value=%d \n", str7, *num77);
    printf("find result key=%s value=%d \n", str8, *num88);
 
    hash_destroy(h);
    return 0;
}

//参考：http://www.php-internals.com/book/?p=chapt03/03-01-01-hashtable

//http://www.cunmou.com/phpbook/preface.md

//http://wiki.swoole.com/wiki/index/prid-7

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "hashtable.h"

int main(int argc, char const *argv[])

{

HashTable *h = (HashTable *)malloc(sizeof(HashTable));

hash_init(h);

char * str1 = "key1";

char * str2 = "key2";

char * str3 = "key3";

char * str4 = "key4";

char * str5 = "key5";

char * str6 = "key6";

char * str7 = "key7";

char * str8 = "key8";

int num1 = 1;

int num2 = 2;

int num3 = 3;

int num4 = 4;

int num5 = 5;

int num6 = 6;

int num7 = 7;

int num8 = 8;

hash_insert(h, str1, &num1);

hash_insert(h, str2, &num2);

hash_insert(h, str3, &num3);

hash_insert(h, str4, &num4);

hash_insert(h, str5, &num5);

hash_insert(h, str6, &num6);

hash_insert(h, str7, &num7);

hash_insert(h, str8, &num8);

int *num11 = NULL;

int *num22 = NULL;

int *num33 = NULL;

int *num44 = NULL;

int *num55 = NULL;

int *num66 = NULL;

int *num77 = NULL;

int *num88 = NULL;

hash_lookup(h, str1, (void **)&num11);

hash_lookup(h, str2, (void **)&num22);

hash_lookup(h, str3, (void **)&num33);

hash_lookup(h, str4, (void **)&num44);

hash_lookup(h, str5, (void **)&num55);

hash_lookup(h, str6, (void **)&num66);

hash_lookup(h, str7, (void **)&num77);

hash_lookup(h, str8, (void **)&num88);

printf("find result key=%s value=%d \n", str1, *num11);

printf("find result key=%s value=%d \n", str2, *num22);

printf("find result key=%s value=%d \n", str3, *num33);

printf("find result key=%s value=%d \n", str4, *num44);

printf("find result key=%s value=%d \n", str5, *num55);

printf("find result key=%s value=%d \n", str6, *num66);

printf("find result key=%s value=%d \n", str7, *num77);

printf("find result key=%s value=%d \n", str8, *num88);

hash_destroy(h);

return 0;

}

#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_
//初始化hashtable的默认长度，当hashtable的实际长度超过HASH_TABLE_INIT_SIZE时会以2倍的方式扩容
#define HASH_TABLE_INIT_SIZE 6
//以下宏配合hashtable.c中的hash_str函数，可以计算hash值(取模法)
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)
//如果定义了DEBUG常量，则LOG_MSG会使用printf，否则是一个空操作
#if defined(DEBUG)
#  define LOG_MSG printf
#else
#  define LOG_MSG(...)
#endif

#define SUCCESS 0
#define FAILED -1

typedef struct _Bucket
{
    char *key;                  //字符串key
    void *value;                //value指针，直接操作传入的指针，不返回value值
    struct _Bucket *next;
} Bucket;

typedef struct _HashTable
{
    int size;                    // 哈希表的大小
    int elem_num;                // 已经保存元素的个数
    Bucket **buckets;            // bucket指针数组
} HashTable;

int hash_init(HashTable *ht);
//**result(参数为二级指针，因为需要传入指针的引用)
int hash_lookup(HashTable *ht, char *key, void **result);
int hash_insert(HashTable *ht, char *key, void *value);
int hash_remove(HashTable *ht, char *key);
int hash_destroy(HashTable *ht);
#endif

#ifndef _HASH_TABLE_H_

#define _HASH_TABLE_H_

//初始化hashtable的默认长度，当hashtable的实际长度超过HASH_TABLE_INIT_SIZE时会以2倍的方式扩容

#define HASH_TABLE_INIT_SIZE 6

//以下宏配合hashtable.c中的hash_str函数，可以计算hash值(取模法)

#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

//如果定义了DEBUG常量，则LOG_MSG会使用printf，否则是一个空操作

#if defined(DEBUG)

# define LOG_MSG printf

#else

# define LOG_MSG(...)

#endif

#define SUCCESS 0

#define FAILED -1

typedef struct _Bucket

{

char *key; //字符串key

void *value; //value指针，直接操作传入的指针，不返回value值

struct _Bucket *next;

} Bucket;

typedef struct _HashTable

{

int size; // 哈希表的大小

int elem_num; // 已经保存元素的个数

Bucket **buckets; // bucket指针数组

} HashTable;

int hash_init(HashTable *ht);

//**result(参数为二级指针，因为需要传入指针的引用)

int hash_lookup(HashTable *ht, char *key, void **result);

int hash_insert(HashTable *ht, char *key, void *value);

int hash_remove(HashTable *ht, char *key);

int hash_destroy(HashTable *ht);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"
//设置key时，检查下哈希表是否已满，已满的话，调用hash_resize方法
static void resize_hash_table_if_needed(HashTable *ht);
//将字符串key转换成数字(每个字符的ASCII累加)
static int hash_str(char *key);
//哈希表扩容方法，将哈希表扩容2倍
static int hash_resize(HashTable *ht);

int hash_init(HashTable *ht)
{
    ht->size 		= HASH_TABLE_INIT_SIZE;
    ht->elem_num 	= 0;
    ht->buckets		= (Bucket **)calloc(ht->size, sizeof(Bucket *));
    //分配内存失败，直接返回错误
    if(ht->buckets == NULL) return FAILED;
    LOG_MSG("[init]\tsize: %d\n", ht->size);
    return SUCCESS;
}

int hash_lookup(HashTable *ht, char *key, void **result)
{
    //把字符串的每个字符的ascii码累加后和hash表的size取模
    int index = HASH_INDEX(ht, key);
    //从buckets中获取bucket指针
    Bucket *bucket = ht->buckets[index];
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            *result = bucket->value;
            return SUCCESS;
        }
        bucket = bucket->next;
    }
    LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);
    return FAILED;
}

int hash_insert(HashTable *ht, char *key, void *value)
{
    resize_hash_table_if_needed(ht);
    int index = HASH_INDEX(ht, key);
    Bucket *org_bucket = ht->buckets[index];
    Bucket *tmp_bucket = org_bucket;
    while(tmp_bucket)
    {
        if(strcmp(key, tmp_bucket->key) == 0)
        {
            tmp_bucket->value = value;
            return SUCCESS;
        }
        tmp_bucket = tmp_bucket->next;
    }
    Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));
    bucket->key	  = key;
    bucket->value = value;
    bucket->next  = NULL;
    ht->elem_num++;
    if(org_bucket != NULL)
    {
        LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);
        bucket->next = org_bucket;
    }
    ht->buckets[index] = bucket;
    LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num);
    return SUCCESS;
}

int hash_remove(HashTable *ht, char *key)
{
    int index = HASH_INDEX(ht, key);
    Bucket *bucket  = ht->buckets[index];
    Bucket *prev	= NULL;
    if(bucket == NULL) return FAILED;
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            LOG_MSG("[remove]\tkey:(%s) index: %d\n", key, index);
            if(prev == NULL)
            {
                ht->buckets[index] = bucket->next;
            }
            else
            {
                prev->next = bucket->next;
            }
            free(bucket);
            ht->elem_num--;
            return SUCCESS;
        }
        prev   = bucket;
        bucket = bucket->next;
    }
    LOG_MSG("[remove]\t key:%s not found remove \tfailed\t\n", key);
    return FAILED;
}

int hash_destroy(HashTable *ht)
{
    int i;
    Bucket *cur = NULL;
    Bucket *tmp = NULL;
    for(i = 0; i < ht->size; ++i)
    {
        cur = ht->buckets[i];
        while(cur)
        {
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(ht->buckets);
    free(ht);
    return SUCCESS;
}

static int hash_str(char *key)
{
    int hash = 0;

    char *cur = key;

    while(*cur != '\0')
    {
        hash +=	*cur;
        ++cur;
    }

    return hash;
}

static int hash_resize(HashTable *ht)
{
    int org_size = ht->size;
    ht->size = ht->size * 2;
    ht->elem_num = 0;
    LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);
    Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));
    Bucket **org_buckets = ht->buckets;
    ht->buckets = buckets;
    int i = 0;
    for(i = 0; i < org_size; ++i)
    {
        Bucket *cur = org_buckets[i];
        Bucket *tmp;
        //循环将原先的bucket指针删除，然后重新插入(因为扩容后，需要重新取模定位)
        while(cur)
        {
            hash_insert(ht, cur->key, cur->value);
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(org_buckets);
    LOG_MSG("[resize] done\n");
    return SUCCESS;
}

static void resize_hash_table_if_needed(HashTable *ht)
{
    if(ht->size - ht->elem_num < 1)
    {
        hash_resize(ht);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "hashtable.h"

//设置key时，检查下哈希表是否已满，已满的话，调用hash_resize方法

static void resize_hash_table_if_needed(HashTable *ht);

//将字符串key转换成数字(每个字符的ASCII累加)

static int hash_str(char *key);

//哈希表扩容方法，将哈希表扩容2倍

static int hash_resize(HashTable *ht);

int hash_init(HashTable *ht)

{

ht->size = HASH_TABLE_INIT_SIZE;

ht->elem_num = 0;

ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));

//分配内存失败，直接返回错误

if(ht->buckets == NULL) return FAILED;

LOG_MSG("[init]\tsize: %d\n", ht->size);

return SUCCESS;

}

int hash_lookup(HashTable *ht, char *key, void **result)

{

//把字符串的每个字符的ascii码累加后和hash表的size取模

int index = HASH_INDEX(ht, key);

//从buckets中获取bucket指针

Bucket *bucket = ht->buckets[index];

while(bucket)

{

if(strcmp(bucket->key, key) == 0)

{

*result = bucket->value;

return SUCCESS;

}

bucket = bucket->next;

}

LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);

return FAILED;

}

int hash_insert(HashTable *ht, char *key, void *value)

{

resize_hash_table_if_needed(ht);

int index = HASH_INDEX(ht, key);

Bucket *org_bucket = ht->buckets[index];

Bucket *tmp_bucket = org_bucket;

while(tmp_bucket)

{

if(strcmp(key, tmp_bucket->key) == 0)

{

tmp_bucket->value = value;

return SUCCESS;

}

tmp_bucket = tmp_bucket->next;

}

Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));

bucket->key = key;

bucket->value = value;

bucket->next = NULL;

ht->elem_num++;

if(org_bucket != NULL)

{

LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);

bucket->next = org_bucket;

}

ht->buckets[index] = bucket;

LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num);

return SUCCESS;

}

int hash_remove(HashTable *ht, char *key)

{

int index = HASH_INDEX(ht, key);

Bucket *bucket = ht->buckets[index];

Bucket *prev = NULL;

if(bucket == NULL) return FAILED;

while(bucket)

{

if(strcmp(bucket->key, key) == 0)

{

LOG_MSG("[remove]\tkey:(%s) index: %d\n", key, index);

if(prev == NULL)

{

ht->buckets[index] = bucket->next;

}

else

{

prev->next = bucket->next;

}

free(bucket);

ht->elem_num--;

return SUCCESS;

}

prev = bucket;

bucket = bucket->next;

}

LOG_MSG("[remove]\t key:%s not found remove \tfailed\t\n", key);

return FAILED;

}

int hash_destroy(HashTable *ht)

{

int i;

Bucket *cur = NULL;

Bucket *tmp = NULL;

for(i = 0; i < ht->size; ++i)

{

cur = ht->buckets[i];

while(cur)

{

tmp = cur;

cur = cur->next;

free(tmp);

}

free(ht->buckets);

free(ht);

return SUCCESS;

}

static int hash_str(char *key)

{

int hash = 0;

char *cur = key;

while(*cur != '\0')

{

hash += *cur;

++cur;

}

return hash;

}

static int hash_resize(HashTable *ht)

{

int org_size = ht->size;

ht->size = ht->size * 2;

ht->elem_num = 0;

LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);

Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));

Bucket **org_buckets = ht->buckets;

ht->buckets = buckets;

int i = 0;

for(i = 0; i < org_size; ++i)

{

Bucket *cur = org_buckets[i];

Bucket *tmp;

//循环将原先的bucket指针删除，然后重新插入(因为扩容后，需要重新取模定位)

while(cur)

{

hash_insert(ht, cur->key, cur->value);

tmp = cur;

cur = cur->next;

free(tmp);

}

free(org_buckets);

LOG_MSG("[resize] done\n");

return SUCCESS;

}

static void resize_hash_table_if_needed(HashTable *ht)

{

if(ht->size - ht->elem_num < 1)

{

hash_resize(ht);

}

all:
	#-DDEBUG指定常量DEBUG，hashtable.h中 #if defined(DEBUG) 有用到
	gcc -DDEBUG main.c hashtable.c -o hashtable.out
test: all
	./hashtable.out
clean:
	rm -rf hashtable.out

all:

#-DDEBUG指定常量DEBUG，hashtable.h中 #if defined(DEBUG) 有用到

gcc -DDEBUG main.c hashtable.c -o hashtable.out

test: all

./hashtable.out

clean:

rm -rf hashtable.out

二叉搜索树

在 2016年7月5日上张贴由 BestLove

#ifndef _TREE_H_

#define _TREE_H_

#include <stdbool.h>

typedef struct item
{
    char petname[20];
    char petkind[20];
} Item;

#define MAXITEMS 10

typedef struct node
{
    Item item;
    struct node * left;
    struct node * right;
} Node;

typedef struct tree
{
    Node * root;                    //指向树根的指针
    int size;                       //树中项目的个数
} Tree;

/*
    操作：把一个树初始为空树
    操作前：ptree指向一个树
    操作后：该树已被初始化为空树
*/
void InitializeTree(Tree * ptree);

/*
    操作：确定树是否为空
    操作前：ptree指向一个树
    操作后：如果树为空则返回true，否则返回false
*/
bool TreeIsEmpty(const Tree * ptree);

/*
    操作：确定树是否已满
    操作前：ptree指向一个树
    操作后：如果树已满则返回true，否则返回false
*/
bool TreeIsFull(const Tree * ptree);

/*
    操作：确定树中项目的个数
    操作前：ptree指向一个树
    操作后：返回树中项目的个数
*/
int TreeItemCount(const Tree * ptree);

/*
    操作：向树中添加一个项目
    操作前：pi是待添加的项目的地址
            ptree指向一个已经初始化的树
    操作后：如果可能，函数把该项目添加到
            树中并返回true，否则返回false
*/
bool AddItem(const Item * pi, Tree * ptree);

/*
    操作：在树中查找一个项目
    操作前：pi指向一个项目
            ptree指向一个已经初始化的树
    操作后：如果该项目在树中，则函数返回true，
            否则返回false
*/
bool InTree(const Item * pi, const Tree * ptree);

/*
    操作：从树中删除一个项目
    操作前：pi是待删除的项目的地址
            ptree指向一个已经初始化的树
    操作后：如果可能，函数从树中删除该项目
            并返回true，否则返回false
*/
bool DeleteItem(const Item * pi, Tree * ptree);

/*
    操作：把一个函数作用于树中每一个项目
    操作前：ptree指向一棵树
            pfun指向一个没有返回值的函数
            该函数接受一个Item作为参数
    操作后：pfun指向的函数被作用于树中每个项目一次
*/
void Traverse(const Tree * ptree, void(* pfun)(Item item));

/*
    操作：从树中删除所有节点
    操作前：ptree指向一个已经初始化的树
    操作后：该树为空树
*/
void DeleteAll(Tree * ptree);

#endif

#ifndef _TREE_H_

#define _TREE_H_

#include <stdbool.h>

typedef struct item

{

char petname[20];

char petkind[20];

} Item;

#define MAXITEMS 10

typedef struct node

{

Item item;

struct node * left;

struct node * right;

} Node;

typedef struct tree

{

Node * root; //指向树根的指针

int size; //树中项目的个数

} Tree;

操作：把一个树初始为空树

操作前：ptree指向一个树

操作后：该树已被初始化为空树

void InitializeTree(Tree * ptree);

操作：确定树是否为空

操作前：ptree指向一个树

操作后：如果树为空则返回true，否则返回false

bool TreeIsEmpty(const Tree * ptree);

操作：确定树是否已满

操作前：ptree指向一个树

操作后：如果树已满则返回true，否则返回false

bool TreeIsFull(const Tree * ptree);

操作：确定树中项目的个数

操作前：ptree指向一个树

操作后：返回树中项目的个数

int TreeItemCount(const Tree * ptree);

操作：向树中添加一个项目

操作前：pi是待添加的项目的地址

ptree指向一个已经初始化的树

操作后：如果可能，函数把该项目添加到

树中并返回true，否则返回false

bool AddItem(const Item * pi, Tree * ptree);

操作：在树中查找一个项目

操作前：pi指向一个项目

ptree指向一个已经初始化的树

操作后：如果该项目在树中，则函数返回true，

否则返回false

bool InTree(const Item * pi, const Tree * ptree);

操作：从树中删除一个项目

操作前：pi是待删除的项目的地址

ptree指向一个已经初始化的树

操作后：如果可能，函数从树中删除该项目

并返回true，否则返回false

bool DeleteItem(const Item * pi, Tree * ptree);

操作：把一个函数作用于树中每一个项目

操作前：ptree指向一棵树

pfun指向一个没有返回值的函数

该函数接受一个Item作为参数

操作后：pfun指向的函数被作用于树中每个项目一次

void Traverse(const Tree * ptree, void(* pfun)(Item item));

操作：从树中删除所有节点

操作前：ptree指向一个已经初始化的树

操作后：该树为空树

void DeleteAll(Tree * ptree);

#endif

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

//局部数据类型
typedef struct pair
{
   Node * parent;
   Node * child; 
} Pair;

static Node * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode(Node * new_node, Node * root);
static void InOrder(const Node * root, void(*pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNodes(Node * ptr);

void InitializeTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
    if (ptree->root == NULL)
    {
        return true;
    } else {
        return false;
    }
}

bool TreeIsFull(const Tree * ptree)
{
    if (ptree->size == MAXITEMS)
    {
        return true;
    } else {
        return false;
    }
}

int TreeItemCount(const Tree * ptree)
{
    return ptree->size;
}

bool AddItem(const Item * pi, Tree * ptree)
{
    Node * new_node;
    if (TreeIsFull(ptree))
    {
        fprintf(stderr, "Tree is full\n");
        return false;
    }
    if (SeekItem(pi, ptree).child != NULL)
    {
        fprintf(stderr, "Attempted to add duplicate item\n");
        return false;
    }
    new_node = MakeNode(pi);
    if (new_node == NULL)
    {
        fprintf(stderr, "Could't create Node\n");
        return false;
    }
    ptree->size++;
    if (ptree->root == NULL)        //树为空树
    {
        ptree->root = new_node;
    } else {
        AddNode(new_node, ptree->root);
    }
    return true;
}

bool InTree(const Item * pi, const Tree * ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

bool DeleteItem(const Item * pi, Tree * ptree)
{
    Pair look;
    look = SeekItem(pi, ptree);
    if (look.child == NULL)
    {
        return false;
    }
    if (look.parent == NULL)    //删除根项目
    {
        DeleteNode(&ptree->root);
    } else if(look.parent->left == look.child) {
        DeleteNode(&look.parent->left);
    } else {
        DeleteNode(&look.parent->right);
    }
    ptree->size--;
    return true;
}

void Traverse(const Tree * ptree, void(*pfun)(Item item))
{
    if (ptree != NULL)
    {
        InOrder(ptree->root, pfun);
    }
}

void DeleteAll(Tree * ptree)
{
    if (ptree != NULL)
    {
        DeleteAllNodes(ptree->root);
    }
    ptree->root = NULL;
    ptree->size = 0;
}

static void InOrder(const Node * root, void(*pfun)(Item item))
{
    if (root != NULL)
    {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}

static void DeleteAllNodes(Node * root)
{
    Node * pright;
    if (root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

static void AddNode(Node * new_node, Node * root)
{
    // new_node->item的指针，不是new_node的指针->item
    if (ToLeft(&new_node->item, &root->item))
    {
        if (root->left == NULL)                 //空子数
        {
            root->left = new_node;              //因此把节点添加到此处
        } else {
            AddNode(new_node, root->left);      //否则处理该子树
        }
    } else if (ToRight(&new_node->item, &root->item)) {
        if (root->right == NULL)
        {
            root->right = new_node;
        } else {
            AddNode(new_node, root->right);
        }
    } else {                                    //不允许含有相同的项目
        fprintf(stderr, "location error in AddNode()\n");
        exit(1);
    }
}

static bool ToLeft(const Item * i1, const Item * i2)
{
    int comp1;
    if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
    {
        return true;
    } else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0) {
        return true;
    } else {
        return false;
    }
}

static bool ToRight(const Item * i1, const Item * i2)
{
    int comp1;
    if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
    {
        return true;
    } else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0) {
        return true;
    } else {
        return false;
    }
}

static Node * MakeNode(const Item * pi)
{
    Node * new_node;
    new_node = (Node *) malloc(sizeof(Node));
    if (new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

static Pair SeekItem(const Item * pi, const Tree * ptree)
{
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;

    if (look.child == NULL)
    {
        return look;
    }
    while(look.child != NULL)
    {
        if (ToLeft(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        } else if (ToRight(pi, &(look.child->item))) {
            look.parent = look.child;
            look.child = look.child->right;
        } else {
            //break出循环，说明在树中找到了相关项
            //如果循环到look.child == NULL，表示没有找到相关项
            break;
        }
    }
    return look;
}

static void DeleteNode(Node **ptr)      //ptr是指向目标节点的父节点指针成员的地址
{
    Node * temp;
    puts((*ptr)->item.petname);
    if((*ptr)->left == NULL)
    {
        // 左节点为空，将其右节点顶上
        temp = *ptr;
        *ptr = (*ptr)->right;
    } else if ((*ptr)->right == NULL) {
        // 右节点为空，将其左节点顶上
        temp = *ptr;
        *ptr = (*ptr)->left;
    } else {
        //被删除的节点有两个子节点
        //从左节点起，一路向子节点的右节点寻找，直到找到一个空位(NULL)
        //将右节点顶在左节点的最右子节点的空位上
        //将左节点顶为根节点
        for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
        {
            continue;
        }
        temp->right = (*ptr)->right;
        temp = *ptr;
        *ptr = (*ptr)->left;
    }
    //释放需要删除的节点(地址指向临时节点)
    free(temp);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#include "tree.h"

//局部数据类型

typedef struct pair

{

Node * parent;

Node * child;

} Pair;

static Node * MakeNode(const Item * pi);

static bool ToLeft(const Item * i1, const Item * i2);

static bool ToRight(const Item * i1, const Item * i2);

static void AddNode(Node * new_node, Node * root);

static void InOrder(const Node * root, void(*pfun)(Item item));

static Pair SeekItem(const Item * pi, const Tree * ptree);

static void DeleteNode(Node **ptr);

static void DeleteAllNodes(Node * ptr);

void InitializeTree(Tree * ptree)

{

ptree->root = NULL;

ptree->size = 0;

}

bool TreeIsEmpty(const Tree * ptree)

{

if (ptree->root == NULL)

{

return true;

} else {

return false;

}

bool TreeIsFull(const Tree * ptree)

{

if (ptree->size == MAXITEMS)

{

return true;

} else {

return false;

}

int TreeItemCount(const Tree * ptree)

{

return ptree->size;

}

bool AddItem(const Item * pi, Tree * ptree)

{

Node * new_node;

if (TreeIsFull(ptree))

{

fprintf(stderr, "Tree is full\n");

return false;

}

if (SeekItem(pi, ptree).child != NULL)

{

fprintf(stderr, "Attempted to add duplicate item\n");

return false;

}

new_node = MakeNode(pi);

if (new_node == NULL)

{

fprintf(stderr, "Could't create Node\n");

return false;

}

ptree->size++;

if (ptree->root == NULL) //树为空树

{

ptree->root = new_node;

} else {

AddNode(new_node, ptree->root);

}

return true;

}

bool InTree(const Item * pi, const Tree * ptree)

{

return (SeekItem(pi, ptree).child == NULL) ? false : true;

}

bool DeleteItem(const Item * pi, Tree * ptree)

{

Pair look;

look = SeekItem(pi, ptree);

if (look.child == NULL)

{

return false;

}

if (look.parent == NULL) //删除根项目

{

DeleteNode(&ptree->root);

} else if(look.parent->left == look.child) {

DeleteNode(&look.parent->left);

} else {

DeleteNode(&look.parent->right);

}

ptree->size--;

return true;

}

void Traverse(const Tree * ptree, void(*pfun)(Item item))

{

if (ptree != NULL)

{

InOrder(ptree->root, pfun);

}

void DeleteAll(Tree * ptree)

{

if (ptree != NULL)

{

DeleteAllNodes(ptree->root);

}

ptree->root = NULL;

ptree->size = 0;

}

static void InOrder(const Node * root, void(*pfun)(Item item))

{

if (root != NULL)

{

InOrder(root->left, pfun);

(*pfun)(root->item);

InOrder(root->right, pfun);

}

static void DeleteAllNodes(Node * root)

{

Node * pright;

if (root != NULL)

{

pright = root->right;

DeleteAllNodes(root->left);

free(root);

DeleteAllNodes(pright);

}

static void AddNode(Node * new_node, Node * root)

{

// new_node->item的指针，不是new_node的指针->item

if (ToLeft(&new_node->item, &root->item))

{

if (root->left == NULL) //空子数

{

root->left = new_node; //因此把节点添加到此处

} else {

AddNode(new_node, root->left); //否则处理该子树

}

} else if (ToRight(&new_node->item, &root->item)) {

if (root->right == NULL)

{

root->right = new_node;

} else {

AddNode(new_node, root->right);

}

} else { //不允许含有相同的项目

fprintf(stderr, "location error in AddNode()\n");

exit(1);

}

static bool ToLeft(const Item * i1, const Item * i2)

{

int comp1;

if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)

{

return true;

} else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0) {

return true;

} else {

return false;

}

static bool ToRight(const Item * i1, const Item * i2)

{

int comp1;

if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)

{

return true;

} else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0) {

return true;

} else {

return false;

}

static Node * MakeNode(const Item * pi)

{

Node * new_node;

new_node = (Node *) malloc(sizeof(Node));

if (new_node != NULL)

{

new_node->item = *pi;

new_node->left = NULL;

new_node->right = NULL;

}

return new_node;

}

static Pair SeekItem(const Item * pi, const Tree * ptree)

{

Pair look;

look.parent = NULL;

look.child = ptree->root;

if (look.child == NULL)

{

return look;

}

while(look.child != NULL)

{

if (ToLeft(pi, &(look.child->item)))

{

look.parent = look.child;

look.child = look.child->left;

} else if (ToRight(pi, &(look.child->item))) {

look.parent = look.child;

look.child = look.child->right;

} else {

//break出循环，说明在树中找到了相关项

//如果循环到look.child == NULL，表示没有找到相关项

break;

}

return look;

}

static void DeleteNode(Node **ptr) //ptr是指向目标节点的父节点指针成员的地址

{

Node * temp;

puts((*ptr)->item.petname);

if((*ptr)->left == NULL)

{

// 左节点为空，将其右节点顶上

temp = *ptr;

*ptr = (*ptr)->right;

} else if ((*ptr)->right == NULL) {

// 右节点为空，将其左节点顶上

temp = *ptr;

*ptr = (*ptr)->left;

} else {

//被删除的节点有两个子节点

//从左节点起，一路向子节点的右节点寻找，直到找到一个空位(NULL)

//将右节点顶在左节点的最右子节点的空位上

//将左节点顶为根节点

for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)

{

continue;

}

temp->right = (*ptr)->right;

temp = *ptr;

*ptr = (*ptr)->left;

}

//释放需要删除的节点(地址指向临时节点)

free(temp);

}

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"

char menu(void);
void addpet(Tree * pt);
void droppet(Tree * pt);
void showpets(const Tree * pt);
void findpet(const Tree * pt);
void printitem(Item item);
void uppercase(char * str);

int main(int argc, char const *argv[])
{
    /*
            数组                                      链表    
    优点：  C对其直接支持                             运行时决定其大小                            
            提供随机访问                              快速插入和删除元素

    缺点：  编译时决定其大小                          不能随机访问(如果你要
            插入和删除元素很费时                      查找链表中的某个值，需要                  
            (需要在数组头部或中间位置，               遍历链表，直到找到为止)
            插入或删除元素时，需要调整                用户必须提供编程支持
            后面的所有元素)

    总结：如果需要频繁插入和删除元素，并且不需要经常搜索，链表是更好的选择
          如果列表基本稳定，只是偶尔插入或删除一些元素，但却需要经常搜索，则数组是更好的选择

          如果需要两者兼备，二叉搜索树，可能正是你所需要的
          二叉搜索树(binary search tree)是一种结合了折半搜索策略的链接结构
    */
    Tree pets;
    char choice;
    InitializeTree(&pets);
    while((choice = menu()) != 'q')
    {
        switch(choice)
        {
            case 'a': addpet(&pets);break;
            case 'l': showpets(&pets);break;
            case 'f': findpet(&pets);break;
            case 'n': printf("%d pets in club\n", TreeItemCount(&pets));break;
            case 'd': droppet(&pets);break;
            default : puts("switching error");
        }
    }
    DeleteAll(&pets);
    puts("Bye.");
    return 0;
}

char menu(void)
{
    int ch;
    puts("Nerfville Pet Club Membership Program");
    puts("Enter the letter corresponding to your choice");
    puts("a) add a pet");
    puts("l) show list of pets");
    puts("n) number of pets");
    puts("f) find pets");
    puts("d) delete a pet");
    puts("q) quit");

    while((ch = getchar()) != EOF)
    {
        while(getchar() != '\n') continue;  //丢弃输入行的剩余部分
        ch = tolower(ch);
        if (strchr("alrfndq", ch) == NULL)
        {
            puts("Please enter an a,l,f,n,d or q");
        } else {
            break;
        }
    }

    if (ch == EOF)          //令EOF导致程序退出
    {
        ch = 'q';
    }
    return ch;
}

void addpet(Tree * pt)
{
    Item temp;
    if (TreeIsFull(pt))
    {
        puts("No room in the club!");
    } else {
        puts("Please enter name of pet");
        gets(temp.petname);
        puts("Please enter pet kind");
        gets(temp.petkind);
        uppercase(temp.petname);
        uppercase(temp.petkind);
        AddItem(&temp, pt);
    }
}

void showpets(const Tree * pt)
{
    if (TreeIsEmpty(pt))
    {
        puts("No entries!");
    } else {
        Traverse(pt, printitem);
    }
}

void printitem(Item item)
{
    printf("Pet:%-19s Kind:%-19s\n", item.petname, item.petkind);
}

void findpet(const Tree * pt)
{
    Item temp;
    if (TreeIsEmpty(pt))
    {
        puts("No entries!");
        return;
    }
    puts("Please enter name of pet you wish to find");
    gets(temp.petname);
    puts("Please enter pet kind");
    gets(temp.petkind);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s\n", temp.petname, temp.petkind);
    if (InTree(&temp, pt))
    {
        printf("is a member\n");
    } else {
        printf("is not a member\n");
    }
}

void droppet(Tree * pt)
{
    Item temp;
    if (TreeIsEmpty(pt))
    {
        puts("No entries");
        return;
    }
    puts("Please enter name of pet you wish to delete");
    gets(temp.petname);
    puts("Please enter pet kind");
    gets(temp.petkind);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s\n", temp.petname, temp.petkind);
    if (DeleteItem(&temp, pt))
    {
        printf("is dropped from the club\n");
    } else {
        printf("is not a member\n");
    }
}

void uppercase(char * str)
{
    while(*str)
    {
        *str = toupper(*str);
        str++;
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include "tree.h"

char menu(void);

void addpet(Tree * pt);

void droppet(Tree * pt);

void showpets(const Tree * pt);

void findpet(const Tree * pt);

void printitem(Item item);

void uppercase(char * str);

int main(int argc, char const *argv[])

{

数组链表

优点： C对其直接支持运行时决定其大小

提供随机访问快速插入和删除元素

缺点：编译时决定其大小不能随机访问(如果你要

插入和删除元素很费时查找链表中的某个值，需要

(需要在数组头部或中间位置，遍历链表，直到找到为止)

插入或删除元素时，需要调整用户必须提供编程支持

后面的所有元素)

总结：如果需要频繁插入和删除元素，并且不需要经常搜索，链表是更好的选择

如果列表基本稳定，只是偶尔插入或删除一些元素，但却需要经常搜索，则数组是更好的选择

如果需要两者兼备，二叉搜索树，可能正是你所需要的

二叉搜索树(binary search tree)是一种结合了折半搜索策略的链接结构

Tree pets;

char choice;

InitializeTree(&pets);

while((choice = menu()) != 'q')

{

switch(choice)

{

case 'a': addpet(&pets);break;

case 'l': showpets(&pets);break;

case 'f': findpet(&pets);break;

case 'n': printf("%d pets in club\n", TreeItemCount(&pets));break;

case 'd': droppet(&pets);break;

default : puts("switching error");

}

DeleteAll(&pets);

puts("Bye.");

return 0;

}

char menu(void)

{

int ch;

puts("Nerfville Pet Club Membership Program");

puts("Enter the letter corresponding to your choice");

puts("a) add a pet");

puts("l) show list of pets");

puts("n) number of pets");

puts("f) find pets");

puts("d) delete a pet");

puts("q) quit");

while((ch = getchar()) != EOF)

{

while(getchar() != '\n') continue; //丢弃输入行的剩余部分

ch = tolower(ch);

if (strchr("alrfndq", ch) == NULL)

{

puts("Please enter an a,l,f,n,d or q");

} else {

break;

}

if (ch == EOF) //令EOF导致程序退出

{

ch = 'q';

}

return ch;

}

void addpet(Tree * pt)

{

Item temp;

if (TreeIsFull(pt))

{

puts("No room in the club!");

} else {

puts("Please enter name of pet");

gets(temp.petname);

puts("Please enter pet kind");

gets(temp.petkind);

uppercase(temp.petname);

uppercase(temp.petkind);

AddItem(&temp, pt);

}

void showpets(const Tree * pt)

{

if (TreeIsEmpty(pt))

{

puts("No entries!");

} else {

Traverse(pt, printitem);

}

void printitem(Item item)

{

printf("Pet:%-19s Kind:%-19s\n", item.petname, item.petkind);

}

void findpet(const Tree * pt)

{

Item temp;

if (TreeIsEmpty(pt))

{

puts("No entries!");

return;

}

puts("Please enter name of pet you wish to find");

gets(temp.petname);

puts("Please enter pet kind");

gets(temp.petkind);

uppercase(temp.petname);

uppercase(temp.petkind);

printf("%s the %s\n", temp.petname, temp.petkind);

if (InTree(&temp, pt))

{

printf("is a member\n");

} else {

printf("is not a member\n");

}

void droppet(Tree * pt)

{

Item temp;

if (TreeIsEmpty(pt))

{

puts("No entries");

return;

}

puts("Please enter name of pet you wish to delete");

gets(temp.petname);

puts("Please enter pet kind");

gets(temp.petkind);

uppercase(temp.petname);

uppercase(temp.petkind);

printf("%s the %s\n", temp.petname, temp.petkind);

if (DeleteItem(&temp, pt))

{

printf("is dropped from the club\n");

} else {

printf("is not a member\n");

}

void uppercase(char * str)

{

while(*str)

{

*str = toupper(*str);

str++;

}

C语言简单队列实现

在 2016年7月1日上张贴由 BestLove

//queue.h
#pragma c9x on
#ifndef _QUEUE_H_

#define _QUEUE_H_

#include <stdbool.h>

//在此处插入Item的类型定义
typedef struct item
{
    long arrive;        //一位顾客加入队列的时间
    int processtime;    //该顾客需要咨询的时间
} Item;

#define MAXQUEUE 10

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct queue
{
    Node * front;   //指向队列首的指针
    Node * rear;    //指向队列尾的指针
    int items;      //队列中项目的个数
} Queue;

/*
    操作：初始化队列
    操作前：pq指向一个队列
    操作后：该队列初始化为空队列
*/
void InitializeQueue(Queue * pq);

/*
    操作：检查队列是否已满
    操作前：pq指向一个先前已初始化过的队列
    操作后：如果该队列满了，则返回true，否则返回false
*/
bool QueueIsFull(const Queue * pq);

/*
    操作：检查队列是否为空
    操作前：pq指向一个先前已初始化过的队列
    操作后：如果该队列为空，则返回true，否则返回false
*/
bool QueueIsEmpty(const Queue * pq);

/*
    操作：确定队列中项目的个数
    操作前：pq指向一个先前已初始化过的队列
    操作后：返回队列中项目的个数
*/
int QueueItemCount(const Queue * pq);

/*
    操作：向队列尾部添加项目
    操作前：pq指向一个先前已初始化过的队列
            item是要添加到队列尾部的项目
    操作后：如果队列未满，item被添加到
            队列尾部，函数返回ture，否则
            不改变队列，函数返回false
*/
bool EnQueue(const Item item, Queue * pq);

/*
    操作：从队列首端删除项目
    操作前：pq指向一个先前已初始化过的队列
    操作后：如果队列非空，队列首端的项目
            被复制到*pitem，并被从队列中删除，
            函数返回true，如果这个操作使队列
            为空，把队列重置为空队列
            如果队列开始时为空
            不改变队列，函数返回false
*/
bool DeQueue(Item * pitem, Queue * pq);

/*
    操作：清空队列
    操作前：pq指向一个先前已初始化过的队列
    操作后：队列被清空
*/
void EmptyTheQueue(Queue * pq);

#endif

//queue.h

#pragma c9x on

#ifndef _QUEUE_H_

#define _QUEUE_H_

#include <stdbool.h>

//在此处插入Item的类型定义

typedef struct item

{

long arrive; //一位顾客加入队列的时间

int processtime; //该顾客需要咨询的时间

} Item;

#define MAXQUEUE 10

typedef struct node

{

Item item;

struct node * next;

} Node;

typedef struct queue

{

Node * front; //指向队列首的指针

Node * rear; //指向队列尾的指针

int items; //队列中项目的个数

} Queue;

操作：初始化队列

操作前：pq指向一个队列

操作后：该队列初始化为空队列

void InitializeQueue(Queue * pq);

操作：检查队列是否已满

操作前：pq指向一个先前已初始化过的队列

操作后：如果该队列满了，则返回true，否则返回false

bool QueueIsFull(const Queue * pq);

操作：检查队列是否为空

操作前：pq指向一个先前已初始化过的队列

操作后：如果该队列为空，则返回true，否则返回false

bool QueueIsEmpty(const Queue * pq);

操作：确定队列中项目的个数

操作前：pq指向一个先前已初始化过的队列

操作后：返回队列中项目的个数

int QueueItemCount(const Queue * pq);

操作：向队列尾部添加项目

操作前：pq指向一个先前已初始化过的队列

item是要添加到队列尾部的项目

操作后：如果队列未满，item被添加到

队列尾部，函数返回ture，否则

不改变队列，函数返回false

bool EnQueue(const Item item, Queue * pq);

操作：从队列首端删除项目

操作前：pq指向一个先前已初始化过的队列

操作后：如果队列非空，队列首端的项目

被复制到*pitem，并被从队列中删除，

函数返回true，如果这个操作使队列

为空，把队列重置为空队列

如果队列开始时为空

不改变队列，函数返回false

bool DeQueue(Item * pitem, Queue * pq);

操作：清空队列

操作前：pq指向一个先前已初始化过的队列

操作后：队列被清空

void EmptyTheQueue(Queue * pq);

#endif

//queue.c
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

//局部函数声明
static void CopyToNode(Item item, Node * pn);
static void CopyToItem(Node * pn, Item * pi);

void InitializeQueue(Queue * pq)
{
    pq->front = pq->rear = NULL;
    pq->items = 0;
}

bool QueueIsFull(const Queue * pq)
{
    return pq->items == MAXQUEUE;
}

bool QueueIsEmpty(const Queue * pq)
{
    return pq->items == 0;
}

int QueueItemCount(const Queue * pq)
{
    return pq->items;
}

bool EnQueue(const Item item, Queue * pq)
{
    Node * pnew;
    if (QueueIsFull(pq))
    {
        return false;
    }
    pnew = (Node *) malloc(sizeof(Node));
    if (pnew == NULL)
    {
        fprintf(stderr, "Unable to allocate memory!\n");
        exit(1);
    }
    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (QueueIsEmpty(pq))
    {
        pq->front = pnew;
    } else {
        pq->rear->next = pnew;
    }
    pq->rear = pnew;
    pq->items++;
    return true;
}

bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt;
    if (QueueIsEmpty(pq))
    {
        return false;
    }
    CopyToItem(pq->front, pitem);
    pt = pq->front;
    pq->front = pq->front->next;
    free(pt);
    pq->items--;
    if (pq->items == 0)
    {
        pq->rear = NULL;
    }
    return true;
}

void EmptyTheQueue(Queue * pq)
{
    Item dummy;
    while(!QueueIsEmpty(pq))
    {
        DeQueue(&dummy, pq);
    }
}

static void CopyToNode(Item item, Node * pn)
{
    pn->item = item;
}

static void CopyToItem(Node * pn, Item * pi)
{
    *pi = pn->item;
}

//queue.c

#include <stdio.h>

#include <stdlib.h>

#include "queue.h"

//局部函数声明

static void CopyToNode(Item item, Node * pn);

static void CopyToItem(Node * pn, Item * pi);

void InitializeQueue(Queue * pq)

{

pq->front = pq->rear = NULL;

pq->items = 0;

}

bool QueueIsFull(const Queue * pq)

{

return pq->items == MAXQUEUE;

}

bool QueueIsEmpty(const Queue * pq)

{

return pq->items == 0;

}

int QueueItemCount(const Queue * pq)

{

return pq->items;

}

bool EnQueue(const Item item, Queue * pq)

{

Node * pnew;

if (QueueIsFull(pq))

{

return false;

}

pnew = (Node *) malloc(sizeof(Node));

if (pnew == NULL)

{

fprintf(stderr, "Unable to allocate memory!\n");

exit(1);

}

CopyToNode(item, pnew);

pnew->next = NULL;

if (QueueIsEmpty(pq))

{

pq->front = pnew;

} else {

pq->rear->next = pnew;

}

pq->rear = pnew;

pq->items++;

return true;

}

bool DeQueue(Item * pitem, Queue * pq)

{

Node * pt;

if (QueueIsEmpty(pq))

{

return false;

}

CopyToItem(pq->front, pitem);

pt = pq->front;

pq->front = pq->front->next;

free(pt);

pq->items--;

if (pq->items == 0)

{

pq->rear = NULL;

}

return true;

}

void EmptyTheQueue(Queue * pq)

{

Item dummy;

while(!QueueIsEmpty(pq))

{

DeQueue(&dummy, pq);

}

static void CopyToNode(Item item, Node * pn)

{

pn->item = item;

}

static void CopyToItem(Node * pn, Item * pi)

{

*pi = pn->item;

}

// 使用队列，做一个一段时间(小时)内，平均每小时接受顾客数的简单数据分析
// 每个顾客所消耗的时间是1-3分钟 最多排10个客户，超出长度的客户不再接受
// gcc -c queue.c  gcc main.c queue.o
#include <stdio.h>
#include <stdlib.h>                 //为rand()、srand()函数提供原型
#include <time.h>                   //为time()函数提供原型
#include "queue.h"
#define MIN_PER_PR 60.0             //顾客到达的平均间隔时间

bool newcustomer(double x);         //有新顾客到来吗
Item customertime(long when);       //设置顾客参量

int main(int argc, char const *argv[])
{
    Queue line;
    Item temp;                      //关于新顾客的数据
    int hours;                      //模拟的小时数
    int perhour;                    //每小时顾客的平均数
    long cycle,cyclelimit;          //循环计数器，计数器的上界
    long turnaways = 0;             //因队列已满而被拒绝的顾客数
    long customers = 0;             //被加入到队列的顾客数
    long served = 0;                //在模拟期间得到服务的顾客数
    long sum_line = 0;              //累计的队列长度
    int wait_time = 0;              //从当前到sigmund空闲所需的时间
    double min_per_cust;            //顾客到来的平均间隔时间
    long line_wait = 0;             //队列累计等待时间

    InitializeQueue(&line);         //初始化队列，开启服务窗口
    srand(time(0));                 //随机初始化rand()函数
    puts("Case Study:Sigmund Lander's Advice Booth");
    puts("Enter the number of simulation hours:");
    // 模拟输入小时数
    scanf("%d", &hours);
    // 转换成分钟数
    cyclelimit = MIN_PER_PR * hours;
    puts("Enter the average number of customers per hour");
    // 模拟输入平均每小时的顾客数
    scanf("%d", &perhour);
    // 比如每小时顾客数为20，那平均间隔就是3分钟一个
    min_per_cust = MIN_PER_PR / perhour;
    // 循环每分钟检查是否有顾客到来，根据队列(排队)情况，做出相应统计
    for (cycle = 0; cycle < cyclelimit; ++cycle)
    {   
        // 如果有新用户到来 因为平均间隔是个平均值，所以在函数中加入rand()增加一些随机性
        // 当然，间隔越短，返回true(有新用户到来)的可能性更大
        if (newcustomer(min_per_cust))
        {
            // 如果有新顾客到来，是否还能排上队(超过10个就排不上了)
            if (QueueIsFull(&line)) {
                // 统计没排上队的顾客数+1
                turnaways++;
            } else {
                // 统计排上队的顾客数+1
                customers++;
                // 将顾客排到队伍中，随机一个[1,3]之间的，顾客需要消耗的时间
                temp = customertime(cycle);
                EnQueue(temp, &line);
            }
        }
        // 看看当前时间点，正在处理的顾客处理完了吗
        // 如果处理完了，看看还有没有需要处理的顾客(正在排队的顾客)
        if (wait_time <= 0 && !QueueIsEmpty(&line))
        {
            // 处理完，并且有人排队，就继续处理。。
            DeQueue(&temp, &line);
            // 获取这个顾客需要服务的时间（如果下一位顾客上来询问，就可以告诉他还要等多久。。）
            wait_time = temp.processtime;
            // 统计等待时间（根据当前顾客从排队，到接受服务等了多久，然后累加所有顾客的等待时间）
            line_wait += cycle - temp.arrive;
            // 统计服务顾客数+1
            served++;
        }
        // 1分钟过去了，顾客的服务时间消耗掉1分钟。。
        if (wait_time > 0)
        {
            wait_time--;
        }
        // 统计队列长度，如果一直排满10个，这个值会变得较大
        sum_line += QueueItemCount(&line);
    }
    // 最后输出统计信息
    if (customers > 0)
    {
        printf("customers accepted: %ld\n", customers);     //排到队伍的顾客数
        printf("customers served: %ld\n", served);          //接受服务的顾客数
        printf("turnaways: %ld\n", turnaways);              //被拒绝的顾客数
        printf("average queue size:%.2f\n", (double)sum_line / cyclelimit);     //平均排队长度
        printf("average wait time: %.2f minutes\n", (double)line_wait / served);    //平均等待时间
    } else {
        puts("No customers!");
    }
    EmptyTheQueue(&line);
    puts("Bye!");
    return 0;
}

/*
    x是顾客到来的平均间隔时间(以秒计)
    如果这1分钟内有顾客到来，则返回true
*/
bool newcustomer(double x)
{
    if (rand() * x / RAND_MAX < 1)
    {
        return true;
    } else {
        return false;
    }
}

/*
    when是顾客到来的时间
    函数返回一个Item结构，该结构的顾客到来时间设置为when
    需要的咨询时间设置为一个范围1到3之间的随机值
*/
Item customertime(long when)
{
    Item cust;
    cust.processtime = rand() % 3 + 1;
    cust.arrive = when;
    return cust;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

// 使用队列，做一个一段时间(小时)内，平均每小时接受顾客数的简单数据分析

// 每个顾客所消耗的时间是1-3分钟最多排10个客户，超出长度的客户不再接受

// gcc -c queue.c gcc main.c queue.o

#include <stdio.h>

#include <stdlib.h> //为rand()、srand()函数提供原型

#include <time.h> //为time()函数提供原型

#include "queue.h"

#define MIN_PER_PR 60.0 //顾客到达的平均间隔时间

bool newcustomer(double x); //有新顾客到来吗

Item customertime(long when); //设置顾客参量

int main(int argc, char const *argv[])

{

Queue line;

Item temp; //关于新顾客的数据

int hours; //模拟的小时数

int perhour; //每小时顾客的平均数

long cycle,cyclelimit; //循环计数器，计数器的上界

long turnaways = 0; //因队列已满而被拒绝的顾客数

long customers = 0; //被加入到队列的顾客数

long served = 0; //在模拟期间得到服务的顾客数

long sum_line = 0; //累计的队列长度

int wait_time = 0; //从当前到sigmund空闲所需的时间

double min_per_cust; //顾客到来的平均间隔时间

long line_wait = 0; //队列累计等待时间

InitializeQueue(&line); //初始化队列，开启服务窗口

srand(time(0)); //随机初始化rand()函数

puts("Case Study:Sigmund Lander's Advice Booth");

puts("Enter the number of simulation hours:");

// 模拟输入小时数

scanf("%d", &hours);

// 转换成分钟数

cyclelimit = MIN_PER_PR * hours;

puts("Enter the average number of customers per hour");

// 模拟输入平均每小时的顾客数

scanf("%d", &perhour);

// 比如每小时顾客数为20，那平均间隔就是3分钟一个

min_per_cust = MIN_PER_PR / perhour;

// 循环每分钟检查是否有顾客到来，根据队列(排队)情况，做出相应统计

for (cycle = 0; cycle < cyclelimit; ++cycle)

{

// 如果有新用户到来因为平均间隔是个平均值，所以在函数中加入rand()增加一些随机性

// 当然，间隔越短，返回true(有新用户到来)的可能性更大

if (newcustomer(min_per_cust))

{

// 如果有新顾客到来，是否还能排上队(超过10个就排不上了)

if (QueueIsFull(&line)) {

// 统计没排上队的顾客数+1

turnaways++;

} else {

// 统计排上队的顾客数+1

customers++;

// 将顾客排到队伍中，随机一个[1,3]之间的，顾客需要消耗的时间

temp = customertime(cycle);

EnQueue(temp, &line);

}

// 看看当前时间点，正在处理的顾客处理完了吗

// 如果处理完了，看看还有没有需要处理的顾客(正在排队的顾客)

if (wait_time <= 0 && !QueueIsEmpty(&line))

{

// 处理完，并且有人排队，就继续处理。。

DeQueue(&temp, &line);

// 获取这个顾客需要服务的时间（如果下一位顾客上来询问，就可以告诉他还要等多久。。）

wait_time = temp.processtime;

// 统计等待时间（根据当前顾客从排队，到接受服务等了多久，然后累加所有顾客的等待时间）

line_wait += cycle - temp.arrive;

// 统计服务顾客数+1

served++;

}

// 1分钟过去了，顾客的服务时间消耗掉1分钟。。

if (wait_time > 0)

{

wait_time--;

}

// 统计队列长度，如果一直排满10个，这个值会变得较大

sum_line += QueueItemCount(&line);

}

// 最后输出统计信息

if (customers > 0)

{

printf("customers accepted: %ld\n", customers); //排到队伍的顾客数

printf("customers served: %ld\n", served); //接受服务的顾客数

printf("turnaways: %ld\n", turnaways); //被拒绝的顾客数

printf("average queue size:%.2f\n", (double)sum_line / cyclelimit); //平均排队长度

printf("average wait time: %.2f minutes\n", (double)line_wait / served); //平均等待时间

} else {

puts("No customers!");

}

EmptyTheQueue(&line);

puts("Bye!");

return 0;

}

x是顾客到来的平均间隔时间(以秒计)

如果这1分钟内有顾客到来，则返回true

bool newcustomer(double x)

{

if (rand() * x / RAND_MAX < 1)

{

return true;

} else {

return false;

}

when是顾客到来的时间

函数返回一个Item结构，该结构的顾客到来时间设置为when

需要的咨询时间设置为一个范围1到3之间的随机值

Item customertime(long when)

{

Item cust;

cust.processtime = rand() % 3 + 1;

cust.arrive = when;

return cust;

}

抽象数据类型ADT(abstract data type)、链表、列表

在 2016年6月29日上张贴由 BestLove

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TSZIE 45
struct film
{
    char title[TSZIE];
    int rating;
    struct film *next;
};
int main(int argc, char const *argv[])
{
    struct film *head = NULL;
    struct film *prev, * current;
    char input[TSZIE];
    puts("Enter the title");
    while(gets(input) != NULL && input[0] != '\0')
    {
        current = (struct film *)malloc(sizeof(struct film));
        strcpy(current->title, input);
        if (head == NULL)
        {
            head = current;
        }
        else
        {
            prev->next = current;
        }
        current->next = NULL;
        puts("Enter the rating<0-10>");
        scanf("%d", &current->rating);
        while(getchar() != '\n')
        {
            continue;
        }
        puts("Enter the next title");
        prev = current;
    }
    if (head == NULL)
    {
        puts("no films");
        return 1;
    }
    current = head;
    while(current != NULL)
    {
        printf("title:%s\n", current->title);
        printf("rating:%d\n", current->rating);
        current = current->next;
    }
    current = head;
    while(current != NULL)
    {
        free(current);
        current = current->next;
    }
    puts("done");
    return 0;
}

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define TSZIE 45

struct film

{

char title[TSZIE];

int rating;

struct film *next;

};

int main(int argc, char const *argv[])

{

struct film *head = NULL;

struct film *prev, * current;

char input[TSZIE];

puts("Enter the title");

while(gets(input) != NULL && input[0] != '\0')

{

current = (struct film *)malloc(sizeof(struct film));

strcpy(current->title, input);

if (head == NULL)

{

head = current;

}

else

{

prev->next = current;

}

current->next = NULL;

puts("Enter the rating<0-10>");

scanf("%d", &current->rating);

while(getchar() != '\n')

{

continue;

}

puts("Enter the next title");

prev = current;

}

if (head == NULL)

{

puts("no films");

return 1;

}

current = head;

while(current != NULL)

{

printf("title:%s\n", current->title);

printf("rating:%d\n", current->rating);

current = current->next;

}

current = head;

while(current != NULL)

{

free(current);

current = current->next;

}

puts("done");

return 0;

}

#ifndef LIST_H_
//标记变量，防止list.h被重复#include
#define LIST_H_
#include <stdbool.h>    //c99特性
#define TSZIE 45        //特定于程序的声明，存放影片名的数组大小
struct film
{
    char title[TSZIE];
    int rating;
};
typedef struct film Item;   //一般类型定义

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef Node * List;
/*
    操作：初始化一个列表
    操作前：plist指向一个列表
    操作后：该列表被初始化为空列表
*/
void InitializeList(List * plist);

/*
    操作：确定列表是否为空列表
    操作前：plist指向一个已初始化的列表
    操作后：如果该列表为空则返回true，否则返回false
*/
bool ListIsEmpty(const List * plist);

/*
    操作：确定列表中的项目的个数
    操作前：plist指向一个已初始化的列表
    操作后：返回该列表中项目的个数
*/
unsigned int ListItemCount(const List * plist);

/*
    操作：在列表尾部添加一个项目
    操作前：item是要被增加到列表的项目
            plist指向一个已初始化的列表
    操作后：如果可能的话，在列表尾部添加一个新项目，
            函数返回true，否则函数返回false
*/
bool AddItem(Item item, List * plist);

/*
    操作：把一个函数作用于列表中的每个项目
    操作前：plist指向一个已初始化的列表
            pfun指向一个函数，该函数接受
            一个Item参数并且无返回值
    操作后：pfun指向的函数被作用到
            列表中的每个项目一次
 */
void Traverse(const List * plist, void(* pfun)(Item item));

/*
    操作：释放已分配的内存(如果有)
    操作前：plist指向一个已初始化的列表
    操作后：为该列表分配的内存已被释放
            并且该列表被置为空列表
 */
void EmptyTheList(List * plist);

#endif

#ifndef LIST_H_

//标记变量，防止list.h被重复#include

#define LIST_H_

#include <stdbool.h> //c99特性

#define TSZIE 45 //特定于程序的声明，存放影片名的数组大小

struct film

{

char title[TSZIE];

int rating;

};

typedef struct film Item; //一般类型定义

typedef struct node

{

Item item;

struct node * next;

} Node;

typedef Node * List;

操作：初始化一个列表

操作前：plist指向一个列表

操作后：该列表被初始化为空列表

void InitializeList(List * plist);

操作：确定列表是否为空列表

操作前：plist指向一个已初始化的列表

操作后：如果该列表为空则返回true，否则返回false

bool ListIsEmpty(const List * plist);

操作：确定列表中的项目的个数

操作前：plist指向一个已初始化的列表

操作后：返回该列表中项目的个数

unsigned int ListItemCount(const List * plist);

操作：在列表尾部添加一个项目

操作前：item是要被增加到列表的项目

plist指向一个已初始化的列表

操作后：如果可能的话，在列表尾部添加一个新项目，

函数返回true，否则函数返回false

bool AddItem(Item item, List * plist);

操作：把一个函数作用于列表中的每个项目

操作前：plist指向一个已初始化的列表

pfun指向一个函数，该函数接受

一个Item参数并且无返回值

操作后：pfun指向的函数被作用到

列表中的每个项目一次

void Traverse(const List * plist, void(* pfun)(Item item));

操作：释放已分配的内存(如果有)

操作前：plist指向一个已初始化的列表

操作后：为该列表分配的内存已被释放

并且该列表被置为空列表

void EmptyTheList(List * plist);

#endif

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

//局部函数原型
static void CopyToNode(Item item, Node * pnode);

void InitializeList(List * plist)
{
    *plist = NULL;
}

bool ListIsEmpty(const List * plist)
{
    if (*plist == NULL)
    {
        return true;
    } else {
        return false;
    }
}

unsigned int ListItemCount(const List * plist)
{
    unsigned int count = 0;
    Node * pnode = *plist;  //设置到列表的开始处
    while(pnode != NULL)
    {
        ++count;
        pnode = pnode->next;
    }
    return count;
}

bool AddItem(Item item, List * plist)
{
    Node * pnew;
    Node * scan = *plist;
    pnew = (Node *)malloc(sizeof(Node));
    if (pnew == NULL)
    {
        return false;
    }
    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (scan == NULL)
    {
        *plist = pnew;
    } else {
        while(scan->next != NULL)
        {
            scan = scan->next;
        }
        scan->next = pnew;
    }
    return true;
}

void Traverse(const List * plist, void(* pfun)(Item item))
{
    Node * pnode = *plist;
    while(pnode != NULL)
    {
        (* pfun)(pnode->item);  //调用函数，操作列表中的项目
        pnode = pnode->next;
    }
}

void EmptyTheList(List * plist)
{
    Node * psave;
    while(*plist != NULL)
    {
        psave = (*plist)->next;
        free(*plist);
        *plist = psave;
    }
}

static void CopyToNode(Item item, Node * pnode)
{
    pnode->item = item;
}

#include <stdio.h>

#include <stdlib.h>

#include "list.h"

//局部函数原型

static void CopyToNode(Item item, Node * pnode);

void InitializeList(List * plist)

{

*plist = NULL;

}

bool ListIsEmpty(const List * plist)

{

if (*plist == NULL)

{

return true;

} else {

return false;

}

unsigned int ListItemCount(const List * plist)

{

unsigned int count = 0;

Node * pnode = *plist; //设置到列表的开始处

while(pnode != NULL)

{

++count;

pnode = pnode->next;

}

return count;

}

bool AddItem(Item item, List * plist)

{

Node * pnew;

Node * scan = *plist;

pnew = (Node *)malloc(sizeof(Node));

if (pnew == NULL)

{

return false;

}

CopyToNode(item, pnew);

pnew->next = NULL;

if (scan == NULL)

{

*plist = pnew;

} else {

while(scan->next != NULL)

{

scan = scan->next;

}

scan->next = pnew;

}

return true;

}

void Traverse(const List * plist, void(* pfun)(Item item))

{

Node * pnode = *plist;

while(pnode != NULL)

{

(* pfun)(pnode->item); //调用函数，操作列表中的项目

pnode = pnode->next;

}

void EmptyTheList(List * plist)

{

Node * psave;

while(*plist != NULL)

{

psave = (*plist)->next;

free(*plist);

*plist = psave;

}

static void CopyToNode(Item item, Node * pnode)

{

pnode->item = item;

}

// gcc -c list.c    
// gcc main.c list.o
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
void showmovies(Item item);
int main(int argc, char const *argv[])
{
    List movies;
    Item temp;
    InitializeList(&movies);
    puts("Enter first movie title:");
    while(gets(temp.title) != NULL && temp.title[0] != '\0')
    {
        puts("Enter your rating <0-10>:");
        scanf("%d", &temp.rating);
        while(getchar() != '\n')
        {
            continue;
        }
        if (AddItem(temp, &movies) == false)
        {
            fprintf(stderr, "Problem allocating memory\n");
            break;
        }
        puts("Enter next movie title(epmty line to stop)");
    }
    if (ListIsEmpty(&movies))
    {
        puts("No data entered");
    } else {
        puts("here is the movie list");
        Traverse(&movies, showmovies);
    }
    printf("you entered %d movies\n", ListItemCount(&movies));
    EmptyTheList(&movies);
    puts("done");
    return 0;
}
void showmovies(Item item)
{
    printf("movie:%s rating:%d\n", item.title, item.rating);
}

// gcc -c list.c

// gcc main.c list.o

#include <stdio.h>

#include <stdlib.h>

#include "list.h"

void showmovies(Item item);

int main(int argc, char const *argv[])

{

List movies;

Item temp;

InitializeList(&movies);

puts("Enter first movie title:");

while(gets(temp.title) != NULL && temp.title[0] != '\0')

{

puts("Enter your rating <0-10>:");

scanf("%d", &temp.rating);

while(getchar() != '\n')

{

continue;

}

if (AddItem(temp, &movies) == false)

{

fprintf(stderr, "Problem allocating memory\n");

break;

}

puts("Enter next movie title(epmty line to stop)");

}

if (ListIsEmpty(&movies))

{

puts("No data entered");

} else {

puts("here is the movie list");

Traverse(&movies, showmovies);

}

printf("you entered %d movies\n", ListItemCount(&movies));

EmptyTheList(&movies);

puts("done");

return 0;

}

void showmovies(Item item)

{

printf("movie:%s rating:%d\n", item.title, item.rating);

}

基础了解(二十)

在 2016年6月29日2016年6月29日上张贴由 BestLove

// atexit(ptr) 注册退出事件
#include <stdio.h>
#include <stdlib.h>
void event1(void);
void event2(void);
int main(int argc, char const *argv[])
{
    atexit(event1);
    atexit(event2);
    /*
        当程序主动调用exit()或main函数中return触发exit()后
        会后进先出地执行被注册到atexit()中的函数
        this is the event2
        this is the event1
     */
    return 0;
}
void event1(void)
{
    puts("this is the event1");
}
void event2(void)
{
    puts("this is the event2");
}

// 快速排序qsort(数组指针,数组长度,单个数组元素长度,自定义排序函数指针)
#include <stdio.h>
#include <stdlib.h>
#define NUM 40
void fillarray(double ar[], int n);
void showarray(const double ar[], int n);
int mycomp(const void * p1, const void * p2);
int main(int argc, char const *argv[])
{
    double vals[NUM];
    fillarray(vals, NUM);
    puts("Random list:");
    showarray(vals, NUM);
    qsort(vals, NUM, sizeof(double), mycomp);
    puts("\nSorted list:");
    showarray(vals, NUM);
    return 0;
}
void fillarray(double ar[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        ar[i] = (double)rand() / ((double)rand() + 0.1);
    }
}
void showarray(const double ar[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        printf("%9.4f ", ar[i]);
        if (i % 6 == 5)
        {
            putchar('\n');
        }
    }
}
int mycomp(const void * p1, const void * p2)
{
    // 需要使用指向double的指针访问值
    const double * a1 = (const double *)p1;
    const double * a2 = (const double *)p2;
    if (*a1 < *a2)
    {
        return -1;
    } else if (*a1 == *a2)
    {
        return 0;
    } else {
        return 1;
    }
}

// 诊断库(用于调试)
#include <stdio.h>
#define NDEBUG  //如果调试完毕，直接在包含assert.h之前定义宏NDEBUG，就能禁用assert()功能
#include <assert.h>
int main(int argc, char const *argv[])
{
    int i = 0;
    assert(i == 0);
    puts("ok");
    // 断言当i=0时，程序直接退出，输出相关错误信息(文件名、行号)
    assert(i != 0);
    puts("done");
    return 0;
}

// 可变参数 stdarg.h
#include <stdio.h>
#include <stdarg.h>
double sum(int, ...);
int main(int argc, char const *argv[])
{
    /*
        在函数原型中使用省略号
        在函数定义中创建一个va_list类型的变量
        用宏将该变量初始化为一个参数列表
        用宏访问这个参数列表
        用宏完成清理工作
        void f1(int n, ...);                        //合法
        int f2(int n, const char * s, ...);         //合法
        char f3(char c1, ..., char c2);             //不合法，省略号必须是最后一个参量
        double f4();                                //不合法，没有任何参量
     */
    double s, t;
    // 第一个参数3，描述了后面有3个可变参数
    // printf()中估计是统计%d、%s等的数量，来计算出可变参数数量的
    s = sum(3, 1.1, 2.5, 13.3);
    t = sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1);
    printf("return value for sum(3, 1.1, 2.5, 13.3) %g\n", s);
    printf("return value for sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1) %g\n", t);
    return 0;
}
double sum(int lim, ...)
{
    va_list ap;             //声明用于存放参数的变量
    double tot = 0;
    int i;
    va_start(ap, lim);      //把ap初始化为参数列表
    for (i = 0; i < lim; ++i)
    {
        tot += va_arg(ap, double);  //访问参数列表中的每一个选项
    }
    va_end(ap);             //清理工作
    return tot;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

// atexit(ptr) 注册退出事件

#include <stdio.h>

#include <stdlib.h>

void event1(void);

void event2(void);

int main(int argc, char const *argv[])

{

atexit(event1);

atexit(event2);

当程序主动调用exit()或main函数中return触发exit()后

会后进先出地执行被注册到atexit()中的函数

this is the event2

this is the event1

return 0;

}

void event1(void)

{

puts("this is the event1");

}

void event2(void)

{

puts("this is the event2");

}

// 快速排序qsort(数组指针,数组长度,单个数组元素长度,自定义排序函数指针)

#include <stdio.h>

#include <stdlib.h>

#define NUM 40

void fillarray(double ar[], int n);

void showarray(const double ar[], int n);

int mycomp(const void * p1, const void * p2);

int main(int argc, char const *argv[])

{

double vals[NUM];

fillarray(vals, NUM);

puts("Random list:");

showarray(vals, NUM);

qsort(vals, NUM, sizeof(double), mycomp);

puts("\nSorted list:");

showarray(vals, NUM);

return 0;

}

void fillarray(double ar[], int n)

{

int i;

for (i = 0; i < n; ++i)

{

ar[i] = (double)rand() / ((double)rand() + 0.1);

}

void showarray(const double ar[], int n)

{

int i;

for (i = 0; i < n; ++i)

{

printf("%9.4f ", ar[i]);

if (i % 6 == 5)

{

putchar('\n');

}

int mycomp(const void * p1, const void * p2)

{

// 需要使用指向double的指针访问值

const double * a1 = (const double *)p1;

const double * a2 = (const double *)p2;

if (*a1 < *a2)

{

return -1;

} else if (*a1 == *a2)

{

return 0;

} else {

return 1;

}

// 诊断库(用于调试)

#include <stdio.h>

#define NDEBUG //如果调试完毕，直接在包含assert.h之前定义宏NDEBUG，就能禁用assert()功能

#include <assert.h>

int main(int argc, char const *argv[])

{

int i = 0;

assert(i == 0);

puts("ok");

// 断言当i=0时，程序直接退出，输出相关错误信息(文件名、行号)

assert(i != 0);

puts("done");

return 0;

}

// 可变参数 stdarg.h

#include <stdio.h>

#include <stdarg.h>

double sum(int, ...);

int main(int argc, char const *argv[])

{

在函数原型中使用省略号

在函数定义中创建一个va_list类型的变量

用宏将该变量初始化为一个参数列表

用宏访问这个参数列表

用宏完成清理工作

void f1(int n, ...); //合法

int f2(int n, const char * s, ...); //合法

char f3(char c1, ..., char c2); //不合法，省略号必须是最后一个参量

double f4(); //不合法，没有任何参量

double s, t;

// 第一个参数3，描述了后面有3个可变参数

// printf()中估计是统计%d、%s等的数量，来计算出可变参数数量的

s = sum(3, 1.1, 2.5, 13.3);

t = sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1);

printf("return value for sum(3, 1.1, 2.5, 13.3) %g\n", s);

printf("return value for sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1) %g\n", t);

return 0;

}

double sum(int lim, ...)

{

va_list ap; //声明用于存放参数的变量

double tot = 0;

int i;

va_start(ap, lim); //把ap初始化为参数列表

for (i = 0; i < lim; ++i)

{

tot += va_arg(ap, double); //访问参数列表中的每一个选项

}

va_end(ap); //清理工作

return tot;

}

基础了解(十九)

在 2016年6月28日2016年6月28日上张贴由 BestLove

// #ifndef常见用法，防止包含多个文件或多次包含同一文件后重复定义
#include <stdio.h>
#ifndef _STDIO_H    //通常用文件名、下划线定义宏
    #define _STDIO_H
    // ... 其他定义
#endif
int main(int argc, char const *argv[])
{
    return 0;
}

// #if #elif #if defined()
#include <stdio.h>
#define FLAG 3
#if FLAG == 1
    #include <string.h>
#elif FLAG == 2
    // ...
#elif FLAG == 3
    // ...
#else
    // ...
#endif
// 使用 if defined()代替 ifdef 语法的好处就是可以使用elif
#if defined(FLAG)
    // ...
#elif defined(VAX)
    // ...
#elif defined(MAC)
    // ...
#else
    // ...
#endif
int main(int argc, char const *argv[])
{
    return 0;
}

// 预定义宏 __DATE__  __FILE__  __LINE__  __STDC__  __STDC_HOSTED__  __STDC_VERSION__  __TIME__
// c99 __func__(预定义标识符，具有函数作用域)
#include <stdio.h>
void why_me();
int main(int argc, char const *argv[])
{
    printf("the file is %s\n", __FILE__);
    printf("the date is %s\n", __DATE__);
    printf("the time is %s\n", __TIME__);
    printf("this version is %ld\n", __STDC_HOSTED__);
    printf("this is line %d\n", __LINE__);
    printf("this fucntion is %s\n", __func__);
    why_me();
    return 0;
}
void why_me()
{
    printf("this is line %d\n", __LINE__);
    printf("this fucntion is %s\n", __func__);
}

// #line指令用于重置由__LINE__和__FILE__宏报告的行号和文件名
#include <stdio.h>
#line 1000              //把当前行号重置为1000
#line 10 "cool.c"       //把行号重置为10，文件名重置为cool.c
int main(int argc, char const *argv[])
{
    return 0;
}

// 如果version不是C99中断编译
#include <stdio.h>
#if __STDC_VERSION__ != 199901L
#error Not C99
#endif
int main(int argc, char const *argv[])
{
    return 0;
}

// 在现代编译器中，可用命令行参数或IDE菜单修改编译器的某些配置
// 也可用 #pragma 将编译器指令置于源代码中
#include <stdio.h>
// 在开发C99时 用C9X代表C99 编译器可以使用pragma来启用对C9X的支持
#pragma c9x on
// c99提供了_Pragma预处理器运算符
_Pragma("nonstandardtreatmenttypeB on")
// 等价于
#pragma nonstandardtreatmenttypeB on 
// 如果没有定义LIMIT宏，编译时提示LIMIT not be defined
#ifndef LIMIT
#pragma message("LIMIT not be defined")
#endif
int main(int argc, char const *argv[])
{
    return 0;
}

// #ifndef常见用法，防止包含多个文件或多次包含同一文件后重复定义

#include <stdio.h>

#ifndef _STDIO_H //通常用文件名、下划线定义宏

#define _STDIO_H

// ... 其他定义

#endif

int main(int argc, char const *argv[])

{

return 0;

}

// #if #elif #if defined()

#include <stdio.h>

#define FLAG 3

#if FLAG == 1

#include <string.h>

#elif FLAG == 2

// ...

#elif FLAG == 3

// ...

#else

// ...

#endif

// 使用 if defined()代替 ifdef 语法的好处就是可以使用elif

#if defined(FLAG)

// ...

#elif defined(VAX)

// ...

#elif defined(MAC)

// ...

#else

// ...

#endif

int main(int argc, char const *argv[])

{

return 0;

}

// 预定义宏 __DATE__ __FILE__ __LINE__ __STDC__ __STDC_HOSTED__ __STDC_VERSION__ __TIME__

// c99 __func__(预定义标识符，具有函数作用域)

#include <stdio.h>

void why_me();

int main(int argc, char const *argv[])

{

printf("the file is %s\n", __FILE__);

printf("the date is %s\n", __DATE__);

printf("the time is %s\n", __TIME__);

printf("this version is %ld\n", __STDC_HOSTED__);

printf("this is line %d\n", __LINE__);

printf("this fucntion is %s\n", __func__);

why_me();

return 0;

}

void why_me()

{

printf("this is line %d\n", __LINE__);

printf("this fucntion is %s\n", __func__);

}

// #line指令用于重置由__LINE__和__FILE__宏报告的行号和文件名

#include <stdio.h>

#line 1000 //把当前行号重置为1000

#line 10 "cool.c" //把行号重置为10，文件名重置为cool.c

int main(int argc, char const *argv[])

{

return 0;

}

// 如果version不是C99中断编译

#include <stdio.h>

#if __STDC_VERSION__ != 199901L

#error Not C99

#endif

int main(int argc, char const *argv[])

{

return 0;

}

// 在现代编译器中，可用命令行参数或IDE菜单修改编译器的某些配置

// 也可用 #pragma 将编译器指令置于源代码中

#include <stdio.h>

// 在开发C99时用C9X代表C99 编译器可以使用pragma来启用对C9X的支持

#pragma c9x on

// c99提供了_Pragma预处理器运算符

_Pragma("nonstandardtreatmenttypeB on")

// 等价于

#pragma nonstandardtreatmenttypeB on

// 如果没有定义LIMIT宏，编译时提示LIMIT not be defined

#ifndef LIMIT

#pragma message("LIMIT not be defined")

#endif

int main(int argc, char const *argv[])

{

return 0;

}

唐晓锋–BLOG

This is just a personal note.

分类：c

简单HashTable(取模法)

二叉搜索树

C语言简单队列实现

抽象数据类型ADT(abstract data type)、链表、列表

基础了解(二十)

基础了解(十九)