结构是一个或者是多变量的集合,这些变量可能为不同的类型,为了处理方便而将这些变量组织在一个名字之下。由于结构将一组相关的变量看做是一个单元而不是各自独立的实体,因此结构有助于组织复杂的数据,特别是在大型的程序中。
工资记录是用来描述结构的一个传统的例子。每个雇员由一个属性描述,如姓名、地址、社会保险号、工资等。其中的某些属性也可以是结构,例如姓名可以分成几个部分,地址甚至工资也可以出现类型的情况。C语言中更典型的一个例子来源于图形领域:点是由一对坐标定义,矩形由两个点定义,等等。
ASNI标准在结构方面最主要的变化是定义结构的赋值操作-结构可以拷贝、赋值、传递给函数、函数也可以返回结构类型的返回值。多年以前,这一操作已经被大多数的编译器所支持,但是,直到这一标准才对其属性进行精确的定义。在ANSI标准中,自动结构和数组现在也可以进行初始化。
6.1结构体的基础知识
我们首先来建立一些适用于图形领域的结构。点是最基本的对象,假定用x和y坐标表示它,且x,y的坐标值都为整数。
我们可以采用结构体存放这两个坐标,其声明如下:
struct point
{
int x;
int y;
}
关键字struct引入结构声明。结构声明由包含在花括号内的一系列声明组成。关键字struct后面的名字是可选的,称为结构标记(这里是point)。结构标记用于为结构命名,在定义之后,结构标记就代表花括号内的声明,可以用它作为该声明的简写形式。
结构中定义的变量称为成员。结构成员、结构标记和普通变量(非成员)可以采用相同的名字,他们之间不会冲突,因为通过上下文分析总可以对它们进行区分。另外,不同结构中的成员可以使用相同的名字,但是从编程风格来说,通常只有密切相关的对象才会使用相同的名字 。
struct声明定义了一种数据类型。在标志结构成员表结束的右花括号之后可以跟一个变量表,这些与其他类型的变量声明是相同。例如:
struct{...}x,y,z;
从语法角度来说,这种方式声明与声明
int x,y,z;
具有类似的意义。这两个声明都将x,y和z声明为指定类型的变量,并且为它们分配存储空间。
如果结构声明的后面不带变量表。则不需要为它分配存储空间,它仅仅描述了一个结构的模板和轮廓。但是,如果结构声明中带有标记,那么在以后定义结构实例时便可以使用该标记定义。例如:对于上面给出的结构声明point,语句
struct point pt;
定义了一个struct point类型的变量pt。结构的初始化可以在定义的后面使用初值表进行。初值表中同每个成员对应的初值必须是常量表达式,例如:
struct point 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);
结构可以嵌套。我们可以用对角线上的两个点来定义矩形,相应的结构定义如下:
struct rect
{
struct point pt1;
struct point pt2;
}
结构rect包含两个point类型成员。如果按照下列方式声明screen变量:
struct rect screen;
则可以使用语句:
screen.pt1.x
引用screen的成员pt1的x坐标。
6.2结构与函数
结构的合法操作只有几种,作为一个整体复制和赋值,通过&运算符取地址,访问其成员。其中,复制和赋值包括向函数传递参数以及从函数返回值。结构之间不可以进行比较。可以用一个常量成员值列表初始化结构,自动结构特可以通过赋值进行初始化 。
为了更进一步理解结构,我们编写几个对点和矩形进行操作的函数。至少可以通过3种可能的方法传递结构:一是分别传递各个成员结构,二是传递整个结构,三是传递指向结构的指针。这三种方法各有利弊。
首先来看一下函数makepoint,它带有两个整型参数,并返回一个point类型的结构:
//makepoint函数:通过x,y坐标构造一个点
struct point makepoint(int x,int y)
{
strcut point temp;
temp.x=x;
temp.y=y;
return temp;
}
注意,参数名和结构成员同名不会引起冲突。事实上,使用重名可以强调两者之间的关系。
现在可以使用makepoint函数动态的初始化任意结构,也可以向函数提供结构类型参数。例如:
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)/2,(screen.pt1.y+screen.pt2.y)/2);
接下来需要编写一系列函数对点执行算术运算。例如:
//addpoint函数:将两个点相加
struct point addpoint(struct point p1,struct point p2)
{
p1.x+=p2.x;
p1.y+=p2.y;
return p1;
}
其中,函数的参数和返回值都是结构类型。之所以直接将相加所得的结果赋值给p1,而没有使用显示的临时变量存储,是为了强调结构类型的参数和其他类型的参数一样,都是通过值传递的。
下面看另外一个例子。函数ptinrect判断一个点是否在给定的矩形内部。我们采用这样一个约定:矩形包括左侧和底边,但是不包括顶边和右侧边
//ptinrect函数:如果点p的矩形r内,则返回1,否则返回0
int ptinrect(struct point p,struct rect r)
{
return p.x>=r.p1.x&&p.x<r.pt2.x&&p.y>=r.pt1.y&&p.y<r.pt2.y;
}
这里假设矩形是用标准形式表示的,其中pt1的坐标小于pt2的坐标。下列函数将返回一个规范形式的矩形: 
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
//canonrect函数:将矩形坐标规范化
struct rect canonrect(struct rect r)
{
struct rect temp;
temp.pt1.x=min(r.pt1.x,r.pt2.x);
temp.pt1.y=max(r.pt1.y,r.pt2.y);
temp.pt2.x=min(r.pt1.x,r.pt2.x);
temp.pt2.y=max(r.pt1.y,r.pt2.y);
return temp;
}
如果传递给函数的结构的结构很大,使用指针方式的效率通常比复制整个结构的效率更高。结构指针类似于普通变量指针。声明
struct point *pp;
将pp定义为一个指向struct point类型对象的指针。如果pp指向一个point结构,那么pp就为该结构,而(pp).x和(*pp).y则是结构成员。可以按照下例中的方式使用pp:  
struct point origin,*pp;
pp=&origin;
printf("origin is (%d,%d)\n",(*pp).x,(*pp).y);
其中,(pp).x中的圆括号是必须的,因为结构成员运算符“.”的优先级“”的优先级高。表达式pp.x的含义等价于(pp.x),因为x不是指针,所以该表达式是非法的。  结构指针的使用频度也比较高。为了使用方便,C语言提供了另外一种简写形式。假定p是一个指向结构体的指针,可以用   p->结构成员   这种形式引用结构成员。这样,可以用下面的形式改写上面的一行代码: 
printf("original is (%d,%d)\n",pp-y);
运算符.和->都是从左到右结合的,所以对于下面的声明:  
struct rect r,*rp=&r;
以下4个表达式是等价的
r.pt1.x;
rp->pt1.x;
(r.pt1).x;
(rp->pt1).x;
在所有的运算符中,下面4个运算符的优先级最高:结构运算符“.”和“->”、用于函数调用的“()”以及用于下标的“[]”,因此,它们同操作数之间的结合也最紧密。例如,对于结构声明  
struct
{
int len;
char *str;
}*p;
表达式  
++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.    6.3结构数组
考虑编写这样一个程序,它用来统计C语言中各个C语言关键字出现的次数。我们需要用一个字符串数组存放关键字名,一个整型数组存放相应关键字的出现次数。一种实现的方法是使用两个独立的数组分别存放它们,如下表示:
char *keyword[NKEYS];
char keycount[NKEYS];
我们注意到,这两个数组的大小相同,考虑到该特点,可以采用另一种不同的组织方式,也就是我们这里所说的结构数组。每一个关键字包含一对变量:
char *word;
int count;
这样的多个变量对共同构成一个数组。我们来看下面的声明:
struct
{
char *word;
int count;
}keytable[NKEYS];
这声明了一个结构设计key,并定义了该类型的结构数组keytable,同时为其分配存储空间。数组keytable的每个元素都是一个结构。上述的声明可以写成下列的形式:
struct
{
char *word;
int count;
};
struct key keytable[NKEYS];
因为结构keytable包含一个固定的名字集合,所以,最好将它们声明为外部变量,这样,只需要初始化一次,所有的地方都可以使用。这种结构的初始化方法与前面所述的初始化方法类似,在定义的后面通过一个用圆括号括起来的初始值表进行初始化,,如下所示:
struct key
{
char *word;
int count;
}keytable[]=
{
"auto",0,
"break",0,
"case",0,
"char",0,
"const",0,
"continue",0,
"default",0,
/*   */
"unsigned",0,
"void",0,
"volatile",0,
"while",0
};
与成员结构相对应,初值也要按照成对的方式列出。更精确的做法是,将每一行(即每个结构)的初值都括在花括号之内,如下表示:
    {"auto",0},
{"break",0},
{"case",0},
但是,如果初始值是简单变量或字符串,并且其中的任何值都不为空,则内层的花括号可以省略。通常情况下,如果初值存在并且方括号[]中没有数值,编译程序将计算数组keytab中的项数。
在统计关键字出现的次数的程序中,我们首先蒂尼keytable。主程序反复调用函数getword读取输入,每次读取一个单词。每个单词将通过折半查找函数在keytable中进行查找。注意,关键字列表必须是按照升序存储在keytable中。
    
