Working with Pointers

of 79

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
79 pages
0 downs
5 views
Share
Description
Working with Pointers. An exercise in destroying your computer. What is this?. Your worst nightmare! Comes from pointer misuse. Let’s look at Memory! Blue is memory address, Black is value. 1 -4717. 2 -901. 3 76. 4 -0. 5 98131. 6 -1038. 7 -554. 8 7462. 9 312. 11 3619. 10
Transcript
Working with PointersAn exercise in destroying your computerWhat is this?
  • Your worst nightmare!
  • Comes from pointer misuse
  • Let’s look at Memory!Blue is memory address, Black is value1-4717 2-901 376 4-0 598131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25-4717 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Declare an intint myInt;1-4717 2-901 376 4-0 598131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt-4717 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 What’ve we done?
  • By declaring the int, we’ve taken up just enough memory to hold an int
  • We don’t know where in memory (the address) that it’s located
  • Computer picks “at random”
  • What value is at that memory location?
  • Can we print that value out?
  • The value –4717 would print! (garbage)
  • Copy 42 into that Section of MemorymyInt = 42;1-4717 2-901 376 4-0 598131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25 myInt26-19 2721511 42329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Pointers
  • Allow us to get to the address of where information is located
  • Similar to call forwarding
  • Ask the pointer where to go
  • Go there for the information
  • To create a pointer, we use the *
  • Follows format of <data type> <name>;
  • Example: int* ptr;
  • Declare an int pointerint* ptr;1-4717 2-901 376 4-0 5ptr98131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Now what have we done?
  • Created a new variable of type ptr that points to an int
  • Notice that we haven’t initialized the pointer to “point” to myInt yet
  • What if we print the pointer out?
  • cout << ptr;(prints out value of ptr: 98131)1-4717 2-901 376 4-0 5ptr98131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Problem
  • How do we get address of myInt so ptr can point to it?
  • Remember, we can still access the value of myInt directly
  • int someInt = myInt;
  • We really need the pointer to store the address of where myInt is located
  • We do not need to store the value of myInt for the pointer (just the address)
  • The & operator
  • Use the & operator to get the address of where the variable is in memory
  • What would the following statement print to the screen?
  • cout << &myInt << endl;What would happen?cout << &myInt;1-4717 2-901 376 4-0 5ptr98131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Getting the Pointer to Point
  • We now need “ptr” to point to myInt
  • Code:
  • ptr = &myInt;ptr is a pointer,so it expects anaddress to be assigned to itHere, we get the address of wheremyInt is stored in memory and copythat value into “ptr”Before1-4717 2-901 376 4-0 5ptr98131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Afterptr = &myInt;1-4717 2-901 376 4-0 5ptr25 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 What would this do?ptr = myInt;1-4717 2-901 376 4-0 5ptr98186 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Wrong Addressptr = myInt;1-4717 2-901 376 4-0 5ptr42 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Tricky Screens of Death!
  • Last thing to learn is how to “de-reference” a pointer
  • This means “how to follow the pointer”
  • Unfortunately, we use the * operator as well
  • Example:
  • cout << *ptr << endl; Follow wherever ptr is pointing to and print that value out.Follow the Pointer and Print it Outcout << *ptr << endl;1-4717 2-901 376 4-0 5ptr25 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25myInt42 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Another ExampleBlue is memory address, Black is value, Red is variable name1-4717 2-901 376 4-0 598131 6-1038 7-55487462 9312 113619 10-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25-4717 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Declare a Pointerint *ptr;1-4717 2-901 376 4-0 598131 6-1038 7-55487462 9312 113619 10 ptr-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25-4717 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 What would happen?cout << *ptr << endl;1-4717 2-901 376 4-0 598131 6-1038 7-55487462 9312 113619 10 ptr-6 12-4717 1360981 144148 21-78781 1586851 16-5155 1795151 18-47 192251 200 28-9 22-901 23-6 246720 25-4717 26-19 2721511 329 3578512917 31-651 34-896761 30-6561 33761 379996 38674547 39-686840-1 415431 42-4717 36-6 Blue Screen of Death!Why do I need Pointers?
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • void cannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012-291571345-29910-336784161-1Declare myInt
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • void cannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012-291571345-29910-33678myInt4117-1Call the function
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • voidcannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012-291571345-29910-33678myInt4117-1Here’s where the Copy is Made
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • void cannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012x-217571345-29910-33678myInt4117-1Changing Only Local Copy
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • void cannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012x-26571345-29910-33678myInt4117-1Print Out Local Copy (6)
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • void cannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012x-26571345-29910-33678myInt4117-1Return to Main (print 17)(x is gone and leaves garbage)
  • Because parameter passing only passes a copy so the function can’t change main’s variables!
  • void cannotChange (int x) { x = 6; cout << x << endl;}void main ( ) {int myInt = 17; cannotChange (myInt); cout << myInt << endl; }Memory012-26571345-29910-33678myInt4117-1Now with Pointersvoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012-26571345-29910-3367841412-1Declare myIntvoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012-26571345-29910-33678myInt4117-1Declare a Pointer to myIntvoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012ptr76571345-29910-33678myInt4117-1Pass a Copy of ptrvoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012ptr76571345-29910-33678myInt4117-1Pass a Copy of ptrvoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012xptr767345-29910-33678myInt4117-1Change Whatever x is Pointing toovoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012xptr767345-29910-33678myInt4117-1Change Whatever x is Pointing toovoid canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012xptr767345-29910-33678myInt416-1Follow x and Print it Out (6)void canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012xptr767345-29910-33678myInt416-1See the Change in main (6 also)void canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Memory012xptr767345-29910-33678myInt416-1Interesting NoteAt this point, these two statements print out the same thing!cout << *ptr << endl;cout << myInt << endlSo do these!cout << ptr << endl;cout << &myInt << endl;WHY?void canChange (int* x) { *x = 6; cout << *x << endl;}void main ( ) {int myInt = 17;int* ptr = &myInt; canChange (ptr); cout << myInt << endl; }Summary of Pointers
  • To understand pointers, you need to understand memory
  • The & is the secret to it all!
  • Create and de-reference with *
  • Passing a pointer to a function can make changes to the main
  • Lists, Linked Lists, Stacks,and QueuesWhat the is a Linked List?
  • A List is a collection of data elements in an array structure. From any given element in the array, the previous and next items can be obtained by moving to adjacent memory locations.
  • A Linked List is a collection of data elements where the location of each element in memory is only recorded by a pointer from a previous element. The data elements may happen to be adjacent in memory, but you cannot rely on this.
  • 221016955527221016955527What the is a Linked List?
  • List : (Array of 5 elements : simple integers)
  • Linked List : (5 elements - all simple integers)
  • What the is a Linked List?
  • Are just a sequence of data linked together in memory.
  • Each element in the list is made up of data plus a pointer to the next element in the list.
  • Node is the common name used for this data plus the associated pointer to the next item in the list.
  • However, many kilo-bytes of data : names, addresses, student-ids, etc - could be stored at each Node.
  • A chain is only as strong as its weakest link.
  • Similarly, if something erased or corrupted a Node in the middle of the list, then Nodes after this will NOT be found !
  • Queues : FIFO Vs LIFO
  • Queues can be of two main types :
  • FIFO - First In First Out
  • The first item into the queue is the first to be processed or output.
  • Example : Supermarket checkout queue.
  • LIFO queue - Last In First Out.
  • The last item into the queue is the first one out.
  • Example : Stack of paper - where you put paper on top of each other and can only get to a page in the stack by removing each page on top of it in turn.
  • Linked Lists - All are LIFO in this Lecture
  • We are going to build all Linked Lists in this lecture on a LIFO queue, but we could have made them all FIFO instead.
  • Exercise : As an exercise that will help you understand queues and Linked Lists, you can convert these examples to FIFO.
  • Building a Basic Linked List#include <iostream.h> // for cin and cout.#include <mem.h> // for NULL.#include <stdio.h> // getchar// Define the type of data to be stored at each nodetypedef float ListElement;struct Node{ ListElement Value; // Data stored at this Node Node* Next; // Pointer to Next Node in the List};Basic Linked List - only 4 Functionsclass Linked_List{ private:Node *First; public: Linked_List(); // Constructor// Add Node into the start of a Linked List void Insert_Node (ListElement In_Value);};Value 1Value 2Value 3FirstNULLNextNextNextBasic Linked List - Diagram
  • Once we have setup the class member functions and created a main() program to use our Linked List class, our Linked List could be visualized as :
  • Basic Linked List - ConstructorLinked_List::Linked_List()// Constructor{// Create an empty list First = NULL;}Basic Linked List - Insert Nodevoid Linked_List::Insert_Node (ListElement In_Value)// Add Node into the start of a Linked List.{ Node *New_Node = new Node;// Store the value of the node. New_Node->Value = In_Value;// The Next Node in the list is currently the First Node. New_Node->Next = First;// Make our new node the new First Node. First = New_Node;}Basic Linked List - Overloaded Output << Operatorostream& operator << (ostream& out, const Linked_List& My_List){ Node *Curr_Node; Curr_Node = My_List.First; // Loop through all nodes in the list. while (Curr_Node != NULL) { out << "\n" << Curr_Node->Value; // Display each Node's Value Curr_Node = Curr_Node->Next; // Point at the next node in the list } out << endl; return out;}Basic Linked List - simple Main programvoid main(){ Linked_List My_List; // Define a Linked List My_List.Insert_Node (1.1); // Add in a bunch of nodes My_List.Insert_Node (2.2); My_List.Insert_Node (3.3); cout << "\n" << My_List; // Display the list}1.1Next2.21.1FirstNULLNextNextBasic Linked List - What really is happening?Declaring the Linked List : Linked_List My_List; Would simply set First to NULL, so we have a pointer pointing at the null memory address.Inserting the first node : My_List.Insert_Node (1.1);Inserting the second node : My_List.Insert_Node (2.2);FirstNULLLinked Lists - Find All Nodes with a particular Valuevoid Linked_List::Find_Nodes_With_Value (ListElement In_Value)// Find ALL Nodes in a Linked List with a particular value stored in them.{// Allocate a working Node. Node *Curr_Node = First; int Node_Count = 0;// Keep track of the number ofNodes found.// Skip through the Linked List and list all nodes we find with the required value. cout << "\nNodes with value of " << In_Value << " : ";Linked Lists - Find All Nodes with a particular Value while (Curr_Node != NULL) { Node_Count++; if (Curr_Node->Value == In_Value) cout << Node_Count << ", "; Curr_Node = Curr_Node->Next; } if (Node_Count == 0) cout << "No Nodes Found !!"; cout << endl;}Linked Lists - Find All Nodes with a particular Value
  • Example Usage :
  • Find_Nodes_With_Value (3.3);
  • will display all Nodes in the linked list with a value of 3.3.
  • If none are found, a “None Found” message will be displayed.
  • Linked ListsDelete a Node from the List
  • We will now look at a function to delete a particular node in the list.
  • Remember:
  • When we insert a new node, it is our new FIRST node.
  • We have a LIFO queue - Last In First Out.
  • So, when we delete node number 1, we are actually deleting the first node in the list, which is the node most recently added to the list!
  • Linked ListsDelete a Node from the List void Linked_List::Delete_Node (unsigned int Node_Num)// Delete a Node from a Linked List.{// Allocate Del and Prev Nodes. Node *Del_Node = First; Node *Prev_Node = First;// Skip through the Linked List to get to the required node. for (int i = 1; i < Node_Num; i++) { if (Del_Node->Next == NULL) // Stop when there are no more nodes. break; Prev_Node = Del_Node; Del_Node = Del_Node->Next; }Linked ListsDelete a Node from the List// Make sure we are deleting a valid Node. if (Node_Num > 0) { if (Node_Num == 1)// If we are deleting the first node, make First point at the second// node in the list. First = Del_Node->Next; else// Point the previous node to the node after the one to be deleted. Prev_Node->Next = Del_Node->Next;// Delete the required Node. delete Del_Node; }}Linked ListsDelete a Node from the ListDelete_Node (0) will delete nothing. There is not a 0’th node number in the list. Delete_Node (1)will delete the first node in the list. (i.e. the last node inserted into the list, since nodes are inserted at the start of the list by the Insert function. Remember : LIFO! Delete_Node (2)will delete the second node. (i.e. the second last node inserted into the list).Linked ListsDelete a Node from the List Delete_Node (50)will delete the last node if there are 50 nodes in the list. (i.e. the very first node inserted into the list). Delete_Node (99)when there are only 50 nodes in the list will delete the last node in the list. (i.e. the very first node inserted into the list).Some Points on Linked Lists
  • When working with pointer data structures (such as Linked Lists) it is important that you use diagrams when developing or interpreting code, even experienced code writers make logic errors.
  • Be very careful when inserting or deleting nodes so that links between nodes are not broken.
  • It is crucial that you ensure your code works with all nodes - especially the first and last nodes in the list.
  • Generic Linked List Class
  • Let’s start of with an extremely basic class - called Animals.
  • Then, we will include this class in a Liked List class, and use the member functions of our Animals class to do any of the input / output for Animals.
  • In this way, by changing a single line of code in our Linked List class, we can make our Linked List work with any kind of data in any kind of class.
  • Generic Linked List - Animals Class Headerclass Animal{ private: float Height; char Name[30]; int Age; public: Animal(); // Constructor.};Generic Linked List - Animals Class Member FunctionsAnimal::Animal() // Constructor.{ Anim_Height = 0; Anim_Name [0] = '\0'; Anim_Age = 0;}Ge
    Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks