Kĩ thuật lập trình - Data structures and algorithms – C++ implementation

Nội dung text: Kĩ thuật lập trình - Data structures and algorithms – C++ implementation

1. BK Ho Chi Minh City University of Technology BK TP.HCM TP.HCM Faculty of Computer Science and Engineering Data Structures and Algorithms – C++ Implementation Hu ỳnh Tấn Đạ t Email: htdat@cse.hcmut.edu.vn Home Page:
2. Pointer in C++
   Declaration Node *ptr; ??? ptr
   Create an object ptr = new Node();
   A pointer usage ptr printf (“Data in node: %d”, ptr ->data);
   Destroy an object ??? delete ptr; ptr
   NULL pointer ptr = NULL; ptr Faculty of Computer Science and Engineering – HCMUT Slide 2
3. Pointer in C++
   Be careful in these cases: Before Before ptr1 ptr1 ptr2 ptr2 ptr1 = ptr2; delete ptr1; ptr1 = NULL; Garbage ptr1 After ptr1 After ptr2 ptr2 Dangling reference problem Faculty of Computer Science and Engineering – HCMUT Slide 3
4. Parameter Passing Techniques void func(int* a, int* b){ void main() { int *t; int *p1 = new int; *p1 = 10; t = a; int *p2 = new int; a = b; *p2 = 20; b = t; func(p1, p2); } printf (“%d”, *p1); void func(int* &a, int* &b){ printf(“%d”, *p2); int *t; } t = a; a = b; b = t; } Faculty of Computer Science and Engineering – HCMUT Slide 4
5. Parameter Passing Techniques void func(int* &a, int* b){ void main() { int *t; int *p1 = new int; *p1 = 10; t = a; int *p2 = new int; a = b; *p2 = 20; b = t; func(p1, p2); } printf (“%d”, *p1); void func(int* a, int* &b){ printf(“%d”, *p2); int *t; } t = a; a = b; b = t; } Faculty of Computer Science and Engineering – HCMUT Slide 5
6. Parameter Passing Techniques void func(int a, int b){ void main() { int *t; int *p1 = new int; *p1 = 10; t = *a; int *p2 = new int; *a = *b; *p2 = 20; *b = t; func(&p1, &p2); } printf (“%d”, *p1); printf(“%d”, *p2); } Faculty of Computer Science and Engineering – HCMUT Slide 6
7. Linked Lists
   A linked list is an ordered collection of data in which each element contains the location of the next element Element = Data + Link head data link empty linked list Faculty of Computer Science and Engineering – HCMUT Slide 7
8. Nodes A node with A node with one data field three data fields number name id number A node with one structured data field name id number Faculty of Computer Science and Engineering – HCMUT Slide 8
9. Nodes Linked List Data node Structure structure count head data link list node dataType count data key head link field1 end list end node field2 fieldN end dataType Faculty of Computer Science and Engineering – HCMUT Slide 9
10. Nodes – Implementation in C++ struct Node { node int data; data Node *next; link end node }; Faculty of Computer Science and Engineering – HCMUT Slide 10
11. Nodes – Implementation in C++ Node *p = new Node(); 5 p->data = 5; p cout data; Node *q = p; cout data; q Node *r = new Node(); 10 r->data = 10; r q->next = r; cout next->data; Faculty of Computer Science and Engineering – HCMUT Slide 11
12. Nodes – Implementation in C++ struct Node { struct Node { int data; float data; Node *next; Node *next; }; }; template struct Node { ItemType data; Node *next; }; Faculty of Computer Science and Engineering – HCMUT Slide 12
13. Nodes – Implementation in C++ Node *p = new Node (); 5 p->data = 5; p cout data; Node *q = p; cout data; q Node *r = new Node (); 10 r->data = 10; r q->next = r; cout next->data; Faculty of Computer Science and Engineering – HCMUT Slide 13
14. Nodes – Implementation in C++ template class Node{ public : Node(){ this->next = NULL; } Node( ItemType data){ this->data = data ; this->next = NULL; } ItemType data; Node *next; }; Faculty of Computer Science and Engineering – HCMUT Slide 14
15. Linked List – Implementation in C++ template list class LinkedList{ count public : head LinkedList(); end list ~LinkedList(); protected : Node * head; int count; }; Faculty of Computer Science and Engineering – HCMUT Slide 15
16. Linked List Algorithms
    Create list
    Insert node
    Delete node
    Traverse
    Destroy list Faculty of Computer Science and Engineering – HCMUT Slide 16
