wujr5 / c-and-cpp-language-learning Goto Github PK

View Code? Open in Web Editor NEW

67.0 67.0 34.0 3.37 MB

C和C++编程语言学习 - 2015级

C 98.75% C++ 1.25%

c-and-cpp-language-learning's People

Contributors

Stargazers

Watchers

c-and-cpp-language-learning's Issues

计科：实验课反馈

请在评论中写下你对实验课的建议或者意见，我们集中讨论，协商问题。记住，一切都是为了让你更好地学习，有问题，请大胆说出来。

计科：第四次课选择题

Which datatype is used to represent the absence of parameters?
a) int
b) short
c) void
d) float
The value 132.54 can represented using which data type?
a) double
b) void
c) int
d) bool
Is bool a fundamental datatype in C++?
a) Yes
b) No, it is a typedef of unsigned char
c) No, it is an enum of {false,true}
d) No, it is expanded from macros
What is the value of the bool?
```
bool is_int(789.54)
```
a) True
b) False
c) 1
d) none of the mentioned
How many characters are specified in the ASCII scheme?
a) 64
b) 128
c) 256
d) none of the mentioned
Select the right option.
Given the variables p, q are of char type and r, s, t are of int type
```
1. t = (r * s) / (r + s);
2. t = (p * q) / (r + s);
```
a) 1 is true but 2 is false
b) 1 is false and 2 is true
c) both 1 and 2 are true
d) both 1 and 2 are false

What is the output of the following program?

1.      #include <iostream>
2.      using namespace std;
3.      int main()
4.      {
5.          int x = -1;
6.          unsigned int y = 2;
7.   
8.          if(x > y) {
9.              cout << "x is greater";
10.         } else {
11.             cout << "y is greater";
12.         }
13.     }

a) x is greater
b) y is greater
c) Implementation defined
d) Arbitrary

What is the value of the following 8-bit integer after all statements are executed?
```
int x = 1;
x = x << 7;
x = x >> 7;
```
a) 1
b) -1
c) 127
d) Implementation defined
Which of the following is not one of the sizes of the floating point types?
a) short float
b) float
c) long double
d) double

What is the output of this program?

1.      #include <iostream>
2.      using namespace std;
3.      int main()
4.      {
5.          float num1 = 1.1;
6.          double num2 = 1.1;
7.          if (num1 == num2)
8.             cout << "stanford";
9.          else
10.            cout << "harvard";
11.         return 0;
12.     }

a) harvard
b) stanford
c) compile time error
d) runtime error

第二次课

本周无特别内容。提供课件作为参考：课件下载

软件：week4 理论作业（2015-10-19 实验课结束后提交）

Attention:

作业写在纸上，写上姓名学号，在实验课结束后提交。

对于每一道题目，写上答案，并且写上解题思路，为什么选这个？（根据什么？）

英文答题

😄 😄 😄

答题例子：
// example

C99 standard guarantees uniqueness of ____ characters for internal names.
a) 31
b) 63
c) 12
d) 14
View Answer
Answer:b
Explanation:ISO C99 compiler may consider only first 63 characters for internal.
// end example

正式题目：

Which of the following is not a valid variable name declaration?
a) int __a3;
b) int __3a;
c) int __A3;
d) None of the mentioned
Which of the following is not a valid variable name declaration?
a) int _a3;
b) int a_3;
c) int 3_a;
d) int _3a
Variable names beginning with underscore is not encouraged. Why?
a) It is not standardized
b) To avoid conflicts since assemblers and loaders use such names
c) To avoid conflicts since library routines use such names
d) To avoid conflicts with environment variables of an operating system
All keywords in C are in
a) LowerCase letters
b) UpperCase letters
c) CamelCase letters
d) None
Which of the following is not a valid C variable name?
a) int number;
b) float rate;
c) int variable_count;
d) int $main;
Which of the following is true for variable names in C?
a) They can contain alphanumeric characters as well as special characters
b) It is not an error to declare a variable to be one of the keywords(like goto, static)
c) Variable names cannot start with a digit
d) Variable can be of any length
The value of expression 3.6-5/2+1.2+5%2 is .
(A) 4.3
(B) 4.8
(C) 3.3
(D) 3.8
_______ translates high-level language program into machine language program.
(A)CPU
(B) A compiler
(C) An assembler
(D) The operating system
Which of the followings cannot be used as an identifier?
(A) _1234
(B) 1_2
(C) int_2
(D) 2_int
If x = 2 and y = 3, what is the value of y for y += x > y ? x *x : y * y.
(A) 12
(B) 9
(C) 7
(D) none of the above
Suppose int i=1,which of the following statements cannot increase variable i by 1?
(A)i=i+1;
(B)i+=1;
(C)i++;
(D)i=1;
Which of the followings cannot be used as an identifier?
(A) true
(B) INT
(C) CHINA
(D) end
The value of expression 4-5/2.0+5%2 is .
(A) 2.5
(B) 3
(C) 4
(D) none of the above

计科：实验课分享

大家可以在评论中分享你觉得很有价值的东西，觉得可能对大家有用的东西。TA会鉴定你所分享的内容，如果不恰当，可能会被修改或者删除。但是请不要因为这样而害怕或者拒绝分享，因为交换想法或者**，你将收获巨大。

软件：week 7 问题反馈

1、记得本周有实验作业实验：程序调试
2、期中考试时间，11月9日，8：00。
地点：实验中心B403
理论考试时间：8:00 ~ 9:30
实验机试：9:40 ~ 11:10 （暂定5题）

周知。

3、往年期中考试题稍后会放在
http://172.18.215.225:8080/
大家可以计时做题。

4、本周讨论请在本issue后留言，欢迎讨论。

计科：实验课计划

助教：吴家荣

简介：中山大学数据科学与计算机学院软件工程 13级嵌入式软件开发方向

Mail: [email protected] or [email protected]

Tel: 18819473270

授课方式：弃用ppt，完全使用github

1 实验报告

1.1 第一次实验报告

主题：学习iomanip, cmath库函数

时间：week3

1.2 第二次实验报告

主题：学习冒泡排序算法

时间：week4

1.3 第三次实验报告

主题：格式化输出，使用windows.h，使用cstring

时间：week5

1.4 第四次实验报告

主题：程序流程图和伪代码

时间：week6

1.5 第五次实验报告

主题：再谈代码风格检查，断点调试

时间：week7

1.6 第六次实验报告

主题：基于命令行窗口的小游戏贪吃蛇

时间：week8 - week10

1.7 第七次实验报告

主题：linux系统初探

时间：week11 - week12

1.8 第八次实验报告

主题：学生信息管理系统

时间：week13 - week15

1.9 第九次实验报告

主题：总结回顾在sicily做过的所有习题

时间：week16

2 习题课

2.1 第一次习题课

时间：初定week11周末

2.2 第二次习题课

时间：初定week16周末

3 考试

3.1 期中考试

3.2 期末考试

软件：12周理论作业

~~一共4个文件，几百题。~~

现在题库**563题。同学们可完成每一类别题目中的三分之一。多做不限。

文件在群共享和FTP的Resource文件夹均有。

DDL：

~~2015年12月30日 18:00~~
2015年12月30日 21:00

命名：

13331314_叶嘉祺_理论题.pdf

要求，对每道题写简单的解释，并且理解。

1 Sicily习题

2 第一次选择题

对比答案，看看答案的解析。

3 第二次实验报告

3.1 学习冒泡排序算法

3.2 存在问题

交互不好
没有按照google style写代码，可读性很差
文件没有按照要求命名
没有cpp程序
程序崩溃
程序错误

3.3 优秀作业展示

4 关于作业和成绩

尽量按时提交，延时适当扣分
一定按照要求的命名和格式提交
自己不需要打包，直接发给学委，学委全部一起打包即可
对成绩有问题及时找我纠正

1 代码风格

要求符合google style。在线google style检查：google style

2 Gitbub账号

要求每个人都注册github账号，并且watch项目：c-and-cpp-language-learning

3 Discussion

要求有问题尽量在github上面讨论，因为这样能尽可能记录问题，如果其他人也遇到类似问题，那么他就能直接在提问中学习，而不需要重新提问。

4 注意目录

建议使用主页的目录帮自己组织内容。如果直接看issue的列表，你会凌乱的。

参见：c-and-cpp-language-learning

经历了半个学期的痛苦、煎熬、无奈、彷徨的DDL

如题。很多同学已经产生对编程无比的抗拒了，大家油然而生一种感觉，我是当初脑子进水了才报软件工程专业，这个专业各种各样的作业，看着别的同学上大学悠闲自在，自由飞翔，羡慕死了。

我们天天被西西里虐成狗，被TA出的实验题玩成熊。天天打代码，周末也一去不复返。

看着无奈的wrong answer，time limit exceeded，memory limit exceeded，runtime error，restrict function，不知道怎么改。“我这个程序绝壁没错，不可能啊”

看着实验题就是恨着TA为毛文件结果错一点点就给个0分。

看着一堆不懂的概念，和不知道说什么的英文。什么指针什么玩意，什么函数原型什么鬼，什么i++,++i什么鬼。

看着这么难的东西居然有大神却能从容自若，谈笑风生，还可以轻易装逼，简直了。

看着老师上课就像在讲天书，哇啦哇啦不知道说什么，隐隐约约听到一个call by value, call by value，也不知道啥意思。

书本如砖头，呵呵。

有人说，你正在痛苦地经历着一切，终有一天你会笑着说出来。没错，这些就是TA的经历。

我们虽然在作业最难最多的专业，可是我们也在最有前途的专业，也许别人开开心心地玩着上大学，以后就哭着找工作养家糊口。

也许，有挑战的事情才是真正的学习。记得小学期有个外教说过，“you should remember how you struggled when you feel it easy” (你要记得你在掌握之前曾经多么纠结)。

也许很多同学上大学就很迷茫，特别在软件学院，懵逼了，找不到方向，有一种我的人生失去了希望的感觉。其实没那么夸张。

最终的结果取决于，你能否坚持下来

其实看到你们现在的状态就看到了我当年的自己。很遗憾，TA并不是大神，只是你们一个师兄，而且还是嵌入式方向，呵呵。很遗憾，个人特长还是搞Web的，c语言学的也不是特别好，c++就更不好了。算法也是学的很渣，离散数学等于没学。现在其实很后悔，如果当初怎么怎么。。。。现在的知识水平也许会更高。

下面给些实质性建议：

个人总结（技术博客）

其实你们学的很好，只是自己感觉比较差而已，我觉得你们应该多做总结。总结是学习很重要的工具，可以知道自己到底学了什么。
所谓总结，并不是说，写一段比如这篇水水的东西一样。最好的办法是，针对一个特定的问题，比如西西里一道纠结的题目，“运算符的优先级和结合性”等问题，写一些个人的博客，进行深度学习，这也是给你们出deepthinking的目的，而不是三两句话就带过

深入学习思考

很多同学的思维通常只会浮在最表面，很多深入的东西并没有认真去思考。比如，函数原型，可能大家看到的定义就是，函数的函数名，函数参数，返回值，书上也会举个很简单的例子A+B。然而，函数原型设计是面向过程程序设计里面一门大学问。当其涉及到指针的时候，一切都变得不简单。所以很多时候大家只会去看到一些很表面的东西，这，远远不够。

关于算法

很多人都很执着于去搞算法，和数据结构。我这方面比较差，连快排也要百度那种。其实怎么说呢，很多时候对于工程来说，最基本的算法确实是必须了解。做工程的人，在能深入研究算法和计算机科学的人面前就是非常弱鸡的。可是我们毕竟是工程师，对于很多问题的实际解决是跟算法有差距的。
也许很多人很惧怕嵌套循环，不过做大型项目的时候，这个东西经常用，甚至都不会考虑用哈希去优化什么的。
教Web的王青老师说过，优化和不优化的问题关键在于，优化的成本很大（写复杂的算法），不优化对性能也造成不了多大的影响。
我个人建议，在大二的时候好好写学数据结构与算法，现在把语言基础都弄扎实。

关于高数、线代：

很多人会有疑问，我们来软件学院不是应该学web技术、机器学习、人工智能、安卓开发、游戏开发等等这样的东西。为什么要学那么多数学。其实当时我也不懂。现在懂了，可能晚了，发现之后的课程里不知不觉之中用到了很多数学的知识，特别是离散数学，线性代数。其实计算机科学就是数学的一个分支（个人观点）。你能学多远，就取决于你数学的抽象思维有多深入。

对于兴趣的建议

如果有些同学觉得纯粹抽象的编程太难，其实不用着急，先把现在的东西学好。兴趣是慢慢来的，前端的技术其实是偏技术性的，可以参考家荣TA的github，里面有很多可以运行的很好玩的web程序。

总结

希望大家能学的更好。

计科：week3 第一次实验报告内容

1 阅读www.cplusplus.com 中关于iomanip, cmath的代码和例子

2 提交两个程序和一份实验报告

程序1：learn-iomanip.cpp

代码不限形式
规定要用到函数setiosflags, resetiosflags, setbase, setfill, setprecision, setw六个函数
要有良好输出，有对比，让我知道你了解了如何使用这些函数

没使用要求的函数，或者输出没让我看懂你是否了解函数的作用，扣分！

程序2：learn-cmath.cpp

代码不限形式
规定使用到你感兴趣的中的函数
有良好的输出，有对比。剩下的要求同程序1

心得：

模板，转发学习委员

计科：week12 project1 The Snake Game

week12 project1 The Snake Game

1 Brief Introduction

Snake is a game where the player maneuvers a line which grows in length, with the line itself being a primary obstacle. There is no standard version of the game. The concept originated in the 1976 arcade game Blockade, and its simplicity has led to many implementations (some of which have the word snake or worm in the title). After a variant was preloaded on Nokia mobile phones in 1998, there was a resurgence of interest in the Snake concept as it found a larger audience.

The player controls a dot, square, or object on a bordered plane. As it moves forward, it leaves a trail behind, resembling a moving snake. In some games, the end of the trail is in a fixed position, so the snake continually gets longer as it moves. In another common scheme, the snake has a specific length, so there is a moving tail a fixed number of units away from the head. The player loses when the snake runs into the screen border, a trail, or another obstacle.

The Snake concept comes in two major variants:

In the first, which is most often a two-player game, there are multiple snakes on the playfield. Each player attempts to block the other so he or she runs into an existing trail and loses. Surround for the Atari 2600 is an example of this type. The Light Cycles segment of the Tron arcade game is a single-player version, where the other "snakes" are AI controlled.
In the second variant, a sole player attempts to eat apples by running into them with the head of the snake. Each object eaten makes the snake longer, so maneuvering is progressively more difficult. Examples: Nibbler, Snake Byte.

2 Requirement

2.1 Developmental Enviroment

Ubuntu or other linux operating system is required

There will be at least 50% penalty for the use of Dev-cpp in windows

2.1 Debug Tool

GDB. Just watch the video of introduction of gdb. To know more detail usage of gdb, search it.

3 Detail Documents (80pts)

3.1 User Interface

Like the following picture. If you want to make some changes, just do it !

3.2 Demand

3.2.1 How to Play Your Game (30pts)

"W, A, S, D" should be the direction controler, represent for direction respectively: UP, LEFT, DOWN, RIGHT
Press key "W": your snake should go up
Press key "A": your snake should go left
Press key "S": your snake should go down
Press key "D": your snake should go right
If the snake hit the food, it eat the food, so the length of the snake should increase by 1 unit

3.2.2 How to Win the Game (20pts)

You can set a maximum length of the snake, if the player's snake reach that, the player win the game

After the player win the game, you should present a win-game interface fot the player, so that he knows what happens. At the same time, he can choose exit the game or restart the game.

3.2.3 When Will the Player Lose the Game (20pts)

The snake hits its body
The snake hits the wall

After the player lose the game, you should present a lose-game interface fot the player, so that he knows what happens. At the same time, he can choose exit the game or restart the game.

3.2.4 Extends (10pts)

Record how many steps the snake have walked, present it bellow the hints.
Automatic snake: the snake can automatic move, the press of key can only change its direction
Degrees of difficulty:
1. You can design increasing maximum length for different levels. For example, the fist level, the maximum length is 10 and 20 for second.
2. You can design increasing moving speed with the snake eating more food. (for automatic snake)

4 Report Template (20pts)

Mind that software = program + data + document, and here the document is your report, so I suggest that you should pay more attention to this part if you want to get higher scores.

Template like that:

(1) Deploy

Here discribe how to run your game and discribe the operating environment.

(2) Pseudocode and Flowchart

Write down the pseudocode and flowchart of your game, just use the knowledge you have learned in lab4

(3) Feelings and Experimences

I concern about how you feel and how you make progress when you finish your work step by step.

Write down some questions you encountered and describe how you solved it.

Write down what have you gained from this project. If you do not gain anything from it, I felt sorry for it and I want to know the reasons.

(4) Bonuses

Show me what bonuses you have finished.

5 Development Advice

Development Process

Step1: Establish develop environment. Using provided code, run it in your computer
Step2: Complete the base functions. Like functions for go up, go down, go right, go left.
Step3: Add advanced functions. Like judge whether winning the game or not, losing the game or not
Step4: Add extended functions. Like automatic moving, different levels.

6 Bonuses

Show me you have used the knowledge you have learned in lab1 in your report. (2pts)
Show me you have used the knowledge you have learned in lab2 in your report. (2pts)
Color your snake, the wall or the food, just used the knowledge you have learned in lab3 in your report. (5pts)
If you encounter some bug in your project, and you use the knowledge you learned in lab5 to fix it, that is to say, you use the method of breakpoint debug to debug your code, just descripe it in your report. (5pts)
It is recommanded to use your myString.h you write in lab6 instead of to process the char string in your project, and you should tell me where you used it in your report. (10pts)

7 Attachment

framework code
Vedio in ftp

8 Submit

cs_project1_学号_姓名.zip
  |-- // add your files here

9 Deadline

2015, Dec 30th, 21:00

软件：Course Project 1 (optional)

Project1：

For a deep understand for c pointers and functions, we will take a project.

An introduction to List

In computer science, a list or sequence is an abstract data type that represents an ordered sequence of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream.[1]:§3.5 Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item.

A singly linked list structure, implementing a list with 3 integer elements.
The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists.

Many programming languages provide support for list data types, and have special syntax and semantics for lists and list operations. A list can often be constructed by writing the items in sequence, separated by commas, semicolons, or spaces, within a pair of delimiters such as parentheses '()', brackets '[]', braces '{}', or angle brackets '<>'. Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array. In object-oriented programming languages, lists are usually provided as instances of subclasses of a generic "list" class, and traversed via separate iterators. List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications. In some contexts, such as in Lisp programming, the term list may refer specifically to a linked list rather than an array.

In type theory and functional programming, abstract lists are usually defined inductively by two operations: nil that yields the empty list, and cons, which adds an item at the beginning of a list.[2]

From wikipedia

Our course project is about List.
List is a data type that defined by programmers or the language. The best advantage of the list(linear list) is that it can store variable length of data. Usually, we use struct in c language with a member variable as a 'next' pointer points to the next element of the list. And we will have some functions for the list operations. These operations is the core of C programming language including the usage of pointers, various data types and also some basic knowledge of a computer.

Detail Introduction: link

Try your best to finish the hardest project.

Basic Knowledge(15 pts)

answer the questions in deep thinking part in your report

1. Memory distribution map for a runtime program (very important for your 4-year study)

From Professor Wan Hai's courseWare

This is an overview for a program when it's loaded into the memory of the computer. There are totally 4 area for it, Code area, Static area, Heap and stack.
Code area: This area is used to store program codes(instructions for cpu to execute)
Static area: This area is for the ralatively ‘static’ variables. Global variables, static local variables, static global variables are allocated in the static storage area.
Heap: This area is management by the operating system and it's shared by other programs. You can get dynamic memory allocations in this area. This is the area we need to use in list
Stack: The stack is a area of memory that allocated by the compile. All variables declared in stack.
Notice that stack and heap in operating system are totally different in data structure
For example:

#include <malloc.h>
int main() {
   int a;  // allocated in stack
   int * b = (int *)malloc(sizeof(int));  // allocated in heap
   free(b);
   return;
}

