C語言實現鏈隊列基本操作

隊列的鏈式存儲結構實現,相比於循環隊列實現要復雜一些,但是沒有隊滿的限制。

頭文件聲明

#include <stdio.h>
#include <stdlib.h>

/**
 * 隊列的鏈式存儲實現
 * [帶頭結點的單鏈表]
 * [-類似於鏈棧,隊列的鏈式存儲實現也不會出現隊滿的情況]
 */
//數據類型
typedef int ElemType;

//定義節點
typedef struct SqQueueNode
{
 ElemType data;//數據域
 struct SqQueueNode* next; //指針域
}SqQueueNode;
//定義隊列
typedef struct SqQueueLink{
 SqQueueNode* front;//隊頭指針
 SqQueueNode* rear;//隊尾指針
}SqQueueLink;

//初始化隊列
void InitQueueLink(SqQueueLink* q);
//判斷隊空
int EmptyQueueLink(SqQueueLink q);
//入隊操作
void EnQueueLink(SqQueueLink *q,ElemType e);
//出隊操作
void DeQueueLink(SqQueueLink q,ElemType *e);
//獲取隊列長度
int LengthQueueLink(SqQueueLink q);
//打印隊列
void printSqQueueLink(SqQueueLink q);
//獲取隊頭元素
void GetHeadLink(SqQueueLink q,ElemType* e);

函數實現

#include "SqQueueLink.h"


//初始化隊列
void InitQueueLink(SqQueueLink* q){
 //創建頭結點
 SqQueueNode* pNode=(SqQueueNode*)malloc(sizeof(SqQueueNode));
 pNode->next=NULL;//指針域置空[數據域不存儲任何內容]
 //初始化隊列-[使隊頭指針和隊尾指針指向頭結點]
 q->front=pNode;
 q->rear=pNode;
}

//判斷隊空
int EmptyQueueLink(SqQueueLink q){
 return q.front==q.rear;
}

//入隊操作
void EnQueueLink(SqQueueLink *q,ElemType e){
 //創建新的數據元素節點
 SqQueueNode* newNode=(SqQueueNode*)malloc(sizeof(SqQueueNode));
 newNode->data=e;//指定數據域
 newNode->next=NULL;//指針域置空
 //入隊操作[從隊尾入隊]
 q->rear->next=newNode;
 q->rear=newNode;
}

//出隊操作
void DeQueueLink(SqQueueLink q,ElemType *e){
 //[從隊頭出隊]
 SqQueueNode* p=NULL;
 //是否隊空
 if (q.front==q.rear)
  return;
 p=q.front->next;//獲取首節點
 *e=p->data;
 //使隊頭指針指向下一節點
 q.front->next=p->next;
 //如果原隊列中隻有一個節點,要將隊尾指針和隊頭指針均指向同一節點-置空
 if (q.rear==p)
  q.rear=q.front;
 //釋放原首節點
 free(p);
}

//獲取隊列長度
int LengthQueueLink(SqQueueLink q){
 //輔助指針
 SqQueueNode* pNode=q.front->next;
 int count=0;
 //獲取隊列長度
 while (pNode!=q.rear)
 {
  count++;
  pNode=pNode->next;
 }
 return count;
}

//打印隊列
void printSqQueueLink(SqQueueLink q){
 //輔助指針
 SqQueueNode* p=q.front->next;
 while (p!=q.rear)
 {
  printf("%4d",p->data);
  p=p->next;
 }
 printf("\n");
}

//獲取隊頭元素
void GetHeadLink(SqQueueLink q,ElemType* e){
 //判斷隊列是否為空
 if (q.front==q.rear)
  return;
 //獲取隊頭元素的值
 *e=q.front->next->data;
}

函數測試

#include "SqQueueLink.h"

int main(int argc,char** argv){
 //聲明隊列
 SqQueueLink sqLink;
 int i;
 ElemType data;
 //初始化隊列
 InitQueueLink(&sqLink);
 //判斷隊列是否為空
 printf("is Empty?%d\n",EmptyQueueLink(sqLink));
 //入隊操作
 for (i=0;i<=20;i++)
 {
  EnQueueLink(&sqLink,i+1);
 }
 //判斷隊列是否為空
 printf("is Empty?%d,len=%d\n",EmptyQueueLink(sqLink),LengthQueueLink(sqLink));
 //打印隊列
 printSqQueueLink(sqLink);
 //出隊列操作
 DeQueueLink(sqLink,&data);
 //判斷隊列是否為空
 printf("is Empty?%d,len=%d\n",EmptyQueueLink(sqLink),LengthQueueLink(sqLink));
 //打印隊列
 printSqQueueLink(sqLink);
 //獲取隊頭元素的值
 GetHeadLink(sqLink,&data);
 printf("the first node value is %d\n",data);
 return 0;
}

以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。

推薦閱讀: