链表创建和链表遍历算法的演示

1337阅读　0评论2012-08-13　高傲的活着
分类：C/C++


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <stdlib.h>
  4. typedef struct Node
  5. {
  6.     int data; //数据域
  7.     struct Node * pNext; //指针域
  8. }NODE, * PNODE;

  10. //函数声明
  11. PNODE create_list(void);
  12. void traverse_list(PNODE pHead);
  13. bool is_empty(PNODE pHead);
  14. int length_list(PNODE);
  15. bool insert_list(PNODE,int,int);
  16. bool delete_list(PNODE,int,int *);
  17. void sort_list(PNODE);
  18. int main(void)
  19. {
  20.    PNODE pHead = NULL;
  21.    pHead = create_list(); //创建一个非循环单链表，并将该链表的头结点的地址赋给pHead
  22.    
  23.    int len = length_list(pHead);
  24.     printf("链表的长度为：%4d\n",len);
  25.     printf("排序前链表序列为:\n");
  26.     traverse_list(pHead);
  27.      printf("排序后链表序列为:\n");
  28.     sort_list(pHead);
  29.     traverse_list(pHead);

  31.     return 0;
  32. }

  34. PNODE create_list(void)
  35. {
  36.      int len; //用来存放有效结点的个数
  37.      int i;
  38.      int val; //用来临时存放用户输入的结点的值

  40.      PNODE pHead = (PNODE)malloc(sizeof(NODE));
  41.      if (NULL == pHead)
  42.      {
  43.          printf("分配失败，程序终止！");
  44.          exit(-1);
  45.      }
  46.      PNODE pTail = pHead;
  47.      pTail->pNext =NULL;
  48.      printf("请输入您需要生成的链表结点的个数：len=");
  49.      scanf("%d",&len);

  51.      for (i=0;i<len;++i)
  52.      {
  53.          printf("请输入第%d个结点的值：",i+1);
  54.          scanf("%d",&val);
  55.          PNODE pNew = (PNODE)malloc(sizeof(NODE));
  56.          if (NULL == pNew)
  57.          {
  58.              printf("分配失败，程序终止！");
  59.              exit(-1);
  60.          }
  61.          pNew->data = val;
  62.          pTail->pNext = pNew; //把pNew挂在了pTail的后边
  63.          pNew->pNext = NULL;
  64.      pTail = pNew;
  65.      }
  66.     return pHead;
  67. }

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

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

  88. int length_list(PNODE pHead)
  89. {
  90.      PNODE p = pHead->pNext;
  91.      int len=0; //局部变量必须赋初值，否则排序会出错 因为len中为垃圾值

  93.      while(NULL != p)
  94.      {
  95.          ++len;
  96.          p = p->pNext;
  97.      }
  98.      return len;
  99. }

  101. void sort_list(PNODE pHead)
  102. {
  103.     int i,j,tmp;
  104.     int len = length_list(pHead);
  105.     PNODE p,q;
  106.     for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext)
  107.     {
  108.         for(j=i+1,q=p->pNext; j<len; ++j,q=q->pNext)
  109.         {
  110.            if (p->data > q->data)
  111.            {
  112.              tmp = p->data;
  113.              p->data = q->data;
  114.              q->data =tmp;
  115.            }
  116.         }
  117.             
  118.     }
  119. }

  121. /*
  122.     for(i=0;i<len-1;++i)
  123.     {
  124.         for (j=i+1;j<len;++j)
  125.         {
  126.             if (a[i] > a[j])
  127.             {
  128.                tmp = a[i];
  129.              a[i] = a[j];
  130.              a[j] = tmp;
  131.             }
  132.         }
  133.     }
  134. */
上一篇：typedef的用法
下一篇：堆与栈的区别