Programming with C

Basic Data Type

Constant

Integer :

• Base Representation of 17 and -31

  Base	Base Representation Of 17	Base Representation Of -31
  Decimal	17	-31
  Binary	00010001	-00011111
  Octal	\(021=2*8^1+1*8^0\) (Three binary digits as a group)	\(-037=-(3*8^1+7*8^0)\) (Three binary digits as a group)
  Hexadecimal	\(0x11=(1*16^1+1*16^0)\) (Four binary digits as a group)	\(-0x1F=-(1*16^1+F*16^0)\) (Four binary digits as a group)

• Length

  Int	12
  Unsigned	12u
  Long Int	12l
  Unsigned Long Int	12lu

-原码、反码(解决减法问题)、补码(解决+0,-0问题 , 整数以补码的形式储存)

• 正数 12
  • 原码：00001100
  • 反码：00001100（正数的反码与原码相同）
  • 补码：00001100（正数的补码与原码相同）
• 负数 -12
  • 原码：10001100（最高位为符号位，负数符号位为 1）
  • 反码：11110011（原码除符号位外，其余各位取反）
  • 补码：11110100（反码加 1） 补码的补码就是原码 12h进制：8+(-2) = 8 + 10 (mod 12)
• \(12+(-12)=00001100[原]+10001100[原]=00001100[补]+11110100[补]=00000000[补]\)

• Memory

  • \(8\space bit\space =\space 1\space Byte\)
  • \(1\space KB\space = \space 1024(2^{10})B\)

• sizeof 是关键字不是函数

Operator

Increment Operator

• m = -(n++)equals m = -n++ equals m = -n; n++

In And Out

Character

• getchar() putchar()
• getchar() 是先将所有字符送入缓冲区，直到键入回车换行符后才从缓冲区中逐个读出并赋值给变量

Printf

• printf返回输出的字符数

Scanf

• scanf 非法处理：

  • scanf("%2d %2d",&a,&b);若输入12 3a，则a=12,b=3;若输入123a，则a=123,b未赋值**

    • scanf() 返回有输入的数据项数，如上例返回2

  • 空格 i. getchar()读掉 ii. scanf(" %c",&c);表达式加空格忽略空白字符

  • 缓存区清除fflush(stdin),不清除stdin会导致下一次读取到scanf终止时留下的非法字符或空白字符

  • while(getchar()!='\n'); 清除非法字符

Selection And Control

• exit(code) 需调用<stdlib.h>，退出程序，并将int型的code传给系统的调用进程
• fabs()需调用<math.h>,对浮点数求绝对值
• 判断 \(\Delta==0\)：( fabs(\(\Delta\) - 0) < = \(\xi\) ) \(\xi\)为精度

Logic Operator

• 优先级! >&& >||

Test

• 白盒测试
• 边界测试

Bitwise Operator

• 对二进制数位进行操作，只能操作int,char类型

Loops

For Loops

• for(初始化表达式;循环控制表达式;增值表达式)
• 其中初始化表达式，增值表达式可以省略
• 延时器：for(int i=0;i<99999;i++);

rand()

• rand()需要调用<stdlib.h>
• 产生一个0~RAND_MAX(32767)的随机数
• 用rand() %b + a将随机数平移到[a,a +b -1]区间内
• srand()设置随机种子
• 使用time()返回的1970.1.1 00 : 00到现在的秒数作为种子

time()

• 参数：(time_t)Pointer保存至Pointer 指向的内存，NULL 不保存
• 返回1970.1.1 00 : 00到现在的秒数

Transference

• goto
• break
• continue
• return

TypeOverflow

• Unsigned char overflow

unsigned char uc = 255; // 最大值为 255
uc = uc + 1; // 溢出 uc=0

• Int Overflow

int i = INT_MAX; // 最大值为 2147483647
i = i + 1; // 溢出 i=-2147483648

Function

Name

