Chinaunix首页 | 论坛 | 博客
  • 博客访问: 35767
  • 博文数量: 24
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 246
  • 用 户 组: 普通用户
  • 注册时间: 2016-02-14 20:13
  • 认证徽章:
文章分类

全部博文(24)

文章存档

2017年(5)

2016年(19)

我的朋友

分类: C/C++

2016-03-05 15:44:56


  1. /*
  2.  * 根据郝斌老师视频整理
  3.  * 编译环境:
  4.  * guo@linux:~$ gcc --version
  5.  * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
  6.  * 链表队列
  7.  */
  8. #include <stdio.h>
  9. #include <malloc.h>
  10. #include <stdlib.h>

  11. #define FALSE 0
  12. #define TRUE 1

  13. typedef struct Node
  14. {
  15.     int data;
  16.     struct Node *pNext;
  17. }NODE, *PNODE;

  18. typedef struct Queue
  19. {
  20.     PNODE pFront;
  21.     PNODE pRear;
  22. }LINK_QUEUE, *PLINK_QUEUE;

  23. /**********************声明**********************************/
  24. /*初始化链表队列*/
  25. void InitLinkQueue(PLINK_QUEUE pLinkQueue);
  26. /*插入链表队列--入队*/
  27. void InsertLinkQueue(PLINK_QUEUE pLinkQueue, int val);
  28. /*遍历链表队列*/
  29. void TraverseLinkQueue(PLINK_QUEUE pLinkQueue);
  30. /*判断一个链表队列是否为空队列*/
  31. int IsEmpty(PLINK_QUEUE pLinkQueue);
  32. /*删除队列一个元素--出队*/
  33. int DeleteLinkQueue(PLINK_QUEUE pLinkQueue, int *pVal);
  34. /*清空队列*/
  35. void ClearLinkQueue(PLINK_QUEUE pLinkQueue);

  1. /*
  2.  * 函数名称:InitLinkQueue。
  3.  * 输入参数:pLinkQueue队列的地址。
  4.  * 输出参数:无。
  5.  * 函数说明:新建一个队列。
  6.  * 申请一块PNODE类型的内存,相当于链表的头节点,不存放有效元素。
  7.  * pFront(头部)和pRear(尾部)都指向此内存。
  8.  * 队列的特点是"先入先出"
  9.  */
  10. void InitLinkQueue(PLINK_QUEUE pLinkQueue)
  11. {
  12.     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  13.     if (NULL == pNew)
  14.     {
  15.         printf("\n");
  16.         exit(-1);
  17.     }
  18.     pNew->pNext = NULL;
  19.     pLinkQueue->pFront = pLinkQueue->pRear = pNew;

  20.     return ;
  21. }


  1. /*
  2.  * 函数名称:InsertLinkQueue。
  3.  * 输入参数:pLinkQueue链表队列的地址;val要插入队列的元素。
  4.  * 输出参数:无。
  5.  * 函数说明:向队列中插入一个元素。
  6.  * 插入时从pRear处插入;删除时从pFront处删除。
  7.  */
  8. void InsertLinkQueue(PLINK_QUEUE pLinkQueue, int val)
  9. {
  10.     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  11.     if (NULL == pNew)
  12.     {
  13.         printf("\n");
  14.         exit(-1);
  15.     }
  16.     pNew->pNext = NULL;
  17.     pNew->data = val;
  18.     
  19.     pLinkQueue->pRear->pNext = pNew;
  20.     pLinkQueue->pRear = pNew;

  21.     return ;
  22. }

  1. /*
  2.  * 函数名称:TraverseLinkQueue。
  3.  * 输入参数:pLinkQueue链表队列的地址。
  4.  * 输出参数:无。
  5.  * 函数说明:遍历输出链表队列。
  6.  */
  7. void TraverseLinkQueue(PLINK_QUEUE pLinkQueue)
  8. {
  9.     PNODE p = pLinkQueue->pFront;
  10.     while (p != pLinkQueue->pRear)
  11.     {
  12.         printf("%d ", p->pNext->data);
  13.         p = p->pNext;
  14.     }
  15.     
  16.     printf("\n");
  17.     return ;
  18. }

  19. /*
  20.  * 函数名称:IsEmpty。
  21.  * 输入参数:pLinkQueue链表队列的地址。
  22.  * 输出参数:如果链表队列为空,返回TRUE;否则返回FALSE。
  23.  * 函数说明:向队列中插入一个元素。
  24.  */
  25. int IsEmpty(PLINK_QUEUE pLinkQueue)
  26. {
  27.     if (pLinkQueue->pFront == pLinkQueue->pRear)
  28.         return TRUE;
  29.     else
  30.         return FALSE;
  31. }


  1. /*
  2.  * 函数名称:DeleteLinkQueue。
  3.  * 输入参数:pLinkQueue链表队列的地址;pVal存储删除的元素的值。
  4.  * 输出参数:删除成功,返回TRUE;否则返回FALSE。
  5.  * 函数说明:在链表队列中删除一个元素。
  6.  */
  7. int DeleteLinkQueue(PLINK_QUEUE pLinkQueue, int *pVal)
  8. {
  9.     if ( IsEmpty(pLinkQueue) )
  10.     {
  11.         return FALSE;
  12.     }
  13.     else
  14.     {
  15.         /*p指向链表队列的第一个有效元素*/
  16.         PNODE p = pLinkQueue->pFront->pNext;
  17.         /**/
  18.         *pVal = p->data;
  19.         /**/
  20.         pLinkQueue->pFront->pNext = p->pNext;

  21.     /*如果不加if这一句,删除完链表队列后,遍历输出会显示“段错误 (核心已转储)*/
  22.         if (pLinkQueue->pRear == p)
  23.         {
  24.             pLinkQueue->pRear = pLinkQueue->pFront;
  25.         }
  26.         free(p);
  27.         p = NULL;

  28.         return TRUE;
  29.     }
  30. }

  1. /*
  2.  * 函数名称:ClearLinkQueue。
  3.  * 输入参数:pLinkQueue链表队列的地址。
  4.  * 输出参数:无。
  5.  * 函数说明:清空一个链表队列,恢复到初始状态。无论是否空队列都适合。
  6.  */
  7. void ClearLinkQueue(PLINK_QUEUE pLinkQueue)
  8. {
  9.     PNODE p,q;
  10.     /*将队尾指针指向头节点*/
  11.     pLinkQueue->pRear = pLinkQueue->pFront;
  12.     /*p指向第一个有效元素*/
  13.     p = pLinkQueue->pFront->pNext;
  14.     /*头节点的指针域设为空*/
  15.     pLinkQueue->pFront->pNext = NULL;

  16.     while (p)
  17.     {
  18.         q = p;
  19.         free(p);
  20.         p = p->pNext;
  21.     }
  22.     return ;
  23. }

  24. int main(void)
  25. {
  26.     LINK_QUEUE LinkQueue;
  27.     int val;
  28.     
  29.     InitLinkQueue(&LinkQueue);
  30.     
  31.     InsertLinkQueue(&LinkQueue, 1);
  32.     InsertLinkQueue(&LinkQueue, 2);
  33.     InsertLinkQueue(&LinkQueue, 3);
  34. /* InsertLinkQueue(&LinkQueue, 4);
  35.     InsertLinkQueue(&LinkQueue, 5);
  36.     InsertLinkQueue(&LinkQueue, 6);*/
  37.     
  38.     TraverseLinkQueue(&LinkQueue);

  39.     if ( IsEmpty(&LinkQueue) )
  40.         printf("队列为空!\n");
  41.     else
  42.         printf("队列非空!\n");

  43.     DeleteLinkQueue(&LinkQueue, &val);
  44.     printf("删除的元素是:%d\n",val);
  45.     TraverseLinkQueue(&LinkQueue);

  46.     DeleteLinkQueue(&LinkQueue, &val);
  47.     printf("删除的元素是:%d\n",val);
  48.     TraverseLinkQueue(&LinkQueue);

  49.     DeleteLinkQueue(&LinkQueue, &val);
  50.     printf("删除的元素是:%d\n",val);
  51.     TraverseLinkQueue(&LinkQueue);


  52.     ClearLinkQueue(&LinkQueue);
  53.     if ( IsEmpty(&LinkQueue) )
  54.         printf("队列为空!\n");
  55.     else
  56.         printf("队列非空!\n");

  57.     return 0;
  58. }





阅读(451) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册