526互联

Data_Structure_Midterm_review

发布时间 2023-11-17 02:03:40作者: oxidationreaction

目录

基本概念

  • 数据的逻辑结构：面向具体问题（线性表，树）

  • 物理结构(储存结构)：面向计算机的具体实现

  • 相关操作

    任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。

  • ADT是一个数学模型和在模型上定义的操作的集合

  • 面向对象的概念

    面向对象 = 对象＋类＋继承＋通信

    面向对象方法中类的定义充分体现了抽象数据类型的思想

  • 算法的基本特点：输入0个ok，输出，确定性（两次输入输出相同），有穷性，有效性

    ps: 算法的时间复杂度和编译无关

    float sum ( float a[ ], const int n )	{
       float s = 0.0;
       count++;	//count统计执行语句条数
       for ( int i = 0; i < n; i++ ) {
           count++;	//针对for语句
	 s += a[i];
	 count++; //针对赋值语句
       }	
       count++;	//针对for的最后一次
       count++;	//针对return语句
       return s;
   }       执行结束得 程序步数 count =2 * n + 3

  • O(n) & T(n):

    并列取max

    嵌套相乘

    常数不管：$T(n)=O(c*f(n))=O(f(n))$

    S (n) = O(f (n)) 空间复杂度

顺序表

表项是从1开始的，每次操作用i-1;

   for (size_t i = 1; i <= m; i++)//union
    {
      type x=la.getdata(i);
      if(!lb.search(x)) {lb.insert(n,x) lb.n++;}
    }

  int i=1,n=la.length();//交集
   while (i<=n)
   {
     int x=la.getdata(i);
     if(lb.search(x)) {lb.remove(x);n--;}
     i++;
   }

  • 定义方式

    • 复合方式

  • 嵌套方式

    • 继承方式

  • 结构方式

链表

 class List;	                    //复合方式

 class ListNode {	        //链表结点类	
 friend class List;	        //链表类为其友元类
 private:
     int data;		        //结点数据, 整型	
     ListNode * link;            //结点指针		
 };

 class List {	                    //链表类		
 private:
     ListNode *first ;            //表头指针
 };

bool List::Remove (int i, int& x) {// delete
  ListNode *del;
  if(i<=1) {del = first;first=first->link}
  else{
    ListNode *cur;
    int k=1;
    while (k<i-1&&cur!=nullptr)
    {
      cur=cur->link; k++;
    }
    if(cur->link==nullptr||cur==nullptr) {return false;}
    else {del=cur->link; cur->link=del->link;} x=del->data;delete del; 
    return true; 
  }
 }

ListNode * List::ReverseList(ListNode *head) //reverse
{ 
  if(head == nullptr) 
    	return NULL; 
    ListNode *pre = NULL; 
    ListNode *next = NULL; 
    while (head!=nullptr)
    {
      next=head->link;
      head->link=pre;
      pre=head;
      head=next;
    }
    return pre;
    }

双向循环链表的搜索

while ( current != first && current->data != x )	
         current = (d == 0) ? current->lLink : current->rLink;//d is dirction

多项式顺序存储表示的缺点
插入和删除时项数可能有较大变化，因此要移动大量数据
不利于多个多项式的同时处理、有溢出问题
多项式链表存储表示的优点
插入、删除方便，不移动元素
多项式的项数可以动态地增长，不存在存储溢出问题。

静态链表是为没有指针的语言实现单链表能力的方法

  • 链表中的表头节点的作用
    • 统一空表和非空表的操作
    • 插入、删除不再区分是头部还是中间位置
  • 单链表插入中 i=0 表示插入到头节点前

栈与队列

  • 链式栈的top在表头

    void LinkedStack<E>::output(ostream& os, //逆向输出栈
    StackNode<E> *ptr, int& i) {
      if(ptr!=nullptr){
        if(ptr->link!=nullptr)
        output(os,ptr->link,i++);
        cout<<i<<':'<<ptr->value;
      }
    }

  • 合法的出栈数$\frac{\binom{2n}{n}}{n+1}$

  • 后缀表达式

  • 计算后缀表达式

    void Calculator :: Run ( ) {
   char ch;   double newoperand;
   while ( cin >> ch,  ch != ‘;’ ) { 
      switch ( ch ) {
        case ‘+’ :  case ‘-’ :   case ‘*’ :   case ‘/’ :            	case ‘^’ :  DoOperator ( ch );  break;   			                         //计算
        default :  cin.putback ( ch ); 
                              //将字符放回输入流
                        cin >> newoperand;  //读操作数
                        S.Push( newoperand );
      }
   }
}