Notice that we have a operation before the program end. free(b). Because we use the memory in the heap which means that these memory should be managed by the programmer. Even though the memory will be free by a mordern operating system, we should prevent memory lost (memory leak).
For example:

int main() {
   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area1
   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area2
   return;
}

The example above cause a memory leak problem because pointer point to another memory area and the previous memory area1 is lost.

2. Malloc() to get memory from heap

The two examples above show how to get memory in heap. In fact, we it's a serial of functions.
C language with the memory of the functions are mainly calloc, alloca, malloc, free, realloc and so on.
<1> alloca is the application of the stack to the memory, so there is no need to release.
<2> malloc allocates memory is located in the heap, and there is no memory of the contents of the initial memory, so after the basic malloc, call the function memset to initialize this part of the memory space.
<3> calloc will initialize this part of the memory, set to 0
<4> realloc is the size of the memory of the malloc application.
<5> The heap needs to be released by the function free.

Notice that everytime you apply memory from heap, you should remember it and delete it(free) when your use of it is end.

int main() {
   int * a = malloc(sizeof(int));

   // code using a

   free(a);
}

3. List operations

The operations about list are appending, deleting, modifying, querying.

we use this simple list again:

If delete the second node:

node* save = head->next;
head->next = head->next->next;
free(save);

2.If append a node at the end of the list

node* last = head;
while(last->next != NULL) {
    last = last->next;
}

last->next = (node*)malloc(sizeof(node));
last->next->data = data;
last->next->next = NULL;

Traversal
node * temp = head;
while(temp != NULL) {
Traversal(temp);
temp = temp->next;
}

Deep Thinking

1. Why use a list instead of an array? What's the advantages of them and disadvantages for them respectively?
2.See the following function:

static void myFunction() { int a; }

(1) Which area in memory does the function store? And which dose the variable int a?
(2) What's the advantages of using static functions?

3. See the following program which is attempt to allocate a dynamic array.

#include <malloc.h>

int main() {
    char ** strs;
    int n ,m;
    int i;

    scanf("%d%d", &n, &m);

    strs = (char **)malloc(sizeof(char *) * n);

    for(i = 0; i < n; i++) {
        strs[i] = (char *)malloc(sizeof(char) * m);
    }


   // code for the 2d array
   // free operations omited
    return 0;
}

Can we create an 2D array in the heap using this way? Give your explanations and give another way that can allocated a dynamic 2D array

4.
(1)See the following program.

head->next = head->next->next;

Why it's a wrong operation for deleting a element in the list?
(2)Write a simple pseudo code program to insert '88' before the last element and then insert '76' before the head. Notice that what you know is the head element address of the list. Think about the difference between instering at the head and not at the head.

5. How to use an array to create a list know as a static list in logic?
For example:

node a[100];
head = a[0];
a[0]->next = 2;   // an array index

6. (optional) Think about that can we use an int_64 (long long) to create a list using the high 32 bits to store an int data and use the low 32 bits to store the next address pointer? If so, write a program to test. If not, wirte a program to explain your reasons.

Grading List

Deep thinking for part 1 (15pts)

Option 1 Generic list (115 pts)

Option 2 Json Parser (105 pts)

计科：期中考试问题总结

要求：每个人都要在这里写下评论总结。并截图放到第五次实验报告当中。如果没有写，实验报告扣除相应分数。

如果你实在不想写，可以联系我，视情况可以免写。

以下格式供参考，不限于以下格式。

格式：

学号：15xxxxx
前半学期学习总结：balabala...
期中考试总结：balabala...
后半学期学习规划：balabala...

计科：week5 第三次实验报告

1 第五次课第三次实验

1.1 实验内容

自行编写小程序，要求：

程序1．格式化输出，输出一个表格
程序2．以不同颜色输出helloworld(提示：使用windows.h库)
程序3．使用<cstring>中8个函数，并计时，将程序运行时间输出

效果图及实验模板链接：模板及效果图

1.2 效果图

表格打印：

颜色输出：

当然你可以选择打印彩色的表格。

2 实验要求

2.1 实验报告模板

下载

2.2 提交格式

打包成zip或rar格式

文件命名

学号_姓名(主目录)
   - table.cpp
   - color.cpp
   - stringFunction.cpp
   - 学号_实验报告.pdf

3 注意

注意，基本要求就是实现上述两个图片上的效果。至于，是否需要人工输入数据，是否有其他的功能，你自己选择，请在实验报告注明。原则就是：做的越多，分数越高，当然你做的东西是要有意义的，如果只是多输出一行数据，那就是没意义的。

4 deadline

2015年11月5日晚12点，务必及时提交

计科：week11 Linux and GDB

week11 Linux and GDB

0 上周限时比赛

简单情况
加分事项

1 presentation

同学展示

参考：

2 自编选择题

随机抽取5个同学的选择题让同学们来做，然后作者讲解，同学们提问并质疑。

3 有关myStrng

函数功能，不是cout，而是返回或者改变传地址的相应的值。
开发测试，分开.cpp，.h，函数定义写在.cpp里面，函数声明写在.h里面，使用的时候直接引用.h

4 ubuntu的使用

project1强制性要求的开发环境：linux或者相关发行版，强制要求风格：google style
简单教程：Ubuntu桌面入门指南

5 GDB的使用

简单教程：GDB十分钟教程

6 其他

科学上网：lantern
Sublime Text 3：Sublime
filezilla：

计科：Final Project

week15 Final Project

Final project is our the last project. There are two options for you guys to choose. But of course, if you are able to do more, just do it!

1 Option 1: Review

1.1 Overview

I think many students did not do your work well in sicily before, or maybe some students did finish the every weeks' subject in sicily but they were not familiar with the relative knowledge. Because of that, this option is called to my mind. I hope most of your guys have a good look of the primer knowledge of C++.

1.2 Requirements (100pts)

Finish the subjects that you have not completed in sicily, or do it again in order to review relative knowledge.
Choose 3 subjects in every weeks' homework. Analyze it and write down the pseudocode for every subject you have chose. At the same time, you should summarize it with writing down what konwledge does this subject want to investigate. Please answer all of this in your report.(80pts)
Write an essay about what have you gained in this semester, and your understanding of C++ and talk about the design function protopyte procedure-oriented thinking.(20pts)

1.3 Report template

Final project

1 简介

Brief introduction of you and your project.

2 题目总结和分析

2.1 第一周题目分析

1000
题意：
伪代码：
Your pseudocode...
相关知识分析：
本题考点分析：

2.2 第二周题目分析

....
依次类推。

3 Essay

Write down your essay here.

1.4 Submit

Please name after the template below.

虽然只有一个文件，但是也请将打包压缩

cs_final_project_option1_学号_姓名.zip
    |-- report.pdf

提交到ftp上的相应目录上。

2 Option 2: simpleList.h

2.1 Overview

链表是一种比较重要的数据类型。大家应该听说过这样的一种说法，程序 = 语言 + 数据结构 + 算法。可能大家要区分一下数据类型和数据结构的概念。我们到目前为止，学习的唯一的数据类型可能就是数组了。数据类型呢，就是平时熟练运用的int, float, double, char之类的了。

下面是C++数据类型的总结。

C++数据类型

基本类型
- 整型
  - 短整形(short int)
  - 整型(int)
  - 长整型(long int)
- 字符型(char)
- 浮点型
  - 单精度类型(float)
  - 双精度类型(double)
  - 长双精度类型(long double)
- 布尔型(bool)
- 空类型(void)
非基本类型
- 枚举类型(enum)
- 数组类型(type[])
- 结构体类型(struct)
- 联合体类型(union)
- 类类型(class)
- type *
指针类型

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

from 百度百科

列举一下常用的数据结构。

数组

在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中，数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

栈

是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

队列

一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。

链表

是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

树

是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：
（1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。　（2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。
（3）K中各结点，对关系N来说可以有m个后继（m>=0）。

图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

堆

在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。

散列表

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个**建立的表为散列表。

2.2 Requirement(100pts)

2.2.1 自学链表数据结构

了解链表组成，自学关于链表的数据结构。

2.2.2 实现simpleList.cpp （70pts）

要求实现simpleList.h头文件的函数。

// 实现一个简单的单向链表

typedef struct node_type {
    int data; // 节点数据
    struct node_type *next; // 指向下一个node_type类型数据
} nodetype;

typedef struct list_type {
    nodetype *head; // 链表头节点
    int length; // 指针长度
} listtype;

// 描述：初始化并生成链表，注意，返回的是listtype类型，代表链表的头部，还有长度记录
// 输入：无
// 返回：返回listtype类型的数据的指针（提示：需要动态生成数据，使用new操作符）
// 例子：无
listtype * list_create(void);

// 描述：打印链表内容
// 输入：链表listtype类型指针，代表一个链表
// 返回：无
// 输出：打印输出链表内容
// 例子：如果链表内容为：1->2->3->4,则打印输出"1->2->3->4"（不包括括号）
void list_print(listtype *list);

// 描述：向链表内插入值
// 输入：listtype指针，插入位置，需要插入的数据
// 返回：返回插入数据后的listtype类型指针
// 例子：list1：1->2->3，调用list_insert(list1, 0, 0)。结果：list1: 0->1->2->3。
// 提示：注意边界情况，如果插入的位置非法（负数、大于length等，则什么都不干）。插入的是动态创建nodetype节点
listtype * list_insert(listtype *list, int location, int data);

// 描述：删除链表的值
// 输入：listtype指针，删除的数据的位置
// 返回：返回被删除的节点的data
// 例子：list1：1->2->3，调用list_delete(list1, 1)，那么list1变为：1->3
// 提示：注意边界情况，如果删除的位置非法（负数、大于length等，则什么都不干）。删除的nodetype节点。
int list_delete(listtype *list, int location);

// 描述：清空链表
// 输入：需要清空的链表指针
// 返回：清空后的链表指针
// 提示：由于nodetype节点是通过new动态创建的，因此，清空链表的时候，需要通过delete删除。避免内存泄漏的发生。
listtype* list_clear(listtype * list);

// 描述：返回链表的长度
// 输入：链表指针
// 返回：链表长度
int list_length(listtype * list);


// 描述：判断链表是否为空
// 输入：链表指针
// 返回：如果链表为空，返回true，否则false
bool list_empty(listtype * list);


// 描述：将输入的链表进行排序
// 输入：链表指针
// 返回：排序后的链表指针
// 要求：从链表头开始按照升序排序
// 例子：list1: 1->4->5->2，list_sort(list1): 1->2->4->5
listtype * list_sort(listtype * list);

2.3 Report template （30pts）

Final project

1 简介

Brief introduction of you and your project.

2 函数功能介绍

类似软件文档，介绍你的函数的用法和功能等

3 心得体会

你的心得体会

2.4 Submit

只需要提交simpleList.cpp文件

cs_final_project_option2_学号_姓名.zip
    |-- simpleList.cpp
    |-- report.pdf

提交到ftp上的相应目录上。

3 Deadline

C++程序设计期末考试之前。

4 小结

好消息：平时分平均分90；坏消息：...
复习tips：
- 理论：书本（概念、语法）、理论课ppt、选择题库
- 实验：final project option 1
补交实验报告：deadline：期末考试前
小小请求：final project 实验报告中，写一段对TA本学期助教工作的评价，TA据此和根据自身情况来决定下学期是否继续担任大家的助教。
最后，多谢大家一学期的配合，考试顺利！

软件： week10 问题反馈

Extra Assignment

Description:

1、按照老师的要求，每位同学需要对现阶段学习的知识（二维数组、函数）等做充分理解。每位同学设计三道理论选择题，并提交收集，以供大家练习。

要求：
1、完整的题目
2、题目的解释
3、请使用英文来编写题目

提交方法：使用markdown进行题目编写，提交文件名：

13331314_叶嘉祺_v0.md

注意v0代表你提交的版本号，第一次提交为v0，第二次为v1，以此类推
提交到指定ftp地址，ftp://172.18.182.75/
远程目录：Experiment/软件班/第十周理论题设计

Deadline：周六下午18点

2、~~限时编程练习题。和期中考试一样，进行现时间编程练习，题目以及时间跟期中考试形式一样，在YOJ上进行，现收集同学们有空时间。~~

限时练习时间：11月28日19:00 ~ 21:00
题目数量：4 题目难度比期中考试略大
题目地址：http://172.18.215.225:8080/questions
评测系统从维护到周六下午3点，比赛时间开启8个评测线程。大家不要拥挤地交，请在本地测试好再提交

3、接下来课程的presentation我们按照期中考试成绩排序，前面的同学请准备好一个专题内容进行讲解，时间为5分钟。

4、之前所有的实验都可以补交，命名要求相同。
命名要求：13331314_叶嘉祺_EXn_v0.zip
参数n指的是第几次实验，1则是实验1，2则是实验2
参数v0指的是第一次提交，v1则是第二次提交

之前提交的文件夹全部改成压缩包形式。
压缩使用zip格式
解压之后应该只有一层目录，也就是不出现压缩包同名的文件夹。

之前所有的题目均可补交，请大家不用再问了。凡是迟交的同学分数表上都可能没有成绩或者成绩为0分，因为我们是分开批改，且批改是采用原始提交版本。所以，请大家以后按时提交作业，不要在ddl之后发邮件，这样非常混乱。

欢迎提问

计科：week7 第六次课总结 && 展示

1 week6 Sicily题目回顾

同学上来讲解题目。每题加5分，记在本周实验报告上。每个人不限题目数，能讲多少讲多少。

1.1 Strings

1.2 Loop

2 同学展示

2.1 Use Graphviz to draw graphs

展示者：郑兴达

展示内容：Introduction to Graphviz

2.2 Any others...

可以当场报名展示...

3 复习指导

3.1 考试时间

初定：11月21日

3.2 复习建议

复习书本内容，教过的内容要过一遍
老师讲课的ppt
之前做过的选择题练习
之前做过的sicily练习重新做一遍

4 Help Others公示

本次实验报告每人加分15，直到加满100。其他同学尽可效而仿之，但希望诚实真实，不辜负TA对你们的付出和信任。

软件：Final 总结

关于平时成绩

这个不用担心，平时成绩的平均分90分左右，之前所有改的作业的得分是按照真正高要求的中肯评分。说了挺多次都叫大家别太在意分数这件事情，确实，来大学学习是为分数的话，很悲哀。

分数这东西确实能够给你带来奖学金，确实会在你找工作的时候有一定作用。然而在谷歌这样的全球的公司是很轻视你的绩点的，特别是**大学，这些基本上没有用。

真真正正是我们核心竞争力的东西是最基础的一些问题，比如c语言的一些问题（我们做过一些）。

选择这个专业真正能够提升你个人核心力的，就是那些你很痛苦地写出来的程序，很纠结地解决的问题。

关于语言

我个人认为语言是一种表达**的工具，无论什么语言都是人类企图和计算机交流的工具。这个学期我们学习的是程序设计1，而不是叫做c语言。很明显c语言程序只是程序设计很小的一个部分。

所谓功夫在语言外，有个老师说的话很经典：“就像莫言获得诺贝尔文学奖一样，并不是因为莫言比我们会多几个汉字，或者是语言。” 因此，接下来的面向对象程序设计、离散数学、数据结构与算法、操作系统、计算机网络、数据库等等，很多都是语言外的功夫。

是不是c语言就学完了？
明显没有。

关于c++

下学期的重点应该是面向对象编程（不过可能杨老师的重点还在指针那些，很可能你们先学到的面向对象的思维就比较少了）。c++绝对不是简单地把printf变为cout而已，
这个下学期再说吧。

关于寒假作业

这个自己自由，我也不会改，也没有ddl；

改进一下自己的管理系统，尝试设计一个庞大的系统，比如教务系统。加入GUI之类的。其实我们学了c语言，很多同学写个教务系统可以秒杀学校那个垃圾玩意。
感兴趣的同学fork一下我YOJ的代码，你可以完善一下那个系统，或者用c语言重新写一次后台。（py的效率较低）
做一下通用链表那个实验，对下学期学习泛型编程很有作用。

期末project较多，不说多了，大家有问题在下面吐槽。哈哈哈哈哈。

可能给大家的作业或者难度偏大。嗯，其实写那么多字的题目还要费脑子想还是很花时间的。师兄也没那么变态总想着虐你们。嗯，过来人，希望大家坑得不要那么深。

给大家造成压力，说声对不起了。

计科：week10 第六次实验报告

计科：week10 C String and Functions

Description

The C programming language has a set of functions implementing operations on strings (character strings and byte strings) in its standard library. Various operations, such as copying, concatenation, tokenization and searching are supported. For character strings, the standard library uses the convention that strings are null-terminated: a string of n characters is represented as an arrays of an n + 1 elements, the last of which is a "NUL" character.

The only support for strings in the programming language proper is that the compiler translates quoted string constants into null-terminated strings.

From wikipedia

String is a very important thing when we are programming. All of the input and ouput are strings and any kind of data can be translated into a "String Form" include int, double and so on. In other words, an integer or a double number can be represented by a string simply.

Strings in C programming language is implemented by using an character array whose length is n+1(n represents the valid length of the string). So the operations on Strings in C can be treated as the operations for arrays. The following standard C library includes some basic Cstring operations.

This header file defines several functions to manipulate C strings and arrays.

Functions

Copying

memcpy
Copy block of memory (function )
memmove
Move block of memory (function )
strcpy
Copy string (function )...
strncpy
Copy characters from string (function )

Concatenation:

strcat
Concatenate strings (function )
strncat
Append characters from string (function )

Comparison:

memcmp
Compare two blocks of memory (function )
strcmp
Compare two strings (function )
strcoll
Compare two strings using locale (function )
strncmp
Compare characters of two strings (function )
strxfrm
Transform string using locale (function )

Searching:

memchr
Locate character in block of memory (function )
strchr
Locate first occurrence of character in string (function )
strcspn
Get span until character in string (function )
strpbrk
Locate characters in string (function )
strrchr
Locate last occurrence of character in string (function )
strspn
Get span of character set in string (function )
strstr
Locate substring (function )
strtok
Split string into tokens (function )

Other:

memset
Fill block of memory (function )
strerror
Get pointer to error message string (function )
strlen
Get string length (function )

Macros

NULL
Null pointer (macro )

Types

size_t
Unsigned integral type (type )

From cplusplus.com

Separate source file and header file

For header file, we just write the declaration of the functions and constants.
For source file, we implement the functions(function definitions)
For example:

func.h

#ifndef FUNC_H_INCLUDED
#define FUNC_H_INCLUDED
int plus(int a, int b);
#endif //FUNC_H_INCLUDED

func.cpp

#include "func.h"
int plus(int a, int b) {
    return a+b;
}

Basic Assignment (90pts):

This time your task is not to just use the functions simply. For this assignment, you will be given serveral function prototypes and your job is to implement the functions with the descriptions and smaples.

#ifndef STRING_H_INCLUDED
#define STRING_H_INCLUDED
/*
   Notice all the samples are use for function logic, not exactly the grammar
*/

/*
    function: myStrlen
    @description: Calculate the length of the string
    @input: const string s
    @output: the length of the string
    @sample input: "abcde\0abcde"
    @sample output: 5
    @Notice:  Function myStrlen() show check whether the input array is NULL.
    If so, you show return 0. Note that strlen() in string.h does not check NULL arrays.
*/
unsigned int myStrlen(const char s[]);

/*
    function: myStrcpy
    @description: copy one string to another
    @input: const string source
    @output: string destination
    @sample input: "a" "abc"
    @sample output: "abc"
    @Notice: You can not assign the array directly which will cause a runtime error.
*/
char * myStrcpy(char destination[], const char source[]);

/*
    function: myStrcat
    @input: const string source
    @output: string destination
    @sample input: "abcde" "abc"
    @sample output: "abcdeabc"
    @Notice: You can not assign the array directly which will cause a runtime error.
*/
char * myStrcat(char destination[], const char source[]);

