THEME: STRUCTURES, POINTERS, AND
LINKED DATA STRUCTURES
• The following slides provide the C-code around which we will structure our discussion tomorrow. • Please note that this code by itself is incomplete. • Class attendance is necessary to understand the theme.
• Those who do not attend the class must read the Text book and come to consultations, if help is needed.

Structures and Lists
#include
#include struct Student { char *name ; int age;
};
// Note: char *name ="xxxxxxxxxxxxxx"; is
// not permitted in structures. Why? int main(void){ struct Student s; // allocates memory.
s.name = malloc(20*sizeof(char)); scanf("%s",s.name); s.age = 20; printf("1:%s %d\n",s.name, s.age); struct Student *ps; ps = &s;
// Dot has higher priority over & scanf("%s%d",(*ps).name,&(*ps).age); printf("2:%s %d\n", (*ps).name, (*ps).age); printf("3:%s %d\n",ps->name,ps->age+3);

struct Student *ps1;
// allocate memory by malloc() dynamically. ps1 = malloc(sizeof(struct Student)); ps1->name = malloc(20*sizeof(char)); scanf("%s%d",ps1->name,&(ps1->age)); printf("4:%s %d\n",ps1->name,ps1->age+3); printf("5:%s %d\n", (*ps1).name, (*ps1).age);
}

Student s

0028FF08

malloc
003C1110

name name age

age ps malloc
0028FF00

003C1188

ps1

malloc

#include
#include
struct S1 { int a1; char b1;
};
struct S2{ int a2; char b2; struct S1 *p2;
};
struct S3{ int a3; char b3; struct S1 *p3a; struct S2 *p3b;
};

Linked structures

// Self referencing structure. Also called: recursive structure. struct S4{ int a4; char b4; struct S4 *p4;
};
int main(){ struct S1 s1; struct S2 s2; struct S3 s3; struct S4 s4; s1.a1=2; s1.b1='A'; s2.a2=20; s2.b2='B'; s2.p2 = &s1; // Creates a list: s2 ---> s1 printf("First:%d %c %d %c\n",s1.a1,s1.b1,s2.a2,s2.b2); printf("Second:%d %c %d %c \n",
(*(s2.p2)).a1, (*(s2.p2)).b1, (s2.p2)->a1, (s2.p2)->b1); scanf("%d%d", &((*(s2.p2)).a1), &((s2.p2)->a1) ); printf("Third:%d %d\n",(*(s2.p2)).a1, (s2.p2)->a1 );
//------s3.a3=5; s3.b3='C'; s3.p3a=&s1; // creates a list: s3 ---> s1
(s3.p3a)->a1 = 8; (s3.p3a)->b1='D'; s3.p3b=&s2; (s3.p3b)->p2 = &s1;
// creates list: s3 ---> s2. s2 is already connected to s1.
// so we have: s3 --> s2 --> s1.
((s3.p3b)->p2)->a1=25;
printf("Fourth:%d is same as %d\n",
(*(*(s3.p3b)).p2).a1 , s1.a1 );
}

#include
#include
// Singly linked list. (Also called linear list.) struct S { int v; struct S *next;
};
int main(){
// Manually building a short list.
// Allocation for pointer variables. struct S *p0, *p1, *p2, *p3, *p4;
// Allocation for list nodes. p0 = (struct S *) malloc(sizeof(struct S)); p1 = (struct S *) malloc(sizeof(struct S)); p2 = (struct S *) malloc(sizeof(struct S)); p3 = (struct S *) malloc(sizeof(struct S)); p4 = (struct S *) malloc(sizeof(struct S));
//Create a list. p0->v=6; p0->next = p1; p1->v=8; p1->next=p2; p2->v=1; p2->next=p3; p3->v=8; p3->next= p4; p4->v=3; p4->next= NULL;

Linear Linked List

//Printing the list.
// This must be done at the beginning.
//Please forgive the bad style :-) struct S *tmp; for(tmp=p0; tmp != NULL; tmp=tmp->next) printf("%d ",tmp->v); printf("\n"); int len; // Bad style. for(tmp=p0,len=0;tmp != NULL; tmp=tmp->next,len++); printf("Length=%d\n",len);
//count occurrences int a,count; count=0; scanf("%d",&a); for(tmp=p0; tmp != NULL; tmp=tmp->next) if(tmp->v==a) count++; printf("count=%d\n",count); return 0;
}

sizeof-operator
#include
int main( void )
{
char c; short s; int i; long l; float f; double d; long double ld; int array[ 20 ]; int *ptr = array; printf( " sizeof c = %d\tsizeof(char) = %d"
"\n sizeof s = %d\tsizeof(short) = %d"
"\n sizeof i = %d\tsizeof(int) = %d"
"\n sizeof l = %d\tsizeof(long) = %d"
"\n sizeof f = %d\tsizeof(float) = %d"
"\n sizeof d = %d\tsizeof(double) = %d"
"\n sizeof ld = %d\tsizeof(long double) = %d"
"\n sizeof array = %d"
"\n sizeof ptr = %d\n", sizeof c, sizeof( char ), sizeof s, sizeof( short ), sizeof i, sizeof( int ), sizeof l, sizeof( long ), sizeof f, sizeof( float ), sizeof d, sizeof( double ), sizeof ld, sizeof( long double ), sizeof array, sizeof ptr ); return 0;
}

