首页 > 程序开发 > 软件开发 > Java >

有序链式队列

2014-08-04

& 65279;& 65279; & 65279;& 65279; 编写头文件 struct queue { int num; 代表数据 int high; 优先级1111 struct queue *pNext

 
  1. 编写头文件

    struct queue

    {

    int num; //代表数据

    int high; //优先级1111

    struct queue *pNext;//存储下一个节点的地址

    };

    typedef struct queue Queue; //简化队列

    Queue * init(Queue *queueHead); //初始化

    Queue * EnQueue(Queue *queueHead, int num, int high); //入队

    Queue * DeQueue(Queue *queueHead, Queue *pOut); //出队

    Queue * freeall(Queue *queueHead); //清空

    void sort(Queue *queueHead); //优先级排队

    void printfall(Queue *queueHead); //打印所有数据,递归

    Queue * insertEnQueue(Queue *queueHead, int num, int high);

    1. 编写实现队列的代码

      #include "Queue.h"

      #include

      #include

      //初始化

      Queue * init(Queue *queueHead)

      {

      return NULL;

      }

      //入队

      Queue * EnQueue(Queue *queueHead, int num, int high)

      {

      //分配内存

      Queue *pnewnode = (Queue *)malloc(sizeof(Queue));

      pnewnode->num = num;

      pnewnode->high = high;

      pnewnode->pNext = NULL;

      if (queueHead == NULL)

      {

      queueHead = pnewnode;

      }

      else

      {

      Queue *p = queueHead;

      while (p->pNext != NULL)

      {

      p = p->pNext;

      }

      //确定要插入的位置

      //插入,这里是尾部插入

      p->pNext = pnewnode;

      }

      return queueHead;

      }

      //出队

      Queue * DeQueue(Queue *queueHead, Queue *pOut)

      {

      if (queueHead == NULL)

      {

      return NULL;

      }

      else

      {

      //这里相当于是

      pOut->num = queueHead->num;

      pOut->high = pOut->high;

      Queue *pTemp = queueHead;

      //记录要删除的地址

      queueHead = queueHead->pNext;

      //释放节点

      free(pTemp);

      return queueHead;

      }

      }

      ////优先级排队

      //void sort(Queue *queueHead)

      //{

      // if (queueHead == NULL || queueHead->pNext == NULL)

      // {

      // return;

      // }

      // else

      // {

      // for (Queue *p1 = queueHead; p1 != NULL;p1 = p1->pNext)

      // {

      // for (Queue *p2 = queueHead; p2 != NULL;p2 = p2->pNext)

      // {

      // if (p1->high > p2->high)

      // {

      // Queue temp;

      // temp.num = p1->num;

      // p1->num = p2->num;

      // p2->num = temp.num;

      //

      // temp.high = p1->high;

      // p1->high = p2->high;

      // //交换节点数据

      // p2->high = temp.high;

      // }

      // }

      // }

      // }

      //}

      //打印所有数据,递归

      void printfall(Queue *queueHead)

      {

      if (queueHead == NULL)

      {

      return;

      }

      else

      {

      printf("%d,%d,%p,%p\n", queueHead->num, queueHead->high, queueHead, queueHead->pNext);

      printfall(queueHead->pNext);

      }

      }

      Queue * insertEnQueue(Queue *queueHead, int num, int high)

      {

      //分配内存

      Queue *pnewnode = (Queue *)malloc(sizeof(Queue));

      pnewnode->num = num;

      pnewnode->high = high;

      //节点为空

      if (queueHead == NULL)

      {

      pnewnode->pNext = NULL;

      queueHead = pnewnode;

      return queueHead;

      }

      else

      {

      //头插

      if (pnewnode->high > queueHead->high)

      {

      //头部插入

      pnewnode->pNext = queueHead;

      //指向这个节点

      queueHead = pnewnode;

      return queueHead;

      }

      else

      {

      //头节点

      Queue *p = queueHead;

      while (p->pNext != NULL)

      {

      p = p->pNext;

      }

      //循环到尾部

      if (pnewnode->high <= p->high)

      {

      p->pNext = pnewnode;

      pnewnode->pNext = NULL;

      return queueHead;

      }

      else

      {

      Queue *p1, *p2;

      p1 = p2 = NULL; //避免野指针

      p1 = queueHead; //头结点

      while (p1->pNext != NULL)

      {

      p2 = p1->pNext;

      if (p1->high >= pnewnode->high && p2->highhigh)

      {

      pnewnode->pNext = p2;

      p1->pNext = pnewnode;//插入

      break;

      }

      p1 = p1->pNext;

      }

      return queueHead;

      }

      }

      }

      }

      3.编写主函数

      #include "Queue.h"

      #include

      #include

      int main(int argc,char *argv[])

      {

      //创建头结点

      Queue *phead = NULL;

      //初始化

      phead = init(phead);

      phead = insertEnQueue(phead, 1, 1);

      printfall(phead);

      phead = insertEnQueue(phead, 2, 12);

      printfall(phead);

      phead = insertEnQueue(phead, 3, 3);

      printfall(phead);

      phead = insertEnQueue(phead, 4, 14);

      printfall(phead);

      phead = insertEnQueue(phead, 5, 5);

      printfall(phead);

      phead = insertEnQueue(phead, 6, 16);

      printfall(phead);

      phead = insertEnQueue(phead, 6, 0);

      printfall(phead);

      phead = insertEnQueue(phead, 7, 0);

      printfall(phead);

      phead = insertEnQueue(phead, 8, 0);

      printfall(phead);

      phead = insertEnQueue(phead, 9, 1);

      printfall(phead);

      phead = insertEnQueue(phead, 10, 0);

      printfall(phead);

      phead = insertEnQueue(phead, 11, 16);

      printfall(phead);

      phead = insertEnQueue(phead, 111, 19);

      printfall(phead);

      printf("打印排序后的链式队列:\n");

      printfall(phead);

      getchar();

      return 0;

      }

相关文章
最新文章
热点推荐