基于斯坦福cs106b的c++数据结构笔记

发表于 2024-01-20 更新于 2023-11-27 分类于课程笔记，数据结构与算法阅读次数：本文字数： 4.2k 阅读时长 ≈ 15 分钟

一些查找和排序算法

二分查找法最坏情况：log2n 寻找最小排序向前插入算法

合并算法接受两个排序的列出并将它们组合成一个排序列表。 ● 虽然两个列表都是非空的，但比较它们的第一要素。删除较小的元素并将其附加到输出。 ● 一旦一个列表为空，添加所有元素另一个列表输出。 ● 它运行时间为 O(n)，其中 n 是总数合并的元素数量。无限递归后的合并算法复杂度：nlog2n

容器类

set（集合）：无序不允许重复的容器类，可以添加删除元素 You can add a value to a Set by writing set += value; s. ● You can remove a value from a Set by writing set -= value; ● You can check if a value exists in a Set by writing set.contains(value)map(键值对的集合) 如果没有对应key的value，返回默认值（见定义文件） `vector vector的remove根据移除元素的索引有1-n的复杂度，移除尾部为O(1)，如果不在意索引，可以交换要移除元素和尾部元素再移除

哈希表

哈希表的负载因子α表示元素和表格键数量的比，决定了查找速度

检查表中是否存在元素

● 计算元素的散列码。 ● 跳转到表格中的那个位置。 ● 向前扫描——必要时环绕——直到项目或一个发现空插槽。

将元素插入表中

● 如果项目已经存在，什么也不做。 ● 否则，跳转到元素哈希码给定的槽。向前走——必要时环绕——直到一个空白点或找到墓碑插槽。然后，将项目放在那里。

从表中删除一个元素

● 跳转到由元素的散列码给定的槽。 ● 向前走——必要时环绕——直到物品或发现空插槽。如果找到该项目，请将其替换为墓碑。

“罗宾汉哈希表”

如果插入的值比其将插入的位置的值距离索引更远，则替换插入值和当前值
删除值时，将后其离原键远的元素前移
★ 罗宾汉哈希一览 ★
检查表中是否存在元素：
● 跳转到表中由元素的散列码给出的位置。
● 向前扫描——如有必要环绕——记录有多少步你拿走了。当您找到该项目、找到一个空白槽或找到一个离家更近的空位比你走的步数还多。
将元素插入表中：
● 如果该元素已在表中，则什么也不做。
● 跳转到由元素的散列码给出的表槽。向前扫描 - 换行如有必要，四处走走——记录所走的步数。如果你找到一个空插槽，将元素放在那里。否则，如果当前插槽已满并且比您插入的元素更靠近家，将要插入的项目放在那里，替换那个位置的元素，然后继续插入，就好像你正在插入被置换的元素。
从表中删除一个元素：
● 跳转到由元素的散列码给定的槽。
● 向前走——如有必要，环绕——直到物品或空槽被放置成立。如果找到该项目，请将其删除。然后，继续前进——包裹 around as necessary – 将表中的元素向后移动一个槽位，直到找到空插槽或位于其原始位置的项目

string类

str::npos表示容器的最后一个成员位置 if (s.find("e") != string::npos) //find函数找不到时返回npos if s in str: string obj; obj.substr(int pos) //pos为要包含的第一个字符串的位置 std::string a = "0123456789abcdefghij";


    // count is npos, returns [pos, size())
    [std::string](http://en.cppreference.com/w/cpp/string/basic_string) sub1 = a.substr(10);
    [std::cout](http://en.cppreference.com/w/cpp/io/cout) << sub1 << '\n';

    // both pos and pos+count are within bounds, returns [pos, pos+count)
    [std::string](http://en.cppreference.com/w/cpp/string/basic_string) sub2 = a.substr(5, 3);
    [std::cout](http://en.cppreference.com/w/cpp/io/cout) << sub2 << '\n';

    // pos is within bounds, pos+count is not, returns [pos, size())
    [std::string](http://en.cppreference.com/w/cpp/string/basic_string) sub4 = a.substr(a.size()-3, 50);
    // this is effectively equivalent to
    // std::string sub4 = a.substr(17, 3);
    // since a.size() == 20, pos == a.size()-3 == 17, and a.size()-pos == 3

    [std::cout](http://en.cppreference.com/w/cpp/io/cout) << sub4 << '\n';

    try {
        // pos is out of bounds, throws
        [std::string](http://en.cppreference.com/w/cpp/string/basic_string) sub5 = a.substr(a.size()+3, 50);
        [std::cout](http://en.cppreference.com/w/cpp/io/cout) << sub5 << '\n';
    } catch(const [std::out_of_range](http://en.cppreference.com/w/cpp/error/out_of_range)& e) {
        [std::cout](http://en.cppreference.com/w/cpp/io/cout) << "pos exceeds string size\n";
    }
}
输出：
abcdefghij
567
hij
pos exceeds string size

`replace和insert str1.insert(start, str2) str1.replace(start, length, str2)

