7-17

发表于 阅读次数：

攻防世界RE题

题目csaw2013reversing2

先打开文件，看到有一处显示乱码
U6b1tx.png

用od打开发现有两个“Flag”字符串，猜测应该是在得出真正flag的语句附近
U6blA1.png

到“Flag”附近。两个“Flag”离得比较近，一路F8运行之后发现中间有一个int3，还有一个跳转使程序跳过了跟一个Flag有关的语句
U6qZ5t.png

把跳转指令跳的地方一改就得到flag了
U6HXff.png

线性表基本概念

线性表包括：顺序表、链表

  • 对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
  • 数据元素之间具有一种线性的或“一对一”的逻辑关系；
  • 第一个数据元素没有前驱，这个数据元素被称为开始节点；
  • 最后一个数据元素没有后继，这个数据元素被称为终端节点；
  • 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继；

顺序表

顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。

  • 在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的；
  • 存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费；
  • 便于随机存储；
  • 不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动；

参考：
https://zhuanlan.zhihu.com/p/138238617
https://zhuanlan.zhihu.com/p/138046349

堆栈

操作

初始化、测试是否为空栈、测试堆栈是否已满、入栈出栈、取当前栈顶元素

堆栈的顺序存储结构可以用一个数组stack[n]来描述。i==0时，stack[i]是第一个进入堆栈的元素；i==-1时，堆栈为空栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//进栈
int push(int stack[],int &top,int item){
    if (Full(top))
        return 0;
    else {
        stack[++top]=item;  //先改变栈顶指针
        return 1;
    }
}

//退栈
int pop(int stack[],int &top,int item){
    if(Empty(top))
        return 0;
    else{
        item=stack[top--];
        return 1;
    }
}

多个堆栈共享连续空间

调整堆栈空间，防止堆栈溢出
如果两个堆栈共享一个储存空间，只需让一个堆栈的栈底位于stack[0]，另一个位于stack[m-1]
如果两个以上的堆栈共享连续空间，且不知道每个堆栈可能存放的最大个数，可将M个存储空间平均分给n个栈，当其中任意一个堆栈产生上溢，而整个空间并未占满，则进行“浮动”再调整。
设top[0…n-1]为n个堆栈的栈顶指针集合，bot[0…n]为n+1个堆栈的的栈底指针集合。
初始时令bot[i]==top[i],bot[n]=max-1（bot[n]的目的时为了测试第n个堆栈是否栈满）
第i个堆栈栈空的条件为top[i]==bot[i],第i个堆栈栈满的条件为top[i]=bot[i+1]
当top[i]==bot[i+1]时，可以分为下列3种情况：

  • 找到这个栈i右边第一个有可用空间的栈j，然后将栈i+1…j向右移一个位置，使栈i空出一个空间
  • 在这个栈左边找到第一个有可用空间的栈j，再将栈j+1~i的元素向前移动一个位置
  • 如果没有发现可用的空间则证明产生了溢出

多个堆栈共享连续空间的优点之一是节省空间，但弊病是需要移动大量数据，时间代价较高，这是顺序存储结构的固有缺陷

堆栈的链式存储结构

称为链接堆栈或链栈