【數據結構作業—02】雙鏈表

2.實現下述要求的Locate運算的函數

問題描述

設有一個帶表頭結點的雙向鏈表L，每個結點有4個數據成員：指向前驅結點的指針prior、指向后繼結點的指針next、存放數據的成員data和訪問頻度freq。所有結點的freq初始時都為0。每當在鏈表上進行一次Locate?(L,?x)操作時，令元素值為x的結點的訪問頻度freq加1，并將該結點前移，鏈接到與它的訪問頻度相等的結點后面（如果該結點沒有找到與它訪問頻度相等的結點，鏈接到表頭后面結點），使得鏈表中所有結點，保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。

?

解決方案要求

輸入參數：

1. 輸入n，n表示雙向鏈表L的長度，L中的結點的data域依次為1到n。
2. 隨機多次調用Locate函數，輸入x（調用函數次數由用戶決定）。

輸出參數：

調用Locate函數結束后，從頭結點開始依次輸出鏈表L中個結點的內容（data+freq）。

參考樣例：

?

?

代碼：

#include "stdlib.h"
#include <iostream>
using namespace std;

typedef int ListData;
typedef struct DoubleNode {
    ListData data, frequency;
    struct DoubleNode *prior, *next;
}DoubleNode, *DoubleList;

void CreateDoubleList (DoubleList &first) {
    first = (DoubleNode*)malloc(sizeof(DoubleNode));
    if(first == NULL)    {
        cout << "存儲分配錯誤！" << endl;
        exit(1);
    }
    first->prior = first->next = first;
}

void IniteList(DoubleList &first, ListData n)    {
    DoubleNode *carrier, *temp = first;
    for (int i = 0; i < n; i++)    {
        carrier = (DoubleNode*)malloc(sizeof(DoubleNode));
        carrier->data = i + 1;
        carrier->frequency = 0;
        //Insert
        carrier->prior = temp;
        temp->next = carrier;
        carrier->next = first;
        carrier->next->prior = carrier;
        
        temp = carrier;
    }
}

DoubleList Locate(DoubleList &first, ListData x, ListData n)    {
    DoubleNode *temp = first->next;
    while(temp->data != x && temp != first)    {
        temp = temp->next;
    }
    if (temp == first)    {
        cout << "Please input number range from " << 1 << " to " << n << endl;
        exit(1);
    }
    else
        return temp;
}

void SortList(DoubleList &first, ListData x, ListData n)    {
    DoubleNode *temp;
    temp = Locate(first, x, n);
    int tempNumber;
    temp->frequency++;
    if (temp->prior != first)    {
        while (temp->frequency > temp->prior->frequency)    {
            //SWAP 
            tempNumber = temp->prior->data;
            temp->prior->data = temp->data;
            temp->data = tempNumber;
            //cout << "temp->prior->data " << temp->prior->data << endl;
            //cout << "temp->data " << temp->data << endl;
            
            tempNumber = temp->prior->frequency;
            temp->prior->frequency = temp->frequency;
            temp->frequency = tempNumber;
            //cout << "temp->prior->frequency " << temp->prior->frequency << endl;
            //cout << "temp->frequency " << temp->frequency << endl;
        }
    }    
}

int main()    {
    int n;
    cout << "Please input the link list length:" << endl;
    cin >> n;
    
    cout << "The link list data are" << endl;
    for (int i = 0; i < n; i++)    
        cout << "The   " << i + 1 << " node is   " << i + 1 << ", its frequency is 0." << endl;
    
    cout << "Let's start to test Locate Function.(-1 meansstopping input number)" << endl;
    
    DoubleList first;
    CreateDoubleList(first);
    IniteList(first, n);
    
    int x = 0;
    while(1)    {
        cout << "Please input number :";
        cin >> x;
        if (x != -1) {
            SortList(first, x, n);
        } 
        else    break;
        
        
    }
    cout << "After test, the link list data are:" << endl;
    DoubleNode *temp = first->next;
    int count = 0;
    while(temp != first)    {
        count++;
        cout << "The   " << count << " node is   " << temp->data 
            << ", its frequency is " << temp->frequency << "." << endl;
        temp = temp->next;
    }
    
    return 0;
}

?