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