Lecture Fri 23Mar Peachanok Lertkajornkitti ECE 264
Linked List
-resizable -do not allow random access -insertion at any point
Example of linked list:
typedef struct int_node_t{ int value; struct int_node_t *next;
} IntNode;
IntNode *IntNode_create(int value) { IntNode *node = malloc(sizeof(IntNode)); node->value = value; node->next = NULL; return node; }
void IntNode_destroy(IntNode *node) { free(node); }
int IntNodeL_elementAt(IntNode *head, int index) { if (head == NULL) return NULL; while(index-- > 0){ head = head->next; } return head; } } IntNode *IntNodeL_insert(IntNode *head, int value) { IntNode *node = IntNode_create(value); node->next = head; return node; }
void IntNodeL_print(IntNode *head) { while(head != NUll){ printf("%d\n",head->value); head=head->next; } }
void IntNodeL_destroy(IntNode *head) { while(head != NULL) { IntNode *tmp = head; head = head->next; IntNode_destroy(tmp); } } IntNode *IntNodeL_insertBack(IntNode *head, int value) { IntNode *node = IntNode_create(value, NULL); if(head == NULL) return node; IntNode *pos = head; while(pos->next != NULL){ pos = pos->next; } pos->next = node; return head; } int main(int argc, char *argv[]) { int i; IntNode *head = NULL; for(i=0;i<100;i++) { head = IntNodeL_insert(head, i); }
IntNodeL_print(head); IntNodeL_destroy(head); return EXIT_SUCCESS; }
IntNode *IntNodeL_reverse(IntNode *head) { if(head == NULL) return NULL; IntNode *new_head = NULL; while (head != NULL) { IntNode *tmp = head; head = head->next; tmp->next = new_head; new_head = tmp; }
return new_head;
} ////////******
Lecture notes 19_Mar 22_Kailu Song
1. Three ways to allocate memory: a. static -> know the size when writing the program e.g. int arr[00]; int arr[200]; b. know the size somewhere during execution. e.g. int length; scanf(“%d”, &length); arr = malloc(sizeof(int)*length); c. grow and shrink based on run-time needs(dynamic structure) e.g. link list
binary tree
2. Example Code Typeof struct dstructure { /*data*/ int value; Vector vec; Person *P; /*LINK*/ struct dsturcture *next;(linked list) struct dsturcture *left; struct dsturcture *right;(binary tree) }Node; 3. How to use linked list Node *n; n = malloc(sizeof(Node)); n->value = 27; n->next = NULL; typeof struct listnode(define linked list) { int value; struct listnode * next; }Node; Node *n = NULL; n = malloc(sizeof(Node)); n->value = 264; n->next = NULL; Node *n2; n2= malloc(sizeof(Node)); n2->value = 264; n2->next = NULL; n->next=n2;
Node*n3; n3 = n;(modify stack for n3) printf(“%d”,n3->value);(=264) n3 = n3->next;(change stack memory for n3) printf(“%d”,n3->value);(=2012) Node * Node_construct (int V) { n = malloc(sizeof(Node)); n->value = v; n->next = NULL; return n; } Node *List_insert(Node *t, int V) { Node *n; n = Node_construct(v); n->next = t; return n; } Node *head = NULL; head = List_insert(head,264); head=List_insert(head,2012);