/*
    function: myStrcmp
    @input: const string1 and const string2
    @output: if string1 is euqal to string2, output 0
             if string1 is greater than string2 ouput an integer > 0
             if string2 is greater than string1 output an integer < 0
    @sample input: "abc" "abc"
    @sample output: 0
*/
int myStrcmp(const char str1[], const char str2[]);

/*
    function: Mystrfind
    @input: cosnt string1 and const string2
    @output: if str2 is a substring of str1, output the first index in str1
             otherwise, ouput -1 which indicates can not find
    @sample input: "abcde" "cde"
    @sample output: 2
*/
int MyStrfind(const char str1[], const char str2[]);

/*
    function: LeftRotateString
    @input: string buff, an integer n which indicates the first n
    @output: put the first n chars to the end of the string
    @sample input: "abcdefg" 4
    @sample output: "efgabcd"
*/
void LeftRotateString(char *buff, int n);

/*
    function: myParseInt
    @input: a const string
    @output: an integer parse from a string
    @sample input: "123"
    @sample output: 123
    @Notice: You should notice show extreme conditions such as:
   1 null array input: the input is an array, the program will crash in the access to the null array, 
       so you need to judge whether the array is null before using the array.
   2 The sign: integer not only contain numbers, and may is the positive integer expressed
       starts with a '+' or '-', so if the first character is' - ', 
       to get the integer value is converted to a negative integer.
   3 illegal characters: the input string may contain characters that are not numbers. 
     Therefore, whenever you encounter these illegal characters, the program should stop converting.
   4 integer overflow: the number of input is the string of the form of input,
      so the input of a very long string will likely lead to overflow. You should set the return 
      value to MAX_INT or MIN_INT in the situation.
*/
int myParseInt(const char str[]);

/*
    function: myStrcontain
    @input: const string1 and const string2
    @output: a boolean value. id all chars in str2 are in str1, output true
             else output flase
    @sample input1: "ABCD" "BAD"
    @sample output1: 1
    @sample input2: "ABCD" "BCE"
    @sample output2: 0
*/
int myStrcontain(const char str1[], const char str2[]);

#endif // STRING_H_INCLUDED

Requirements:

You need to write a file myString.cpp for all the implements of the function prototypes.
In file myString.cpp you can not include any other standard C or C++ library, the file should be the same type like the following:
```
#include "myString.h"
#ifndef NULL
#define NULL 0
#endif // NULL

/*code*/
/*function definations*/
/*code end*/
```
You can not change the function prototypes.
Black box testing will be again applied this experiment. Please check your file names for three times.
Please do not add main function in your file, you can only add it when you are testing.

Deep Thinking(10pts)

For the function char * myStrcat(char destination[], const char source[]);, the array destination indicates the result of the function, why does the function add a return value char *? Why not void myStrcat(char destination[], const char source[]);?（Microsoft interview question）
Many functions in C standar library <string.h> do not check NULL array and they also do not carry about the size of the array. Why? And why strlen_s in c11 provide size check? (Google interview questions)
We have a small C program:

#include <iostream>
using namespace std;

int main() {
    char s1[100] = "abcdefg";
    char * s2 = "abcdefg";
    s1[0] = 'z';
    s2[0] = 'z';

    return 0;
}

What will happen when we run the program and why? What if we remove s2[0] = 'z';?
4. Why separate the source file and the header file? Think about the reasons. (Microsoft interview question)
5. How can we improve LeftRotateString or myStrcontain by other algorithm? (optional question, Microsoft interview questions)
Hint: String Reverse can be applied for LeftRotateString and hash table can be used for myStrcontain.

Report:

Just answer the questions in deep thinking part

Submit (Please pay attention to this part)

~~作业提交方式：作业由学委收好，再发到我邮箱.~~

提交方式：FTP

地址: ftp://172.18.182.75/
远程目录: Experiment/计科班/Experiment6
命名规范：13331314_叶嘉祺_EX6_v0.zip
注意v0代表你提交的版本号，第一次提交为v0，第二次为v1，以此类推
注意，要打包压缩程ZIP格式

--13331314_叶嘉祺_EX6.zip
  |--myString.cpp
  |--report.pdf

注意，文件压缩包里不能出现文件夹，只能包含一层目录

作业缓交或补交：每缓交一天 -5% 总分

Deadline

12月10日 18:00

最后

1、文件命名绝对不能错
2、你需要先学习如何写一个函数库。也就是第一个任务，如何编写.h文件和.cpp文件分开，然后在main函数中调用.h文件中的函数。说白了就是明白#include 这种实现的机制。
3、.h文件和.cpp文件请严格遵守要求中的约定。设定好的函数原型和.h文件请不要更改，并且理解为什么一字不能改？对于系统构架师（编写.h的工程师）和具体实现的工程师（编写.cpp文件工程师），以及测试工程师（编写main.cpp进行测试的工程师），和用户（调用库函数的人）之间是怎样合作，怎样沟通理解的？
4、请先自己尝试编写main函数进行测试（文件分离，再编写）

软件：week1 代码风格检查

week1 代码风格检查

唠叨几句：

大家叫师兄就好了，不要叫老师，听着别扭=_=。

上了实验课或者上了理论课，可能比较多的同学会有这样的想法：学了这些到底有什么用？好像觉得就只是敲几行不知道在干嘛的代码，输出一些不知道干嘛的结果。非常无聊。

对于这个问题，我还真不知道怎么回答。因为我大一的时候也是这样想的。其实软件工程专业，c语言是非常基础的一门语言，很多计算机类专业都以c语言作为入门语言。作为初学者，最重要的是对语言本身语法的了解和认识，算法的话，学有余力可以深究，这门课不会对算法有过高的要求。

我觉得现在同学们coding最大的动力来源于学业要求和把题目做对的成就感吧。在我们学校，你能真正利用编程做出产品或者有趣的东西，可能要到大二，那个时候你可能真的要迷恋上编程了。现在的话，我建议是，加油吧，好好学~慢慢的你会发现其实敲代码挺有意思的。

一、本周情况小结

第一周要求很低。基本上是熟悉练习系统Sicily，还有编辑器DevCpp的使用。对于这两个要求，我相信不会有什么问题。问题集中出现在同学们对c语言语法的理解上面。

下面列出出现频率较高的错误。

scanf("%d", &a);使用scanf函数读取输入内容，放到变量中的时候，记得添加取址运算符&
使用系统暂停函数system("pause");时，记得在头文件添加#include<stdlib.h>
建议尽量不要在Sicily上面直接编写代码，而是在DevCpp或者VS上面先编辑调试确定语法没问题，输入输入没问题的时候，在把代码全部复制粘贴到Sicily上面提交，不然会浪费很多时间。
注意学会用编辑器阅读程序语法或者运行错误。

二、用cpplint.py进行代码风格检查

Sicily系统没有在编程风格上作要求，只要你的代码能运行，输入输出没问题，就可能可以通过。但是这样会写出可能可读性很差的代码。因此我们TA强烈要求同学们一定要注意自己的代码编写的风格。

下面介绍一个工具的使用来进行代码风格检查。

步骤1：安装python

教程：安装python

要注意的是，教程中说的系统变量就是python的安装路径。

步骤2：检查python是否安装成功

打开命令行窗口（win键+R；输入cmd；回车）如下：
如果安装成功，在命令行窗口输入python将会出现以下的输出：

步骤3：下载cpplint.py

点击下载cpplint.py

步骤4：代码风格检查

把cpplint.py文件复制到你的程序代码所在的目录。比如：
打开命令行窗口，方法就是步骤2的第一点。导航到代码所在目录。

cd命令的含义是打开目录，dir命令的含义是查看该目录下地文件和文件夹
运行命令
```
python cpplint.py --filter=-whitespace/tab filename.c
```
注意finename.c是你的源代码的文件名

然后就会有如下的输出：

注意错误，如test.c:7: Line ends in whitespace. Consider deleting these extra spaces. [whitespace/end_of_line] [4]。test.c指的是文件名，7指的是行号，后面的 Line ends in whitespace. Consider deleting these extra spaces. [whitespace/ end_of_line] [4]指的是代码中出现的错误。

步骤5：根据输出的改善代码

根据输出的错误，逐行改进代码。直到错误数目为0。如Total errors found: 0：

步骤6：提交到Sicily

把通过google style的cpplint.py测试的代码，也就是Total errors found: 0，再把代码提交到Sicily。

总结

进行google style风格检测的目的是让同学们写出可读性良好的代码。按照上面的流程编写代码，能帮助你养成良好的编程习惯。希望同学们重视。

有任何问题欢迎评论。我们会持续改进。

参考

软件：13周补充知识 Undefined behavior and sequence points

What are "sequence points"?What is the relation between undefined behaviour and sequence points?

Reference ：Stackoverflow

C98 and C03

This answer is for the older versions of the C++ standard. The C++11 and C++14 versions of the standard do not formally contain 'sequence points'; operations are 'sequenced before' or 'unsequenced' or 'indeterminately sequenced' instead. The net effect is essentially the same, but the terminology is different.

What are Sequence Points?

The Standard says

At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. (§1.9/7)

Side effects? What are side effects?

Evaluation of an expression produces something and if in addition there is a change in the state of the execution environment it is said that the expression (its evaluation) has some side effect(s).

For example:

int x = y++; //where y is also an int

In addition to the initialization operation the value of y gets changed due to the side effect of ++ operator.

So far so good. Moving on to sequence points. An alternation definition of seq-points given by the comp.lang.c author Steve Summit:

Sequence point is a point in time at which the dust has settled and all side effects which have been seen so far are guaranteed to be complete.
What are the common sequence points listed in the C++ Standard ?
Those are:

at the end of the evaluation of full expression (§1.9/16) (A full-expression is an expression that is not a subexpression of another expression.)1
Example :
int a = 5; // ; is a sequence point here
in the evaluation of each of the following expressions after the evaluation of the first expression(§1.9/18) 2
a && b (§5.14)
a || b (§5.15)
a ? b : c (§5.16)
a , b (§5.18)
(in func(a,a++) , is not a comma operator, it's merely a separator between the arguments a and a++. The behaviour is undefined in that case if a is considered to be a primitive type)
at a function call (whether or not the function is inline), after the evaluation of all function arguments (if any) which takes place before execution of any expressions or statements in the function body (§1.9/17).

1 : Note : the evaluation of a full-expression can include the evaluation of subexpressions that are not lexically part of the full-expression. For example, subexpressions involved in evaluating default argument expressions (8.3.6) are considered to be created in the expression that calls the function, not the expression that defines the default argument

2 : The operators indicated are the built-in operators, as described in clause 5. When one of these operators is overloaded (clause 13) in a valid context, thus designating a user-defined operator function, the expression designates a function invocation and the operands form an argument list, without an implied sequence point between them.

What is Undefined Behaviour?

The Standard defines Undefined Behaviour in Section §1.3.12 as

behaviour, such as might arise upon use of an erroneous program construct or erroneous data, for which this International Standard imposes no requirements 3.

Undefined behaviour may also be expected when this International Standard omits the description of any explicit definition of behavior.
3 : permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or with- out the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

In short, undefined behaviour means anything can happen from daemons flying out of your nose to your girlfriend getting pregnant.

What is the relation between Undefined Behaviour and Sequence Points?
Before I get into that you must know the difference(s) between Undefined Behaviour, Unspecified Behaviour and Implementation Defined Behaviour.

You must also know that the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified.

For example:

int x = 5, y = 6;

int z = x++ + y++; //it is unspecified whether x++ or y++ will be evaluated first.

Another example here.

Now the Standard in §5/4 says

Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression.
What does it mean?

Informally it means that between two sequence points a variable must not be modified more than once. In an expression statement, the next sequence point is usually at the terminating semicolon, and the previous sequence point is at the end of the previous statement. An expression may also contain intermediate sequence points.

From the above sentence the following expressions invoke Undefined Behaviour.

i++ * ++i; // i is modified more than once
i = ++i    // same as above
++i = 2;   // same as above
i = ++i +1 // same as above
++++++i;   //parsed as (++(++(++i)))

i = (i,++i,++i); // Undefined Behaviour because there's no sequence point between `++i`(right most) 
and assignment to `i` (`i` gets modified more than once b/w two SP)

But the following expressions are fine

i = (i, ++i, 1) + 1; //well defined (AFAIK)
i = (++i,i++,i) // well defined 
int j = i;
j = (++i, i++, j*i); // well defined

Furthermore, the prior value shall be accessed only to determine the value to be stored.
What does it mean? It means if an object is written to within a full expression, any and all accesses to it within the same expression must be directly involved in the computation of the value to be written.

For example in i = i + 1 all the access of i (in L.H.S and in R.H.S) are directly involved in computation of the value to be written. So it is fine.

This rule effectively constrains legal expressions to those in which the accesses demonstrably precede the modification.

Example 1:

std::printf("%d %d", i,++i); // invokes Undefined Behaviour because of Rule no 2

Example 2:

a[i] = i++ // or a[++i] = i or a[i++] = ++i etc

is disallowed because one of the accesses of i (the one in a[i]) has nothing to do with the value which ends up being stored in i (which happens over in i++), and so there's no good way to define--either for our understanding or the compiler's--whether the access should take place before or after the incremented value is stored. So the behaviour is undefined.

Example 3 :

int x = i + i++ ;// Similar to above

软件：第13周额外作业

Dynamic Memory Allocation

1. Memory distribution map for a runtime program (very important for your 4-year study)

From Professor Wan Hai's courseWare

For example:

#include <malloc.h>
int main() {
   int a;  // allocated in stack
   int * b = (int *)malloc(sizeof(int));  // allocated in heap
   free(b);
   return;
}

int main() {
   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area1
   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area2
   return;
}

The example above cause a memory leak problem because pointer point to another memory area and the previous memory area1 is lost.

2. Malloc() to get memory from the heap

Notice that everytime you apply memory from heap, you should remember it and delete it(free) when your use of it is end.

int main() {
   int * a = malloc(sizeof(int));

   // code using a

   free(a);
}

Function Prototype

extern void *malloc(unsigned int num_bytes);

注意，对于一个函数，一定要看函数原型，函数原型里面包含了这个函数接口功能的很多信息。
这个函数的名称是malloc，动态分配内存
参数是unsigned int num_bytes，意思是分配的内存的字节数。
返回值是void 指针，理论是就是应该指向被分配的内存。

由于返回的指针是一种泛型编程**中的无类型指针，所以应该强制转换为你需要的类型。

注意：在一次malloc函数调用中，返回的一段内存是连续的

3. Memory Leak

From Wikipedia, the free encyclopedia
In computer science, a memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations[1] in such a way that memory which is no longer needed is not released. In object-oriented programming, a memory leak may happen when an object is stored in memory but cannot be accessed by the running code.[2] A memory leak has symptoms similar to a number of other problems (see below) and generally can only be diagnosed by a programmer with access to the program's source code.

Because they can exhaust available system memory as an application runs, memory leaks are often the cause of or a contributing factor to software aging.

Consequences

A memory leak can diminish the performance of the computer by reducing the amount of available memory. Eventually, in the worst case, too much of the available memory may become allocated and all or part of the system or device stops working correctly, the application fails, or the system slows down vastly due to thrashing.

Memory leaks may not be serious or even detectable by normal means. In modern operating systems, normal memory used by an application is released when the application terminates. This means that a memory leak in a program that only runs for a short time may not be noticed and is rarely serious.

Much more serious leaks include those:

where the program runs for an extended time and consumes additional memory over time, such as background tasks on servers, but especially in embedded devices which may be left running for many years
where new memory is allocated frequently for one-time tasks, such as when rendering the frames of a computer game or animated video
where the program can request memory — such as shared memory — that is not released, even when the program terminates
where memory is very limited, such as in an embedded system or portable device
where the leak occurs within the operating system or memory manager
when a system device driver causes the leak
running on an operating system that does not automatically release memory on program termination. Often on such machines if memory is lost, it can only be reclaimed by a reboot, an example of such a system being AmigaOS.[citation neede

From 百度百科

内存泄漏也称作“存储渗漏”，用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元。直到程序结束。（其实说白了就是该内存空间使用完毕之后未回收）即所谓内存泄漏。

内存泄漏形象的比喻是“操作系统可提供给所有进程的存储空间正在被某个进程榨干”，最终结果是程序运行时间越长，占用存储空间越来越多，最终用尽全部存储空间，整个系统崩溃。所以“内存泄漏”是从操作系统的角度来看的。这里的存储空间并不是指物理内存，而是指虚拟内存大小，这个虚拟内存大小取决于磁盘交换区设定的大小。由程序申请的一块内存，如果没有任何一个指针指向它，那么这块内存就泄漏了。

从用户使用程序的角度来看，内存泄漏本身不会产生什么危害，作为一般的用户，根本感觉不到内存泄漏的存在。真正有危害的是内存泄漏的堆积，这会最终消耗尽系统所有的内存。从这个角度来说，一次性内存泄漏并没有什么危害，因为它不会堆积，而隐式内存泄漏危害性则非常大，因为较之于常发性和偶发性内存泄漏它更难被检测到。

简单来讲，内存泄露就是动态分配的内存没有在使用完之后进行释放，导致内存垃圾堆积。

这样的危害有可能直接让你的操作系统崩溃掉（可以自己做下实验）

For example:

int main() {
    int * c = (int *)malloc(sizeof(int) * 100);
    c = NULL;
    while(1);
}

上述代码分配了100个int类型大小的连续内存单元，我们可以通过这个方式分配动态数组。上述代码分配的就是可以理解成100个int的数组。

运行上述程序，在运行到while(1)时候发生了内存泄露，因为原来动态分配的内存地址丢失了！你的程序无法再获得那100个在堆中申请的内存单元。可是这些内存单元仍然占据着内存，也就是内存垃圾。在编写动态分配的程序时，很容易出现这样的错误。正确做法是在这个指针不用的情况下，将其free。

int main() {
    int * c = (int *)malloc(sizeof(int) * 100);
    free(c);
    c = NULL;
    while(1);
}

有时候有些内存泄露是自己看不出来的，特别当函数变得复杂起来的时候。
下列程序为死亡程序，可以试试运行看看自己电脑的内存变化。

#include <stdio.h>
#include <malloc.h>
int main() {
 while(1) {
    malloc(100);
  }
  return 0; 
}

3. List（链表或线性表）

An introduction to List

In computer science, a list or sequence is an abstract data type that represents an ordered sequence of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream.[1]:§3.5 Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item.

A singly linked list structure, implementing a list with 3 integer elements.
The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists.

Many programming languages provide support for list data types, and have special syntax and semantics for lists and list operations. A list can often be constructed by writing the items in sequence, separated by commas, semicolons, or spaces, within a pair of delimiters such as parentheses '()', brackets '[]', braces '{}', or angle brackets '<>'. Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array. In object-oriented programming languages, lists are usually provided as instances of subclasses of a generic "list" class, and traversed via separate iterators. List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications. In some contexts, such as in Lisp programming, the term list may refer specifically to a linked list rather than an array.

In type theory and functional programming, abstract lists are usually defined inductively by two operations: nil that yields the empty list, and cons, which adds an item at the beginning of a list.[2]

From wikipedia

The operations about list are appending, deleting, modifying, querying.

we use this simple list again:

If delete the second node:

node* save = head->next;
head->next = head->next->next;
free(save);

2.If append a node at the end of the list

node* last = head;
while(last->next != NULL) {
    last = last->next;
}

last->next = (node*)malloc(sizeof(node));
last->next->data = data;
last->next->next = NULL;

3.Traversal

node * temp = head;
while(temp != NULL) {
    Traversal(temp);
    temp = temp->next;
}

Deep Thinking(120pts, 20 for each)

1.Look at the following function:

static void myFunction() { int a; }

(1) Which area in memory does the function store? And which dose the variable int a?
function store : Code Area
variable 'int a': (function) stack
(2) What's the advantages of using static functions?

static says the function has internal linkage. This means it will not be linked with other uses of the same identifier in other files (translation units).
For example, suppose in Tree.c I have a function that operates on Tree structures, and I have some local subroutine called UpdateNode that operates on part of the Tree. Further suppose that in List.c, I have a function that operates on List structures, and it also has some local subroutine called UpdateNode that is just for List structures, not for Tree structures.
If I left both of these subroutines with external linkage, the linker would complain about multiple definitions. By marking them with internal linkage with static, this problem is avoided.
From stack overflow

2. Look at the following program which is attempt to allocate a dynamic array.

#include <malloc.h>

int main() {
    char ** strs;
    int n ,m;
    int i;

    scanf("%d%d", &n, &m);

    strs = (char **)malloc(sizeof(char *) * n);

    for(i = 0; i < n; i++) {
        strs[i] = (char *)malloc(sizeof(char) * m);
    }


   // code for the 2d array
   // free operations omited
    return 0;
}

Can we create an 2D array in the heap using this way? Give your explanations and give another way that can allocate a dynamic 2D array
No, the 2D dynamic array is discontinuous in 1D memory space which does not fit the accurate 2D array definition.

issues:

When call memset or other memory operation on the whole block of memory, you can not get your expected result.
When pass the array into a function as parameter.
Look at the following program:

#include <malloc.h>

void test(char strs[][20], int m, int n) {
    int i, j;
    for(i = 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            printf("%p ", &strs[i][j]);
        }
        printf("\n");
    }
}

int main() {
    char ** strs;
    int n ,m;
    int i, j;

    scanf("%d%d", &n, &m);

    strs = (char **)malloc(sizeof(char *) * n);

    printf("%p\n", strs);

    for(i = 0; i < n; i++) {
        strs[i] = (char *)malloc(sizeof(char) * m);
    }

    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            printf("%p ", &strs[i][j]);
        }
        printf("\n");
    }

    printf("\n");

    test(strs, 10, 20);

    printf("\n");



   // free operations omited
    return 0;
}

