数据结构2

数据结构2 线性表

线性表

线性表的抽象类中，少了构造函数（对应create函数），多了析构函数。我们将create函数交给了具体类的构造函数。那为什么要加析构函数呢？这里的虚析构函数是为了防止派生类中出现内存泄漏。计算机看到抽象类的析构函数时，才回去找到派生类中的析构函数，防止派生类出现内存泄漏。
virtual ~list(){};

什么是顺序实现？

线性表中结点存放在存储器上一块连续的空间中，即一个数组。且这个数组一定是动态数组。借助存储空间的连续性，结点可以按照其逻辑顺序依次存放。顺序表类的定义同样不太常见，是一个类模板的继承。在实现时，我们需要注意顺序存储的容量问题，有2种解决方法，要么不执行操作（这不好吧），要么让用户觉得这是一个无限的空间，即程序员需要增设一个扩大空间的函数。
但顺序表同样存在一个问题，当执行insert操作时，最坏时间复杂度达到了O(N)，remove操作也同样如此，所以当执行插入删除操作次数较少时，适合用顺序实现（静态的）

什么是链接实现

每个结点存放在独立的存储空间中，结点间的逻辑关系依靠存储单元中附加的指针给出。通常用链表实现，具体有单链表、双链表和循环链表

单链表

注意：struct默认成员是public，而class默认成员是private

所以，在整个单链表类中，我们将Node类定为private，但Node类内部成员均为public，这是因为我们需要在Node结构体外调用各种数据成员，但是从外部来看，class外的成员无需知晓内部实现，更无需调用Node结构体中成员变量。

执行insert操作时，可以调用一个私有的move函数，返回指向相应结点的指针。同样在remove操作时，也是调用move函数定位。

双链表 循环链表

对于：有经常要找前驱的操作

循环链表又分为单循环链表、双循环链表，单循环链表很适合解决约瑟夫环问题

STL

STL（标准模板库）：C++中数据结构的实现，这些数据结构称为集合或容器

• vector: 线性表的顺序实现
  特有操作：[]的重载，按下标访问元素
• list: 线性表的双链表实现
  特有操作：表头的插入和删除

迭代器操作

迭代器：指向容器中元素的抽象指针
迭代器都被定义为对应容器的公有内嵌类，所有迭代器都有相同的名字

• const_iterator
• iterator

栈

FILO 先进后出结构
进栈运算在最坏情况下的时间复杂度是O(N)，这很不公平，因为很少发生doubleSpace()的情况。为了更加合理，我们提出均摊分析法，把多出的次数分摊到先前进栈、出栈操作中每个插入只多了一个复制操作，因此从平均的意义上讲，插入运算的时间复杂度还是常批的。

STL中的栈是一个容器适配器，借助vector、list、deque

栈的应用（QUITE IMPORTANT FOR THE COMPILER）

递归函数的非递归实现

递归函数中，每次递归调用都要花费系统时间和空间。于是我们的想法是：把递归函数变成非递归函数。

首先，我们需要知道计算机是如何进行函数调用的————栈！！！
栈中保存的是调用结束后回到的地址，如果递归函数调用层次过深，可能会导致Stack Over Flow(爆栈)。

为了变成一个非递归函数，我们可以考虑自己维护一个栈。
举个例子：快速排序
递归实现：

quickSort(a,low,mid-1);
quickSort(a,mid+1,high);

非递归实现：设置一个栈，记录要做的工作（即要排序的数据段）

struct Node {
    int left;
    int right;
};

先将整个数组进栈，弹出一个区间，将区间分成两半，若区间长度大于2，则进栈

void quickSort(int a[],int size){
    seqStack<Node> st;
    int mid,start,end;
    Node s;

    if(size <= 1){
        return;
    }

    s.left = 0;
    s.right = size - 1;
    while(!st.isEmpty()){
        s = st.pop();
        start = s.left;
        end = s.right;
        mid = divide(a,start,end);

        if(mid - start > 1){
            s.left = start;
            s.right = mid -1;
            st.push(s);
        }
        if(end - mid > 1){
            s.left = mid + 1;
            s.right = end;
            st.push(s);
        }
    }
}

