Today's topics

C Programming Basic week 3

For Data Structure and Algorithms

Self referential structure in C Data structure single linked LIST

Implementation of single linked LIST Algorithm for scanning data Algorithm for inserting, deleting

Lecturers : Cao Tuan Dung Le Duc Trung Dept of Software Engineering Hanoi University of Technology

Data structure double linked LIST

Implementation of double linked LIST Algorithm for scanning data Algorithm for inserting, deleting
2

Self-Referential Structures
One or more of its components is a pointer to itself.
struct list { char data; struct list *link; }; a b list item1, item2, item3; item1.data=a; item2.data=b; item3.data=c; item1.link=item2.link=item3.link=NULL;

Implemetation of List in C
LIST means data structure that keeps the information of the location of next element generally. The elements of Single linked LIST have only next location. In C, the pointer is used for the location of the next element. Array: We can access any data immediately. Linked List: We can change the number of data in it.

root (or head)

NULL 4

Declaration of a Linked List

typedef ... elementtype; typedef struct node{ elementtype element; node* next; }; node* root; node* cur;

Memory allocation for an element

We need to allocate a memory bloc for each node (element) via a pointer.
struct node * new; new = (struct node*) malloc(sizeof(structnode)); new->element = new->next = null;

typedef ... elementtype; struct node{ elementtype element; struct node* next; }; struct node* root; struct node* cur;
5

new->addr means (*new).addr. pointer variable for record structure -> member name
6

Question 3-1
We are now designing address list for mobile phones. You must declare a record structure that can keep a name, a phone number, and a e-mail address at least. And you must make the program which can deals with any number of the data
7

Exercise
Create a singly linked list to store a list of phone address. Write a function to insert to a list a new element just after the current element and use it to add node to the list Write a function for traversing the list to print out all information stored. Write a function for the removal of a node in the list.
8

Hint
you can organize elements and data structure using following record structure AddressList. Define by your self a structure for storing infomation about an address. struct AddressList { struct AddressList *next; struct Address addr; };
9

Declaration of record structure

struct AddressList { struct AddressList *next; struct Address addr; }; next is the pointer variable which can express the next element; an element of AddressList. addr is instance of an address.
10

Important 3 factors of a LIST

Root: It keeps the head of the list. NULL: The value of pointer. It means the tail of the list. Cur: Pointer variable that keeps the element just now.
cur

Link list: insertion

Just after the current position
create new_item new->next = cur->next; cur->next = new; cur= cur->next;

cur

root

root (or head)

NULL
11

new_item

12

Link list: insertion

Just after the current position
new = ( struct AddressList * ) malloc( sizeof( struct AddressList ) ); new->addr = addr; new->next = NULL; if ( root == NULL ) { /* if there is no element */ root = new; cur = root; } else { cur->next = new; cur = cur->next; } }

Linked lists insertion

Another case: before the current position prev cur

root

13

Insert new item:

14

Traversing a list
for ( cur = root; cur != NULL; cur = cur->next ) { showAddress( cur->addr, stdout ); }

Traversing a list
Changing the value of pointer variable cur in sequence. These variables are called iterator. The traversing is finished if the value is NULL

cur

cur

root

NULL
15

root

NULL
16

Deletion
When we remove the first element root = del->next; free(del); When we remove the first element, change the value of root into the value of next which is pointed by del.
del

Deletion from the middle

We want to remove the node pointed by cur Determine prev which point to the node just before the node to delete

prev->next = cur->next; free(cur);

root

prev

cur

root

NULL
17 18

Exercise
Implement function insert, delete with a parameter n (integer) indicating the position of node to be affected.
The head position means 0th. 1st means that we want to add the element into the next place of the first element. 2nd means the next place of the second element. struct AddressList *insert (struct AddressList *root, struct Address ad, int n); struct AddressList *delete(struct AddressList *root, int n);
19

Freeing a list
to_free = root ; while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

20

Freeing all nodes of a list

to_free = root ; while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

to_free = root ;

to_free

root

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

21

22

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

23

24

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

25

26

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

27

28

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

29

30

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

31

32

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

33

34

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

to_free

root

to_free

root

35

NULL 36

Freeing all nodes of a list

while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }

Reverse a list
Given a list defined as:
struct list_int { int val; struct list_int *next; }; ... struct list_int *head=NULL;

to_free

root

Write a function that reverse a list of this type.

NULL 37
38

Exercise 3-3
Develop a simple student management program using linked list composed of node like this: typedef struct Student_t { char id[ID_LENGTH]; char name[NAME_LENGTH]; int grade; struct Student_t *next; } Student;

Exercise 3-3
so that: - The list is sorted in descending order of student's grades. - Program provide the functionality of:
- Insert new student (when you insert a new student into this list, first find the right position) - searching a student by ID: return to a pointer - delete a student with a given ID

- ;

39

40

Adding a student - begining

Next

Adding a student mid/end

root
Previous Next

root

Insert new item:

root

41

42

Student *add_student(Student *root, Student *to_add) { Student *curr_std, *prev_std = NULL; if (root == NULL) return to_add;

Adding a student beginning

if (root == NULL) return to_add; if (to_add->grade > root->grade) { to_add->next = root; return to_add; }

handle empty list handle beginning

if (to_add->grade > root->grade) { to_add->next = root; return to_add; }

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root; }

root

95

80

70

the rest

to_add
43

100
44

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

curr_std
80 70 60

