Electrical Engineering - Chapter 16: Data Structures and Recursion

Chapter 16 – Data Structures and RecursionData StructuresBuilt-inArraystructUser developedlinked liststackqueuetreeLesson 16.1Programmer-defined Linked List ClassData members (could be different types) stored in (usually) contiguous block of memoryOne of the data members is a pointer variableAddress stored points to the next objectData member that has address creates link between objectsEach object referred to as a nodeLesson 16.1Linked List RepresentationLesson 16.1Head node Object 2 Object 3 Object 4Objects in linked listlinkPointer variable valueFact that addresspoints to next object Actions on Linked ListMust go node to node from head nodeCan delete node by making address that points to one to be deleted to next objectCan insert node by changing address stored in pointer variable for node preceding location of insertionCan move node from one location to anotherMust keep track of current node and head nodeLesson 16.1Linked List ClassesUse two classes to create linked listNode classHolds only the dataAll data members public because no function membersSecond used to manipulate nodesOne variable holds address of first object in listAnother variable holds current node addressLesson 16.1Node ClassGeneral form:Lesson 16.1class Node{ public: type member1; type member2; Node* next_node;};Class nameData types(not necessarily all the same)Identifiers representingnode dataName for storingaddress of next node in listSecond ClassUsed to manipulate the nodesData only pointer variables used to hold addressesLesson 16.1class Llist{ private: Node* head; Node* current; public: void make_list ( ); void show_list ( );};Address of nodebeing manipulatedAddress offirst objectStackData structure created using linked list modelWith stack can perform only two fundamental operationsPushInsert node immediately after the headPopRetrieve and delete node immediately after headOnly work with nodes at topLesson 16.2Stack ClassesTwo classes create stackOne class holds only dataSame form as linked listone member must be pointer variableSecond class used to manipulate nodesData only pointer variables used to hold addresses of nodesNodes of interest for stack are head and tailFunction members initialize, push and pop itemsLesson 16.2Stack ClassLesson 16.2class Stack{ private: Node* head; Node* tail; public: Stack ( ); void push (int); int pop ( );};Address of head node and last nodeStack ClassesCreate empty stack by initializing a head and tail nodeAllow finding top and bottom of stackShould not pop from an empty stackLIFOLast In First OutLast node pushed is first node popped offLesson 16.2Queue ClassCan create with linked list formMust have a head and tail nodeFIFOFirst node inserted into queue is first node removedNodes are inserted at tail of queue and removed from head of queueLesson 16.3Queue ClassLesson 16.3class Queue{ private: Node* head; Node* tail; public: Queue ( ); void insert (int); int remov ( );};Class Node{ public: type member; Node* next_node;};Types of QueuesDequeue - "double-ended queue"Nodes can be inserted at either end and removed from either endOutput restricted dequeueInsertion allowed at both ends but removal allowed at only one endInput restricted dequeueRemoval allowed at both ends, insertion allowed at only one endPriority queuePriority for each node – highest priority processed firstLesson 16.3Binary TreeTree is particular type of graphBinary tree is particular type of treeGraph is data structure that includes nodeseach node can have more than one pointerLesson 16.4Linked List GraphGraph TerminologyNodes can also be called vertices or pointsConnections between nodes called edges or arcsTwo nodes considered adjacent of neighbors if edge connects themPath between one node and another indicated by list of connect nodes between twoSimple path is path with no repeated nodesLesson 16.4GraphsWeighted graphAssign length or cost of each edgeTreegraph with characteristic that there is only one path between any two nodesRooted treeTree with one node specified to be rootRoot traditionally shown at top of diagramBinary treeTree in which no node has more than two childrenLesson 16.4Tree ClassSimilar to linked list and stack classesTwo classesOne class holds content of nodesSecond class manipulates the nodesLesson 16.4class Tree_node{ public: type member; Tree_node* left_child; Tree_node* right_child;};RecursionWithin function body there is call to function with identical name and signatureBasic action which is repeated until it reaches the final iteration of the basic actionLesson 16.5SummaryCreate a linked listCreate a stackCreate a queueCreate a binary treeIdentify recursive functionsLearned how to: