结构

结构的基本知识

结构是一个或多个变量的集合，这些变量可能为不同的类型，为了处理的方便而将这些变量组织在一个名字之下。关键字struct引入结构声明。结构声明由包含在花括号内的一系列声明组成。关键字struct后面的名字是可选的，称为结构标记。结构标记用于为结构命名，在定义之后，结构标记就代表花括号内的声明，可以用它作为该声明的简写形式。如：

/* 声明一个没有名字的结构体p1 */
struct{
    int x;
    int y;
}p1;

/* 声明一个结构体的模板，没有分配内存 */
struct point{
    int x;
    int y;
};
/* 声明一个结构体p2 */
struct point p2;

结构体的初始化可以在定义后面使用初值表进行，初值表中同每个成员对应的初值必须是常量表达式，如：

p1 = {1,2};

在表达式中，可以通过下列形式引用某个特定结构中的成员：

结构名.成员

其中的结构成员运算符“.”将结构名与成员名连接起来。结构可以嵌套，如：

struct rect{
    struct point pt1;
    struct point pt2;
};
struct rect Rect;
Rect.pt1.x = 1;

结构与函数

结构的合法操作只有几种：作为一个整体复制和赋值，通过&运算符取地址，访问其成员。其中，复制和赋值包括想函数传递参数以及从函数返回值。可以通过以下三种方式向函数传递结构：分别传递各个结构成员，传递整个结构和传递指向结构的指针。对于结构指针来说，可以通过下面的方式进行访问其成员：

struct point *p;
p = &pt;
printf("x= %d,y = %d\n",(*p).x,(*p).y);

结构指针的使用频率非常高，为了使用方便，C语言提供了另一种简写方式：

p->结构体成员

结构数组和sizeof

我们可以定义一个结构数组，并且可以按照数组的方式对元素进行访问。这一点很好理解， 结构的大小是固定的，编译器可以通过地址的偏移得到数组中元素的位置，再根据结构中成员相对于首地址的偏移，就能访问到结构的各个成员了。很多情况下，我们需要知道结构所占的存储空间的大小，所以C语言提供了一个编译时一元运算符sizeof，它可以用来计算任一对象的长度。表达式

sizeof(对象/类型名)

将返回一个整型值，它等于指定对象或类型占用的存储空间字节数。下面是一个例子：

#include<stdio.h>
#include<stdlib.h>
struct key{
    char *word;
    int count;
};

int main(int argc, char const *argv[])
{
    struct key keytab[] = {
        {"auto",0},{"break",0},{"case",0}
    };
    printf("keytab length = %d\n",sizeof(keytab)/sizeof(struct key));
    printf(keytab[0].word);
    system("pause");
    return 0;
}

自引用结构

结构体里面可以含有指向自己结构体的指针，但不能含有一个自己结构体的成员。这也好理解，在编译的时候，我们需要知道结构体的大小，但是如果定义一个本类型的结构体成员，那么将是子子孙孙无穷尽也，这个类型的大小将是无限的，就是一个无穷递归。我觉得对于这个结构体，我们应该记住，只要编译器能通过偏移进行成员的访问即可，至于成员存储了什么东西，编译器并不关心。这里有两个例子，第一个例子是对输入单词的次数统计，使用二叉树进行动态的查找和插入。第二个示例是一个使用拉链法的散列表的例子。

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#define MAXWORD 100

typedef struct node* Node;
struct node{
    char *word;
    int n;
    struct node *left;
    struct node *right;
};

