CMPT 135语言 辅导、 写作C++编程

” CMPT 135语言 辅导、 写作C++编程CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 1CMPT 135 FIC 202101 – Assignment 2Supplementary Material: Linked List Data StructureInstructor: Dr. Yonas T. Weldeselassie (Ph.D.)In this supplementary material, we will describe the linked list data structure and discuss the typicaloperations that we can perform on linked lists.Linked List Data StructureDefinition: A linked list data structure is a container whose size can expand (by inserting new objects intothe container) or shrink (by removing objects from the container) and that stores its objects in sequence suchthat each object Knows the object in the container that comes after it. Fig 1 below shows a linked list with fourobjects.Fig 1. Linked List Data StructureTerminologies Each object in a linked list is called a node. Thus the linked list in fig 1 above has four nodes. A node has two parts: a data part where we store data and a pointer part which points to the nextnode in the linked list. The last node in the linked list points to a special pointer value that indicates the end of the linked list.A convenient value that we can easily use will be the nullptr value. A linked list also requires a pointer that points to the first node in the linked list. This pointer is usuallyreferred to as the head of the linked list. A linked list with no nodes is known as an empty linked list. Thus a linked list is empty if its headpointer has a nullptr value.Representing a Node of a linked listSince a node is an object, we may use either a C++ struct or a C++ class to represent it. A node will have twomember variables; namely a data member variable (where we will store some data of our choice) and apointer member variable of type node pointer (where we will store the memory address of the next node inthe linked list). The data member variable can be any data type depending on what kind of information we areinterested to store in our linked list.The following class demonstrates a C++ class named Node that represents a node of a linked list whose datamember variable is an integer data type and whose pointer member variable is a Node* data type.Observe that it is a good programming Habit to have typedef names whenever we work with pointers so thatto minimize coding and debugging time. Thus since we will be working quite a lot with Node*, it is a good ideato have a typedef name for it. We see that we can specify a typedef name inside a class right at the beginningin order to use the typedef inside the class block but not outside the class block. We will then need to specifythe typedef name again outside the class in order to use it in the remaining part of our program. The bestplace to specify the typedef Again is right after the class declaration but before the class definition as shownbelow. We also provide a test program to demonstrate how to use the Node class in our applications.head nullptrData Data Data DataCMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 2#includeiostreamusing namespace std;class Node{typedef Node* NodePtr;private:int data;NodePtr link;public:Node();Node(const int );Node(const Node );//Deep copy of the node but not any other node linked to itint getData() const;NodePtr getLink() const;void setData(const int );void setLink(const NodePtr );friend ostream operator (ostream , const Node );};typedef Node* NodePtr;Node::Node() : data(0), link(nullptr) {}Node::Node(const Node n) : data(n.data), link(nullptr) {}Node::Node(const int d) : data(d), link(nullptr) {}int Node::getData() const { return data; }NodePtr Node::getLink() const { return link; }void Node::setData(const int d) { data = d; }void Node::setLink(const NodePtr p) { link = p; }ostream Operator (ostream out, const Node n){out n.data;return out;}int main(){//Create three nodes and print themNode n1; //n1 data is 0 and n1 link is nullptrNode n2(5); //n2 data is 5 and n2 link is nullptrNode n3(n2); //n3 data is 5 and n3 link is nullptrcout Node 1 is n1 endl;cout Node 2 is n2 endl;cout Node 3 is n3 endl;system(Pause);return 0;}Representing a linked listIn order to represent a linked list, all we need is the head pointer of the linked list. Then the head pointer willhave information where to find the first node in the linked list. Why? Because it will be assigned the memoryaddress of the first node in the linked list and therefore will be pointing to the first node in the linked list.Similarly the first node will know where to find the second node. Why? Because the link pointer of the firstnode will be assigned the memory address of the second node and thus it will be pointing to it. Similarly, thesecond node also will know where to find the third node, the third node will know where to find the fourthnode, and so on so forth. Thus given the Node class shown above, the following program demonstrates theCMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 3creation of a linked list and traversal of the linked list in order to print the nodes in the order they arearranged in the linked list.int main(){//Create three nodesNode n1; //n1 data is 0 and n1 link is nullptrNode n2(5); //n2 data is 5 and n2 link is nullptrNode n3(n2); //n3 data is 5 and n3 link is nullptr//Create a linked list with the sequence head–n1–n2–n3–nullptrNodePtr head = n1; //head is pointing to n1 noden1.setLink(n2); //n1 link is pointing to n2 noden2.setLink(n3); //n2 link is pointing to n3 node//Traverse the linked list to print the nodes in the linked listcout Printing the linked list endl;while (head != nullptr){cout *head ;head = head-getLink(); //Now head will point to the next node}cout endl;system(Pause);return 0;}Observation: Observe that traversal of a linked list is possible only in the forward direction but not in thebackward direction. Neither does a linked list data structure allow random access of its nodes. If we want toaccess a node, then the only Way is to start from the head pointer and traverse in a forward direction until wefind the node of our interest.Caution 1: Observe that we must always test if any node pointer (including the head pointer) is a nullptrbefore we dereference the pointer or before calling the getLink() member function. Otherwise dereferencingor calling the getLink() member function on a node pointer with a nullptr value will cause a runtime error. Ingeneral, we should always consider the nullptr value as a special case whenever we work with node pointers.Caution 2: Observe that after traversing through the linked list during the printing of the nodes in theprogram above, at the end the value of the head pointer will become nullptr; which means it is no morepointing to the first node in the linked list and therefore it is no more the head of the linked list. This means inessence we have lost our linked list. Thus, if we want to perform more traversals of the linked list afterwardsthen we cant because we have lost the head of the linked list. This shortcoming will be fixed in our nextexample program.Constructing linked lists: Empty linked listA linked list is constructed starting with an empty linked list; that is where there are no nodes in it. An emptylinked list is constructed by assigning its Head pointer a nullptr value. Then new nodes are inserted to thelinked list either at the beginning of the linked list, in the middle of the linked list, or at the end of the linkedlist as we desire.Moreover, typically nodes of a linked list are stored on the heap memory so that to be able to expand orshrink the linked list at run time as we desire.CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 4Inserting nodes in a linked list: head_insert algorithmThe easiest way to insert a new node into a linked list is to insert the new node as a first node in the linked list.Inserting a new node as a first node is usually referred to as head_insert operation. The diagram below showsa linked list before and after a new node (shown in red color) is inserted using head_insert algorithm.Given linked listThe same linked list after a new node is inserted with head_insertThe following program demonstrates the creation of an empty linked list, inserting new nodes (created on theheap memory) with head_insert algorithm, traversal of the linked list in order to print the nodes, and finallytraversal of the linked list in order to delete the nodes of the linked list from the heap memory.int main(){//Create an empty linked listNodePtr head = nullptr;//Insert five nodes in the linked list using head_insert operationfor (int i = 0; i 5; i++){NodePtr n = new Node(i);n-setLink(head);head = n;}//Print the linked listcout Printing the linked list. endl;NodePtr temp = head;while (temp != nullptr){cout *temp endl;temp = temp-getLink();}//Delete the nodes From the heapcout Deleting the linked list. endl;while (head != Nullptr){temp = head;head = head-getLink();delete temp;}system(Pause);return 0;}nullptrnullptrheadheadCMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 5The output of the program will be 4 3 2 1 0. We note that when using the head_insert algorithm, the lastnode that has been inserted will be printed first. This is known as last in first out (LIFO) ordering.Some remarks about the program: We observe that the head pointer should never be used for traversal except when deleting the nodes.Otherwise if we had used the head pointer for traversal (say for example for printing the nodes) thenafter printing the nodes the head pointer would have had a nullptr value which means it would notknow where the first node is located in the heap memory. Moreover we wouldnt be able to re-assignthe head pointer the memory address of the first node because we dont have not stored in anothervariable. This means we would have lost the first node. Then that would mean we wouldnt be able tolocate the second node either because the only way to locate the second node is by going through thefirst node. It means we would Also lose the third node and so on so forth. That is, we would have lostthe entire linked list. When deleting a linked list however, it is perfectly fine to use the head pointer for traversal becausewe dont need to locate the nodes After they are deleted. Once all the nodes are deleted, we see thatthe head pointer will have a nullptr value which indicates the linked list has become empty which iscorrect.Typically, we perform the head_insert, printing, and other operations of a linked list using functions. Thus theprogram given above modified to use functions for its head_insert, printing, and deleting the linked listoperations would look like as follows.void head_insert(NodePtr head, const int value){NodePtr n = new Node(value);n-setLink(head);head = n;}void print_linkedlist(const NodePtr head){NodePtr temp = head;while (temp != nullptr){cout *temp ;temp = temp-getLink();}cout endl;}void delete_linkedlist(NodePtr head){NodePtr temp;while (head != nullptr){temp = head;head = Head-getLink();delete temp;}}int main(){//Create an empty linked listNodePtr head = nullptr;//Insert five nodes in the linked list using head_insertalgorithmfor (int i = 0; i 5; i++)CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 6head_insert(head, i);//Print the linked listcout Printing the linked list. endl;print_linkedlist(head);//Delete the nodes of the linked list from the heap memorycout Deleting the linked list. endl;delete_linkedlist(head);system(Pause);return 0;}Some remarks about the functions: The head argument must pass by reference to the head_insert and delete_linkedlist functions because wewant to modify its value in these functions and have the modification reflected on the main program aswell. This means we will be passing a pointer by reference. The typedef name will make the syntax easierto understand. However it is not necessary to pass the head argument by reference to the print_linkedlist function;although we still do so for efficiency purposes and use const modifier to make sure the value of the headargument is not modified in the function.Searching for a node in a linked list: search_node algorithmWe may also be interested to search if there exists a node in a linked list that satisfies some condition. Forexample, we could search for a node whose data is equal to a given value.The search_node function given below takes the head pointer of a linked list and an integer value as itsarguments and returns a pointer to a node in the linked list whose data is equal to the integer value argument.If there is no any node in the linked list that satisfies the condition then the function will return nullptr.Moreover if there are two or more nodes that satisfy the condition then the function will return a pointer tothe first node it finds that satisfies the condition.NodePtr search_node(const NodePtr head, const int value){NodePtr temp = head;while (temp != nullptr){if (temp-getData() == value)return temp;elsetemp = temp-getLink();}return nullptr;}int main(){//Create an empty linked listNodePtr head = nullptr;//Insert five nodes in the linked list using head_insertalgorithmfor (int i = 0; i 5; i++){CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 7head_insert(head, i);}//Print the linked listcout Printing the linked list. endl;print_linkedlist(head);int search_value = 2;NodePtr n = search_node(head, search_value);if (n != nullptr)cout A node whose data is equal to n-getData() is found. endl;elsecout A node whose data us Equal to search_value is not found. endl;search_value = 8;n = search_node(head, search_value);if (n != nullptr)cout A node whose data is equal to n-getData() is found. endl;elsecout A node whose data us equal to search_value is not found. endl;//Delete the linked listcout Deleting the linked list. endl;delete_linkedlist(head);system(Pause);return 0;}Inserting nodes in a linked list: insert_after algorithmWe may also insert a new node after a specified node. For example, we may use the search_node function tosearch for a specific node and then insert a new node after that specified node.The diagram below shows a given linked list with three nodes and the same linked list after a new node(shown in red color) has been inserted after the second node (that is between the second the third nodes).Such insertion operation is commonly known as insert_after operation.Given linked listThe same linked list after inserting a new node after the second node in the linked listIn order to implement the insert_after function, we first note the following subtle points about the operationhead nullptrhead nullptrCMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 8 The function takes two arguments; namely a node pointer and an integer value. If the node pointer argument is a nullptr value then this function should return without inserting anynew node because it doesnt make sense to insert after a nullptr. The new nodes data will be the integer value argument and it will be inserted after the node pointedby the node pointer argument. This function does not require the head pointer of the linked list.The following program demonstrates the insert_after algorithm. Please note that it is not necessary to passthe node pointer argument to the function by reference because we will not modify its value. Instead we aredereferencing it and therefore even if We use parameter passing by value then it would still be fine.void insert_after(const NodePtr n, const int value){if (n == nullptr)return;else{NodePtr temp = new Node(value);temp-setLink(n-getLink());n-setLink(temp);}}int main(){//Create an empty linked listNodePtr head = nullptr;//Insert five nodes in the linked list using head_insert operationfor (int i = 0; i 5; i++){head_insert(head, i);}//Print the linked list. This will print 4,3,2,1,0cout Printing the linked list. endl;print_linkedlist(head);//Insert a new node with data equal to -4 after the node whose data is equal to 2int search_value = 2;NodePtr n = search_node(head, search_value);insert_after(n, -4);//Print the linked list. This will print 4,3,2,-4,1,0cout Printing the linked list. endl;print_linkedlist(head);//Insert a new node with data equal to -6 after the node whose data is equal to 8search_value = 8;n = search_node(head, search_value);insert_after(n, -6); //This will not insert because n will be nullptr//Print the linked list. This will still print 4,3,2,-4,1,0cout Printing the linked list. endl;print_linkedlist(head);//Delete the nodes from the heapcout Deleting the linked list. endl;delete_linkedlist(head);CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 9Inserting nodes in a linked list: tail_insert algorithmWe may also be interested to insert a new node as a last node in a given linked list. Then we will have twocases to consider: If the linked list is empty then this function will insert the new node as the first node of the linked list(which will also be the last node in the linked). Thus the insertion will be performed using thehead_insert function. Otherwise we will first find the last node of the linked list and then we will insert after the last nodeusing the insert_after function.The following program demonstrates the tail_insert algorithm.void tail_insert(NodePtr head, const int value){if (head == nullptr)head_insert(head, value);else{//Find the last node in the linked listNodePtr b = head; //Here b is guaranteed to be not nullptrwhile (b-getLink() != nullptr)b = b-getLink();//Now insert after binsert_after(b, value);}}int main(){srand(time(0));//Create an empty linked listNodePtr head = nullptr;//Insert ten random integers using insert_increasing functionfor (int i = 0; i 5; i++)tail_insert(head, i);//Print the linked list. This will still print 0,1,2,3,4cout Printing the linked list. endl;print_linkedlist(head);//Delete the nodes from the heapcout Deleting the linked list. endl;delete_linkedlist(head);system(Pause);return 0;}The output of the program will be 0 1 2 3 4.system(Pause);return 0;}CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 10Removig a specified node from a linked list: remove_node algorithmWe may also remove a specified node from a linked list. The following diagram shows a given linked list andthe same linked list after the second node (crossed in red color) is removed.Given linked listThe same linked list after the second node has been removed from the linked listWe observe that in order to remove a node from a linked list, we first need to find the node that is just beforeit in the linked list. The following program demonstrates the remove_node algorithm. The function will takethe head of a linked list and a node pointer pointing the node to be removed as arguments and it will removethe node pointed by the node pointer from the linked list. Of course this function will not remove a node ifany of the following conditions is true The head of the linked list argument is nullptr (that is the linked list is empty), or The node pointer argument is nullptr, or The node pointer is not found in the linked list.Moreover the function must pass the head pointer argument by reference because we need to modify thehead pointer if the node to be removed happens to be the first node.void remove_node(NodePtr head, const NodePtr n){if (head == nullptr || n == nullptr)//empty linked list or nullptr nreturn;else if (head == n){head = head-getLink();delete n;return;}else{NodePtr b = head;while (b != nullptr){if (b-getLink() == n) //found the node before n{b-setLink(n-getLink());delete n;return;}b = b-getLink();}}}CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 11int main(){//Create an empty linked listNodePtr head = nullptr;//Insert five nodes in the linked list using head_insert operationfor (int i = 0; i 5; i++){head_insert(head, i);}//Print the linked list. This will print 4,3,2,1,0cout Printing the linked list. endl;print_linkedlist(head);//Remove the node in the linked list whose data is 2int search_value = 2;NodePtr n = search_node(head, search_value);remove_node(head, n);//Print the linked list. This will print 4,3,1,0cout Printing the linked list. endl;print_linkedlist(head);//Remove the node in the linked list whose data is 6search_value = 6;n = search_node(head, search_value);remove_node(head, n);//Print the linked list. This will still print 4,3,1,0cout Printing the linked list. endl;print_linkedlist(head);//Delete the nodes from the heapcout Deleting the linked list. endl;delete_linkedlist(head);system(Pause);return 0;}We may also be interested to remove a node whose data is equal to a specified integer value. This can easilybe done by calling the search_node function in order to first find a node pointer pointing to the node to beremoved as follows.void remove_node(NodePtr head, const int value){NodePtr n = search_node(head, value);remove_node(head, n);}Removig all nodes satisfying a condition from a linked list: remove_allWe may also be interested to remove all nodes from a linked list whose data is equal to some specified integervalue. This can easily be done using a loop and the search_node and remove_node functions as follows.CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 12void remove_all(NodePtr head, const int value){NodePtr n;while (true){n = search_node(head, value);if (n == nullptr)break;remove_node(head, n);}}int main(){//Create an empty linked listNodePtr head = nullptr;//Insert ten nodes in the linked list using head_insert operationfor (int i = 0; i 10; i++){head_insert(head, i/3);}//Print the linked list. This will print 3,2,2,2,1,1,1,0,0,0cout Printing the linked list. endl;print_linkedlist(head);//Remove all the nodes whose data is 2remove_all(head, 2);//Print the linked list. This will print 3,1,1,1,0,0,0cout Printing the linked list. endl;print_linkedlist(head);//Delete the nodes from the heapcout Deleting the linked list. endl;delete_linkedlist(head);system(Pause);return 0;}Inserting nodes in a linked list: insert_before algorithmWe may also insert a new node before a specified node in a linked list. In this case, we first need to find thenode just before the specified node and then use insert_after function.In order to mimic the insert member function in STL containers, we will design this function with the followingconstraints If the linked list is empty and the specified node is nullptr then this function should do head_insert. If the linked list is empty and the specified node is not nullptr then the specified node cannot befound in the linked list and therefore an error message should be printed and this function shouldnot insert any new node. If the linked list is not empty and the specified node is nullptr then this function should dotail_insert. If the linked list is not empty and the first node in the linked list is equal to the specified node thenthis function should do head_insert.CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 13 If the linked list is not empty and the specified node is not nullptr but that it is not found in thelinked list then an error message should be printed and this function should not insert any newnode. Otherwise a node just before the specified node will be found and this function should insert afterit using the insert_after function.The following program demonstrates the insert_before function with a test main program designed to test allthe above six different cases.void insert_before(NodePtr head, const NodePtr n, const int value){//If the linked list is empty then insert only if n is nullptr tooif (head == nullptr){if (n == nullptr)head_insert(head, value);elsecout Insertion failed. Bad node argument. endl;}//If n is nullptr then tail_insertelse if (n == nullptr)tail_insert(head, value);//If head is equal to n then head_insertelse if (head == n)head_insert(head, value);//Find the node just before n and insert after itelse{NodePtr b = head;while (b != nullptr){if (b-getLink() == n)break;b = b-getLink();}if (b == nullptr)cout Insertion failed. Bad node argument. endl;elseinsert_after(b, value);}}int main(){srand(time(0));//Create an empty linked listNodePtr head = nullptr;NodePtr n = new Node(-3);//Insert a node with data 0 before a non-existing node. This does nothinginsert_before(head, n, 0);cout Printing the linked list. endl;print_linkedlist(head);//Prints empty linked list//Insert a node with data 6 before nullptr. This does head_insertinsert_before(head, nullptr, 6);cout Printing the linked list. endl;print_linkedlist(head); //Prints 6CMPT 135 – FIC 202101 Assignment 2 Supplementary Material Dr. Yonas T. Weldeselassie (Ph.D.) Page 14//Insert a node with data 3 before nullptr. This does tail_insertinsert_before(head, nullptr, 3);cout Printing the linked list. endl;print_linkedlist(head); //Prints 6, 3\”

添加老师微信回复‘’官网 辅导‘’获取专业老师帮助,或点击联系老师1对1在线指导