17. Linked List Implementation template class LinkedList{ public : LinkedList(); ~LinkedList(); protected : int InsertNode(Node * pPre, List_ItemType value); List_ItemType DeleteNode (Node * pPre , Node * pLoc); int Search(List_ItemType value, Node * &pPre, Node * &pLoc); void Traverse(); Node * head; int count; }; Faculty of Computer Science and Engineering – HCMUT Slide 17
18. Linked List Implementation template class LinkedList{ public : LinkedList(); ~LinkedList(); void InsertFirst(List_ItemType value); void InsertLast(List_ItemType value); int InsertItem(List_ItemType value, int Position); List_ItemType DeleteFirst (); List_ItemType DeleteLast(); int DeleteItem(int Postion); int GetItem(int Position, List_ItemType &dataOut); void Print2Console(); void Clear(); // Augment your methods for linked list here!!! LinkedList * Clone(); protected : // Faculty of Computer Science and Engineering – HCMUT Slide 18
19. Linked List Implementation
    How to use Linked List data structure? int main( int argc, char* argv[] ) { LinkedList * myList = new LinkedList (); myList->InsertFirst(15); myList->InsertFirst(10); myList ->InsertFirst (5); myList->InsertItem(18, 3); myList->InsertLast(25); myList->InsertItem(20, 3); myList->DeleteItem(2); printf("List 1:\n"); myList->Print2Console(); Faculty of Computer Science and Engineering – HCMUT Slide 19
20. Linked List Implementation // int value; LinkedList * myList2 = myList->Clone(); printf("\nList 2:\n"); myList2 ->Print2Console(); myList2->GetItem(1, value); printf(“Value at position 1: %d”, value); delete myList; delete myList2; return 1; } Faculty of Computer Science and Engineering – HCMUT Slide 20
21. Create List Before list ? ? count head list.head = null list.count = 0 After list 0 count head Faculty of Computer Science and Engineering – HCMUT Slide 21
22. Create List Algorithm createList (ref list ) Initializes metadata for a linked list Pre list is a metadata structure passed by reference Post metadata initialized 1 list.head = null 2 list.count = 0 3 return End createList Faculty of Computer Science and Engineering – HCMUT Slide 22
23. Linked List Implementation template LinkedList ::LinkedList(){ this->head = NULL; this->count = 0; } Faculty of Computer Science and Engineering – HCMUT Slide 23
24. Insert Node
    Allocate memory for the new node and set up data
    Point the new node to its successor
    Point the new node's predecessor to it Faculty of Computer Science and Engineering – HCMUT Slide 24
25. Insert into Empty List Before 0 75 count head list pNew pNew -> link = list. head list.head = pNew After 1 75 count head list pNew Faculty of Computer Science and Engineering – HCMUT Slide 25
26. Insert at the Beginning Before 1 75 count head list 39 pNew pNew -> link = list.head list.head = pNew After 2 75 count head list 39 pNew Faculty of Computer Science and Engineering – HCMUT Slide 26
27. Insert in Middle Before 2 39 75 count head list 52 pPre pNew pNew -> link = pPre -> link pPre -> link = pNew After 3 39 75 count head list 52 pPre pNew Faculty of Computer Science and Engineering – HCMUT Slide 27
28. Insert at End Before 3 39 52 75 count head list 134 pPre pNew pNew -> link = pPre -> link pPre -> link = pNew After 4 39 52 75 count head list 134 pPre pNew Faculty of Computer Science and Engineering – HCMUT Slide 28
29. Insert Node Algorithm Algorithm insertNode (ref list , val pPre , val dataIn ) Inserts data into a new node in the linked list Pre list is metadata structure to a valid list pPre is pointer data’s logical predecessor dataIn contains data to be inserted Post data have been inserted in sequence Return true if successful, false if memory overflow Faculty of Computer Science and Engineering – HCMUT Slide 29
30. Insert Node Algorithm 1 allocate(pNew) 2 if (memory overflow) 1 return false 3 pNew -> data = dataIn 4 if (pPre = null) Adding before first node or to empty list 1 pNew -> link = list.head 2 list.head = pNew 5 else Adding in middle or at end 1 pNew -> link = pPre -> link 2 pPre -> link = pNew 6 list.count = list.count + 1 7 return true End insertNode Faculty of Computer Science and Engineering – HCMUT Slide 30
31. Insert Node template int LinkedList ::InsertNode( Node *pPre, List_ItemType value) { Node *pNew = new Node (); if (pNew == NULL) return 0; pNew->data = value; if ( pPre == NULL){ pNew->next = this->head; this->head = pNew; } else { pNew->next = pPre->next; pPre->next = pNew; } this->count++; return 1; } Faculty of Computer Science and Engineering – HCMUT Slide 31
32. Delete Node
    Locate the node to be deleted.
    Point the node predecessor's link to its successor.
    Release the memory for the deleted node Faculty of Computer Science and Engineering – HCMUT Slide 32
33. Delete First Node Before 3 39 52 75 count head list pPre pLoc list.head = pLoc -> link recycle(pLoc) After 2 recycled 52 75 count head list pPre pLoc Faculty of Computer Science and Engineering – HCMUT Slide 33
34. General Delete Case Before 3 39 52 75 count head list pPre pLoc pPre -> link = pLoc -> link recycle (pLoc) After 2 39 recycled 75 count head list pPre pLoc Faculty of Computer Science and Engineering – HCMUT Slide 34
35. Delete Node Algorithm Algorithm deleteNode (ref list , val pPre , val pLoc ref dataOut ) Delete data from a linked list and returns it to calling module Pre list is metadata structure to a valid list pPre is a pointer to predecessor node pLoc is a pointer to node to be deleted dataOut is variable to receive deleted data Post data have been deleted and returned to caller Faculty of Computer Science and Engineering – HCMUT Slide 35
36. Delete Node Algorithm 1 dataOut = pLoc -> data 2 if (pPre = null) Delete first node 1 list.head = pLoc -> link 3 else Delete other nodes 1 pPre -> link = pLoc -> link 4 list.count = list.count - 1 5 recycle (pLoc) 6 return End deleteNode Faculty of Computer Science and Engineering – HCMUT Slide 36
37. Delete Node template List_ItemType LinkedList ::DeleteNode( Node *pPre, Node *pLoc){ List_ItemType result = pLoc->data; if (pPre == NULL) list->head = pLoc->next; else pPre->next = pLoc->next; this->count ; delete pLoc; return result; } Faculty of Computer Science and Engineering – HCMUT Slide 37
38. Traverse List
    Traverse module controls the loop: calling a user-supplied algorithm to process data pWalker = list.head loop ( pWalker not null) process (pWalker -> data) pWalker = pWalker -> link Faculty of Computer Science and Engineering – HCMUT Slide 38
39. Traverse List template void LinkedList ::Traverse() { Node *p = head; while (p != NULL){ p->data++; // process data here!!! p = p->next; } } template void LinkedList ::Traverse( void (*visit)(List_ItemType &) ) { Node *p = head; while (p != NULL){ (*visit)(p->data); p = p->next; } } Faculty of Computer Science and Engineering – HCMUT Slide 39
40. Searching in Linked List template int LinkedList :: Search(List_ItemType value, Node * &pPre, Node * &pLoc){ pPre = NULL; pLoc = this->head; while (pLoc != NULL && pLoc->data != value){ pPre = pLoc; pLoc = pLoc->next; } return (pLoc != NULL); // found: 1; notfound: 0 } Faculty of Computer Science and Engineering – HCMUT Slide 40
41. Destroy List Algorithm Algorithm destroyList (val list ) Deletes all data in list. Pre list is metadata structure to a valid list Post all data deleted 1 loop (list.head not null) 1 dltPtr = list.head 2 list.head = this.head -> link 3 recycle (dltPtr) No data left in list. Reset metadata 2 list.count = 0 3 return End destroyList Faculty of Computer Science and Engineering – HCMUT Slide 41
42. Destroy list template void LinkedList ::Clear(){ Node *temp; while (this->head != NULL){ temp = this->head; this->head = this->head->next; delete temp; } this->count = 0; } template LinkedList :: ~LinkedList (){ this->Clear(); } Faculty of Computer Science and Engineering – HCMUT Slide 42
43. Exercises template class LinkedList{ public : LinkedList(); ~LinkedList(); int InsertFirst(List_ItemType value); int InsertLast(List_ItemType value); int InsertItem (List_ItemType value, int Position); List_ItemType DeleteFirst(); List_ItemType DeleteLast(); int DeleteItem(int Postion); int GetItem(int Position, List_ItemType &dataOut); void Print2Console(); // Augment more methods for linked list here!!! LinkedList * Clone(); protected : // as previous slide Faculty of Computer Science and Engineering – HCMUT Slide 43
44. Pointer vs. Object Variable void main(){ LinkedList *p = new LinkedList(); p->InsertLast(20); // do sth with p here 1 20 func(p); p count head delete p; } void main(){ LinkedList ob; 1 20 ob.InsertLast(20); count head // do sth with ob here func(ob); ob } Faculty of Computer Science and Engineering – HCMUT Slide 44
45. Pointer vs. Object Variable void func(LinkedList *a) a->InsertFist(10); a } void func(LinkedList myOb) myOb.InsertFist (10); count head } myOb
    What are the pros and cons? Faculty of Computer Science and Engineering – HCMUT Slide 45
46. Sample Solution: Insert template int LinkedList ::InsertItem(List_ItemType value, int position) { if (position this->count) return 0; Node * newPtr, *pPre; newPtr = new Node (); if (newPtr == NULL) return 0; newPtr->data = value; if (head == NULL) { head = newPtr; newPtr->next = NULL; } else if (position == 0) { newPtr->next = head; head = newPtr; } Faculty of Computer Science and Engineering – HCMUT Slide 46
47. Sample Solution: Insert else { // Find the position of pPre pPre = this->head; for (int i = 0; i next; // Insert new node newPtr ->next = pPre ->next; pPre->next = newPtr; } this->count++; return 1; } Faculty of Computer Science and Engineering – HCMUT Slide 47
48. Sample Solution: Delete template int LinkedList ::DeleteItem(int position){ if (position this->count) return 0; Node *dltPtr, *pPre; if (position == 0) { dltPtr = head; head = head->next; } else { pPre = this ->head; for (int i = 0; i next; dltPtr = pPre->next; pPre->next = dltPtr->next; } delete dltPtr; this->count ; return 1; } Faculty of Computer Science and Engineering – HCMUT Slide 48
49. Sample Solution: Clone template LinkedList * LinkedList ::Clone(){ LinkedList * result = New LinkedList (); Node * p = this->head; while (p != NULL) { result->InsertLast(p->data); p = p->next; } result->count = this->count; return result; } Faculty of Computer Science and Engineering – HCMUT Slide 49
50. Homework
    Reverse a linked list head a b a b c Result: a b a b c head Faculty of Computer Science and Engineering – HCMUT Slide 50
51. Homework
    Hint 1 head a b a b c new_tail ->next = head; head->next = NULL; Result: head = new_head; a b a b c new tail new head Faculty of Computer Science and Engineering – HCMUT Slide 51
52. Homework
    Hint 2 head a b a b c p->next = head; Result: head = p; p= p1; p1=p1->next a b a b c head p p1 Faculty of Computer Science and Engineering – HCMUT Slide 52
53. Homework template void LinkedList ::Reverse(){ } Faculty of Computer Science and Engineering – HCMUT Slide 53