prev_std
80

curr_std
70 60

root

95

root

95

to_add

75

45

to_add

75

46

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

prev_std
80

curr_std
70 60

prev_std
80

curr_std
70 60

root

95

root

95

to_add

75

47

to_add

75

48

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

prev_std
80

curr_std
70 60

prev_std
80

curr_std
70 60

root

95

root

95

to_add

75

49

to_add

75

50

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

prev_std
80

curr_std
70 60

prev_std
80

curr_std
70 60

root

95

root

95

to_add

75

51

to_add

75

52

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

Adding a student mid / end

curr_std = root; while (curr_std != NULL && to_add->grade < curr_std->grade) { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;

prev_std
80

curr_std
70 60

prev_std
80

curr_std
70 60

root

95

root

95

to_add

75

53

to_add

75

54

Exercise
Implement find_student, which receives a list and an ID number and returns a pointer to a student whose ID matches or NULL if no such student is found.

Removing a student
We would like to be able to remove a student by her/his ID. The function that performs this is remove_student

Student *find_student(Student *root, char* id); Hint: Use strcmp(s1, s2) which compares s1 and s2 and returns 0 if they are equal
55 56

Removing a student reminder

root
Previous Current

Removing a student beginning

if (root == NULL) return root; cur = root;

ID 14525 cur last

if (strcmp(cur->id, id) == 0) { root = root->next; free(cur); return root; }

57

root

14525

74823

53621

25773

58

Removing a student mid list

while (cur != NULL && { prev = cur; cur = cur->next; } strcmp(cur->id, id) != 0)

Removing a student mid list

while (cur != NULL && { prev = cur; cur = cur->next; } strcmp(cur->id, id) != 0)

ID 53621

ID 53621

if (cur != NULL) { prev->next = cur->next; free(cur); } return root;

if (cur != NULL) { prev->next = cur->next; free(cur); } return root;

cur

prev

cur

root

14525

74823

53621

25773

59

root

14525

74823

53621

25773

60

10

Removing a student mid list

while (cur != NULL && { prev = cur; cur = cur->next; } strcmp(cur->id, id) != 0)

Removing a student mid list

while (cur != NULL && { prev = cur; cur = cur->next; } strcmp(cur->id, id) != 0)

ID 53621

ID 53621

if (cur != NULL) { prev->next = cur->next; free(cur); } return root;

if (cur != NULL) { prev->next = cur->next; free(cur); } return root;

prev

cur

prev

cur

root

14525

74823

53621

25773

61

root

14525

74823

53621

25773

62

Removing a student mid list

while (cur != NULL && { prev = cur; cur = cur->next; } strcmp(cur->id, id) != 0)

Exercise
Add a change_grade function. The function should take as parameters the root of the list, the ID whose grade wed like to change, and the new grade Hint Create a new student with the same name, ID as the old one, with the new grade. Then remove the old student from the list and add the new one using the existing functions

ID 53621

if (cur != NULL) { prev->next = cur->next; free(cur); } return root;

prev

cur

root

14525

74823

25773

63

64

Question
We are now designing address list for mobile phones. You must declare a record structure that can keep a name, a phone number, and a e-mail address at least. And you must make the program which can deals with any number of the data. Hint: you can organize elements and data structure using following record structure AddressList

Double link list

An element has 2 pointer fields, we can follow front and back.
tail

/
5 head 12 5

struct AddressList { struct AddressList *prev; struct AddressList *next; struct Address addr; };
65

66

11

Declaration
typedef ... ElementType; typedef struct Node{ ElementType Element; Node* Prev; Node* Next; }; typedef Node* Position; typedef Position DoubleList;
67

Initialisation and check for emptiness

void MakeNull_List (DoubleList *DL){ (*DL)= NULL; } int Empty (DoubleList DL){ return (DL==NULL); }

68

Delete a node pointed by p

void Delete_List (Position p, DoubleList *DL){ if (*DL == NULL) printf(Empty list); else { if (p==*DL) (*DL)=(*DL)->Next; //Delete first element else p->Previous->Next=p->Next; if (p->Next!=NULL) p->Next->Previous=p->Previous; free(p); } }
DL 8 5 12

Delete a node pointed by p

void Delete_List (Position p, DoubleList *DL){ if (*DL == NULL) printf(Empty list); else { if (p==*DL) (*DL)=(*DL)->Next; //Delete first element else p->Previous->Next=p->Next; if (p->Next!=NULL) p->Next->Previous=p->Previous; free(p); } }
DL 8 5 12

/
5

/
5

69

70

Delete a node pointed by p

void Delete_List (Position p, DoubleList *DL){ if (*DL == NULL) printf(Empty list); else { if (p==*DL) (*DL)=(*DL)->Next; //Delete first element else p->Previous->Next=p->Next; if (p->Next!=NULL) p->Next->Previous=p->Previous; free(p); } }
DL 8 5

Insertion
void Insert_List (ElementType X,Position p, DoubleList *DL){ if (*DL == NULL){ // List is empty (*DL)=(Node*)malloc(sizeof(Node)); (*DL)->Element = X; (*DL)->Previous =NULL; (*DL)->Next =NULL; } else{ Position temp; temp=(Node*)malloc(sizeof(Node)); temp->Element=X; temp->Next=p; temp->Previous=p->Previous; if (p->Previous!=NULL) p->Previous->Next=temp; p->Previous=temp; } }
72

/
5

71

12