DOC PREVIEW
IUPUI CSCI 23000 - Data Structure Review

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Data Structure ReviewPointer Review (1)Pointer Review (2)Pointer Review (3)Pointer Review (4)Dynamic Storage QuestionDynamic Storage AnswerLinked List InsertionLinked List Insertion (Answer)Linked List DeletionSlide 11Creating a linked list of wordsCreating a linked list of words (Answer)Create a two node listCreate a two node list (Answer)AcknowledgementsDale RobertsDepartment of Computer and Information Science,School of Science, IUPUICSCI 230Dale Roberts, LecturerDale Roberts, [email protected]@cs.iupui.eduData Structure ReviewData Structure ReviewDale RobertsPointer Review Pointer Review (1)(1) int i, *pi;ipi10002000? ?pi = &i;ipi10002000? 1000*pii = 10 or *pi = 10ipi1000200010 1000*piDale RobertsPointer Review Pointer Review (2)(2)typedef struct list_node *list_pointer;typedef struct list_node { int data; list_pointer link; }list_pointer ptr = NULL;ptr1000NULLptr = malloc(sizeof(list_node));ptr100020002000 *ptrptr->data(*ptr).datadata linkDale RobertsPointer Review Pointer Review (3)(3)void delete(list_pointer *ptr, list_pointer trail, list_pointer node)ptr: a pointer point to a pointer point to a list node10002000ptr200030003000*ptr (*ptr)->linktrail (node): a pointer point to a list nodetrail100030003000 *traildata linktrail->link(*trail).linkDale RobertsPointer Review Pointer Review (4)(4)element delete(stack_pointer *top)topdelete(&st) vs. delete(st)200 300300400...200300topst 200400300300sttop400Does not change.Dale RobertsDynamic Storage QuestionDynamic Storage QuestionQuestion: Dynamically allocate an integer, and then Question: Dynamically allocate an integer, and then return the memory back to the operating system.return the memory back to the operating system.Dale RobertsDynamic Storage AnswerDynamic Storage AnswerAnswer:Answer:int *pi;int *pi;pi = (int *) malloc(sizeof(int));pi = (int *) malloc(sizeof(int));free(pi);free(pi);request memoryreturn memoryDale Roberts bat  cat  sat  vat NULLLinked List InsertionLinked List InsertionQuestion: Given the following sorted linked list, Question: Given the following sorted linked list, draw the diagram for inserting the word “mat” draw the diagram for inserting the word “mat” into the list.into the list.Dale Roberts bat  cat  sat  vat NULL mat Linked List Insertion (Answer)Linked List Insertion (Answer)Answer: Scan the list for where to insert mat (linear Answer: Scan the list for where to insert mat (linear search). Make mat point to where cat points, and search). Make mat point to where cat points, and then make cat point to mat.then make cat point to mat.Dale RobertsLinked List DeletionLinked List DeletionQuestion: Given the following list, delete the Question: Given the following list, delete the word mat.word mat. bat  cat  sat  vat NULL mat Dale Roberts bat  cat  sat  vat NULL mat danglingreferenceLinked List DeletionLinked List DeletionAnswer: Make cat point to where mat points, Answer: Make cat point to where mat points, then free mat. Make sure to not lose your only then free mat. Make sure to not lose your only reference to mat when you change cat’s link.reference to mat when you change cat’s link.Dale RobertsCreating a linked list of wordsCreating a linked list of wordsQuestion: Create a linked list with one node with the value Question: Create a linked list with one node with the value of “bat”.of “bat”.DefinitionDefinitiontypedef struct list_node, *list_pointer;typedef struct list_node, *list_pointer;typedef struct list_node {typedef struct list_node {char data [4];char data [4];list_pointer link;list_pointer link;};};CreationCreationlist_pointer ptr =NULL; list_pointer ptr =NULL; TestingTesting#define IS_EMPTY(ptr) (!(ptr))#define IS_EMPTY(ptr) (!(ptr))AllocationAllocationptr=(list_pointer) malloc (sizeof(list_node));ptr=(list_pointer) malloc (sizeof(list_node));Dale Roberts b a t \0 NULL address offirst nodeptr dataptr linkptrReminder: e -> name  (*e).namestrcpy(ptr -> data, “bat”);ptr -> link = NULL;Creating a linked list of words (Answer)Creating a linked list of words (Answer)Dale RobertsCreate a two node listCreate a two node listtypedef struct list_node *list_pointer;typedef struct list_node *list_pointer;typedef struct list_node {typedef struct list_node { int data; int data; list_pointer link; list_pointer link; }; };list_pointer ptr =NULLlist_pointer ptr =NULL 10  20 NULL ptrDale RobertsCreate a two node list (Answer)Create a two node list (Answer)list_pointer create2( )list_pointer create2( ){{/* create a linked list with two nodes *//* create a linked list with two nodes */ list_pointer first, second; list_pointer first, second; first = (list_pointer) malloc(sizeof(list_node)); first = (list_pointer) malloc(sizeof(list_node)); second = ( list_pointer) malloc(sizeof(list_node)); second = ( list_pointer) malloc(sizeof(list_node)); second -> link = NULL; second -> link = NULL; second -> data = 20; second -> data = 20; first -> data = 10; first -> data = 10; first ->link = second; first ->link = second; return first; return first;}} 10  20 NULL ptrDale RobertsAcknowledgementsAcknowledgementsSome code is from Horowitz, Sahni, and Anderson-Freed, Some code is from Horowitz, Sahni, and Anderson-Freed, Fundamentals of Fundamentals of Data Structures in C.Data Structures in C.Some slides were originally developed by Chen, Hsin-His.Some slides were originally developed by Chen,


View Full Document

IUPUI CSCI 23000 - Data Structure Review

Download Data Structure Review
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Data Structure Review and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Data Structure Review 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?