Result:

10 20
0xe04010
0xe04070 0xe04071 0xe04072 0xe04073 0xe04074 0xe04075 0xe04076 0xe04077 0xe04078 0xe04079 0xe0407a 0xe0407b 0xe0407c 0xe0407d 0xe0407e 0xe0407f 0xe04080 0xe04081 0xe04082 0xe04083 
0xe04090 0xe04091 0xe04092 0xe04093 0xe04094 0xe04095 0xe04096 0xe04097 0xe04098 0xe04099 0xe0409a 0xe0409b 0xe0409c 0xe0409d 0xe0409e 0xe0409f 0xe040a0 0xe040a1 0xe040a2 0xe040a3 
0xe040b0 0xe040b1 0xe040b2 0xe040b3 0xe040b4 0xe040b5 0xe040b6 0xe040b7 0xe040b8 0xe040b9 0xe040ba 0xe040bb 0xe040bc 0xe040bd 0xe040be 0xe040bf 0xe040c0 0xe040c1 0xe040c2 0xe040c3 
0xe040d0 0xe040d1 0xe040d2 0xe040d3 0xe040d4 0xe040d5 0xe040d6 0xe040d7 0xe040d8 0xe040d9 0xe040da 0xe040db 0xe040dc 0xe040dd 0xe040de 0xe040df 0xe040e0 0xe040e1 0xe040e2 0xe040e3 
0xe040f0 0xe040f1 0xe040f2 0xe040f3 0xe040f4 0xe040f5 0xe040f6 0xe040f7 0xe040f8 0xe040f9 0xe040fa 0xe040fb 0xe040fc 0xe040fd 0xe040fe 0xe040ff 0xe04100 0xe04101 0xe04102 0xe04103 
0xe04110 0xe04111 0xe04112 0xe04113 0xe04114 0xe04115 0xe04116 0xe04117 0xe04118 0xe04119 0xe0411a 0xe0411b 0xe0411c 0xe0411d 0xe0411e 0xe0411f 0xe04120 0xe04121 0xe04122 0xe04123 
0xe04130 0xe04131 0xe04132 0xe04133 0xe04134 0xe04135 0xe04136 0xe04137 0xe04138 0xe04139 0xe0413a 0xe0413b 0xe0413c 0xe0413d 0xe0413e 0xe0413f 0xe04140 0xe04141 0xe04142 0xe04143 
0xe04150 0xe04151 0xe04152 0xe04153 0xe04154 0xe04155 0xe04156 0xe04157 0xe04158 0xe04159 0xe0415a 0xe0415b 0xe0415c 0xe0415d 0xe0415e 0xe0415f 0xe04160 0xe04161 0xe04162 0xe04163 
0xe04170 0xe04171 0xe04172 0xe04173 0xe04174 0xe04175 0xe04176 0xe04177 0xe04178 0xe04179 0xe0417a 0xe0417b 0xe0417c 0xe0417d 0xe0417e 0xe0417f 0xe04180 0xe04181 0xe04182 0xe04183 
0xe04190 0xe04191 0xe04192 0xe04193 0xe04194 0xe04195 0xe04196 0xe04197 0xe04198 0xe04199 0xe0419a 0xe0419b 0xe0419c 0xe0419d 0xe0419e 0xe0419f 0xe041a0 0xe041a1 0xe041a2 0xe041a3 

0xe04010 0xe04011 0xe04012 0xe04013 0xe04014 0xe04015 0xe04016 0xe04017 0xe04018 0xe04019 0xe0401a 0xe0401b 0xe0401c 0xe0401d 0xe0401e 0xe0401f 0xe04020 0xe04021 0xe04022 0xe04023 
0xe04024 0xe04025 0xe04026 0xe04027 0xe04028 0xe04029 0xe0402a 0xe0402b 0xe0402c 0xe0402d 0xe0402e 0xe0402f 0xe04030 0xe04031 0xe04032 0xe04033 0xe04034 0xe04035 0xe04036 0xe04037 
0xe04038 0xe04039 0xe0403a 0xe0403b 0xe0403c 0xe0403d 0xe0403e 0xe0403f 0xe04040 0xe04041 0xe04042 0xe04043 0xe04044 0xe04045 0xe04046 0xe04047 0xe04048 0xe04049 0xe0404a 0xe0404b 
0xe0404c 0xe0404d 0xe0404e 0xe0404f 0xe04050 0xe04051 0xe04052 0xe04053 0xe04054 0xe04055 0xe04056 0xe04057 0xe04058 0xe04059 0xe0405a 0xe0405b 0xe0405c 0xe0405d 0xe0405e 0xe0405f 
0xe04060 0xe04061 0xe04062 0xe04063 0xe04064 0xe04065 0xe04066 0xe04067 0xe04068 0xe04069 0xe0406a 0xe0406b 0xe0406c 0xe0406d 0xe0406e 0xe0406f 0xe04070 0xe04071 0xe04072 0xe04073 
0xe04074 0xe04075 0xe04076 0xe04077 0xe04078 0xe04079 0xe0407a 0xe0407b 0xe0407c 0xe0407d 0xe0407e 0xe0407f 0xe04080 0xe04081 0xe04082 0xe04083 0xe04084 0xe04085 0xe04086 0xe04087 
0xe04088 0xe04089 0xe0408a 0xe0408b 0xe0408c 0xe0408d 0xe0408e 0xe0408f 0xe04090 0xe04091 0xe04092 0xe04093 0xe04094 0xe04095 0xe04096 0xe04097 0xe04098 0xe04099 0xe0409a 0xe0409b 
0xe0409c 0xe0409d 0xe0409e 0xe0409f 0xe040a0 0xe040a1 0xe040a2 0xe040a3 0xe040a4 0xe040a5 0xe040a6 0xe040a7 0xe040a8 0xe040a9 0xe040aa 0xe040ab 0xe040ac 0xe040ad 0xe040ae 0xe040af 
0xe040b0 0xe040b1 0xe040b2 0xe040b3 0xe040b4 0xe040b5 0xe040b6 0xe040b7 0xe040b8 0xe040b9 0xe040ba 0xe040bb 0xe040bc 0xe040bd 0xe040be 0xe040bf 0xe040c0 0xe040c1 0xe040c2 0xe040c3 
0xe040c4 0xe040c5 0xe040c6 0xe040c7 0xe040c8 0xe040c9 0xe040ca 0xe040cb 0xe040cc 0xe040cd 0xe040ce 0xe040cf 0xe040d0 0xe040d1 0xe040d2 0xe040d3 0xe040d4 0xe040d5 0xe040d6 0xe040d7

This is the Problem.

One possible way:

strs=(char (*)[10])malloc(n*10*sizeof(int)); // n rows and 10 cols

3.Why use a list instead of an array? What's the advantages and disadvantages of them respectively?
Both store a sequence of elements, but using different techniques.
An array stores elements in successive order in memory, i.e. it looks like follows:

--------------------------------------------------------------------------------------
|  item 1  |  item 2  |  item 3  |  ...  ...  |  item x  | //here comes other stuff
--------------------------------------------------------------------------------------

This means, elements are one after another consecutive in memory.

A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":

                                 ------------
------------        ----------    |  item 4  |
|  item 1  |        | item 2 |    |  next ---+----...
|  next ---+------->| next   |    ------------
------------        ---+------      ^
                       |            |
                       |            |
                       v            |
                       ----------   |
                       | item 3 |   |
                       | next --+---+
                       ----------

Both store a sequence of elements, but using different techniques.

An array stores elements in successive order in memory, i.e. it looks like follows:

--------------------------------------------------------------------------------------
|  item 1  |  item 2  |  item 3  |  ...  ...  |  item x  | //here comes other stuff
--------------------------------------------------------------------------------------

This means, elements are one after another consecutive in memory.

                                  ------------
------------        ----------    |  item 4  |
|  item 1  |        | item 2 |    |  next ---+----...
|  next ---+------->| next   |    ------------
------------        ---+------      ^
                       |            |
                       |            |
                       v            |
                       ----------   |
                       | item 3 |   |
                       | next --+---+
                       ----------

This means, the elements can be spread all over the memory and are not stored at specific memory locations.

Now that we know this, we can compare some usual operations on sequences of elements:

Accessing an element at a specific index: Using an array, we simply compute the offset for this index and have the element at the index. This is very cheap. With a list on the other hand, we do not know a priori where the element at index is stored (since all elements can be anywhere in memory), so we have to walk the list item by item until we find the element at the index. This is an expensive operation.
Adding a new element at the end of the sequence: Using an array this can lead to the following problem: Arrays are usually of fixed size, so if we have the situation that our array is already completely filled (see //here comes other stuff), we probably cant put the new element there because there might already be something else. So, maybe we have to copy the whole array. However, if the array is not filled, we can simply put the element there. Using a list, we have to generate a new "list item", put the element into it and set the next pointer of the currently last element to this new list item. Usually, we store a reference to the currently last element so that we don't have to search through the whole list to find it. Thus, inserting a new element is no real problem with lists.
Adding a new element somewhere in the middle: Let's first consider arrays: here, we might get into the following situation: We have an array with elements 1 to 1000:
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
Now, we want to insert 4.5 between 4 and 5: This means, we have to move all elements from 5 to 1000 one position right in order to make space for the 4.5:

 1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free
                  ||
                  vv
 1 | 2 | 3 | 4 | 4.5  | 5 | 6 | ... | 999 | 1000 | free

Moving all these elements, is a very expensive operation. So better don't do this too often.
Now we consider, how a list can perform this task: Let's say we have currently the following list:

 1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000

Again, we want to insert 4.5 between 4 and 5. This can be done very easily: We generate a new list item and update the pointers/references:

 1 -> 2 -> 3 -> 4        5 -> ... -> 999 -> 1000
                |        ^
                +-> 4.5 -+

We have simply created a new list element and generated sort of "bypass" to insert it - very cheap (as long as we have a pointer/reference to the list item the new element will be inserted after).

So, let's sum up: Linked lists are really nice when it comes to inserting at random positions (as long as you have a pointer to the adequate list item). If your operation involves adding lots of elements dynamically and traversing all elements anyway, a list might be a good choice.

An array is very good when it comes to index accesses. If your application needs to access elements at specific positions very often, you should rather use an array.

Notable things:

Solving the fixed-size problem for arrays: As mentioned before, (raw) arrays are usually of fixed size. However, this problem is nowadays no real point anymore, since almost all programming languages provide mechanisms to generate arrays that grow (and possibly shrink) dynamically - just as needed. This growing and shrinking can be implemented such that we have amortized runtime of O(1) for inserting and removing elements (at the end of the array) and such that the programmer doesn't have to call grow and shrink explicitly.
Since lists provide such nice properties for insertions, they can be used as underlying data structures for search trees, etc. I.e. you construct a search tree, whose lowest level consists of the linked list.

4.
(1)Why is it necessary to have a heap, i.e. why not use stack only?
The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.

The heap is memory set aside for dynamic allocation. Unlike the stack, there's no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.

Each thread gets a stack, while there's typically only one heap for the application (although it isn't uncommon to have multiple heaps for different types of allocation).

To answer your questions directly:

To what extent are they controlled by the OS or language runtime?
The OS allocates the stack for each system-level thread when the thread is created. Typically the OS is called by the language runtime to allocate the heap for the application.
What is their scope?
The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.
What determines the size of each of them?
The size of the stack is set when a thread is created. The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system).
What makes one faster?
The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or free. Also, each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor's cache, making it very fast. Another performance hit for the heap is that the heap, being mostly a global resource, typically has to be multi-threading safe, i.e. each allocation and deallocation needs to be - typically - synchronized with "all" other heap accesses in the program.

(2)What's the max size of the stack or the heap for a c program in your computer? Can you revise it?
In linux,

xinyuan@xinyuan-pc:~/Desktop/testAll$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 15333
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 15333
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

revise stack example

ulimit -s 1000

max heap size is usually the virtual memory of your computer.

(3)Will deep recursive program really lead to stack overflow?Why? (The answer is no)
No, not really. The following program will cause stack overflow in normal mode compile.
But if we add compile parameter gcc -O1 -foptimize-sibling-calls recursion.c, there will not be stack overflow.

#include <stdio.h>

typedef unsigned long long int RES;

RES recursion(RES a) {
  if(a == 1000000000) {
    return a;
  } else {
    return recursion(a+1);
  }
}

int main(int argc, char const *argv[]) {
  recursion(0);
  return 0;
}

Also we can calculate how large is it in one function stack, think about it.

5.(optional) How to use an array to create a list know as a static list in logic?
For example:

node a[100];
head = a[0];
a[0]->next = 2;   // an array index

Deadline and Submit

Dec 19th, 2015 18:00

Submit to ftp

Filename : 13331314_叶嘉祺_DMA.pdf

Questions

周一早上随机提问同学相关知识

软件：week11 问题反馈和讨论

Reserved...

Google IPv6-hosts

https://github.com/LGA1150/IPv6-hosts

记得强制HTTPS方式访问！
chrome://net-internals/#hsts

SDCS2015, 15331058

软件：week6 实验：程序流程图和伪代码

实验二：程序流程图和伪代码

实验目的：当大家学习了程序的控制结构之后，代码就变得复杂起来。在这时，我们解决问题就需要有很严密的逻辑思维。程序流程图和伪代码就是帮助我们去描述我们解决问题的方法（也称为算法）的工具。本次实验在于让大家学习如何使用这些工具，这对大家以后的编程有很大的帮助。

1.Flowchart(程序流程图)

A flowchart is a type of diagram that represents an algorithm, workflow or process, showing the steps as boxes of various kinds, and their order by connecting them with arrows. This diagrammatic representation illustrates a solution model to a given problem. Flowcharts are used in analyzing, designing, documenting or managing a process or program in various fields.

From wikipedia

Detailed Description: flowchat

There is an example:

And this is the flowchart:

2.Pseudocode (伪代码)

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

From wikipedia

There is an example:

We can describe this question by this way rather than write a C program immediately:

main {
input two integers height and n
initialize answer = 0
loop for n times {
    input tree_height
    if height >= tree_height:
       answer = answer + 1
  }
print answer
}

Pseudocode is used to express your thought, you do not need to care about the grammar.

Pre Assignment

Learn about Flowchart and Pseudocode.

Assignment 0 (20pts)

Choose one question from soj.me in week6 in our course and then write the Pseudocode.

Assignment 1 (35pts)

option 1

Translate the following flowchart into Pseudocode

option 2

Translate the following flowchart into Pseudocode and C programming language program.

Description

Several surveys indicate that the taller you are, the higher you can climb the corporate ladder. At TALL Enterprises Inc. this "de facto standard" has been properly formalized: your boss is always at least as tall as you are. Furthermore, you can safely assume that your boss earns a bit more than you do. In fact, you can be absolutely sure that your immediate boss is the person who earns the least among all the employees that earn more than you and are at least as tall as you are. Furthermore, if you are the immediate boss of someone, that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody's boss, then you have no subordinates. As simple as these rules are, many people working for TALL are unsure of to whom they should be turning in their weekly progress report and how many subordinates they have. Write a program that will help in determining for any employee who the immediate boss of that employee is and how many subordinates they have. Quality Assurance at TALL have devised a series of tests to ensure that your program is correct. These test are described below.

May be you can not write out the problem, the only work you will do is write out this program from the following flowchart(Since there are many methods to sort, so you can use one of them, the flowchart does not display in the flow chat, instead a dashed line).

Flowchart

Simple input and output

Input

2
3
123456 14323 1700000
123458 41412 1900000
123457 15221 1800000
123458
4
200002 12234 1832001
200003 15002 1745201
200004 18745 1883410
200001 24834 1921313
200002

Output

(0,2)
(200004,0)

Assignment 2 (35pts)

Draw a flowchart from the following C language program which instruct the movement of a robot going on patrol along the wall.

#include <stdio.h>

/* this program is used for a robot to walk along
   a wall next to him.
*/

/* Note that if the robot's eyes get something 
   whose distance is less than 40cm, there must
   be an obstacle(wall).
*/
const int SENSOR_DISTANCE = 40; // 40 cm

/*
  predifined methods:
  1. void lookLeft() and void lookRight()
  function: Let the robot to look at the left or right side.
  2. void lookForward()
  function: let the robot to look forward.
  3. int getDistance()
  function: get a distance from the eye to another.
  object if there is one.
  4. void moveStraight()
  function: go straight for some distance.
  5.int shutDown()
  function: shut down the robot.
*/



int main() {
  /* we assume that for the initial state, either 
     the robot's left side or the right side is 
     toward the wall.

     wall = 0 means that the wall is at the left side
     wall = 1 means that the wall is at the right side
  */
  int wall;

  lookLeft();
  if(getDistance() < SENSOR_DISTANCE) {
    wall = 0;
  } else {
    lookRight();
    wall = 1;
  }

  if(wall == 0) {
    while(shutDown() != 1) {
      moveStraight();
      while(1) {
        lookLeft();
        if(getDistance() < SENSOR_DISTANCE) {
          lookForward();
          if(getDistance() < SENSOR_DISTANCE) {
            turnRight();
          } else {
        break;
      }
        } else {
      turnLeft();
        }
      }
    }
  } else {
    do {
      moveStraight();
      while(1) {
        lookRight();
        if(getDistance() < SENSOR_DISTANCE) {
          lookForward();
          if(getDistance() < SENSOR_DISTANCE) {
            turnLeft();
          } else {
        break;
      }
        } else {
      turnRight();
        }
      }
    } while (shutDown() != 1);
  }


  return 0;
}

Extended Assignment (10pts)

option 1

Draw a flowchart and write Pseudocode as well as a C language program for the following description.

option 2

Simplify the logic in Assignment 2 and then draw a new flowchart and rewrite the C code.（Reduce at least one level of logic nesting）

Discussion，Cooperation and Summary (15pts)

In this part, you will have some options, if you do more options, you will learn more and get more marks.
You should note this part in your report

option 1: Github Discussion

Comment at this issue and decribe a problem that you meet and how you solve detailedly.

Notice that

you should not copy and paste your personal report simply.
you should not write a very simple one and your comment will be deleted if you do that.
you should not post meaningless questions.

option 2: Simple Presentation

Have a simple presentation in the lab class on Monday (4 persons limited). And after the presentation, everyone is encouraged to ask questions and you can get bonus by asking good questions.

Notice that

The presentation is no more than 5 minutes and there will be 5 extra minutes for discussion.
You should prepare much for it.
First come, first get the opportunity.

option 3: Helping others

