cdk's blog

个人博客

0%

发表于： 分类于：

栈和队列

Stack Overview 堆栈概述

  1. The first ADT we saw today was the stack. A stack is a LIFO (last-in, first-out) data structure. It generally supports a limited set of operations: 我们今天看到的第一个抽象数据类型是栈。栈是一种后进先出（ LIFO ）数据结构。它通常只支持有限的操作：
Member Function 成员函数Description 描述
clear()removes all elements from the stack 从栈中移除所有元素
equals(stack)returns true if the two stacks contain the same elements in the same order, false otherwise 如果两个栈包含相同顺序的相同元素，则返回 true，否则返回 false
isEmpty()returns true if the stack contains no elements, false otherwise 如果栈不包含任何元素，则返回 true，否则返回 false
peek()returns the element on the top of the stack without removing it 返回栈顶元素但不移除它
pop()removes the element from the top of the stack and returns it 从栈顶移除元素并返回它
push(value)pushes value onto the stack 将值压入栈中
size()returns the number of values in the stack 返回栈中的元素数量
. . .For an exhaustive list, see: Stanford Stack class 如需完整列表，请参阅：斯坦福栈类

Queue Overview 队列概述

  1. We then discussed the queue ADT. A queue is a FIFO (first-in, first-out) data structure. Like the stack, it generally supports a limited set of operations: 我们接着讨论了队列抽象数据类型。队列是一种先进先出（FIFO）的数据结构。和栈一样，它通常支持一组有限的操作：
Member Function 成员函数Description 描述
clear()removes all elements from the queue 从队列中移除所有元素
dequeue()removes and returns the frontmost element in the queue 移除并返回队列中最前面的元素
enqueue(value)adds value to the back of the queue 将 value 添加到队列的末尾
equals()returns true if the two queues contain the same elements in the same order, false otherwise 如果两个队列包含相同顺序的相同元素，则返回 true，否则返回 false
isEmpty()returns true if the queue contains no elements, false otherwise 如果队列不包含任何元素，则返回 true，否则返回 false
peek()returns the frontmost element in the queue without removing it 返回队列中最前面的元素，但不移除它
size()returns the number of values in the queue 返回队列中的值数量
. . .For an exhaustive list, see: Stanford Queue class 如需完整列表，请参阅：斯坦福队列类

发表于： 分类于：

作业1

We wrote various tests for the extractAlpha() function in class today. Add to that code a separate STUDENT_TEST that contains a suite of test cases for the passwordChecksOut() function. What sorts of things would you test to ensure you have robust testing coverage for that function?

我们今天在课堂上为 extractAlpha（） 函数编写了各种测试。在该代码中添加一个单独的 STUDENT_TEST，其中包含一套 passwordChecksOut（） 函数的测试用例。您将测试哪些内容来确保该函数具有强大的测试覆盖率？

主要是为了给 passwordChecksOut（） 函数编写测试用例没有难度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include "console.h"
#include "SimpleTest.h"
#include "strlib.h"
using namespace std;

string extractAlpha(string s)
{
    string result;

    for (int i = 0; i < s.length(); i++)
    {
        if (isalpha(s[i]))
        {
            result += s[i];
        }
    }
    return result;
}

bool passwordChecksOut(string username, string password)
{
    string alphaPortion = extractAlpha(password);
    return !stringContains(toLowerCase(alphaPortion), toLowerCase(username));
}

STUDENT_TEST("various tests of extractAlpha() function")
{
    EXPECT_EQUAL(extractAlpha("sean"), "sean");
    EXPECT_EQUAL(extractAlpha("sean11"), "sean");
    EXPECT_EQUAL(extractAlpha("1sean"), "sean");
    EXPECT_EQUAL(extractAlpha("s1ean"), "sean");
    EXPECT_EQUAL(extractAlpha("s1e1a1n"), "sean");
    EXPECT_EQUAL(extractAlpha("s9e$a***&n"), "sean");
    EXPECT_EQUAL(extractAlpha(""), "");
    EXPECT_EQUAL(extractAlpha("9$&"), "");
}

