一道微軟的Mini-Test筆試題(二)

  一道微軟的Mini-Test筆試題(二) 題目要求基本如下：

請編寫一個控制台程式,要求使用者可以輸入任意組條件，定義兩個字母之間的大小關系。程式可以通過已輸入的條件，推斷出給定的兩個字母之間的大小關系。例如：

使用者輸入：A>B

使用者輸入：B>C

使用者輸入：A?C

程式顯示：A>C

使用者輸入：C<D

使用者輸入：A?D

程式顯示：無法判斷

使用者輸入：A<C

程式顯示：與原有條件沖突

。。。

字母僅為 26 個英文字母之一，條件隻有大于和小于兩種，問号表示向計算機提問。程式要能檢查使用者輸入的文法是否正确，檢查條件是否于原有的條件沖突，并輸入判斷結果。

其實這個題目考的是如何選擇一個好的資料結構，來實作這個算法。

我的思路就是使用最簡單的二維數組來表達，具體如下：

總共隻有 26 個英文字母，是以不訪定義一個26X26的二維字元數組來儲存互相之間的關系；

因為關系是互相的，是以隻需要矩陣的上半部分或者下半部分（不過26X26也不算很大，就算了吧～～）；

例如：    如果使用者輸入了A>B,先查詢A和B之間的大小關系，如果與‘>’沖突，則提示出錯； 不存在沖突則設定[A][B]='>'和[B][A]='<'；并且做如下設定：将是以小于B的字元都小于A、所有大于A的字元都大于B； 如果使用者查詢兩個字元之間的關系，則直接從二維表中查找二者的關系并輸出 這樣一來，問題就迎刃而解了 具體代碼如下：

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#define UNKNOWN  'u'

#define LARGER   '>'

#define LESS    '<'

#define MAX_COL    26

//初始化二維數組

void Init();

//列印二維數組

void Print();

//查詢兩個字元的大小關系

bool Query(char v1,char v2);

//輸入兩個字元的大小關系

bool Input(char v1,char op,char v2);

//擷取兩個字元的大小關系

char GetRel(char v1,char v2);

//設定兩個字元的大小關系

void SetRel(char v1,char v2,char op);

char matrix[MAX_COL][MAX_COL];

//主函數

int main()

{

    Init();

    char buf[8];

    char v1,op,v2;

    while(true)

    {

        printf("使用者輸入：");

        memset(buf,0,8);

        scanf("%s",buf);

        strupr(buf);

        if(strcmp(buf,"EXIT")==0

            ||strcmp(buf,"QUIT")==0

            ||strcmp(buf,"Q")==0

            )

            break;

        if(strcmp(buf,"PRINT")==0

            ||strcmp(buf,"P")==0 )

        {

            Print();

            continue;

        }

        v1=buf[0];

        op=buf[1];

        v2=buf[2];

        if(!isalpha(v1) || !isalpha(v2))

        {

            printf("Error:Invalid char!/n");

            continue;

        }

        if(op=='?')

        {

            Query(v1,v2);

        }

        else if(op == '>' || op == '<')

        {

            if(v1==v2)

            {

                printf("Error:two chars are equal!/n");

                continue;

            }

            Input(v1,op,v2);

        }

        else

        {

            printf("Error:Unknown operator!/n");

        }

    }

}

void Init()

{

    for(int i=0;i<MAX_COL;i++)

    {

        for(int j=0;j<MAX_COL;j++)

        {

            matrix[i][j]=UNKNOWN;

        }

    }

}

void Print()

{

    for(int i=0;i<MAX_COL;i++)

    {

        for(int j=0;j<MAX_COL;j++)

        {

            printf("%c",matrix[i][j]);

        }

        printf("/n");

    }

}

bool Query(char v1,char v2)

{

    char rel=GetRel(v1,v2);

    switch(rel)

    {

    case UNKNOWN:

        printf("程式顯示：無法判斷/n");       

        return true;

    }

    printf("程式顯示：%c%c%c/n",v1,rel,v2);

    return true;

}

bool Input(char v1,char op,char v2)

{

    char rel=GetRel(v1,v2);

    if(rel==UNKNOWN)

    {

        SetRel(v1,v2,op);

        //若v1>v2,則所有比v1大的符号都将比v2大,所有比v2小的符号都将比v1小

        if(op == LARGER)

        {

            for(int i='A';i<='Z';i++)

            {

                if(LARGER ==GetRel(i,v1))

                {

                    SetRel(i,v2,LARGER);

                }

                if(LESS == GetRel(i,v2))

                {

                    SetRel(i,v1,LESS);

                }

            }

        }

        //若v1<v2,則是以小于v1的符号都比v2小，所有大于v2的符号都将比v1大

        else if(op==LESS)

        {

            for(int i='A';i<='Z';i++)

            {

                if(LESS ==GetRel(i,v1))

                {

                    SetRel(i,v2,LESS);

                }

                if(LARGER == GetRel(i,v2))

                {

                    SetRel(i,v1,LARGER);

                }

            }

        }

    }

    else if(rel != op)

    {

        printf("程式顯示：與原有條件沖突/n");

        return false;

    }

    return true;

}

char GetRel(char v1,char v2)

{

    return matrix[v1-'A'][v2-'A'];

}

void SetRel(char v1,char v2,char op)