You can help others to slove any problems the will meet. Detailedly decribe the quesion, the solution and your personal experience as well.

Notice that

it's no need to consult with others that I help you, you help you to get marks. You can simply send email to me and I will give you the marks.

option 4: Personal Summary

Write personal summary for yourself.
List at least 10 problems that you have met in your learning in c language and decribe the solution as well.

Notice that

you should not have ten very simple problems, you must let me know your learning method and also the method to solve problems.

Report(50% pts for your project ducumenting):

There will be no Report Template this time which means it's all depends on yourself.

Notice that

the report is the most important document for your project, you should pay more attention to it.
you are supposed to write a report that is friendly to your 'users', which means that you need to consider about the typesetting, the logical structure of the content.
There should contain one item, self grading that you should give a score to evaluate your job as well as a reason.

For example: sinew

Flowchart Tool: Process On

Process on is a good tool for drawing flowchart.
link

Submit List

Notice that:
13331314 means your student id.
the first assignment need to name your file with your chosen problem id.

Deadline and how to submit:

18:00 on Nov 7th, 2015

学习委员整理好发到邮箱：[email protected]
不接受作业单独发到邮箱

Notification:

Submit after deadline will cause a 30% penalty.
If your file structure of filename is wrong, you will probably get 0 in that part.
Any questions, you can ask us and email is better.
Full mark will be 100, but you may get more than 100 within this project.
You can use any tool include word, process on to draw a flowchart. You can use any form to write your Pseudocode but should be of high readability. If TA can not understand your Pseudocode clearly, you will get low points.(you can use Chinese to write Pseudocode if you like).

计科：week4 第二次实验内容

第四次课实验：学习冒泡排序算法

要求：

1. 具体实现方式可以上网查
2. 实验报告写上你对算法的理解
3. 程序：输入n，表示有n个数输入，接着输入n个随机的整数。输出：从小到大的有序的数，空格分隔。
4. 拓展：改进版本的冒泡
5. 提交：实验报告+程序。
6. deadline: 本周日晚12点。

课件下载

软件：week7 实验：c程序测试与断点调试

实验3：c程序断点调试

C程序完成一般思路

对于复杂的逻辑需求，先写伪代码或者画程序流程图得到清晰的逻辑结构。
自顶向下逐步求精解决问题（大问题分解为可解决的小问题），写出C程序。
修改C程序的编译错误。
通过测试，修改C程序的逻辑错误。

高效c语言编程方法

1、命令行编译与高效文本编辑器

为什么使用命令行编译？

可以获得比集成编译系统（IDE）更高的自由度。
为之后的linux编程工具链打下基础。
更好的理解c程序编译执行过程。

配置方法：
1、打开Dev Cpp，并且找到对应的安装路径。

2、找到定义的MinGW目录下的bin目录这个是dev cpp的核心编译器。

3、配置系统环境变量，在系统的高级选项中找到path（可见第一周python配置方法）

4、打开cmd窗口，输入gcc --version输出编译器版本信息，配置完成。

编译方法：
1、找到一个c源代码所在的文件夹，在文件夹中按住shift+鼠标右键，选择在此处打开命令行。
2、输入gcc + 空格 + 你要编译的文件 -o 编译出来之后的可执行程序的名字，如：gcc main.c -o main.exe（如果省略-o后面的命令，则会生成a.exe）

3、在命令行中输入 main.exe 即可运行程序。

高效文本编辑器：
高效文本编辑器是一些专门为编程者设计的编辑器，他们具有自动缩进、自动补全代码、自由配置的特点，深受程序员喜爱。这些编辑器不仅仅c语言使用，c++、pyhton、html、markdown和许多其他语言都适用。他们有，vim、emacs、sublime等。

现在我们介绍sublime-text 3，这是一款收费软件，可是有无限试用期。

下载和使用请自行百度。

2、测试数据的文件输入输出代替键盘输入输出（重点）

现在大家做题一般的输入方法就是，按照西西里的测试例子，键盘输入，当程序错误的时候需要一次次输入非常繁琐，现在给大家提供一种高效而且重要的方法，文件流输入代替键盘流输入。

其实，在抽象的层面上，键盘输入、文件输入和网络输入等都是IO，是等价的。我们可以利用这个进行文件代替键盘输入。

1、在刚才我们编译的程序之中，我们生成了main.exe的程序。建设现在我们的程序是做a-b的简单运算。我们现在在源代码的同一个目录下新建一个文件"input.txt"。我们打开文件输入两个数100和99。

2、接着我们在命令行输入命令main.exe < input.txt。我们很惊喜地发现，程序自动输出了1,我们不需要手动去使用键盘输出。

对于长而复杂的输入，这无疑是一个简化的过程。

对于文件输出，同样是可以的 'main.exe < input.txt >output.txt'

3、断点调试法（课题讲解）

错误示例代码（来源于同学）

#include<stdio.h>

struct employee {
    long id, salary, height, boss, subordinate;
};
int main() {
    struct employee a[10000], temp, current_deal, potential_boss, search;
    int total_test, current_test, current_e, e_num, id_search;
    int i, k, j, m, n, t, u;
    for (u = 1;u <= 10000;u++) {
        a[u].subordinate = 0;
        a[u].boss = 0;
        a[u].height = 0;
        a[u].id = 0;
        a[u].salary = 0;
    }
    printf("How many test do you want to have?\n");
    scanf("%d", &total_test);
    current_test = 1;
    while (current_test <= total_test) {
        printf("please input the number of employees\n");
        scanf("%d", &e_num);
        current_e = 1;
        for (i = 1;current_e <= e_num;i++) {
            printf("please input No.%d empolyees' id, salary, height(seperated by space)\n", i);
            scanf("%d %d %d", &a[i].id, &a[i].salary, &a[i].height);
            current_e ++;
        }  for (k = 1;k <= (e_num - 1);k++) {
            for(j = 1;j <= (e_num - 1);j++) {
                if(a[j].salary > a[j+1].salary) {
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp; 
                }
            }
        }   

             for (m = 1;m <= e_num;m++) {
                     current_deal = a[m];
                for(n = e_num;n <= (m + 1);n--) {
                            potential_boss = a[n];
                    if(current_deal.height <= potential_boss.height) {
                        a[m].boss = potential_boss.id;
                        a[n+1].subordinate += 1;
                     }
                 }  
             }
             printf("please input the id you want to search for its boss and subordinates\n");
             scanf("%d", &id_search);
             for (t = 1;t <= e_num;t++) {
                if (id_search == a[t].id) {
                    search = a[t];
                 }
             }
             printf("(%d,%d)\n", search.boss, search.subordinate);
             current_test ++;

    }    
        return 0;
}

1、设置断点
2、运行程序
3、添加监控变量
4、执行程序、单步运行

关于期中考

1003输入0结束循环那里，卡了，输入0也输出0，导致一直wrong answer。

软件：week3 实验：数学函数与格式输出

问题

不少同学还是没有看gitub的issue，那些scanf和printf问题上周issue已经说过，不看是自己吃亏。看了不懂再提出问题，总比在实验课上写scanf("char a = %c")还纠结为什么错高效率很多。

其次，再次强调一下，扩展题目也是自己自学为主，不强制要求做，不占期末分数，没有ddl，也没有提交规定。这个题目老师也没有要求我们出，出这个题主要目的是使让大家提前预习前面的知识，提前自学完，到老师讲概念定义的理论时候，你就不会晕，也知道怎么回事。这是一种高效率的学习方法。做不出来没关系，学完到一定程度再做。

另外，我每周会放一些往年的期中或者期末考试题在扩展题上，供大家参考。

问题1 不懂得使用搜索工具

编程语言学习不是像高中时候学语文数学那样拿着书，听老师讲就行了。有很多知识老师是不讲的，而且书上面也没有。比如，一个库函数 double log(double _x)，书本或者老师不会教你怎么怎么用的，必须要你自己去百度或者谷歌。

搜索引擎：
谷歌、百度

参考it界的学习网站：
Stack Overflow
CSND 博客
 开源**

问题2 不会看编译错误

编译器的一个很重要的功能就是检查你写的代码是否符合这个语言定义的语法，一定要学会看编译器的提示信息，例如：

1.c:12:3: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘scanf’
   scanf("%c%d%f%ld%lld%lf", &a, &b, &c, &d, &e, &f);

这句话的意思你不要晕，看到一大串就慌了，这不是应该有的学习态度。你要仔细去理解。这句话说在1.c这个文件中的第12行的第三列出现了错误，你就要到文件中找到相应的那一行。它继续描述错误，是在scanf前少了一个符号，删了赋值运算符，逗号运算符，或者后面的一个attribute宏，我们在源代码中发现，就是少了一个分号而已。

练习，解释下列编译错误是什么意思？

1.c:13:59: error: ‘g’ undeclared (first use in this function)
   printf("%c %d %.2f %ld %lld %.7lf\n", a, b, c, d, e, f, g);

1.c:13:3: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘long long unsigned int’ [-Wformat=]
   printf("%c %d %.2f %ld %lld %.7lf\n", a, b, c, d, e, f);
   ^

问题3 对评测系统的误解

在线评测系统（Online Judge）是用户提交代码后，后台通过测试样例测试程序正确性的系统。我们先看几个概念：
1、测试样例
对于程序的一组符合题目逻辑输入输出，称为一组测试样例。如a-b中，输入 1 2，输出 -1 是一组测试样例。每个题目中会有多个样例，可是评测系统并不会公布这些样例，你需要通过完善自己的程序逻辑来达到通过测试的目的。因此，你通过题目给的example并不意味着你通过全部测试。
2、评测过程
如图所示

3、输入输出流
输入流指的是程序的所有输入，输出流指的是程序的所有输出。也就是评测系统会给你的程序一个输入流作为你的处理的开始，然后你的程序需要提供一个符合预期的输出。因此，所有的提示型语句：“please input ”之类的会被认为是输出流中的东西，你的程序不能够出现这个。
4、数据输入范围
数据输入范围是指你需要解决的问题规模。
比如，同样是a-b的题目，a，b的范围可以有很多种，因为实数是一个无穷集合。你需要解决的问题大小是题目给你限定好的。比如题目说a<10000, b<1000, 就说明题目的输入流中不存在大于1000的a或者b，你不需要考虑大数字的相加。相反，有些题目就是要求大数据的问题，这个题目的难度就不一样，难度和数据的大小一般成正比。

这是评测系统的原理。因此你需要考虑很多东西，否则我所有的答案直接printf出来，这样题目没有任何意义。

问题4 代码风格很糟糕

大家现在写的代码开始复杂了，代码风格也就开始不管了。有些同学把所有的计算表达式全部放到printf里面，看的我眼花缭乱。有的同学写代码左对齐，毫无缩进，非常难看。
1、请大家检查自己的代码风格，用之前的cpplint，否则一年之后你会埋怨我没有抓代码风格，到时候习惯了之后，你会发现那样写的代码是项目毒瘤。
2、你可以给其他同学看你的代码，看看你要花多少口舌解释你的代码，就是你这份代码在协同工作时候的交流成本，这个肯定越低越好。

google style 在线检查

练习：给你的同学看1003你提交的代码，让他理解1003那个题目的思路，和各个变量是干嘛的。

问题5 不会读题，读题不认真

现阶段西西里的课程练习题都是中文的，而考试的时候是英文的。你怎么读这个题目，决定了你是否能做对这个题目。比如，二次方程的题目明确说明了输出时候小根在前，大根在后，这是题目的关键信息，然而不少同学直接忽略。

所以，请大家认真读题目。

问题 6 不会使用函数

函数是c语言一个很重要的概念，之后老师肯定会重点讲。而现在我们使用的printf，scanf和log这些都是库里面定义好的函数。既然学习一个东西，首先得知道怎么用，之后才能学习怎么创造。

对于每个函数的使用方法，你需要去看他的函数原型（prototype）：
函数原型有三个元素：函数名（一般蕴含这个函数的作用）、函数的返回类型、函数的参数列表，如：

double log (double x);

这个函数规定了输入的参数是double，处理后得到的结果也是double。这也就是为什么vs里面直接把int类型的变量当做参数传入会报错的原因。这个函数的返回值是double。所以应该对应起来，用double类型来存储，或者在printf中咏%lf直接输出。

double x = 100.0;
double a = log(x);
printf("%lf", log(x));

练习，解释下面函数的参数和函数的调用方法用法：

int scanf(const char *format,...);
extern void printf(const char *format,...);
double pow(double x, double y);

本周扩展题目：

http://172.18.228.154:8080/

大家有什么问题就在下面留言，非常欢迎

软件：week10 C String and Functions

大家注意问题

1、文件命名绝对不能错
2、你需要先学习如何写一个函数库。也就是第一个任务，如何编写.h文件和.c文件分开，然后在main函数中调用.h文件中的函数。说白了就是明白#include <stdio.h>这种实现的机制。
3、.h文件和.c文件请严格遵守要求中的约定。设定好的函数原型和.h文件请不要更改，并且理解为什么一字不能改？对于系统构架师（编写.h的工程师）和具体实现的工程师（编写.c文件工程师），以及测试工程师（编写main.c进行测试的工程师），和用户（调用库函数的人）之间是怎样合作，怎样沟通理解的？
4、请先自己尝试编写main函数进行测试（文件分离，再编写）

软件：week5 实验问题反馈

实验主要问题

大家可能是上大学以来第一次写实验报告，可能问题挺多，下面将详细介绍。

另外，对于大家提出的建议进行一一回答。

不要抄袭，不要抄袭，不要抄袭

很遗憾你们遇到我这个大一实训时候的ta，我们那时候检查抄袭是通过py的正则表达式和距离算法判断相似度，你可以去问问你们14级的师兄师姐。为什么不能抄袭？我想这个问题不是问题吧。

还是那句话，你做不出来，或者直接说不想做，跟我说，我直接给你及格（不过不要每次都来这样），你做不出来，可以缓交。除此之外，要不就不做，要不就好好做。

抄袭一次，本次实验0分；抄袭两次，实验作业全部零分；抄袭三次，直接挂科重修。

实验报告问题

软件 = 程序 + 数据 + 文档
仅仅的代码不是软件，这个实验的实验代码就是程序，文档就是实验报告，文档和程序同样重要。有下列几个普遍问题：
1、不按照模板自由发挥。
既然实验报告给了模板，你就应该按照这个来写，不要自己重新编一个，这样不好。
2、格式不正确
要求说了用pdf格式，不少word的格式，这个不好。
3、主要内容太吹水
前两部分是给你写你做了什么事情的，比如你用了什么函数，他是什么功能，是写这些的，很多同学就开始水他学习这个经历了九九八十一难，这个应该在心得那里写。

以后的课程基本上很多都要写报告的，所以大家还是学习好怎么写实验报告

优秀报告请参考：优秀报告

代码问题

1、普遍问题，没有输入输出提示：哎呀，师兄不是西西里，而且大家写的函数五花八门，你不提示我你在做什么，我要去一句一句翻看源代码非常痛苦。另外，有些同学实验报告也是没写干了什么，所以我就完全不知道你做了什么。

所以，程序应该有简单的输入输出的提示，告诉我输入什么，输出什么。退一步，实验报告里也总有个程序使用说明。

2、代码编译问题。我用的编译器是dev c++ 很多同学会用vs编译，可以你要考虑兼容的问题。比较多的问题是两个，第一个是使用_s后缀的vs专用函数，第二个就是使用for循环时候直接在里面申明自增变量i。前者是通用性很差，只支持vs，后者是只有c99标准才支持那样子的申明，大家注意。建议还是使用GCC为内核的编译器，如dev，CFREE，当然vs是可以用的，不过你要注意通用性。

优秀代码请参考：优秀代码

附上一份我们一个小project的实验报告：sinew

问题反馈

1、西西里题目太难的问题，以及西西里理论课和实验课脱节：
说实话，我们在西西里上放的题目真的不难，而且这个是每周老师根据教学进度放的题目，恰恰是和理论课结合很紧密的题目。如果不会做的同学最好多和其他同学交流，和TA交流，和老师交流，特别是在实验课上，你可以准备很多问题来问老师和TA，因为这个时间TA和老师的关注点是大家。

2、扩展题太难，以及扩展题希望能出更具思考的题目：
首先，扩展题的来源有三个，第一个是往年的期中期末考试题，第二个是15教务四班每周的作业题，第三个是我自己出的题目。一个是供大家检考试的例子以及督促大家往新的知识学习，第二种是对比其他班学习的进度弥补我们因为班级的差异带来的教学不足，第三种是我自己出的，对于算法要求低，对语言本身要求极高的题目以及一些考验思维严密性的问题，还有就是应用题（读数字，贪吃蛇）。每个题后面都有难度，一般1~4都是不难的。

而且这个题目做不做随大家，不计入成绩。而且这些题目一般都不偏向经典算法（除了个别期中期末考试题），而是重于对语言本身的应用，逻辑思维的严密性等。如果想做算法题，1、以后算法课肯定会有，2、可以考虑去ACM队，3、找我要，我很多

3、代码风格问题以及衍生的关于软件工程的问题：
我们要时时刻刻记住我们学的是软件工程，也就是说我们的代码是给我们合作的程序员看的，我们的产品（程序、文档、数据）是给我们的用户看的。工程重在的就是协同完成一个很大的项目。比如假设我们现在要100个人来完成一个软件，假如别人和你合作却读不懂你的代码，或者很难读懂怎么办？有的同学说很容易的，如果我是1万行代码呢？

另外提到一点，工程的**。你要验证问题的解决方法对不对，可能没办法通过数学证明。这时候你需要做什么？

测试

这是在西西里通过的关键。不是说我过了那个example就好了，这远远不够，你需要做的事对于那些数据的很多情况，自己去考虑更多的数据输入输出，从而找到自己程序的问题。因为很多时候我们都会有一种错觉，认为自己的逻辑是正确的，所以测试是解决工程问题最好的办法。

4、看不懂报错，看不懂风格报错：
首先要说一点就是，英文必须要学会看，看不懂就是因为不会翻译。翻译出来正确了，你自然就懂了。要学会适应英语阅读，以及表达，这就是为什么要大家用英文解释理论选择题。

5、感觉老师上课讲的天花乱坠，云里雾里：
我当时也是杨老师教的，上课也是这种感觉，那时候实验题目是竞赛队的TA出的（大家可以在扩张体里看到变态的期中考试题），那时候我们学的更加吃力。我想说的是，老师讲的东西即使你听不懂你也要听进去，以后会有一次恍然大悟的感觉，哦原来是这样的。你会知道这些理论知识多么重要，会贯穿软件工程大学的四年，因为这门课是基础中的基础。

讲点题外话，很多13级的同学就是那时候被题目虐的太惨了，恐惧编程，害怕编程，所以13级整体两级分化是很严重的，很多同学至今仍然不理解当初程序设计的**方法和理论，很抗拒打代码。我想说，一件事就算再难你也要坚持下来，难不是你放弃的理由，有问题找TA，找老师，找同学，找师兄师姐。

6、时间太紧，TA回复时间太久：
我们TA的时间确实很少，所以希望同学们能够集中在实验课问问题。平时的话如果发qq我可能会不小心忽略或者什么的。

建议大家发邮件给我们，或者在群上和其他同学讨论（不要害羞，有些大神比较高冷，其实他们内心还是很善良的），大家也应该积极去解决其他同学的问题，这样你也可以学到不少。

或者，你可以直接在这下面留言

还有个人时间问题，有人会说我参加了很多社团什么的。
首先，我要说，这里是中山大学，不是中山大社团，所以你应该以学为主。另外，你在社团的活动其实也是一种大学的学习，可是你需要学会安排时间，这是一种能力。我大一也参加过社团，大二是学生会副秘书长，但这些你要安排好。

7、学习编程要到怎样的程度才算好：
这没有一个明确的界限。就像你问，什么样的作家才是好作家？
学习就是一个漫长的，潜移默化的过程，我现在也还在学c语言。
在这个过程，第一，你最需要的是总结。你学了什么，你遇到了什么问题，怎么解决的，什么思路？这些事学习中最关键的积累。第二，理论是很抽象的，你需要做的是两件事，首先将理论具体化，通过实践做题去得到经验，当经验到达一定程度，你可以试着把具体的经验抽象成理论，这才是一个完整的学习过程。比如，老师说c语言的数学计算不同于数学的表达式，那我就使用几个个math函数，模仿别人怎么用的，最后可以抽象出，c语言的数学计算是需要库函数的使用。

