資料結構熱身--隊列的C++實作

//SinglyLinkedList.h

#pragma once
#include <windows.h>
#include <iostream>
using namespace std;

// 資料結構體
struct STDataInfo
{
  char name[20]; // 姓名
  char club[20]; // 俱樂部
  char nation[20];// 國家
  int price; // 身價
  int num; // 号碼
};

// 連結清單節點
struct stuLink
{
  STDataInfo data;  // 資訊域
  stuLink * next; // 指向下一節點的指針
};

class SinglyLinkedList
{
public:
  SinglyLinkedList();

  ~SinglyLinkedList();

public:

  // 建立新的節點
  static stuLink* createNewNode(STDataInfo stData);

  // 後向插入
  static void insertAfter( stuLink* head, STDataInfo data);
 
  //按照num檢視前一個節點
  stuLink* selectPreNodeByNum( stuLink* head, int num);
 
   // 按照num檢視目前節點
   stuLink *selectNowNodeByNum(stuLink* head, int num);

   // 按照名字查詢前面一個節點
   static stuLink *selectPreNodeByName(stuLink *head,char* name);

  //按照名字查詢目前節點
  static stuLink* selectNowNodeByName( stuLink* head, char *name);
 
  //删除節點--按照num删除
  void deleteByNum(stuLink* head, int num);
 
  //删除節點--按照name删除
  static void deleteByName(stuLink*head, char *name);
 
  //銷毀連結清單
  void freeLink(stuLink* head);
 
  //循環列印連結清單
  static void printLink(stuLink*head);

  // 儲存連結清單
  static void save(stuLink * head);

  // 加載連結清單
  static void load(stuLink *head);

  // 測試函數
  //void TestLink();

private:

};

//SinglyLinkedList.cpp
#include "SinglyLinkedList.h"
SinglyLinkedList::SinglyLinkedList()
{
}

SinglyLinkedList::~SinglyLinkedList()
{
}

stuLink* SinglyLinkedList::createNewNode(STDataInfo stData)
{
  stuLink *NewNode = (stuLink*)malloc(sizeof(stuLink));
  NewNode->data = stData;
  NewNode->next = NULL;

  return NewNode;

}
 
void SinglyLinkedList::insertAfter(stuLink* head, STDataInfo data)
{
  if(NULL == head)
  {
    cout <<"目前節點不能為空" << endl;
    return;
  }

  while(NULL != head->next)
  {
    head = head->next;
  }

  stuLink * newNode = createNewNode(data);
  head->next = newNode;
}

// 傳回前一個節點
stuLink* SinglyLinkedList::selectPreNodeByNum(stuLink* head, int num)
{
  if(NULL == head) // 判斷頭結點是否為空 
  {
    cout << "目前節點不能為空"<< endl;

    return NULL;
  }

  stuLink *pre = head; // 前一個節點
  head = pre->next; 
  while(NULL != head)
  {
    if(head->data.num == num)
    {
      return pre;
    }
    pre = head;
    head = head->next;
  }

  return NULL;
}

stuLink * SinglyLinkedList::selectNowNodeByNum(stuLink* head, int num)
{
  if(NULL == head) // 判斷頭結點是否為空 
  {
    cout << "目前節點不能為空" << endl;

    return NULL;

  }

  while(NULL!= head->next)
  {
    head = head->next;

    if(head->data.num == num)
    {
      return head;
    }
  }
  
  return NULL;
}

stuLink * SinglyLinkedList::selectPreNodeByName(stuLink *head, char* name)
{
  if(NULL == head)
  {
    cout <<"頭結點為空" << endl;

    return NULL;
  }

  stuLink *pre = head;
  head = head->next; // 目前節點

  while(NULL != head)
  {
    if(0 == strcmp(head->data.name,name))
    {
      return pre;
    
    }

    pre = head;
    head = head->next;
  }

  cout << "節點不存在"<< endl;
  
  return NULL;

}

stuLink* SinglyLinkedList::selectNowNodeByName(stuLink* head, char *name)
{
  if(NULL == head) // 判斷頭結點是否為空
  {
    cout << "目前節點"<< endl;

    return NULL;
  }

  while(NULL != head->next)
  {
    head = head->next;
    if(0 == strcmp(head->data.name,name))
    {
      return head;
    }
  }

  return NULL;
}

