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
