- #include <stdio.h>
- #include <stdlib.h>
- #ifdef DEBUG
- #define dbg_printf(fmt, args...) printf("[%s: %d]"fmt, __FUNCTION__, __LINE__, ##args);
- #else
- #define dbg_printf(fmt, args...)
- #endif
- struct Node {
- int data;
- struct Node *next;
- };
- typedef struct Node node;
- typedef struct Node *pNode;
- void pushNode(pNode *, int);
- void appendNode(pNode *, int);
- void deleteNode(pNode *, int);
- void displayList(pNode);
- void sortList(pNode *);
- void reverseList(pNode *);
- int main()
- {
- pNode head = NULL;
- int index, item, data;
- while (1)
- {
- index = 1;
- printf("please select a item: \\n");
- printf("\\t%d: push node\\n", index++);
- printf("\\t%d: append node\\n", index++);
- printf("\\t%d: delete\\n", index++);
- printf("\\t%d: display\\n", index++);
- printf("\\t%d: sort\\n", index++);
- printf("\\t%d: reverse\\n", index++);
- scanf("%d", &item);
- switch (item)
- {
- case 1:
- printf("please input a number: ");
- scanf("%d", &data);
- pushNode(&head, data);
- displayList(head);
- break;
- case 2:
- printf("please input a number: ");
- scanf("%d", &data);
- appendNode(&head, data);
- displayList(head);
- break;
- case 3:
- printf("please input a number: ");
- scanf("%d", &data);
- deleteNode(&head, data);
- displayList(head);
- break;
- case 4:
- break;
- case 5:
- sortList(&head);
- displayList(head);
- break;
- case 6:
- reverseList(&head);
- displayList(head);
- default:
- break;
- }
- }
- return 0;
- }
- void pushNode(pNode *head, int data)
- {
- dbg_printf("head location: %p\\n", *head);
- pNode pCurrent = (pNode)malloc(sizeof(node));
- pCurrent->data = data;
- pCurrent->next = *head;
- *head = pCurrent;
- return;
- }
- void appendNode(pNode *head, int data)
- {
- pNode pTemp, pCurrent;
- pCurrent = (pNode)malloc(sizeof(node));
- pCurrent->data = data;
- if (*head == NULL)
- {
- *head = pCurrent;
- pCurrent->next = NULL;
- return;
- }
- else
- {
- pTemp = *head;
- while (pTemp->next != NULL)
- pTemp = pTemp->next;
- pTemp->next = pCurrent;
- pCurrent->next = NULL;
- }
- }
- void deleteNode(pNode *head, int data)
- {
- dbg_printf("head location: %p\\n", *head);
- pNode pCurrent, pTemp;
- pCurrent = *head;
- if (pCurrent == NULL)
- return;
- //first is the location
- if (pCurrent->data == data)
- {
- pTemp = pCurrent;
- *head = pCurrent->next;
- free(pTemp);
- }
- else
- {
- while (pCurrent->next && pCurrent->next->data != data)
- pCurrent = pCurrent->next;
- //found
- if (pCurrent->next)
- {
- pTemp = pCurrent->next;
- pCurrent->next = pCurrent->next->next;
- free(pTemp);
- }
- }
- return;
- }
- void displayList(pNode head)
- {
- dbg_printf("head location: %p\\n", head);
- pNode pCurrent = head;
- printf("head------>");
- while (pCurrent != NULL)
- {
- printf("%d------>", pCurrent->data);
- pCurrent = pCurrent->next;
- }
- printf("NULL\\n");
- return;
- }
- //straight insertion sort
- void sortList(pNode *head)
- {
- dbg_printf("head location: %p\\n", *head);
- if (*head == NULL || (*head)->next == NULL)
- return;
- pNode pCurrent, pSearch, pTemp;
- //pCurrent loop from head->next
- pCurrent = (*head)->next;
- //pSearch form *head
- pSearch = *head;
- pSearch->next = NULL;
- //head->a->b->c->d->NULL
- //head->a
- // b->c->d->NULL
- while (pCurrent != NULL)
- {
- dbg_printf("head location: %p\\n", *head);
- pTemp = pCurrent->next;
- *head = pSearch;
- if (pSearch->data > pCurrent->data)
- {
- pCurrent->next = pSearch;
- *head = pCurrent;
- }
- else
- {
- //find the location to insert;
- while (pSearch->next != NULL && pSearch->next->data < pCurrent->data)
- pSearch = pSearch->next;
- pCurrent->next = pSearch->next;
- pSearch->next = pCurrent;
- /*
- if (pSearch->next == NULL)
- {
- pCurrent->next = NULL;
- pSearch->next = pCurrent;
- }
- else
- {
- pCurrent->next = pSearch->next;
- pSearch->next = pCurrent;
- }
- */
- }
- pSearch = *head;
- pCurrent = pTemp;
- }
- dbg_printf("head location: %p\\n", *head);
- return;
- }
- void reverseList(pNode *head)
- {
- dbg_printf("head location: %p\\n", *head);
- if (*head == NULL || (*head)->next == NULL)
- return;
- pNode p1, p2;
- p1 = *head;
- p2 = p1->next;
- //head->a->b->c->d->NULL
- while (p2)
- {
- p1->next = p2->next;
- p2->next = *head;
- *head = p2;
- p2 = p1->next;
- }
- dbg_printf("head location: %p\\n", *head);
- return;
- }
- //该片段来自于http://www.codesnippet.cn/detail/2212201411385.html
来源: http://www.codesnippet.cn/detail/2212201411385.html