• Windows应用程序的标识符通常采用“大小写”混排的单词组合而 成。例如，函数名采用FunctionName这样的形式，变量名采用newValue这样的形式。
• Linux/UNIX应用程序的标识符通常采用“小写加下划线”的方式。例如函数名采用function, name这样的形式，变量名采用new_value这样的形式。

Entrance Security

• • 有的编译器会把printf的返回值作为函数的返回值返回给主函数
  • 处理：为非法输入规定一个返回值
• Defensive Programming
  • 函数接口中清楚地定义函数的行为，包括入口参数、出口参数、返回状态、异常处理
  • 尽量不使用全局变量向函数传递信息。
  • 功能要单一
  • 检查操作数及其类型的合法性，以避免发生除零、数据溢出、类型转换、类型不匹配等错误
  • 判断函数调用是否成功和函数调用失败的处理
  • 函数没有返回值时应用void声明

Scope

• 全局变量不指定初始值会自动初始化位零

assert()

• 当括号内条件为假时，终止程序并报错，输出所在行数

Conditional Compilation

• a.h 中的内容：

#ifndef _A_H_
#define _A_H_//没有指定值，默认为1
//主程序
#endif

Array

• 当数组在所有函数外定义，或用static定义为静态存储类型时，即使不给数组元素赋初值, 那么数组元素也会自动初始化为0,这是在编译阶段完成的
• C89规定在定义数组时不能使用变量定义数组的大小

2-Dimension Array

• 初始化可省略第一维的长度
• 初始值少于数组元素个数，未初始化的自动初始化为0

  short matrix[3][4] = { {1,2,3}   , {4,5}     , {6} };
  short matrix[3][4] = { {1,2,3,0} , {4,5,0,0} , {6,0,0,0} };

Linear Search

• 循环扫描整个数组

Binary Search

Pointer

• 定义指针变量并用NULL对其初始化

Function Pointer

• 一个函数名就是这个函数的源代码在内存中的起始地址
• 调用函数指针 void Function( int (*f) , int a , int b ,···)
• (*f)(a,b)：两个整型形参、返回值为整型的函数
• *f(a,b)：两个整型形参并返回 整型指针 的函数
• 可以不用指针解引用来调用函数，即把函数指针当做函数名来直接使用，编译器会自动把f解释为函数指针，格式如下f(a,b)

void type pointer

• void 类型指针是一种通用指针类型，可以指向任何类型的数据,针，即声明了一个指针变量，但未指定它可以指向哪一种基类型的数据。由于 void 类型指针不具有具体的数据类型，因此不能直接进行算术运算或解引用操作。
• 将 void 类型指针转换为具体类型的指针，以便进行解引用操作： int *intPtr = (int *)ptr;

Character Array

• 若定义时省略长度，务必加上\0：char str[]={'H','e','l','l','o','\0'};
• char str[]={'H','e','l','l','o'};不是字符串！

Character Pointers

• 字符串字面量本身代表的就是存放它的常量存储区的首地址，是一 个地址常量

• char *str="Hello";(将保存在常量存储区中的"Hello"的首地址赋值给ptr)

• 字符串"Hello"保存在只读的常量存储区中，此时不能修改*str的值

• char a[]="Hello";char *str=a;此时可以修改

• 注：str是常量，不能str++

scanf() vs gets()

• gets() puts()也是<stdio.h>的函数
• scanf以空格为分隔
• gets()以回车符作为字符串的终止符，同时读走回车符

puts()

• 以’\0’为输出结束，并且自动输出一个换行符

缓冲区溢出

• 用 fgets(name, sizeof(name), stdin);限制输入长度

Const

atoi()

• atoi()函数需要调用<stdlib> , 当某个字符可能是转换后的数值的组成部分时，函数开始执行转换，当某个字符不可能为数值的组成部分时，转换结束。

Array Pointers

一维数组

• P + 1 相当于执行P + 1*sizeof(p的基类型)