Node createNode(char *s){
    Node node = (Node)malloc(sizeof(struct node));
    node->word = (char *)malloc((strlen(s)+1) * sizeof(char));
    strcpy(node->word,s);
    node->n = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int getWord(char *word,int lim){
    char c;
    char *w = word;
    /* 先跳过非数字或字母的字符 */
    while(!isalnum(c = getchar()) && c!=EOF)
        ;
    /* 如果为EOF则返回 */
    if(c == EOF){
        return c;
    }
    *w++ = c;
    for(;--lim;w++){
        /* 读到非数字或字母就压回输入流 */
        if(!isalnum(*w = getchar())){
            if(c != EOF){
                 ungetc(*w,STDIN_FILENO);
            }
            break;   
        }
    }
    *w = '\0';
    return word[0];
}

Node addNode(Node root,char *s){
    int cmp;
    /* 创建结点 */
    if(root == NULL){
        root = createNode(s);
    }
    else if((cmp = strcmp(s,root->word)) ==0){
        root->n++;
    }else if(cmp < 0){
        root->left = addNode(root->left,s);
    }else{
        root->right = addNode(root->right,s);
    }
    return root;
}

void printTree(Node root){
    if(root != NULL){
        printTree(root->left);
        printf("%s : %d\n",root->word,root->n);
        printTree(root->right);
    }
}

int main(int argc, char const *argv[])
{
    char word[MAXWORD];
    Node root = NULL;
    while(getWord(word,MAXWORD)!= EOF){
        root = addNode(root,word);
    }
    printTree(root);
    system("pause");
    return 0;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define HASHSIZE 101
typedef struct list* List;

struct list{
    struct list* next;
    char* name;
    char *defn;
};

unsigned int hash(char *s){
    unsigned hashval;
    for(hashval =0;*s != '\0';s++){
        hashval = *s + 31 * hashval;
    }
    return hashval % HASHSIZE;
}

List lookup(List *hashtable,char *name){
    List ret = NULL;
    for(ret = hashtable[hash(name)];ret != NULL && strcmp(ret->name,name)!=0;
        ret = ret->next)
        ;
    return ret;
}

List insert(List *hashtable,char *name,char *defn){
    List temp = NULL;
    if( (temp = lookup(hashtable,name) )== NULL){/* 未找到 */
        /* 在前端插入 */
        temp = (List)malloc(sizeof(struct list));
        temp->name = (char *)malloc( (strlen(name)+1) * sizeof(char));
        strcpy(temp->name,name);
        hashtable[hash(name)] = temp;
    }else{
        free(temp->defn);
    }
    /* 无论找到与否，都需要更新defn */
    temp->defn = (char *)malloc( (strlen(defn)+1) * sizeof(char));
    strcpy(temp->defn,defn);
    return temp;
}

void printList(List list){
    if(list != NULL){
        printf("%s %s\n",list->name,list->defn);
    }else{
        printf("NULL\n");
    }
}

int main(int argc, char const *argv[])
{
    List hashtable[HASHSIZE];
    int i;
    for(i=0;i<HASHSIZE;i++){
        hashtable[i] = NULL;
    }
    insert(hashtable,"hello","wolrld");
    insert(hashtable,"hash","1");
    insert(hashtable,"is","are");
    printList(lookup(hashtable,"hello"));
    printList(lookup(hashtable,"name"));
    system("pause");
    return 0;
}

typedef

C语言提供了一种称为typedef的功能，它用来建立新的数据类型名，例如，声明

typedef int length;

将length定义为与int具有同等意义的名字。typedef很好理解，只需要主要它用来定义函数指正的情况就行了。如：

typedef int(*func)(int a,int b);

这个是将func定义为一个指向返回值为int，参数为两个int类型的函数。

联合

联合union是可以在不同时刻保存不同类型和长度的对象的变量，编译器负责跟踪这些对象的长度和对齐要求。实际上，联合就是一个结构，它的所有成员相对于基地址的偏移量都为0，此结构空间要大到足够容纳最宽的成员，并且，其对齐方式要适合于联合中所有类型的成员。

位字段

C语言提供了一种可以直接定义和访问一个字中的字段的能力，而不需要通过按位逻辑运算符。位字段，或简称字段，是”字“中相邻的集合。”字“是单个的存储单元，它同具体的实现有关。下面是一个例子。

#include<stdio.h>
#include<stdlib.h>
struct bits{
    unsigned int is_keyword : 1;
    unsigned int is_extern : 1;
    unsigned int is_static : 1;
};

int main(int argc, char const *argv[])
{
    struct bits bit;
    bit.is_keyword = 1;
    bit.is_extern = 1;
    /* 输出4 1 0 */
    printf(" %d %d %d\n",sizeof(bit),bit.is_keyword,bit.is_static);
    system("pause");
    return 0;
}

由于现在的内存价格的下降，这个使用得很少。