一些实现

优先队列

# include "HeapPQueue.h"
using namespace std;

HeapPQueue::HeapPQueue() {
    elems = new DataPoint[INITIAL_SIZE] {};
    for (int i=0;i<INITIAL_SIZE;i++)
    {
        elems[i].weight=0;
    }
    allocatedSize=INITIAL_SIZE;
}

HeapPQueue::~HeapPQueue() {
    delete [] elems;
}

int HeapPQueue::size() const {
    return logicalSize;
}

bool HeapPQueue::isEmpty() const {
    return logicalSize==0;
}

void HeapPQueue::enqueue(const DataPoint& data) {
    if (logicalSize+1<allocatedSize)
    {
        if (logicalSize==0)
        {
            elems[1]=data;
            logicalSize++;
        }
        else
        {
            logicalSize++;
            int i=1;
            while (data.weight>elems[i].weight && i<=logicalSize && elems[i].weight!=0)
            {
                i++;
            }
            if (i<logicalSize)
            {
                DataPoint temp=elems[i];
                elems[i]=data;
                for(i;i<logicalSize;i++)
                {
                    DataPoint temp_plus=elems[i+1];
                    elems[i+1]=temp;
                    temp=temp_plus;

                }
            }
            else
            {
                elems[i]=data;
            }

        }
    }
}

DataPoint HeapPQueue::peek() const {
    return elems[logicalSize];
}

DataPoint HeapPQueue::dequeue() {
    DataPoint to_return=elems[1];
    if(!isEmpty())
    {

        for (int i=1;i<logicalSize;i++)
        {
            elems[i]=elems[i+1];
        }
        elems[logicalSize]={};
        logicalSize--;
    }
    return to_return;
}

计数排序

首先算出最大值，然后用一个数组的索引存储待排序数组的成员，其索引对应值存储出现次数，然后用两个同步的for循环和递增的next参数表示排序中的索引值来进行排序（也就是重新赋值）

/* Given a Vector<int>, returns the largest number in that Vector. */
int maxOf(const Vector<int>& values) {
    /* Bounds-check inputs. */
    if (values.isEmpty()) {
        error("Can't find the maximum of no values.");
    }
    
    int result = values[0];
    for (int i = 1; i < values.size(); i++) {
        result = max(result, values[i]);
    }
    return result;
}

/* Given a list of numbers, creates a histogram from those numbers. */
Vector<int> histogramFor(const Vector<int>& values) {
    /* Create a histogram with the right number of slots. Initially, all values
     * in the histogram will be zero.
     */
    Vector<int> histogram(maxOf(values) + 1);
    
    /* Scan across the input vector, incrementing the histogram values. */
    for (int value: values) {
        histogram[value]++;
    }
    
    return histogram;
}

