Chinaunix首页 | 论坛 | 博客
  • 博客访问: 488336
  • 博文数量: 111
  • 博客积分: 3146
  • 博客等级: 中校
  • 技术积分: 939
  • 用 户 组: 普通用户
  • 注册时间: 2009-07-07 11:23
个人简介

Nathing

文章分类

全部博文(111)

文章存档

2016年(2)

2015年(1)

2014年(31)

2012年(2)

2011年(9)

2010年(36)

2009年(30)

我的朋友

分类: C/C++

2014-07-25 09:29:57


点击(此处)折叠或打开

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

  4. typedef struct Node
  5. {
  6.     int data;
  7.     struct Node * pNext;
  8. }NODE, *PNODE;

  9. PNODE create_Node();
  10. void traversal(PNODE p);
  11. bool is_empty(PNODE);
  12. int length(PNODE);
  13. void sort(PNODE);
  14. bool insert(PNODE pHead, int pos, int val);
  15. bool delete_list(PNODE pHead, int pos, int *pVal);

  16. int main(int argc, char * argv)
  17. {
  18.     PNODE p = create_Node();

  19.     traversal(p);

  20.     if (is_empty(p))
  21.         printf("empty\n");
  22.     else
  23.         printf("not empty\n");

  24.     printf("链表的长度为:%d\n", length(p));

  25.     sort(p);

  26.     traversal(p);

  27.     insert(p, 2, 9);
  28.     printf("插入后:\n");

  29.     traversal(p);

  30.     int d_val;
  31.     delete_list(p, 2, &d_val);
  32.     printf("删除后:\n");
  33.     traversal(p);
  34.     free(p);
  35.     return 0;
  36. }

  37. PNODE create_Node()
  38. {
  39.     PNODE pHead = (PNODE)malloc(sizeof(NODE));
  40.     if (NULL == pHead)
  41.     {
  42.         printf("分配失败,程序终止!");
  43.         exit(-1);
  44.     }
  45.     PNODE pTail = pHead;
  46.     pTail->pNext = NULL;
  47.     int i;
  48.     int len;
  49.     int val;
  50.     printf("input arg number: len=");
  51.     scanf("%d", &len);
  52.     for (i = 0; i < len; ++i)
  53.     {
  54.         printf("第%d个值:", i+1);
  55.         scanf("%d", &val);
  56.         PNODE pNew = (PNODE)malloc(sizeof(NODE));
  57.         if (NULL == pNew)
  58.         {
  59.             printf("分配失败,程序终止!");
  60.             exit(-1);
  61.         }
  62.         //set pNew
  63.         pNew->data = val;
  64.         pNew->pNext = NULL;
  65.         //将pNew挂到pTail下
  66.         pTail->pNext = pNew;
  67.         //更新中间变量
  68.         pTail = pNew;
  69.     }
  70.     return pHead;
  71. }

  72. void traversal(PNODE pHead)
  73. {
  74.     PNODE p = pHead->pNext;
  75.     while (NULL != p)
  76.     {
  77.         printf("%d\n",p->data);
  78.         p = p->pNext;
  79.     }
  80. }

  81. bool is_empty(PNODE pHead)
  82. {
  83.     if (NULL == pHead->pNext)
  84.         return true;
  85.     else
  86.         return false;
  87. }

  88. int length(PNODE pHead)
  89. {
  90.     PNODE p = pHead->pNext;
  91.     int len = 0;
  92.     while (NULL != p)
  93.     {
  94.         ++len;
  95.         p = p->pNext;
  96.     }
  97.     return len;
  98. }

  99. void sort(PNODE pHead)
  100. {
  101.     int i, j, t;
  102.     int len = length(pHead);
  103.     PNODE p, q;
  104.     for (i = 0,p = pHead->pNext; i < len - 1; ++i, p = p->pNext)
  105.     {
  106.         for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext)
  107.         {
  108.             if (p->data > q->data)
  109.             {
  110.                 t = p->data;
  111.                 p->data = q->data;
  112.                 q->data = t;
  113.             }
  114.         }
  115.     }
  116. }

  117. bool insert(PNODE pHead, int pos, int val)
  118. {
  119.     int i = 0;
  120.     PNODE p = pHead;

  121.     //通过i的递增来定位到p节点(在p节点的后面插入新节点)
  122.     while (NULL != p && i < pos - 1)
  123.     {
  124.         p = p->pNext;
  125.         ++i;
  126.     }

  127.     if (i > pos - 1 || NULL == p)
  128.     {
  129.         return false;
  130.     }

  131.     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  132.     if (NULL == pNew)
  133.     {
  134.         printf("分配失败,程序终止!");
  135.         exit(-1);
  136.     }
  137.     pNew->data = val;
  138.     pNew->pNext = p->pNext;
  139.     p->pNext = pNew;

  140.     return true;
  141. }

  142. bool delete_list(PNODE pHead, int pos, int *pVal)
  143. {
  144.     int i = 0;
  145.     PNODE p = pHead;

  146.     while (NULL != p->pNext && i < pos - 1)
  147.     {
  148.         p = p->pNext;
  149.         ++i;
  150.     }

  151.     if (i > pos - 1 || NULL == p->pNext)
  152.     {
  153.         return false;
  154.     }

  155.     PNODE q = p->pNext;
  156.     *pVal = q->data;

  157.     p->pNext = p->pNext->pNext;
  158.     free(q);
  159.     q = NULL;
  160.     return true;
  161. }

阅读(404) | 评论(0) | 转发(0) |
0

上一篇:中医入门必读

下一篇:栈之数据结构

给主人留下些什么吧!~~