首页 代码 编程语言

# 结构的基本知识

结构是一个或者多个变量的几何，这些变量可能为不同的类型，为了处理的方便而将这些变量组织在一个名字之下。
结构可以拷贝、赋值、传递给函数，函数也可以返回结构类型的返回值，在 ANSI 标准中，自动结构和数组现在也可以进行初始化。

我们首先来看一个关于平面坐标的结构体

1
2
3
struct point {
    int x , y ; 
} ;

关键字 struct 引入结构声明。结构声明由包含在花括号内的一系列声明组成。关键字 struct 后面的名字是可选的，称为结构标记（这里是 point）。
结构标记用于为结构命名，在定义之后，结构标记就代表花括号内的声明，可以用它作为该声明的简写形式。
结构中定义的变量称为成员。结构成员，结构标记和普通变量（即非成员）可以采用相同的名字，它们之间不会冲突，因为通过上下文分析总可以对它们进行区分。不同结构中的成员也可以使用相同的名字。
struct 声明定义了一种数据类型，在标志结构成员表结束的右花括号之后可以跟一个变量表，这与其它基本类型的变量声明是相同的。例如：

1
struct { ... } x , y , z ;

从语法角度来说，这种声明与声明

1
int x , y , z ;

具有类似的意义。如果结构声明的后面不带变量表，则不需要为它分配存储空间，它仅仅描述了一个结构的模版。但是，如果结构声明中带有标记，那么在以后定义结构实例时便可以使用该标记定义。例如：

1
struct point maxpt = { 320 , 200 } ;

定义了一个 struct point 类型的变量 pt。结构的初始化可以在定义的后面使用初值表进行，除指标中同每个成员对应的处置必须是常量表达式。
自动结构也可以通过赋值初始化，还可以通过调用返回相应类型结构中的成员。
在表达式中可以通过下列形式引用某哥特定结构中的成员：
结构名。成员
结构可以嵌套，例如

1
2
3
4
5
struct rect { 
    struct point pt1 ; 
    struct point pt2 ; 
} ;
struct rec screen ;

我们可以使用语句

1
screen.pt1.x ;

# 结构与函数

结构的合法操作只有：

  1. 作为一个整体赋值
  2. 通过 & 运算符取地址，访问其成员。

其中复制和复制包括向函数传递参数以及从函数返回值。结构之间不可以进行比较。
可以用一个常量成员值列表初始化结构，自动结构也可以通过赋值进行初始化。
我们可以通过至少 3 种方法传递结构：

  1. 分别传递各个结构成员
  2. 传递整个结构
  3. 传递指向结构的指针

例如以下函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct point makepoint ( int x , int y ) {
    struct point temp ; 
    temp.x = x ; temp.y = y ; 
    return temp ; 
}

struct rect screen ; 
struct point middle ; 
struct point makepoint ( int , int ) ; 
screen.pt1 = makepoint ( 0 , 0 ) ; 
screen.pt2 = makepoint ( XMAX , YMAX ) ; 
middle = makepoint ( ( screen.pt1.x + screen.pt2.x ) >> 1 , ( screen.pt1.y + screen.pt2.y ) >> 1 ) ; 

struct point addpoint ( struct point p1 , struct point p2 ) { 
    p1.x += p2.x ; 
    p1.y += p2.y ; 
    return p1 ; 
}

addpoint 函数的参数和返回值都是结构类型，结构类型的参数和其它参数是一样的都是通过值传递的。

如果传递给函数的结构很大，使用指针方式的效率通常比赋值整个结构的效率更高，结构指针类似于普通变量指针。声明：

1
struct point * pp ;

如果 pp 指向一个 point 结构，那么 * pp 即为该结构，而（ * pp ).x 和 (* pp).y 则是结构成员。其中 ( * pp ).x 的圆括号是必须的，因为结构成员运算符 "." 的优先级比 "*" 的优先级高。表达式 * pp.x 的含义等价于 *(pp.x)，因为 x 不是指针，所以该表达式是非法的。
结构指针的使用频率非常高，为了使用方便，C 语言提供了另一种简写方式。嘉定 p 是一个指向结构的指针，可以用
p-> 结构成员
这种形式来引用相应的结构成员。
运算符。和 -> 都是从左至右结合的，所以以下声明都是等价的：

