程序设计语言概述

编译程序与解释程序

编译与解释区别

编译器与解释器

多种程序设计语言特点

1. Fortran语言(科学计算，执行效率高)
2. Pasca语言(为教学而开发的，表达能力强，Delph)
3. C语言(指针操作能力强，高效)
4. Lisp语言(函数式程序语言，符号处理，人工智能)
5. C++语言(面向对象，高效)
6. Java语言(面向对象，中间代码，跨平台)
7. C#语言(面向对象，中间代码，Ne)
8. Prolog语言(逻辑推理，简洁性，表达能力，数据库和专家系统)
9. Python语言(解释型，面向对象，胶水语言)

程序设计语言的基本成分

常见数据类型

• 数字数据类型
• 布尔类型
• 字符类型
• 枚举类型

• 指针类型
  程序控制结构

  顺序结构、选择结构、循环结构

函数调用方式

传值与传址

函数调用
传值调用：

    void swap(int x, int y)
    {
        int t;
        t = x;
        x = y;
        y = t;
        printf("%d %d,", x, y);
    }
    main()
    {
        int a = 3, b = 4;
        swap(a, b);
        printf("%d %d", x, y);
    }
    // 输出结果：4 3, 3 4

传址调用：

    void swap(int *x, int *y)
    {
        int *t;
        *t = *x;
        *x = *y;
        *y = *t;
        printf("%d %d,", *x, *y);
    }
    main()
    {
        int a = 3, b = 4;
        swap(&a, &b);
        printf("%d %d", x, y);
    }
    // 输出结果：4 3, 4 3

编译程序基本原理

编译过程概述

词法分析

词法分析：从左到右逐个扫描源程序中的字符，识别其中如关键字(或保留字)、标识符、常数、运算符以及分隔符(标点符号和括号)等

语法分析

语法分析：根据语法规则将单词符号分解成各类语法单位，并分析源程序是否存在语法上的错误。包括:语言结构出错、if···end if不匹配，缺少分号、括号不匹配、表达式缺少操作数等

• 自顶向下（或自上而下）分析法

• 自底向上语法分析法（移进-归约分析法）

  语义分析

  语义分析：进行类型分析和检查，主要检测源程序是否存在静态语义错误。包括：运算符和运算类型不符合，如取余时用浮点数。

错误管理

动态错误

• 发生在程序运行时
• 也叫动态语义错误
• 陷入死循环、变量取零时做除数、引用数组元素下标越界等错误
  静态错误
• 编译时所发现的程序错误
• 分为语法错误和静态语义错误
• 语法错误包含：单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误
• 静态语义分析：运算符与运算对象类型不合法等错误

文法

文法定义

一个形式文法是一个有序四元组G=(V,T,S,P)，其中：

1) V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符
2) T：终结符。是语言的组成部分，是最终结果。V∩T=ø
3) S：起始符。是语言的开始符号
4) P：产生式。用终结符替代非终结符的规则。形如α→β

正则闭包:A⁺=A¹∪A²∪A³∪…∪Aⁿ∪···（也就是所有幂的组合）。
闭包:A^*=A⁰∪A⁺（在正则闭包的基础上，加上A⁰={ε}）
例如a^*={a,aa,a,···,ε}，而(ab)^*={ab,abab,ababab,···,ε}

语法推导树

正规式与正规集

正规式

正规式是描述程序语言单词的表达式，对于字母∑，其上的正规式及其表示的正规集可以递归定义如下

①ε是一个正规式，它表示集合L(ε)={ε}
②若a是Σ上的字符，则a是一个正则式，它所表示的正规L(a)={a}
③若正规式r和s分别表示正规集L(r)=L(s)，则

