Data structure memo

绪论

抽象数据类型是抽象数据组织及与之相关的操作。

数据结构包含逻辑结构、存储结构和数据的运算。

有序表中的“有序”是逻辑意义上的有序,指表中的元素按照某种规则已经排好了位置。顺序表中的“有序”是物理意义上的,指线性表中的元素一个接一个的存储在一片相邻的存储区域中。

栈是一种抽象数据类型,可以采用顺序存储和链式存储,只表示逻辑结构。

算法

链表合并

已知长度分别为m和n的升序链表,若将它们合并为长度为m+n的一个升序链表,则最坏情况下的时间复杂度是 O(m+n)。


class Solution {
  public:
      ListNode* mergeTwoList(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr) {
          return l2;
        }
      } else if (l2 == nullptr) {
         return l1;
      } else if (l1->val < l2->val) {
        l1->next = mergeTwoList(l1->next, l2);
        return l1;
      } else {
        l2->next = mergeTwoList(l1, l2->next);
        return l2;
      }
}

冒泡排序算法

void BbbleSort(int[] A, int n) {
  for(int i = 0; i < n-1; i++) {
    bool flag = false;
    for(int j = n-1; j > i; j--)
      if(A[j-1] > A[j])
      swap(A[j-1], A[j]);
      flag = true;
  }
  if(flag == false)
    return;
}

void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}


算法原地工作的含义是指算法所需的辅助空间是常量。

线性表

线性表是一种逻辑结构。

顺序表

算法

插入操作 后移应该从末尾元素往后移动

bool ListInsert(SqList &L, int i, ElemType e) {
  if(i < 1 || i > L.length+1) // 判断 i 的范围是否有效
    return false;
  if(L.length > = MaxSize)  // 当前存储空间已满,不能插入
    return false;
  for(int j = L.length; j >= i; j--)  // 将第i个元素及之后的元素后移
    L.data[j] = L.data[j-1] // 从线性表的末尾元素开始后移
  L.data[i-1] = e;
  L.length++;
  return true; 
}

删除操作 前移应该从首部元素往前移动

bool ListDelete(SqList &L, int i; ElemType e) {
  if(i < 1 || i > L.length) // 判断i的范围是否有效  
    return false;
  e = L.data[i-1];
  for(int j = i; j < L.length; j++) // 将第i个位置后的元素前移
    L.data[j-1] = L.data[j];
  L.length--;
  return true;
}


C++中的“脏数据”

malloc函数返回一个指向一整片连续的存储空间的起始地址的指针