《The C Programming Language, 2nd Edition》K&R Chapter 6 - Structures 笔记
结构
如果结构声明不后跟变量表，则只是结构的模板或轮廓，不分配内存，如：
struct point {
int x;
int y;
};
如果结构声明后跟变量表，会为变量分配内存，这是个定义，如struct { ... } x, y, z;。
如果结构声明带有标记，那么可以使用这个标记定义变量，如struct point pt;。
结构定义可以后跟初值表进行初始化，如struct maxpt = { 320, 200 };。
静态结构初值表中每个成员对应的初始值必须为常量表达式，自动结构无此限制。
自动结构还可以通过赋值初始化。
结构支持赋值、取址、成员访问。不支持比较。
结构可以嵌套。
结构传递时，指针复制的效率要比复制整个结构要高。
访问结构指针成员，如(*pp).x，()是必须的，因为.的优先级比*高。
C语言提供访问结构指针成员的简写：p->结构成员。
.和->都是从左向右结合。
所有运算符中，结构运算符.和->，函数调用()，下标[]优先级最高。
++p->len等价于++(p->len)。
*p->str等价于*(p->str)。
*p->str++等价于(*(p->str))++。
*p++->str先读str指向的对象的值，然后再将p加1。
结构体数组支持初始化列表进行初始化：
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
};
当然以下这种也支持：
{ "auto", 0 },
{ "break", 0 },
{ "case", 0 },
...
结构的长度不等于成员长度之和，因为对齐要求，结构中会出现空穴(hole)。
struct {
char c;
int i;
};
假如char占1字节，int占4字节，这个结构占8字节，而不是5字节。
sizeof
编译时(compile-time)一元运算符sizeof，支持sizeof 对象或sizeof(类型名)。
sizeof返回字节数，返回值为size_t类型，在<stddef.h>中定义。
sizeof支持结构和指针。
获取数组长度的常用方法为#define NKEYS (sizeof keytab / sizeof(keytab[0]))。
#if语句中不能使用sizeof，预处理器不分析类型名。
#define语句中可以使用sizeof，因为#define语句不求值。
指针
两个指针之间的加法运算是非法的，但减法运算是合法的。
&tab[-1]和&tab[n]都超过了数组边界，但前者是非法的，后者是合法的，C语言保证数组末尾之后的第一个元素的指针运算合法，间接取址非法。
typedef
typedef语法：typedef int Length;，Length与int同义。
typedef char *String;，String与char*同义。
typedef不创建新的类义，也不增加新的语义。
typedef由编译器解释，功能超过预处理器的能力。
typedef int (*PFI)(char *, char *)，PFI是形参为两个char*，返回int的函数指针。
typedef为不同大小的整型定义类型名，提高可移植性。
联合
联合语法：
union u_tag {
int ival;
float fval;
char *sval;
} u;
联合读取的类型必须是最近一次存入的类型，否则结果取决于具体实现。
联合与结构、数组之间可以嵌套。
联合本质上是一个结构，所有成员相对于基地址的偏移量都为0。
联合的大小要足够容纳最宽的成员，对齐方式要适合所有成员。
联合只能用第一个成员类型进行初始化。
位字段(bit-field)
位字段语法：
struct {
unsigned int is_keyword : 1;
unsigned int is_extern : 1;
unsigned int is_static : 1;
} flags;
冒号后的数字表示字段的宽度，单位为bit。
与结构相同，字段可以像小整数一样，出现在算术表达式中。
字段是否能覆盖字边界取决于具体实现。
字段可以不命名(只有冒号和宽度），起填充作用。
宽度0的字段必须是不命名的，表示下一个成员强制在下一个字边界上对齐。
字段是从左向右分配，还是相反取决于机器。
字段没有地址，不能&取地址。
- 字边界的概念，经测试，我理解为字为CPU处理的最自然长度，通常为int。
其他
malloc函数保证内存对整齐。
例程
构造点
/* makepoint: make a point from x and y components */
struct point makepoint(int x, int y)
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
两个点相加
/* addpoints: add two points */
struct addpoint(struct point p1, struct point p2)
{
p1.x += p2.x;
p1.y += p2.y;
return p1;
}
判断点是否在矩形中
/* ptinrect: return 1 if p in r, 0 if not */
int ptinrect(struct point p, struct rect r)
{
return p.x >= r.pt1.x && p.x < r.pt2.x
&& p.y >= r.pt1.y && p.y < r.pt2.y;
}
矩形坐标规范化
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
/* canonrect: canonicalize coordinates of rectangle */
struct rect canonrect(struct rect r)
{
struct rect temp;
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);
return temp;
}
不同版本的统计源代码中的关键字出现次数
相同代码：
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
};
/* getword: get next word or character from input */
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];
}
差异代码：
#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 */
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;
}
#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 */
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;
}
统计出现的单词和频率(二叉树实现)
struct tnode { /* the tree node: */
char *word; /* points to the text */
int count; /* number of occurrences */
struct tnode *left; /* left child */
struct tnode *right; /* right child */
};
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
/* word frequency count */
main()
{
struct tnode *root;
char word[MAXWORD];
root = NULL;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
treeprint(root);
return 0;
}
struct tnode *talloc(void);
char *strdup(char *);
/* addtree: add a node with w, at or below p */
struct tnode *addtree(struct tnode *p, char *w)
{
int cond;
if (p == NULL) { /* a new word has arrived */
p = talloc(); /* make a new node */
p->word = strdup(w);
p->count = 1;
p->left = p->right = NULL;
} else if ((cond = strcmp(w, p->word)) == 0)
p->count++; /* repeated word */
else if (cond < 0) /* less than into left subtree */
p->left = addtree(p->left, w);
else /* greater than into right subtree */
p->right = addtree(p->right, w);
return p;
}
/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}
#include <stdlib.h>
/* talloc: make a tnode */
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
char *strdup(char *s) /* make a duplicate of s */
{
char *p;
p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */
if (p != NULL)
strcpy(p, s);
return p;
}
宏替换(Hash实现)
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
/* hash: form hash value for string s */
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; /* found */
return NULL; /* not found */
}
struct nlist *lookup(char *);
char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /*free previous defn */
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}