#include < stdio.h>
#include  < ctype.h>
#include < string.h>
#define MAXWORD 100
int getword(char *,int);
int binsearch(char *,struct key *,int);
//统计C语言关键字出现的次数
main()
{
int n;
char word[MAXWORD];

while(getword(word,MAXWORD)!=EOF)
{
if(isalpha(word[0]))
{
if((n=binsearch(word,keytable,NKEYS))>=0)
ketable[n].count++;
}
}
for(n=0;n < NKEYS;n++)
{
if(keytab[n].count > 0)
{
printf("%4d %4s\n%,keytab[n].count,keytab[n].word);
}
}
return 0;

}
//binsearch函数:在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;
}
函数getword将在稍后介绍,这里只需要理解它的功能是每调用一次该函数,将读入一个单词,并将其复制到名字为该函数的第一个参数数组中。 NKEYS代表keytable中关键字的个数。尽管可以手工计算,但由机器实现会更简单、更安全,当列表可能变更时,尤其如此。一种解决的办法是,在初值表的结尾处加一个空指针,然后循环遍历keytab,直到读到尾部的空指针为止。 但实际上不需要这么做,因为数组长度在编译时已经完全确定,它等于数组项的长度乘以项数,因此,可以得出项数为: keytab的长度/struct key长度 C语言提供了一个编译时一元运算符sizeof,它可用来计算任一对象长度。表达式:
sizeof 对象
以及
sizeof(类型名)
返回一个整型值,它等于指定对象或类型占用的存储空间字节数。(严格的说,sizeof的返回值是一个无符号整型值,其类型为size_t,该类型在头文件<stddef.h>中定义)其中,对象可以是变量、数组或结构;类型可以是基本类型,如int,double,也可以是派生类型,如结构类型或指针类型。 在该例子中,关键字的个数等于数组的长度除以单个元素的长度。下面的define语句中使用了这种方法设置NKEYS的值。 #deifne NKEYS (sizeof keytab/sizeof(struct key)) 另一种方法是用数组长度除以一个指定元素的长度,如下所示:
#define NKEYS (sizeof keytab/sizeof(keytab[0]))
使用第二种方法,即使类型改变了,也不需要改动程序。 下面来讨论getword。这里给出一个更加通用的getword函数。该函数的功能已经超出了这个实例程序的要求,不过,函数本身并不复杂。getword函数从输入中读取下一个单词,单词可以是以字母开头字母和字符串,也可以是一个非空白符字符。函数返回值可能单词的第一个字符、文件结束符EOF或字符本身(如果该字符不是字母字符的话)
//getword函数:从输入中读取下一个字符或者单词
int getword(char *word,int lim)
{
int c,getch(void);
void ungetch(int);
char *w=word;
while (isspace(c=getch()))
;
if (c!=EOF)
*w++=c;
if(!isalpha(c))
{
*w='\0';
return c;
}
for(;--lim>0;w++)
{
if(!isalnum(*w=getch()))
{
ungetch(*w);
break;
}
}
*w='\0';
return word[0];
}
getword函数使用了第4章中的函数getch和ungetch。当读入的字符不属于字母数值的集合时,说明getword多读入了一个字符。随后,调用ungetch将多读入的字符放回到输入中,以便下一次调用使用。getword还使用了其他一些函数:isspace函数跳过空白符,isalpha函数识别字母,isalnum函数识别字母和数字,所有的这些函数都定义在标准头文件<stype.h>中。
类型定义(typedef):
C语言提供了一个称为typedef的功能,它用来建立新的数据类型名,例如,声明:
typedef int Length;
将Length定义为与int具有同等意义的名字。类型Length可用于类型声明、类型转换等,它和int类型完全相同,例如:
Length len,maxlen;
Length *lengths[];
类似的声明:
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 struct tnode   //树节点
{
char *word;    //指向文本
int count;     //出现次数
Treeptr left;  //左子树
Treeptr right;  //右子树
}Treenode;
上述类型定义创建了两个新类型关键字Treenode(一个结构体)和Treeptr(一个指向该结构的指针)。这样,函数talloc可相应的修改为:
Treeptr talloc(void)
{
return (Treeptr) malloc(sizeof(Treenode));
}
这里必须强调的是,从任何意义上讲,typedef声明并没有创建一个新类型,它只是为某个已存在的类型增加一个新的名称而已。typedef声明也没有增加任何新的语义:通过这种方式声明的变量与通过普通声明方式声明的变量具有完全相同的属性。实际上,typedef类似于#define语句,但由于typedef是由编译器解释的,因此它的文本替换功能要超过预处理器能力。例如:
typedef int (*PFI)(char *,char *);
该语句定义类型为PFI是“一个指向函数的指针,该函数具有两个char *类型的参数,返回值类型为int”,它可用于某一些上下文中,例如,可以用在第5章的排序程序中,如下所示:
PFI strcmp,numcmp;
除了表达方式更简洁之外,使用typedef还有另外两个重要的原因。首先,它可以使程序参数化,以提供程序的可移植性。如果typedef声明的数据类型同机器有关,那么,当程序移植到其他机器上时, 只需要改变typedef类型定义就可以了。一个经常用到的情况是,对于各种不同大小的整型值来说,都使用通过typedef定义的类型名,然后,分别为各个不同的宿主机选择一组合适的short,int和long类型大小即可。标准库中有一些例子,例如:size_t和ptrdiff_t等。 typedef的第二个作用是为程序提供更好的说明性-Treeptr类型显然比一个声明为指向复杂结构的指针更容易让人理解。