Catalog description: Prereq.: CS 152. Introduction to programming for students with substantial computer science background. [c]
Prerequisites: CS 152.
General description and objectives: The course outlines the basic language features of C. Some complicated and language specific elements are omitted in order to show the direct correspondence of C to the other general-purpose programming languages as Pascal and Java. Upon successful completion of this course the students will able to write significant application programs in C, using advanced programming techniques as structures, pointers and dynamic data.
Textbook: B. Kernighan and D. Ritchie, The C Programming Language, 2nd ed., Prentice Hall, 1988.
Grading:
50% of the total grade depends on test grades and 50% depends on grades
of exercises and projects. However, if the projects/exercises grade is
grater than the test grade by more than 20%, then the former will
be made equal to the test grade + 20%. The letter grades will be calculated
according to the following table:
| A | A- | B+ | B | B- | C+ | C | C- | D+ | D | D- | F |
| 95-100 | 90-94 | 87-89 | 84-86 | 80-83 | 77-79 | 74-76 | 70-73 | 67-69 | 64-66 | 60-63 | 0-59 |
Schedule of classes and assignments
Example: Print Fahrenheit-to-Celsius table for fahr = 0, 20, ...,300 (Kernighan & Ritchie, 1988, page 9).
Pascal:
program fahr_to_celsius;
var
fahr, celsius, upperLimit: integer;
begin
upperLimit := 300;
fahr := 0;
while fahr <= upperLimit do begin
celsius := 5 * (fahr
- 32) / 9;
writeln(fahr," ",celsius);
fahr := fahr + 20
end
end.
Java:
class fahr_to_celsius {
public static void main (String [] args) {
int fahr, celsius, upperLimit;
upperLimit = 300;
fahr = 0;
while (fahr <= upperLimit) {
celsius = 5 * (fahr
- 32) / 9;
System.out.println (fahr
+ "\t" + celsius);
fahr = fahr + 20;
}
}
}
C:
#include <stdio.h>
void main () {
int fahr, celsius, upperLimit;
upperLimit = 300;
fahr = 0;
while (fahr <= upperLimit) {
celsius = 5 * (fahr
- 32) / 9; /* means DIV since int */
printf ("%d\t%d\n",
fahr, celsius); /* prints integers */
fahr = fahr + 20;
}
}
More complex language features (structures, pointers and dynamic data) – more difference
Example: representing a structure (record)
book
| author | Kernighan and Ritchie |
| title | The C Programming Language |
| year | 1988 |
Pascal:
type
book = record
author: string[40];
title: string[4];
year: integer;
end;
var
b1: book;
…
b1.author := "Kernighan and Ritchie";
b1.title := "The C Programming Language";
b1.year := 1988;
…
Java:
public class book {
public string author;
public string title;
public int year;
}
…
book b1;
b1 = new book;
b1.author := “Kernighan and Ritchie”;
b1.title := “The C Programming Language”;
b1.year := 1988;
…
C:
struct book {
char author [40];
char title[40];
int year;
}
struct book b1;
…
b1.author = “Kernighan and Ritchie”;
b1.title = “The C Programming Language”;
b1.year = 1988;
…
Program 1:
void main() {
int a=1;
int i=0;
while (a*2>a) {
a=a*2;
i++;
printf("%d\t2^%d\n",a,i);
}
}
Program 1 output:
2 2^1
4 2^2
…
536870912 2^29
1073741824 2^30
Program 2:
void main() {
float a=1;
while (a*2>a) /* or (a/2<a)*/ {
a=a*2; /* or a=a/2; */
printf("%E\n",a);
}
}
Program 2 output (a=a*2):
2.000000E+00
…
1.701412E+38
+Infinity
Program 2 output (a=a/2):
5.000000E-01
…
1.401298E-45
0.000000E+00
Prove experimentally that if the sum of the digits of a number is 9 then the digit is multiple of 9 (what is about the reverse).
int sumd(int n) {
int sum = 0;
while (n>0) {
sum = sum + n%10;
n = n/10;
}
return sum;
}
void main() {
int i;
for (i=1;i<10000;i++)
if (sumd(i)==9 && i%9!=0)
printf("Wrong gues");
}
Bitwise operations: set operations (set elements in [1,32]).
int set(int n) { return 1 << n-1; } /* {n} */
int setunion(int a, int b) { return a | b; } /* a ?
b */
int inset(int a, int s) { return s & 1 << a-1; } /* a
? s */
void printset(int s) {
int i;
printf("{");
for (i=1;i<=32;i++) if (inset(i,s)) printf("%d
",i);
printf("}\n");
}
void main() {
int a=100;
int s=0;
while (a>0) {
scanf("%d",&a);
s = setunion(s,set(a));/* s = s ? {n}
*/
printset(s);
}
}
Program output:
5
{5 }
2
{2 5 }
9
{2 5 9 }
31
{2 5 9 31 }
5
{2 5 9 31 }
1
{1 2 5 9 31 }
/* A naive version */
void main() {
int a,b,i,d;
printf("Enter two integers: ");
scanf("%d%d",&a,&b);
if (a<b)
d=a;
else
d=b;
/* The following lines perform equivalently - choose one */
/* for (i=d; i>0; i--) {if (a%i==0 && b%i==0) break;} d=i;
*/
/* for (i=d; a%i>0 || b%i>0 ; i--) ; d=i;
*/
/* for ( ; a%d>0 || b%d>0 ; d--);
*/
for ( ; ; ) {if (a%d==0 && b%d==0) break;
else d--;}
/* while (a%d>0 || b%d>0) d--;
*/
printf("The greatest common divisor of %d and %d is
%d\n",a,b,d);
}
/* Euclid's algorithm */
void main() {
int a,b,t;
scanf("%d%d",&a,&b);
while (b>0) {
t=a%b;
a=b;
b=t;
}
printf("%d\n",a);
Do-while loops :
void main() {
int a,i=0;
float s=0;
do {
scanf("%d",&a);
s=s+a;
i++;
}
while (a>0);
/* Equivalent while loop
a=100;
while (a>0) {
scanf("%d",&a);
s=s+a;
i++;
}
*/
printf("The mean is %f\n",s/(i-1));
}
float rand() {
static int seed; /* seed must be available for
the next execution */
int a=27121, b=12345, c=65535;
seed=(a*seed+b)%c;
return (float)seed/c;
}
Example of using random numbers: Calculating the area of a circle by the Monte Carlo method.
/* Calculates the area of a circle with radius 1 and center (0,0)
*/
main() {
int i,n,inside;
float x,y;
/* Coordinates of a random point */
printf("Enter the number of random points: ");
scanf("%d",&n); /* Read how many points
to generate */
inside=0;
for (i=1;i<=n;i++) {
x=rand();
/* Generate a random point */
y=rand();
if (x*x+y*y<=1) /* Check if it is inside
the circle */
inside++;
}
printf("%f\n",4*(float)inside/n); /* Print the circle area
*/
}
1. Mathematical recursion
0!=1
N!=N*(N-1)!
int fact(int n){
if (n==0)
return 1;
else
return n*fact(n-1);
}
2. Combinatorics: Calculation of binomial coefficients (overflow)
- approximation of N!.
(Example: 52!/(13!*(52-13)!) = 639437890037)
float stirling(int n) {
float pi=acos(-1);
return sqrt(2*pi*n)*pow(n/exp(1),n);
}
n fact(n)
stirling(n)
-----------------------------------
1
1
1
2
2
2
3
6
6
4
24
24
5 120
118
6 720
710
7 5040
4980
8 40320
39902
9 362880
359537
10 3628800
3598696
11 39916800
39615626
12 479001600
475687493
13 1932053504
6187239561
14 1278945280
86661002946
15 2004310016 1300430740293
3. Lexicographic order
/* if s>t then gt(s,t)=1 else gt(s,t)=0 */
int gt(char s[], char t[]) {
int i;
for (i=0;s[i]==t[i];i++)
if (s[i]=='\0')
return 0;
return s[i]>t[i];
}
/* recursive version of gt; call gt(0,s,t) */
int gtr(int i, char s[], char t[]) {
if (s[i]=='\0' || t[i]=='\0' || s[i]!=t[i]) /* Base
condition */
return s[i]>t[i];
else
return gtr(i+1,s,t);
/* Recursive call */
}
1. Arrays:
int a[MAX];
a[0]=10;
a[1]=22;
swap_ij(a,1,2);
a[0] a[1] a[2] a[MAX-1]
| 10 | 22 | 25 | ... | ... | ... | ... | ... |
int swap_ij(int a[], int i, int j) {
int t;
t=a[i];
a[i]=a[j];
a[j]=t;
}
2. Pointers
int *p;
p=&a[0]; /* p=a; */
*p=10; /* a[0]=10; */
*(p+1)=22; /* a[1]=22; */
swap(&a[1],&a[2]); /* swap(p+1,p+2); */
*p *(p+1) *(p+2) *(p+MAX-1)
| 10 | 22 | 25 | ... | ... | ... | ... | ... |
int swap(int *a, int *b) {
int t;
t=*a;
*a=*b;
*b=t;
}
3. Bubble sort
int swaps(int a[], int n) {
int i, count=0;
for (i=0;i<n-1;i++)
if (a[i]>a[i+1]) {
/* The following 3 statements are equivalent
- choose one */
/* swap(&a[i],&a[i+1]); */
swap(a+i,a+i+1);
/* swap_ij(a,i,i+1);
*/
count++;
}
return count>0;
}
void bubble_sort(int a[], int n) {
while (swaps(a,n)) ;
}
void main() {
int i;
int a[MAX];
for (i=0;i<MAX;i++) /* read MAX numbers
*/
scanf("%d",&a[i]);
buble_sort(a,MAX); /* sort them
*/
printf("Sorted:\n");
for (i=0;i<MAX;i++) /* print them */
printf("%d\n",a[i]);
}
1. Multi-dimensional arrays:
char a[ROW][COL];
a[2][3]='x';
a[1]="second row"; /* fills the cells of the array, COL>=10 */
2. Arrays of pointers:
char*b[ROW];
b[1]="second row"; /* p[1] points to a string constant */
b[2]="third row";
b[2]=b[1]; /* b[2] points to "second row", no pointer to "third
row" */
3. Allocating storage for strings:
/* Returns a pointer to a sequence of bytes containing a string
*/
char *readline() {
char c[80];
char *p;
int i;
for (i=0; (c[i]=getchar()) != '\n' ;i++) ;
c[i]='\0';
p=(char *)malloc(i+1);
/* now p points to the first byte of a storage block of
i+1 bytes */
i=0;
while ((*(p+i)=c[i]) != '\0') i++;
return p;
}
4. Sorting strings:
void bubble_sort(char *a[], int n) {
while (swaps(a,n)) ;
}
int swaps(char *a[], int n) {
int i, count=0;
for (i=0;i<n-1;i++)
if (gt(a[i],a[i+1])) {
swap(a[i],a[i+1]);
count++;
}
return count>0;
}
void main() {
char *lines[25];
int n,i;
printf("How many lines? ");
scanf("%d\n",&n);
for(i=0;i<n;i++)
lines[i]=readline();
bubble_sort(lines,n);
for(i=0;i<n;i++)
printf("%s\n",lines[i]);
}
struct point {
int x;
int y;
};
struct triangle {
struct point a;
struct point b;
struct point c;
};
struct line { /* if (vert != 0) x=c; else y=a*x+b */
int vert;
float a;
float b;
int c;
};
Functions returning structures:
struct point makepoint(int xc, int yc) {
struct point p;
p.x=xc;
p.y=yc;
return p;
}
struct line makeline(struct point p1, struct point p2) {
float a,b;
struct line l;
if (p1.x != p2.x) {
a=(float)(p2.y-p1.y)/(p2.x-p1.x);
b=(float)p1.y-a*p1.x;
l.vert=0;
l.a=a;
l.b=b;
}
else { /* vertical line */
l.vert=1;
l.c=p1.x;
}
return l;
}
Example:
float on(struct point p, struct line l) { /* returns 0 if p is on
l */
if (l.vert==1)
return (float)p.x-l.c;
else
return (float)p.y-p.x*l.a-l.b;
}
void main() {
int x1,x2,x3,y1,y2,y3;
struct point p;
struct line l;
printf("Enter two points (x1 y1 x2 y2) to make a line:
");
scanf("%d %d %d %d", &x1,&y1,&x2,&y2);
printf("Enter a point (x y): ");
scanf("%d %d",&x3,&y3);
l=makeline(makepoint(x1,y1),makepoint(x2,y2));
p=makepoint(x3,y3);
if (on(p,l)==0)
printf("The point is on the line %f\n",
on(p,l));
else
printf("The point is not on the line %f\n",
on(p,l));
}
1. Linked lists
struct list {
int val;
/* a value */
struct list *next; /* a pointer to the next element
*/
};
struct list *p; /* a pointer to the first element of the list */
2. Allocating storage for list elements
struct list *newelement() { /* creates an instance of the list structure
*/
return (struct list *)malloc(sizeof(struct list));
}
3. Adding list elements
void push(int val) { /* add an element in the beginning of the list
*/
struct list *q;
q=newelement(); /* create new element
*/
(*q).val=val; /* assign the
value member */
(*q).next=p; /* set
the pointer to the next element */
p=q;
/* set the global list pointer */
}
void append(int val) { /* add an element at the end of the list
*/
struct list *q, *t;
q=newelement();
(*q).val=val; /* alternative notation: q->val=val
*/
(*q).next=NULL;
if (p==NULL) /* the list is empty */
p=q;
else {
/* the list is not empty */
t=p;
while ((*t).next!=NULL) /* move t at the
and of the list */
t=(*t).next;
(*t).next=q;
/* connect the new element */
}
}
4. Reading and printing lists
void main() {
struct list *q;
int x;
p=NULL; /* initialize the list - empty list
*/
do { /* read numbers and store
them in a list */
scanf("%d",&x);
if (x>0) append(x); /* push(x) stores the list
in reverse order */
} while (x>0); /* x<=0 end of input */
q=p;
while (q!=NULL) { /* print the list */
printf("%d\n",(*q).val);
q=(*q).next;
}
}
1. Creating new data type names - typedef
typedef struct list *listptr;
struct list {
int val;
listptr next;
};
listptr p; /* a pointer to the first element of the list */
2. Pull an element from the stack
int pull() {
int val;
if (p!=NULL) {
val=p->val; /* -> alternative notation for pointers
to structures */
p=p->next;
return val;
}
else
printf("stack empty\nl");
}
3. Print and empty the list
while (p!=NULL) printf("%d\n",pull());
4. Using a second list pointer for the queue
listptr e; /* a pointer to the last element of the list */
void append(int val) {
listptr q;
q=newelement();
q->val=val;
q->next=NULL;
if (p==NULL) {
p=q;
e=q;
}
else {
e->next=q;
e=q;
}
}
5. Lists as sets
listptr element(int val) {
listptr q;
q=p;
while (q!=NULL) {
if (q->val==val)
return q;
else
q=q->next;
}
return NULL;
}
void main() {
listptr q;
int x;
p=NULL;
do {
scanf("%d",&x);
if (x>0) append(x); /* or push(x) */
} while (x>0); /* x<=0 end of input */
/* assume the elements of the list are in the interval [1,100]
*/
for (x=0;x<=100;x++) /* print the set (ordered
list) */
if (element(x)!=NULL)
printf("%d\n",x);
}
1. Defining a binary tree structure
typedef struct node *nodeptr;
struct node {
int label;
nodeptr left;
nodeptr right;
};
2. Creating trees
nodeptr newnode(int label, nodeptr left, nodeptr right) {
nodeptr t;
t=(nodeptr)malloc(sizeof(struct node));
t->label=label;
t->left=left;
t->right=right;
return t;
}
nodeptr leaf(int label) {
nodeptr t;
t=newnode(label,NULL,NULL);
}
3. Arithmetic expression as trees
t=newnode('*',newnode('+',leaf(1),newnode('/',leaf(5),leaf(2))),
newnode('-',leaf(7),leaf(4)));
Infix notation: (1 + 5 / 2) * (7 - 4)
Prefix notation: * + 1 / 5 2 - 7 4
Horizontal tree:
*
+
1
/
5
2
-
7
4
4. Evaluating arithmetic expression
float eval(nodeptr t) {
if (t!=NULL) {
switch (t->label) {
case '*':
return eval(t->left)*eval(t->right);
case '+':
return eval(t->left)+eval(t->right);
case '-':
return eval(t->left)-eval(t->right);
case '/':
return eval(t->left)/eval(t->right);
default:
return t->label;
}
}
else
printf("illegal expression\n");
}
void main(){
nodeptr t;
t=newnode('*',newnode('+',leaf(1),
newnode('/',leaf(5),leaf(2))),
newnode('-',leaf(7),leaf(4)));
printf("\n");
printf("%f\n",eval(t));
}
1. Printing a prefix expression in infix format
void printexpr() {
int c;
c=getchar();
switch(c) {
case '*': case '/':
printexpr();
printf("%c",c);
printexpr();
break;
case '+': case '-':
printf("(");
printexpr();
printf("%c",c);
printexpr();
printf(")");
break;
default:
printf("%c",c);
break;
}
}
void main(){
nodeptr t;
printf("Enter an expression in prefix notation\n");
printexpr();
printf("\n");
}
Enter an expression in prefix notation
/+23-4+35
(2+3)/(4-(3+5))
2. Reading and evaluating a simple expression in infix format
float eval() {
char line[20];
char c;
float a,b,r;
scanf("%s",line);
sscanf(line,"%f%1s%f",&a,&c,&b);
switch(c) {
case '+':
r=a+b;
break;
case '*':
r=a*b;
break;
case '/':
r=a/b;
break;
case '-':
r=a-b;
break;
}
return r;
}
void main() {
float v;
v=eval();
printf("%f\n",v);
exit(0);
}
3. Reading and classifying words
char *word() {
char *s;
char c;
int i=0;
s=(char *)malloc(10);
while ((c=getchar())==' ') ;
s[0]=c;
while (c!=' ' && c!='\n') {
c=getchar();
s[++i]=c;
}
s[i]='\0';
return s;
}
void main() {
char *w;
int i;
float f;
printf("Enter a line: ");
for (; w=word(),(*w)!='\0'; )
if (sscanf(w,"%f",&f)==1)
printf("%s is a number\n",w);
else
printf("%s is a string\n",w);
}
Enter a line: 123 abcd 3.14
123 is a number
abcd is a string
3.14 is a number
1. Representation
typedef struct node *nodeptr;
struct node {
char label;
nodeptr son;
nodeptr brother;
};
nodeptr newt(char label, nodeptr son, nodeptr brother) {
nodeptr t;
int i;
t=(nodeptr)malloc(sizeof(struct node));
t->label=label;
t->son=son;
t->brother=brother;
return t;
}
2. Printing in standard (term) notation
void printterm(nodeptr t) {
nodeptr q;
if (t!=NULL) {
printf("%c",t->label);
if (t->son!=NULL) {
printf("(");
q=t->son;
while(q!=NULL) {
printterm(q);
if (q->brother!=NULL)
printf(",");
q=q->brother;
}
printf(")");
}
}
}
3. Printing horizontal trees
void blanks(int n) {
int i;
for (i=0;i<n;i++) printf(" ");
}
void printtree(nodeptr t, int n) {
nodeptr q;
if (t!=NULL) {
blanks(n);
printf("%c\n",t->label);
q=t->son;
while(q!=NULL) {
printtree(q,n+1);
q=q->brother;
}
}
}
void main() {
nodeptr t;
t=newt('p', // generate the
term: p(a(b),c(d,e,f))
newt('a',
newt('b',
NULL,
NULL),
newt('c',
newt('d',
NULL,
newt('e',
NULL,
newt('f',
NULL,
NULL))),
NULL)),
NULL);
printterm(t); // print
in standard form
printf("\n");
printtree(t,0); // print as a horizontal
tree
}
p(a(b),c(d,e,f))
p
a
b
c
d
e
f
How many words? 4Use a single-dimensional array of characters to store the words. Reserve a fixed number of characters to store each word (e.g. 8). Thus the content of the array for the above example will be the following:
John
Ann
James
Bill
Sorted:
Ann
Bill
James
John
Before sorting:
| J | o | h | n | A | n | n | J | a | m | e | s | B | i | l | l | ... |
After sorting:
| A | n | n | B | i | l | l | J | a | m | e | s | J | o | h | n | ... |
To input and to print the words use scanf and printf correspondingly, as shown below:
for (i=0;i<=24;i=i+8) /* Input of 4 words by 8 chars
maximum */
scanf("%s",&words[i]);
for (i=0;i<=24;i=i+8) /* Prints 4 words */
printf("%s\n",&words[i]);
Use the bubble sort method for sorting and the lexicographic order for word comparison.
Implement the linked list by using self-referential structures.
* + 1 / 5 2 - 7 4
the program should print the value of the expression (10.5) and then the following horizontal tree:
*
+
1
/
5
2
-
7
4
The expressions must be checked for correctness. For example, given the expression "*+1/52" the program should print a message that the second argument of "*" is missing. The program should also detect division by 0.
Use binary tree structures to represent the expressions and restrict the input to single digit numbers. Extra credit (5 pts): Allowing expressions with unrestricted integer numbers (with more than one digit).