void countingSort(Vector<int>& values) {
    /* Edge Case: If the array is empty, then it's already sorted. This is
     * needed because we can't take the maximum value of an empty vector.
     */
    if (values.isEmpty()) {
        return;
    }
    
    /* Form the histogram. */
    auto histogram = histogramFor(values);
    
    /* Scan across the histogram writing out the appropriate number of copies
     * of each value. We track the index of the next free spot to write to,
     * as it varies based on how many items we've written out so far.
     */
    int next = 0;
    for (int value = 0; value < histogram.size(); value++) {
        /* Write out the right number of copies. */
        for (int copy = 0; copy < histogram[value]; copy++) {
            values[next] = value;
            next++;    
        }
    }
}

错题集

递归的效率优化

每次递归都会创造所有变量的临时复制基于递归的这种性质，它会需要巨大的时间和空间来完成任务，并且会造成算力上的浪费。通过记忆表机制能部分解决这个问题，方法是每次递归的返回值都会按索引存入一个表格，并且每次递归前查询表格中是否有结果，这样可以让每个临时副本的运算结果能被所有函数共享。

递归计算给定元素的不同结构哈夫曼树的数量

对每个给定元素集来说，首先要做到是确定根节点元素是第几个大的元素，确定之后，左子树和右子树的元素数也随之确定，在此之后分别对左节点和右节点作为根节点做同样的递归


int numBSTsOfSize(int n) {

  /* Base case: There’s only one tree of size 0, namely, the empty BST. */
  if (n == 0) return 1;
  
  /* Recursive case: Imagine all possible ways to choose a root and build the
   * left and right subtrees.
  */
  int result = 0;
  
  /* Put the the nodes at indices 0, 1, 2, ..., n-1 up at the root. */
  for (int i = 0; i < n; i++) {
    /* Each combination of a BST of i elements and a BST of n - 1 - i elements
     * can be used to build one BST of n elements. The number of pairs of
     * trees we can make this way is given by the product of the number of
     * trees of each type.
     */
     result += numBSTsOfSize(i) * numBSTsOfSize(n - 1 - i);
  }
  
  return result;
}

递归解决吃巧克力问题

求出吃法数量

if (numSquares<0)
{
    error("输入数据不能为负数");
}
else if (numSquares<=1)
{
    return 1;
}
else
{
    return numWaysToEat(numSquares-1)+numWaysToEat(numSquares-2);
}

打印每种吃法