void SinglyLinkedList::deleteByNum(stuLink* head, int num)
{
  if(NULL == head)
  {
    return ;
  }

  stuLink *preNode = selectPreNodeByNum(head, num);
  stuLink *delNode = preNode->next;

  preNode->next = delNode->next;
  free(delNode);

  cout <<" 删除成功" << endl;
}

void SinglyLinkedList::deleteByName(stuLink*head, char *name)
{
  if(NULL == head)
  {
    return;
  }

  stuLink *pPreNode = selectPreNodeByName(head, name);

  stuLink *delNode = pPreNode->next;
  pPreNode->next = delNode->next;
  free(delNode);

  cout << "節點删除成功"<< endl;
}

void SinglyLinkedList::freeLink(stuLink* head)
{
  if(NULL == head)
  {
    return;
  }

  head = head->next;
  while(NULL != head)
  {
    stuLink * tempNode = head->next;
    free(head);
    head = tempNode;
  }
}

void SinglyLinkedList::printLink(stuLink*head)
{
  if(NULL == head)
  {
    cout << "頭節點為空" << endl;
    return;
  }
  
  head = head->next;

  while(NULL != head)
  {
    const char* pszName = head->data.name;
    const char* pszClub = head->data.club;
    const char* pszNation = head->data.nation;
    int iPrice = head->data.price;
    int iNum = head->data.num;

    cout << "球員名"<<pszName << " ";
    cout << "球衣号" << iNum << " ";
    cout << "俱樂部" << pszClub << " ";
    cout << "國籍" << pszNation << " ";
    cout << "身價" << iPrice << endl;
    head = head->next;

  }
}

void SinglyLinkedList::save(stuLink * head)
{
  if(NULL == head)
  {
    cout <<"頭節點為空" << endl;
    return;
  }

  FILE * fp = NULL; // 檔案指針變量
  fp = fopen("FootballPlayer.txt","w+");
  if(NULL == fp)
  {
    cout << "儲存失敗"<< endl;
    return;
  }

  head = head->next;
  while(NULL != head)
  {
    fwrite(&head->data,sizeof(STDataInfo),1,fp);
    head = head->next;
  }

  cout <<"儲存成功" << endl;
  
  fclose(fp);
}

void SinglyLinkedList::load(stuLink *head)
{
  if(NULL == head)
  {
    cout << "頭節點為空"<< endl;

    return;
  }

  FILE * fp = NULL; // 檔案指針變量
  fp = fopen("FootballPlayer.txt", "r+");
  if(NULL == fp)
  {
    system("echo > FootballPlayer.txt");
    
    return;
  }

  while(1)
  {
    STDataInfo stInfo;
    int iFlag = fread(&stInfo,sizeof(STDataInfo),1,fp);
    if(iFlag <1)
    {
      break;
    }

    insertAfter(head, stInfo);
  }

  cout << "加載成功"<< endl;

  fclose(fp);
}
/*
void SinglyLinkedList::TestLink()
{
  // 初始化頭結點
  stuLink *head = NULL;
  head = (stuLink *)malloc(sizeof(stuLink));
  head->next = NULL;

  // 新增節點
  STStudent stKAKA;
  strcpy(stKAKA.name,"KAKA");
  stKAKA.num = 22;
  insertAfter(head,stKAKA);

  STStudent stINZAGHI;
  strcpy(stINZAGHI.name, "INZAGHI");
  stINZAGHI.num = 9;
  insertAfter(head, stINZAGHI);

  STStudent stPirlo;
  strcpy(stPirlo.name, "Pirlo");
  stPirlo.num = 21;
  insertAfter(head, stPirlo);

  STStudent stBuffon;
  strcpy(stBuffon.name, "Buffon");
  stBuffon.num = 1;
  insertAfter(head, stBuffon);

  int num = 21;
  struct stuLink* nodeNow = selectNowNodeByNum(head, num);

  char name[20];
  strcpy(name, nodeNow->data.name);
  //strcpy(name, pre->next->data.name);

  cout << "Current Name is " <<name << endl;
}
*/