STUDENT_TEST("这是我的测试, 关于函数 passwordChecksOut()")
{
    EXPECT_EQUAL(passwordChecksOut("dk","d9327309k**%dd"), false);
    EXPECT_EQUAL(passwordChecksOut("dk","kdbusa*7^//"),true);
}

int main_test()
{
    runSimpleTests(ALL_TESTS);

    string username = "Sean";
    string password = "s1e1a1n1'1s1p1a1s1s1w1o1r1d";

    if (passwordChecksOut(username, password))
    {
        cout << "Hooray!" << endl;
    }
    else
    {
        cout << "Oh no! Bad password." << endl;
    }

    return 0;
}

作业2

简单情形

Write a function that takes a vector of integers as its only argument and prints it in the following format:

编写一个函数，该函数将整数向量作为其唯一参数，并按以下格式打印：

1
2
3
4

+----+----+----+----+----+----+
| 43 | 19 | 12 | 95 | 83 | 13 |
+----+----+----+----+----+----+
  0    1    2    3    4    5

The function signature is: 函数签名为：

1

printVector(Vector<int>& v)

To simplify the problem, you may assume all the integers in the vector have exactly two digits. 为了简化问题，您可以假设向量中的所有整数恰好有两位数字。

这个问题也是简单的, 因为假设了二位整数所以没有任意整数的困难(包括负数, 位数不同等).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include "console.h"
#include "SimpleTest.h"
#include "vector.h"
#include "string.h"
using namespace std;

void printVector(Vector<int>& v)
{
    string s1, s2, s3;
    int count = 0;
    for (int i : v)
    {
        s1 += "+----";
        s2 += "| " + to_string(i) + " ";
        s3 += "  " + to_string(count) + "  ";
        ++count;
    }
    s1 += "+";
    s2 += "|";
    cout << s1 << "\n"
         << s2 << "\n"
         << s1 << "\n"
         << s3 << endl;
}


int main_printVector()
{
    Vector<int> v1 = {43, 19, 12, 95, 83, 13};
    printVector(v1);
    // cout << "+----+----+----+----+----+----+\n| 43 | 19 | 12 | 95 | 83 | 13 |\n+----+----+----+----+----+----+\n  0    1    2    3    4    5";
    return 0;
}

改进

Additional challenge (this is fairly advanced; don’t worry too much about this one if you don’t have time): 额外的挑战（这是相当高级的，如果你没有时间，不要太担心这个）：

  • How could you ensure when printing the contents of a vector that the largest box has exactly enough space for the largest integer in the vector to be surrounded by one space on either side, and all other boxes have the same amount of space, with each integer being centered within its cell to the extend possible? For example: 在打印向量的内容时，如何确保最大的框有足够的空间让向量中最大的整数在两侧被一个空格包围，并且所有其他框具有相同的空间量，每个整数在其单元格内居中，尽可能地扩大？ 例如：
1
2
3
4

+------+------+------+------+------+------+
|  43  |  1   |  9   | 129  | 5821 |  3   |
+------+------+------+------+------+------+
   0      1      2      3      4      5

这里位数不同的问题应该是普遍意识到的问题, 但是还有一个问题在于我们事实上是可以考虑负数的情形的但是这样需要考虑一些额外的情况.

1
2
3
4

+-------+-------+-------+-------+-------+-------+-------+
|  43   |   1   |   9   |  129  | 5821  |   3   | -5633 |
+-------+-------+-------+-------+-------+-------+-------+
    0       1       2       3       4       5       6

如图所示存在问题: 计算整数位数时, 负数需要计算-号也会占用一个位置.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <iostream>
#include "console.h"
#include "SimpleTest.h"
#include "string.h"
#include "vector.h"
using namespace std;

int widthOfNum(int num){
    if (num == 0) return 1; // 0是1位数

    int count = 0;
    // 处理负数：转换为正数
    if (num < 0) {
        num = -num;
        ++count;
    }

    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}