`需要一个辅助向量储存历史记录

/* Print all ways to eat numSquares more squares, given that we've
 * already taken the bites given in soFar.
 */
void printWaysToEatRec(int numSquares, const Vector<int>& soFar) {
    /* Base Case: If there are no squares left, the only option is to use
     * the bites we've taken already in soFar.
     */
    if (numSquares == 0) {
        cout << soFar << endl;
    }
    /* Base Case: If there is one square lfet, the only option is to eat
     * that square.
     */
    else if (numSquares == 1) {
        cout << soFar + 1 << endl;
    }
    /* Otherwise, we take take bites of size one or of size two. */
    else {
        printWaysToEatRec(numSquares - 1, soFar + 1);
        printWaysToEatRec(numSquares - 2, soFar + 2);
    }
}

void printWaysToEat(int numSquares) {
    if (numSquares < 0) {
        error("You owe me some chocolate!");
    }

    /* We begin without having made any bites. */
    printWaysToEatRec(numSquares, {});
}

递归解决翻煎饼问题

bool isSorted(Stack<double> pancakes) {
    double last = -1; // No pancakes have negative size;

    while (!pancakes.isEmpty()) {
        /* Check the next pancake. */
        double next = pancakes.pop();
        if (next < last) {
            return false;
        }

        last = next;
    }

    /* Pancakes are in increasing order! */
    return true;
}

/* Given a stack of pancakes and a flip size, flips that many pancakes
 * on the top of the stack.
 */
Stack<double> flip(Stack<double> pancakes, int numToFlip) {
    /* Take the top pancakes off the stack and run them into a queue.
     * This preserves the order in which they were removed.
     */
    Queue<double> buffer;
    for (int i = 0; i < numToFlip; i++) {
        buffer.enqueue(pancakes.pop());
    }

    /* Move the pancakes back. */
    while (!buffer.isEmpty()) {
        pancakes.push(buffer.dequeue());
    }

    return pancakes;
}

Optional<Vector<int>> sortStack(Stack<double> pancakes, int numFlips) {
    /* Base Case: If the stack is sorted, great! We're done, and no flips
     * were needed.
     */
    if (isSorted(pancakes)) {
        return { }; // No flips
    }
    /* Base Case: If the stack isn't sorted and we're out of flips, then
     * there is no way to sort things.
     */
    else if (numFlips == 0) {
        return Nothing;
    }
    /* Recursive Case: The stack isn't sorted and we still have flips left.
     * The next flip could flip 1, 2, 3, ..., or all N of the pancakes.
     * Try each option and see whether any of them work.
     */
    for (int numToFlip = 1; numToFlip <= pancakes.size(); numToFlip++) {
        /* Make the flip and see if it works. */
        auto result = sortStack(flip(pancakes, numToFlip), numFlips - 1);
        if (result != Nothing) {
            /* The result holds all the remaining flips but doesn't know about
             * the flip we just did. Insert that flip at the beginning.
             */
            result.value().insert(0, numToFlip);
            return result;
        }
    }

    /* If we're here, then no matter which flip we make first, we cannot
     * get the pancakes sorted. Give up.
     */
    return Nothing;
}

递归解决天平问题

bool isMeasurableRec(int amount, const Vector<int>& weights, int index) {
  if (index == weights.size()) {
      return amount == 0;
  } else {
      return isMeasurableRec(amount,                  weights, index + 1) ||
             isMeasurableRec(amount + weights[index], weights, index + 1) ||
             isMeasurableRec(amount - weights[index], weights, index + 1);
  }
}

bool isMeasurable(int amount, const Vector<int>& weights) {
    return isMeasurableRec(amount, weights, 0);
}

想象一下，我们首先将要测量的数量（称为 n ）放在天平的左侧。这使得规模上的不平衡等于 n 。想象一下，有某种方法可以测量 n 。如果我们一次将一个重量放在秤上，我们可以查看第一个重量的放置位置（假设它的重量为 w ）。它必须：

向左走，使规模上的净不平衡 n + w ，或
向右走，使规模上的净不平衡 n – w ，或
根本不习惯，留下净不平衡 n 。

如果确实有可能测量 n ，那么这三个选项之一必须是实现它的方法，即使我们不知道它是哪一个。然后我们要问的问题是，是否有可能使用剩余的权重来衡量新的净失衡——我们可以递归地确定！另一方面，如果无法测量 n ，那么无论我们选择哪个选项，我们都会发现没有办法使用剩余的权重来使一切平衡！

如果我们递归地进行，我们在这里，我们需要考虑我们的基本情况。我们可以选择的选项有很多。一个简单的方法如下：假设我们根本没有任何重量，我们被要求查看是否可以不使用重量来测量某些重量。在什么情况下我们可以这样做？好吧，如果我们称重的东西有一个非零重量，我们就不可能测量它——把它放在秤上会使它倾斜到某一边，但这并不能告诉我们它有多少重量。另一方面，如果我们称量的东西是完全失重的，那么把它放在秤上也不会导致它倾斜，让我们相信它确实是失重的！因此，作为我们的基本情况，我们会说当我们减少到没有剩余权重时， ，我们可以精确测量n 如果 n = 0 。考虑到这一点，这是我们的代码：

递归解决找零问题

不使用记忆的情况

`从第一个硬币开始遍历，并穷举它的所有枚数，将其作为下一枚硬币的参数传递

