Chapter 1 模块化程序设计

代码规范

1. 不直接使用基础类型
   使用指示了大小和符号的typedef以代替基本数据类型

   typedef char char_t;
   typedef signed int int32_t;
   

   typedef详见C语言笔记

2. 变量、函数的命名符合编码规范
   Pascal命名规则：当变量名和函数名称是由二个或二个 以上单字连结在一起，而构成的唯一识别字时，第一个单字首字母采用大写字母，后续单字的首字母亦用大写 字母，例如：FirstName、LastName。

3. 小心使用全局变量
   多线程代码中非常数全局变量是禁止使用的。内建类型的全 局变量是允许的，但使用时务必三思

4. 用访问器子程序来取代全局数据
   把数据隐藏到模块里面。用static关键字来定义该数据，写出可以read读、write和initialize初始化该数据的子程序来。要求模块外部的代码使用该访问器子程序来访问该数据，而不是直接操作它。

结构化程序设计

自顶向下，逐步求精，函数实现

调用返回结构：控制模块+工作模块(worker，单一)

​ 降低程序的构思，编写，调试复杂度

​ 可读性好

注意问题

​ 起名：见名知意

​ 少用全局变量

​ 限制函数长度

​ 函数参数：每个函数头要有注释

模块

较小的原文济南称为模块，包含main函数的模块叫做主模块（main module）

独立编译单元：utility.c->utility.obj

头文件

• 内容是函数声明（函数原型要求）、常量定义等

• 作用
  调用函数功能 在很多场合，源代码不便（或不准）向 用户公布，只要向用户提供头文件和二进制的库即可。用户只需要按 照头文件中的接口声明来调用库功能，而不必关心接口怎么实现的。 编译器会从库中提取相应的代码。
  加强类型安全检查 如果某个接口被实现或被使用时，其方式与头文件中的声明不一致，编译器就会指出错误，这一简单的规则 能大大减轻程序员调试、改错的负担

• eg.如果一个源文件如：Utility.c中，要使用 Utility.h中声明的函数、类型和具名符号等，在该源文件开始处：

  #include “Utility.h” 
  #include  <stdio.h>
  

• 组成：只用于声明，不包含或生成储存空间的变量或函数的定义

  • 版权和版本说明
  • 预处理块
  • 函数，结构和枚举类型声明，外部变量声明、具名常量定义。typedef和宏等

• #define保护
  函数、变量的声明都可以重复，同一个声明出现多次也不会影响程序的运行，但重复引用头文件会浪费编译时间；
  当头文件中包含结构的定义、枚举定义等一些定义时，这些定义时不可重复的，必须通过一定措施防止重复引用

  #ifndef _HEADERNAME_H
  #define _HEADERNAME_H
  .....//头文件内容
  #endif
  

编译预处理

c语言由源代码生成的各阶段如下：
C源程序->编译预处理->编译->汇编程序->链接程序->可执行文件

编译预处理：读取C源程序，对其中的伪指令（以#开头）和特殊符号进行处理。扫描源代码，对其进行初步的转换，产生新的源代码提供给编译器。主要包括：条件编译，宏定义和文件包含

一整行语句构成了一条预处理指令，意味着程序的一行只能有一个有效的预处理命令行

伪指令（预处理指令）
#+指令关键字

#			//空指令
#include	//包含一个源代码文件
#include < > 
//用于标准或系统提供的头文件，到保存系统标准头文件的位置查找头文件。
#include " "
//常用于程序员自己的头文件。先查找当前目录是否有指定名称的头文件，然后在从标准头文件目录中查找。
#define		//定义宏
#undef		//取消已定义的宏
#if			//如果给定条件为真，编译下面代码
#ifdef		//如果宏已定义，编译下面代码	
#ifndef		//如果宏没有定义，则编译下面代码
#elif		//如果前面#if给定条件不为真，当前条件为真，编译下面代码	
#endif		//结束一个#if...#else条件编译块
#error		//停止编译并显示错误信息

带参数的宏定义
#define 宏名(形参表) 字符串

• 带参宏定义中，宏名和形参表之间不能有空格出现
• 要宏展开，而且要用实参去代换形参。
• 形式参数是标识符，不分配内存单元，因此不必作类型定义。而宏调用中的实参有具体的值，要用它们去代换形参。实参也可以是表达式。
• 宏定义是直接替换，不包括任何其他处理，因此一般在定义时要用括号括起来

  #define MA(x, y)  ( x*y )i = 5;i = MA(i, i + 1) – 7;//=19
//i=i*i-1-7=5*5-1-7=19
修改：  #define MA(x, y)  ( (x)*(y) )

递归

• 调用递归函数：调用另一个有着相同名字和 相同代码的函数。
• 每次调用函数时分配参数和局部变量的存储 空间，退出函数时释放。
• 随着递归函数的层层深入，存储空间的一端 逐渐增加，然后随着函数调用的层层返回， 存储空间的这一端又逐渐缩短。
• 递归存在着可用堆栈空间过度使用的危险。（禁止没有base case的无穷递归）
• 对于某一小范围内的问题，使用递归会带来简单、优雅的解。对于大多 数问题，它所带来的解将会是极其复杂的。因此要有选择地使用递归。
• 递归存在着可用堆栈空间过度使用的危险，这能导致严重的错误。在安 全相关系统中强制规定：不能使用递归函数调用。
• **递归调用：**在调用一个函数的过程中又出现直接或间接地调用该函数本身。
  **嵌套调用：**在调用一个函数时，其函数体内又包含另一个函数的调用。

汉诺塔问题