int maxWidthOfVector(Vector<int> &v){
    int numVec = v.size();
    int maxNum = widthOfNum(v[0]);
    for(int i= 1;i<numVec;i++){
        if(widthOfNum(v[i]) > maxNum)
        {maxNum = widthOfNum(v[i]);}
    }
    return maxNum;
}



void printVectorAdvanced(Vector<int> &v)
{
    //runSimpleTests(SELECTED_TESTS);
    int maxVecWidth = maxWidthOfVector(v)+2;
    string s1,s2,s3;
    int count = 0;
    for(int i:v)
    {
        int iWidth = widthOfNum(i);
        s1 += string("+") + string(maxVecWidth,'-');
        int whiteSpace1 = (maxVecWidth-iWidth)/2;
        int whiteSpace2 = maxVecWidth - whiteSpace1-iWidth;
        s2 += string("|") + string(whiteSpace1,' ') + to_string(i) + string(whiteSpace2,' ');
        int whiteSpace3 = (maxVecWidth+1)/2;
        s3 += string(whiteSpace3,' ') + to_string(count) + string(maxVecWidth/2,' ');
        count++;
    }
    s1 += string("+");
    s2 += string("|");
    cout << s1 << "\n" << s2 << "\n" << s1 << "\n" << s3 << endl;
}

STUDENT_TEST("测试maxWidthOfVector函数")
{
    Vector<int> v1 = {43,1,9,129,5821,3};
    Vector<int> v2 = {43,1,9,129,582,3,-256};
    EXPECT_EQUAL(maxWidthOfVector(v1), 4);
    EXPECT_EQUAL(maxWidthOfVector(v2), 7);
}


STUDENT_TEST("测试函数widthOfNum"){
    EXPECT_EQUAL(widthOfNum(1890),4);
    EXPECT_EQUAL(widthOfNum(0),1);
    EXPECT_EQUAL(widthOfNum(-1),2);
}

int main()
{
    //runSimpleTests(SELECTED_TESTS);
    Vector<int> v1 = {43,1,9,129,5821,3};
    Vector<int> v2 = {43,1,9,129,5821,3,-5633};
    printVectorAdvanced(v2);
    return 0;
}

可能的改进

  1. 可能可以使用一些更好的方法来拼接字符串或者是直接打印.

作业3

In the previous problem, why would we pass the vector by reference if we have no intention of modifying it in the printVector() function?

在上一个问题中，如果我们无意在 printVector（） 函数中修改向量，为什么还要通过引用传递向量？

个人感觉还是直接传递变量副本太占据存储空间.

Tips: 需要注意所有程序中的 main() 函数都添加了 _filename 使得能够在同一个空白项目中编译成功, 需要用的时候去掉后缀同时保证项目中没有其他 main() 函数即可

发表于： 分类于：

设计原则：功能分解及其他

  1. (Key Concept!) Breaking up a task into constituent functions that each fulfill a single purpose is called functional decomposition and improves the readability and maintainability of our code.

    （核心概念！）将任务分解为各自实现单一功能的组成函数，称为功能分解，并提高代码的可读性和可维护性。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

    #include <iostream>
#include "console.h"
#include "strlib.h"
using namespace std;

string extractAlpha(string s)
{
   string result;

   for (int i = 0; i < s.length(); i++)
   {
      if (isalpha(s[i]))
      {
         result += s[i];
      }
   }
   return result;
}

bool passwordChecksOut(string username, string password)
{
   string alphaPortion = extractAlpha(password);
   return !stringContains(toLowerCase(alphaPortion), toLowerCase(username));
}

int main()
{
   string username = "Sean";
   string password = "s1e1a1n1'1s1p1a1s1s1w1o1r1d";

   if (passwordChecksOut(username, password))
   {
      cout << "Hooray!" << endl;
   }
   else
   {
      cout << "Oh no! Bad password." << endl;
   }

   return 0;
}