int fewestCoinsFor(int cents, const Set<int>& coins) {
    /* Can't have a negative number of cents. */
    if (cents < 0) {
        error("You owe me money, not the other way around!");
    }
    /* Base case: You need no coins to give change for no cents. */
    else if (cents == 0) {
        return 0;
    }
    /* Base case: No coins exist. Then it's not possible to make the
     * amount. In that case, give back a really large value as a
     * sentinel.
     */
    else if (coins.isEmpty()) {
        return cents + 1;
    }
    /* Recursive case: Pick a coin, then try using each distinct number of
     * copies of it that we can.
     */
    else {
        /* The best we've found so far. We initialize this to a large value so
         * that it's replaced on the first iteration of the loop. Do you see
         * why cents + 1 is a good choice?
         */
        int bestSoFar = cents + 1;
        /* Pick a coin. */
        int coin = coins.first();
        /* Try all amounts of it. */
        for (int copies = 0; copies * coin <= cents; copies++) {
            /* See what happens if we make this choice. Once we use this
             * coin, we won't use the same coin again in the future.
             */
            int thisChoice = copies + fewestCoinsFor(cents - copies * coin,
                                                     coins - coin);
          /* Is this better than what we have so far? */
            if (thisChoice < bestSoFar) {
                bestSoFar = thisChoice;
            }
        }
        /* Return whatever worked best. */
        return bestSoFar;
    }
}

使用记忆进行优化

/* How few coins are needed to make the total, given that we can only use
 * coins from index startIndex and onward?
 */
int fewestCoinsRec(int cents, const Vector<int>& coins, int startIndex,Grid<int>& memo) {
    /* Base case: You need no coins to give change for no cents. */
    if (cents == 0) {
        return 0;
    }
    /* Base case: No coins exist. Then it's not possible to make the
     * amount. In that case, give back a really large value as a
     * sentinel.
     */
    else if (startIndex == coins.size()) {
        return cents + 1;
    }
    /* Base case: We already know the answer. */
    else if (memo[cents][startIndex] != -1) {
        return memo[cents][startIndex];
    }
    /* Recursive case: Pick a coin, then try using each distinct number of
     * copies of it that we can.
     */
    else {
        /* The best we've found so far. We initialize this to a large value so
         * that it's replaced on the first iteration of the loop. Do you see
         * why cents + 1 is a good choice?
         */
        int bestSoFar = cents + 1;

        /* Pick a coin. */
        int coin = coins[startIndex];

        /* Try all amounts of it. */
        for (int copies = 0; copies * coin <= cents; copies++) {
            /* See what happens if we make this choice. Once we use this
             * coin, we won't use the same coin again in the future.
             */
            int thisChoice = copies + fewestCoinsRec(cents - copies * coin,
                                                     coins, startIndex + 1,
                                                     memo);

            /* Is this better than what we have so far? */
            if (thisChoice < bestSoFar) {
                bestSoFar = thisChoice;
            }
        }

        /* Return whatever worked best. */
        memo[cents][startIndex] = bestSoFar;
        return bestSoFar;
    }
}

int fewestCoinsFor(int cents, const Set<int>& coins) {
    /* Can't have a negative number of cents. */
    if (cents < 0) {
        error("You owe me money, not the other way around!");
    }

    /* Convert from a Set<int> to a Vector<int> so we have a nice ordering
     * on things.
     */
    Vector<int> coinVec;
    for (int coin: coins) {
        coinVec += coin;
    }

    /* Build our memoization table. Since the number of cents left ranges from
     * 0 to cents, we need cents+1 rows. Since the start index of the coin
     * ranges from 0 to coins.size(), we make coins.size() + 1 columns.
     *
     * -1 is used as a sentinel to indicate "nothing has been computed here
     * yet."
     */
    Grid<int> memo(cents + 1, coins.size() + 1, -1);

    /* Now ask how many coins are needed to make the total, using any coins
     * from index 0 onward.
     */
    return fewestCoinsRec(cents, coinVec, 0, memo);
}