#include<stdio.h>
#include<string.h>
int tot=0;
void move(int num,char *a,char *b){printf("move %d from %s to %s\n",num,a,b);tot++;return ;
} 
void hanoi(int num,char *x,char *y,char *z){//从x借助y转移到zif(num==1) move(num,x,z);else {hanoi(num-1,x,z,y);move(num,x,z);hanoi(num-1,y,x,z);}return ;
}
int main(){hanoi(3,"A","B","C");printf("%d",tot);
} 

递归求简单交错幂级数的部分和

本题要求实现一个函数，计算下列简单交错幂级数的部分和：

f(x,n)=x−x²+x³−x⁴+⋯+(−1)ⁿ⁻¹xⁿ

double fn( double x, int n ){if(n==1) return x;return x*(1-fn(x,n-1));
}

Chapter 2 多文件项目

文本文件和二进制文件

例如：整数1234

文本文件： 49 50 51 52（4个字符）

二进制文件保存：04D2（1234的二进制数）

函数

fread(buffer,size,count,fp);
//从二进制文件中读入一个数据块到变量
fwrite(buffer,size,count,fp);
//向二进制文件中写入一个数据块buffer: 指针，表示存储数据的变量首地址
size:数据块的字节数
count：要读写的数据块数目
fp:文件指针

多文件的程序结构

• 一个大程序会由几个文件组成,把保存有一部分程序的文件成为程序文件模块（函数书写的载体）

多文件的程序结构（程序 - 文件 - 函数）

• ​ 整个程序只允许有一个main函数，包含main函数的模块叫主模块

• 一个程序通常包含多个.h文件和 .c文件

  • .h文件（头文件）

    ​ 为了方便模块中的函数被别人调用，专门形成一个头文件，内容是类型定义，typedef，函数原型声明，全局变量外部声明，常量定义等。

  • .c文件（实现文件）

    ​ 函数定义（实现），全局变量定义

    • 通常，每一个.c文件都有一个对应的.h文件。

• 补充：定义与声明的区别

​ 定义：只能定义一次，意味着分配空间

​ 声明：说明，不会再分配空间

文件模块间的连接

文件包含

通过#include "demo.h"实现

重复包含

对声明没有影响，对定义有影响（定义不可以重复）

头文件#include保护符#define机制

也会出问题，不要在头文件中定义变量、函数（在link时会出现错误），而是声明变量

文件模块间的通信–存储类别

变量存储类别

• extern

  在某个文件定义了一个全局变量，在另一个文件中去使用该变量，用extern声明，告诉编译器该变量在其他文件中已经定义，此处引用。
  不能对变量进行初始化

• static
  用static修饰局部变量（函数内的），那这个变量就不会存储在栈区，而是存储在静态数据区，其生命周期会一直持续到整个程序结束，该变量只在初次运行时进行一次初始化，但作用域只能在函数里面。
  用static修饰一个全局变量，那这是一个只允许本源文件中所有函数使用的全局变量。

• register
  早期c语言编译器不会对代码进行优化 ， 用register关键字修饰变量 ， 请求让编译器将变量a直接放入寄存器里面，以提高读取速度，在C语言中register关键字修饰的变量不可以被取地址，但是c++中进行了优化 。
  c++中依然支持register关键字，但是c++编译器也有自己的优化方式，即某些变量不用register关键字进行修饰，编译器也会将多次连续使用的变量优化放入寄存器中，例如入for循环的循环变量i。
  c++中也可以对register修饰的变量取地址，不过c++编译器发现程序中需要取register关键字修饰的变量的地址时，register关键字的声明将变得无效。

• auto
  函数中未指定存储类别的局部变量，其隐含的存储类别为自动存储类别。
  函数中的局部变量，如果不专门声明为static存储类别，都是动态的分配存储空间，数据存储在动态存储区中。这类变量叫做自动变量，可以用关键字auto作为存储类型的声明，实际上关键字auto是可以省略的（一般不写），不写则自动隐含为“自动存储类别”。

  在C语言中，使用 auto 修饰的变量，是具有自动存储器的局部变量，但很少有人去使用它，在C++11中，auto 有了新的含义，它不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto 声明的变量必须由编译器在编译时期推导而得。

文件模块与函数

• 外部变量/函数 extern

  在引用其他文件的变量时，前缀 extern

• 静态全局变量 /函数 static

  时全局变量只限于本文件引用，而不能被其他文件引用

工程文件

Chapter 3 链表

内存动态分配

C程序内存分布区域

1.代码区

​ 主函数，其他函数

2.静态存储区（编译器内存静态分配

​ 编译时分配空间，到程序结束时空间释放。

​ 全局变量+静态局部变量

3.栈区/局部变量区（编译器内存静态分配

​ 生命期短，函数调用时分配空间，函数结束时收回空间。

​ 自动变量，在执行进入变量定义所在的复合语句时为它们分配存储，变量的大小也是静态确定的。

​ main局部变量

​ 其他函数内局部变量

4.堆区

​ 内存动态分配 随时开辟释放。

动态按需分配

编写程序时，不知道需要处理的数据量or难以评估数据量的变动程度

申请空间足够大？浪费+不能修改+数组越界----->按需动态分配

不是预先分配，而是在程序运行时由系统根据程序的需要即时分配内存，且分配的大小就是程序要求的大小，并在使用完毕后尽早释放不需要的内存。

• 用时申请

• ！用完释放 //不释放会出现内存溢出

• 同一段内存可以有不同的用途

步骤

1. 了解需要多少内存空间

2. 利用C语言提供的动态分配函数来分配所需要的存储空间

3. 使指针指向获得的内存空间，以便用指针在该空间内实现运算或操作

4. 当使用完毕内存后，释放这一空间

所需函数

