wujr5 / c-and-cpp-language-learning Goto Github PK
View Code? Open in Web Editor NEWC和C++编程语言学习 - 2015级
C和C++编程语言学习 - 2015级
对于project1的任何问题,计科的同学请在这里讨论。
自行编写小程序,要求:
程序1.格式化输出,输出一个表格
程序2.以不同颜色输出helloworld(提示:使用windows.h库)
程序3.使用<cstring>中8个函数,并计时,将程序运行时间输出
效果图及实验模板链接:模板及效果图
表格打印:
颜色输出:
当然你可以选择打印彩色的表格。
打包成zip或rar格式
文件命名
学号_姓名(主目录)
- table.cpp
- color.cpp
- stringFunction.cpp
- 学号_实验报告.pdf
注意,基本要求就是实现上述两个图片上的效果。至于,是否需要人工输入数据,是否有其他的功能,你自己选择,请在实验报告注明。原则就是:做的越多,分数越高,当然你做的东西是要有意义的,如果只是多输出一行数据,那就是没意义的。
2015年11月5日晚12点,务必及时提交
大家学习编程差不多一个月多了,编程对初学者是非常痛苦的事情,我们也曾经历过上课听老师讲得如痴如醉,下课看书像看天书,做题感觉难到爆炸的时候。别慌,这都是称为强者必经之路。
说说我们大一的时候。我们的Ta是竞赛队的,然后出的题目特别难,我们有一次宿舍一个周日就做了一道题。反正我们是各种被虐,而且那时候实验课和理论课基本上脱节,实验课的内容大概超前2~3周左右。
说这些干嘛,就是想说,编程入门的门槛是不低的,他考验人的耐心、细心、专心和信心,同时也考验你严密的思维。
比如,你看到scanf就要意识到参数需要取地址,否则就会出现内存报错。自己犯下的错误会一而再再而三地犯,比如赋值运算符 =
和 逻辑判断相等 ==
,比如变量忘记初始化,比如循环一轮之后没有把变量重新初始化,这些等等等,大家绝对会搞错。
有人会说会打代码就行,那些理论可以不管。这些是误人子弟的说法。c语言是大家学习的一门编程语言,是一个很基础但是是全世界使用排名第一的语言,它里面蕴含很多计算机编程的基本的东西,其实只要搞懂c和下学期的c++,你会发现其他语言的学习完全可以通过类比的方式快速学到。功夫在语言之外,练功在语言之内。
习惯是很难改的,编程也是一样,一旦养成一些坏毛病以后就一直那样了。为什么要抓代码风格?我参加过的一些大型项目里面就有很深刻的体会,那些代码量很大,是协同合作完成的,可是人与人之间的沟通成本是很大的。如果代码是乱乱的,变量名乱乱的,毫无注释,这些代码真的就是团队毒瘤,谁都看不懂。或者说,你自己写的代码乱用这那的,然后过一段时间你也不知道自己当时写的啥。所以这个真的很重要。
问问题是一门艺术,真的。首先你要问,不要害怕同学或者师兄,很多问题你可以提出来的,不要不懂就放在那,然后抱怨很难。第二,问问题是有技巧的。
第一种问法: 给一段长长的代码,跟我说,师兄,这个题不对啊,怎么办啊?
第二种问法:师兄,我这题系统显示runtime error,怎么办呀?
第三种问法:师兄,我这题系统显示runtime error。我的程序的思路是先用scanf读入两个整数,然后将他们相加,然后进行输出。在这个过程中我用到了三个变量,分别代表和(用于输出),两个临时变量进行存储两个输入的值。系统说运行时错误,运行时错误的原因,我查过了,可能是非法内存访问。请问这怎么办?
大家可以到stackoverflow上面看看大家是怎么提出技术问题的。
什么是算法?
如果是有编程基础,或者志向于ACM队的同学,你就应该多搞算法,刷西西里的题目。对于其他同学我认为,你大可不必放太多精力去那些著名的算法理论中。这一年我们学的重点是基础,是学会如何使用编程语言,让他成为一个软件工程中的有效的工具,同时提取编程语言中的**。而且,以后你们学习算法的课还多了去了。
我们对于变量一般采用意义来命名。也就是说变量是干嘛的就命名成什么。
比如一道题目,输入n个数,求n个数的和,那就应该这样声明变量:
int n; // the number of digits
int sum; // the sum of the n digits
而不要声明成
int a, b;
这两个声明方法的可读性有着本质性的区别,大家好好体会。
很多同学可能现在已经养成了熬夜的习惯。可是我想说,无论你是社团任务重还是课程任务重,都不要选择熬夜。第一熬夜很伤身,第二早起的效果更好。以后周日的作业还是周一早上在放出来,免得大家熬夜写作业,真心不好。
有些题目难度很大,希望你只看一眼,起码要知道题目是要你干嘛的,思考一下,实在做不来就放着,继续看书自学,争取走在老师前面,这样效果更好。
特别注意:贪吃蛇那道题目是你们软件工程导论之后要做的课程项目,那个题给了你们核心算法的思路,可以看看。
13级嵌入式:叶嘉祺
2015年10月19日
不少同学还是没有看gitub的issue,那些scanf和printf问题上周issue已经说过,不看是自己吃亏。看了不懂再提出问题,总比在实验课上写scanf("char a = %c")
还纠结为什么错高效率很多。
其次,再次强调一下,扩展题目也是自己自学为主,不强制要求做,不占期末分数,没有ddl,也没有提交规定。这个题目老师也没有要求我们出,出这个题主要目的是使让大家提前预习前面的知识,提前自学完,到老师讲概念定义的理论时候,你就不会晕,也知道怎么回事。这是一种高效率的学习方法。做不出来没关系,学完到一定程度再做。
另外,我每周会放一些往年的期中或者期末考试题在扩展题上,供大家参考。
编程语言学习不是像高中时候学语文数学那样拿着书,听老师讲就行了。有很多知识老师是不讲的,而且书上面也没有。比如,一个库函数 double log(double _x)
,书本或者老师不会教你怎么怎么用的,必须要你自己去百度或者谷歌。
搜索引擎:
谷歌、百度
参考it界的学习网站:
Stack Overflow
CSND 博客
开源**
编译器的一个很重要的功能就是检查你写的代码是否符合这个语言定义的语法,一定要学会看编译器的提示信息,例如:
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);
^
在线评测系统(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出来,这样题目没有任何意义。
大家现在写的代码开始复杂了,代码风格也就开始不管了。有些同学把所有的计算表达式全部放到printf里面,看的我眼花缭乱。有的同学写代码左对齐,毫无缩进,非常难看。
1、请大家检查自己的代码风格,用之前的cpplint,否则一年之后你会埋怨我没有抓代码风格,到时候习惯了之后,你会发现那样写的代码是项目毒瘤。
2、你可以给其他同学看你的代码,看看你要花多少口舌解释你的代码,就是你这份代码在协同工作时候的交流成本,这个肯定越低越好。
练习:给你的同学看1003你提交的代码,让他理解1003那个题目的思路,和各个变量是干嘛的。
现阶段西西里的课程练习题都是中文的,而考试的时候是英文的。你怎么读这个题目,决定了你是否能做对这个题目。比如,二次方程的题目明确说明了输出时候小根在前,大根在后,这是题目的关键信息,然而不少同学直接忽略。
所以,请大家认真读题目。
函数是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);
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
实验目的:当大家学习了程序的控制结构之后,代码就变得复杂起来。在这时,我们解决问题就需要有很严密的逻辑思维。程序流程图和伪代码就是帮助我们去描述我们解决问题的方法(也称为算法)的工具。本次实验在于让大家学习如何使用这些工具,这对大家以后的编程有很大的帮助。
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:
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.
Learn about Flowchart and Pseudocode.
Choose one question from soj.me in week6 in our course and then write the Pseudocode.
Translate the following flowchart into Pseudocode
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).
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
(0,2)
(200004,0)
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;
}
Draw a flowchart and write Pseudocode as well as a C++ language program for the following description.
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
Comment at this issue and decribe a problem that you meet and how you solve detailedly.
Notice that
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
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
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
There will be no Report Template this time which means it's all depends on yourself.
Notice that
For example: sinew
Process on is a good tool for drawing flowchart.
link
Notice that:
13331314 means your student id.
the first assignment need to name your file with your chosen problem id.
23:59 on Nov 12th, 2015
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:
Ubuntu or other linux operating system is required
There will be at least 50% penalty for the use of Dev-cpp in windows
GDB. Just watch the video of introduction of gdb. To know more detail usage of gdb, search it.
Like the following picture. If you want to make some changes, just do it !
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.
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.
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:
Here discribe how to run your game and discribe the operating environment.
Write down the pseudocode and flowchart of your game, just use the knowledge you have learned in lab4
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.
Show me what bonuses you have finished.
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.
cs_project1_学号_姓名.zip
|-- // add your files here
2015, Dec 30th, 21:00
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
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.
windows: commandline or DEV cpp
ubuntu linux: command line (optional bonus)
ubuntu linux using command line and makefile (optional bonus)
使用linux开发可以加分,期末考试很可能使用linux系统。
另外,ftp上有相关虚拟机和镜像文件下载,以及安装教程,入门教程等。
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.
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.
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.
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.
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.
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 *));
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 is very important for you. The style rules including google style are required.
What's more, you should have good comments with your code.
Maybe you will us File IO operation, you can use your own data format. Json or CVS is recommended.
Make a brief introduction for your project.
Statements about how to run the program. How to use this system.
Statements about your project structure, i.e. your function interfaces and file structure.
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.
Some important algorithm and data structure you use should be mentioned. And draw flowchart or write Pseudo code for them.
Statements about how you test the system.
Personal summary about this project.
We will ask some students to discuss about how to build a framework for the system on Dec 14th 2015.
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.
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 to the course ftp
ftp://172.18.182.75
username:c_and_cpp
password:c_and_cpp
filename : 13331314_叶嘉祺_CourseProject.zip
代码不限形式
规定要用到函数setiosflags, resetiosflags, setbase, setfill, setprecision, setw六个函数
要有良好输出,有对比,让我知道你了解了如何使用这些函数
没使用要求的函数,或者输出没让我看懂你是否了解函数的作用,扣分!
代码不限形式
规定使用到你感兴趣的中的函数
有良好的输出,有对比。剩下的要求同程序1
模板,转发学习委员
Now, we are going to do a small project named a small plane 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:
Actions:
#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
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);
}
You do not need to write this part to your report.
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:
(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.
just send me your github address.
2015 12.15 18:00
https://github.com/LGA1150/IPv6-hosts
记得强制HTTPS方式访问!
chrome://net-internals/#hsts
SDCS2015, 15331058
一共4个文件,几百题。
现在题库**563题。同学们可完成每一类别题目中的三分之一。多做不限。
文件在群共享和FTP的Resource文件夹均有。
2015年12月30日 18:00
2015年12月30日 21:00
13331314_叶嘉祺_理论题.pdf
唠叨几句:
大家叫师兄就好了,不要叫老师,听着别扭=_=。
上了实验课或者上了理论课,可能比较多的同学会有这样的想法:学了这些到底有什么用?好像觉得就只是敲几行不知道在干嘛的代码,输出一些不知道干嘛的结果。非常无聊。
对于这个问题,我还真不知道怎么回答。因为我大一的时候也是这样想的。其实软件工程专业,c语言是非常基础的一门语言,很多计算机类专业都以c语言作为入门语言。作为初学者,最重要的是对语言本身语法的了解和认识,算法的话,学有余力可以深究,这门课不会对算法有过高的要求。
我觉得现在同学们coding最大的动力来源于学业要求和把题目做对的成就感吧。在我们学校,你能真正利用编程做出产品或者有趣的东西,可能要到大二,那个时候你可能真的要迷恋上编程了。现在的话,我建议是,加油吧,好好学~慢慢的你会发现其实敲代码挺有意思的。
第一周要求很低。基本上是熟悉练习系统Sicily,还有编辑器DevCpp的使用。对于这两个要求,我相信不会有什么问题。问题集中出现在同学们对c语言语法的理解上面。
下面列出出现频率较高的错误。
scanf("%d", &a);
使用scanf
函数读取输入内容,放到变量中的时候,记得添加取址运算符&
system("pause");
时,记得在头文件添加#include<stdlib.h>
Sicily系统没有在编程风格上作要求,只要你的代码能运行,输入输出没问题,就可能可以通过。但是这样会写出可能可读性很差的代码。因此我们TA强烈要求同学们一定要注意自己的代码编写的风格。
下面介绍一个工具的使用来进行代码风格检查。
教程:安装python
要注意的是,教程中说的系统变量就是python的安装路径。
点击下载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]
指的是代码中出现的错误。
根据输出的错误,逐行改进代码。直到错误数目为0。如Total errors found: 0
:
把通过google style的cpplint.py测试的代码,也就是Total errors found: 0
,再把代码提交到Sicily。
进行google style风格检测的目的是让同学们写出可读性良好的代码。按照上面的流程编写代码,能帮助你养成良好的编程习惯。希望同学们重视。
有任何问题欢迎评论。我们会持续改进。
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
为什么使用命令行编译?
配置方法:
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,这是一款收费软件,可是有无限试用期。
下载和使用请自行百度。
现在大家做题一般的输入方法就是,按照西西里的测试例子,键盘输入,当程序错误的时候需要一次次输入非常繁琐,现在给大家提供一种高效而且重要的方法,文件流输入代替键盘流输入。
其实,在抽象的层面上,键盘输入、文件输入和网络输入等都是IO,是等价的。我们可以利用这个进行文件代替键盘输入。
1、在刚才我们编译的程序之中,我们生成了main.exe的程序。建设现在我们的程序是做a-b的简单运算。我们现在在源代码的同一个目录下新建一个文件"input.txt"。我们打开文件输入两个数100和99。
2、接着我们在命令行输入命令main.exe < input.txt
。我们很惊喜地发现,程序自动输出了1,我们不需要手动去使用键盘输出。
对于长而复杂的输入,这无疑是一个简化的过程。
对于文件输出,同样是可以的 'main.exe < input.txt >output.txt'
#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、执行程序、单步运行
实验目的:当大家学习了程序的控制结构之后,代码就变得复杂起来。在这时,我们解决问题就需要有很严密的逻辑思维。程序流程图和伪代码就是帮助我们去描述我们解决问题的方法(也称为算法)的工具。本次实验在于让大家学习如何使用这些工具,这对大家以后的编程有很大的帮助。
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:
Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.
From wikipedia
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.
Learn about Flowchart and Pseudocode.
Choose one question from soj.me in week6 in our course and then write the Pseudocode.
Translate the following flowchart into Pseudocode
Translate the following flowchart into Pseudocode and C programming language program.
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).
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
(0,2)
(200004,0)
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;
}
Draw a flowchart and write Pseudocode as well as a C language program for the following description.
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)
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
Comment at this issue and decribe a problem that you meet and how you solve detailedly.
Notice that
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
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
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
There will be no Report Template this time which means it's all depends on yourself.
Notice that
For example: sinew
Process on is a good tool for drawing flowchart.
link
Notice that:
13331314 means your student id.
the first assignment need to name your file with your chosen problem id.
18:00 on Nov 7th, 2015
学习委员整理好发到邮箱:[email protected]
不接受作业单独发到邮箱
From: The Art of Programming link
给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“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个步骤操作即可:
如下图所示:
代码则可以这么写:
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。如果整个过程中没有余数,则说明第二个字符串是第一个的子集了(判断是不是真子集,可以比较两个字符串对应的素数乘积,若相等则不是真子集)。
思路总结如下:
如前所述,算法的时间复杂度为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、变位词
输入一个由数字组成的字符串,把它转换成整数并输出。例如:输入字符串"123",输出整数123。
给定函数原型int StrToInt(const char *str)
,实现字符串转换成整数的功能,不能使用库函数atoi。
本题考查的实际上就是字符串转换成整数的问题,或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢?以"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。
我们先设置一些变量:
而后,你可能会编写如下代码段处理溢出问题:
//当发生正溢出时,返回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定义了长整型,但最后返回时系统会自动转换成整型。咱们下面主要来看第二种处理方式。
对于上面第二种方式,先举两个例子说明下:
一直以来,我们努力的目的归根结底是为了更好的处理溢出,但上述第二种处理方式考虑到直接计算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;
}
分析:此题虽然类似于atoi函数,但毕竟double为64位,而且支持小数,因而边界条件更加严格,写代码时需要更加注意。
要求:
1. 具体实现方式可以上网查
2. 实验报告写上你对算法的理解
3. 程序:输入n,表示有n个数输入,接着输入n个随机的整数。输出:从小到大的有序的数,空格分隔。
4. 拓展:改进版本的冒泡
5. 提交:实验报告+程序。
6. deadline: 本周日晚12点。
请在评论中写下你对实验课的建议或者意见,我们集中讨论,协商问题。记住,一切都是为了让你更好地学习,有问题,请大胆说出来。
大家可能是上大学以来第一次写实验报告,可能问题挺多,下面将详细介绍。
另外,对于大家提出的建议进行一一回答。
很遗憾你们遇到我这个大一实训时候的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上这个仓库。
可能还有些同学的问题没有解答。总结起来,大家学习的过程中需要多提问题,不要自己憋着;多和大家讨论;多思考,深入的思考。
Reserved...
如果熟悉linux系统,且有使用经验的,或者已经安装的同学,直接截图即可,可以不用做第一个额外任务。
在FTP上可以下载。
下载以上文件到你的电脑。
按照普通的安装步骤即可:双击运行。
注意,可能要求输入安装密钥等。百度之 or 土豪可购买之。涉及版权问题,在此不再细说。
观看视频教程:
将以上安装步骤适当截图,放在report.pdf里面。
如果熟悉linux系统,且有使用经验的,或者已经安装的同学,直接截图即可,可以不用安装虚拟机。
YOJ 在线评测系统
如题。很多同学已经产生对编程无比的抗拒了,大家油然而生一种感觉,我是当初脑子进水了才报软件工程专业,这个专业各种各样的作业,看着别的同学上大学悠闲自在,自由飞翔,羡慕死了。
我们天天被西西里虐成狗,被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程序。
希望大家能学的更好。
这个不用担心,平时成绩的平均分90分左右,之前所有改的作业的得分是按照真正高要求的中肯评分。说了挺多次都叫大家别太在意分数这件事情,确实,来大学学习是为分数的话,很悲哀。
分数这东西确实能够给你带来奖学金,确实会在你找工作的时候有一定作用。然而在谷歌这样的全球的公司是很轻视你的绩点的,特别是**大学,这些基本上没有用。
真真正正是我们核心竞争力的东西是最基础的一些问题,比如c语言的一些问题(我们做过一些)。
选择这个专业真正能够提升你个人核心力的,就是那些你很痛苦地写出来的程序,很纠结地解决的问题。
我个人认为语言是一种表达**的工具,无论什么语言都是人类企图和计算机交流的工具。这个学期我们学习的是程序设计1,而不是叫做c语言。很明显c语言程序只是程序设计很小的一个部分。
所谓功夫在语言外,有个老师说的话很经典:“就像莫言获得诺贝尔文学奖一样,并不是因为莫言比我们会多几个汉字,或者是语言。” 因此,接下来的面向对象程序设计、离散数学、数据结构与算法、操作系统、计算机网络、数据库等等,很多都是语言外的功夫。
是不是c语言就学完了?
明显没有。
下学期的重点应该是面向对象编程(不过可能杨老师的重点还在指针那些,很可能你们先学到的面向对象的思维就比较少了)。c++绝对不是简单地把printf变为cout而已,
这个下学期再说吧。
这个自己自由,我也不会改,也没有ddl;
期末project较多,不说多了,大家有问题在下面吐槽。哈哈哈哈哈。
可能给大家的作业或者难度偏大。嗯,其实写那么多字的题目还要费脑子想还是很花时间的。师兄也没那么变态总想着虐你们。嗯,过来人,希望大家坑得不要那么深。
给大家造成压力,说声对不起了。
由于本周没有实验任务,根据老师要求,添加小小的课后练习。很轻松,很简单,也很有趣。
要求
模板
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题目内容
Reference :Stackoverflow
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.
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)
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).
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 herein 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.
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
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
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级 嵌入式软件开发方向
Mail: [email protected] or [email protected]
Tel: 18819473270
授课方式:弃用ppt,完全使用github
主题:学习iomanip, cmath库函数
时间:week3
主题:学习冒泡排序算法
时间:week4
主题:格式化输出,使用windows.h,使用cstring
时间:week5
主题:程序流程图和伪代码
时间:week6
主题:再谈代码风格检查,断点调试
时间:week7
主题:基于命令行窗口的小游戏 贪吃蛇
时间:week8 - week10
主题:linux系统初探
时间:week11 - week12
主题:学生信息管理系统
时间:week13 - week15
主题:总结回顾在sicily做过的所有习题
时间:week16
时间:初定week11周末
时间:初定week16周末
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.
memcpy
Copy block of memory (function )
memmove
Move block of memory (function )
strcpy
Copy string (function )...
strncpy
Copy characters from string (function )
strcat
Concatenate strings (function )
strncat
Append characters from string (function )
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 )
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 )
memset
Fill block of memory (function )
strerror
Get pointer to error message string (function )
strlen
Get string length (function )
NULL
Null pointer (macro )
size_t
Unsigned integral type (type )
From cplusplus.com
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;
}
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
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.
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)#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.
Just answer the questions in deep thinking part
作业提交方式:作业由学委收好,再发到我邮箱.
地址: ftp://172.18.182.75/
远程目录: Experiment/计科班/Experiment6
命名规范:13331314_叶嘉祺_EX6_v0.zip
注意v0代表你提交的版本号,第一次提交为v0,第二次为v1,以此类推
注意,要打包压缩程ZIP格式
--13331314_叶嘉祺_EX6.zip
|--myString.cpp
|--report.pdf
注意,文件压缩包里不能出现文件夹,只能包含一层目录
作业缓交或补交:每缓交一天 -5% 总分
12月10日 18:00
1、文件命名绝对不能错
2、你需要先学习如何写一个函数库。也就是第一个任务,如何编写.h文件和.cpp文件分开,然后在main函数中调用.h文件中的函数。说白了就是明白#include 这种实现的机制。
3、.h文件和.cpp文件请严格遵守要求中的约定。设定好的函数原型和.h文件请不要更改,并且理解为什么一字不能改?对于系统构架师(编写.h的工程师)和具体实现的工程师(编写.cpp文件工程师),以及测试工程师(编写main.cpp进行测试的工程师),和用户(调用库函数的人)之间是怎样合作,怎样沟通理解的?
4、请先自己尝试编写main函数进行测试(文件分离,再编写)
为什么使用命令行编译?
配置方法:
1、打开Dev Cpp,并且找到对应的安装路径。
2、找到定义的MinGW目录下的bin目录这个是dev cpp的核心编译器。
3、配置系统环境变量,在系统的高级选项中找到path(可见第一周python配置方法)
4、打开cmd窗口,输入gcc --version输出编译器版本信息,配置完成。
编译方法:
g++ main.cpp -o main.exe
(如果省略-o后面的命令,则会生成a.exe)现在大家做题一般的输入方法就是,按照西西里的测试例子,键盘输入,当程序错误的时候需要一次次输入非常繁琐,现在给大家提供一种高效而且重要的方法,文件流输入代替键盘流输入。
其实,在抽象的层面上,键盘输入、文件输入和网络输入等都是IO,是等价的。我们可以利用这个进行文件代替键盘输入。
main.exe < input.txt
。我们很惊喜地发现,程序自动输出了1,我们不需要手动去使用键盘输出。对于长而复杂的输入,这无疑是一个简化的过程。
对于文件输出,同样是可以的 main.exe < input.txt > output.txt
#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;
}
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.
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).
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:
Notice that
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
#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;
}
#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;
}
#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;
}
}
}
格式无要求,part two必须截图表明你使用了断点调试的技巧来调试你的代码,包括但不限于:如何添加断点,如何删除断点,如何运行下一条语句,如何运行到下一个断点,如何添加查看,如何删除查看,等等。
作业发给学委,不要发压缩包,注意文件命名必须完全一致,否则机器测试无法进行,0分处理。
19 Nov. 2015, 23:59
Please submit your homework on time.
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
Comment at this issue and describe a problem that you meet and how you solve it detailedly.
Notice that
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
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
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
本周题目仍然较为简单,大概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个整数,这两者是一样的。
Time Limit: 1sec Memory Limit:256MB
输入一个数,输出对应的这样的图像:
link
Time Limit: 1sec Memory Limit:256MB
输入两个整数A和B,输出这两个整数的商A除以B,保留两位小数。
注意:当除数为0时候应当输出“Error!”
3 5
0.60
1 0
Error!
注意使用浮点数运算
Time Limit: 1sec Memory Limit:256MB
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
1 0
1 0
x^2
Time Limit: 1sec Memory Limit:256MB
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 指的是数字的大小!不是长度!╮(╯▽╰)╭)
123456789011121314151617181920
101
#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;
}
#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;
}
#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;
}
#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);
}
}
#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;
}
#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;
}
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之后发邮件,这样非常混乱。
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后留言,欢迎讨论。
同学展示
参考:
随机抽取5个同学的选择题让同学们来做,然后作者讲解,同学们提问并质疑。
Sicily系统没有在编程风格上作要求,只要你的代码能运行,输入输出没问题,就可能可以通过。但是这样会写出可能可读性很差的代码。因此我们TA强烈要求同学们一定要注意自己的代码编写的风格。
下面介绍一个工具的使用来进行代码风格检查。
教程:安装python
要注意的是,教程中说的系统变量就是python的安装路径。
点击下载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]
指的是代码中出现的错误。
根据输出的错误,逐行改进代码。直到错误数目为0。如Total errors found: 0
:
把通过google style的cpplint.py测试的代码,也就是Total errors found: 0
,再把代码提交到Sicily。
进行google style风格检测的目的是让同学们写出可读性良好的代码。按照上面的流程编写代码,能帮助你养成良好的编程习惯。希望同学们重视。
有任何问题欢迎评论。我们会持续改进。
For a deep understand for c pointers and functions, we will take a project.
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.
answer the questions in deep thinking part in your report
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.
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);
}
The operations about list are appending, deleting, modifying, querying.
we use this simple list again:
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;
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.
大家可以在评论中分享你觉得很有价值的东西,觉得可能对大家有用的东西。TA会鉴定你所分享的内容,如果不恰当,可能会被修改或者删除。但是请不要因为这样而害怕或者拒绝分享,因为交换想法或者**,你将收获巨大。
为了同学们更好地学习C++程序设计实验课,特别列出以下对学习有帮助的要求。
要求符合google style。在线google style检查:google style
要求每个人都注册github账号,并且watch项目:c-and-cpp-language-learning
要求有问题尽量在github上面讨论,因为这样能尽可能记录问题,如果其他人也遇到类似问题,那么他就能直接在提问中学习,而不需要重新提问。
建议使用主页的目录帮自己组织内容。如果直接看issue的列表,你会凌乱的。
作业写在纸上,写上姓名学号,在实验课结束后提交。
对于每一道题目,写上答案,并且写上解题思路,为什么选这个?(根据什么?)
英文答题
😄 😄 😄
答题例子:
// example
正式题目:
要求:每个人都要在这里写下评论总结。并截图放到第五次实验报告当中。如果没有写,实验报告扣除相应分数。
如果你实在不想写,可以联系我,视情况可以免写。
以下格式供参考,不限于以下格式。
格式:
学号:15xxxxx
前半学期学习总结:balabala...
期中考试总结:balabala...
后半学期学习规划:balabala...
本周无特别内容。提供课件作为参考:课件下载
1、文件命名绝对不能错
2、你需要先学习如何写一个函数库。也就是第一个任务,如何编写.h文件和.c文件分开,然后在main函数中调用.h文件中的函数。说白了就是明白#include <stdio.h>这种实现的机制。
3、.h文件和.c文件请严格遵守要求中的约定。设定好的函数原型和.h文件请不要更改,并且理解为什么一字不能改?对于系统构架师(编写.h的工程师)和具体实现的工程师(编写.c文件工程师),以及测试工程师(编写main.c进行测试的工程师),和用户(调用库函数的人)之间是怎样合作,怎样沟通理解的?
4、请先自己尝试编写main函数进行测试(文件分离,再编写)
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.
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);
}
Function Prototype
extern void *malloc(unsigned int num_bytes);
注意,对于一个函数,一定要看函数原型,函数原型里面包含了这个函数接口功能的很多信息。
这个函数的名称是malloc,动态分配内存
参数是unsigned int num_bytes,意思是分配的内存的字节数。
返回值是void 指针,理论是就是应该指向被分配的内存。
由于返回的指针是一种泛型编程**中的无类型指针,所以应该强制转换为你需要的类型。
注意:在一次malloc函数调用中,返回的一段内存是连续的
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.
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;
}
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:
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;
}
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:
memset
or other memory operation on the whole block of memory, you can not get your expected result.#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.
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 --+---+
----------
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:
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
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:
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:
(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
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, write a program to explain your reasons.
Dec 19th, 2015 18:00
Submit to ftp
Filename : 13331314_叶嘉祺_DMA.pdf
周一早上随机提问同学相关知识
1003输入0结束循环那里,卡了,输入0也输出0,导致一直wrong answer。
同学上来讲解题目。每题加5分,记在本周实验报告上。每个人不限题目数,能讲多少讲多少。
展示者:郑兴达
可以当场报名展示...
初定:11月21日
本次实验报告每人加分15,直到加满100。其他同学尽可效而仿之,但希望诚实真实,不辜负TA对你们的付出和信任。
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!
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++.
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.
Please name after the template below.
虽然只有一个文件,但是也请将打包压缩
cs_final_project_option1_学号_姓名.zip
|-- report.pdf
提交到ftp上的相应目录上。
链表是一种比较重要的数据类型。大家应该听说过这样的一种说法,程序 = 语言 + 数据结构 + 算法。可能大家要区分一下数据类型和数据结构的概念。我们到目前为止,学习的唯一的数据类型可能就是数组了。数据类型呢,就是平时熟练运用的int, float, double, char之类的了。
下面是C++数据类型的总结。
C++数据类型
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
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),按这个**建立的表为散列表。
了解链表组成,自学关于链表的数据结构。
要求实现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);
Final project
1 简介
Brief introduction of you and your project.
2 函数功能介绍
类似软件文档,介绍你的函数的用法和功能等
3 心得体会
你的心得体会
只需要提交simpleList.cpp文件
cs_final_project_option2_学号_姓名.zip
|-- simpleList.cpp
|-- report.pdf
提交到ftp上的相应目录上。
C++程序设计期末考试之前。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.