递归穷举付账单

递归机制：对第一个人来说，0-total所有金额都会付一遍，随后传递给下一个人，当只有一人时，付清所有余额并打印账单传递参数：string,int的映射存储目前为止的账单，string集合存储所有付账者

void listPossiblePaymentsRec(int total, const Set<string>& people,const Map<string, int>& payments) {
    /* Base case: if there's one person left, they have to pay the whole bill. */
    if (people.size() == 1) {
        Map<string, int> finalPayments = payments;
        finalPayments[people.first()] = total;
        cout << finalPayments << endl;
    }
    /* Recursive case: The first person has to pay some amount between 0 and the
     * total amount. Try all of those possibilities.
     */
    else {
        for (int payment = 0; payment <= total; payment++) {
            /* Create a new assignment of people to payments in which this first
             * person pays this amount.
             */
            Map<string, int> updatedPayments = payments;
            updatedPayments[people.first()] = payment;
            listPossiblePaymentsRec(total - payment, people - people.first(),updatedPayments);
        }
    }
}
void listPossiblePayments(int total, const Set<string>& people) {
    /* Edge cases: we can't pay a negative total, and there must be at least one
     * person.
     */
    if (total < 0) error("Guess you're an employee?");
    if (people.isEmpty()) error("Dine and dash?");
 listPossiblePaymentsRec(total, people, {});
}

递归寻找完全平方数列

主要参数为sofar——用于存储目前的序列和一个set用于存储还没放入数列的数字，`确保这两者同时被传递，且其并集为所有数字

Optional<Vector<int>> findSquareSequence(int n) {
    /*Validate input.*/
    if (n < 0) {
        error("Don't be so negative!");
    }

    /* Build a set of the numbers 1, 2, 3, ..., n. */
    Set<int> options;
    for (int i = 1; i <= n; i++) {
        options += i;
    }
    return findSequenceRec(options, { });
}

Optional<Vector<int>> findSequenceRec(const Set<int>& unused,
                                      const Vector<int>& soFar) {
    /*Base Case: If all numbers are used, we have our sequence!*/
    if (unused.isEmpty()) {
        return soFar;
    }

    /* Recursive Case: Some number comes next. Try each of them and see which
     * one we should pick.
     */
    for (int next: unused) {
        /* We can use this if either
         *
         * 1. the sequence is empty, so we're first in line, or
         * 2. the sequence is not empty, but we sum to a perfect square
         *    with the previous term.
         */
        if (soFar.isEmpty() ||
            isPerfectSquare(next + soFar[soFar.size() - 1])) {
            /* See what happens if we extend with this number. */
            auto result = findSequenceRec(unused - next, soFar + next);
            if (result != Nothing) {
                return result;
            }
        }
    }

    /* Tried all options and none of them worked. Oh well! */
    return Nothing;
}

汉诺塔递归

假设有三座汉诺塔，start ,temp ,finish 对n层的汉诺塔问题，先考虑n-1层的，随后考虑n-2层，到最后只需要考虑两层问题，两层的汉诺塔非常容易解决，起点为start,终点是temp,临时塔为finish，最后我们得到temp上的两层汉诺塔这时将start的3移动到finish塔，这时只要将两层汉诺塔转移到finish则完成了三层汉诺塔，这个过程中的起点为temp,终点是finish,临时塔是start 以此类推，四层塔基于三层塔，n层塔基于n-1塔，汉诺塔问题解决

int moveTower(int numDisks, char start, char finish, char temp) {
    if (numDisks == 0) {
        return 0;
    } else {
        int movesOne = moveTower(numDisks - 1, start, temp, finish);
        moveSingleDisk(start, finish);
        int movesTwo = moveTower(numDisks - 1, temp, finish, start);

        return 1 + movesOne + movesTwo;
    }
}