1
2
3
4
5
6
struct rec r , * rp = & r ; 

r.pt1.x 
rp->pt1.x 
(r.pt1).x 
(rp->pt1).x

在所有运算符中，下面 4 个运算符的优先级最高：结构运算符 “.” 和 “->”、用于函数
调用的 “()” 以及用于下标的 “[]”，因此，它们同操作数之间的结合也最紧密。例如，对于
结构声明

1
2
3
4
struct { 
    int len; 
    char *str; 
} *p ;

表达式

1
++p->len

将增加 len 的值，而不是增加 p 的值，这是田为，其中的隐含括号关系是 ++(p->len)。可 以使用括号改变结合次序。例如：(p)->len 将先执行 p 的加 1 操作，再对 len 执行操作； 而 (p)->len 则先对 len 执行操作，然后再将 p 加 1（该表达式中的括号可以省略）。 同样的道理，*p->str 读取的是指针 str 所指向的对象的值；*p->str 先读取指针 str 指向的对象的值，然后再将 str 加 1（与 * s 相同）；(*p->str）将指针 str 指向 的对象的值加 1；*p->str 先读取指针 str 指向的对象的值，然后再将 p 加 1。

# 结构数组

考虑编写一个程序，用来统计输入中各个 C 语言关键字出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct key {
    char *word;
    int count;
} keytab[] = {
    "auto", 0,
    "break", 0,
    "case", 0,
    "char", 0,
    "const", 0,
    "continue", 0,
    "default", 0,
    /* ... */
    "unsigned", 0,
    "void", 0,
    "volatile", 0,
    "while", 0
};

与结构成员相对应，初值也要按照成对的方式列出。更精确的做法是，将每一行（即每个结
构）的初值都括在花括号内，如下所示：

1
2
3
4
{ "auto", 0 }, 
{ "break", 0 }, 
{ "case", 0 }, 
...

但是，如果初值是简单变量或字符串，并且其中的任何值都不为空，则内层的花括号可以省 略。通常情况下，如果初值存在并且方括号 [ ] 中没有数值，编译程序将计算数组 keytab 中 的项数。
在统计关键字出现次数的程序中，我们首先定义了 keytab。主程序反复调用函数 getword 读取输入，每次读取一个单词。每个单词将通过折半查找函数在 keytab 中进行查找。注意，关键字列表必须按升序存储在 keytab 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
int binsearch(char *, struct key *, int);
/* count C keywords */
int main()
{
    int n;
    char word[MAXWORD];
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
              if ((n = binsearch(word, keytab, NKEYS)) >= 0)
                    keytab[n].count++;
    for (n = 0; n < NKEYS; n++)
        if (keytab[n].count > 0)
            printf("%4d %s\n",
                keytab[n].count, keytab[n].word);
    return 0;
}
/* binsearch: find word in tab[0]...tab[n-1] */
int binsearch(char *word, struct key tab[], int n)
{
    int cond;
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low+high) / 2;
        if ((cond = strcmp(word, tab[mid].word)) < 0)
            high = mid - 1;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}
int getword ( char * word , int lim ) {
    int c , getch ( void ) ; 
    void ungetch ( int ) ; 
    char * w = word ; 
    while ( isspace ( c = getch ( ) ) ) ; 
    if ( c != EOF ) * w ++ ; 
    if ( ! isalpha ( c ) ) { * w = '\0' ; return c ; } 
    for ( ; -- lim > 0 ; w ++ ) 
        if ( ! isnum ( * w = getch ( ) ) ) {
            ungetch ( * w ) ; break ; 
        }
    * w = '\0' ; 
    return word[0] ; 
}
/*我们可以通过如下方法计算NKEYS的值*/
#define NKEYS ( sizeof keytab / sizeof ( struct key ) ) 
#define NKEYS ( sizeof keytab / sizeof keytab[0] )

