数据结构(0)--预备知识

0.引言

程序(Program) = 算法(Algorithms) + 数据结构(Data Structure)

数据结构需要使用程序语言来描述，比如C/C++

以下是C/C++的第一个程序

#include <stdio.h>           // 预处理指令
#include <stdlib.h>          // 将stdio.h和stdlib.h引入程序，stdio中包含标准输入输出函数 stdlib为标准库头文件，一些宏和一些函数如malloc()、system()等需要用到 在C++中为cstdio、cstdlib
int main()                  // main函数函数头
{                           // {...}为函数体
    printf("Hello World");  // 打印语句
    return 0;               // 函数返回0，0称为函数返回值
}
// 注释：单行注释使用"//",块注释使用"/* */",Java中文档注释使用"/** */"

#include <iostream>
using namespace std;        // 使用std这个命名空间，函数体中使用cout、cin就不需要写成std::cout、std::cin的格式了
int main()
{
    cout << "Hello World" <<endl;
    return 0;
}
//main(int argc,char *argv[])--带参数的main函数 argc代表命令行参数的个数，argv[0]存放的是命令，argv[i]存放的是命令行中的第i个参数(i>=1)eg:ping 192.168.1.1   argc=1;argv[0]="ping";argv[1]="192.168.1.1";

C/C++程序运行：源程序test.c(.cpp)-编译->二进制文件test.obj-连接->test.exe(或其他可执行文件)-运行->运行成功或失败

1.变量和数据类型

• 常量

常量是程序运行过程中值不能改变的量
(1)整型常量：如10000，0，-345
(2)实型常量：123.4，0.0，-9.79，12.34e3(12.34x10^3)
(3)字符常量：普通字符如’a’，’Z’，’3’，’?’及转义字符\n，\t等
(4)字符串常量：”hello”，”12346”
(5)符号常量：不占内存

#define PI 3.1415926

const float PI = 3.14159f;

• 变量

变量代表一个有名字的、具有特定属性的一个存储单元，用来存放变量的值，变量的值是可以改变的。变量必须先定义，后使用。
变量定义：

<数据类型> <变量名1>[,<变量名2>,···];

如int a; char c; double b; bool isE;等
变量名使用标识符来标识。用来对变量、符号常量名、函数、数组、类型等命名的有效字符徐磊统称为标识符。标识符由大小写字母、数字字符和下划线组成，且第一个字符不能为数字，还有用户定义的标识符不能和系统保留关键字同名。
在同一个作用域中不能有两个或两个以上相同的变量名
变量赋值和初始化
(1)定义后赋值

int x,y;
x = 8;
y = x;

(2)定义的同时赋值

int n = 1;
double d = 1.25;
char c = 'a';

(3)定义多个变量时单独赋一个

int n1, n2 = 4, n3;

(4)C++中

int n1(1), n2(4), n3;       //定义三个整型变量n1、n2、n3,且赋初值n1为1、n2为4

• 保留关键字

asm auto break case catch char class const continue default delete do double else enum extern float for friend goto if inline int long new operator private protected public register return short signed sizeof static struct switch template this throw try typedef union unisigned virtual void volatile while

• 数据类型

使用sizeof()获取数据类型字宽

• 运算符和表达式

• 算术运算符：四则运算(+ 、-、*、/),求余(%),自增(++),自减(--)
• 关系运算符：大等小(>、>=、==、<、<=),不等(!=)
• 逻辑运算符：与或非(&&、||、!)
• 位运算符：按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(<<)、右移(>>)
• 赋值运算符：赋值(=),扩展(+=、-=、/=、*=、%=···)
• 条件运算符：(? :)
• 逗号运算符：(,)
• 指针运算符：(*、&)
• 求字节数运算符：(sizeof())
• 强制类型转换运算符：((<type>))
• 成员运算符：(.、->)
• 下标运算符：([])
• 其他：函数调用(())

注意运算符的优先级，运算顺序

• 运算符表达式–用算术运算符和括号将运算对象连接起来的，符合C/C++语法规则的式子

• 语句

• 控制语句 –控制功能语句
  • 条件语句 if()···else···
  • 循环语句 for()···、while()···、do···while();
  • 结束本次循环 continue
  • 终止执行switch语句或循环语句 break
  • 多分支选择语句 switch()
  • 函数返回语句 return
  • 转向语句 goto
