Chinaunix首页 | 论坛 | 博客
  • 博客访问: 279317
  • 博文数量: 94
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 202
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-08 20:07
文章分类

全部博文(94)

文章存档

2017年(19)

2016年(30)

2015年(12)

2014年(33)

我的朋友

分类: C/C++

2017-04-28 13:31:23


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>

  4. typedef struct ListNode {
  5.     int value;
  6.     struct ListNode *next;
  7. } listnode_t;

  8. void addListTail(listnode_t **phead, int val)
  9. {
  10.     if (phead == NULL) {
  11.         printf("phead NULL\n");
  12.         return;
  13.     }

  14.     listnode_t *p = new listnode_t();
  15.     p->value = val;
  16.     p->next = NULL;
  17.     
  18.     if (*phead == NULL) {
  19.         *phead = p;
  20.     } else {
  21.         listnode_t *pnode;
  22.         pnode = *phead;
  23.         while (pnode->next != NULL) {
  24.             pnode = pnode->next;
  25.         }

  26.         pnode->next = p;
  27.     }
  28. }

  29. void addListSort(listnode_t **phead, int val)
  30. {
  31.     listnode_t *pb, *pc;
  32.     
  33.     if (phead == NULL) {
  34.         printf("phead NULL\n");
  35.         return;
  36.     }

  37.     listnode_t *p = new listnode_t();
  38.     p->value = val;
  39.     p->next = NULL;

  40.     if (*phead == NULL) {
  41.         *phead = p;
  42.     } else if (val < (*phead)->value){
  43.         p->next = *phead;
  44.         *phead = p;
  45.     } else {
  46.         pb = *phead;
  47.         pc = pb->next;

  48.         while (pc != NULL) {
  49.             if (val < pc->value) {
  50.                 break;
  51.             }
  52.             pb = pc;
  53.             pc = pc->next;
  54.         }

  55.         pb->next = p;
  56.         p->next = pc;
  57.     }
  58. }

  59. void delListNode(listnode_t **phead, int val)
  60. {
  61.     listnode_t *ptodel;
  62.     listnode_t *pb, *pc;
  63.     
  64.     if (phead == NULL || *phead == NULL) {
  65.         printf("invalid input...\n");
  66.         return;
  67.     }

  68.     ptodel = NULL;
  69.     
  70.     if ((*phead)->value == val) {
  71.         ptodel = *phead;
  72.         *phead = (*phead)->next;
  73.     } else {
  74.         pb = *phead;
  75.         pc = pb->next;

  76.         while (pc != NULL) {
  77.             if (pc->value == val) {
  78.                 break;
  79.             }

  80.             pb = pc;
  81.             pc = pc->next;
  82.         }

  83.         if (pc != NULL &&
  84.                 pc->value == val) {
  85.             ptodel = pc;
  86.             pb->next = pc->next;
  87.         }
  88.     }

  89.     if (ptodel != NULL) {
  90.         ptodel->next = NULL;
  91.         delete ptodel;
  92.     }
  93. }

  94. listnode_t *mergList(listnode_t *phead1, listnode_t *phead2)
  95. {
  96.     listnode_t *phead;
  97.     listnode_t *p1, *p2, *p;
  98.     
  99.     if (phead1 == NULL) {
  100.         return phead2;
  101.     }

  102.     if (phead2 == NULL) {
  103.         return phead1;
  104.     }

  105.     p1 = phead1;
  106.     p2 = phead2;
  107.     
  108.     if (p1->value < p2->value) {
  109.         phead = p1;
  110.         p1 = p1->next;
  111.     } else {
  112.         phead = p2;
  113.         p2 = p2->next;
  114.     }

  115.     p = phead;

  116.     while ((p1 != NULL) && (p2 != NULL)) {
  117.         if (p1->value < p2->value) {
  118.             p->next = p1;
  119.             p1 = p1->next;
  120.         } else {
  121.             p->next = p2;
  122.             p2 = p2->next;
  123.         }

  124.         p = p->next;
  125.     }

  126.     if (p1 != NULL) {
  127.         p->next = p1;
  128.     }

  129.     if (p2 != NULL) {
  130.         p->next = p2;
  131.     }

  132.     return phead;
  133. }

  134. listnode_t *findKth(listnode_t *phead, unsigned int k)
  135. {
  136.     listnode_t *pa = NULL;
  137.     listnode_t *pb = NULL;
  138.     
  139.     if (phead == NULL || k == 0) {
  140.         printf("Invalid input\n");
  141.         return NULL;
  142.     }

  143.     pa = pb = phead;

  144.     while ((pa->next != NULL) && (k > 1)) {
  145.         k--;
  146.         pa = pa->next;
  147.     }

  148.     if (k > 1) {
  149.         return NULL;
  150.     }

  151.     while (pa->next != NULL) {
  152.         pa = pa->next;
  153.         pb = pb->next;
  154.     }

  155.     return pb;
  156. }

  157. void printList(listnode_t *phead)
  158. {
  159.     listnode_t *p;
  160.     if (phead == NULL) {
  161.         printf("list empty!!!\n");
  162.         return;
  163.     }

  164.     p = phead;
  165.     while (p) {
  166.         printf("%d--->", p->value);
  167.         p = p->next;
  168.     }
  169.     printf("NULL\n");
  170. }

  171. int main()
  172. {
  173.     int val = 1;
  174.     listnode_t *head = NULL;
  175.     listnode_t *head2 = NULL;
  176.     listnode_t *phead = NULL;
  177.     
  178.     while (val != 0) {
  179.         scanf("%d", &val);
  180.         //addListTail(&head, val);
  181.         addListSort(&head, val);
  182.         printList(head);
  183.     }

  184.     scanf("%d", &val);
  185.     phead = findKth(head, val);
  186.     if (phead == NULL) {
  187.         printf("node not exist!\n");
  188.         return 0;
  189.     }
  190.     printf("the Kth node value is %d\n", phead->value);

  191. #if 0
  192.     val = 1;
  193.     printf("start inpurt list2:\n");
  194.     while (val != 0) {
  195.         scanf("%d", &val);
  196.         //addListTail(&head, val);
  197.         addListSort(&head2, val);
  198.         printList(head2);
  199.     }

  200.     phead = mergList(head, head2);
  201.     printList(phead);

  202.     while (1) {
  203.         scanf("%d", &val);
  204.         delListNode(&head, val);
  205.         printList(head);
  206.     }
  207. #endif

  208.     return 0;
  209. }

阅读(1212) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~