后面的期中考试就是一次检验的机会

8、思维混乱：
对于一个编程的题目你不能晕，你要做的思考，不要害怕题目。
先读懂题目，输入时什么，输出是什么。
再者，细分问题，将问题减小。千万不急着写代码。
搞清楚逻辑关系，逐个小问题解决。
测试，修改错误。
（这个以后会再讲）

9、公布答案
这个建议很好，那以后每周题目的答案就公布在git上这个仓库。

总结

可能还有些同学的问题没有解答。总结起来，大家学习的过程中需要多提问题，不要自己憋着；多和大家讨论；多思考，深入的思考。

本周扩展题：

扩展题

软件：Course Project

C Programming : Course Project

## Update History

2015/12/9 22:30 Update deadline, a day ahead.
2015/12/9 22:54 Update Presentation, add a presentation for framework discuss
2015/12/11 12:00 Simplify the project requirement

Abstract

Many basically and widely used system are using C language because it's fast and more closed to the underlying of the computer structure. We are going to build a system as a real world project to understand the system design as well as a system implement.

Modeling is very important in process oriented programming. You are going to design the system yourself and design a good file structure with .h files and .c files. And also you should design good function prototypes and make clear the usage of each part.

What's more is that you should implement the functions for the complete logic.

We are going to build a student management system.

Targets

Improve the C language grammar learning.
Learn to design a system using process-oriented programming.
Learn to use modeling method to implement each part of the process.
Learn how to work for a project in Software Engineering.
Learn code style deeply.

Develop Environment

windows: commandline or DEV cpp
ubuntu linux: command line (optional bonus)
ubuntu linux using command line and makefile (optional bonus)

使用linux开发可以加分，期末考试很可能使用linux系统。
另外，ftp上有相关虚拟机和镜像文件下载，以及安装教程，入门教程等。

Requirements

Introduction

Now, you are the system designer for our student grading system. And the our course need the following functions, you job is to implement the system demands.

1. Append Records:

You can insert a grade record into the system.
The record include the several properties studentID, studentName, studentClass, studentGrade.
You can also insert a number of this kind of records at the same time.

2. Delete Records:

You can delete a Record from the system by a studentID, a studentName or a wholeClass, a range of grade.
You can also delete a number of this kind of records at the same time.

3. Modify Records:

You can modify the records.
For example, I can change a student's name, a student's class or a student's grade.
You can also modify a number of this kind of records at the same time.

4. Querying Records:

You can query some students that meets a setting condition. For example, query the students whose grade is less than 60 in a given class.
You can also get the max grade, the average grade, the number of students who's grade is greater than 90.

5. Extended Functions:

You can extend the system with other functions (鼓励添加其他功能).

For example, you can use function functional programming. It means that you are supposed to use function pointers to role as filters to meet the requirements more easily. We have note functional programming in optional project 1.

For example:

Student * Query(Student[] stus, bool(*filter)(const void *));

## Other Requirements: ### Designing Style:

You can not defined useless or meaningless functions. And you can not put all project logic in one file(very bad) or put all logic in a main fuction(very very bad).
How to design good function prototypes and how to divide into several files is very important and this will be the most important part for grading.

Coding Style:

Coding style is very important for you. The style rules including google style are required.
What's more, you should have good comments with your code.

File Method:

Maybe you will us File IO operation, you can use your own data format. Json or CVS is recommended.

Report Template:

Abstract

Make a brief introduction for your project.

User Documentation

Statements about how to run the program. How to use this system.

Project Structure

Statements about your project structure, i.e. your function interfaces and file structure.

Design Thinking && Design Process

Statements about how you think about the project, i.e. how to divided the project(big question) into smaller questions.
Statements about your details of your project design, i.e. how to implement the structure of your system.

Important Algorithm and Data Structure

Some important algorithm and data structure you use should be mentioned. And draw flowchart or write Pseudo code for them.

Testing

Statements about how you test the system.

Conclusion

Personal summary about this project.

Persentation Week 13

We will ask some students to discuss about how to build a framework for the system on Dec 14th 2015.

Presentation Final

We will have a presentation time on January 4th 2016 in the lab class. There will be randomly selected students need to do the presentation.

Deadline:

~~Dec 31st 2015 18:00~~
pay attention, one day ahead deadline
~~Dec 30th 2015 18:00~~
Dec 30th 2015 21:00
And have a good time on new year's eve.

Submit

Submit to the course ftp

ftp://172.18.182.75

username：c_and_cpp
password：c_and_cpp

filename : 13331314_叶嘉祺_CourseProject.zip

计科：week7 第五次实验报告

1 编程相关

1.1 C++程序完成思路

对于复杂的逻辑需求，先写伪代码或者画程序流程图得到清晰的逻辑结构。
自顶向下逐步求精解决问题（大问题分解为可解决的小问题），写出C++程序。
修改C++程序的编译错误。
通过测试，修改C++程序的逻辑错误。

1.2 命令行编译

为什么使用命令行编译？

可以获得比集成编译系统（IDE）更高的自由度。
为之后的linux编程工具链打下基础。
更好的理解c++程序编译执行过程。

配置方法：

1、打开Dev Cpp，并且找到对应的安装路径。

2、找到定义的MinGW目录下的bin目录这个是dev cpp的核心编译器。

3、配置系统环境变量，在系统的高级选项中找到path（可见第一周python配置方法）

4、打开cmd窗口，输入gcc --version输出编译器版本信息，配置完成。

编译方法：

找到一个c++源代码所在的文件夹，在文件夹中按住shift+鼠标右键，选择在此处打开命令行。
输入g++ + 空格 + 你要编译的文件 -o 编译出来之后的可执行程序的名字，如：g++ main.cpp -o main.exe（如果省略-o后面的命令，则会生成a.exe）
在命令行中输入 main.exe 即可运行程序。

1.3 测试数据的文件输入输出

其实，在抽象的层面上，键盘输入、文件输入和网络输入等都是IO，是等价的。我们可以利用这个进行文件代替键盘输入。

在刚才我们编译的程序之中，我们生成了main.exe的程序。假设现在我们的程序是做a-b的简单运算。我们现在在源代码的同一个目录下新建一个文件"input.txt"。我们打开文件输入两个数100和99。
接着我们在命令行输入命令main.exe < input.txt。我们很惊喜地发现，程序自动输出了1,我们不需要手动去使用键盘输出。

对于长而复杂的输入，这无疑是一个简化的过程。

对于文件输出，同样是可以的 main.exe < input.txt > output.txt

2 断点调试法（课题讲解）

#include<iostream>
using namespace std;

