CS计算机代考程序代写 c/c++ Slide 1

Slide 1

Aspects of Programming Languages
Know your paradigms:
OOP
Procedural
Functional
Service Oriented
1

Aspects of Programming Languages
Know your analysis methods
Efficiency
Reliability
Readability
Writeability
Resusability
2

The Structure of Programs
Different levels of analyses:
lexical:
variable name, symbol, begin … end, { … };
syntactic:
if … then … else …, switch, for … Do structures
contextual:
Variable type and initialization, etc.
semantic:
meaning of a program, dynamic execution
3

The Structure of Programs
Know your errors:
Syntax – is it built correctly?
Context – is it built from the right stuff?
Semantic – is it working correctly?
4

Syntactic Analyses: Backus-Naur Form (BNF)
BNF: Meta-language for describing languages, context free language:
non-terminal symbol: symbols in grammar — don’t appear in final program
terminal symbol: symbols that appear in actual program — go no further in translating from grammar

5

Syntactic Analyses : BNF Example
Programming Language Example
::= a | b | c | … | z | 0 | 1 | … | 9
::= + | – | * | / | % | < | > | == |  | 
::= | < variable>
< expr > ::= < variable>
| ( ) ( )
::= < variable> = ;
::= |

Which are valid?
sum4 = (a1 + a2) * (3b % 4*b);
2sum = 2+3;
3p4rd2 = ((1a + a2) * (b3 % b4)) / (c7 – c8);
foo_bar = (a1 + a2 – b3 – b4);
(a1 / a2) = (c3 – c4);
6

Syntactic Analyses: Backus-Naur Form (BNF)
Given a situation you should be able to generate rules and prove validity
Given:
:= |
A number can be defined as a number and a digit or just a digit
:= 0|1|2|3|4|5|6|7|8|9
Our digits are terminals
Example: write some syntax rules for simple arithmetic expressions
+, – , *, /
:= |

7

Syntactic Analyses: Syntax Graph
A language can also be defined by a syntax graph
if (condition) statements ;

else statements ;

if (a < 0) return -a; if (a < 0) return -a; else return a; switch (expr) { case value: statements ; default: statements; } switch (ch) { case '+': x = a + b; break; case '-': x = a - b; break; case '*': x = a * b; break; case '': x = a / b; x = round(x); break; default: printf("invalid operator"); break; } 8 Does a while-loop’s syntax graph have a loop? Macro, Inlining, and Function Compare and contrast macros, inlinings, and funtions How are macros used? And what are macro side-effects? (Can you provide some examples?) In term of execution, which has better performance? And why? 9 Type Equivalence What is name equivalence? What is structural equivalence? Weak type checking vs. Strong type checking Implicit conversion (Coercion) Explicit conversion (Type Casting) 10 Data Understand your aspects of data Type: what values and operations are allowed Location: where data are stored in memory Address: an integer associated to a location Reference/pointer: a name associate with the variable that holds an address of a location Variable name: a name associated with a location Value: what stored in a memory location Scope: (lifetime) and visibility 11 Know your sizes 32 Bit based: 12 Type Typical Bit Width Typical Range char 1byte -128 to 127 or 0 to 255 unsigned char 1byte 0 to 255 signed char 1byte -128 to 127 int 4bytes -2147483648 to 2147483647 unsigned int 4bytes 0 to 4294967295 signed int 4bytes -2147483648 to 2147483647 short int 2bytes -32768 to 32767 unsigned short int 2bytes 0 to 65,535 signed short int 2bytes -32768 to 32767 long int 8bytes -2,147,483,648 to 2,147,483,647 signed long int 8bytes -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 unsigned long int 8bytes 0 to 18,446,744,073,709,551,615 float 4bytes +/- 3.4e +/- 38 (~7 digits) double 8bytes +/- 1.7e +/- 308 (~15 digits) long double 8bytes +/- 1.7e +/- 308 (~15 digits) / (~19 digits) wchar_t 2 or 4 bytes 1 wide character Array, string, and pointers In C, a string is an array of characters. char Name[] = “Mary”; // How many elements? char Name[6] = {‘C’, ‘h’, ‘a’, ‘r’, ‘l’, ‘e’, ‘s’} // Is this possible? What are some side effects? char *p = “Charles”; // Is this possible? // How can we print each of the individual char? * Assume “p” is a pointer and “Name” is a character array… p = Name; // Is this possible? Name = p; // Is this possible? 13 Pointers in C/C++ What are the two pointer-specific operations? & is a referencing function that returns the address value of the variable it precedes. Note, &x is r-value. * represents the name of the memory location of the address it precedes. Note, *y is a l-value. Example: Brickyard is the name of ASU Engineering Building “699 S. Mill Avenue” is the address of the building People can enter and leave the building and are value. Brickyard = Peter; means Peter enters the building; &Brickyard is the string: “699 S. Mill Avenue”; &Brickyard = Peter; Is it OK? What does the statement mean? *(“699 S. Mill Avenue”) = Peter; Is it OK? *(&Brickyard) = Peter; Is it OK? 14 Pointers Example #include
int main() {
int i1 = 0, i2 = 10, *p1, *p2, **p3;
p1 = &i1; // What is the value *p1?
p2 = &i2; // What is the value *p2?
p3 = &p2; // What is the value **p3?

**p3 = 20; // What variable is changed?
return 0;
}
15
&i1 = 5; Is it OK? What does the statement mean?
7000 = 5; Is it OK? What does the statement mean?
*(7000) = 5; Is it OK?
*(&i1 ) = 5; Is it OK?
What is &p1?
P3 = &p1; Is it OK?

Pointers Example
#include