% a.out sizeof c = 1 sizeof(char) = 1 sizeof s = 2 sizeof(short) = 2 sizeof i = 4 sizeof(int) = 4 sizeof l = 4 sizeof(long) = 4 sizeof f = 4 sizeof(float) = 4 sizeof d = 8 sizeof(double) = 8 sizeof ld = 12 sizeof(long double) = 12 sizeof array = 80 sizeof ptr = 4
%
Note: byte = 8bits. 1 char = 8 bits; some compilers 16 bits;
Uses of this operator:
a) Idea about how much of space occupied.
b) Useful in dynamic memory allocation.
c) Advice: Do not hard code size info in your program as it is non standard. Always use sizeof operator.
-------------------------------- ---------------Whole may be greater than the sum: struct student{ char grade; /* char is 1 byte long */ int age; /* int is 4 bytes long */
};
printf("%zu", sizeof (struct student));
This may give us 8.

Simple List Operations struct Node { char ch; struct Node *next;
};
typedef struct Node ListNode; typedef ListNode *Ptr;

1 void create(Ptr *head) { // Passs by reference.
// Caller pointner may be modified. struct Node *p0, *p1, *p2, *p3, *p4,*p5; p0 = (struct Node *) malloc(sizeof(struct Node)); p1 = (struct Node *) malloc(sizeof(struct Node)); p2 = (struct Node *) malloc(sizeof(struct Node)); p3 = (struct Node *) malloc(sizeof(struct Node)); p4 = (struct Node *) malloc(sizeof(struct Node)); p5 = (struct Node *) malloc(sizeof(struct Node)); p0->ch='a'; p0->next = p1; p1->ch='b'; p1->next=p2; p2->ch='c'; p2->next=p3; p3->ch='d'; p3->next= p4; p4->ch='e'; p4->next= p5; p5->ch='f'; p5->next=NULL;
*head = p0;
}

// Call by value; caller pointer protected against changes. int printFirst(Ptr list){ if (list==NULL) {printf("Empty list.\n"); return 0;} printf("%c\n",list->ch); return 0;
}
char getSecond(Ptr list){ if (list == NULL ) {printf("Empty list.\n"); return 0;} if (list->next == NULL) { printf("Single element list.\n"); return 0; } return(list->next->ch); } char getlast(Ptr list){
Ptr previous; if(list==NULL) {printf("List is empty.\n"); return 0;} for (;list != NULL; list=list->next ) previous = list; return previous->ch;
}

int ordered(Ptr list){
Ptr current,previous; if(list==NULL || list->next==NULL) return 1; previous=list; current=list->next; for (; current!=NULL; previous=current,current=current->next) if(previous->ch > current->ch) return 0; return 1;
}

Simple List Operations (contd.) struct Node { char ch; struct Node *next;
};
typedef struct Node ListNode; typedef ListNode *Ptr;

1 int getAll(Ptr list, char a[]){ int i=0; for(;list!=NULL;list=list->next) a[i++]=list->ch; a[i]='\0'; return 0;
}

int countOccurrences(Ptr list, char c, Ptr ptr[]){ int i=0; for (;list!=NULL; list=list->next) if(list->ch==c)ptr[i++]=list; return i;
}

Ptr previous(Ptr list, char c){
Ptr prev=list, current=list; for(;current!=NULL;current=current->next){ if (current->ch==c) return prev; prev=current; } return NULL;
}

int main() {
Ptr list; int i, k; char a[100]; Ptr ptr[100]; create(&list); printFirst(list); printf("%c\n",getSecond(list)); printf("%c\n",getlast(list)); printf("%d\n",ordered(list)); getAll(list,a); printf("Length=%d chars=%s\n",strlen(a),a ); k=countOccurrences(list, 'b', ptr); printf("k=%d\n",k); for(i=0;ich); printf("\n");
Ptr tmp = previous(list,'e'); if (tmp!=NULL)printf("previous=%c\n",tmp->ch); else printf("previous=NULL\n"); return 0;
}

List modification
#include
#include
#define MAX 2 struct Node { char ch; struct Node *next;
};
typedef struct Node ListNode; typedef ListNode *Ptr; typedef struct Four{
Ptr p1,p2,p3,p4;
} *Ptr4;

Ptr checkString(Ptr list, char a[]){ for(;list!=NULL;list=list->next) if(checkString1(list,a)) return list; return NULL;
}
int checkString1(Ptr list,char a[] ){ int i; for(i=0;inext,i++) if(list->ch!=a[i]) return 0; return 1;
}