• void *malloc(unsigned size)

  • 在内存的动态存储区中分配一连续空间，长度为size

  • 申请成功，返回一个指向所分配内存空间的起始地址的指针

  • 申请不成功，返回null

  • 返回类型（void*）：通用指针,需强制类型转换

  #include<stdlib.h>
  void *malloc(unsigned size)
  -----------------------------
  if((p=(int *)malloc(n*sizeof(int)))==NULL){
  //sizeof计算大小
  //强制类型转换赋值给p,p指向起始地址指针，p+1下一个int位置
  //每次都要检查是否成功printf("Not able to allocate memory.\n");exit(1);
  }

• void *calloc(unsigned n,unsigned size)

  • 计数动态存储分配函数
  • 分配n个连续空间，每一段长度为size，分配后会把存储块内全部初始化为0
  • 若申请成功，则返回一个指向被分配内存空间的起始地址的指针
  • 若申请内存空间不成功，则返回NULL

  #include<stdlib.h>void *calloc(unsigned n,unsigned size)
  

• void free(void *ptr)

  • 动态存储释放函数
  • ptr为指向要释放空间的首地址，释放ptr所在的整块内存空间
  • 一定要存储内存首地址ptr，否则无法释放
  • free不能重复释放一块内存
  • ptr指向地址仍然存在，仍然可以调用，最好free之后令ptr=null，否则容易错误

  #include<stdlib.h>void free(void *ptr)//动态存储释放函数
  

• void *realloc(void &ptr,unsigned size)

  • 更改以前的存储分配

  • ptr必须是以前通过动态存储分配得到的指针；size为现在所需要的空间大小

  • 如果调整失败，返回NULL，同时原来ptr指向存储块的内容不变。

  • 如果调整成功，返回一片能存放大小为size的区块，并保证该块的内容与原块的一致。如果size小于原块的大小，则内容为原块前size范围内的数据；如果新块更大，则原有数据存在新块的前一部分。

  • 如果分配成功，原存储块的内容就可能改变了，因此不允许再通
    过ptr去使用它。

  #include<stdlib.h>
  void *realloc(void *ptr,unsigned size)//更改以前的存储分配
  

//计算任意n个数字的和
#include<stdio.h>
#include<stdlib.h>
int main(){int n,sum=0,i,*p;printf("Enter n:");scanf("%d",&n);if((p=(int *)calloc(n,sizeof(int)))==NULL){printf("NULL");exit(1);}for(i=0;i<n;i++) scanf("%d",p+i);for(i=0;i<n;i++) sum+=*(p+i);printf("%d",sum);free(p);return 0;
}

链表

一种动态存储分布的数据结构，若干个同一结构类型的结点依次串接而成

不连续的数组？ 存储相同类型、不同地方的一批数，通过**链（指针）**连接起来。
与数组相比，链表是动态存储分布的数据结构。根据需要动态地开辟内存空间，可以比较自由方便地插入新元素（结点），故使用链表可以节省内存， 操作效率高。

单向链表 双向链表 环

单向链表的实现

链表节点的类型定义

//结构的递归定义
struct node{数据成员：int，double，stuct等struct node *next;  //链成员（node型指针）
};

链表的表示

头指针struct node *head，

尾结点

链表的基本操作

• 链表的建立
• 链表的遍历/求表长
• 插入结点
• 删除结点
• !!!不能使 链 断掉

#include<stdio.h>
#include<stdlib.h>
struct stu_node{int num;char name[20];int score;struct stu_node *next;
};
struct stu_node *head=NULL,*tail=NULL;struct stud_node *createlist(){//链表的建立
//首先建立一个空链表
//然后加入新节点到已有链表的末尾 int num,score;char name[20];int size=sizeof(struct stud_node);struct stud_node *q;scanf("%d",&num);while(num!=0){scanf("%s%d",name,&score);q=(struct stud_node *)malloc(size);q->num=num; q->score=score;strcpy(q->name,name);q->next=NULL;if(head==NULL) head=q;else tail->next=q;tail=q;scanf("%d",&num);}return head;
}
struct stud_node *deletelist( struct stud_node *head, int min_score ){//删除成绩小于min_score的结点struct stud_node *ptr1,*ptr2;//处理前部while(head!=NULL&&head->score<min_score){ptr2=head;head=head->next;free(ptr2);}if(head==NULL) return head;ptr1=head;ptr2=ptr1->next;while(ptr2!=NULL){if(ptr2->score<min_score){ptr1->next=ptr2->next;free(ptr2);}else ptr1=ptr2;ptr2=ptr1->next;}return head;
}int main(){struct stu_node *p;createlist();deletelist(head,20);
}

while(data>0){//逆向建表p=(struct ListNode *) malloc(size);p->data=data;p->next=head;head=p;scanf("%d",&data);
}
//合并链表
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2){struct ListNode *head,*p;head=p=NULL;while(list1!=NULL&&list2!=NULL){if(list1->data < list2->data){if(head==NULL) 	head=p=list1;else p->next=list1,p=p->next;;list1=list1->next;}else {if(head==NULL) 	head=p=list2;else p->next=list2,p=p->next;list2=list2->next;}}if(head==NULL) return head;if(list1==NULL) p->next=list2;else p->next=list1;return head;
}
//链表奇偶分离
//函数getodd将单链表L中奇数值的结点分离出来，重新组成一个新的链表。返回指向新链表头结点的指针，同时将L中存储的地址改为删除了奇数值结点后的链表的头结点地址（所以要传入L的指针）。
struct ListNode *getodd( struct ListNode **L ){struct ListNode *p,*ptr1,*ptr2,*odd;p=*L;*L=odd=NULL;ptr1=ptr2=NULL;while(p!=NULL){if(p->data%2==1)	{if(odd==NULL)	odd=p,ptr1=p;else ptr1->next=p,ptr1=ptr1->next;}else {if(*L==NULL) *L=p,ptr2=p;else ptr2->next=p,ptr2=ptr2->next;}p=p->next;}if(ptr1) ptr1->next=NULL;if(ptr2) ptr2->next=NULL;return odd;
}//链表逆置
struct ListNode *reverse( struct ListNode *head ){if(head==NULL||head->next==NULL) return head;struct ListNode *ptr=head->next;if(ptr->next==NULL){ptr->next=head;head->next=NULL;return ptr;}struct ListNode *p=reverse(head->next);ptr->next=head;head->next=NULL;return p;
}
//链表逆置2
struct ListNode *reverse( struct ListNode *head )
{struct ListNode *L=head;if(L==NULL)	return NULL;	struct ListNode *l1=NULL;struct ListNode *l2=NULL;	while(L!=NULL)	{	l1=L->next;		L->next=l2;		l2=L;		L=l1;	}return l2;}