(a)r|s是正规式，表示集合L)UL(s)
(b)r·s是正规式，表示集合L(r儿L(s);
(c)r^*是正规式，表示集合(L(r))^*;
(d)(r)是正规式，表示集合L(r)

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。由此可见，正规式要么为空，要么由字母、或、连接、闭包运算符组成。其中闭包运算符“^*”具有最高的优先级，连接运算具有次高优先级，或运算符“|”具有最低优先级

有限自动机

后缀表达式

线性结构

顺序表与链表

线性表

顺序存储方式

数组的内存是连续分配的并且是静态分配的，即在使用数组之前需要分配固定大小的空间。

链表(inked-list)存储方式

链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的所有元素串起来。

尾结点：最后一个有效结点
首结点：第一个有效结点
头结点：第一个有效结点之前的那个结点，存放链表首地址
头指针：指向头结点的指针变量
尾指针：指向尾结点的指针变量

特点：
①n个结点离散分布，彼此通过指针相联系
②除头结点和尾结点外，每个结点只有一个前驱结点和一个后续结点。头结点没有前驱结点，尾结点没有后继结点
③头结点并不存放有效数据，只存放链表首地址。其头结点的数据类型和首结点类型一样
④加头结点的目的是方便对链表的操作，比如在链表头部进行结点的删除、插入

链表的每个结点实际上是一个结构体变量,它有若干成员组成,包括数据部分和指针变量。

链表

单链表

设单链表结点类型定义为：

typede struct node{
    int data;  /*数据域*/
    struct node *link;  /*指针域*/
}NODE,*LinkList;

• 在单链表p所指结点后插入新元素结点（s所指结点）
  
  ①s>ink=p->link;
  ②pnk=s;
• 在单链表中删除p所指结点的后继结点
  
  ①q=p->link;
  ②p->link=p->link->link;
  ③free(q);
• 在单链表中删除p所指结点
  
  ①p->data=p->link->data;
  ②q=p->link;
  ③p-link=p->link->link
  ④free(a);

双链表

• 双向链表插入q所指向的结点
  
  ①q->front=p;
  ②q->next=p->next;
  ③p->next->front=q;
  ④p->next=q;
• 双向链表删除结点p所指向的结点
  
  ①p->front->next=p->next;
  ②p->next->front=p->front;
  ③free(p);

顺序存储与链式存储对比

队列与栈

习题：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。

abc acb bac bca cba

循环队列

• 队空条件：head=tall
• 队满条件：(tail+1)%size=head
• 队列长度：(tail-head+size)%size
  循环队列（通过整数取余运算实现）

串

串的定义

串是仅由字符构成的有限序列，是一种线性表。一般记为S="a₁a₂a₃···a_n"，其中，S是串名，单引号括起来的字符序列是串值

基本概念

(1) 空串与空格串

• 空串：长度为零，不包含任何字符。
• 空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。

(2) 子串与子序列

• 子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
• 子序列：一个串的“子序列”(subsequence)是将这个串中的一些字符提取出来得到一个新串并且不改变它们的相对位置关系。

(3) 串比较与串相等

• 串比较：两个串比较大小时以字符的ASCII码值(或其他字符编码集合)作为依据。实质上，比较操作从两个的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
• 串相等：指两个串长度相等且对应序号的字符也相同。

基本操作

(1)赋值操作 StrAssign(s,t)

• 将串s的值赋给串t。
  (2)连接操作 Concat(s,t)
• 将串接续在串s的尾部，形成一个新的串。
  (3)求串长 StrLength(s)
• 返回串s的长度。
  (4)串比较 StrCompare(s,t)
• 比较两个串的大小。返回值1、0和1分别表示s<t、s=t和s>t三种情况。
  (5)求子串 SubString(s,star,len)
• 返回串S中从 start开始的、长度为len的字符序列。

存储

(1)顺序存储
(2)链式存储

模式匹配

模式匹配：子串的定位操作通常称为串的模式匹配。(串也称为模式串)

朴素的模式匹配算法(布鲁特福斯算法)

其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对字符迸行后续的比较，否则从主串第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次与主串中一个连续的字符序列相等时为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。

改进的模式匹配算法(KMP算法)

其改进之处在于每当匹配过程中出现相比较的字符不相等时，不需要回退到主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。
在KMP算法中，依据模式串的next函数值实现子串的滑动。若令next[j]=k，则next[j]表示当模式串中的p与主串中相应字符不相等时，令模式串的p_next[j]与主串的相应字符进行比较。（j=next[j]）

next函数的定义如下：

数组与矩阵

数组

矩阵

稀疏矩阵	示意图	要点
上三角矩阵		在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为：(2n-i+1)×i/2+j
下三角矩阵		在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为：(i+1)×i/2+j
对角矩阵		矩阵中的非零元素都集中在以主对角线为中心的带状区域中。

树

树与二叉树的特性

数转二叉树

常见二叉树

二叉树的重要特性

1. 在二叉树的第i层上最多有2^i-1个结点(i≥1)；
2. 深度为k的二叉树最多有2^k-1个结点(k≥1)；
3. 对任何一棵二叉树，如果其叶子结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

4. 如果对一棵有n个结点的完全二又树的结点按层序编号(从第1层到「Log2n」+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：

   如果i=1，则结点无父结点，是二叉树的根；如果i>1，则父结点是「i2」；
   如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；
   如果2i+1>n，则结点i无右子叶点，否则，其右子结点是结点2i+1。

二叉树的遍历

• 前序遍历：根-左-右
• 中序遍历：左-根-右
• 后序遍历：左-右-根

• 层次遍历：按层次从左至右遍历
  
  图中的前序遍历、中序遍历、后序遍历、层次遍历

  前序：1-2-4-5-7-8-3-6
  中序：4-2-7-8-5-1-3-6
  后序：4-8-7-5-2-6-3-1
  层次：1-2-3-4-5-6-7-8

二叉排序树

也叫查找二叉树，二叉排序树要么是空二叉树，要么具有如下特点：

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
• 二叉排序树的左右子树也要求都是二叉排序树；

如图为一个二叉排序树

时间复杂度：最优时，即为完全二叉树或者满二叉树的时候，时间复杂度为O((log₂n)+1)；最差的时候（但分支结构），时间复杂度为O(n)

最优二叉树（哈夫曼树）

路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常记作 “WPL”
如图中所示的这颗树的带权路径长度为：

WPL = 7 1 + 5 2 + 2 3 + 4 3

哈夫曼树：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

例子：假设一个文本文件TFile中只包含7个字符{A，B，C，D，E，F，G}，这7个字符在文本中出现的次数为{5，24，7，17，34，5，13}，利用哈夫曼树可以为文件TFile构造出符合前缀编码要求的不等长编码

图

图的定义与存储

图的基本概念

• 完全图

  在无向图中，若每对顶点之间都有一条边相连,则称该图为完全图(complete graph)。
  在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。

• 连通图

  连通图：指任意两个顶点之间都有一个路径相连。

图的存储-邻接矩阵
用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素R定义为：

图的存储-邻接表
首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。

图的遍历

邻接表的方式

拓扑排序

我们把用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称AOV网络。

上图的拓朴序列有:02143567,01243657,02143657,01243567

最小生成树与最短路径问题（软考涉及少）

最小生成树：对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。
构成生成树的准则有三条：

1. 必须只使用该网络中的边来构造最小生成树。
2. 必须使用且仅使用n-1条边来连接网络中的n个顶点
3. 不能使用产生回路的边。

• 克鲁斯卡尔算法：在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。
• 普里姆算法：普里姆算法是以其中某一顶点为起点，逐步寻找各个顶点上最小权值的边来构建最小生成树。其中运用到了回溯，贪心的思想。

最短路径
一批货物要从城市s发送到城市t，线条上的数字代表通过这条路的费用(单位为万元)。那么，运送这批货物，至少需要花费多少元？

• 迪杰斯拉算法：是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

都用到了贪心算法策略