c位操作，预处理，抽象数据

位操作

二进制数、位和字节

C用术语字节（byte）表示用于存放系统字符集的空间大小，所以一个C字节可能为8位，9位，16位或其他值。然而描述存储芯片和数据传输率时使用的字节指8位字节。

位运算符

~ 安位取反：~(10011010) = (01100101) 反转一个字节中的所有位

& 位与(10010011)&(00111101) =00010001

| 位或（10010011）|（00111101）=10111111

^位异或   可以用于转置单个位。

掩码

   任何数位与上 1 都为1；

打开位

   或 1

关闭位

  与上某位的0

转置位

   Flag= flag ^ Mask(1)

查看某一位

  If((flag & Mask) ==MASK)

     Puts(“Wow!”);

移位运算符不改变操作数

   左移  <<

   右移  >>

Unsigned long值代表颜色值，其中低位字节存放红色亮度，下一字节存放绿色亮度，第三字节存放蓝色亮度。

#define

& 就是位操作符，所以上图中使用了1 & 这个数就得到了最后一个二进制位加上‘0’的ANSIC就转换为字符存储在数组中。

这个例子中关键是生成一个N位BIT位为1的数，然后与NUM异或。

位字段

节约字段空间

是一个signed int or unsigned int 类型的位可以存储多个配置。

总的位超过一个unsigned int 是可以的，但是其中的一个字段超过了就不可以。

主要是理解定义的时候是定义BIT的个数，而赋值的时候是这个字段的位上的值，所以这个值不能大于这个字段所占用BIT所能表示的最大值。

下面是一个混合例子

上面分别用联合位字段和位运算来表示设置。

C预处理器和C库

翻译程序

首先把源代码中出现的字符映射到源字符集。

删除反斜线，

然后是换分预处理  空白  注释

然后进入预处理

预处理指令#

只作用一行最好#在最后一行，并且和指令间无空格。

组成 #define 宏替换列表或主体。

预编译的时候只是把宏替换成常量，实际的运算则发生在编译阶段。

宏常量可以用来指定标准数组的大小并作为CONST值得初始化值。

#define LIMIT 20

Const int LIM = 50;

Static data1[LIMIT];  //合法

Static int data2[LIM];//无效

Const int LIM2 = 2* LIMIT;//合法

Const int LIM# = 2*LIM;//无效

系统把宏主体当做语言符号类型字符串，而不是字符型字符串。C预处理器中的语言符号是宏定义主体中的单独的词，用空白字符把这些词分开。

如#define EIGHT 4 * 8;如果是字符串字符串替换的时候它们是一个整体，如果是语言符号则是由空格分开的 3个语言符号。

标准C只允许新定义与旧定义完全不同时才是正确的。也可以用UNDEF指令重新定义宏，

有参数的宏

#define SQUARE(X) X*X

在程序中可以这样使用：

Z = SQUARE(2);

PS：在使用过程中，它只是简单的替换，如 X+2 替换后是 x+2 * x+2; 不是(x+2)*(X+2);

宏中不要使用增量或减量运算符。

利用宏参数创建字符串：#运算符

#define PSQR(X) printf(“The square of ” #x “ is %d.\n”,((x)*(x)));

参数字符串化，传入什么就是什么不会计算。

##可以用于类函数宏的替换部分，另外还可用于类对象宏的替换部分。把两个运算符号组合成单个语言符号。

#define XNAME (n) x ## 4

XNAME(4) 变成x4

可变参量就是参数列表中的最后一个参数为省略号，这样预定义宏 __VA_ARGS__就可以被用在替换部分中，以表明省略号代表什么。

#define PR(…)  printf(__VA_ARGS__);

宏还是函数：宏某种程度上比常规的函数复杂，宏产生内联代码，就是字程序中产生语句。使用宏20次，则会把20行代码插入程序中，如果使用函数20次，那么程序只有一份函数语句的拷贝，因此节省了空间。另一方面，程序的控制必须转移到函数中，并随后返回调用程序，

#define MAX(X,Y) ((X)>(Y)?(X)(Y))

#define ABS (X) ((X)<0? –(X)(X))

#define ISSIGN (X) ((X) ==’+’ ||（x） ==’-’?1:0)

