Lecture19ECE264Spring2012 - Rhea

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);

ECE264 LEC19 Shiyu Wang Mar 25

There are three ways to allocate memory 1. Static(know the size when writing the program) eg. int arr[100]; vector v[200];

2. know the size somewhere during execution eg. int length; scanf("%d",&length)

int *arr; arr=malloc(sizeof(int)*length);

3.grow and shrink based on run-time needs(dynamic structures) eg. linked list, binary tree

EXAMPLE

typedef struct destructure {

 /*data*/
 int value;
 vector vec;
 person *p;
 ...
 /*link*/
 struct destructire *next;(linked list)
 struct destructure *left;(binary tree)
 struct destructure *right;(binary tree)

}Node;

How to use linklist Node * n; n=malloc(size of(Node)) n-> value=27 n->next = NULL;

Expressive1 type def struct list node {

 int value;
 struct list node* next;

}Node;

Expressive2 Node*n=NULL; n=malloc(size of (Node)); n->value = 264; n -> next=NULL; Node *n2; n2=malloc(size of (Node)); n2->value = 2012; n2->next = n2;

Expressive 3 Node *n3 n3=n; printf("%d",n3->value); n3=n3->next; printf("%d",n3->value);

Structure Node *Node_construct(int U) {

 Node *n;
 n=malloc(sizeof(Node));
 n->value = v;
 n->next = NULL;
 return n;

}

Node *List_inserct(Node *t,int v) {

 Node *n = node_construct (v);
 n->next = t;
 return n;

}

Node *head = NULL; head=list_inserct(head,264); head=list_inserct(head,2012);