C Programming/Exercise solutions

Beginning Exercises - Solutions

Variables

Naming

Data Types

Assignment

doublepi;
pi=3.14;

constfloatpi=3.14;
#define pi 3.14

inta=67;
doubleb;
b=a;

doublea=89;
intb;
b=(int)a;

Referencing

Simple I/O

String manipulation

#include<stdio.h>
#include<string.h>
intmain(void)
{
chars[81];// A string of upto 80 chars + '0円'
inti;

puts("Please write a string: ");
fgets(s,81,stdin);
puts("Your sentence in reverse: ");
for(i=strlen(s)-1;i>=0;i--)
{
if(s[i]=='\n')
continue;// don't write newline
else
putchar(s[i]);
}
putchar('\n');
return0;
}

#define __STDC_WANT_LIB_EXT1__ 1 // Active C11 extended functions (this case is gets_s)
#include<stdio.h>
intslen(constchar*);// I don't want to include whole string lib just for get size
intmain(void){
chars[500];
printf("%s","Enter a sentence: ");
if(!gets_s(s,500)){
puts("Error!");
getchar();
return0;
}
for(inti=0;i<slen(s);i++)
if(s[i]!=32)
putchar(s[i]);
else
putchar(10);
putchar(10);
getchar();
return0;
}
intslen(constchar*s){
inti;
for(i=0;s[i]!=0;i++);
returni;
}

Loops

