New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Data & File Structures

by: Aleen Crona MD

Data & File Structures CS 246

Aleen Crona MD
GPA 3.91

Lila Ghemri

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Lila Ghemri
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 62 page Class Notes was uploaded by Aleen Crona MD on Wednesday October 21, 2015. The Class Notes belongs to CS 246 at Texas Southern University taught by Lila Ghemri in Fall. Since its upload, it has received 23 views. For similar materials see /class/226264/cs-246-texas-southern-university in ComputerScienence at Texas Southern University.


Reviews for Data & File Structures


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15
Structure s A Structure is a data type suitable for grouping data elements together All of the elements in the structure are logically related The elements or fields which make up the structure use the five basic data types int char oat double bool We want to de ne a point in a plan that is two coordinates define each point X and y The following code fragment shows how to create a structure template to define the Point structure struct Point int X39 int y39 This declares a NEW data type called Point This Point structure consists of two basic data elements of type integer one called X and one called y Definition is terminated by a semicolon because the definition is a statement The structure tag Point identifies or is the name this particular data structure We want to define a data type called date A date is defined by a month a day and a year so we would need at least 3 variables to define that structure struct date int month int day int year In essence structure de ne a new data type keyword like int and char and can be used to create variables A structure definition is a de nition to the compiler It does not create any storage space and cannot be used as a variable General form of a structure definition is struct tag type variableinamel type variableinameZ type variableinamei structureivariables the reserved word struct is used to declare a structure tag is the name of the structure type is an of the 5 basic types or a user defined type variablename is the name of the element that will hold a given value it is also called a member variable Structure definition forms a template that is used to create variables of the structure type At this point in the code no variable has actually been declared Only the form of the data has been defined To declare a variable of type date we use the following form struct date todaysidate This declaration defines a variable called todaysidate to be of the same data type as that of the newly defined data type struct date If a structure definition does not contain a structure tag variables of the structure type may be declared only in the structure definition not in a separate declaration For example struct int month int day int year todaysidate We want to define a structure person that represents a person with their name their age and their gender We want to create two variables Jack and Jill of type person struct person char name39 int age39 char gender39 struct person Jack Jill Initializing Structures Structure variables can be initialized using initialized lists as with arrays The format to initialize a structure variable is in the date example struct date todaysdate 04 08 2002 This declaration creates a variable of type date and initializes the members month day and year respectively to 04 08 and 2002 If there are fewer initializations in the list than members of the structure the remaining members are automatically initialized to 0 or NULL if the member is a pointer Jack Jack 7 M 39 include ltiostreamgt using namespace std39 struct person char name39 int age39 char gender39 This declares a structure The structure tag is person The structure has 3 data elements or members I a string name I an integer age I and a character gender To initialize a variable Jack of type struct we use int main struct person Jack quotJackquot 7 M 39 return 039 Accessing and referencing members of Structures Two operators are used to access members of structure operator the dot operator The structure member operator accesses a structure member Via the structure variable name For example to print the member name of the variable Jack we use cout ltlt Jackname include ltiostreamgt using namespace std struct person char name int age char gender int main struct person Jack quotJackquot 7 M struct person Jill Jill gender F Jillname quotJillquot coutltlt Jackname ltltJillname return 0 Sample Program Output J a c k J i l l Program to illustrate a structure include ltiostreamgt using namespace std struct date global definition of type date int month int day int year int main struct date today todaymonth 8 todayday 27 todayyear 2007 coutltlt Today s date is ltlt todaymonth ltlt ltlt todayday ltlt ltlt todayyear return 0 Sample Output Program Today s date is 08272007 Pointers to Structures include ltiostreamgt using namespace std struct person char name nuagm char gender int main struct person Jack quotJackquot 7 M struct person Jill HumptyDumpty J Lgender F Jillname quotJillquot mnnltltJad nmneltltmn ltltJ anneltltendh struct person HumptyPtr HumptyPtr ampHu1nptyDumpty HumptyDumptyname quotHumpty Dumptyquot mnnltltIhnnpg pgtnmneltltendh retum 0 Sample Program Output Jack Jill Humpty Dumpty The structure pointer operator gt accesses a structure member Via a pointer to the variable struct person HumptyDumpty 6 Line A struct person HumptyPtr 6 Line B HumptyPtr ampHumptyDumpty 6 Line C HumptyDumptyname Humpty Dumpty coutltlt HumptyPtrgtnameltltendl Line A declares a variable HumptyDumpty of type person Line B declares a pointer named HumptyPtr that points to a variable of type person Line C assigns the address of the variable HumptyDumpty to the pointer variable HumptyPtr Operations on Structures The only valid operations that may be performed on structures are I Assigning structure variables to structure variables of the same type I Taking the address amp of a structure variable I Accessing the members of a structure variable I Using the sizeof operator to determine the size of a structure variable include ltiostreamgt using namespace std void mainvoid struct int a int b x y Xa 10 YZX coutltlt ya return 0 Sample Program Output 10 Arrays of Structures The most common usage of structures is in arrays of structures To declare an array of structures I First define the structure I Then declare an array variable of that structure type For example struct person personlistlOO39 This declaration creates 100 sets of variables that are organized as defined in the struct person To access a specific structure indeX the structure name For example to print age of structure at the position 3 one should write coutltlt personlist2 age39 If we use coutltlt personlist239 it only prints the first member of the structcompiler dependent Using Structures with Functions Structures may be passed to functions by I Passing individual structure members I Passing an entire structure I Passing a pointer to a structure When an element or a member of a structure variable is passed to a function39 it is actually the value of the element that is passed Therefore it is the same as passing a simple variable it is a callby value When a structure is used as an argument to a function the entire structure is passed using the standard callbyvalue method This means that any changes made to the contents of the structure inside the function to which it is passed do not affect the structure used as an argument When using a structure as a parameter the type of the argument must match the type of the parameter include ltiostreamgt using namespace std int main struct int a b char ch arg arga 1000 f1arg void fl struct int X y char ch param coutltlt paramX This program could not compile Most compilers do not allow structures to be passed to functions by callbyvalue One way to solve this issue is to declare the structure as a global variable include ltiostreamgt using namespace std struct A int a b char ch void fl A int main A arg arga 1000 f1arg return 0 void fl A param coutltlt parama This compiles correctly Output Sample Program 10 00 The major drawback in passing structures to functions callbyvalue is the overhead needed to put all the structure elements into the stack push and remove all of them from itpull Run time performance degrades to unacceptable levels if several structure variables are used in a function call The solution to this problem is to pass only a pointer to the structure to a function Structure Pointers The way to define a pointer to a structure is struct tag structurevariable For example struct person HumptyDumpty HumptyPtr This declaration creates a pointer called HumptyPtr that points to or holds the address of a structure variable The statement HumptyPtr ampHumptyDumpty assigns the address of the variable HumptyDumpty to the pointer HumptyPtr Using Structure Pointers A primary use for structure pointers is to generate a call by reference to functions When a pointer to a structure is passed to a function only the address of the structure variable is pushed and popped on the stack This makes for very fast function calls By passing a pointer we can modify the contents of the actual elements of the structure used in the call Example include ltiostreamgt using namespace std struct addr char name char street char city char state unsigned long int zip address struct addr addrPtr void deletefstruct addr address int main struct addr Jackaddress quotJackquotquot234 UpHillquotquotH0ustonquot quotTexasquot 90876 addrPtr ampJackaddress coutlt addrPtrgtname deletefaddrPtr c0utltlt quotName is now quotltlt addrPtrgtname retum 0 void deletefstruct addr Address Addressgtname 0 Program Sample Output Name is Jack Name is now null Typedef The keyword typedef provides a mechanism for creating synonyms or aliases for preViously defined data types These data types can be the language defined or user defined For example typedef oat balance This statement tells the compiler to recognize balance as another name for oat The new name is in addition to not a replacement for the existing type name Next we can create a oat variable using balance balance overdue Using typedef can make the code easier to read Names for structure types are often defined with typedef to create synonyms For example typedef struct char face char suit Card This creates the structure type Card without the need for a separate typedef statement High Performance Card Shuttling and Dealing Simulation The program represents the deck of cards as an array of structures The program uses highperformance card shuf ing and dealing program include ltstdiohgt include ltstd1ibhgt include lttimehgt typedef struct card char face char suit Card void fillDeckCard char char void shuf eCard void dealCard mainO Card deck52 char face quotAcequot quotDeucequot quotThreequot quotFourquot quotFivequot quotSixquot quotSevenquot quotEightquot quotNinequot quotTenquot quotJackquot quotQueenquot quotKingquot char suit quotHeartsquot quotDiamondsquot quotClubsquot quotSpadesquot srandtimeNULL fillDeckdeck face suit shuf edeck dealdeck retum 0 void fillDeckCard wDeck char wFace char wSuit int 1 for i 0 ilt 52 i wDeckiface wFace i 13 wDeckisuit wSuiti13 void shuf eCard wDeck int 1 J Card temp for i0 ilt52 i j rand 52 temp wDecki wDecki wDeckU wDeckU temp void deal Card wDeck mt 1 for i0 ilt52 i printfquot55 of 85 nquot wDeckiface wDeckisuit CEvrand39 lusPr snan jggej 3 Trees and Search Strategies and Algorithms Reference Dr Franz J Kurfess Computer Scien epartment Cal Poly Basic Search Strategies depthfirst breadthfirst exercise apply depthfirst to finding a path from this buildin39 to our favorite feedin39 station McDonalds Jason Deli Pizza Hut is this task sufficiently specified IS success guaranteed how long will it take could you remember the path how good is the solution Motivation search strategies are important methods for many approaches to problemsolving the use of searon requires an abstract formulation of the problem and the available steps to construct solutions search algorithms are the basis for many optimization and planning methods Objectives formulate appropriate problems as search tasks states initial state goal state successor functions operators cost know the fundamental search strategies and algorithms breadthfirst depthfirst evaluate the suitability of a search strategy for a problem completeness time amp space complexity optimality Problems solution path from the initial state to a goal state search cost time and memory required to calculate a solution path cost determines the expenses of the agent for executing the actions in a path sum of the costs of the individual actions in a path total cost sum of search cost and path cost overall cost for finding a solution Traveling Salesperson states locations cities illegal states each city may be visited only once visited cities must be kept as state information initial state starting point no cities visited successor function operators mv frm n lin nhr n goal test all locations visited agent at the initial location path cost distance between locations Searching for Solutions traversal of the search space from the initial state to a goal state leal se ruence of actions as defined b successor function operators general procedure check for goal state expand the current state determine the set of reachable states return failure if the set is empty select one from the set of reachable states move to the selected state a search tree is generated Search Terminology search tree generated as the search space is traversed the search space itself is not necessarily a tree frequently it is a graph the tree specifies possible paths through the search spac expansion of nodes as states are explored the corresponding nodes are expanded by applying the successor function this generates a new set of child nodes the fringe frontier is the set of nodes not yet visited newly generated nodes are added to the fringe search strategy determines the selection of the next node to be expanded can be achieved by omering Lhc nodes in the ringe eg queue FIFO stack LIFO best node wrt some measure cost Example Graph Search the graph describes the search state space each node in the graph represents one state in the search Space eg a city to be visited in a routing or touring problem this graph has additional information names and properties for tne States eg S 3 links between nodes specified by the successor function brooerties for links distance cost name l Breadth First Search Graph and Tree the tree is generated by traversing the graph the same node in the graph may appear repeatedly in the tree the arrangement of the tree depends on the traversal strategy search method the initial state becomes the root node of the tree in the fully expanded tree the goal states are the leaf nodes A Search General Search Algorithm generate the nooe rrom the Inltlal state OT the proolem repeat return failure if there nodes inth ringe examine the current node if it s a goal return the solution expand the current node and add the new nodes to the fringe General Search Algorithm function GENERAL SEARCHproblem QUEUING FN returns solution nodes MAKE QUEUE MAKE NODE INITIAL STATE problem loop do if nodes is empty then return failure node REMOVE FRONTnodes if GOAL TESTproblem applied to STATEnode succeeds then return node nodes QUEUING FNnodes EXPANDnode OPERATORSproblem Evaluation Criteria completeness if there is a solution will it be found time complexity how long does it take to find the solution does not include the time to perform actions space complexity memory required for the search optimality will the best solution be found main factors for com lexit considerations branching factor b depth dof the shallowest goal node maximum path length m Search Cost the search cost indicates how expensive it is to generate a solution time complexity eg number of nodes generated is usually the main factor sometimes space complexity memory usage is considered as well path cost indicates how expensive it is to execute the solution found in the search distinct from the search cost but often related total cost is the sum of search and path 1 BreadthFirst all the nodes reachable from e Vurrent node are explored first achieved the I IllethOd appending newly generated nodes at the end of the search ueue lution BreadthFirst Snapshot 1 Initial Visited 4 Fringe Current Vi51ble Goal BreadthFirst Snapshot 2 Initial Li Visited 1 Fringe Current Vi51ble 9 Goal 11 16 17 18 19 2O 21 22 23 24 25 26 27 28 29 30 31 BreadthFirst Snapshot 3 ilgw Fringe 45 67 Initial Visited 4 Fringe Current Vi51ble Goal if a BreadthFirst Snapshot 4 Fringe 567 89 Initial 3 Visited 4 Fringe Current Vi51ble Goal if a BreadthFirst Snapshot 5 Initial Q Visited Q Fringe 1 Current Vi51ble Goal Ah 2 f OO Fringe 6789 BreadthFirst Snapshot 6 Fringe 7891011 Initial Visited Fringe Current Vi51ble Goal 0 O f OO BreadthFirst Snapshot 7 Fringe 8910111213 Initial Q Visited Q Fringe Current j Vi51ble Goal O BreadthFirst Snapshot 8 Initial Visited Fringe Current Vi51ble Goal 0 O f OO BreadthFirst Snapshot 9 Initial Visited Fringe Current Vi51ble Goal 0000 BreadthFirst Snapshot 10 Initial Visited Fringe Current Vi51ble Goal 0000 BreadthFirst Snapshot 11 Initial Visited Fringe Current Vi51ble Goal 0000 BreadthFirst Snapshot 12 Initial Visited Fringe Current Vi51ble Goal 0000 Note The goal node is Visible here but we can not perform the goal test yet BreadthFirst Snapshot 13 Initial Visited Fringe Current Vi51ble Goal 0000 BreadthFirst Snapshot 14 Initial Visited Fringe Current Vi51ble Goal QOOOOO x l d dd 3 L T A p z If f i s39f 16 17 18 19 20 21 22 BreadthFirst Snapshot 15 Initial Visited Fringe Current Vi51ble Goal QOOOOO i It i g i I 3f 39 f d ddde d 16 17 18 19 20 21 22 Fringe 151617 81920212223242526272829 3031 16 17 BreadthFirst Snapshot 16 18 19 Initial Visited Fringe Current Vi51ble Goal QOOOOO Te 17 BreadthFirst Snapshot 17 t g i 1 4 i y re 1 f J 18 19 Initial Visited Fringe Current Vi51ble Goal QOOOOO BreadthFirst Snapshot 18 Initial Visited Fringe Current Vi51ble Goal QOOOOO BreadthFirst Snapshot 19 Initial Visited Fringe Current Vi51ble Goal 0000 u t quota a r I I u I 1 x x A n g 39 J v I i xiii f k 1quot Run a a a 2 x t E 8 x xx k Na K x GOO 30 31 24 25 28 27 28 29 f i j j if 39 a i quot i x t v I x ftquot x q JU O OO 7 BreadthFirst Snapshot 20 Vi51ble Goal Initial Visited O Fringe Current 0 O in a x 2 x a 8 x xx k Na K x O O O 30 31 wquot t i OO 24 25 28 27 28 29 BreadthFirst Snapshot 21 Initial Visited Fringe Current Vi51ble Goal 00000 I t mi a r I Pay x A n g 39 J v in z rquot 39K 3 RR 3 x t v x x A k E S RN a x i 5quot X OOQQOO CO 0 31 21 22 23 24 25 28 27 28 29 3 BreadthFirst Snapshot 22 gr TJO 24 ti 3 x u u 1 w 27 a Vx quot 3928 29 V 8 X K xix K i w bbb 30 31 Initial Visited Fringe Current Vi51ble Goal 0000 BreadthFirst Snapshot 23 i f x i j I I 4quot 24 OO 3 x u u 1 w 27 a Vx quot 3928 29 a X X K xix K V 4 K Kb 3 30 31 Initial Visited Fringe Current Vi51ble Goal 0000 BreadthFirst Snapshot 24 mm Visited Fringe Current Vis1ble Goal 0000 Note The goal test is positive for this node and a solution is found in 24 steps De thFirst lution d 5e nodes achieved the I IllethOd appending newly generated nodes at the beginning of the search ueue utilizes a LastIn FirstOut LIFO queue or stack DepthFirst Snapshot QOQQOO t Fringe Curren Vi51b1 Goal 3 Um 11 MV Fringe 3 DepthFirst vs BreadthFirst depthfirst goes off into one branch until it reaches a leaf node not good if the voal is on another branch neither complete nor optimal uses much less space than breadthfirst much fewer visited nodes to keep track of smallerfringe breadthfirst is more careful by checking all alternatives complete and optimal very memoryintensive


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.