Chapter 4 指针进阶

主要内容

二级指针的概念与变量定义
指针数组的定义和使用
指针数组名与二级指针的关系
命令行参数
数组指针的概念与变量定义
二维数组和指针的关系
二维数组名作为函数的参数
多个字符串的处理
函数指针的定义和使用

二级指针（指向指针的指针）

定义： 类型名 * * 变量名

二级指针	一级指针	变量
int **p2	int *p1	int i
p2	p1	i
&p1	&i	3

#include<stdio.h>
int main(){int a=10,b=20,t;int *pa=&a,*pb=&b,*pt;int **ppa=&pa,**ppb=&pb,**ppt;ppt=ppb,ppb=ppa,ppa=ppt;pt=pb,pb=pa,pa=pt;t=b,b=a,a=t;printf("%d %d\n",a,b);// 20 10printf("%d %d\n",*pa,*pb);// 10 20printf("%d %d\n",**ppa,**ppb);//20 10
} 

指针数组

类型名 * 数组名[数组长度]

数组元素是指针类型，用于存放内存地址

指针数组名是一个二级指针

int main(){int a[4]={1,2,3,4},i;int *b[4];for(i=0;i<4;i++) b[i]=&a[i];*b[i]==**(b+i)==*(a+i)==a[i]
} 

/*例：使用指针数组输出5种颜色的英文名称*/
#include<stdio.h>
int main(){int i;char  *color[5]={"red","blue","yellow","green","purple"};for(i=0;i<5;i++) printf("%s\n",color[i]);  //输出字符串for(i=0;i<5;i++) printf("%c\n",*color[i]); //输出字符串首字母return 0;
} 

字符数组，字符指针 字符串

#include<stdio.h>
int main(){char sa[]="hello";char *str="This is a string";str=sa;str="new string";//sa的长度与 串常量长度相等，可以视作串常量的备份 //sa是数组名，为常量指针，永远指向数组的首元素//str是字符指针，为变量，经修改可以指向新的字符 
} 

命令行参数

C语言源程序经编译和连接处理，生成可执行程序(例如test.exe)后，才能运行。
在OS的命令行模式窗口中，输入可执行文件名，就以命令方式运行该程序。
输入命令时，在可执行文件(命令)名的后面可以跟一些参数,这些参数被称为命令行参数，这些参数传递给main

win+R  cmd 打开dir 查看该目录下可运行程序dir/p 翻页展开dir/w 平铺展开

命令行的一般形式为

命令行 参数1 参数2 …参数n

使用命令行的程序不能在编译器中执行，需要将源 程序经编译、链接为相应的命令文件（一般以.exe 为后缀），然后回到命令行状态，再在该状态下直 接输入命令文件名。

test.cpp
#include<stdio.h>
#include<stdlib.h> 
int main(int argc,char *argv[]){//第一个参数argc接受命令行参数（包括命令名）的个数 //第二个参数argv接受以字符串常量形式存放的命令行参数,  argv[0]是命令名(text)，argv[i]是参数int x,y,sum;x=atoi(argv[1]);y=atoi(argv[2]);sum=x+y;printf("%d+%d=%d\n",x,y,sum);return 0; 
}   命令行操作
C:\Users\PC>Desktop\test 123 123
123+123=246

Chapter 5

指针补充

指针的要素：基类型，地址值

double ***p5 p5的基类型是double **

指针加法对地址值的影响

• 地址值的增量=sizeof(基类型)

理解运算符

x[y]==*(x+y)

数组指针

数组指针：指向一个数组或一个二维数组某行的指针

变量定义：

​ 类型名 （* 指针名）[数组长度]

int (*ap)[4];
char (*colorp)[5];

int (*p)[4]=NULL;
int a[8]={1,3,5,7,2,4,6,8};
p=(int (*)[4])a;
printf("%d ",(*p)[2]);
printf("%d",(*(p+1))[0]);
//out:5 2

二维数组与指针的关系

二维数组是数组元素为一维数组的一维数组

int a[n][m];
a[i]是整数指针 a[i]+1指向下一个int数
二维数组名a是一个数组指针 a+1指向下一行数组&a[i]==&a[i][0]==a+i
地址一样，但基类型不同

表达式	含义
a	数组首地址，即&a[0][0]
a[0],*(a+0),*a	&a[0][0]
a+1,a[1],*(a+1)	a[1]的首地址，即&a[1][0]
a+i,a[i],*(a+i)	a[i]的首地址，即&a[i][0]
a[1]+2,*(a+1)+2	&a[1][2]
a[i]+2,*(a+i)+2	&a[i][2]
*(a[1]+2),*(*(a+1)+2)	元素a[1][2]
*(a[i]+j),*(*(a+i)+j)	元素a[i][j]

指针作为函数的返回值

在C语言中，函数返回值也可以是指针（返回一个地址，定义和调用这类函数的方法与其他函数是一样 的。