• 函数调用语句 –函数调用加分号结尾
  • printf("1");
  • max(1,2);
• 表达式语句 –表达式加分号结尾
  • 赋值语句 a=3;
  • i++;
• 空语句 ; 只有一个分号，什么也不做
• 复合语句 –用{}把语句和声明括起来，又称语句块

函数体包含声明部分和执行部分，执行部分是由语句组成的，语句的作用是向计算机系统发出操作指令，要求执行相应的操作。

2.输入输出

input：

• scanf("%c",&s);
• a = getchar();
• gets();
• std::cin >> a;

output:

• printf("%s",s);
• putchar(a);
• puts();
• std::cout << a <<endl;

格式控制

• %d、%i–十进制整型
• %o–八进制整型
• %x、%X–十六进制数
• %u–无符号型
• %c–字符
• %s–字符串
• %f–6位小数单双精度
• %e、%E–指数形式的实型

• %g、%G–自动选择%f %e

• %l–长整型，加在d、o、x、u前

• %-m.nf–向左靠齐，m个宽度，n为小数的实数

3.三大基本结构

顺序结构

在顺序结构中，各语句是自上而下的顺序执行的，执行完上一个语句就自动执行下一个语句，是无条件的，不需要作任何判断。是最简单的程序结构。

选择(分支)结构

• 根据某个条件是否满足来决定是否执行指定的操作

if语句 选择结构

if(表达式) 语句1
[else 语句2]
/*
此处的表达式主要为：
关系表达式 （a>b）==c
逻辑表达式  !a&&(b||c)
条件表达式  a>b ? (max=a) : (max=b)
*/

注意if语句的嵌套

• 满足条件后从给定的两种或多种操作选择其一

switch语句 多分支选择结构

switch(表达式){
    case 常量1:语句1 break;
    case 常量2:语句2 break;
        ·
        ·
        ·
    case 常量n:语句n break;
    default:语句n+1
}
/*
·表达式的值为整数类型
·表达式中的值满足下面的常量i,则case 常量i,执行语句i
·遇到break跳出switch，一直没有break则一直按顺序往下执行语句
·没有找到常量i,则执行default后的语句，如果没有default也没找到常量i则不执行任何语句
·每个常量必须不同
·case只起标记作用
·多个case标号可以共用一组执行语句
*/

循环结构

• while语句

while(表达式)
{
    循环体
}
/* 先判断表达式，后执行循环语句 */

• do···while语句

do
{
    循环体
}while(表达式);
/* 先无条件执行循环体，然后判断循环条件是否成立。因此最少需要执行循环体一次。 */

• for语句

for(循环变量赋初值;循环条件;循环变量增值){
    循环体
}
/* 表达式可以省，但是分号要保留 */

• 循环的嵌套

注意分析即可

• 改变循环执行状态

continue：结束本次循环
break:终止整个循环

4.数组

数组是相同类型的元素的有序集合。每个元素在内存中占用相同大小的内存单元，这些内存单元在内存空间中都是连续存放的。

一维数组

• 定义
  类型 数组名[常量表达式]; 比如int a[10];这是一个含有a[0]到a[9]十个元素的名字为a的数组

• 引用
  数组名[下标]

• 初始化

  • 在定义时对所有数组元素初始化 int a[5] = {0,1,2,3,4};
  • 定义时部分元素初始化，其余为0 int a[5] = {0,1};
  • 全部赋值为0 int a[5] = {0,0,0,0,0};或int a[5] = {0};
  • 对全部袁术赋初值时，数据个数已定了，故可省略 int a[] = {0,1,2,3,4};

二维数组

• 定义

类型 数组名[常量表达式1][常量表达式2];比如float a[3][4],b[5][10];,C中存放数组是按行优先的

• 引用
  数组名[下标][下标]

• 初始化
  • 分行赋值

    int a[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    

  • 不分行

    int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
    

  • 部分元素赋值

    int a[3][4] = {{1},{5},{9}};
    

  • 全部元素赋值，只能省前面维度的数值

    int a[][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
    

  • 分行赋值省前面维度

    int a[][4] = {{0,0,3},{},{0,10}};
    

5.字符串

字符数组

string类

字符串处理函数

6.函数

7.递归

8.指针和引用

7.结构体