Linked List Operations

Presentation on theme: "Linked List Operations"— Presentation transcript:

1 Linked List Operations
Dr. David Tsai 2010/4

2 struct Node { int data; struct Node
struct Node { int data; struct Node *next; }; typedef struct Node LNode; typedef LNode *List; List first = NULL; extern void creatList(int len, int *array); extern int isListEmpty(); extern void printList(); extern List searchNode(int d); extern int deleteNode(List ptr); extern void insertNode(List ptr, int d); 修改自教科書：資料結構理論與實務以C語言實作/陳會安

3 typedef struct Node LNode; typedef LNode *List; List first = NULL;
int data; struct Node *next; }; typedef struct Node LNode; typedef LNode *List; List first = NULL; Typedef struct Node { }Lnode; 修改自教科書：資料結構理論與實務以C語言實作/陳會安

4 void createList (int len, int*array) { List newnode;
for (int i = 0; i < len; i++) { newnode = (List) malloc (sizeof(LNode)); newnode->data = array[i]; newnode->next = first; first = newnode; } 修改自教科書：資料結構理論與實務以C語言實作/陳會安

5 if (first == NULL) return 1; else return 0; }
int isListEmpty () { if (first == NULL) return 1; else return 0; } void printList () { List current = first; while (current ! = NULL) { printf ([％d] , current->data); current = current->next; } printf (﹨n ); 修改自教科書：資料結構理論與實務以C語言實作/陳會安

6 if (first == NULL) return 1; else return 0; } void printList () {
int isListEmpty () { if (first == NULL) return 1; else return 0; } void printList () { if (isListEmpty()) { printf(“The Linked List is Empty\n”); return 0; } List current = first; while (current ! = NULL) { printf ([％d] , current->data); current = current->next; printf (﹨n ); 修改自教科書：資料結構理論與實務以C語言實作/陳會安

7 List searchNode (int d) { if (!isListEmpty()) { List current = first;
while (current ! = NULL) { if (current->data == d) return current; current = current->next; } return NULL; else { printf(“The Linked List is Empty\n”); return 0; 修改自教科書：資料結構理論與實務以C語言實作/陳會安

8 int deleteNode (List ptr) { List current = first; int value = ptr->data; if (isListEmpty() ) { return -1; } if (ptr==first∥ptr==NULL) { first = first->next; else { while (current->next!=ptr){ current = current->next; if (ptr->next == NULL){ current->next = NULL; current->next = ptr->next; free (ptr); return value; 修改自教科書：資料結構理論與實務以C語言實作/陳會安

9 void insertNode (List ptr, int d) { List newnode;
newnode = (List) malloc (sizeof(LNode)); newnode->data = d; newnode->next = NULL; if (ptr == NULL) { newnode->next = first; first = newnode; } else { if (ptr->next == NULL) { ptr->next = newnode; newnode->next=ptr->next; { newnode->next=ptr->next; ptr->next = newnode; } 修改自教科書：資料結構理論與實務以C語言實作/陳會安

10 ptr = searchNode(temp); if ( ptr != NULL ) insertNode(ptr, temp);
int main() { int temp; int data[6]={ 1, 2, 3, 4, 5, 6 }; List ptr; createList(6, data); printList(); temp = 0; insertNode(NULL, 50); while ( temp != -1 ) { scanf("%d", &temp); if ( temp != -1 ) { ptr = searchNode(temp); if ( ptr != NULL ) insertNode(ptr, temp); printf("插入後串列: "); } system("PAUSE"); return 0; List searchNode (int d) { if (!isListEmpty()) { List current = first; while (current ! = NULL) { if (current->data == d) return current; current = current->next; } return NULL; } else { printf(“The Linked List is Empty\n”); return 0; } void insertNode (List ptr, int d) { List newnode; newnode = (List) malloc (sizeof(LNode)); newnode->data = d; if (ptr == NULL) { newnode->next = first; first = newnode; } else { if (ptr->next == NULL) { ptr->next = newnode; newnode->next = NULL; } newnode->next=ptr->next; ptr->next = newnode; } } }

11 完成分別在(1)串列首之前、(2)串列之間、(3)串列之後插入節點
ptr = ptr ptr first 50 6 5 3 2 newnode 4 1 newnode newnode 完成分別在(1)串列首之前、(2)串列之間、(3)串列之後插入節點