返回指针的函数一般都返回 全局数据对象或主调函数中 数据对象的地址

不能返回在函数内部定义的局部数据对象的地址，这是 因为所有的局部数据对象在 函数返回时就会消亡，其值 不再有效

函数指针（指向函数的指针）

• 每个函数都占用一段内存单元，它们有一个入口地址( 起始地址)
• 在C语言中，函数名代表函数的入口地址。
• 可以定义一个指针变量，接收函数的入口地址，让它指向函数，这就是指向函数的指针，也称为函数指针。
• 通过函数指针可以调用函数，它也可以作为函数的参数

函数指针定义

类型名（*变量名）（参数类型表）

int (*futher)(int int)

类型名指定函数返回值的类型，变量名是指向函数的指针变量的名称。

调用

（*函数指针名）（参数表）

int fun(int x,int y);
int (*funptr)(int,int);
funptr=fun;
(*funptr)(3,5);

作用

#include<stdio.h>
int maxx(int x,int y){if(x>y) return x;return y;
}
int sum(int x,int y){return x+y;
}
int process(int x,int y,int (*fun)(int,int))
{int ret;ret=fun(x,y);return ret;
}
int main(){printf("%d\n",process(1,2,sum));printf("%d\n",process(1,2,maxx));
} //out:3 2

题目 待做

行指针（数组指针）程序解析
#include<stdio.h>
#include<string.h>
char (*defy(char *p))[5]
{int i;for(i=0;i<3;i++)p[strlen(p)]='A';return (char(*)[5])p+1;
}
int main(){char a[]="FROG\0SEAL\0LION\0LAMB";puts(defy(a)[1]+2);
}
out： ONALAMB

Chapter 6 算法分析基础

数据结构和算法的关系

数据:所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息)。
数据元素:是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等)。
数据项:构成数据元素的项目。是具有独立含义的最小标识单位(又称字段、域、属性等)。
数据对象:性质相同的数据元素的集合。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合

**逻辑结构: **指数据对象中数据元素之间的相互关系，面向问题

​ eg 线性表：有起点终点，前驱后继

**物理结构: **指数据的逻辑结构在计算机中的存储形式，面向程序

​ eg 顺序存储 ：可以用一组地址连续的存贮单元依次存储线性表元素（可通过数组实现）

算法效率的度量方法和大0记法

算法的特性： 输入，输出，有穷性，确定性，可行性

**算法设计要求：**正确性，可读性，健壮性（当输入数据不合法时，算法能做出相关处理，而非产生异常结果），时间效率高，存储量低

算法的时间复杂度

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，更应该关注最高次项的次数(阶数)

除非特别指定，提到的都是最坏时间复杂度

常见的时间复杂度有：
常数阶O(1)，对数阶O(log₂n)，线性阶O(n)，线性对数阶O(nlog₂n)，平方阶O(n²)，立方阶O(n³)，k次方阶O(n^k)，指数阶O(2ⁿ)，阶乘阶O(n!)

算法的空间复杂度

存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间，算法在运行程序中临时占用的存储空间。 算法的空间复杂度S(n)算法是对一个算法在运行过程中临时占用存储空间大小的量 度。

查找算法—线性、二分

查找方法

• 静态查找：线性查找，折半查找，索引查找
• 动态查找：二叉排序树，平衡二叉树
• 哈希表：构造哈希函数，处理冲突方法 开放定址法（线性探测法，二次探测法，伪随机探测法），链地址法，再哈希法，建立一个公共溢出区

二分查找

1. 在已排好序的数列中查找

2. 可以用while语句实现，也可用递归函数实现

   while(low<=high){mid=(low+high)/2;if() high=mid-1;else low=mid+1;
   }
   

插值查找法

核心是插值公式 时间复杂度不变（平均变快）
适用于分布均匀的情况

二分查找法
mid=(low+high)/2=low+(high-low)/2
优化：插值查找法
mid=low+(high-low)*(key-a[low])/(a[high]-a[low])

排序算法

排序方法	最好时间	平均时间	最坏时间	辅助空间	稳定性
简单选择	n^2	n^2	n^2	1	不稳定
冒泡排序	n	n^2	n^2	1	稳定
直接插入	n	n^2	n^2	1	稳定
归并排序	nlogn	nlogn	nlogn	n	稳定

稳定排序：

值相同的元素排序后相对位置不发生改变。

内排序 插入，选择，交换 等

在排序过程中待排序的记录全部放置在内存中

冒泡排序

两两比较相邻记录的关键字，若反序则交换，直至没有反序对

含有n个元素的数组原则上要进行n-1次排序。 对于每一次排序，从第一个数开始，依次比较前一个数与后一个数的大小。如果前一个数比后一个数大，则进行交换。这样一轮过后，最大的数将会“沉到底”，成 为最末位的元素。第二轮则去掉最后一个数，对前n-1个 数再按照上面的步骤找出最大数，该数将成为倒数第二 位的元素…n-1轮过后，就完成了排序。

时间效率： O(n^2) ，稳定排序

void bubblesort0(){int i,j;for(i=1;i<L->length;i++){for(j=i+1;j<L->length;j++)if(L->r[i]>L->r[j])swap(L,i,j);}
}void bubblesort1(){//真实的冒泡int i,j;for(i=1;i<L->length;i++){for(j=L->length-1;j>=i;j--)if(L->r[j]>L-r[j+1])swap(L,j+1,j);}
}

选择排序

对一组数据，每次将其中的一个数据放在它最终要放的位置。第一步 是找到整个数据中最小的数据并把它放在最终要放的第一个位置上，第 二步是在剩下的数据中找最小的数据并把它放在第二个位置上。对所有 数据重复这个过程，最终将得到按从小到大顺序排列的一组数据。