struct employee {
    long id, salary, height, boss, subordinate;
};
int main() {
    struct employee a[10000], temp, current_deal, potential_boss, search;
    int total_test, current_test, current_e, e_num, id_search;
    int i, k, j, m, n, t, u;
    for (u = 1;u <= 10000;u++) {
        a[u].subordinate = 0;
        a[u].boss = 0;
        a[u].height = 0;
        a[u].id = 0;
        a[u].salary = 0;
    }
    cout << "How many test do you want to have?\n";
    cin >> total_test;

    current_test = 1;
    while (current_test <= total_test) {
        cout << "please input the number of employees\n";
        cin >> e_num;

        current_e = 1;
        for (i = 1;current_e <= e_num;i++) {
            printf("please input No.%d empolyees' id, salary, height(seperated by space)\n", i);
            scanf("%d %d %d", &a[i].id, &a[i].salary, &a[i].height);
            current_e ++;
        }
        for (k = 1;k <= (e_num - 1);k++) {
            for(j = 1;j <= (e_num - 1);j++) {
                if(a[j].salary > a[j+1].salary) {
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }

        for (m = 1;m <= e_num;m++) {
            current_deal = a[m];
            for(n = e_num;n <= (m + 1);n--) {
                potential_boss = a[n];
                if(current_deal.height <= potential_boss.height) {
                    a[m].boss = potential_boss.id;
                    a[n+1].subordinate += 1;
                }
            }
        }

        cout << "please input the id you want to search for its boss and subordinates\n";
        cin >> id_search;

        for (t = 1;t <= e_num;t++) {
            if (id_search == a[t].id) {
                search = a[t];
            }
        }

        cout << "(" << search.boss  << ", " << search.subordinate;
        current_test ++;
    }

    return 0;
}

设置断点
运行程序
添加监控变量
执行程序、单步运行

3 实验报告内容 Breakpoint Debug

3.1 Pre Assignment

Learn about breakpoint debug method.
Learn about file stream input for a C++ executable program.
Learn about how to compile a program using command line interface.

Notice that

These knowledge is very important for you and it is a good preparation for the course project as well as some other following courses. You can ignore this assignment, but you are responsible for the yourself.

3.2 Assignment 0(10pts)

Learn about command line compile and file input. And then use the method on one of the questions in week 7 in sicily (write this part in your report and snap shoots are recommended).

3.3 Assignment 1(80pts)

Learn about breakpoint debug method yourself and using it to debug the following three C programs.

Target: A solution with three correct C++ source program.

Questions:

What is the bugs of the program and how can you find the bug? (8 pts)
What test data you use in the debug process? (8 pts)
Tell the problems about coding styling in the following program.(8 pts)
Understand three sorting algorithm(Bubble sort, selection sort and insertion sort), and then write Pseudo code or Flowchart for them respectively.(16 pts)
Correct these three programs include its style problems respectively and note that you should submit your source code. (55pts )

Notice that

Style is very important while coding, so if your new program is still ugly in style, 50% score will be deducted.
We will use black box test this time with auto running scripts. So if your file structure is wrong or your program result in errors will cause 0pts. And the grade depends on how many test cases passed like that in YOJ.
You should not add prompt statement this time like "please input an integer". The testing program will consider it to be wrong answer if you do it.
Sample input and output for all the three correct program.

Input: The first line contain an integer n which indicates the number of test cases. There will be n line in the flowing. For each line, there will be an integer m at the first of the line which means the size of the array. And there will be m integers. Note that, 1<n<20, 1<m<10000.

Output: For each input output the sorted array(from small to big) with spaces between elements.

input:
3
3 1 3 2
5 1 2 3 4 5
4 99 100 22 33

output:
1 2 3
1 2 3 4 5
22 33 99 100

Also Notice that the output of the flowing program is not correct at all, please correct it

link:
bubble sort
insertion sort
selection sort

3.3.1 Program 1 Bubble sort

#include<iostream>
using namespace std;

int main() {
int num[10000];
int n;
int i, j, temp;
int m, k, p, q, o;
int result[2000];

cin >> n;

for(i = 0; i < n; i++) {
cin >> num[i];
}

for(i = 0; i <= n; i++) {
for(j = 0; i + j < n; j++) {
  if(num[j] > num[j + 1]) {
temp = num[j];
num[j + 1] = num[j];
num[j] = temp;
  }
}
}

for(i = 0; i < n - 1; i++) {
cout << num[i] << " ";
}
cout << num[i] << endl;

return 0;
}

3.3.2 Program 2 Insertion sort

#include <iostream>
using namespace std;

int main() {
  int num[10000];
  int n;
  int i, j, temp;
  cin >> n;
  for(i = 0; i < n; i++) {
  cin >> num[i];}
  for(i=1; i<n; i++){
  temp = num[i];
  for(j=i-1; j>-1&&num[j]>temp;j--) {
  num[i]=num[j]; num[j]=temp;}}
  for(i = 0; i < n - 1; i++) {
  cout << num[i] << " ";}
  cout << num[i] << endl;
  return 0;
}

3.3.3 Program 3 Selection sort

#include <iostream>
using namespace std;

int main() {
  int num[10000];
  int n;
  int i, j, temp;
  int min;
  cin >> n;
  for(i = 0; i < n; i++)
    cin >> num[i];
  for(i=0; i < n; i++){
    min = num[i];
    for(j = i; j < n; j++) {
      if(min>num[j]) {
    temp = num[j];
    num[j] = min;
    min = temp;
    } for(i = 0; i < n - 1; i++) {
    cout << num[i] << " ";}
  cout << num[i] << endl;
  return 0;
}
}
}

3.4 Report

part one: Assignment 0
part two: Assignment 1
part three: Discussion，Cooperation and Summary (optional)

格式无要求，part two必须截图表明你使用了断点调试的技巧来调试你的代码，包括但不限于：如何添加断点，如何删除断点，如何运行下一条语句，如何运行到下一个断点，如何添加查看，如何删除查看，等等。

3.5 Submit lists

作业发给学委，不要发压缩包，注意文件命名必须完全一致，否则机器测试无法进行，0分处理。

3.6 Deadline

19 Nov. 2015, 23:59

Please submit your homework on time.

4 Discussion，Cooperation and Summary (15pts)

In this part, you will have some options, if you do more options, you will learn more and get more marks.

You should note this part in your report

option 1: Github Discussion

Comment at this issue and describe a problem that you meet and how you solve it detailedly.

Notice that

you should not copy and paste your personal report simply.
you should not write a very simple one and your comment will be deleted if you do that.
you should not post meaningless questions.
Show me in your report about your discussion on github with screenshot.

option 2: Simple Presentation

Have a simple presentation in the lab class on Friday (4 persons limited). And after the presentation, everyone is encouraged to ask questions and you can get bonus by asking good questions.

Notice that

The presentation is no more than 5 minutes and there will be 5 extra minutes for discussion.
You should prepare much for it. PPT is encouraged.
First come, first get the opportunity.
You can describe a algorithm you have learn, but you should make a majority of your classmates know what you are describing.
You can also share with us your learning experience about C++, and give some advice about how to learn it well.
The theme of your presentation is very important, if you are not sure whether your theme is good or not, you can contact me for some advice.

option 3: Helping others

You can help others to solve any problems the will meet. Detailedly describe the question, the solution and your personal experience as well.

Notice that

it is no need to consult with others that I help you, you help you to get marks. You can simply send email to me and I will give you the marks. No worry about that, if you do have helped others and spent a lot of time on it, you deserve the score.

option 4: Personal Summary

Write personal summary for yourself.
List at least 10 problems that you have met in your learning in C++ language and describe the solution as well.

Notice that

you should not have ten very simple problems, you must let me know your learning method and also the method to solve problems.

软件：week6 理论题（2015-11-2 实验课结束提交）

1. What's the output of the following program:

#include <stdio.h>
int main() {
    int n = 1, m = 4;
    while(n = 1) {
        m--;
        n--;
    }
    printf("%d %d\n", n, m);
    return 0;
}

A. 1 -1

B. 1 0

C. Dead Loop

D. 0 0

2.What's the output of the following program:

#include<stdio.h>
int main() {
    int a=4,b=8,c=5;
    int d1,d2,d3,d4;
    d1=(a<b)||(++a==5)||(c>b--);
    printf("d1=%d,a=%d,b=%d,c=%d\n",d1,a,b,c);
    d2=(a>b)&&(++a==5)||(c>b--);
    printf("d2=%d,a=%d,b=%d,c=%d\n",d2,a,b,c);
    d3=(a<b)||(++a==5)&&(c>b--);
    printf("d3=%d,a=%d,b=%d,c=%d\n",d3,a,b,c);
    d4=(a>b)&&(++a==5)&&(c>b--);
    printf("d4=%d,a=%d,b=%d,c=%d\n",d4,a,b,c);
    return 0;
}

A.
d1=1,a=5,b=7,c=5
d2=0,a=6,b=6,c=5
d3=0,a=7,b=5,c=5
d4=1,a=8,b=6,c=5

B.
d1=1,a=5,b=7,c=5
d2=1,a=6,b=6,c=5
d3=1,a=7,b=5,c=5
d4=0,a=8,b=6,c=5

C.
d1=1,a=4,b=8,c=5
d2=0,a=4,b=7,c=5
d3=1,a=4,b=7,c=5
d4=0,a=4,b=7,c=5

D. Compile error

3.What's the output of the following program:

#include<stdio.h>
int main() {
    int a = 2, b = 3, c = 4;
    printf("%d %d",c > b > a, c < b < a);
    return 0;
}

A. 0 0

B. 0 1

C. 1 0

D. 1 1

4.What's the output of the following program:

#include<stdio.h>
int main() {
    int a = 3, b = 4, c = 5;
    int d = (a + b) + c - 1 && b + c / 2;
    printf("%d\n", d);
    return 0;
}

A. 13

B. 1

C. 3

D. Compile error

5.What's the output of the following program:

#include<stdio.h>
int main() {
    float x = 2.5, y = 4.7;
    int a = 7;
    printf("%.1f\n", x+a%3*(int)(x+y)%2/4);
    return 0;
}

A. 2.5

B. error: invalid operands to binary %

C. 0.0

D. 1.2

6.Expression !x||a==b is Equivalent to
A. !((x||a)==b)

B. !(x||y)==b

C.!(x||(a==b))

D.(!x)||(a==b)

7.What's the output of the following program:

#include<stdio.h>
int main() {
    int i = -2;
    int n = ++i == 0 ? 99 : (i == -1 ? 11 : 22);
    printf("%d\n",  n);
    return 0;
}

A.22

B.Compile error

C.0

D.11

8.What's the output of the following program:

#include<stdio.h>
int main() {
    int x = 0, y = 0;
    switch(x) {
        x++;
      y = 2;
      case(0):
        printf("%d\n", y--);
        break;
      case(1):
        printf("%d\n", ++y);
        break;
   }
}

A. 0

B. 2

C. 3

D. -1

9.What's the output of the following program:

#include <stdio.h>
int main() {
    int number = 10;
    printf("%d %d %d %d\n", number, number++, number--, --number);
    return 0;
}

A. 10 10 11 9

B. 10 11 10 10

C. 9 8 9 9

D. 10 11 10 9

10.What's the output of the following program:

int main() {
    int a = 21, b = 11;
    printf("%d\n", (--a+b, --b+a));
}

A.30

B.31

C.32

D.33

软件：期中考试问题总结

软件学院15级教务1班程序设计(实验)期中考试参考答案

1000

#include <stdio.h>

int main() {
  int n;
  int plus;
  int min;
  int flag = 1;

  scanf("%d", &n);

  int i, j, k;
  plus = n / 2;
  min = 0;

  for(i = 0; i < n; i++) {    
    for(j = 0; j < min; j++) {
      printf("-");
    }
    for(j = 0; j < plus; j++) {
      printf("+");
    }
    printf("+");
    for(j = 0; j < plus; j++) {
      printf("+");
    }
    for(j = 0; j < min; j++) {
      printf("-");
    }
    printf("\n");
    if(flag) {
      plus --;
      min ++;
    } else {
      plus++;
      min--;
    }

    if(plus <= 0) {
      flag = 0;
    }
  }

  return 0;
}

1001

#include <stdio.h>

const int chair = 30;
const int trees = 10;

int main() {
  int i;
  int height;
  int apple[10];
  int ans = 0;

  for(i = 0; i < trees; i++) {
    scanf("%d", &apple[i]);
  }
  scanf("%d", &height);
  for(i = 0; i < trees; i++) {
    if(height + chair >= apple[i]) {
      ans ++;
    }
  }

  printf("%d\n", ans);

  return 0;
}

1002

#include <stdio.h>

int main() {
  int m,n;
  int i;
  unsigned long long ans;
  scanf("%d", &m);

  while(m--) {
    scanf("%d", &n);
    ans = 1;
    for(i = 2; i <= n; i++) {
      ans += i*i*i;
    }
    printf("%lld\n", ans);
  }

  return 0;
}

1003

#include <stdio.h>

int main() {
  int n;
  int array[101];
  int i, j;
  int ans;

  while(scanf("%d", &n) && n) {
    ans  = 0;
    for(i = 0; i < n; i++) {
      scanf("%d", &array[i]);
    }

    for(i = 0; i < n; i++) {
      for(j = 0; j < n; j++) {
    if(array[j] * 2 == array[i]) {
      ans++;
    }
      }
    }
    printf("%d\n", ans);
  }

}

1004

#include<stdio.h>

int main(){
  int i,j,a[1000][1000];
  int n;
  while(scanf("%d", &n) && n) {
    for(i = 0; i < n; i++) {
      for(j = 0; j < n; j++){
    a[i][0] = 1;
    a[i][i] = 1;
      }
    }
    for(i = 2; i < n; i++) {
      for(j = 1; j <= i-1; j++) {
    a[i][j] = a[i-1][j-1] + a[i-1][j];
      }
    }
    for(i = 0; i < n; i++){
      for(j = 0; j <= i; j++) {
    printf("%d\t", a[i][j]);
      }
      printf("\n");
    }
  }
  return 0;
}

1005

#include <stdio.h>

int main() {
  int start_hour;
  int start_min;
  int end_hour;
  int end_min;

  int sleep_hour;
  int sleep_min;

  scanf("%d:%d", &start_hour, &start_min);
  scanf("%d:%d", &end_hour, &end_min);

  if((end_hour < start_hour) ||
     ((end_hour == start_hour) && (start_min > end_min))) {
    end_hour += 24;
  }

  sleep_hour = end_hour - start_hour;
  sleep_min = end_min - start_min;

  if(sleep_min < 0) {
    sleep_min += 60;
    sleep_hour--;
  }

  if(sleep_hour < 10){
    printf("0");
  }
  printf("%d:", sleep_hour);

  if(sleep_min < 10) {
    printf("0");
  }
  printf("%d\n", sleep_min);

  return 0;
}

计科：week1 代码风格检查

week1 代码风格检查

一、用cpplint.py进行代码风格检查

Sicily系统没有在编程风格上作要求，只要你的代码能运行，输入输出没问题，就可能可以通过。但是这样会写出可能可读性很差的代码。因此我们TA强烈要求同学们一定要注意自己的代码编写的风格。

下面介绍一个工具的使用来进行代码风格检查。

步骤1：安装python

教程：安装python

要注意的是，教程中说的系统变量就是python的安装路径。

步骤2：检查python是否安装成功

打开命令行窗口（win键+R；输入cmd；回车）如下：
如果安装成功，在命令行窗口输入python将会出现以下的输出：

步骤3：下载cpplint.py

点击下载cpplint.py

步骤4：代码风格检查

把cpplint.py文件复制到你的程序代码所在的目录。比如：
打开命令行窗口，方法就是步骤2的第一点。导航到代码所在目录。

cd命令的含义是打开目录，dir命令的含义是查看该目录下地文件和文件夹
运行命令
```
python cpplint.py --filter=-whitespace/tab filename.cpp
```
注意finename.cpp是你的源代码的文件名

然后就会有如下的输出：

注意错误，如test.c:7: Line ends in whitespace. Consider deleting these extra spaces. [whitespace/end_of_line] [4]。test.c指的是文件名，7指的是行号，后面的 Line ends in whitespace. Consider deleting these extra spaces. [whitespace/ end_of_line] [4]指的是代码中出现的错误。

步骤5：根据输出的改善代码

根据输出的错误，逐行改进代码。直到错误数目为0。如Total errors found: 0：

步骤6：提交到Sicily

把通过google style的cpplint.py测试的代码，也就是Total errors found: 0，再把代码提交到Sicily。

总结

进行google style风格检测的目的是让同学们写出可读性良好的代码。按照上面的流程编写代码，能帮助你养成良好的编程习惯。希望同学们重视。

有任何问题欢迎评论。我们会持续改进。

参考

软件：week2 问题反馈+扩展练习

问题反馈

本周题目仍然较为简单，大概60多个同学课上把一周的题目都做完了。

** 学有余力的同学最好做一下扩展练习题 **

存在如下一些问题：
1、scanf("%d", &a) 的第一个参数是格式化字符串，在要求键盘输入多个变量时候，格式化字符串中间不应该用逗号隔开，格式化字符串中也不应该出现换行符号。同时，输入的时候应该要使用取地址符号&，不使用则会出错。以下几种情况均为错误的:

   scanf("%d,%d", &a, &b); 
   scanf("%d%d\n", &a, &b);
   scanf("%d%d", &a &b);
   scanf("%d%d", a, b);

正确写法：

   scanf("%d%d", &a, &b);

2、printf中前面是格式化字符串，很多同学不理解printf的机制。

   int year = 2015;
   int month = 9;
   int day = 28;

   printf("%d年%d月%d日", year, month, day);

也就是说前面的格式化字符串定义了输出的格式，其中%d是等待某个整型变量来填充进去的意思。

printf中的变量带有取地址符号是不能输出我们期望输出的变量的。
printf格式化字符串中的参数和后面不对应也是错误的。
以下写法是错误的：

   printf("%d %d", &a, &b);
   printf("%d %d", a);
   printf("hello world!\n", a);

3、记得输出需要换行

4、空格和回车在输入整数时候的作用是相同的：
1 2 3 4
与
1 2
3 4
若都是输入4个整数，这两者是一样的。

扩展练习

1000 Triangle II

Time Limit: 1sec Memory Limit:256MB

Description:

输入一个数，输出对应的这样的图像：
link

1001 A/B

Time Limit: 1sec Memory Limit:256MB

Description:

输入两个整数A和B，输出这两个整数的商A除以B,保留两位小数。
注意：当除数为0时候应当输出“Error!”

input

3 5

output

0.60

input

1 0

output

Error!

HINT:

注意使用浮点数运算

1002 Polynomial II

Time Limit: 1sec Memory Limit:256MB

Description:

Given two pair of integers (a1,b1) and (a2,b2),can you calculate the expanded form of (a1_x+b1)(a2_x+b2)?
(note that we use "x^2" to express x2 and omit "")
这次你需要考虑系数为0的情况，即： 2x^2+0x+1, 这样应该写成: 2x^2+1

input

1 0
1 0

output

x^2

1003 Sum the digits in a big integer

Time Limit: 1sec Memory Limit:256MB

Description:

Write a program that reads an integer with 3 digits and adds all the digits in the integer.For example,if an integer is 932,the sum of all its digits is 9+3+2=14.
现在要假设处理的数字非常大( 2^64 < length <= 10^200 )

（length 指的是数字的大小！不是长度！╮(╯▽╰)╭）

input

123456789011121314151617181920

output

101

扩展练习题测试数据

第二周测试数据

评测地址

YOJ 在线评测（校园内网）

软件：Optional Lab C Small Plane Game

Description

Now, we are going to do a small project named a small plane game.

Requirements

Lookahead Self Learning is required in this project. The knowledge include struct and pointers in C.
Especially for struct, you should know its advantage and usage. For pointer, you should know the deep thoughts.
Debug method should be mastered such as breakpoint debug, binary debug or output debug.
Good programming style should be mastered.

Let's build a game!

We need to know what roles at the game and the rules as well. The question is what rules we need.

In this project, we are going to build the small plane game. We have the following roles:

Plane, the main character in the game, and the player can control the plane.
Note that we use 1 to mark plane in the game prototype.
2.Obstacles, the second main characters in the game. It can move as an AI, and when it hits the player, game over.
Note that we use 2 to mark obstacles in game prototype.
The map, the scene to play on. And the map display the objects in the map. Like the image, we can regard it as a map in the game.

Actions:

For player, it can move left, right, up and down if it's still in the map.
For obstacles, it can move from right to left trying to hit the player.
Update the game pane when something change.
We need to draw the game pane when the map update.(print)

Game Structure Code

#ifndef GAME_H
#define GAME_H

typedef struct point {
  int x;
  int y;
} point;

typedef enum objects {BLANK = 0, PLANE = 1, OBSTACLE = 2} OBJ;
typedef enum operations {UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3} OP;

#define GAME_ROW 2
#define GAME_COL 16

typedef struct gamePane {
  // the game pane, 0 for blank, 1 for plane and 2 for obstacle
  OBJ pane[GAME_ROW][GAME_COL];
  point cursor;
  int gameOver;
} gamePane;

typedef struct plane {
  point position;
} plane;

typedef struct obstacle {
  point position;
} obstacle;

// function list
void init(gamePane * thePane, plane * thePlane, obstacle * theObstacle1, obstacle * theObstacle2);
void setCursor(gamePane * thePane, const int x, const int y);
void setplane(gamePane * thePane, plane * plane);
void setobstacle(gamePane * thePane, obstacle * obstacle);
void removeOBJ(gamePane * thePane, const point p);
void gameOver();
void printPane(const gamePane thePane);
void movePlane(gamePane * thePane, plane * thePlane, OP op);
void moveObstacle(gamePane * thePane, obstacle * theObstacle);
#endif // GAME_H

Game Source Code

void init(gamePane * thePane, plane * thePlane, obstacle * theObstacle1, obstacle * theObstacle2) {
  thePlane->position.x = 0;
  thePlane->position.y = 0;
  theObstacle1->position.x = 0;
  theObstacle1->position.y = GAME_COL-1;
  theObstacle2->position.x = 1;
  theObstacle2->position.y = GAME_COL-3;

  int i, j;

  for(i = 0; i < GAME_ROW; i++) {
    for(j = 0; j < GAME_COL; j++) {
      thePane->pane[i][j] = BLANK;
    }
  }

  setplane(thePane, thePlane);
  setobstacle(thePane, theObstacle1);
  setobstacle(thePane, theObstacle2);
  thePane->gameOver = 0;
  thePane->cursor.x = 0;
  thePane->cursor.y = 0;
}


// basic operation for game pane
void setCursor(gamePane * thePane, const int x, const int y) {
  thePane->cursor.x = x;
  thePane->cursor.y = y;
}

void setplane(gamePane * thePane, plane * plane) {
  if(thePane->pane[plane->position.x][plane->position.y] == OBSTACLE) {
    thePane->gameOver = 1;
    gameOver();
    return;
  }
  thePane->pane[plane->position.x][plane->position.y] = PLANE;
}

void setobstacle(gamePane * thePane, obstacle * obstacle) {
  if(thePane->pane[obstacle->position.x][obstacle->position.y] == PLANE) {
    thePane->gameOver = 1;
    gameOver();
    return;
  }
  thePane->pane[obstacle->position.x][obstacle->position.y] = OBSTACLE;
}

void removeOBJ(gamePane * thePane, const point p) {
  thePane->pane[p.x][p.y] = BLANK;
}

void gameOver() {
  printf("GameOver\n");
}

void printPane(const gamePane thePane) {
  int i, j;
  for(i = 0; i < GAME_ROW; i++) {
    for(j = 0; j < GAME_COL; j++) {
      printf("%d", thePane.pane[i][j]);
    }
    printf("\n\n");
  }
}

// operation for plane
void movePlane(gamePane * thePane, plane * thePlane, OP op) {
  removeOBJ(thePane, thePlane->position);
  switch(op) {
  case 0 :
    if(thePlane->position.x > 0) {
      thePlane->position.x--;
    }
    break;
  case 1 :
    if(thePlane->position.x < GAME_ROW - 1) {
      thePlane->position.x++;
    }
    break;
  case 2:
    if(thePlane->position.y > 0) {
      thePlane->position.y--;
    }
    break;
  case 3:
    if(thePlane->position.y < GAME_COL - 1) {
      thePlane->position.y++;
    }
    break;
  }
  setplane(thePane, thePlane);
}

//operations for obstacle
void moveObstacle(gamePane * thePane, obstacle * theObstacle) {
  removeOBJ(thePane, theObstacle->position);
  if(theObstacle->position.y <= 0) {
    theObstacle->position.y = GAME_COL - 1;
  }

  theObstacle->position.y--;

  setobstacle(thePane, theObstacle);
}

Assignment 0

You do not need to write this part to your report.

What's the meaning of the code, please write comments(注释) for each functions as well as the important expressions and statements.
2.The header declarations and source code of the game are provided. But we can not run the game without a game launch function(main function), please write a main function to run the game.

Assignment 1

As you play the game, the interface of the game is very ugly. And also the game is not a game at all. Your job is to modify the game using your idea.

Some advice:

Add bullet for the plane, which means that you can control the plane to hit the obstacles.
Add score counter, and a list of score. And it can record the ranking of the score every you play it. You should use c file IO in this part.
Large plane Scene, get a large Play Scene to the game.
Muti-obstcales that the obstacles can spawn a bullet or any other idea.

Grade

(55pts) Your personal runable game.
(25pts) Your Document about your game elucidatio. And your algorithm to get to your idea game.
(20pts) The Style of your source code. Besides google style check, you should have good indent in the source code and you are supposed to write good comments(充分的代码注释) for you game.

Notice that, you should upload you game project to your github repository and write the documentation using markdown and named it "Readme.md".

You will get bonus in the final grade.

Submit

just send me your github address.

Deadline

2015 12.15 18:00

计科：week10 问题反馈和额外任务

week10 问题反馈和额外任务

如果熟悉linux系统，且有使用经验的，或者已经安装的同学，直接截图即可，可以不用做第一个额外任务。

1 安装vmware，运行ubuntu虚拟机

1.1 安装文件

在FTP上可以下载。

下载以上文件到你的电脑。

1.2 安装vmware pro 12

按照普通的安装步骤即可：双击运行。

注意，可能要求输入安装密钥等。百度之 or 土豪可购买之。涉及版权问题，在此不再细说。

1.3 运行ubuntu kylin虚拟机 && 编译运行.cpp程序

观看视频教程：

1.4 report

将以上安装步骤适当截图，放在report.pdf里面。

如果熟悉linux系统，且有使用经验的，或者已经安装的同学，直接截图即可，可以不用安装虚拟机。

1.5 参考

安装双系统，自行查阅网上资料
g++命令参数

2 编程周末赛

YOJ 在线评测系统

时间：本周六晚19:00-21:00
奖励：计科班前10名在期末平时成绩基础上加分
地址：http://172.18.215.225:8080/
登录：用户名密码都是你的学号
比赛：非强制，有时间，愿意做就去做
更多信息留意群通知

计科：week6 第四次实验程序流程图和伪代码

week6 第四次实验程序流程图和伪代码

实验目的：当大家学习了程序的控制结构之后，代码就变得复杂起来。在这时，我们解决问题就需要有很严密的逻辑思维。程序流程图和伪代码就是帮助我们去描述我们解决问题的方法（也称为算法）的工具。本次实验在于让大家学习如何使用这些工具，这对大家以后的编程有很大的帮助。

1 Flowchart (程序流程图)

From wikipedia

Detailed Description: flowchat

There is an example:

And this is the flowchart:

2 Pseudocode (伪代码)

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

From wikipedia

There is an example:

We can describe this question by this way rather than write a C++ program immediately:

main {
    input two integers height and n
    initialize answer = 0

    loop for n times {
        input tree_height
        if height >= tree_height:
            answer = answer + 1
    }

    print answer
}

Pseudocode is used to express your thought, you do not need to care about the grammar.

3 Pre Assignment

Learn about Flowchart and Pseudocode.

4 Assignment (100pts)

4.1 Assignment 0 (20pts)

Choose one question from soj.me in week6 in our course and then write the Pseudocode.

4.2 Assignment 1 (35pts)

Translate the following flowchart into Pseudocode

Description

Flowchart

Simple input and output

Input

2
3
123456 14323 1700000
123458 41412 1900000
123457 15221 1800000
123458
4
200002 12234 1832001
200003 15002 1745201
200004 18745 1883410
200001 24834 1921313
200002

Output

(0,2)
(200004,0)

4.3 Assignment 2 (35pts)

Draw a flowchart from the following C++ language program which constructs a bubble sort algorithm.

#include <iostream>
using namespace std;

void print(int* pData, int count) {
    for (int i = 0; i< count; i++) {
        cout << pData[i] << " ";
    }
    cout << endl;
}

void BubbleSort(int* pData, int count) {
    int temp;
    for (int i = 1; i < count; i++) {
        bool flag = true;

        for (int j = 0; j < count - i; j++) {
            if (pData[j] > pData[j+1]) {
                temp = pData[j+1];
                pData[j+1] = pData[j];
                pData[j] = temp;
                flag = false;
            }
        }

        if (flag) break;

        cout << "The "<< i <<" round:" << endl;
        print(pData, count);
        cout << "----------------------------" << endl;

    }
}

int main() {
    int n;
    int data[100];

    cout << "How many numbers you want to input ? (less than 100)" << endl;
    cin >> n;
    cout << "Please input " << n << "numbers, separating with space: " << endl;

    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }

    BubbleSort(data, n);

    cout << "The sort result:" << endl;

    print(data, n);

    return 0;
}

5 Extended Assignment (10pts)

Draw a flowchart and write Pseudocode as well as a C++ language program for the following description.

6 Discussion，Cooperation and Summary (15pts)

In this part, you will have some options, if you do more options, you will learn more and get more marks.

You should note this part in your report

option 1: Github Discussion

Comment at this issue and decribe a problem that you meet and how you solve detailedly.

Notice that

you should not copy and paste your personal report simply.
you should not write a very simple one and your comment will be deleted if you do that.
you should not post meaningless questions.

option 2: Simple Presentation

Have a simple presentation in the lab class on Friday (4 persons limited). And after the presentation, everyone is encouraged to ask questions and you can get bonus by asking good questions.

Notice that

The presentation is no more than 5 minutes and there will be 5 extra minutes for discussion.
You should prepare much for it.
First come, first get the opportunity.

option 3: Helping others

You can help others to slove any problems the will meet. Detailedly decribe the quesion, the solution and your personal experience as well.

Notice that

it's no need to consult with others that I help you, you help you to get marks. You can simply send email to me and I will give you the marks.

option 4: Personal Summary

Write personal summary for yourself.
List at least 10 problems that you have met in your learning in c language and decribe the solution as well.

Notice that

you should not have ten very simple problems, you must let me know your learning method and also the method to solve problems.

7 Report Template

There will be no Report Template this time which means it's all depends on yourself.

Notice that

the report is the most important document for your project, you should pay more attention to it.
you are supposed to write a report that is friendly to your 'users', which means that you need to consider about the typesetting, the logical structure of the content.
There should contain one item, self grading that you should give a score to evaluate your job as well as a reason.

For example: sinew

8 Flowchart Tool: Process On

Process on is a good tool for drawing flowchart.
link

9 Submit List

Notice that:
13331314 means your student id.
the first assignment need to name your file with your chosen problem id.

10 Deadline

23:59 on Nov 12th, 2015

11 Notification

Submit after deadline will cause a 30% penalty.
If your file structure of filename is wrong, you will probably get 0 in that part.
Any questions, you can ask us and email is better.
Full mark will be 100, but you may get more than 100 within this project.
You can use any tool include word, process on to draw a flowchart. You can use any form to write your Pseudocode but should be of high readability. If TA can not understand your Pseudocode clearly, you will get low points.(you can use Chinese to write Pseudocode if you like).

第十二周问题反馈

String 操作的后三个函数

From: The Art of Programming link

1.1 旋转字符串

题目描述

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

分析与解法

解法一：暴力移位法

初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的尾部，如此我们可以实现一个函数LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾部的功能，代码如下所示：

void LeftShiftOne(char* s, int n)
{
    char t = s[0];  //保存第一个字符
    for (int i = 1; i < n; i++)
    {
        s[i - 1] = s[i];
    }
    s[n - 1] = t;
}

因此，若要把字符串开头的m个字符移动到字符串的尾部，则可以如下操作：

void LeftRotateString(char* s, int n, int m)
{
    while (m--)
    {
        LeftShiftOne(s, n);
    }
}

下面，我们来分析一下这种方法的时间复杂度和空间复杂度。

针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要 m*n 次操作，同时设立一个变量保存第一个字符，如此，时间复杂度为O(m * n)，空间复杂度为O(1)，空间复杂度符合题目要求，但时间复杂度不符合，所以，我们得需要寻找其他更好的办法来降低时间复杂度。

解法二：三步反转法

对于这个问题，换一个角度思考一下。

将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。

例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：

首先将原字符串分为两个部分，即X:abc，Y:def；
将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

如下图所示：

代码则可以这么写：

void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void LeftRotateString(char* s,int n,int m)
{
    m %= n;               //若要左移动大于n位，那么和%n 是等价的
    ReverseString(s, 0, m - 1); //反转[0..m - 1]，套用到上面举的例子中，就是X->X^T，即 abc->cba
    ReverseString(s, m, n - 1); //反转[m..n - 1]，例如Y->Y^T，即 def->fed
    ReverseString(s, 0, n - 1); //反转[0..n - 1]，即如整个反转，(X^TY^T)^T=YX，即 cbafed->defabc。
}

这就是把字符串分为两个部分，先各自反转再整体反转的方法，时间复杂度为O(n)，空间复杂度为O(1)，达到了题目的要求。

举一反三

1、链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。

2、编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。
例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。

3、单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”。

字符串包含

题目描述

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？

为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)

