CC(含数据结构)知识点.docVIP

第一阶段 C、数据结构、C++、mfc应用知识点 C语言基础 编译过程：预处理、编译、链接、运行。 预处理： 编译： 链接： 目标文件：可重定位目标文件、可执行目标文件。 可重定位目标文件： 静态库： 共享库（动态链接库）： 可执行程序运行原理： ? 计算机系统组成：存储器、控制器、运算器、输入输出设备（I/O设备）。 总线： 存储器：SRAM、DRAM、ROM、磁盘。 SRAM： DRAM： ROM： DMA： ? 操作系统；进程、虚拟存储器、文件。 进程： 线程： 文件： 内存空间（内存映像、虚拟存储器）： ? 内存空间的分区：全局数据区、只读数据区、栈、堆。 栈： 堆： 字长：计算机在同一时间内处理的一组二进制数称为一个计算机的“字”，而这组二进制数的位数就是“字长”。 字节对齐： 字节顺序： ? 标准无参main函数声明：int main(void) main函数中的参数解释： ? 流程控制：顺序结构、选择结构、循环结构。 选择结构：if、switch。 循环结构：for、while、do...while。 ? 预处理的作用：文件包含、条件编译、宏定义。 ? 数据类型：基本数据类型、复杂数据类型、指针类型、空类型。 基本数据类型：int、char、float、double。 复杂数据类型：数组、struct结构体、union共用体、enum枚举。 数据类型转换：强制转换、隐式转换。 ? 常量：字面常量、宏常量、const常量。 变量： 存储模型：extern、static、auto、register。 extern： static： auto： register： ? 指针： 指针的作用： 指针常量与常量指针辨析： 指针数组与数组指针辨析： 指针函数与函数指针辨析： ? 数组： 数组与指针的关系： C语言中的字符串：字符数组、字符指针。 字符数组与字符指针辨析： ? 函数： 函数前置声明： 函数原型： 回调函数： 输入参数与输出参数： 值传递： 地址传递（指针传递）： 引用传递： 动态内存传递的几种方法： ? struct结构体： 结构体中的位域： union共用体（联合体）： enum枚举： ? 几个重要的关键字：const、static、sizeof、volatile、typedef。 const： static： sizeof： volatile： typedef： ? 库函数： ? 文件 文件： 流： 普通文件与设备文件： 字符设备与块设备： 文本文件（ASCII文件）与二进制文件： 文件读写的大致过程：打开文件、读/写文件、关闭文件。 打开文件的相关库函数； 读/写文件的相关库函数： 关闭文件的相关库函数； ? 数据结构 数据结构：逻辑结构+存储结构+运算。 逻辑结构： 存储结构： 主要的运算：插入、删除、查找。 数据结构的分类：线性结构、树、图、集合。 ? 线性结构：顺序表、单链表、循环链表、双链表、栈、队列。 带头结点链表与不带头结点链表的辨析： 带头结点的单链表和不带头结点的单链表的区别 带头结点的单链表和不带头结点的单链表的区别主要体现在其结构和算法操作上。 在结构上，带头结点的单链表不管链表是否为空，均含有一个头结点；而不带头结点的单链表不含头结点。 在操作上，带头结点的单链表的初始化为申请一个头结点，且在任何结点位置进行的操作算法一致；而不带头结点的单链表让头指针为空，同时其他操作要特别注意空表和第一个结点的处理。下面列举带头结点的单链表插入操作和不带头结点的插入操作的区别。 定义单链表的结点类型如下： typedef struct node { ElemType data; /*结点的数据域*/ struct node *next; /*结点的指针域或链域*/ } Slink; 1) 带头结点的单链表插入函数insert(Slink *head, int i , ElemType x) 带头结点的单链表插入函数的设计思想是：创建一个data域值为x的新结点*p，然后插入到head所指向的单链表的第i个结点之前。为保证插入正确有效，必须查找到指向第i个结点的前一个结点的指针，主要的时间耗费在查找上，因而在长度为n的线性单链表中进行插入操作的时间复杂度为O(n)。 2) 不带头结点的单链表插入函数insert(int i , ElemType x) 不带头结点的单链表插入函数的设计思想是：创建一个data域值为x的新结点*p，然后插入到单链表的第i个结点之前。由于链表不带头结点，所以当i=1时的插入操作的算法实现与i1时是有差别的，必须单独处理。为保证插入正确有效，必须查找到指向第i个结点的前一个结点的指针，主要的时间耗费在查找上，因而在长度为