Ptr4 lastFour(Ptr list){
Ptr p1,p2,p3,p4; Ptr save1,save2,save3,save4;

if ( !list || !list->next || !list->next->next || !list->next->next->next)
{printf("List is too small.\n"); return NULL; } p1=list; p2=list->next; p3=list->next->next; p4=list->next->next->next; save1=p1;save2=p2;save3=p3;save4=p4; for(;p4!=NULL;p1=p1->next,p2=p2->next,p3=p3->next,p4=p4->next){ save1=p1;save2=p2;save3=p3;save4=p4; }
Ptr4 p5; p5=(Ptr4)malloc(sizeof(struct Four)); p5->p1=save1; p5->p2=save2; p5->p3=save3; p5->p4=save4; return p5;
}

List modification (contd.) int main(){ int deleteFirst(Ptr *list){ if(!*list) return 0;
Ptr save=*list; *list=(*list)->next; free(save); return 0;
}
int insertEnd(Ptr *list, char v){
Ptr save,tmp,save1; if(!*list) return 0; save1=*list; for(;*list;*list=(*list)->next)save=*list; tmp=malloc(sizeof(struct Node)); tmp->ch=v; tmp->next=NULL; save->next=tmp; *list=save1; return 0;
}

Ptr list,tmp; int j; char a[MAX]={'c','d'}; create(&list); tmp=checkString(list,a); if (tmp==NULL) return 0; for (j=0;jnext) putchar(tmp->ch); putchar('\n');
Ptr4 tmp1=NULL; create(&list); tmp1=lastFour(list); printf("%c %c %c %c\n",tmp1->p1->ch,tmp1->p2->ch,tmp1->p3->ch,tmp1->p4->ch); print(list); deleteFirst(&list); print(list); insertEnd(&list,'g'); print(list); InsertEnd(&list,'h'); print(list); return 0;
}

List of Lists

struct Node { char ch; struct Node *next;
};
typedef struct Node ListNode; typedef ListNode *Ptr; struct Node3{ char *name; // name of the list.
Ptr list; struct Node3 *next;
};
typedef struct Node3 *Ptr3;

// Passs by reference.
//Caller poitner may be modified. void create(Ptr *head) { struct Node *p0, *p1, *p2, *p3, *p4,*p5; p0 = (struct Node *) malloc(sizeof(struct Node)); etc. p0->ch='a'; p0->next = p1; etc. *head = p0;
}

int create3(Ptr3 *list){
Ptr3 p0,p1,p2,p3; p0=malloc(sizeof(struct Node3)); p1=malloc(sizeof(struct Node3)); p2=malloc(sizeof(struct Node3)); p3=malloc(sizeof(struct Node3)); p0->name=malloc(MAX*sizeof(char)); strcpy(p0->name,"AAAAA");create(&(p0->list)); p1->name=malloc(MAX*sizeof(char)); strcpy(p1->name,"BBBBB");create(&(p1->list)); p2->name=malloc(MAX*sizeof(char)); strcpy(p2->name,"CCCCC");create(&(p2->list)); p3->name=malloc(MAX*sizeof(char)); strcpy(p3->name,"DDDDD");create(&(p3->list)); p0->next=p1; p1->next=p2; p2->next=p3; p3->next=NULL;
*list = p0; return 0;
}
int print3(Ptr3 list){ // print for list of lists. if(!list) { printf("List is empty.\n"); return 0; } for(;list;list=list->next) { printf("Name:%s ",list->name); printf("Content:"); print(list->list );printf("\n");
}
return 0;
}
// print for list of chars. int print(Ptr list){ if(!list){printf("print():Empty list.\n"); return 0;} for(;list;list=list->next) putc(list->ch,stdout); putc('\n', stdout); return 0;
}

int main(){
Ptr3 list; create3(&list); print3(list); return 0;
}

Doubly Linked List struct Node2 { char ch; struct Node2 *prev; struct Node2 *next;
};
typedef struct Node2 ListNode2; typedef ListNode2 *Ptr2;

int print(DLPtr list){
Ptr2 p = list->first; if(!p) {printf("DL list is empty.\n"); return 0;} for(;p;p=p->next)printf("%c",p->ch); printf("\n"); return 0;
}

typedef struct DoubleList{ int length;
Ptr2 first;
Ptr2 last;
} *DLPtr;

int main(){
DLPtr list; list=malloc(sizeof(struct DoubleList)); list->length=0; list->first=NULL; list->last=NULL; create(&list); print(list); return 0;
}

int create(DLPtr *list){
Ptr2 p1,p2,p3,p4; p1=malloc(sizeof(struct Node2)); p2=malloc(sizeof(struct Node2)); p3=malloc(sizeof(struct Node2)); p4=malloc(sizeof(struct Node2)); p1->ch='a'; p1->prev=NULL; p1->next=p2; p2->ch='b'; p2->prev=p1; p2->next=p3; p3->ch='c'; p3->prev=p2; p3->next=p4; p4->ch='d'; p4->prev=p3; p4->next=NULL;
(*list)->first=p1; (*list)->last=p4; (*list)->length=4; return 0;
}