基本结构c语言,C语言语法结构
C语言系列：6、结构文章目录C语言系列：6、结构1、结构基础知识2、结构与函数3、结构数组4、结构指针5、自引用结构6、表查找7、类型定义8、并集9、位域
结构是一个或多个变量的集合，这些变量可以是不同的类型。为了便于处理，这些变量被组织在一个名称下。(有些语言把结构称为“记录”，比如Pascal。因为该结构将一组相关变量视为一个单元而不是独立的实体，所以它有助于组织复杂的数据，尤其是在大型程序中。
薪金记录是用来描述该结构的传统示例。每个雇员由一组属性描述，如姓名、地址、社会保险号、工资等。它的一些属性也可以是结构化的，比如名字可以分成几个部分，地址甚至工资可能都差不多。C语言中比较典型的例子来自图形领域：一个点由一对坐标定义，一个矩形由两个点定义，等等。
ANSI标准在结构上的主要变化是定义了结构的赋值操作。——结构可以复制、赋值、传递给函数，函数也可以返回结构类型的返回值。这个操作已经被大多数编译器支持了很多年，但是直到这个标准才精确地定义了它的属性。在ANSI标准中，自动结构和数组现在也可以初始化。
1.结构基础知识。首先，我们先建立一些适合图形领域的结构。点是最基本的对象，假设用X和Y坐标表示，X和Y的坐标值是整数(见图6-1)。
我们可以用结构来存储这两个坐标，其语句如下：
结构点{
int x；
int y；
};关键字struct引入了结构声明。声明由一系列用花括号括起来的声明组成。关键字struct后面的名字是可选的，叫做结构标签(这里是点)。结构标签用于命名结构。定义后，structure标记用花括号表示语句，花括号可以用作语句的缩写形式。
结构中定义的变量称为成员。成员、结构标记和公共变量(即非成员)可以使用相同的名称，它们不会相互冲突，因为它们总是可以通过上下文分析来区分。此外，不同结构中的成员可以使用相同的名称，但就编程风格而言，通常只有密切相关的对象才会使用相同的名称。
结构声明定义了一种数据类型。标记结构成员表结束的右花括号后面可以跟一个变量表，这和其他基本类型的变量声明是一样的。例如：
结构{.} x，y，z；从语法的角度来看，这种申报和申报的方式
int x，y，z；有类似的意思。两个声明都将X、Y和Z声明为指定类型的变量，并为它们分配存储空间。
如果结构声明后面没有变量表，就不需要为它分配存储空间。它只描述模板或结构的轮廓。但是，如果在结构声明中有一个标记，它可以在以后用于定义结构实例。例如，对于上面给出的结构声明点，语句
结构点pt；定义了结构点类型的变量pt。结构的初始化可以在定义之后通过使用初始值表来完成。初始值表中每个成员对应的初始值必须是常量表达式，例如：
结构点maxpt={320，200 }；自动结构也可以通过赋值或者调用返回相应结构类型的函数来初始化。
在表达式中，可以用下列形式引用特定结构中的成员：
姓名。成员
其中结构成员运算符“.”将结构名称与成员名称连接起来。例如，点pt的坐标可以用下面的语句打印出来：
printf(%d，%d ，pt.x，pt . y)；或者通过以下代码计算从原点(0，0)到点pt的距离：
double dist，sqrt(double)；
dist=sqrt((double)pt . x * pt . x(double)pt . y * pt . y)；结构可以嵌套。我们可以用对角线上的两点定义一个矩形(见图6-2)，对应的结构定义如下：
结构矩形{
结构点pt1
结构点pt2
};rect结构包含两个point类型的成员。如果您按如下方式声明屏幕变量：
结构矩形屏幕；您可以使用语句
Screen.pt1.x是指Screen的成员pt1的x坐标。
2.结构和函数* *结构的合法操作只有几个：整体复制赋值，通过运算符获取地址，访问其成员。* *其中，复制和赋值包括向函数传递参数和从函数返回值。结构不能比较。您可以用一列常量成员值来初始化该结构，也可以通过赋值来初始化自动结构。
为了进一步理解该结构，我们编写了几个对点和矩形进行操作的函数。传递结构至少有三种可能的方法：一种是分别传递每个结构成员，一种是传递整个结构，第三种是传递指向结构的指针。这三种方法各有利弊。
让我们先来看看函数makepoint，它接受两个整数参数并返回一个point类型的结构：
/* makepoint:从x和y分量创建一个点*/
结构点makepoint(int x，int y)
{
结构点温度；
temp.x=x
温度=y
返回温度；
}注意，同名的参数名和结构成员不会引起冲突。事实上，重名的使用可以强调两者之间的关系。
现在您可以使用makepoint函数动态初始化任何结构，或者您可以向函数提供结构类型的参数。例如：
结构矩形屏幕；
结构点中间；
struct point makepoint(int，int)；
screen.pt1=makepoint(0，0)；
screen.pt2=makepoint(XMAX，YMAX)；
middle=make point((screen . pt1 . x screen . pt2 . x)/2，
(screen . pt1 . y screen . pt2 . y)/2)；接下来，您需要编写一系列函数来对点执行算术运算。例如：
/* addpoints:添加两个点*/
结构添加点(结构点p1，结构点p2)
{
P1 . x=p2 . x；
P1 . y=p2 . y；
返回P1；
}其中函数的参数和返回值都是结构类型。之所以把加法的结果直接赋给p1，而不使用显式的临时变量存储，是为了强调结构类型的参数和其他类型的参数一样是按值传递的。
让我们看另一个例子。prinrect函数确定一个点是否在给定的矩形内。我们采用的惯例是，矩形包括它的左边缘和下边缘，但不包括它的上边缘和右边缘。
/* ptinrect:如果p在r中，则返回1，否则返回0 */
int ptinrect(结构点p，结构点r)
{
返回p.x=r.pt1.x p.x r.pt2.x
p . y=r . pt 1 . y p . y r . pt 2 . y；
这里，假设矩形以标准形式表示，其中pt1的坐标小于pt2的坐标。以下函数将以规范形式返回一个矩形：
#定义min(a，b) ((a) (b)？(a) : (b))
#定义max(a，b) ((a) (b)？(a) : (b))
/* canonrect:规范化矩形的坐标*/
结构矩形能纠正
{
结构矩形温度；
temp.pt1.x=min(r.pt1.x，r . pt2 . x)；
temp.pt1.y=min(r.pt1.y，r . pt2 . y)；
temp.pt2.x=max(r.pt1.x，r . pt2 . x)；
temp.pt2.y=max(r.pt1.y，r . pt2 . y)；
返回温度；
}如果传递给函数的结构很大，使用指针通常比复制整个结构更高效。指针类似于普通的变量指针。声明
结构点* pp将pp定义为指向struct point类型对象的指针。如果pp指向一个点结构，那么
姚*pp是结构，而(*pp)。x和(*pp)。y是该结构的成员。Pp可用于以下示例：
结构点原点，* pp
pp=原点；
printf(原点是(%d，%d)\n ，(*pp)。x，(*pp)。y)；其中(*pp)中的括号。x是必要的，因为结构成员运算符“.”的优先级是高于*”的。表达式*pp.x等价于*(pp.x)，因为x不是指针，所以这个表达式是非法的。
使用结构指针的频率非常高。为了方便起见，C语言提供了另一种速记方法。假设p是指向一个结构的指针，那么对应的结构成员可以以p- structure成员的形式被引用。这样，上面的代码行可以重写为以下形式：
printf(原点是(%d，%d)\n ，pp- x，PP-y)；操作员。和-从左到右组合，因此，对于下面的语句：
struct rect r，* RP=r；以下4个表达式是等价的：
r.pt1.x
rp- pt1.x
(r.pt1)。x
(rp- pt1)。x在所有运算符中，以下四个运算符的优先级最高：结构运算符“.”和“-”，用于函数。
调用的“()”和下标使用的“[]”，因此，它们与操作数结合得最紧密。例如，对于结构声明
结构{
int len
char * str
} * p；表示
P- len会增加len而不是p的值，就是田维，这里隐含的括号是(p- len)。您可以使用括号来更改组合顺序。比如：(p)- len会先给p加1，然后对len进行运算；While (p )- len先对len进行运算，然后在p上加1(该表达式中的括号可以省略)。
同理，*p- str读取指针str指向的对象的值；*p- str首先读取指针
str指向的对象的值，然后str加1(同* s)；(*p- str)指针str指向的对象的值加1；* p str先读取指针str指向的对象的值，然后将p加1。
3.结构数组考虑写这样一个程序，用来统计每个C语言关键字在输入中出现的次数。我们需要使用一个字符串数组来存储关键字名称，使用一个整数数组来存储相应关键字的出现次数。实现这一点的一种方法是使用两个独立的数组keyword和keycount来分别存储它们，如下所示
char * keyword[NKEYS]；
int key count[NKEYS]；我们注意到两个数组大小相同。考虑到这个特点，我们可以采用另一种不同的组织方式，也就是我们这里所说的结构化数组。每个关键字项包括一对变量：
char * word
int cout这样的多个变量对一起形成一个数组。让我们看看下面的陈述：
结构键{
char * word
int计数；
} keytab[NKEYS]；它声明一个结构类型键，定义它的结构数组keytab，并为它分配存储空间。array keytab的每个元素都是一个结构。上述语句也可以写成以下形式：
结构键{
char * word
int计数；
};
struct key keytab[NKEYS]；因为结构keytab包含一组固定的名称，所以最好将其声明为外部变量，这样它只需要初始化一次，就可以在任何地方使用。该结构的初始化方法类似于上面提到的初始化方法。3354由定义后括号中的初始值表初始化，如下所示：
结构键{
char * word
int计数；
} keytab[]={
自动，0，
中断，0，
案例，0，
字符，0，
常数，0，
继续，0，
默认，0，
/* .*/
未签名，0，
void ，0，
易变，0，
while ，0
};对应于结构成员，初始值也要成对列出。更准确地说，用花括号将每行(即每个结构)的初始值括起来，如下所示：
{ 自动，0 }，
{ break ，0 }，
{ 案例，0 }，
.但是，如果初始值是一个简单的变量或者字符串，并且它的值都不是空的，那么内层的花括号可以省略。通常情况下，如果初始值存在，并且方括号[]中没有值，编译器将计算数组keytab中的项数。
在计算关键字出现次数的程序中，我们首先定义了keytab。主程序反复调用函数。
Getword读取输入，一次一个单词。半搜索功能将在keytab中搜索每个单词(参见第3章)。注意，关键字列表必须以升序存储在keytab中。
#包含stdio.h
#包含ctype.h
#包含字符串. h
#定义MAXWORD 100
int getword(char *，int)；
int binsearch(char *，struct key *，int)；
/* count C关键字*/
主()
{
int n；
char word[max word]；
while (getword(word，MAXWORD)！=EOF)
if (isalpha(word[0]))
if ((n=binsearch(word，keytab，NKEYS))=0)
keytab[n]。数数；
for(n=0；n NKEYSn)
if (keytab[n].计数0)
printf(M %s\n ，
keytab[n]。计数，keytab[n]。word)；
返回0；
}
/* binsearch:在选项卡[0]中查找单词.tab[n-1] */
int binsearch(char *word，struct key tab[]，int n)
{
int cond
int低、高、中；
低=0；
高=n-1；
while(低=高){
mid=(低高)/2；
if ((cond=strcmp(word，tab[mid])。word)) 0)
高=中-1；
否则如果(条件0)
低=中1；
其他
返回mid
}
return-1；
}后面会介绍getword这个函数。这里只需要知道它的作用是，每次调用函数，都会读入一个字，复制到作为函数第一个参数命名的数组中。
NKEYS表示keytab中关键字的数量。虽然可以手工计算，但是用机器实现会更简单更安全，尤其是在列表可能发生变化的情况下。一种解决方案是在初始值表的末尾添加一个空指针，然后遍历keytab，直到读到末尾的空指针。
其实没必要这么做，因为数组的长度在编译时就已经完全确定了，它等于数组项的长度乘以项数。因此，可以得出这样的结论，物品的数量是：
Keytab的长度structkey的长度
c语言提供了一个编译时一元运算符sizeof，可以用来计算任何对象的长度。表示
Sizeof对象
和
Sizeof(类型名)
返回一个整数值，该值等于指定对象或类型占用的存储空间的字节数。(严格来说sizeof的返回值是一个无符号整数值，类型是size_t，在头文件stddef.h中定义)其中对象可以是变量、数组或者结构；类型可以是基本类型，如int和double，也可以是派生类型，如结构类型或指针类型。
在这个例子中，关键字的数量等于数组的长度除以单个元素的长度。以下#define语句使用此方法设置NKEYS的值：
# define keys(sizeoffkeytab/sizeof(struct key))另一种方法是将数组的长度除以指定元素的长度，如下所示：
# define keys(sizeof keytab/sizeof(keytab[0]))使用第二种方法。即使改变了类型，也不需要改变程序。
Sizeof不能用在条件语句#if中，因为预处理器不分析类型名。但是，预处理器不会计算#define语句中的表达式，因此在#define中使用sizeof是合法的。
我们来讨论一下getword这个函数。这里我们给出一个更一般的getword函数。这个函数的功能已经超出了这个示例程序的要求，但是函数本身并不复杂。Getword从输入中读取下一个单词，这个单词可以是以字母或非空白字符开头的字母和数字的字符串。该函数的返回值可能是单词的第一个字符、文件e of的结尾或字符本身(如果字符不是字母字符)。
/* getword:从输入中获取下一个单词或字符*/
int getword(char *word，int lim)
{
int c，getch(void)；
void un getch(int)；
char * w=word
while (isspace(c=getch()))
；
如果(c！=EOF)
* w=c；
如果(！isalpha(c)) {
* w= \ 0
返回c；
}
for(；-lim 0；w)
如果(！isalnum(* w=getch()){
un getch(* w)；
打破；
}
* w= \ 0
返回单词[0]；
}getword函数使用第4章中的函数getch和ungetch。当读取的字符不属于字母号时
单词集合表示getword又读入了一个字符。然后，调用ungetch将一个额外的字符放回下一次调用的输入中。Getword还使用了一些其他的函数：isspace函数跳过空格，isalpha函数识别字母，isalnum函数识别字母和数字。所有这些函数都在标准头文件ctype.h中定义
4.结构指针为了进一步说明结构指针和结构数组，我们重新编写了关键字统计程序，这次用指针代替数组下标。
keytab的外部声明不需要修改，但是main和binsearch函数必须修改。修订计划
如下所示：
#包含stdio.h
#包含ctype.h
#包含字符串. h
#定义MAXWORD 100
int getword(char *，int)；
struct key *binsearch(char *，struct key *，int)；
/* count C个关键字；指针版本*/
主()
{
char word[max word]；
结构键* p；
while (getword(word，MAXWORD)！=EOF)
if (isalpha(word[0]))
if ((p=binsearch(word，keytab，NKEYS))！=空)
p计数；
for(p=keytab；p keytab NKEYSp)
如果(p计数为0)
printf(M %s\n ，p- count，p-word)；
返回0；
}
/* binsearch:在选项卡[0]中查找单词.tab[n-1] */
struct key *binsearch(char *word，striked key * tab，int n)
{
int cond
struct key * low=tab[0]；
struct key * high=tab[n]；
结构键* mid
当(低高){
mid=低(高-低)/2；
if ((cond=strcmp(word，mid- word)) 0)
高=中；
否则如果(条件0)
低=中1；
其他
返回mid
}
返回NULL
}这里有几点需要注意。首先，binsearch函数必须在声明中指明其返回的值类型是指向struct key类型的指针，而不是整数类型，这一点在函数原型和binsearch函数中都要声明。如果Binsearch找到与输入单词匹配的数组元素，它将返回指向该元素的指针，否则将返回NULL。
其次，这里通过指针访问keytab的元素。这需要对binsearch进行重大修改。
这里，low和high的初始值分别是指向header元素的指针和指向footer元素之后的元素的指针。
这样，我们就不能简单地用下面的表达式来计算中间元素的位置了：
Mid=(低高)/2 /*错*/这是因为两个指针之间的加法是非法的。但是指针的减法是合法的，高低值就是数组元素的个数。因此，可以使用下面的表达式：
Mid=low(高-低)/2将Mid设置为指向高和低之间的中间元素的指针。
对算法最重要的修改是确保不会生成非法指针，或者不会访问数组范围之外的元素。问题是tab[-1]和tab[n]都超出了数组tab的范围。前者是绝对违法的，而间接引用后者也是违法的。但是C语言的定义保证了数组结束后第一个元素(tab[n])的指针算术运算可以正确执行。
主程序main有以下语句：
for(p=keytab；p keytab NKEYSp)如果p是结构的指针，p的算术运算需要考虑结构的长度。所以在执行表达式p的时候，会在p的基础上加上一个正确的值，保证得到结构数组的下一个元素。这样，上述测试条件可以确保循环的正确终止。但是，千万不要认为结构的长度等于所有构件长度之和。由于不同的对象有不同的对齐要求，结构中可能会出现未命名的孔。例如，假设char类型占用一个字节，int类型占用四个字节，那么下面的结构：
结构{
char c；
int I；
};它可能需要8字节的存储空间，而不是5字节。使用sizeof运算符返回正确的对象长度。
最后说明一下程序的格式：当函数的返回值类型比较复杂时(比如结构指针)，比如
Structkey * Binsearch (char * word，structkey * tab，int n)很难看到函数名，使用文本编辑器也不容易找到。我们可以用另一种格式来写上面的语句：
结构键*
Binsearch (char * word，struct key * tab，int n)是个人习惯问题。可以选择自己喜欢的方式，永远保持自己的风格。
5.自引用结构假设我们需要处理一个更普遍的问题：统计输入中所有单词的出现次数。因为不知道提前出现的单词列表，所以不能方便的排序，使用对折搜索；也不可能对输入中的每个单词单独进行线性搜索，看它是否已经出现在前面。这样做，程序的执行时间会太长。(更准确地说，程序的执行时间与输入字数的二次方成正比。)我们如何组织这些数据来有效处理一系列任意的单词？
一种解决方案是读取输入中的任何单词，并将其放在正确的位置，以便始终确保所有单词都是有序的。虽然这可以在不移动线性数组中的字的情况下实现，但仍然会导致程序执行时间过长。我们可以用一种叫做二叉树的数据结构来代替。
每个不同的单词是树中的一个节点，每个节点包含：
指向单词内容的指针。
用于计数出现次数的计数值
指向左侧子树的指针
指向右边子树的指针。
任何节点最多有两个子树，或者它可能只有一个子树或者根本没有。
在一个节点上的所有操作应该确保任何节点的左子树只包含那些在字典顺序上小于该节点中的单词的单词，而右子树只包含那些在字典顺序上大于该节点中的单词的单词。图6-3是把句子“现在是所有好人来帮助他们的党的时候了”中的词按顺序插入而生成的树。
要找出一个新单词是否已经在树中，可以从根节点开始，将新单词与该节点中的单词进行比较。如果匹配，答案是肯定的。如果新词小于节点中的词，则继续在左子树中搜索，否则在右子树中搜索。如果搜索方向没有子树，则新单词不在树中，当前空位置是存储新添加单词的正确位置。因为从任何节点开始的搜索都必须以同样的方式搜索它的子树，所以这个过程是递归的。因此，在插入和打印操作中使用递归过程是很自然的。
我们来看看对节点的描述。最方便的表达方式是将其表达为具有4个成员的结构：
结构节点{ /*树节点：*/
char * word/*指向文本*/
int计数；/*出现次数*/
struct tnode * left/*左孩子*/
struct tnode * right/*右孩子*/
};这种节点的递归声明看似不确定，但却是正确的。包含自身实例的结构是非法的，但下列语句是合法的：
struct tnode * left它将left声明为指向tnode的指针，而不是tnode实例本身。
偶尔，我们也会使用自指结构的一种变体：两个结构相互指。具体使用方法如下：
结构t {
.
结构s * p；/* p指向s */
};
结构
.
结构t * q；/* q指向一个t */
};如下图，整个程序的代码很短。当然，它需要我们之前写的一些程序的支持，比如getword等。main函数通过getword读入单词，通过addtree函数插入树中。
#包含stdio.h
#包含ctype.h
#包含字符串. h
#定义MAXWORD 100
struct tnode * add tree(struct tnode *，char *)；
void tree print(struct tnode *)；
int getword(char *，int)；
/*词频计数*/
主()
{
struct tnode * root
char word[max word]；
root=NULL
while (getword(word，MAXWORD)！=EOF)
if (isalpha(word[0]))
root=addtree(root，word)；
treeprint(根)；
返回0；
}函数addtree是递归的。由主函数main作为参数传递给该函数的单词将作为树的顶层(即树的根)。在每一步中，新单词与存储在节点中的单词进行比较，然后，通过递归调用addtree转向左子树或右子树。该单词最终将匹配树中的一个节点(在这种情况下，计数值增加1)，或者它将遇到一个空指针(指示必须创建一个节点并将其添加到树中)。如果生成了一个新节点，addtree将返回一个指向新节点的指针，该指针保存在父节点中。
struct tnode * talloc(void)；
char * strdup(char *)；
/* addtree:在p处或p之下添加一个带有w的节点*/
struct treenode * add tree(struct tnode * p，char *w)
{
int cond
if (p==NULL) { /*新单词已经到达*/
p=talloc()；/*创建新节点*/
p-word=strdup(w)；
p-count=1；
p左=p右=空；
} else if ((cond=strcmp(w，p- word))==0)
p计数；/*重复的单词*/
else if (cond 0) /*小于进入左子树*/
p- left=addtree(p- left，w)；
else /*大于右子树*/
p- right=addtree(p- right，w)；
返回p；
}新节点的存储空间由子程序talloc获得。Talloc函数返回一个可以保存
节点的可用空间。strdup函数将新单词复制到一个隐藏的位置(这些子例程将在后面讨论)。计数值将被初始化，并且两个子树将被设置为空。添加新节点时，这部分代码只在叶子部分执行。程序忽略了strdup和talloc返回值的错误检查(这显然是不完美的)。
treeprint函数按顺序打印树。在每个节点，它打印左子树(所有比单词小的单词)，然后是单词本身，最后是右子树(所有比单词大的单词)。如果你对递归操作有些疑惑，不妨模拟一下上面树上的treeprint的执行过程。
/* treeprint:树p的有序打印*/
void treeprint(struct tnode *p)
{
如果(p！=NULL) {
treeprint(左侧)；
printf(M %s\n ，p- count，p-word)；
treeprint(右侧)；
}
}这里有一点值得注意：如果单词没有随机到达，树就会变得不平衡。在这种情况下，程序的运行时间会大大增加。在最坏的情况下，如果单词已经按顺序排列，程序模拟线性搜索的代价会非常大。有些广义二叉树不受这种最坏情况的影响，这里不讨论。
在结束这个例子之前，让我们简单讨论一下存储分配器的问题。虽然存储分配器需要为不同的对象分配存储空间，但显然，程序中只会有一个存储分配器。然而，假设使用一个分配器来处理多种类型的请求，比如指向char类型的指针和指向struct tnode类型的指针，就会出现两个问题。第一，它是如何满足大多数真实机器上各种类型对象的对齐要求的(比如整数类型通常要分配给偶数地址)，第二，用什么样的声明来处理分配器必须能够返回不同类型指针的问题？
一般来说，对齐要求很容易满足。只需要确保分配器总是返回满足所有对齐限制的指针，以牺牲一些存储空间为代价。第5章介绍的alloc函数不保证任何特定类型的对齐，所以我们使用标准库函数malloc，它可以满足对齐要求。第八章将介绍一种实现malloc函数的方法。
对于任何执行严格类型检查的语言，像malloc这样的函数的类型声明总是令人头疼。在C语言中，合适的方法是将malloc的返回值声明为指向void类型的指针，然后将指针显式地强制转换为所需的类型。Malloc和相关函数在标准头文件stdlib.h中声明.因此，talloc函数可以写成以下形式：
#包含stdlib.h
/* talloc:创建一个tnode */
struct tnode *talloc(void)
{
return(struct tnode *)malloc(sizeof(struct tnode))；
}strdup函数只是将通过其参数传入的字符串复制到一个安全的位置。这是通过调用
Malloc函数实现：
char *strdup(char *s) /*复制s */
{
char * p；
p=(char *)malloc(strlen(s)1)；/* 1表示“\ 0”*/
如果(p！=空)
strcpy(p，s)；
返回p；
}没有可用空间时，malloc函数返回NULL，strdup函数也会返回NULL。strdup函数的调用者负责错误处理。
通过调用malloc函数获得的存储空间，可以通过调用free函数释放出来重新使用。详情请参考。
参见第7章和第8章。
6.表查找为了深入讨论该结构的更多方面，让我们编写一个表查找包的核心代码。这段代码很典型，可以在宏处理器或编译器的符号表管理例程中找到。例如，考虑#define语句。当遇到类似
#defINe IN 1，您需要在表中存储名称和替换文本1。此后，当IN中的名称出现在某些语句中时，例如：
statet=IN你必须用1代替IN。
以下两个函数用于处理名称和替换文本。install(s，t)函数更改名称s和替换文本t
记录到表中，其中s和t只是字符串。lookup(s)函数在表中查找s，如果找到了，就返回指向它的指针；如果没有找到，则返回NULL。
该算法使用哈希查找方法——将输入名称转换为一个小的非负整数，然后该整数将用作指针数组的下标。数组的每个元素都指向一个链表的头，链表中的每个块都用哈希值来描述名称。如果没有名字被散列到这个值，数组元素的值为空(见图6-4)。
链表中的每个块都是一个结构，它包含一个指向名称的指针、一个指向替换文本的指针和一个指向链表的后续块的指针。如果指向链表后续块的指针为空，则表示链表结束。
struct nlist { /*表条目：*/
struct nlist * next/*链中的下一项*/
char * name/*定义的名称*/
char * defn/*替换文本*/
};的相应指针数组定义如下：
#定义哈希大小101
静态结构nlist * hashtab[HASHSIZE]；/*指针表*/hash函数hash在lookup和install函数中都有使用，由for循环计数。
Calculate，在每个循环中，它把上一个循环计算的结果值变换(即乘以31)后得到的新值加到字符串中当前字符的值(*s 31 * hashval)上，然后用数组长度对结果值取模，结果就是这个函数的返回值。这不是最好的哈希函数，但它很短，也很有效。
/* hash:字符串s的格式哈希值*/
无符号哈希(char *s)
{
未签名的hashval
for(hashval=0；*s！=\0;s)
hashval=* s 31 * hashval
return hashval % HASHSIZE
}由于哈希计算采用了无符号算术运算，保证了哈希值不为负。
散列过程生成开始下标，以在数组hashtab中执行查找。如果可以找到该字符串，它一定在起始下标所指向的链表块中。具体的查找过程是通过查找函数来实现的。如果查找函数发现该条目已经存在，它将返回指向该条目的指针，否则将返回NULL。
/* lookup:在hashtab中查找s */
结构nlist *查找(字符)
{
struct nlist * np
for(NP=hashtab[hash(s)]；np！=NULLnp=np- next)
if (strcmp(s，np- name)==0)
返回NP；/*找到*/
返回NULL/*未找到*/
}lookup函数中的for循环是遍历链表的标准方式，如下所示：
for(ptr=head；ptr！=NULLptr=ptr- next)
.安装函数借助查找函数确定要添加的名称是否已经存在。如果它已经存在，请使用新的
相反，定义；否则，创建一个新条目。如果没有足够的空间来创建新条目，install函数将返回NULL。
struct nlist *查找(char *)；
char * strdup(char *)；
/* install:将(name，defn)放入hashtab */
结构nlist *install(char *name，char *defn)
{
struct nlist * np
未签名的hashval
if ((np=lookup(name))==NULL) { /*未找到*/
NP=(struct nlist *)malloc(sizeof(* NP))；
if(NP==NULL (NP-name=strdup(name))==NULL)
返回NULL
hash val=hash(name)；
NP-next=hashtab[hashval]；
hashtab[hashval]=NP；
} else /*已经在那里*/
free((void *)NP-defn)；/*自由先前定义*/
if((NP-defn=strdup(defn))==NULL)
返回NULL
返回NP；
}7.类型定义C语言提供了一个名为typedef的函数，用于建立新的数据类型名称，例如声明。
typedef int长度；将Length定义为与int含义相同的名称。类型长度可用于类型声明、类型转换等。它与int类型完全相同，例如：
Length len，maxlen
长度*长度[]；同样，声明
typedef char * String将String定义为char *或字符指针的同义词。之后，可以在类型声明和类型转换中使用String，例如：
String p，lineptr[MAXLINES]，alloc(int)；
int strcmp(String，String)；
p=(String)malloc(100)；请注意，typedef中声明的类型出现在变量名的位置，而不是紧跟在关键字typedef之后。
之后。Typedef在语法上类似于存储类extern、static等。我们在这里使用大写字母作为
由typedef定义的类型名的第一个字母，用于显示差异。
下面是一个更复杂的例子：用typedef定义本章前面介绍的树节点。如下所示：
typedef struct tnode * Treeptr
typedef结构tnode { /*树节点：*/
char * word/*指向文本*/
int计数；/*出现次数*/
struct tnode * left/*左孩子*/
struct tnode * right/*右孩子*/
} Treenode上面的类型定义创建了两个新的类型关键字：Treenode(一个结构)和Treeptr(一个指向该结构的指针)。这样，函数talloc可以修改为：
Treeptr talloc(void)
{
return(tree ptr)malloc(sizeof(Treenode))；
}这里必须强调的是，从任何意义上来说，typedef声明并没有创建一个新的类型，它只是在一个已有的类型上增加了一个新的名字。Typedef声明也没有添加任何新的语义：这样声明的变量与普通声明中声明的变量具有完全相同的属性。实际上，typedef类似于#define语句，但是因为typedef是由编译器解释的，所以它的文本替换功能超出了预处理器的能力。例如：
typedef int (*PFI)(char *，char *)；该语句定义类型PFI是“指向一个函数的指针，该函数有两个char *类型的参数，返回值类型是int”。它可以在某些上下文中使用，例如，它可以在第5章的排序器中使用，如下所示：
PFI strcmp，num mcmp；除了简洁的表达，使用typedef还有另外两个重要的原因。首先，它可以将程序参数化，提高可移植性。如果typedef声明的数据类型与机器相关，那么当程序移植到其他机器上时，只需要改变typedef类型定义。常见的情况是，对于各种不同大小的整数值，使用typedef定义的类型名，然后可以为不同的主机选择一组合适的类型short、int、long。标准库中有一些例子，比如size_t和ptrdiff_t等。
Typedef的第二个功能是为程序提供更好的解释。——Treeptr类型显然比声明要好。
指向复杂结构的指针更容易理解。
8.Union Union是一个变量，可以保存不同类型和长度的对象(在不同的时间)。编译器负责跟踪对象的长度和对齐要求。它提供了一种在单个存储区域中管理不同类型数据的方法，而无需在程序中嵌入任何与机器相关的信息。它类似于Pascal语言中的变量记录。
我们来看一个例子(可以在编译器的符号表管理器中找到)。假设一个常量可以是int，f1oat或者一个字符指针。特定类型的常数值必须存储在适当类型的变量中。但是，如果不同类型的常量占用相同的存储空间，并且存储在同一个地方，那么表管理将是最方便的。
这就是联合的目的。——一个变量可以合法地保存任何一种数据类型的对象。其语法基于结构，如下所示：
联合u_tag {
国际间；
浮点fval
char * sval
} u；变量u必须足够大，以容纳这三种类型中最大的一种，具体长度取决于具体实现。任何这些类型的对象都可以赋给U并在后续的表达式中使用，但是它们必须是一致的：读取的类型必须是最后存储的类型。程序员负责跟踪当前保存在联合中的类型。如果保存的类型与读取的类型不一致，结果取决于具体的实现。
您可以通过以下语法访问联盟中的成员：
联名。成员
或者
联合指针-成员
这与访问结构是一样的。如果变量utype用于跟踪保存在U中的当前数据类型，则可以按如下方式使用union:
if (utype==INT)
printf(%d\n ，u . ival)；
if (utype==FLOAT)
printf(%f\n ，u . fval)；
if (utype==STRING)
printf(%s\n ，u . sval)；
其他
printf( utype中的错误类型% d in ，utype)；Union可以用在结构和数组中，反之亦然。访问结构中联合成员的表示(反之亦然)与嵌套结构中的表示相同。例如，假设您有以下结构数组定义：
结构{
char * name
int标志；
int utype
工会
国际间；
浮点fval
char * sval
} u；
} symtab[NSYM]；它的成员ival可以被下面的语句引用：
Symtab[i].u.ival也可以通过以下语句之一引用字符串sval的第一个字符：
*symtab[i].u.sval
Symtab[i].u.sval[0]实际上，一个并集是一个结构，其所有成员相对于基址的偏移量为0。这种结构的空间应足够大，以容纳最宽的成员，其排列应适合联盟中所有类型的成员。union允许的操作与structure允许的操作相同：将成员作为一个整体进行赋值、复制、寻址和访问。
Union只能用它的第一个成员类型的值初始化，所以上面的union u只能用整数值初始化。
第8章中的存储分配程序将解释如何使用union来强制一个变量存储在一个特定的类型中。
边界上对齐。
9. 位字段在存储空间很宝贵的情况下，有可能需要将多个对象保存在一个机器字中。一种常用的方法是，使用类似于编译器符号表的单个二进制位标志集合。外部强加的数据格式（如硬件设备接口）也经常需要从字的部分值中读取数据。
考虑编译器中符号表操作的有关细节。程序中的每个标识符都有与之相关的特定信息，例如，它是否为关键字，它是否是外部的且（或）是静态的，等等。对这些信息进行编码的最简洁的方法就是使用一个char或int对象中的位标志集合。
通常采用的方法是，定义一个与相关位的位置对应的“屏蔽码”集合，如：
#define KEYWORD 01
#define EXTRENAL 02
#define STATIC 04或
enum { KEYWORD = 01, EXTERNAL = 02, STATIC = 04 };这些数字必须是2 的幂。这样，访问这些位就变成了用第2 章中描述的移位运算、屏蔽运算及补码运算进行简单的位操作。
下列语句在程序中经常出现：
flags = EXTERNAL STATIC;该语句将flags中的EXTERNAL和STATIC位置为1，而下列语句：
flags = ~(EXTERNAL STATIC);则将它们置为0。并且，当这两位都为0 时，下列表达式：
if ((flags (EXTERNAL STATIC)) == 0) ...的值为真。
尽管这些方法很容易掌握，但是，C语言仍然提供了另一种可替代的方法，即直接定义和访问一个字中的位字段的能力，而不需要通过按位逻辑运算符。位字段（bit-field），或简称字段，是“字”中相邻位的集合。“字”（word）是单个的存储单元，它同具体的实现有关。例如，上述符号表的多个#define语句可用下列3 个字段的定义来代替：
struct {
unsigned int is_keyword : 1;
unsigned int is_extern : 1;
unsigned int is_static : 1;
} flags;这里定义了一个变量flags，它包含3 个一位的字段。冒号后的数字表示字段的宽度（用二进制位数表示）。字段被声明为unsigned int类型，以保证它们是无符号量。
单个字段的引用方式与其它结构成员相同，例如：flags.is_keyword、
flags.is_extern 等等。字段的作用与小整数相似。同其它整数一样，字段可出现在算术表达式中。因此，上面的例子可用更自然的方式表达为：
flags.is_extern = flags.is_static = 1;该语句将is_extern和is_static位置为1。下列语句：
flags.is_extern = flags.is_static = 0;将is_extern和is_static位置为0。下列语句：
if (flags.is_extern == 0 flags.is_static == 0)
...用于对is_extern和is_static位进行测试。
字段的所有属性几乎都同具体的实现有关。字段是否能覆盖字边界由具体的实现定义。字段可以不命名，无名字段（只有一个冒号和宽度）起填充作用。特殊宽度0 可以用来强制在下一个字边界上对齐。
某些机器上字段的分配是从字的左端至右端进行的，而某些机器上则相反。这意味着，尽管字段对维护内部定义的数据结构很有用，但在选择外部定义数据的情况下，必须仔细考虑哪端优先的问题。依赖于这些因素的程序是不可移植的。字段也可以仅仅声明为int，为了方便移植，需要显式声明该int类型是signed还是unsigned类型。字段不是数组，并且没有地址，因此对它们不能使用 运算符。
©
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。