int temp,index;
for(k=1;k<=n;k++){index=k;for(int i=k+1;i<=n;i++)if(x[i]<x[index]) index=i;temp=x[index];x[index]=x[k];x[k]=temp;
}

插入排序

将待排序的记录Ri插入，到已排好序的记录表 R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。

设待排序的记录顺序存放在数组R[1…n]中，在排序的某一时刻，将记录序列分成两部分：
◆ R[1…i-1]：已排好序的有序部分；
◆ R[i…n]：未排好序的无序部分。

显然，在刚开始排序时，R[1]是已经排好序的。

int i,j;
for(i=2;i<=n;i++){if(x[i]<x[i-1]){x[0]=x[i];/*设置哨兵*/for(j=i-1;x[j]>x[0];j--)x[j+1]=x[j];x[j+1]=x[0];}
}

归并排序

对于一个规模为n的问题，若该问题可以容易地解决 （比如说规模n较小）则直接解决，否则将其分解为k 个规模较小的子问题，这些子问题互相独立且与原问题 形式相同，递归地解这些子问题，然后将各子问题的解 合并得到原问题的解。这种算法设计策略叫做分治法。

归并排序就是一个典型的分治法的例子，将一个数列 分成两部分，分别排序，然后合并。 合并操作与递归分解相结合，产生了新的排序算 法——归并排序。

算法描述：首先判断数组大小，若无元素或只有一个 元素，则数组必然已被排序；若包含的元素多于1个， 则执行下列步骤：

• step1: 把数组分为大小相等的两个子数组；
• step2: 对每个子数组递归采用归并算法进行排序；
• step3: 合并两个排序后的子数组。

#define MAXSIZE 1000
void Merge(int *x,int *y,int s,int m,int t){int i=s,j=m+1,k=s;while(i<=m&&j<=t){if(x[i]<x[j])y[k]=x[i],i++;elsey[k]=x[j],j++;k++;		}while(i<=m) {y[k]=x[i];i++;k++;} while(j<=t){y[k]=x[j];j++;k++;}
}
void MergeSort(int *SR,int *TR,int s,int t){int m;int TR2[MAXSIZE];if(s==t)TR[s]=SR[s];else{m=(s+t)/2;MergeSort(SR,TR2,s,m);MergeSort(SR,TR2,m+1,t);Merge(TR2,TR,s,m,t);}
}
int main(){int x[100],n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x[i]);}MergeSort(x,x,1,n);
}

位运算

位运算的操作数必须是int型或者char型

位逻辑运算 ~, &, ^, |

移位运算 << , >>

复合位赋值运算 &= , |= , ^= , >>= , <<=

符号	名称	规则
~	按位取反	单目，右结合
&	按位与	同1则1
^	按位异或	不同取1，相同取0
|	按位或	有1则1
<<	左移	高位丢弃，低位补0
>>	右移	低位丢弃，高位补0或1（系统实现不同）

Chapter 7 图形程序设计基础

• 初步了解Windows程序，理解Windows消息机制和事件编程
• 学习课程交互式图形编程的基本框架
• 学习使用Windows API来编写GUI程序
• 熟悉graphics.h的接口函数，实现基本的图形程序，实践综合性交互式图形程序

GUI编程相关C基础知识

typedef

​ 已有类型重新命名

函数指针

​ int (*funptr)(int a,int b);

typedef void (*FunPtr)(int a,int b);
FunPtr fptr;//<==> void (*fptr)(int a,int b);

值调用

switch (a){case 0:a0();break;case 1:a1();break;case 2:a2();break;
}
//  <==>
void(*fa[])()={a0,a1,a2};
if(a>=0&&a<sizeof(fa)/sizeof(fa[0]))(*fa[a])();

void bubble(int array[],int n,int (*compare)(int a,int b))
{int i,j,k;for(j=0;j<n-1;j++)for(i=0;i<n-1-j;i++)if((*compare)(array[i],array[i+1])){t=array[i];array[i]=array[i+1];array[i+1]=t;}
}

联合体

union perdata
{int class;char officae[10];
}
perdata a,b;

结构体中，各成员有各自的内存空间

联合体中，各成员共享一段内存空间，一个联合变量的长度等于各成员中最长的长度。联合变量可被赋予任一成员值，但每次只能赋一种值，赋入新值则冲去旧值。

枚举

enum DAY{MON=1,TUE,WED,THU,FRI,SAT,SUN
};
enum today;
today=TUE;

• 枚举型是一个集合，集合中的元素(枚举成员)是一些命名的整型常量，元素之间用逗号隔开。
• DAY是一个标识符，可以看成这个集合的名字，是一个可选项，即是可有可无的项。
• 第一个枚举成员的默认值为整型的0，后续枚举成员的值在前一个成员上加1.
• 可以人为设定枚举成员的值，从而自定义某个范围内的整数。
• 枚举型是预处理指令#define的替代。
• 枚举变量类型取值集合即为枚举成员

Windows编程入门

windows API 应用程序编程接口

在windows上运行的程序，本质上都是通过调用Windows API来完成功能的

DOS VS Windows

• DOS是磁盘操作系统的缩写，它是一个单任务的操作系统，一般都是黑底白色文字的界面。DOS下的程序是过程驱动的。
• Windows是一个多任务的操作系统，它有方便用户使用的交互式界面。Windows下的程序是事件驱动的。

windows程序结构

控制台程序以main()为入口函数，Windows程序以WinMain()为入口函数

窗口

句柄

基本图形函数

绘图函数
InitGraphics()	Initializes the graphics package, open the window for rendering
MovePen(x, y)	Moves the pen to an absolute position
DrawLine(dx, dy)	Draws a line from current position to a relative coordinates
DrawArc(r, start, sweep)	Draws an arc specified by a radius and two angles
GetWindowWidth()	Returns the width of the graphics window
GetWindowHeight()	Returns the height of the graphics window
GetCurrentX()	Returns the current x-coordinate of the pen
GetCurrentY()	Returns the current y-coordinate of the pen

