14.Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

1
2

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

个人解答：

时间复杂度：O(n^2)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

string longestCommonPrefix(vector<string>& strs) {
    string ans_string = "";
    int nums_string = size(strs);//字符串的数目
    int min_lenth_string = strs[0].length();
    for (int i = 1; i < nums_string; ++i) {
        if (strs[i].length() < min_lenth_string)min_lenth_string = strs[i].length();//找到最短的字符串的长度
    }
    for (int i = 0; i < min_lenth_string; ++i) {
        for (int j = 0; j < nums_string; ++j) {
            if (strs[0][i] != strs[j][i])return ans_string;
        }
        ans_string += strs[0][i];
    }
    return ans_string;
}

1
2
3
4
5
6
7
8
9
10
11

string longestCommonPerfix(vector<string> strs) {
    sort(begin(strs), end(strs));
    int size = strs.size();
    int length = min(strs[0].size(), strs[size-1].size());
    int index = 0;
    while (index < length) {
        if (strs[0][index] == strs[size-1][index]) ++index;
        else break;
    }
    return strs[0].substr(0, index);
}

13.Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

Example 1:

1
2
3

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

1
2
3

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

1
2
3

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

int romanToInt(string s) {
    int sum_int = 0;
    int pos = 0;
    bool is_double = true;//两个字符转换
    while (is_double) {
        pos = s.find("IV");
        if (pos != -1) {
            sum_int += 4;
            s.erase(pos, 2);
        }
        pos = s.find("IX");
        if (pos != -1) {
            sum_int += 9;
            s.erase(pos, 2);
        }
        pos = s.find("XL");
        if (pos != -1) {
            sum_int += 40;
            s.erase(pos, 2);
        }
        pos = s.find("XC");
        if (pos != -1) {
            sum_int += 90;
            s.erase(pos, 2);
        }
        pos = s.find("CD");
        if (pos != -1) {
            sum_int += 400;
            s.erase(pos, 2);
        }
        pos = s.find("CM");
        if (pos != -1) {
            sum_int += 900;
            s.erase(pos, 2);
        }
        is_double = false;
    }
    while (s != "") {
        pos = s.find("V");
        if (pos != -1) {
            sum_int += 5;
            s.erase(pos, 1);
        }
        pos = s.find("L");
        if (pos != -1) {
            sum_int += 50;
            s.erase(pos, 1);
        }
        pos = s.find("D");
        if (pos != -1) {
            sum_int += 500;
            s.erase(pos, 1);
        }
        pos = s.find("M");
        if (pos != -1) {
            sum_int += 1000;
            s.erase(pos, 1);
        }
        pos = s.find("I");
        if (pos != -1) {
            sum_int += 1;
            s.erase(pos, 1);
        }
        pos = s.find("X");
        if (pos != -1) {
            sum_int += 10;
            s.erase(pos, 1);
        }
        pos = s.find("C");
        if (pos != -1) {
            sum_int += 100;
            s.erase(pos, 1);
        }
    }
    return sum_int;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int romanToInt(string s) {
    unordered_map<char, int> romanToInt_table = {
        { 'I', 1 },
        { 'V', 5 },
        { 'X', 10 },
        { 'L', 50 },
        { 'C', 100 },
        { 'D', 500 },
        { 'M', 1000 },
    };
    int sum_int = 0;
    int s_size = s.length();
    for (int i = 0; i < s_size; ++i) {
        int value = romanToInt_table[s[i]];
        if (i < s_size - 1 && value < romanToInt_table[s[i + 1]]) {
            sum_int -= value;
        }
        else {
            sum_int += value;
        }
    }
    return sum_int;
}

9.Palindrome Number

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

Example 1:

1
2
3

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

1
2
3

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

bool isPalindrome(int x) {
    if(x < 0)return false;
    int count = 0;//x位数
	int temp = x;
	while (temp != 0) {
		temp /= 10;
		count++;
	}
	int first = pow(10, count-1);//选中首位时所需除数
	count /= 2;//只需遍历数字一半
	while (count--) {
		if (x / first != x % 10)return false;
		else {
			x %= first;
			x /= 10;
			first /= 100;
		}
	}
	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <string>
#include <iomanip>

using namespace std;


class Solution {

public:
    bool is_palindrome(int value) {
        if (value < 0) return false;
        if (value < 10) return true;
        int divdend = 1;
        while (divdend < value) {
            divdend *= 10;
        }
        divdend /= 10;
        while (value != 0) {
            int first = value / divdend;
            int last = value % 10;
            if (first != last) return false;
            value = (value % divdend) / 10;
            divdend /= 100;
        }
        return true;
    }
    bool is_palindrome_str(int value) {
        if (value < 0) return false;
        string s = to_string(value);
        string backup = s;
        reverse(begin(s), end(s));
        return s == backup;
    }
};

int main(int argc, char* argv[]) {
    int value;
    Solution sol;
    while (cin >> value) {
        cout << value << " is palindrome: " << boolalpha << sol.is_palindrome_str(value) << endl;
    }
    return EXIT_SUCCESS;
}

使用stl中list的list.remove()函数删除结构体结点时，会遇到==的运算符重载问题，解决方法如下：

• 结构体定义内容：

1
2
3
4
5
6

struct msg
{
  string studentNumber;
  string studentName;
  int gradeChinese, gradeMath, gradeEnglish;
}

• ==运算符重载实现

1
2
3
4
5
6
7
8
9
10

bool operator ==(const CInfoFile::msg& msg1, const CInfoFile::msg& msg2)
{
  bool flag = false;
  if (msg1.studentNumber == msg2.studentNumber 					              		  &&msg1.studentName==msg2.studentName
	  &&msg1.gradeChinese==msg2.gradeChinese
      &&msg1.gradeEnglish==msg2.gradeEnglish
      &&msg1.gradeMath==msg2.gradeMath)
  flag = true;
  return flag;
}

将String类型的sring1转换为CSting类型的cstring1

1
2
3
4
5

CStringA str;

str1 =string1;

cstring1 = str1.GetBuffer();

在MFC框架下将CInfoDlg界面挂载到主页面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Context.m_pNewViewClass = RUNTIME_CLASS(CInfoDlg);

Context.m_pCurrentFrame = this;

Context.m_pLastView = (CFormView *)m_spliter.GetPane(0, 1);

m_spliter.DeleteView(0, 1);

m_spliter.CreateView(0, 1, RUNTIME_CLASS(CInfoDlg), CSize(600, 0), &Context);

CInfoDlg *pNewView = (CInfoDlg *)m_spliter.GetPane(0, 1);

m_spliter.RecalcLayout();

pNewView->OnInitialUpdate();

m_spliter.SetActivePane(0, 1);

struct定义

1
2
3
4
5

struct Linklist
{
	int data;
	Linklist *next;
}；

函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void deleteNode(LinkList *list)
{
    int value;//要删除的结点数据
    cin>>value;
    Linklist *t = list->next,*in = list;
    while(t != NULL)
    {
        Linklist *t = list ->next,* in = list;
        while(t != NULL)
        {
            int is = 1;//判断是否查找到对象
            if(t->date != age)is = 0;
            if(is == 1)
            {
                in ->next = t->next;
                delete(t);
                break;
            }
            t = t->next;
            in = in->next;
        }
        if(t == NULL)break;
    }
}

1
2
3
4
5
6

template<class T>
typedef struct NODE
{
	T data;
	struct NODE *next;
} LinkList;

这里的代码会报错，因为define和typedef不允许定义模糊的类型，如果要使用，一定要显式指明数据类型。

1
2
3
4
5
6
7

template<class T>
struct NODE
{
	T data;
	struct NODE *next;
};
typedef NODE<int> LinkList;

上面为正确的用法，并且对于typedef必须定义在模板结构的下面。

程序设计与C语言

计算机与编程语言

• 编程语言不是人与计算机交谈的语言，而是以计算机可理解方式对解决问题的步骤进行描述

• 不同算法可以影响计算机运算速度（如限定条件）

• 执行方式：

  • 解释：借助一个程序，此程序指导计算机进行操作运行“目的程序”（可以理解“目的程序”）
  • 编译：借助一个程序，此程序对目的程序进行翻译，来让计算机执行
  • 有的程序语言既可以编译执行也可以解释执行

C语言

• 程序框架

1
2
3
4
5
6

#include<stdio.h>

int main() {
    
    return 0;
}

• ""里面的内容叫做"字符串"，printf会把其中的内容原封不动地输出

• \n表示再输出的结果后面换一行

计算

变量

• 在按下回车键前，程序不会得到输入

• 定义变量

  1 2	int price = 0； // 类型 名字 赋值 初始值

• 变量是一个保存数据的地方，变量只有保存数据才能参与计算

• 变量定义的一般形式：<类型名称><变量名称>

• 变量名称（标识符）：只能由字母、数字、下划线组成。数字不可以出现在第一个位置。C语言关键字（保留字）不可作标识符。

• C语言保留字：

auto; break; case; char; const; continue; default; double; do; else; enum; extern; float; for; goto; if; int; long; register; return; short; signed; sizeof; static; struct; switch; typedef; union; unsigned; void; volatile; while; inline; restrict

• 变量在被使用之前应当初始化（被赋值）

1
2
3

// 初始化：<类型名称><变量名称>=<初始化>
int price = 0；
int price = 0，amount = 100；

• C语言是一种有类型的语言。且程序执行过程中变量类型不可改变。

• printf输出函数

  scanf输入函数：

  • 加&在变量名称前
  • 出现在scanf的格式字符串里面的东西是它一定要输出的东西（空格、回车、制表符均指空白字符）

• 固定不变的数是常数，直接写在程序里称为直接量。

• const为修饰符，在int之前，表示不变的属性，表示这变量的值一旦初始化无法修改（全大写）

数据类型

• 10和10.0不同

  10为整数 10.0为浮点数

• 两个整数的计算结果只能是整数（去尾法保留），整数与浮点数运算时整数将变为浮点数

表达式

• 一个表达式是一系列运算符和算子的组合，用来计算一个值。

  count = count + 1

• 运算符指进行运算的动作；算子指参与运算的值。

  +；-；sizes = 7

  %表示取两个数相除以后的余数

• 运算符优先级

1 + - 单目（只有一个算子）不变 自右向左 a*-b a*+b

2 * / %

3 + -

4 = 赋值 自右向左 a = b

• 断点：让程序运行过程中暂停

• total += 5；等价于 total = total + 5

• 两个运算符之间不留空格

• 符合赋值：+=、-=、*=、/=、%=

• total /= a + b 等价于total = total /（a + b）

• ++和–是单目运算符，且算子必须是变量（不能5++或++5），称作递增和递减，作用为为变量+1或-1，后缀a++代表a加1以前的值，前缀++a代表a加1以后的值。若a = 10则a++ = 10，++a = 11，a=11

• INC：递增

  DEC：递减

判断与循环

判断

• if常用框架

  1 2 3

  if(判断条件){ }

• if语句中条件的逻辑表达式若为true，则执行大括号中的语句，反之不执行

• ==相等；!=不相等 ；>大于； >=大于或等于；<小于；<=小于或等于

• 关系运算的结果成立为1，否则为0；

  1	printf("%d\n", (5 == 3))// 输出0

• 关系运算符优先级小于算术运算，大于赋值运算

• 判断是否相等关系运算低于其他关系运算

• a == b == c：0/1与c比较

• 以//开头的语句将程序分开进行注释，为人类读者提供解释信息，对程序无影响，或以/*到*/

• else：否则的话 else{}

• if()后不加;因为语句并没与结束

• if、else后若没有{}则只读其后一个语句

循环

• 计算机内最高能输入的整数为10位数

• while：当条件满足时，不断重复循环体内的语句。循环可能执行一次，也可能不执行

• do-while：进入循环时不检查，执行完一轮循环代码之后再判断循环条件

1
2
3
4
5

 do {

<循环体语句>

}while(<循环条件>)；// 注意分号

• for（初始条件；循环继续的条件（判断式）；循环每轮要进行的动作（累加器））

  1	for (count = 10; count > 0; count--)

• 对于一开始的count = 10，当count > 0时，重复做循环体，每一轮循环在做完循环体内语句后，使得count--

• 做求和的程序时，记录结果变量初始化为0，而做求积变量时，记录结果变量初始化为1

• 循环的控制变量i是选择从0开始还是从1开始是判断i < n还是判断i <= n，对循环的次数，循环结束后变量的值都有影响。

• for == while

• for(int i=1; i<=n; i++){fact *= i}

  先fact *= i后i++

• 固定次数 for

  必须执行一次 do-while

  其他情况 while

• 省略循环的条件表示循环总是满足的

进一步判断与运算

逻辑类型和运算

• #include<stdio.h> 可用bool，true，false

• 逻辑运算是对逻辑量进行的运算，结果只有0或1

• 逻辑量是关系运算或逻辑运算的结果

• 符号	逻辑关系	表达式	用法
  ！	逻辑非	!a	a true 则 !a false
  &&	逻辑与	a && b	a、b均true为true否则false
  ||	逻辑或	a || b	a、b均false为false否则true

• x∈(4, 6)等价于x > 4 && x < 6

• 判断字符 c是否为大/小写字母：c >= 'A' && c <= 'Z'

• 逻辑运算符优先级普遍低于比较运算符，单目运算符优先级高于双目运算符（!age < 20代表0/1与20比较）

  1. () 自左向右（结合性）
  2. ！ + - ++ – 自右向左（单目+或-）
  3. * / %
  4. + -
  5. < <= > >=
  6. == !=
  7. &&
  8. ||
  9. = += -= *= /= %= 自右向左（结合性）

• 逻辑运算自左向右进行，如果左边结果可以决定运算结果，就不会做右边的计算（短路）

  a == 6 && b == 1 a == 6 && b += 1

  对于&&：左边为false则右边不做；对于||：左边为true则不做右边

  不要把赋值，包括复合赋值组合进表达式

• 条件运算符 count = (count > 20) ? count - 10 : count+10

  表示

  1 2 3 4

  if(count > 20) count = count-10; else count = count+10;

  条件满足时的值和条件不满足时的值

• “表达式”主要在for中使用，赋予不同变量值

级联和嵌套的判断

• 若if条件判断后语句仍为if或if - else语句，则为嵌套if语句

• else总是与最近的if匹配（大括号存在时可能特殊），在if或else后面总是用{}

• 级联的if- else if

  1 2 3 4 5 6

  if(exp1) stl1; else if(exp2) stl2; else stl3；

多路分支

• switch - case

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  swich(控制表达式) { case 常量: break; case 常量: break; default: break; }

• 常量只能是整数型结果

  • int type（正确）
  • double type（错误）

• 常量可为常数，或常数计算表达式（编译知道结果）

• switch可视作跳转，若case后无break，则执行下一个case，case不会让语句停止

循环的例子

• 计算之前先保存原始的值，后面可能有用

• 可以用模拟较少的循环次数来推断很大次数的循环

• 随机数rand()，得到一个随机的整数函数

判断和循环常见的错误

if常见错误：

• 忘了{}

• if后面错加;

• 错误地使用==和=

• 令人困惑的else：

  • if和else之后加大括号
  • 大括号内语句缩进一个tab

循环控制

循环控制

• 循环中可用break跳出循环

• 循环中可用continue跳过循环这一轮剩下语句进入下一轮

多重循环

• 嵌套的循环：循环里面还是循环

• break和continue只能对它所在的那层循环做

• 接力break

• goto：goto xx(符号) -> xx(同上符号):

  1 2 3

  again: 语句; goto again;//again可以替换成其他的，这里不要求一定是again

循环应用

数组和函数

数组

• 数组是长度固定的数据结构，用来存放指定类型的数据，所有数据的类型都相同

• <类型>变量名称[元素类型];

  int grades [100]; double weight [20];

• 元素数量必须是整数；C99之前，元素数量必须是编译时刻确定的字面量

• 数组是一种容器：

  • 类型相同

  • 一旦创建，不可改变大小

  • 数组元素在内存中是连续依次排列的

    int a[10]: a[0], a[1], a[2], … a[9]（10个单元）

• 可以在赋值左边或右边

• 使用数组时放在[]中的数字叫下边或索引，下标从0开始计数

  a[100] →0~99

• 编译器不会检查数组是否越界，但运用到程序中可能会崩溃

• 长度为0的数组：int a[0]; 可以存在但无用

函数的定义和使用

• 函数是一块代码，接受0个或多个参数，做一件事情，并返回一个或零个值

• 函数头 {函数体}

  void + sum(int begin, int end)

  返回类型 函数名 参数表（类型+名字）

• 调用函数 函数名（参数值） （即使不给参数依然需要（ ）），若有参数则需要正确数量和顺序

• return 停止函数的执行，并返回一个值

  return；

  return 表达式；

• 没有返回值的函数：

  • void函数名（参数表）
  • 不能使用（无）return
  • 不能做返回值的赋值

函数的参数和变量

• 在看到sum(1, 10)，它需要知道sum()的样子以检查对sum()的使用是否正确（C的编译器自上而下分析代码）

• 函数头()；（函数声明（函数原型）可用来判断函数的调用是否正确）

  1 2 3

  int main() { }

  函数头()（编译器会再次检查调用是否正确）（实际函数头）

• 调用函数必须传递给它数量、类型正确的值

  字面量，变量，函数的返回值，计算结果

• 调用函数时给的值与参数的类型不匹配是C语言系统上最大的漏洞,编译器总是自己转换，但可能会产生错误 C++/java却避免了

• C语言在调用函数，永远只传值给函数

• 传值：每个函数有自己的变量空间，参数也位于这个独立的空间中，和其他函数没有关系（int main()后a和b与调用函数中a和b无关系）

• 过去称函数参数表中的参数为形式参数，调用函数时给的值叫实际参数。但现代不再适用。现代称前者为参数，后者为值。

• 定义在函数内部的变量就是本地变量。参数也是本地变量。

• 生存期：变量出现的时间与消亡的时间。

• 作用域：在代码的什么范围内可以访问这个变量（变量起作用）对于本地变量这两个问题的答案是{}（块）

• 本地变量定义在块内，可以是函数块内，也可以是语句块内。程序进入块之前，变量不存在，离开这个块，其中的变量就消失了。

• 块外面定义变量在块里面依然有效，反之无效

• 若块里面定义了和外面同名的变量则掩盖了外面的，但不能在一个块内定义同名变量

• 本地变量不会被默认初始化，参数在进入函数时被初始化了

• 传统C中，void f() -> 不代表无参数，表示f函数参数未知，当无参数时，最好写void f(void)

• C语言不允许函数嵌套定义

二维数组

• int a[3][5]3行5列矩阵

• a[i][j]表示一个int，是i行j列上的单元

• 二维数组的初始化

  • 列必须给出，行数可由编译器数
  • 每行一个{}，逗号分隔
  • 如果省略表示补零
  • 也可以用定位（C99only）

数组运算

数组运算

• 数组的集成初始化

  1	int a[] = { 2,4,6,7,1}

• 不需要给出数组大小，编译器替我们数

• 集成初始化的定位（C99only）

  1	int a[10] = { [0] = 2, [2] = 3, 6 };

  • 用[n]在初始化数据中给出定位
  • 没有定位的数据接在前面的位置后面
  • 其他位置补0
  • 特别适合初始数据稀疏的数组

• sizeof：给出整个数组所占据的内容的大小，单位是字节

• sizeof(a) / sizeof(a[0])为数组元素个数

• 要把一个数组所有元素交给另一个数组，必须采用遍历

• 遍历数组作为函数参数时：

  • 不能在[]中给出数组大小
  • 不能利用sizeof来计算数组元素个数

搜索

• 在一个数组中找到某个数的位置（确认是否存在）

• 基本方法：遍历

• 二分搜索

指针与字符串

指针

• sizeof：运算符，给出某个类型或变量在内存中所占据的字节数sizeof(int)；sizeof(i)

• &：运算符，获得变量的地址，它的操作必须是变量

• 地址的大小是否与int相同取决于编译器

• 指针：就是保存地址的变量 int *p=&i

  int* p, q和int *p, q都代表p为指针，q为int

• 普通变量的值是实际的值；指针变量的值是具有实际值的变量的地址

• void f(int *p)；在被调用时得到了某个变量的地址，在函数里面可以通过这个指针访问外面这个i

• *是单目运算符，用来访问指针的值所表示的地址上的变量，可以做左值也可以做右值

• 函数参数表中的数组实际上是指针，sizeof(a) == sizeof(int*)，但是可以用数组的运算符[]进行计算

• 参数表中以下四种函数原型是等价的：

  • int sum(int *arr, int n)
  • int sum(int *, int)
  • int sum(int arr[], int n)
  • int sum(int[ ], int)

• 数组变量是特殊的指针，数组变量本身表达地址，（int a[10]; int *p = a;无需用&取地址）

• 但是数组的单元表达的是变量，需要用&取地址，a == &a[0]

• []运算符可以对数组做，也可以对指针做：p[0]等价于a[0]

• *可以对指针做，也可以对数组做

• 数组变量是const的指针，所以不能被赋值（int a[ ] = 等价于int *const a =）

字符类型

• char是一种整数，也是一种特殊的类型字符。

• 用单引号表示的字符字面量：'a'，'1'，''也是一个字符，printf和scanf里用%c来输出输入字符。

• 大小写转换：'a' - 'A'得到a和A在ASCII上的距离，a + 'a' - 'A'可以将大写字母变为小写字母，而a + 'A' - 'a'可以将小写字母变为大写字母

• 逃逸字符：用来表达无法印出来的控制字符或特殊字符，它由一个反斜杠\开头，后面跟上另一个字符，这两个字符合起来，组成一个字符。

• \b：回退一格

  \t：到下一个表格位

  \n：换行

  \r：回车

  \"：双引号

  \'：单引号

  \\：反斜杠本身

字符串

• 字符串是以\0结尾的一串字符

• 0或\0相同，但和'0'不同，0标志字符串的结束，但它不是字符串的一部分，计算字符串长度的时候不包括这个0

• 字符串以数组的形式存在，以数组或指针的形式访问，更多以指针形式

• string.h里有很多处理字符串的函数

• 字符串变量：char *str = "Hello"; char word[] = "Hello"; char line[10] = "Hello"

• 字符串常量："Hello"，会被编译器编程一个字符数组放在某处，这个数组的长度是6（结尾还有表示结束的0）

• 两个相邻的字符串常量会被自动连接起来

• C语言的字符串是以字符数组的形态存在的，不能用运算符对字符串做运算，通过数组的方式可以遍历字符串，唯一特殊的地方是字符串字面量可以用来初始化字符数组

• 如果要构造一个字符串->数组；

  如果要处理一个字符串->指针

• 字符串可以表达为char*的形式，char*不一定是字符串，只有它所指的字符数组有结尾的0；才能说它所指的是字符串

字符串的计算

• 并没有产生新的字符串，只是让指针s指向了t所指的字符串，对s的任何操作就是对t做的

  1 2 3

  char *t = "title"; char *s; s = t;

• scanf(“%7s”, string)；在%和s之间的数字表示最多允许读入的字符的数量，这个数字应该比数组的长度小

• string.h:

  • strlen：返回s的字符串长度（不包括结尾的\0）
  • strcmp：比较两个字符串，返回：0：s1 == s2；正差值：s1 > s2；负差值：s1 < s2
  • strcpy：把第二个参数的字符串拷贝到第一个空间；restrict表明两个字符串不重叠（C99），返回第一个参数
  • strcat：把第二个参数的字符串接到第一个参数的后面去接成一个长的字符串
  • strchr：从字符串左边找字符；strrchr：从字符串右边找字符。返回NULL表示没有找到。

指针与字符串（进阶）

指针的使用

• 比如：交换两个变量的值

• 函数返回多个值，某些值就只能通过指针返回，传入的参数实际上是需要保存带回的结果的变量

• 函数返回应用的状态，结果通过指针返回

• 常见错误：定义了指针变量，还没有指向任何变量，就开始使用指针

• 函数参数表中的数组实际上是指针，sizeof(a)== sizeof(int*)，但是可以用数组的运算符[]进行计算

• 数组变量是特殊的指针，数组变量本身表达地址，（int a[10];int *p = a;）无需用&取地址）

• []运算符可以对数组做，也可以对指针做：p[0]等价于a[0] ，*可以对指针做，也可以对数组做

• 数组变量是const的指针，所以不能被赋值（int a[]=等价于int *const a=）

• 指针是const：不能指向其他变量（声明时*在const前）

  指针所指是const：不能通过指针修改变量（声明时*在const后）

  const数组：数组每个单元都是const int，必须通过初始化赋值

指针运算

• 指针加1表示指针指向下一个变量（地址加sizeof(指针指向类型)）

• 如果指针不是指向一片连续分布空间（如数组），“加1”运算毫无意义

• 指针计算：加减整数（+，+=，-，-=）；递增递减（++, –）；两个指针相减（结果为地址差值/sizeof(指针指向类型)）

• *p++：取出p所指的数据，再将p指向下一位置，++的优先级高于*，常用于数组类的连续空间操作，在某些CPU上可以直接被翻译成汇编指令

• 指针比较：比较在内存中的地址，数组中单元的地址递增排列

• 0地址：用NULL表示，不代表数值0

• 所有指针大小相同，指向不同类型指针无法赋值

• void*：不知道指向什么东西的指针，计算时与char*相同（但不相通）

• 指针的类型转换：int *p = &i；void *q = (void*)p（p所指变量类型为int，但从q看所指变量类型未知）

• 指针的用处：

  • 需要传入较大的数据作参数
  • 传入数组后对数组操作
  • 函数返回不止一个结果
  • 需要用函数修改不止一个变量
  • 动态申请的内存

• 动态内存分配：malloc函数（<stdlib.h>），申请以字节为单位的空间，返回的类型是

  void* ( (int*)malloc(n*sizeof(int)))结束后free()；申请失败则返回0（NULL）

• free()归还申请的空间给“系统”，只能还申请来的空间的首地址

• 申请了没free，长时间运行内存逐渐下降

字符串操作

• putchar：向标准输出写一个字符，返回输出了几个字符（int），EOF表示写失败

• getchar：从标准输入读入一个字符，返回类型是int是为了返回EOF

• char **a ：a是指针，指向一个指向字符的指针

• char[ ][n] != char *a[ ]

结构类型

枚举

• 定义：用户定义的数据类型，用关键字enum来声明enum枚举类型名字{名字0，…，名字n}；

• 枚举类型名字未必真的使用，要用的是大括号里面的名字，因为他们就是常量符号，类型为int，值从0到n

• 枚举量可以作为值，枚举类型可以跟上enum作为类型，实际上是以整数做内部计算和外部输入输出

• 枚举最后可以加number来代表代表枚举个数，方便遍历

• 枚举类型很少当做类型使用，排比有意义的名字比const int好用，枚举比宏好，因为枚举有int类型

结构

• 定义：复合数据类型，包含多种类型，用一个变量表示

• 和本地变量一样，在函数内部声明的结构类型只能在函数内部使用

• p1和p2都是point里面有x和y的值

  1 2 3 4

  struct point{ int x; int y; }p1, p2;//（注意分号）

• p1和p2是一种无名结构，里面有x和y

  1 2 3 4

  struct{ int x; int y; }p1, p2;

• p1和p2都是point里面有x和y的值

  1 2 3 4 5 6

  struct{ int x; int y; }p1, p2; struct point p1,p2;

• 结构用.运算符和名字访问其成员p1.x

• 对于整个结构，可以做赋值、取地址，也可以传值给函数参数

  p1 = p2等价于p1.x=p2.x，p1.y = p2.y（数组不可以）

  p1 = (struct point){5,10}等价于p1.x = 5，p1.y = 10

• 和数组不同，结构变量的名字并不是结构变量的地址，必须用&运算符

• 整个结构可以作为参数的值传入函数，在函数内新建一个结构变量，并复制调用者的结构的值，也可以返回一个结构（与数组完全不同）

• 用->表示指针所指的结构变量中的成员 p->y = 10

• 结构数组：

  struct date arr[100];

​ struct date arr[] = { { 4,52005 }, { 2,4,2005 } };

• 结构中的变量也可以是结构

联合

• 自定义数据类型：typedef，声明一个已有的数据类型的新名字typedef int Length;使得Length成为int的别名Length a；等价于int a；

  1 2 3 4 5

  typedef struct point{ int x, y }Date;//表示Date可代替struct point

• 定义：union，所有成员共享一个空间，同一时间只有一个成员是有效的，union的大小是其最大的成员

程序结构

全局变量

• 定义：定义在函数外面的变量，具有全局的生存期和作用域，与任何函数无关，在任何函数内部都可以使用它们。

• 没有做初始化的全局变量会得到0值，指针会得到NULL，只能用编译时刻确定值来初始化全局变量，它们的初始化发生在main函数之前

• 在本地变量定义时加上static修饰就成为静态本地变量，当函数离开时，静态本地变量会继续存在并保存其值，静态本地变量的初始化只会在第一次进入这个函数时做，以后进入函数会保持上次离开时的值

• 静态本地变量实际是全局变量，它们位于相同的内存区域，它具有全局的生存期，函数内的局部作用域，static此处意为局部作用域（本地可访问）

• 返回本地变量的指针是危险的，返回全局变量或静态本地变量的指针是安全的，返回在函数内malloc的内存是安全的，但容易造成问题，最好的做法是返回传入的指针

• 不要使用全局变量在函数间传递参数和结果，尽量避免使用全局变量，使用全局变量和静态本地变量的函数是线程不安全的

编译预处理和宏

• #开头的是编译预处理指令，他们不是C的成分，但C语言离不开叫他们，#define用来定义一个宏

• #define <名字><值> 注意结尾没有分号，名字必须是一个单词，值可以是各种东西，在C语言编译器编译之前，编译预处理程序（cpp）会把程序中的名字换成值

• 若宏中出现其他宏的名字，也是会被替换的，若一个宏的值超过一行，最后一行之前的行末需要加\，宏值后出现的注释不会被当做宏值的一部分

• 没有值的宏：#define_DEBUG，条件编译，后面有其他的编译预处理指令来检查这个宏是否已经被定义过了

• 预定义的宏：__LINE__（源代码文件行号）；__FILE__（文件名）；__DATE__（编译日期）；__TIME__（编译时间）；__STDC__（如果编译器遵循ANSI C，其值为1，否则未定义 ）

• 像函数的宏：#define cude(x) ((x)*(x)*(x))，宏可以带参数，一切都要带括号，整个值要括号，参数出现的每个地方都要括号，也可以带多个参数，也可以组合（嵌套）使用其他宏

• 部分宏会被inline函数替代

大程序文件

• 一个.c文件是一个编译单元，编译器每次只处理一个编译单元

• 把函数原型放进一个头文件当中（以.h结尾）中，在需要调用这个函数的源代码文件（.c文件）中#include这个头文件，就能让编译器在编译的时候知道函数的原型

• #include把那个文件的全部文本内容原封不动地插入到它所在的地方

• #include“ ” 要求编译器首先在当前目录（.c所在的目录）寻找这个文件，如果没有，到编译器指定的目录去找。

• #include< >让编译器只在指定的目录去找

• 环境变量和编译器命令行参也可以指定寻找头文件的目录

• #include不是用来引入库的

• 在使用和定义这个函数的地方都应该#include这个头文件

• 一般的做法任何.c都有对应的同名.h，把所有对外公布的函数的原型和全局变量的声明都放进去

• 在函数前面加上static使得它成为只能在所在的编译单元中使用的函数

• 在全局变量前面加上static就使得它成为只能在所在的编译单元中被使用的全局变量

• int i; extern int i; 是变量的声明

• 声明是不产生代码的东西：函数原型；变量声明；结构声明；宏声明；枚举声明；类型声明；inline函数，定义是产生代码的东西：函数；全局变量

• 只有声明可以放在头文件当中否则会造成一个项目中多个编译单元有重名的实体，某些编译器允许几个编译单元中存在同名的函数或者用weak修饰符来强调这种存在。

• 同一个编译单元里同名的结构不能被重复声明，如果你的头文件里有结构的声明，很难这个头文件不会在一个编译单元里被#include多次

• 标准头文件结构：

  1 2 3

  #ifndef __LIST_HEAD__ #define __LIST_HEAD__ #endif

  #pragmam once也能起到相同作用，但不是所有编译器都支持

文件

文件

• 格式化的输出：%[flags][width][.prec][hlL]type

  • flag
    • - 左对齐
    • +：在前面放+或-
    • (space)：正数留空
    • 0：0填充
  • width或prec：
    • number：最小字符数
    • *：下一个参数是字符数
    • .number：小数点后位数
    • .*：下一个参数是小数点后位数
  • hlL（类型修饰）：
    • hh：单个字节
    • h：short
    • l：long
    • ll：long long
    • L：long double

• %n：读入或写入的个数

• 格式化输入：%[flag]type

• flag：

  • *：跳过
  • 数字：最大字符数；
  • hh：char；h；l；ll；L

• type：[…]：所允许的字符

• printf和scanf的返回值是读入和输出的返回值

• 用>和<做重定向，<指定输入，>指定输出

• 打开文件的标准代码

  1 2 3 4 5 6 7 8

  FILE* fp=fope(“file”,”r”); if(fp) { scanf(fp,...); fclose(fp); } else { }

• fopen：

  • r：打开只读
  • r+：打开读写，从文件头开始
  • w：打开只写，如果不存在则新建，如果存在则清空
  • w+：打开读写，如果不存在则新建，如果存在则清空
  • a：打开追加，如果不存在则新建，如果存在则从文件尾开始
  • ...x（…加x结尾）：只新建，如果文件已新建则不能打开

• 所有的文件最终都是二进制的，文本文件是用最简单的方法可以读写的文件，而二进制文件是需要专门的程序来读写的文件，文本文件的输入输出是格式化，可能经过转码

位运算

• 按位运算：

  • &按位的与
  • |按位的或
  • ~按位取反
  • ^按位的异或
  • <<左移；
  • >>右移

• &按位的与：二进制中若两个位对应均为1，则取&结果为1，否则为0，

  • 让某一位或某些位为0：x & 0xFE；
  • 取一个数中间的一段：x & 0xFF

• |按位的或：二进制中若两个位有1则|结果为1，否则为0

• ~按位取反：把二进制数各位0变为1,1变为0

• 按位异或^：若两个位相等，则结果为1，不相等则为0

• <<左移：i << j：i中所有的位向左移动j个位置，而右边填入0，所有小于int的类型，移位以int的方式来做，结果是int

  x <<= 1等价于x *= 2，x << n等价于x *= n * 2

• >>右移：i>>j：i中所有的位向右移动j个位置，而左边填入0，所有小于int的类型，移位以int的方式来做，结果是int，对于unsigned类型，左边填0，对于signed类型，左边填入原来的最高位（保持符号不变）

  x >>= 1等价于x /= 2，x>>n等价于x /= 2 * n

• 可以认为逻辑运算相当于把所以非0值变成1，然后做按位运算

• 位段：把一个int的若干位组合成一个结构

  1 2 3 4 5 6

  struct { unsigned int leading : 3; unsigned int FLAG1 : 1; unsigned int FLAG2 : 1; int trailing : 11; } ;

• 可以直接用位段的成员名称来访问，比移位、与、或还方便，编译器会安排其中位的排列，不具有可移植性，当所需的位超过一个int时会采用多个int