void DoOperator ( char op ) {
//从栈S中取两个操作数，形成运算指令并计算进栈
    double left, right;   Boolean result;
    result = Get2Operands(left, right); //退出两个操作数
    if ( !result ) return;
    switch ( op ) {
       case ‘+’: S.Push ( left + right);  break;     //加
       case ‘-’: S.Push ( left - right);  break;     //减
       case ‘*’: S.Push ( left * right);  break;      //乘
       case ‘/’: if ( right != 0.0 ) {S.Push ( left / right); break; }
                     else { cout << “除数为0!\n” );  exit(1); } //除
       case ‘^’: S.Push ( Power(left,right) ); //乘幂
    }
}
    image-20231114210704193

    • 汉诺塔

      void hano(int n,char A,char B, char C){
  if(n==1) {cout<<A<<" to "<<C<<endl;return;}
  else{
    hano(n-1,A,C,B);
    cout<<A<<" to "<<C<<endl;
    hano(n-1,B,A,C);
  }
}

    • 循环队列 队列存放数组被当作首尾相接的表处理。

      • 队头、队尾指针加1时从maxSize-1直接进到0,可用语言的取模(余数)运算实现。

      • 队头指针进1: front = (front+1) % maxSize;

      • 队尾指针进1: rear = (rear+1) % maxSize;

      • 队列初始化：front = rear = 0;

      • 队空条件：front == rear;

      • 队满条件：(rear+1) % maxSize == front;

        杨辉三角

        void YANGHVI(int n) {
     queue q(n+3);                     //队列初始化
     q.MakeEmpty();
     q.EnQueue(1);  q.EnQueue(1);	
     int s = 0, t;
  for (int i = 1; i <= n; i++) {         //逐行计算
          cout << endl;			  //换行	
          q.EnQueue(0);					
          for (int j = 1; j <= i+2; j++) {  //处理第i行的系数
	    q.DeQueue(t);
              q.EnQueue(s + t);		
              s = t;
              if (j != i+2) cout << s << " " ; //输出i行的系数，
                                                              //第i+2个是0
         }
     }

    • 下三角矩阵

      若 i < j，数组元素 A[i][j] 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素$A[j][i] = j (j +1) / 2 + i $
      若已知某矩阵元素位于数组 B 的第 k个位置（k≥0），可寻找满足
      i (i + 1) / 2 < k < (i + 1)      (i + 2) / 2
      的 i, 此即为该元素的行号。
      j = k - i * (i + 1) / 2
      此即为该元素的列号。
      例，当 k = 8, 34 / 2 = 6 < k < 45 / 2 =10,
      取 i = 3。则 j = 8 - 3*4 / 2 = 2。

    • 上三角矩阵

      若i<=j:

      $n + n-1 + n-2 +...+ n-i+1+ j-i = \frac{i(n-i+1+n)}{2}+j-i$

  • 三对角矩阵

    $k=i*2+j$

    image-20231115214743182

  • 稀疏矩阵快速转置 真的nb,不开玩笑,桶排序天花板

    for (i = 0; i < Terms; i++)
                 rowSize[smArray[i].col]++; 
            rowStart[0] = 0;	
       for (i = 1; i < Cols; i++)			
	       rowStart[i] = rowStart[i-1]+rowSize[i-1];
	  for (i = 0; i < Terms; i++) {			
	       j = rowStart [smArray[i].col];		
	       B.smArray[j].row = smArray[i].col;
	       B.smArray[j].col = smArray[i].row;
	       B.smArray[j].value = smArray[i].value;
	       rowStart [smArray[i].col]++;		
	  }

string

  • 提取字串时记得最后一个字符是'\0'

  • 伟大的KMP算法 真叹为观止，道爷我疯了

    int posP = 0,  posT = k;	//两个串的扫描指针
     int lengthP = pat.curLength;         //模式串长度
     int lengthT = curLength;               //目标串长度
 	 while (posP < lengthP && posT < lengthT)	{
        if(posP==-1||ch[posT]==pat.ch[posP]) {posP++;posT++;}
        else posP=next[posP];
     }
     if(posP<lengthP) return -1;
     else return posT-lengthP;

      int j = 0, k = -1,  lengthP = curLength;// 生成next
     next[0] = -1;
     while (j < lengthP) {
        if(k==-1||ch[j]==ch[k]){j++;k++;next[j]=k;}
        else k=next[k];
     }

广义表

例：设广义表
A = (apple,( (orange, banana),(peach, pear, kiwifruit))),

则取出A中的原子orange的操作是:
head (head(head(tail(A))))

这里取完tail括号是没有减少的

  • 广义表删除再看看,有些仓促

树和森林

  • 树的度：树中节点上最大的度

  • 子女的度=节点的度数

  • 二叉树中叶结点为$n_{0}$, 度为2的节点为$n_{1}$, 有 $n_{0}=n_{1}+1$

  • 具有 n (n≥0) 个结点的完全二叉树的深度为 log2(n+1)(取上整)

  • 删除算法

if(subtree!=nullptr){
destory(subtree->left);
destory(sub->right);
delete subtree;
}

  • 后序遍历 真没看出来，但是好像也只能这么写

     if (subTree == NULL) return 0;	       //空树
     else return 1+Size (subTree->leftChild) 
                          + Size (subTree->rightChild);

    • 计算树高度 very elegant

       int i = Height (subTree->leftChild);
          int j = Height (subTree->rightChild);
	      return (i < j) ? j+1 : i+1;

    • find parents

      FindParent (TreeNode<T> *t, TreeNode<T> *p) {
//在根为*t的树中找*p的双亲, 并置为当前结点
     TreeNode<T> *q = t->firstChild;     //*q是*t长子
     bool succ;
     while (q != NULL && q != p) {	  //扫描兄弟链
          if ((succ = FindParent (q, p)) == true) 
               return succ;	//递归搜索以*q为根的子树
          q = q->nextSibling;}
            if (q != NULL && q == p) {
          current = t;  return true;
     }
     else { current = NULL;  return false; }   //未找到
};

    • 广度优先遍历

      template <class T> 
void Tree<T>::
LevelOrder(void (*visit) (BinTreeNode<T> *t) ) {
//按广度优先次序分层遍历树, 树的根结点是
//当前指针current。   
Queue<TreeNode<T>*> Q;
     TreeNode<T> *p;
     if (current != NULL) { 	      //树不空 
          p = current;                             //保存当前指针
          Q.enqueue(p)
          while (current!=nullptr)
          {
            Q.dequeue(current);
            visit(current);
            current=current->nextchild;
            while (current!=nullptr)
            {
               Q.enqueue(current);
               current=current->nextsblings;
               
            }
            
          }
          current = p;	  //恢复算法开始的当前指针
     }
};

    • 森林的广度优先遍历是侧向的

      image-20231116212507054

最小堆

  • shift down

    template <class T, class E>
void MinHeap<T>::siftDown (int start, int m ) {
//私有函数: 从结点start开始到m为止, 自上向下比较, 
//如果子女的值小于父结点的值,  则关键码小的上浮, 
//继续向下层比较, 将一个集合局部调整为最小堆。
	int i = start,   j = 2*i+1;  	//j是i的左子女位置
	E temp = heap[i]; 			
	while (j <= m) {	
      if(heap[j]>heap[j+1]) j++;
      if(temp<heap[j]) break;
      else {
         heap[i]=heap[j];i=j;j=i*2+1;
      } }
      heap[i]=temp;

};

  • fiterup

    template <class T, class E>
void MinHeap<T>::FilterUp (int start) {
//私有函数: 从结点start开始到结点0为止, 自下向上
//比较, 如果子女的值小于父结点的值, 则相互交换, 
//这样将集合重新调整为最小堆。关键码比较符<=
//在E中定义。
	 int j = start,  i = (j-1)/2;   E temp = heap[j];
	 while (j > 0) {		//沿父结点路径向上直达根
	      if (heap[i] <= temp) break;							//父结点值小, 不调整
		else { heap[j] = heap[i];  j = i;  i = (i-1)/2; }
					//父结点结点值大, 调整
	  }
     	heap[j] = temp;				//回送
};

    Huffman树

    • 扩充二叉树只有0度和2度

      有n个外节点，n-1个内节点，2n-1个节点

  • image-20231116223932986