FDS-期末复习

1. 时、空复杂性 （Ω-下界、훩-确界、O-上界）及等级、RUNTIME CALCULATION

2. 数据结构基本概念：

   • 数据类型、对象、操作、数据结构

   • 三大类数据结构：线性（堆栈、队列）、树、图

   • 数据结构的物理表示方法：数组、链表

1. 堆栈（STACK）：

   1. 概念：在同一端插入和删除，FILO

   2. 表示：数组、链表

   3. 操作：入/出栈，空/满判断

2. 队列（QUEUE）

   1. 概念：在一段插入而在另一端删除，FIFO

   2. 表示：数组、链表

   3. 操作：入/出队列，空/满判断

3. 应用——表达式求值，eval，POSTFIX（后缀表达式）

拓展：表达式求值：

题目：3302. 表达式求值 - AcWing题库

题解：AcWing 3302. 表达式求值 - AcWing

1. 基本思想：解决动态查找问题

2. hash函数的构造方法（hash function construction）

3. 冲突处理方法（collision resolution）:

   1. 开放地址法（open addressing）:linear probing,quadratic probing

   2. Chaining

   3. Double hashing

   4. Rehashing (再哈希)

冲突（collision）：当两个关键字散列到同一个值

装填因子（load factor）: 为散列表中的元素个数与散列表大小的比值

分离链接法（seperate chaining）(俗称：拉链法)：将散列到同一个值的所有元素保留到一个表中

//Find 
Position Find(ElementType Key,HashTable H)
{
  Position P;
  List L;
  
  L=H->TheLists[Hash(Key,H->TableSize)];
  P=L->Next;
  while(P!=NULL && P->Element!=Key)
    P=P->Next;
  return P;
}
​
//Insert
void Insert(){
  Position Pos,NewCell;
  List L;
  
  Pos=Find(Key,H);
  if(Pos==NULL){//没有找到的话就选择插入
    NewCell=malloc(sizeof(struct ListNode));
    L=H->TheLists[Hash(Key,H->TableSize)];
    NewCell->Next=L->Next;
    NewCell->Element=Key;
    L->Next=NewCell;
  }
}

开放地址法（Open addressing）

关键函数：hi(X) = (Hash(X )+ F(i)) mod TableSize

1. 线性探测法（linear probing）:F(i)=i

   1. 插入和不成功的查找：1/2*(1+1/(1-λ)2)

   2. 成功的查找：1/2*(1+1/(1-λ))

   3. 一次聚集

2. 平方探测法（quadratic probing）:F(i)=i2

   1. 如果使用平方探测，且表的大小为素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。可以通过证明前（tablesize/2）个备选位置是互异

   Position Find(ElementType Key,HashTable H)
   {
     Position CurrentPos;
     int CollisionNum;
     CollisionNum = 0;
     CurrentPos=Hash(Key,H->TableSize);
     while(H->Thecells[CurrentPos].Info!=Empty && H->TheCells[CurrentPos].Element!=Key){
       CurrentPos+=2*++CollisionNUm-1;//F(i)=F(i-1)+2i-1
       if(CurrentPos>=H->TableSize)CurrentPos-=H->TableSize;
     }
     return CurrentPos;
   }

   Legitimate合法的

   1. 二次聚集

3. 双散列（double hashing）：F(i)=i*hash2(X)

   1. 一般来说 hash2 (X)=R-(X mod R)，其中R为小于TableSize的素数

4. 再散列（rehashing）：建立另外一个大约两倍大（大于两倍的第一个素数）的表，而且使用一个相关的新散列函数，扫描整个原始的散列表，插入新表中

   1. NewTableSize为原表大小两倍后的第一个素数