getchar 函数的返回值也是 int 类型的

# 指向结构的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h> 
#include <ctype.h> 
#include <string.h> 
#define MAXWORD 100 
int getword(char *, int); 
struct key *binsearch(char *, struct key *, int); 
/* count C keywords; pointer version */ 
int main() 
{ 
    char word[MAXWORD]; 
    struct key *p; 
    while (getword(word, MAXWORD) != EOF) 
        if (isalpha(word[0])) 
            if ((p=binsearch(word, keytab, NKEYS)) != NULL) 
                p->count++; 
    for (p = keytab; p < keytab + NKEYS; p++) 
        if (p->count > 0) 
            printf("%4d %s\n", p->count, p->word); 
    return 0; 
} 
/* binsearch: find word in tab[0]...tab[n-1] */ 
struct key *binsearch(char *word, struck key *tab, int n) 
{ 
    int cond; 
    struct key *low = &tab[0]; 
    struct key *high = &tab[n]; 
    struct key *mid; 
    while (low < high) { 
        mid = low + (high-low) / 2; 
        if ((cond = strcmp(word, mid->word)) < 0) 
            high = mid; 
        else if (cond > 0) 
            low = mid + 1; 
        else 
            return mid; 
    } 
    return NULL; 
}

这一个部分比较简单，就不细写了，上面的程序等于是改写了一下。搜索函数里面的 while 循环是为了防止死循环写的，当 high==low 的时候，如果没有 low<high 这个条件会一直死循环下去。
特别需要注意的是千万不要认为结构的长度等于各成员长度的和。因为不同的对象有不同的对齐要 求，所以，结构中可能会出现未命名的 “空穴 “（hole）。例如，假设 char 类型占用一个字节，int 类型占用 4 个字节，则下列结构：

1
2
3
4
struct { 
    char c; 
    int i; 
};

可能需要 8 个字节的存储空间，而不是 5 个字节。使用 sizeof 运算符可以返回正确的对象
长度。

# 自引用结构

假定我们需要处理一个更一般化的问题：统计输入中所有单词的出现次数。因为预先不 知道出现的单词列表，所以无法方便地排序，并使用折半查找；也不能分别对输入中的每个单词都执行一次线性查找，看它在前面是否已经出现，这样做，程序的执行将花费太长的时 间。（更准确地说，程序的执行时间是与输入单词数目的二次方成比例的。）我们该如何组织这些数据，才能够有效地处理一系列任意的单词呢？
一种解决方法是，在读取输入中任意单词的同时，就将它放置到正确的位置，从而始终 保证所有单词是按顺序排列的。虽然这可以不用通过在线性数组中移动单词来实现，但它仍 然会导致程序执行的时间过长。我们可以使用一种称为二叉树的数据结构来取而代之。 每个不同的单词在树中都是一个节点，每个节点包含：

  1. 一个指向该单词内容的指针
  2. 一个统计出现次数的计数值・一个指向左子树的指针
  3. 一个指向右子树的指针
    任何节点最多拥有两个子树，也可能只有一个子树或一个都没有。 对节点的所有操作要保证，任何节点的左子树只包含按字典序小于该节点中单词的那些单词，右子树只包含按字典序大于该节点中单词的那些单词。要查找一个新单词是否已经在树中，可以从根节点开始，比较新单词与该节点中的单词。若 匹配，则得到肯定的答案。若新单词小于该节点中的单词，则在左子树中继续查找，否则在 右子树中查找。如在搜寻方向上无子树，则说明新单词不在树中，并且，当前的空位置就是 存放新加入单词的正确位置。因为从任意节点出发的查找都要按照同样的方式查找它的一个子树，所以该过程是递归的。相应地，在插入和打印操作中使用递归过程也是很自然的事情。
    对节点的递归的：
更新于 阅读次数 次