宏的名字中不能有空格，但是在替代的字符串中可以使用空格，ANSIC允许在参数列表中使用空格。

用圆括号括住每个参数，并括住宏的整体定义。

用大写字母表示宏名，该约定不如使用大写字母表示宏常量的预定用的广泛，但是使用大写字母可以提醒程序员注意宏可能产生的副作用，

如果打算使用宏代替函数来加快程序的运行速度，那么首先应确定宏是否会引起重大差异，在程序中使用一次的宏对程序运行时间可能不会产生明显的改善，在嵌套循环中使用宏更有助2加速程序的运行。

#include 指令，预处理器发现#include指令后，就会寻找后跟文件名把这个文件的内容包含到当前的文件中。

尖括号告诉预处理器在一个或多个标准系统目录中寻找文件，双引号告诉预处理器先在当前目录或文件名指定的其它目录中寻找文件，然后再标准位置寻找文件。

#include <stdio.h>

#include “hot.H”

#include “/usr/biff/p.h”

头文件内容的最常见的形式包括：

1）明显的常量，典型地EOF、NULL

2）宏函数如：getchar()

3）函数声明，包含字符串函数系列的函数

4）结构模板定义

5）类型定义

其它指令：

#undef 取消定义一个给定的#define.即使没有定义也是合法。

#define创建宏名时，那么这个标识符就是已定义的，如果变量（文件作用域）

则是未定义的，如果遇到#undef 则这个变量是未定义的。Define的作用域是从定义点开始，直到用#undef指令取消宏为止，或直到文件尾为止，如果头文件中引入宏，那么#define在文件中的位置依赖于#include指令的位置。

条件编译：

  #ifdef  #else  #endif  如：

  #ifdef MAVIS

     #include “horse.h”

     #define STABLES 5

  #else

     #include “cow.h”

     #define STABLES 5

  #endif

这些指令可以用来标记C语句块，

#ifndef

#else

#endif

因为头文件中的有些语句在一个文件中只能出现一次如：结构类型声明，，如何确保您使用的标识符在其它任何地方都没有定义过，用下划线代替文件名中间的句点字符、用下划线作为前缀，和后缀，

#if

#elif指令。

更像c中的if，可以使用关系运算符和逻辑运算符。

#if SYS == 1

#include “ibm.h”

#endif

可以使用#elif指令扩展if-else

#if sys == 1

 #include “ibmpc.h”

#elif sys ==2

 #include sys ==3

#else

 #include “general.h”

#endif

和它配套的有

#if defined  == #ifdef

一些预定义的宏

宏本质上具有文件作用域，因而__func__是c语言预定义标识符。而非预定义宏

#line指令用于重置由__LINE__和__FILE__宏报告的行号和文件名，

#error 指令发出一条错误消息，该消息包含指令中的文本。

#pragma修改编译器的某些设置。

内联函数

函数调用需要一定的时间开销，用于建立调用，参数传递，跳转到函数代码段并返回。使用类函数宏可以减少执行时间，内联函数也可以函数变为内联函数将建议编译器尽可能快速地调用该函数。也可能不起作用依赖于实现

编译器看到调用后会用函数体代替函数调用，，但是无法获得函数的地址，并且不会再调试器中调用，编译器优化内联函数时，必须知道函数定义的内容。这意味着内联函数的定义和对该函数的调用必须在同一个文件中，正因为这样，内联函数通常具有内部链接。因此在多文件程序中，每个调用内联函数的文件都要对该函数进行定义，最简单的方法就是放置在头文件中，内联函数具有内部链接所以在多个文件中定义同一个内联函数不会产生什么问题。

C允许内联函数和外部函数混用，

C 库文件依赖于实现，因此您需要明白应用与所用系统的更多的一般情况，

1）自动访问一般包含适当的头文件就可以了，但是一些旧的系统，必须自己输入函数声明，函数类型仍是到用户手册中区查找，标准C把库函数分为多个系列，每个系列的函数原型都放在一个特定的头文件中。

2）文件包含

如果函数定义为宏，可使用#include指令包含拥有该定义的文件。