符号平衡检查

• 检查程序中括号是否匹配
  遇到右括号时，与最近遇到的、没有匹配的左括号匹配
  使用栈的思想：
  遇到左括号，进栈，遇到右括号，将栈顶元素出栈并进行比较

还有几个特殊情况：
当括号出现在注释、字符常量、字符串常量

• balance类实现
  在balance类中，为什么用输入文件流对象ifstream而不是string类文件名？
  读文件是通过文件流对象的，类中各种小函数可能都需要对文件进行读写，使用文件流对象会更加简洁。

class balance{
private:
    ifstream fin;
    int currentLines;
    int errors;
    struct Symbol{
        char Token;
        int theLine;
    }; 
    enum CommentType{
        //C++和C注释风格不一样
        SlashSlash;
        SlashStar;
    };

public:
    balance(const char *s);
    int checkBalance(); // 返回出错数
};

balance类有2种执行方式：

• 用户通过键盘输入文件名
• 将要检查的源文件名作为命令行参数
  我们就可以利用main函数的参数

  int main(int argc,const char **argv){
      //...
  }

表达式计算

• 中缀和后缀表达式
  中缀表达式：运算符在2个运算数之间 a + b
  中缀表达式的计算：运算符的优先级和结合性
  后缀表达式：运算符在运算数后面 a b +
  这就可以采用栈来存储最近的2个运算数了

对于后缀表达式：

• 初始化一个栈
• 依次读入后缀式的操作数和运算符直到结束
  若读到的是操作数，则将其进栈
  若读到的是运算符，则将栈顶的两个操作数出栈，后弹出的操作数为被操作数，先弹出的为操作数，将得到的操作数完成运算符所规定的运算，并将结果进栈
• 当栈中只剩有一个操作数时，弹出该操作数，它就是表达式的值

程序员希望看到中缀表达式而不是后缀表达式
我们希望编译器将中缀表达式转化为后缀表达式
遍历中缀表达式时，无法确定当前处理的运算符是否能够运算，但能确定它之前的运算符是否能运算

• 中缀转后缀算法
  若读入的是操作数，立即输出
  若读入的是闭括号，则将栈中的运算符依次出栈并输出，直到遇到相应的开括号，将开括号出栈
  若读入的是开括号，则进栈
  若读入的是运算符，如果栈顶运算符优先级高于或等于读入的运算符，则栈顶运算符出栈；直到栈顶运算符优先级低于读入的运算符为止，读入的运算符进栈
  在读入操作结束时，将栈中所有的剩余运算符依次出栈并输出，直至栈空为止

简单计算器类实现

使用方法：

int main(){
    calc.exp("3 * (7 + 5) / 6 - 2");
    cout << exp.result() << endl;
    
    exp = "3 * 7 + 5";
    cout << exp.result << endl;
}

注意：增加乘法运算符，优先级最高！
也就是说，只要出现乘方运算符，直接进栈，如果遇到其他运算符（当栈顶是乘方运算符时），乘方运算符直接出栈

关于calc类的设计，我们需要：

• 一个字符串（保存表达式）
• 构造和析构函数
• 计算表达式结果
• 赋值运算符重载

重点在于“计算表达式的结果”——result函数的实现

计算器中的表达式中的运算数都是常量，没有必要先转换成后缀表达式，在计算后缀表达式的值。可以将转换和计算两个步骤合并起来，边转换边计算
在中缀转后缀时，发现某个运算符可以出栈时，则直接执行运算
运算过程需要用到两个栈：中缀表达式转后缀表达式时的运算符栈，执行后缀表达式运算时的运算数栈 opStack dataStack