int main() {

int ma[2][4], *p;
p = &ma[0][0];

*p = 5; // What is the value of ma?
*(p + 2) = 10; // What is the value of ma?
*(p + 5) = 20; // What is the value of ma?

return 0;
}

16
5
10
20
20

Dynamic Allocation
Make sure you know dynamic allocation
malloc
int* myArray = (int*)malloc(COUNT * sizeof(int));
new
int* myArray = new int[COUNT];
If you dynamically allocate you should release the memory
malloc -> free
new -> delete/delete[]
17

Multidimensional Allocation
Remember when you build a multi dimensional array you need a pointer level for each dimension and you are building arrays of arrays.
int** my2D = new int*[Y_DIM];
for(int i = 0; i < Y_DIM; i++) my2D[i] = new int[X_DIM]; 18 Constants in C/C++ What are constants? Can the value of a constant be changed? If so, how? 19 Parameters Know your parameter passing differences Reference – passes the memory Pointer – passes a pointer to the memory Value – passes a copy 20 Parameters Handy-dandy Guide: Pass by value when a function does not want to modify the parameter and the value is easy to copy (simple data types and certain things like strings) Pass by constant pointer when the value is expensive to copy the function DOES NOT want to modify the value pointed to NULL is valid and expected and handled Pass by pointer when the value is expensive to copy the function WANTS to modify the value pointed to NULL is valid and expected and handled Pass by constant reference when the value is expensive to copy the function DOES NOT want to modify the value NULL is not valid Value might not be addressed Pass by reference when the value is expensive to copy the function DOES want to modify the value NULL is not valid Structures and Unions What is a structure? struct contact { // a node to hold personal details char name[30]; int phone; char email[30]; } x; Is padding required? Can the padding be removed? 22 Structs Make sure you understand how to get the size of the struct and when padding should occur integers have to address on multiples of 4 doubles on multiples of 8 Struct aligns to its largest DATA TYPE which can cause additional padding 23 Parameter Passing What are different type of parameter passing mechanism? Call-by-value Call-by-reference Call-by-address What are the differences between each parameter passing mechanism? (Advantages and Disadvantages) 24 Linked List Example (using Pointer) #include
#include
#include // used by malloc

struct contact { // define a node holding a person’s details
char name[30];
int phone;
char email[30];
struct contact *next; // pointer to contact structure
} *head = NULL; //head is a global pointer to the first entry

void branching(char c); // function forward declaration
int insertion();
struct contact *search();
void delete();
25
Does the contact struct require padding? How many bytes?
Can we eliminate them?

Linked List Example (Cont’d)
int insertion() { // insert a new entry
struct contact *p;
p = (struct contact *) malloc(sizeof(struct contact));
if (p == 0) {
printf(“out of memory\n”); return -1;
}
printf(“Enter name, phone, email: \n”);
scanf(“%s”, p->name);
scanf(“%d”, &p->phone);
scanf(“%s”, p->email);
p->next = head; // Where is the new node inserted?
head = p;
return 0;
}

26

Linked List Example (Cont’d)
How can we modify the insertion code so that the new node is inserted upon the sorted?
Joe
1122334

next
John
1122556

head
Tom
1122667

p
 temp

 temp->next = p;
Zac
1122889

0

 p->next = temp->next;

27

Linked List Example (Cont’d)
void insertion() { // insert a new entry
struct contact *p, *temp;
p = (struct contact *) malloc(sizeof(struct contact));
if (p == 0) { printf(“out of memory\n”); return; }
printf(“Enter name, phone, email: \n”);
scanf(“%s”, p->name); // p->name is array
scanf(“%d”, &p->phone);
scanf(“%s”, p->email);
temp = head;
if ((head == 0)||(stricmp(p->name, temp->name) <=0)) { p->next = head;
head = p;
}
// continued next page

28

Linked List Example (Cont’d)
else { while (temp->next != 0) {
if (stricmp(p->name, temp->next->name) <=0) { p->next = temp->next;
temp->next = p;
return;
} else
temp = temp->next;
}
p->next = 0;
temp->next = p;
}
}

29
Joe
1122334

next
John
1122556

head
Tom
1122667

p
 temp

 temp->next = p;
Zac
1122889

0

 p->next = temp->next;

Recursion
What are the four-steps abstract approach for solving recursive problems?

Formulate the size-n problem.
Find the stopping condition and the corresponding return value.
Formulate the size-m problem and find m. In many cases, m = n – 1;
Construct the solution of size-n problem from size-m problem.

30

Recursion
What does the tail-recursive program resemble?
while-loop

1
2
n
condition
Jump to

tail-recursion
part 1

1
2
n
recursive call

condition
loop-body
31

Recursion
Fibonacci numbers are defined by

Can you write a recursive function for it?

32

Merge Short (pseudo code textbook Section 2.8.5)
mergesort (A, L,R) {
if R > L then
{ M = (R+L)//2; // integer division
mergesort (A, L, M);
mergesort (A, M+1,R);
merge(A, L, M, R); }
else Return A
}
merge (A, L, M, R) {
for i = M down to L do B[i] = A[i];
for j = M+1 to R do B[R+M+1-j] = A[j];
i = L; j = R;
for k=L to R do {
if B[i] < B[j] then { A[k]=B[i]; i = i+1; } else { A[k]=B[j]; j = j-1; } } 33 L R M R M+1 L M Identify the code for defining : size-n problem stopping condition and return value size-m problems the size-n solution from the size-m solutions ï î ï í ì ³ - + - = = = 2 ) 2 ( ) 1 ( 1 1 0 0 ) ( n n fib n fib n n n fib /docProps/thumbnail.jpeg