{

    matrix[v1-'A'][v2-'A']=op;

    matrix[v2-'A'][v1-'A']=(op==LARGER)?LESS:LARGER;

} ＝＝＝＝＝＝＝＝＝解法二＝＝＝＝＝＝＝＝＝＝ ///

實作方法：

根據輸入的條件，建立一個主連結清單，表示輸入的所有的字元

主連結清單的每一個元素含有一個數組，用它來儲存所有比他小的元素的位址。具體實作看代碼。

希望黏貼的很完全，^_^.

// MiniTest.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#include <string>

#include <vector>

#include <vld.h>

using namespace std;

class Data  

{

    public:

    char c;

    Data(char ch)

    {

        this->c=ch;

    }

    ~Data()

    {

        if (relationlink.size ()>0)

        {

            relationlink.clear ();

        }

    }

    vector<Data*> relationlink;//儲存所有小于 指針

    Data* link;//指向下一個元素

    bool operator==(Data* pdata)

    {

        if (pdata->c==c)

        {

            return true;

        }

        return false;

    }

    bool operator==(char ch)

    {

        if (c==ch)

        {

            return true;

        }

        return false;

    }

    bool operator==(Data& data)

    {

        if (data.c==c)

        {

            return true;

        }

        return false;

    }

};

class MiniTest

{

public:

    MiniTest()

    {

        mHeader=NULL;

    }

    ~MiniTest()

    {    Data* p=mHeader;

        Data* next;

        while (NULL!=p)

        {

            next=p->link;

            delete p;

            p=next;

        }

    }

    void setUserInput(string str)

    {

        if (str.length ()>3)

        {

            cout<<"請根據要求輸入資料";

            return;

        }

        string tempstr=convertInput (str);

        if (""==tempstr)

        {

            return;

        }

        if ("?"==tempstr)

        {

            //Data data(str[0]);

            bool res=getResult (str[0],str[2]);

            if (res)

            {

                cout<<str[0]<<">"<<str[2]<<endl;

                return;

            }

            res=getResult (str[2],str[0]);

            if (res)

            {

                cout<<str[0]<<"<"<<str[2]<<endl;

                return;

            }

            cout<<"根據輸入的條件還不能判斷"<<endl;

            return;

        }

        if (str[0]==str[2])

        {

            cout<<"輸入了相同的資料"<<endl;

            return;

        }

        Data* p;

        if (NULL==mHeader)

        {

            mHeader= new Data(tempstr[0]);

            mHeader->link=NULL;

            mLastData=mHeader;

            p=getData (tempstr[2]);

            if (p)

            {    

                mHeader->relationlink.push_back(p);

            }

            else

            {

                cout<<"run error";

            }

        }

        else

        {

            p=getData (tempstr[0]);

            if (IsSameCase (p,tempstr[2]))

            {

                return;

            }

            if (inputConflict (tempstr[0],tempstr[2]))

            {

                cout<<"條件沖突"<<endl;

                return;

            }

            p->relationlink.push_back (getData (tempstr[2]));

        }

    }

protected:

    string convertInput(string str)

    {

        char tempch=str[1];

        if (!('>'==tempch||'?'==tempch||'<'==tempch))

        {

            cout<<"請根據要求輸入資料";

            return "";

        }

        if ('<'==tempch)

        {

            char temp;

            temp=str[0];

            str[0]=str[2];

            str[1]='>';

            str[2]=temp;

            return str;

        }

        if ('?'==tempch)

        {

            return "?";

        }

        return str;

    }

    Data* getData(char ch)

    {

        Data* p;

        p=mHeader;

        //assert(p);

        while (NULL!=p)

        {

            if (*p==ch)

            {

                return p;

            }

            p=p->link;

        }

        mLastData->link=new Data(ch);

        mLastData=mLastData->link;

        mLastData->link=NULL;

        return mLastData;

    }

    bool getResult(char ch1,char ch2)

    {

        Data* p=existData (ch1);

        if (NULL==p)

        {

            return false;

        }

        if(!searchData(p->relationlink,ch2))

        {

            return false;

        }

        return true;

    }

    Data* existData(char ch)

    {

        Data* p;

        p=mHeader;

        while (NULL!=p)

        {

            if (*p==ch)

            {

                return p;

            }

            p=p->link;

        }

        return NULL;

    }

    bool searchData(vector<Data*> vecdata,char ch)

    {    bool ret;

        int count=vecdata.size ();

        for (int i=0;i<count;i++)

        {

            if (*vecdata[i]==ch)

            {

                return true;

            }

             ret= searchData (vecdata[i]->relationlink,ch);

             if (ret)

             {

                 return true;

             }

        }

        return false;

    }

    bool IsSameCase(Data* p,char ch)

    {

        int count=p->relationlink.size ();

        for (int i=0;i<count;i++)

        {

            if (*p->relationlink[i]==ch)

            {

                return true;

            }

        }

        return false;

    }

    bool inputConflict(char ch1,char ch2)

    {

        Data* p=getData (ch2);

        int count=p->relationlink.size ();

        for (int i=0;i<count;i++)

        {

            if (*p->relationlink[i]==ch1)

            {

                return true;

            }

        }

        return false;

    }

protected:

        Data* mHeader;

        Data* mLastData;

};

int _tmain(int argc, _TCHAR* argv[])

{

    MiniTest* test=new MiniTest;

    while (1)

    {

        string str;

        cin>>str;

        if ("q"==str)

        {

            break;

        }

        test->setUserInput (str);

    }

    delete test;

    return 0;

}