3）库包含，在程序编译或链接的某些阶段，您可能需要指定库选项，即使在自动检查标准库的系统上，也可能有不常使用的函数库。

通用的工具

Rand srand malloc free()

Exit() atexit()

错误时输出了2个，说明最后一个并没有去掉前一个。实际标准C可以注册32个函数。

Exit(0执行atexit()指定的函数后，将做一些自身清理工作，它会刷新所有的输出流，关闭所有打开的流，并关闭通过标准IO函数tmpfile（）创建的临时文件。然后把控制权返回给主机环境，如果可能还向主机环境报告终止状态。

快速排序 qsort()

ANSI原型为：

Void qsort(void * base,size_t nmemb,size_t size,int(*compar)(const void *,const void*));

1.指向要排序的数组头部指针，

2.要排序的项目数量，函数原型将该值转换为size_t类型，

3.为每一个元素的大小。

4.一个指向函数的指针。来确定排序顺序。

相当于java中排序，多了几个参数。

诊断库

由头文件assert.h支持的诊断库是设计用于辅助调试程序的小型库。由宏assert()构成，该宏接受整数表达式作为参数，表达式值为假，宏assert()向标准错误流写一条错误消息并调用abort终止程序。

在包含文件前加入 NDEBUG就可以禁用调试语句。

String.h中的memcpy() 和memmove()

Void * memcpy(void * restrict s1,const void * restrict s2,size_t n);

Void * memmove(void * s1,const void *s2,size_t n);

均从s2指向的位置复制n个字节数据到s1指向的位置，且均返回s1的值，两者间的差别由关键字restrict造成，memcpy假设两个字符串之间没有重叠，move则不作这个假设，因此复制过程类似于首先将所有字节复制到一个临时的缓冲区，然后再复制到最终的目的地，

使用CPY程序员要确定2个字符之间没有重复。

类型要一致。它只是复制字节不关心类型。

本章前面部分讨论了可变宏，该宏接受可变个数的参数，头文件stdarg.h为函数提供了类似的能力，

可变参数类似java中的一样，在定义的部分

Va_list ap用于存放参数的变量，

高级数据表示

一门语言从数据开始，然后是操作方法，还有一些解决一些类似问题的处理方法（算法），

对于特定的问题要创建合适的结构（结构型数据  类），然后用上类似问题的处理方法（算法  设计模式），数据方面可以使用结构和数组（编译时就要确定大小），进一步使用结构和指向结构的指针（运行时要确定大小）。这样也是由限制的，必须运行时决定大小，进一步用数组存储指针，这样还是由大小的限制，可以重新定义结构（包含一个指向下一个结构的指针），

书上

有误，释放了指针指向的空间，那结构中的指针也没有值了，

一个类型指定两类信息：一个属性集和一个操作集，比如：int类型的属性是它表示一个整数值，因此它拥有整数的属性，可以相加想减相乘等操作。要创建一个新的数据结构，要先创建存储结构，然后是操作方式。

三个步骤完成抽象到具体的过程

1.为类型的属性和对类型执行的操作提供一个抽象的描述。这个描述不应受任何特定实现的约束，甚至不应该受到任何特定编程语言的约束。这样一种正式的抽象描述被称为抽象数据类型（ADT）.

2.开发一个实现该ADT的编程接口，即说明如何存储数据并描述用于执行所需操作的函数集合。比如在C中您可能同时提供一个结构的定义和用来操作该结构的函数原型。

3.编码代码来实现这个接口。但是使用这种新类型的程序员无需了解实现的细节。

功能设计实现。

类似一个小的程序开发。相当java的接口与实现。比java开发多出定义使用与的列表。

创建一个列表

1．列表类型总结

1．构建接口

Struct file
 
{
 
  Char title[45];
 
  Int rating;
 
};
 
Typedef struct film Item;

2．实现

定义了item之后需要决定如何存储这种类型的项目。

Typedef struct  node
 
{
 
Item item;
 
Struct node * next;
 
} Node;
 
Typedef Node * List;
 
3．使用  List movies;
 
初始化列表
 
   Movies = null;
 
  Movies.next = null;

提供一个函数来初始化

InitializeList(movies);

应该传过来一个地址：

InitializeList(&movies);

因为c按值来传递。

这样定义一个头文件

#ifndef LIST_H_
 
#define LIST_H_
 
#define TSIZE 45
 
Include <stdbool.h>
 
 
 
Struct filem
 
{
 
Char title[TSIZE];
 
 Int rating;
 
 
 
};
 
Typedef struct film Item;
 
 
 
Typedef struct node
 
{
 
Item item;
 
Struct node * next;
 
} Node;
 
Typedef Node * List;
 
/* 函数原型                        */
 
/* 操作初始化一个列表                                 */
 
/* 操作前 PLIST指向一个列表                      */
 
/* 操作后该列表被初始化为一个空列表*/
 
Void InitializeList(List * plist);

#endif

Typedef Node * List; List 成为指向Node类型的指针的名称。

List movies 是一个适合指向链表的指针。

因为你创建了一个新的类型 Listc是传值的函数调用，所以把形参的值赋予NULL并没有把调用时传递过来的指针值清空。所以要传地址。

有点类似于JAVA的接口和实现。

队列 ADT

1.类型描述

1.

定义接口

设计原型

Void InitializeQueue(Queue * pq);
 
…
 
Bool QueueIsEmpty(const Queue * pq);

2.实现

还是使用链表实现比较好，比列表多了一个尾指针

实现类似。

链表与数组

链表只能顺序访问，数组可以随机访问，

查找可以先对列表排序，这样查找平均时间减半。

对于一个排序的列表（数组）用折半搜索会比顺序收索好的多。

链表不能折半查找。

二叉树ADT

二叉树接口

Typedef SOMETHING Item;
 
   Typedef struct node
 
{
 
  Item item;
 
  Struct node * left;
 
  Struct node * right;
 
} Node;
 
Typedef struct tree
 
{
 
  Node * root;
 
  Int size;
 
} Tree;

树接口原型

1)首先初始化数，就是把头节点指针变为Null，在加上数量为0.