文本函数
DrawTextString(char *string*)	从当前位置开始输出文本（字符串）string（字符串指针）
int sprintf(char *str,const char *format)	将格式化数据输出到一个缓冲区中，形成一个字符串

其他函数
void InitConsole(void);	打开一个控制窗口 ； 从而可以用scanf/printf进行 quick&dirty 输入输 出 ；方便调试程序
void SetWindowSize(double w, double h);	设置窗口的大小 w - 窗口宽度，单位英寸 ；h -窗口高度，单位英寸 。如果设置的尺寸大于屏幕尺寸，那么 系统会进行等比例的缩小 ，使得符合屏幕大小
void StartFilledRegion(double density); void EndFilledRegion(void);	区域填充开启函数 ,开启填充->绘制封闭图形->停止填充

其他函数
void SetWindowTitle(string title);void SetPointSize(int size);
int GetPointSize(void);void SetPenSize(int size);
int GetPenSize(void);void DrawTextString(string text);
double TextStringWidth(string text);void DrawArc(double r, double start, double sweep);
void DrawEllipticalArc(double rx, double ry, double start, double sweep);
void DefineColor(string name, double red, double green, double blue);void SetFont(string font);
string GetFont(void); 

以画圆为例

文件准备

• myGraphics

  • libgraphics //
    存放解压后图形库文件
  • simpleGUI
    存放解压后的simpleGUI文件
  • myDevProject
    存放devc工程文件，临时文件包含其中
  • mySource Files
    存放自己编写的源代码

建立项目

1. 打开DEV-C++
2. 文件 -> 新建 -> 项目 新建一个Windows Application项目，C语言，重新命名为drawCircle，将生成的drawCircle.dev工程文件保存到myDevProject文件夹中
3. 将默认的main.c保存到mySource Files文件夹（名字可改）由于本次使用第三方库编程，不需要模板代码，可将全部内容删去
4. 项目管理->鼠标右键点“drawCircle”->添加文件夹libgraphics
5. 继续鼠标右键点”libgraphics“，添加MyGraphics\libgraphics文件夹下的14个文件
6. 选择菜单项目 -> 项目属性 -> 文件/目录 -> 包含文件目录，将MyGraphics\libgraphics完整路径加入

开始编写main.c

#include "graphics.h"
#include "extgraph.h"
#include "genlib.h"
#include "simpio.h"
#include "random.h"
#include "strlib.h"
#include "conio.h"
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <windows.h>
#include <olectl.h>
#include <mmsystem.h>
#include <wingdi.h>
#include <ole2.h>
#include <ocidl.h>
#include <winuser.h>
/*包含图形库中所有可能用到的头文件所需的头文件*/static double cx,cy; /*圆心坐标*/
void DrawCircle(double x,double y,double r);/* 画圆函数声明*/void Main(){ /*程序入口函数，相当于控制台程序main函数*/InitGraphics();/*初始化得到空窗口*/cx=GetWindowWidth()/2;/*得到窗口宽度的一半*/cy=GetWindowHeight()/2;/*得到敞口高度的一半*/DrawCircle(cx,cy,1);/*在窗口中心画一个半径为1的圆*/
} 
/*   
画圆函数DrawCircle(double x, double y, double r)x为圆心横坐标y为圆心纵坐标r为圆半径
*/   
void DrawCircle(double x,double y,double r){MovePen(x+r,y);/*移动画笔到圆的最右段*/DrawArc(r,0.0,360.0);/*从画笔位置开始，画一个0-360度半径为r的弧线*/
}

交互式GUI编程基础

回调函数

• 当事件发生时，调用我的函数

1.给将来会发生事件的地方注册一个回调函数.

2.当事件发生时，该回调函数被调用（执行）.

• 回调函数经常用于事件处理（ event handling ），譬如：当按下键盘、移动鼠标 等事件发生时，就调用相应的回调函数去 处理这些操作.

• 可在回调函数中实现对图形的交互。

• 注册函数已在系统中定义，直接调用即可。回调函数需要自己写

键盘消息回调函数

typedef void (*KeyboardEventCallback) (int key, int event); 
/*key表示哪个键(键盘虚拟码)
event表示按下或松开等事件*///注册回调函数    
void registerKeyboardEvent ( KeyboardEventCallback callback);registerKeyboardEvent(mykeyboard);
void mykeyboard(int key, int event)
{…. // 实现代码略
}

字符消息回调函数

typedef void (*CharEventCallback) (int char); void registerCharEvent ( CharEventCallback callback);registerCharEvent( mychar);
void mychar(int char)
{…. // 实现代码略
}

鼠标消息回调函数

typedef void (*MouseEventCallback) (int x, int y, int button, int event);
/*x,y 位置坐标，button鼠标键
Event是鼠标事件：按下、松开、移动*/void registerMouseEvent ( MouseEventCallback callback);registerMouseEvent( mymouse);
void mymouse(int x, int y, int button, int event )
{…. // 实现代码略
}

定时器消息回调函数

typedef void (*TimerEventCallback) (int timerID);void registerTimerEvent ( TimerEventCallback callback);registerTimerEvent( mytimer);
void mytimer(int timerID)
{…. // 实现代码略
}
启动定时器
void startTimer( int timerID, int timeinterval);
// timerID - 定时器的编号
// timeinterval - 定时间隔
关闭某个定时器
void cancelTimer( int timerID );
// timerID - 定时器的编号

chapter 8 SimpleGUI

去看imgui库

熟悉simpleGUI库，实现带button、菜单、文本框等控件的交互式图形程序