#include<stdio.h>
intmain(void){
intn;
scanf("%d",&n);
for(inti=0;i<n;i++){
for(intj=0;j<=i;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return0;
}

#include<stdio.h>
intmain(void){
intn;
scanf("%d",&n);
for(inti=0;i<n;i++){
for(intj=0;j<=i;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return0;
}

#include<stdio.h>
// This is the fastest way
intmain(void){
intn;
scanf("%d",&n);
for(inti=0;i<n;i++){
for(intj=0;j<=i;j++)
putchar(42);
putchar(10);
}
for(inti=n-1;i>0;i--){
for(intj=0;j<i;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return0;
}

voidsideways(intn)
{
inti=0,j=0;
for(i=1;i<2*n;i++){
for(j=1;j<=(n-(abs(n-i)));j++){
printf("*");
}
printf("\n");
}
}

voidright_side_up(intn)
{
intx,y;
for(y=1;y<=n;y++)
{
for(x=0;x<n-y;x++)
putchar(' ');
for(x=(n-y);x<(n-y)+(2*y-1);x++)
putchar('*');
putchar('\n');
}
}

#include<stdio.h>
intmain(void){
intn;
scanf("%d",&n);
for(inti=0;i<n;i++){
for(intj=0;j<n-i-1;j++)
putchar(32);
for(intj=0;j<i*2+1;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return0;
}

Math

// to compile: gcc -Wall prime.c -lm -o prime
#include<math.h> // for the square root function sqrt()	
#include<stdio.h>
intis_prime(intn);
intmain()
{
printf("Write an integer: ");
intvar;
scanf("%d",&var);
if(is_prime(var)==1){
printf("A prime\n");
}else{
printf("Not a prime\n");
}
return1;
}
intis_prime(intn)
{
intx;
intsq=sqrt(n)+1;

// Checking the trivial cases first
if(n<2)
return0;
if(n==2||n==3)
return1;

// Checking if n is divisible by 2 or odd numbers between 3 and the
// square root of n.
if(n%2==0)
return0;
for(x=3;x<=sq;x+=2)
{
if(n%x==0)
return0;
}

return1;
}

#include<stdio.h>
intisPrime(constunsignedlonglongint);
intmain(void){
unsignedlonglongn;
scanf("%llu",&n);
printf("%d\n",isPrime(n));
while((n=getchar())!=10);
getchar();
return0;
}
intisPrime(constunsignedlonglongintx){
if(x<4)
returnx>1;
if(x%2==0||x%3==0)
return0;
for(unsignedlonginti=5;i*i<=x;i+=6)
if(x%i==0||x%(i+2)==0)
return0;
return1;
}

Recursion

Merge sort

// to compile: gcc -Wall rmergesort.c -lm -o rmergesort
/*
 ============================================================================
 Name  : rmergesort.c
 Author  : Anon
 Version  : 0.1
 Copyright  : (C)2013 under CC-By-SA 3.0 License
 Description : Recursive Merge Sort, Ansi-style
 ============================================================================
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//const int MAX = 200;
constintMAX=20000000;
int*b;
intprintOff=0;
// this debugging print out of the array helps to show
// what is going on.
voidprintArray(char*label,int*a,intsz){
inth=sz/2;
inti;
if(printOff)return;
printf("\n%s:\n",label);
for(i=0;i<h;++i){
printf("%d%c",a[i],
// add in a newline every 20 numbers
((i!=0&&i%20==0)?'\n':' '));
}
printf(" | ");
for(;i<sz;++i){
printf("%d%c",a[i],
((i!=0&&i%20==0)?'\n':' '));
}
putchar('\n');
}
voidmergesort(int*a,intm){
printArray("BEFORE",a,m);
if(m>2){
// if greater than 2 elements, then recursive
mergesort(a,m/2);
mergesort(a+m/2,m-m/2);
}elseif(m==2&&a[0]>a[1]){
// if exactly 2 elements and need swapping, swap
intt=a[1];
a[1]=a[0];
a[0]=t;
gotoend;
}
// 1 or greater than 2 elements which have been recursively sorted
// divide the array into a left and right array
// merge into the array b with index l.
intn=m/2;
into=m-n;
inti=0,j=n;
intl=0;
// i is left, j is right ;
// l should equal m the size of the array
while(i<n){
if(j>=m){
// the right array has finished, so copy the remaining left array
for(;i<n;++i){
b[l++]=a[i];
}
// the merge operation is to copy the smaller current element and
// increment the index of the parent sub-array.
}elseif(a[i]<a[j]){
b[l++]=a[i++];
}else{
b[l++]=a[j++];
}
}
while(j<m){
// copy the remaining right array , if any
b[l++]=a[j++];
}
memcpy(a,b,sizeof(int)*l);
end:
printArray("AFTER",a,m);
return;
}
voidrand_init(int*a,intn){
inti;
for(i=0;i<n;++i){
a[i]=rand()%MAX;
}
}
intmain(void){
puts("!!!Hello World!!!");/* prints !!!Hello World!!! */
//	int N = 20;
// int N = 1000;
// int N = 1000000;
intN=100000000;// still can't make a stack overflow on ubuntu,4GB, phenom
printOff=1;
int*a;
b=calloc(N,sizeof(int));
a=calloc(N,sizeof(int));
rand_init(a,N);
mergesort(a,N);
printOff=0;
printArray("LAST",a,N);
free(a);
free(b);
returnEXIT_SUCCESS;
}
/* Having failed to translate my concept of non-recursive merge sort,
 * I tackled the easier case of recursive merge sort.
 * The next task is to translate the recursive version to a non-recursive
 * version. This could be done by replacing calls to mergesort, with
 * pushes onto a stack of
 * tuples of ( <array start address>, <number of elements to process> )
 */
/* The central idea of merging, is that two sorted lists can be
 * merged into one sorted list, by comparing the top of each list and
 * moving the lowest valued element onto the end of the new list.
 * The other list which has the higher valued element keeps its top
 * element unchanged. When a list is exhausted, copy the remaining other list
 * onto the end of the new list.
 */
/* The recursive part, is to defer any work in sorting an unsorted list,
 * by dividing it into two lists until there is only 1 or two elements,
 * and if there are two elements, sort them directly by swapping if
 * the first element is larger than the second element.
 *
 * After returning from a recursive call, merge the lists, which will
 * begin with one or two element sorted lists. The result is a sorted list
 * which will be returned to the parent of the recursive call, and can
 * be used for merging.
 */
/* The following is an imaginary discussion about what a programmer
 * might be thinking about when programming:
 *
 * Visualising recursion in terms of a Z80 assembly language, which
 * is similar to most assembly languages, there is a data stack (DS) and
 * a call stack (CS) pointer, and each recursive call to mergesort
 * pushes the return address , which is the program address of the instruction
 * after the call , onto the stack pointed to by CS and CS is incremented,
 * and the address of the array start and integer which is the subarray length
 * onto the data stack pointed to by DS, which will be incremented twice.
 *
 * If the number of recursive , active calls exceed the allowable space for either the call stack
 * or the data stack, then the program will crash , or a process space protection
 * violation interrupt signal will be sent by the CPU, and the interrupt vector
 * for that signal will jump the processor's current instruction pointer to the
 * interrupt handling routine.
 */

Binary heaps

Quick sort

/*
 * qsortsimp.h
 *
 * Created on: 17/03/2013
 * Author: anonymous
 */
#ifndef QSORTSIMP_H_
#define QSORTSIMP_H_
#include<stdlib.h>
voidqsortsimp(void*a,size_telem_sz,intlen,int(*cmp)(void*,void*));
voidshutdown_qsortsimp();
#endif /* QSORTSIMP_H_ */
//----------------------------------------------------------------------------
/* qsortsimp.c
 * author : anonymous
 */
#include"qsortsimp.h"
#include<stdlib.h>
#include<string.h>
staticvoid*swap_buf=0;
staticintbufsz=0;
voidswap(void*a,inti,intj,size_telem_sz){
if(i==j)return;
if(bufsz==0||bufsz<elem_sz){
swap_buf=realloc(swap_buf,elem_sz);
bufsz=elem_sz;
}
memcpy(swap_buf,a+i*elem_sz,elem_sz);
memcpy(a+i*elem_sz,a+j*elem_sz,elem_sz);
memcpy(a+j*elem_sz,swap_buf,elem_sz);
}
voidshutdown_qsortsimp(){
if(swap_buf){
free(swap_buf);
}
}
intpartition(void*a,size_telem_sz,intlen,int(*cmp)(void*,void*)){
inti=-1;
intj=len-1;
void*v=a+j*elem_sz;
for(;;){
while((*cmp)(a+++i*elem_sz,v)<0);
while((*cmp)(v,a+--j*elem_sz)<0)if(j==0)break;
if(i>=j)break;
swap(a,i,j,elem_sz);
}
swap(a,i,len-1,elem_sz);
returni;
}
voidqsortsimp(void*a,size_telem_sz,intlen,int(*cmp)(void*,void*)){
if(len>2){
intp=partition(a,elem_sz,len,cmp);
qsortsimp(a,elem_sz,p,cmp);
qsortsimp(a+(p+1)*elem_sz,elem_sz,len-p-1,cmp);
}
}
//------------------------------------------------------------------------------
/*
Name  : words_quicksort.c
 Author  : anonymous
 Version  :
 Copyright  : 
 Description : quick sort the words in moby dick in C, Ansi-style
 ============================================================================
 */
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include"qsortsimp.h"
voidprintArray(constchar*a[],intn){
inti;
for(i=0;i<n;++i){
if(i!=0&&i%5==0){
printf("\n");
}
if(i%1000000==0){
fprintf(stderr,"printed %d words\n",i);
}
printf("%s ",a[i]);
}
printf("\n");
}
constintMAXCHARS=250;
char**wordlist=0;
intnwords=0;
intremaining_block;
constsize_tNWORDS_PER_BLOCK=1000;
//const char* spaces=" \t\n\r";
//inline isspace(const char ch) {
//	int i=0;
//	while(spaces[i]!='0円') {
//		if(spaces[i++] == ch)
//			return 1;
//	}
//	return 0;
//}
voidfreeMem(){
inti=nwords;
while(i>0){
free(wordlist[--i]);
}
free(wordlist);
}
staticchar*fname="~/Downloads/books/pg2701-moby-dick.txt";
voidgetWords(){
charbuffer[MAXCHARS];
FILE*f=fopen(fname,"r");
intstate=0;
intch;
inti;
while((ch=fgetc(f))!=EOF){
if(isalnum(ch)&&state==0){
state=1;
i=0;
buffer[i++]=ch;
}elseif(isalnum(ch)&&i<MAXCHARS-1){
buffer[i++]=ch;
}elseif(state==1){
state=0;
buffer[i++]='0円';
char*dynbuf=malloc(i);
intj;
for(j=0;j<i;++j){
dynbuf[j]=buffer[j];
}
i=0;
if(wordlist==0){
wordlist=calloc(NWORDS_PER_BLOCK,sizeof(char*));
remaining_block=NWORDS_PER_BLOCK;
}elseif(remaining_block==0){
wordlist=realloc(wordlist,(NWORDS_PER_BLOCK+nwords)*sizeof(char*));
remaining_block=NWORDS_PER_BLOCK;
fprintf(stderr,"allocated block %d , nwords = %d\n",remaining_block,nwords);
}
wordlist[nwords++]=dynbuf;
--remaining_block;
}
}
fclose(f);
}
voidtestPrintArray(){
inti;
for(i=0;i<nwords;++i){
printf("%s | ",wordlist[i]);
}
putchar('\n');
printf("stored %d words. \n",nwords);
}
intcmp_str_1(void*a,void*b){
intr=strcasecmp(*((char**)a),*((char**)b));
returnr;
}
intmain(intargc,char*argv[]){
if(argc>1){
fname=argv[1];
}
getWords();
testPrintArray();
qsortsimp(wordlist,sizeof(char*),nwords,&cmp_str_1);
testPrintArray();
shutdown_qsortsimp();
freeMem();
puts("!!!Hello World!!!");/* prints !!!Hello World!!! */
returnEXIT_SUCCESS;
}