void InitializeTree(Tree * ptree)
 
{
 
    ptree->root = NULL;
 
    ptree->size = 0;
 
}
 
2)检查是否是空的。
 
bool TreeIsEmpty(const Tree * ptree)
 
{
 
    if (ptree->root == NULL)
 
        return true;
 
    else
 
        return false;
 
}

主要查看这个头指针是不是空的就可以了。

3)检查是不是满了

主要和最大设定的数量比较

1)计算总数

直接返回类型的数量，这个设计有点类似表中的金额，可以有个字段存储总数，也可以遍历整个来获得，各有优缺点。

int TreeItemCount(const Tree * ptree)
 
{
 
    return ptree->size;
 
}

2)添加一个节点

首先查看树是不是满的

在从跟节点检查和比较这个节点是安排在左边的树叉中还是右边的树叉中，递归进行比较。最后插入适当的位置。

3)删除一个节点

首先如果没有左节点话，就把这个节点的右指针赋给这个指针。

如果没有右节点

如果有左右的话

1)打印的话

递归形式：打印一个节点的左边打印节点打印节点的右边

递归调用先找到最左的点然后打印，在找右边的最左边打印，然后节点的右边的左左边。

Ps:如果树是平衡的话收索是比较快的，如果不平衡则就要重新排列节点使之平衡，有AVL算法可以实现，二叉树应用有：单词计数，结构定义为一个单词和一个数量，另一个就是宠物分明类别，结构定义为一个名字和一个类型的列表。

小结

了解了C的一些特征，

1.内存方面，分为三块静态内存（具有文件作用域），堆栈（自动变量）自行管理的（mcall free）.

2.基本数据类型:常有的整数，字符，数组，特有的指针，字符串。C以字符和数组或字符和指针虚拟出字符串，存储都是字符和数组。数组和指针是C的基石。

3．基本的数据操作都有，特别的有指针（指针和指针只能减比较，指针和整数可以加减），和位操作。

4. 赋值方便支持连续赋值，表达式都有值，如x=3;这个值是3，还可以传递。

5. 抽象数据方面，就是c利用typedef对面向对象的延伸。

总的来说，语言都是想通的，不同语言适用不同的应用。延伸下：

C 对静态编译方向扩展有C++ 对动态编译有object c 动态再向上有JAVA c#