比如，如果是下面两个字符串：

String 1：ABCD

String 2：BAD

答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。

如果是下面两个字符串：

String 1：ABCD

String 2：BCE

答案是false，因为字符串String2里的E字母不在字符串String1里。

同时，如果string1：ABCD，string 2：AA，同样返回true。

分析与解法

题目描述虽长，但题意很明了，就是给定一长一短的两个字符串A，B，假设A长B短，要求判断B是否包含在字符串A中。

初看似乎简单，但实现起来并不轻松，且如果面试官步步紧逼，一个一个否决你能想到的方法，要你给出更好、最好的方案时，恐怕就要伤不少脑筋了。

解法一

判断string2中的字符是否在string1中?最直观也是最简单的思路是，针对string2中每一个字符，逐个与string1中每个字符比较，看它是否在String1中。

代码可如下编写：

bool StringContain(string &a,string &b)
{
    for (int i = 0; i < b.length(); ++i) {
        int j;
        for (j = 0; (j < a.length()) && (a[j] != b[i]); ++j)
            ;
        if (j >= a.length())
        {
            return false;
        }
    }
    return true;
}

假设n是字符串String1的长度，m是字符串String2的长度，那么此算法，需要O(n*m)次操作。显然，时间开销太大，应该找到一种更好的办法。

解法二

如果允许排序的话，我们可以考虑下排序。比如可先对这两个字符串的字母进行排序，然后再同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。

关于排序方法，可采用最常用的快速排序，参考代码如下：

//注意A B中可能包含重复字符，所以注意A下标不要轻易移动。这种方法改变了字符串。如不想改变请自己复制
bool StringContain(string &a,string &b)
{
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    for (int pa = 0, pb = 0; pb < b.length();)
    {
        while ((pa < a.length()) && (a[pa] < b[pb]))
        {
            ++pa;
        }
        if ((pa >= a.length()) || (a[pa] > b[pb]))
        {
            return false;
        }
        //a[pa] == b[pb]
        ++pb;
    }
    return true;
}

解法三

有没有比快速排序更好的方法呢？

我们换一种角度思考本问题：

假设有一个仅由字母组成字串，让每个字母与一个素数对应，从2开始，往后类推，A对应2，B对应3，C对应5，......。遍历第一个字串，把每个字母对应素数相乘。最终会得到一个整数。

利用上面字母和素数的对应关系，对应第二个字符串中的字母，然后轮询，用每个字母对应的素数除前面得到的整数。如果结果有余数，说明结果为false。如果整个过程中没有余数，则说明第二个字符串是第一个的子集了（判断是不是真子集，可以比较两个字符串对应的素数乘积，若相等则不是真子集）。

思路总结如下：

按照从小到大的顺序，用26个素数分别与字符'A'到'Z'一一对应。
遍历长字符串，求得每个字符对应素数的乘积。
遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。
输出结果。

如前所述，算法的时间复杂度为O(m+n)的最好的情况为O(n)（遍历短的字符串的第一个数，与长字符串素数的乘积相除，即出现余数，便可退出程序，返回false），n为长字串的长度，空间复杂度为O(1)。

//此方法只有理论意义，因为整数乘积很大，有溢出风险
bool StringContain(string &a,string &b)
{
    const int p[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79, 83, 89, 97, 101};
    int f = 1;
    for (int i = 0; i < a.length(); ++i)
    {
        int x = p[a[i] - 'A'];
        if (f % x)
        {
            f *= x;
        }
    }
    for (int i = 0; i < b.length(); ++i)
    {
        int x = p[b[i] - 'A'];
        if (f % x)
        {
            return false;
        }
    }
    return true;
}

此种素数相乘的方法看似完美，但缺点是素数相乘的结果容易导致整数溢出。

解法四

如果面试官继续追问，还有没有更好的办法呢？计数排序？除了计数排序呢？

事实上，可以先把长字符串a中的所有字符都放入一个Hashtable里，然后轮询短字符串b，看短字符串b的每个字符是否都在Hashtable里，如果都存在，说明长字符串a包含短字符串b，否则，说明不包含。

再进一步，我们可以对字符串A，用位运算（26bit整数表示)计算出一个“签名”，再用B中的字符到A里面进行查找。

// “最好的方法”，时间复杂度O(n + m)，空间复杂度O(1)
bool StringContain(string &a,string &b)
{
    int hash = 0;
    for (int i = 0; i < a.length(); ++i)
    {
        hash |= (1 << (a[i] - 'A'));
    }
    for (int i = 0; i < b.length(); ++i)
    {
        if ((hash & (1 << (b[i] - 'A'))) == 0)
        {
            return false;
        }
    }
    return true;
}

这个方法的实质是用一个整数代替了hashtable，空间复杂度为O(1)，时间复杂度还是O(n + m)。

举一反三

1、变位词

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，比如bad和adb即为兄弟字符串，现提供一个字符串，如何在字典中迅速找到它的兄弟字符串，请描述数据结构和查询过程。

字符串转换成整数

题目描述

输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串"123"，输出整数123。

给定函数原型int StrToInt(const char *str) ，实现字符串转换成整数的功能，不能使用库函数atoi。

分析与解法

本题考查的实际上就是字符串转换成整数的问题，或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢？以"123"作为例子：

当我们扫描到字符串的第一个字符'1'时，由于我们知道这是第一位，所以得到数字1。
当扫描到第二个数字'2'时，而之前我们知道前面有一个1，所以便在后面加上一个数字2，那前面的1相当于10，因此得到数字：1*10+2=12。
继续扫描到字符'3'，'3'的前面已经有了12，由于前面的12相当于120，加上后面扫描到的3，最终得到的数是：12*10+3=123。

因此，此题的基本思路便是：从左至右扫描字符串，把之前得到的数字乘以10，再加上当前字符表示的数字。

思路有了，你可能不假思索，写下如下代码：

int StrToInt(const char *str)
{
    int n = 0;
    while (*str != 0)
    {
        int c = *str - '0';
        n = n * 10 + c;
        ++str;
    }
    return n;
}

显然，上述代码忽略了以下细节：

空指针输入：输入的是指针，在访问空指针时程序会崩溃，因此在使用指针之前需要先判断指针是否为空。
正负符号：整数不仅包含数字，还有可能是以'+'或'-'开头表示正负整数，因此如果第一个字符是'-'号，则要把得到的整数转换成负整数。
非法字符：输入的字符串中可能含有不是数字的字符。因此，每当碰到这些非法的字符，程序应停止转换。
整型溢出：输入的数字是以字符串的形式输入，因此输入一个很长的字符串将可能导致溢出。

上述其它问题比较好处理，但溢出问题比较麻烦，所以咱们来重点看下溢出问题。

一般说来，当发生溢出时，取最大或最小的int值。即大于正整数能表示的范围时返回MAX_INT：2147483647；小于负整数能表示的范围时返回MIN_INT：-2147483648。

我们先设置一些变量：

sign用来处理数字的正负，当为正时sign > 0，当为负时sign < 0
n存放最终转换后的结果
c表示当前数字

而后，你可能会编写如下代码段处理溢出问题：

//当发生正溢出时，返回INT_MAX
if ((sign == '+') && (c > MAX_INT - n * 10))
{

    n = MAX_INT;
    break;
}
//发生负溢出时，返回INT_MIN
else if ((sign == '-') && (c - 1 > MAX_INT - n * 10))
{
    n = MIN_INT;
    break;
}

但当上述代码转换" 10522545459"会出错，因为正常的话理应得到MAX_INT：2147483647，但程序运行结果将会是：1932610867。

为什么呢？因为当给定字符串" 10522545459"时，而MAX_INT是2147483647，即MAX_INT(2147483647) < n_10(1052254545_10)，所以当扫描到最后一个字符‘9’的时候，执行上面的这行代码：

c > MAX_INT - n * 10

已无意义，因为此时(MAX_INT - n * 10)已经小于0，程序已经出错。

针对这种由于输入了一个很大的数字转换之后会超过能够表示的最大的整数而导致的溢出情况，我们有两种处理方式可以选择：

一个取巧的方式是把转换后返回的值n定义成long long，即long long n；
另外一种则是只比较n和MAX_INT / 10的大小，即：
- 若n > MAX_INT / 10，那么说明最后一步转换时，n*10必定大于MAX_INT，所以在得知n > MAX_INT / 10时，当即返回MAX_INT。
- 若n == MAX_INT / 10时，那么比较最后一个数字c跟MAX_INT % 10的大小，即如果n == MAX_INT / 10且c > MAX_INT % 10，则照样返回MAX_INT。

对于上面第一种方式，虽然我们把n定义了长整型，但最后返回时系统会自动转换成整型。咱们下面主要来看第二种处理方式。

对于上面第二种方式，先举两个例子说明下：

如果我们要转换的字符串是"2147483697"，那么当我扫描到字符'9'时，判断出214748369 > MAX_INT / 10 = 2147483647 / 10 = 214748364（C语言里，整数相除自动取整，不留小数），则返回MAX_INT；
如果我们要转换的字符串是"2147483648"，那么判断最后一个字符'8'所代表的数字8与MAX_INT % 10 = 7的大小，前者大，依然返回MAX_INT。

一直以来，我们努力的目的归根结底是为了更好的处理溢出，但上述第二种处理方式考虑到直接计算n * 10 + c 可能会大于MAX_INT导致溢出，那么便两边同时除以10，只比较n和MAX_INT / 10的大小，从而巧妙的规避了计算n*10这一乘法步骤，转换成计算除法MAX_INT/10代替，不能不说此法颇妙。

如此我们可以写出正确的处理溢出的代码：

c = *str - '0';
if (sign > 0 && (n > MAX_INT / 10 || (n == MAX_INT / 10 && c > MAX_INT % 10)))
{
    n = MAX_INT;
    break;
}
else if (sign < 0 && (n > (unsigned)MIN_INT / 10 || (n == (unsigned)MIN_INT / 10 && c > (unsigned)MIN_INT % 10)))
{
    n = MIN_INT;
    break;
}

从而，字符串转换成整数，完整的参考代码为：

int StrToInt(const char* str)
{
    static const int MAX_INT = (int)((unsigned)~0 >> 1);
    static const int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
    unsigned int n = 0;

    //判断是否输入为空
    if (str == 0)
    {
        return 0;
    }

    //处理空格
    while (isspace(*str))
        ++str;

    //处理正负
    int sign = 1;
    if (*str == '+' || *str == '-')
    {
        if (*str == '-')
            sign = -1;
        ++str;
    }

    //确定是数字后才执行循环
    while (isdigit(*str))
    {
        //处理溢出
        int c = *str - '0';
        if (sign > 0 && (n > MAX_INT / 10 || (n == MAX_INT / 10 && c > MAX_INT % 10)))
        {
            n = MAX_INT;
            break;
        }
        else if (sign < 0 && (n >(unsigned)MIN_INT / 10 || (n == (unsigned)MIN_INT / 10 && c > (unsigned)MIN_INT % 10)))
        {
            n = MIN_INT;
            break;
        }

        //把之前得到的数字乘以10，再加上当前字符表示的数字。
        n = n * 10 + c;
        ++str;
    }
    return sign > 0 ? n : -n;
}

举一反三

实现string到double的转换

分析：此题虽然类似于atoi函数，但毕竟double为64位，而且支持小数，因而边界条件更加严格，写代码时需要更加注意。

软件：week4 问题反馈+扩展练习

week4 问题

大家学习编程差不多一个月多了，编程对初学者是非常痛苦的事情，我们也曾经历过上课听老师讲得如痴如醉，下课看书像看天书，做题感觉难到爆炸的时候。别慌，这都是称为强者必经之路。

说说我们大一的时候。我们的Ta是竞赛队的，然后出的题目特别难，我们有一次宿舍一个周日就做了一道题。反正我们是各种被虐，而且那时候实验课和理论课基本上脱节，实验课的内容大概超前2~3周左右。

说这些干嘛，就是想说，编程入门的门槛是不低的，他考验人的耐心、细心、专心和信心，同时也考验你严密的思维。

1、要善于观察和发现错误，善于总结经验。

比如，你看到scanf就要意识到参数需要取地址，否则就会出现内存报错。自己犯下的错误会一而再再而三地犯，比如赋值运算符 = 和逻辑判断相等 ==，比如变量忘记初始化，比如循环一轮之后没有把变量重新初始化，这些等等等，大家绝对会搞错。

2、要好好理解概念。

有人会说会打代码就行，那些理论可以不管。这些是误人子弟的说法。c语言是大家学习的一门编程语言，是一个很基础但是是全世界使用排名第一的语言，它里面蕴含很多计算机编程的基本的东西，其实只要搞懂c和下学期的c++，你会发现其他语言的学习完全可以通过类比的方式快速学到。功夫在语言之外，练功在语言之内。

3、养成好的编程习惯。

习惯是很难改的，编程也是一样，一旦养成一些坏毛病以后就一直那样了。为什么要抓代码风格？我参加过的一些大型项目里面就有很深刻的体会，那些代码量很大，是协同合作完成的，可是人与人之间的沟通成本是很大的。如果代码是乱乱的，变量名乱乱的，毫无注释，这些代码真的就是团队毒瘤，谁都看不懂。或者说，你自己写的代码乱用这那的，然后过一段时间你也不知道自己当时写的啥。所以这个真的很重要。

4、学会问问题。

问问题是一门艺术，真的。首先你要问，不要害怕同学或者师兄，很多问题你可以提出来的，不要不懂就放在那，然后抱怨很难。第二，问问题是有技巧的。
第一种问法：给一段长长的代码，跟我说，师兄，这个题不对啊，怎么办啊？
第二种问法：师兄，我这题系统显示runtime error，怎么办呀？
第三种问法：师兄，我这题系统显示runtime error。我的程序的思路是先用scanf读入两个整数，然后将他们相加，然后进行输出。在这个过程中我用到了三个变量，分别代表和（用于输出），两个临时变量进行存储两个输入的值。系统说运行时错误，运行时错误的原因，我查过了，可能是非法内存访问。请问这怎么办？

大家可以到stackoverflow上面看看大家是怎么提出技术问题的。

5、关于算法和语言。

什么是算法？
如果是有编程基础，或者志向于ACM队的同学，你就应该多搞算法，刷西西里的题目。对于其他同学我认为，你大可不必放太多精力去那些著名的算法理论中。这一年我们学的重点是基础，是学会如何使用编程语言，让他成为一个软件工程中的有效的工具，同时提取编程语言中的**。而且，以后你们学习算法的课还多了去了。

6、关于变量命名

我们对于变量一般采用意义来命名。也就是说变量是干嘛的就命名成什么。

比如一道题目，输入n个数，求n个数的和，那就应该这样声明变量：

int n; // the number of digits
int sum; // the sum of the n digits

而不要声明成

int a, b;

这两个声明方法的可读性有着本质性的区别，大家好好体会。

7、早起早睡

很多同学可能现在已经养成了熬夜的习惯。可是我想说，无论你是社团任务重还是课程任务重，都不要选择熬夜。第一熬夜很伤身，第二早起的效果更好。以后周日的作业还是周一早上在放出来，免得大家熬夜写作业，真心不好。

本周扩展题目

week 4 扩展题

有些题目难度很大，希望你只看一眼，起码要知道题目是要你干嘛的，思考一下，实在做不来就放着，继续看书自学，争取走在老师前面，这样效果更好。

特别注意：贪吃蛇那道题目是你们软件工程导论之后要做的课程项目，那个题给了你们核心算法的思路，可以看看。

记得在周日前提交实验报告

同时之后会有实验课的课程设计，大家做好心理准备

有任何问题，欢迎留言，无论学习c语言还是其他课程或者大学生活，欢迎。

还有，以后实验课问问题可以报下自己什么名字，好让我认识一下大家。Ta也是大家朋友，一起学习嘛。

13级嵌入式：叶嘉祺
2015年10月19日

计科：week11 额外作业

计科：week11 自编选择题

week11 Experiment 5.5

自编选择题

由于本周没有实验任务，根据老师要求，添加小小的课后练习。很轻松，很简单，也很有趣。

要求

每个人设计三道选择题。
每一道选择题覆盖的知识点不限，但不能太简单，一看就懂的那种就十分不建议。
最好是C++语言中难以理解的知识点，或者容易忽略的重点。
除了问题以外，你还有为你的问题准备答案，以及相关解释。
周五上课随机抽取部分同学的选择题，让大家一起做，然后由作者讲解，其他同学可以质疑并提问。
请使用英文。

模板

0 简介

你的姓名学号
balabala你出题的初衷诸如此类

1 题目

1.1 题目1

balabala题目内容

1.2 题目2

balabala题目内容

1.3 题目3

balabala题目内容

2 答案及解析

2.1 题目1答案及解析

balabala题目答案及解析

2.2 题目2答案及解析

balabala题目答案及解析

2.3 题目3答案及解析

balabala题目答案及解析

提交

提交到如下文件夹。

命名格式

cs_cpp_学号_姓名_exp5.5.pdf

Deadline

12月3日 21：00

最后

请把你的题目部分添加到本github下面的评论区域，就像你的期中总结一样。

格式：(注意加粗和空行，为了好看些~)

学号：1555xxxx，姓名：张三

题目1：
balabala题目内容

题目2：
balabala题目内容

题目3：
balabala题目内容

wujr5 / c-and-cpp-language-learning Goto Github PK

c-and-cpp-language-learning's People

Contributors

Stargazers

Watchers

Forkers

c-and-cpp-language-learning's Issues

计科：实验课反馈

第二次课

Attention:

计科：实验课分享

计科：实验课计划

1 实验报告

1.1 第一次实验报告

1.2 第二次实验报告

1.3 第三次实验报告

1.4 第四次实验报告

1.5 第五次实验报告

1.6 第六次实验报告

1.7 第七次实验报告

1.8 第八次实验报告

1.9 第九次实验报告

2 习题课

2.1 第一次习题课

2.2 第二次习题课

3 考试

3.1 期中考试

3.2 期末考试

DDL：

命名：

要求，对每道题写简单的解释，并且理解。

计科：week6 第五次课总结

1 Sicily习题

2 第一次选择题

3 第二次实验报告

3.1 学习冒泡排序算法

3.2 存在问题

3.3 优秀作业展示

4 关于作业和成绩

计科：实验课要求

1 代码风格

2 Gitbub账号

3 Discussion

4 注意目录

经历了半个学期的痛苦、煎熬、无奈、彷徨的DDL

个人总结（技术博客）

深入学习思考

关于算法

关于高数、线代：

对于兴趣的建议

总结

1 阅读www.cplusplus.com 中关于iomanip, cmath的代码和例子

2 提交两个程序和一份实验报告

程序1：learn-iomanip.cpp

程序2：learn-cmath.cpp

心得：

week12 project1 The Snake Game

1 Brief Introduction

2 Requirement

2.1 Developmental Enviroment

2.1 Debug Tool

3 Detail Documents (80pts)

3.1 User Interface

3.2 Demand

3.2.1 How to Play Your Game (30pts)

3.2.2 How to Win the Game (20pts)

3.2.3 When Will the Player Lose the Game (20pts)

3.2.4 Extends (10pts)

4 Report Template (20pts)

(1) Deploy

(2) Pseudocode and Flowchart

(3) Feelings and Experimences

(4) Bonuses

5 Development Advice

6 Bonuses

7 Attachment

8 Submit

9 Deadline

Project1：

An introduction to List

1 第五次课第三次实验