图形绘制是像素级，图形库里部分函数是以英寸为单位的

• 是一种简单的即时模式GUI

• 适合高刷新率的应用程序

• 屏幕总在实时刷新

• 目前只实现了三个控件

  • button 鼠标按钮
  • menulist 菜单列表
  • textbox 编辑字符串

• 必须和libgraphics库一起使用

• 在程序中包含头文件#include "imgui.h"

• 将imugui.c加入程序工程中，或者在某个C文件中包含它（不推荐）

• 在鼠标处理函数中调用simpleGUI函数

  uiGetMouse 记录鼠标状态

  void MouseEventProcess(int x,int y,int button,int event)
  {/*获取鼠标状态*/uiGetMouse(x,y,button,event);/*擦除屏幕*/DisplayClear();/*调用显示函数显示内容*/display();}
  

  button控件

  所有的控件的创建和响应都在 display函数中完成

  调用button函数 创建一个按钮

  根据返回值判断 用户是否点击了 该按钮，并进行 相应处理。

void display()
{double fH=GetFontHeight();//字体的高度double h=fH*2;double x=winwidth/2.5;double y=winheight/2-h;double w=winwidth/5;/*button(GenUIID(0),x,y,w,h,"OK");GenUIID(0) 创建一个id句柄x,y起始位置w宽度 h高度button信息*/button(GenUIID(0),x,y,w,h,"OK");button(GenUIID(0),x+=w,y,w,h,"Cancel");if(button(GenUIID(0),x+=w,y,w,h,"Quit"))exit(-1);
}

关于宏 GenUIID

#define GenUIID(N) ( ((__LINE__<<16) | ( N & 0xFFFF))^((long)&__FILE__) )

**GenUIID(k) **在编译时计算生成一个唯一号。计算时使用 ：参数k，宏调用所在的 文件名，宏调用所在的 行号 ，宏调用时的参数 k

• 用法 1: GenUIID(0) 如果一行代码只产生一个唯 一ID

• 用法 2: GenUIID(k)
  如果需要在一行代码产生多 个不同的唯一ID。
  例如： 用for循环创建三个按钮，纵向排 列，标签为names[k]

  for( k = 0; k<3; k++ )
  {button(GenUIID(k), x, y-k*40, w, h, names[k]);
  } 
  

menulist控件

• 在display函数中完成menu控件的创建和响应

• 定义菜单选项字符串

```c
char * menuListFile[ ] = {"File",
"Open | Ctrl-O",
"Close",
"Exit | Ctrl-E" }; 
```

• 绘制和处理菜单

```c
selection = menuList(GenUIID(0), x, y, w, wsub, h,
menuListFile,sizeof(menuListFile)/sizeof(menuListFile[0]));
if( selection==3 ) // choose to the menu of exitexit(-1); // act on the selection 
```

• 用户可以用鼠标选择菜单，也可以用快捷键

• 快捷键在选项字符串中给出

• 快捷键必须是Ctrl-X形式，而且位于字符串的结尾部分

• 为了使用快捷键，还需要调用simpleGUI的uiGetKeyboard 函数

• 参数说明

  int menuList(int id,double x,double y,
  //x, y - 菜单左上角坐标double w,
  //w - 类别标签的显示宽度double wlist,
  //wlist – 菜单选项的显示宽度double h,
  //h – 菜单项的显示高度char *labels[],//labels[0]是菜单的类别名，labels[1……n-1]是该类别菜单选项标签,其中可以包含快捷键int n
  //– labels中标签字符串的个数); 
  

text控件

• 在display函数中完成textbox控件的创建和编辑

static char str[80] = "Click and Edit";textbox(GenUIID(0), x, y, w, h, str, sizeof(str)); 

• 如果有多个textbox，用户可以用Tab和Shift+Tab在他们 之间轮转

• 还可以根据textbox返回值判断用户是否进行了编辑

必须定义为static，用于每个编辑框文本的存在，否则无法修改，每次都重新定义

控件颜色设置

• 调用下面的函数，使用预定义的颜色组合

void usePredefinedColors(int k);
void usePredefinedButtonColors(int k);
void usePredefinedMenuColors(int k);
void usePredefinedTexBoxColors(int k); 

• 函数usePredefinedColors会对button/menu/textbox三 种类型全部进行设置

• 而其他的三个函数对button/menu/textbox分别进行设置

• 设置自定义的颜色组合

  • 当某个参数字符串为空时，对应的颜色不做改变
  • 颜色设置是状态变量，会影响之后绘制的控件

  1. setButtonColors - 设置按钮颜色
  2. setMenuColors - 设置菜单颜色
  3. setTextBoxColors - 设置编辑框颜色
  参数
  1. frame/label - 控件框/文字标签的颜色
  2. hotFrame/hotLabel - 鼠标划过时，控件框/文字标签的颜色
  3. fillflag - 是否填充背景。0 - 不填充，1 - 填充void setButtonColors (char *frame, char*label, char *hotFrame, char *hotLabel, int
  fillflag);
  void setMenuColors (char *frame, char*label, char *hotFrame, char *hotLabel, int
  fillflag);
  void setTextBoxColors(char *frame, char*label, char *hotFrame, char *hotLabel, int
  fillflag); 

其他辅助画图函数

画一个矩形 (x,y,w,h)
fillflag 是填充与否的标志
1 - 填充
0 - 不填充
void drawRectangle(double x, double y, double w, double h,int fillflag); 

同时画矩形和标签字符串
xalignment – 指定标签和矩形的对齐方式'L' - 靠左'R' - 靠右其他- 居中
labelColor – 指定标签的颜色名void drawBox(double x, double y,double w, double h, int fillflag,char *label, char xalignment,char *labelColor);