• P + + 相当于执行p = p+sizeof(p的基类型)

• 注：数组名a是指针常量，代表一个地址常量，其值是不能被改变的

• 用一维数组作函数形参与用指针变量作函数形参本质上是一样的，因为它们接收的都是数组的起始地址，都需按此地址对主调函数中的实参数组元素进行间接寻址，因此在被调函数中既能以下标形式也能以指针形式来访问数组元素。

• 但数组和指针并非在所有的情况下都是等同的。例如,

• sizeof(数组名)返回的是数组的大小

• sizeof(指针变量名)返回的是指针的大小

二维数组

• p [i][j] = * ( p[i]+j ) = *( *( p+i )+ j) = (*(p+i) )[j]

• 数组名p类型为int (*)[N],但值p==&p[0][0],(注意不是二级指针类型!)

• p =a[0] == p=*a == p = &a[0][0]

指针数组

• 可加快字符串排序的速度
• char *p[]中[ ]优先级高于*
• char *str[]={"Hello",World"}将两字符串的首地址分别给str[0],str[1]

命令行传参

• int main(int argc,char *argv[]) 其中argc为用户输入指令个数，argv储存指令

Dynamic Memory Allocation

Memmory

• 动态内存分配的内存区域称为堆（Heap），与静态存储区和栈（Stack）不同。

静态存储区

• 静态存储区用于存储全局变量和静态变量，这些变量在程序的整个生命周期内都存在。
• 静态存储区的内存分配在程序编译时完成，并在程序结束时释放。

栈

• 栈用于存储局部变量和函数调用的上下文（如返回地址、参数等）。
• 栈的内存分配在函数调用时自动进行，并在函数返回时自动释放。
• 栈的大小通常较小，并且由系统自动管理。

堆

• 堆用于动态内存分配，程序员可以在运行时请求和释放内存。
• 堆的内存分配由程序员手动管理，使用 malloc、calloc、realloc 等函数分配内存，使用 free 函数释放内存。
• 堆的大小通常较大，但需要注意内存泄漏和碎片化问题。

malloc

• p = (int *)malloc(sizeof(int))

calloc

• p=(int *)calloc(10,sizeof(int))
• 相当于声明了一个一维数组，第一个参数表示分配的数量，决定了数组的大小，第二个表示类型的大小
• malloc所没有的功能：初始化内存为0

free

• 为动态分配的内存不会在函数调用结束后被自动释放，必须使用free才能释放

realloc

• p = (int *)realloc(p, new_size * sizeof(int))
• realloc 用于调整之前分配的动态内存的大小。new_size 是新的大小，单位是字节。
• 如果 realloc 成功，它返回指向新内存块的指针，并且原来的内存块被释放。如果失败，它返回 NULL，原来的内存块保持不变。

Note

• 判断指针是否非空，是否成功分配内存
• 初始化memset(变量名，要初始化为的字符，变量大小)，指针初始化为NULL
• 释放内存
• 能用自动变量就不要用malloc，重复利用malloc申请到的内存

Struct

Memory Alignment

Union

• 不能比较，不能作为函数参数

Initialise

  union UNION{
    int score;
    int num;
  }u;
  u = { .score = 100 };

enum

• enum tag{MON,TUE,...} Day
• 默认从0开始，也可以自定义赋值，后面未指定值的为前一个的值加1

Linked Table

establishment

• 若链表为空表，新建节点为头节点
• • 若非空，新建节点添加至末尾

NodeType *Append(NodeType *head,int data){
  NodeType *p = NULL,*pr = head;
  p=(NodeType *)malloc(sizeof(NodeType));
  if(p == NULL){
    printf("Allocation error");
    exit(0);
  }
  if(head == NULL)head = p;
  else{
    while(pr->next!=NULL)
    {
      pr = pr->next;
    }
    pr->neat = p;
  }
  p->data=data;
  p->next=NULL;
  return head;
}
 

Delete

• 若为空列表，退出
• 若待删除的节点为头节点，head指向下一节点，并释放内存
• 若不是头节点，前一指针跳过当前指针指向下一指针，释放内存
• 若已搜索到链表的末尾，仍未找到，输出No Found

NodeType *DeleteNode(NodeType *head,int data)
{
  NodeType *p = head,*pr = head;
  if(head == NULL)
  {
    printf("Empty");
    return head;
  }
  while (data != p->data && p->next != NULL)
  {
    pr = p;
    p = p->next;
  }
  if (data == p->data)
  {
    if (p == head)
    {
      head = p->next;
    }
    else{
      pr->neat = p->next;
    }
    free(p);
  }
  else{
    printf("No Found");
  }
  return head;
}

Insert

• 若链表为空，新节点p作为头节点，head指向头节点
• 若非空，确定插入位置
  • 若在头节点前，新节点的指针指向原头节点，head指向新节点
  • 若在中间，新节点指针指向下一节点，前一节点指针指向新节点
  • 若在末尾，末指针指向新节点

NodeType *InsertNode(NodeType *head, int data)
{
  NodeType *p = head, *temp = NULL;
  p = (NodeType *)malloc(sizeof(NodeType));
  if (p == NULL)
  {
    printf("Allocation error");
    exit(0);
  }
  p->next = NULL;
  p->data =data;
  if (head ==NULL)
  {
    head = p;
  }
  else {
    while (pr->data < data && pr->next !=NULL)//condition
    {
      temp = pr;
      pr = pr->next;
    }
    if (pr->data >= data)
    {
      if (pr == head)
      {
        p->next = head;
        head  = p;
      }
      else
      {
        pr = temp;
        p->next = pr->next;
        pr->next = p;
      }
    }
    else{
      pr->next = p;
    }
  }
  return head;
}

stack

顺序储存

Initialise

typedef struct node{
  int data;
}NodeType;
typedef struct stack{
  NodeType data[N];
  int top;
}STACK;
int main()
{
  STACK stack;
  stack.top = 0;
  ···
}

push

void Push(STACK *stack,NodeType data)
{
  memcpy(&stack->data[stack->top],&data, sizeof(NodeType));
  stack->top = stack->top + 1;
}

pop

NOdeType Pop(STACK *stack)
{
  stack->top = stack->top - 1;
  return stack->data[stack->top];
}

链式储存

Initialize

typedef struct node{
  int data;
}NodeType;
typedef struct stack{
  NodeType data;
  struct stack *next;
}STACK;
int main()
{
  STACK *top = NULL;
  ···
}

push

STACK *Push (STACK *top,NodeType data)
{
  STACK *p;
  p = (STACK *)malloc(sizeof(STACK));
  p->data = data;
  p->next = top;
  top = p;
  return top;
}
STACK *Pop(STACK *top)
{
  STACK *p;
  if(top ==NULL)
  {
    return NULL;
  }
  else
  {
    p = top;
    top =top->next;
    free(p);
  }
  return top;
}

queue

顺序储存

Initialise

typedef struct queue
{
  int data[N];
  int front;
  int rear;
}QUEUE;

链式储存

Initialize

typedef struct queue{
  int data;
  struct queue *front;
  struct queue *rear;
}QUEUE;

循环队列

• rear不存数据
• 有数据进队时，rear = (rear +1) % QMAX
• 有数据进队时，front = (front +1) % QMAX
  • 取模的意义在于如果front达到队列的末尾（即QMAX），则通过取模操作 % QMAX 将 front 重置为 0，从而实现循环
• 队空：rear==front 队满：front == (rear + 1) % QMAX
• 保留了一个空rear,目的时防止front == rear产生假满

tree

Binary Tree

typedef struct BiTNode{
  int data;
  struct BiTNode * lchild;//左子树
  struct BiTNode * rchild;//右子树
}BI_TREE;

Concept

遍历

graph

连接

• 邻接矩阵
  • 初始化为inf一个较大的数，有连接为1，无连接为0
• 邻接表
  • 对每个顶点建立单向链表，记录与该点连接的节点
• DFS 、BFS

Files

fopen

• 不建议以读写方式打开文件，因为读写其实 共用 一个缓冲区，每次读写都会 改变文件位置指针 ，很容易写乱，破坏原来文件的内容，并且需要调用文件定位函数才能在读写之间转换

FILE *fp;
fp = fopen("···","w");

• 打开错误返回NULL

fclose

• 返回一个整型数，文件关闭成功返回0值

fgetc

fgetc(fp)//fp: FILE *

• 是从fp所指的文件中读取一个字符，并将位置指针指向下一个字符
• 读取成功返回字符，都到末尾返回EOF

fputc

fputc(int c,FILE *fp);//c只写入低字节

• 写入错误返回EOF,正确则返回字符c

feof

ch = fgetc(fp);
while (!=feof(fp))
{
  putchar(ch);
  ch = fgetc(fp);
}

• 返回0值, 当且仅当fp指向文件结束符时才返回真值

isprint

• 判断字符是否可输出
• 打印1-127ASCII码在不同的机器上可能显示的乱码有所不同，用记事本或写字板打开文件看到的也是乱码，而且与屏幕显示的结果可能并不完全一致。
• 这是因为在Windows文本编辑器中打开文件时,显示的那些拐来拐去、方块箭头等符号都不是可打印字符。
• 使用不同的文本编辑软件会有不同的处理，而且还会配合字符集等进行转码，甚至换用不同的字体时会有不同的显示结果

iscntrl

• 判断是否为控制字符

fgets

fgets(str,n,fp);

• 最多读入n-1个字符，在末尾添加\0，返回指针给str，读取失败返回NULL

ferror

• 检测文件错误

fputs

• 错误返回EOF,成功返回非负数
• 不会在末尾加上换行符

fscanf fprintf

fscanf(fp,"%d",&n);
fprintf(fp,"%d",n);

• 但输入时要将ASCII字符转换成二进制数，输出时要将二进制数转换为ASCII字符，耗时较多

fread fwrite

• 将fp指向的文件中读取数据块并存储到buffer指向的内存中 (读取buffer指向的内存写入fp指向的文件)，buffer为起始地址，count为最多读取 (写入) 的数据块数
• 返回读入 (写入) 的数据块数

fread (buffer, size, count, fp);
fwrite (buffer, size, count, fp);

Random Access

fseek

• 将fp的文件位置指针从fromwhere开始移动offset个字节，指示下一个要读取的数据的位置。
• offset是一个偏移量，它告诉文件位置指针要跳过多少个字节。offset为正时，向后移动，为负时，向前移动。ANSI C要求位移量offset是长整型数据(常量数据后要加L),这样当文件的长度大于64kb时不至于出问题
• fromwhere用于确定偏移量计算的起始位置，它的可能取值有3种:
  • SEEK_SET或0,代表文件开始处；
  • SEEK_CUR或1,代表文件当前位置;
  • SEEK_END或2,代 表文件结尾处。
  • 通过指定fromwhere和offset的值，可使位置指针移动到文件的任意位置，从而实现文件的随机读取。
• 如果函数fseekO调用成功，则返回0值，否则返回非0值。

rewind

• 重置位置指针到文件首字节rewind(fp)

ftell

• ftell(fp)返回当前读取位置(相对起始字节的偏移量L),调用失败返回-1L

fflush

• fflush(fp)强行将缓冲区数据写入物理设备，清空缓冲区

redirect

• 3个特别的文件指针常数：stdin stdout stderr
• 标准错误输出不能进行重定向
• fgets( str, size, stdin)与gets(str)相比限制了输入长度，更安全
• 命令行：
  • ezample.exe < file.in从file.in读入数据
  • example.exe > file.out输出到file.out

freopen