//Queue.h
#pragma once
#include "SinglyLinkedList.h"
/*
  隊列實作
*/
class Queue :public SinglyLinkedList 
{
public:
  Queue();

  ~Queue();

public:

  // 初始化隊列
  static void InitializeQueue(stuLink *pQueue);

  // 入隊
  static void enQueue(stuLink* pQueue,STDataInfo pNode);

  // 出隊
  static void* deQueue(stuLink* pQueue, STDataInfo& stData);

  // 周遊隊列
  static void PrintQueue(stuLink* pQueue);

  // 隊列測試方法
  static void TestQueue();
private:

};
//Queue.cpp
#include "Queue.h"

Queue::Queue()
{
}

Queue::~Queue()
{
}

void Queue::InitializeQueue(stuLink *pQueue)
{
  pQueue = (stuLink*)malloc(sizeof(stuLink));
  pQueue->next = NULL;
}

void Queue::enQueue(stuLink* pQueue, STDataInfo Node)
{
  SinglyLinkedList::insertAfter(pQueue,Node);
}

void*  Queue::deQueue(stuLink* pQueue, STDataInfo& stData)
{
  if(NULL == pQueue)
  {
    return NULL;
  }
 
  if(NULL == pQueue->next)
  {
    return NULL;
  }

  stData = pQueue->next->data; // 待傳回資料
  
  stuLink* tempNode = pQueue; // 頭節點

  stuLink *delNode = pQueue->next; // 待删除節點

  stuLink* nextNode = delNode->next; // 待删除節點的下一個


  tempNode->next = nextNode;
  
  free(delNode);

  delNode = NULL;

  return NULL;
}

void Queue::PrintQueue(stuLink* pQueue)
{
  if(NULL == pQueue->next)
  {
    return;
  }

  pQueue = pQueue->next;
  while(NULL != pQueue)
  {
    cout << "Name is "<< pQueue->data.name<< endl;
    pQueue = pQueue->next;
  }
}

// 隊列測試函數
void Queue::TestQueue()
{
  //stuLink* pQueue = NULL;

//  InitializeQueue(pQueue);

  STDataInfo stKAKA;
  strcpy(stKAKA.name , "KAKA");
  strcpy(stKAKA.club, "MILAN");
  strcpy(stKAKA.nation, "BRAZIL");
  stKAKA.price = 7000;
  stKAKA.num = 22;

  STDataInfo stINZAGHI;
  strcpy(stINZAGHI.name, "INAZGHI");
  strcpy(stINZAGHI.club, "MILAN");
  strcpy(stINZAGHI.nation, "ITALIA");
  stINZAGHI.price = 7000;
  stINZAGHI.num = 9;


  STDataInfo stPiero;
  strcpy(stPiero.name, "Piero");
  strcpy(stPiero.club, "JUVENTUS");
  strcpy(stPiero.nation, "ITALIA");
  stPiero.price = 8000;
  stPiero.num = 10;

  stuLink* pQueue = NULL;//建立頭節點

  pQueue = (stuLink*)malloc(sizeof(stuLink));//配置設定堆空間

  pQueue->next = NULL;//讓head的下一個節點為空

  enQueue(pQueue, stKAKA);
  enQueue(pQueue, stINZAGHI);
  enQueue(pQueue, stPiero);

  STDataInfo Node1;

  Queue::deQueue(pQueue, Node1);
  cout <<"Node1 Name = " << Node1.name<< endl;
  cout << "Node1 Club = " << Node1.club << endl;

  STDataInfo Node2;
  Queue::deQueue(pQueue, Node2);
  cout << "Node2 Name = " << Node2.name << endl;
  cout << "Node2 Club = " << Node2.club << endl;


  STDataInfo Node3;
  Queue::deQueue(pQueue, Node3);
  cout << "Node3 Name = " << Node3.name << endl;
  cout << "Node3 Club = " << Node3.club << endl;

}
//main.cpp
#include<iostream>
using namespace std;
#include "Queue.h"
#include <windows.h>



int main()
{
  Queue::TestQueue();
  system("pause");

  return 0;
}