Связь списков

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define bIfUnique_dflt true // sets is object will store unique elements
 
//Provides base functionality for strings databaze, by default it will react to calls
//using unsorted strings array, where strings are in the same order
//flags bSrtRtrnAutoFalse and bSrtRtrn are used to kontrol output order of strings
//bErrFlag is set to true value if error aquired
//bSpecFlag only used for special functions.
//Has 2 constructors, default creates object storing only unique strings
//Using CStrTbl(bool bIfUnique) it is possible to create object which stores
//non-unique strings.
 
class CStrTbl {
public:
    CStrTbl();
    CStrTbl(bool bIfUnique);
    ~CStrTbl();
    std::string * pStrAdd(std::string& sInsStr); //adds string and returns pointer to it
    std::string * operator[](unsigned int iX); // access to strings using [] opearator, depends on bSrtRtrn flag
    std::string * pStrFind(const std::string& sInsStr); // returns pointer if sInsStr exists in object
    bool bStrDel(const std::string& sInsStr); //deletes sInsStr string if exists;
    bool bStrDel(const unsigned int& iNdx); //deletes string iX if Exists
    unsigned int nStrFind(const std::string& sInsStr); //returns index of sInsStr if exists
    unsigned int iGetSize() const; //returns number of elements
    bool bIfExists(const std::string& sInsStr);
    bool bErrFlag; //if error happened in last operation
    bool bSpecFlag; // special flag for temp purposes
    bool bSrtRtrnAutoFalse; // if set then every timy you call method which depends on bSrtRtrn, 
    //bSrtRtrn sets to false, by default is true
    bool bSrtRtrn; // WARNING USE IT FOR OUTPUT ONLY!!! if Object should be used as been sorted or unsorted, 
    //by default everytime after call automatically changes to false
private:
    void vChngHAddr(std::string* sFind, std::string* sReplace);
    unsigned int nFindInsPos(const std::string& sInsStr); //returns propriate index for sInsStr insertion in dynamic arr
    unsigned int nFindHardPos(const std::string* sFndStr); //returns propriate index for sFndStr insertion in hard arr
    bool bIsUnique; // if Object consists of unique values
    bool ThereIsEmpty; //if string was deleted and it is place in the array for new string;
    unsigned int * iDelIndexes; //array of deleted indexes for adding and removing strings;
    unsigned int iDynSize; //size of the strings array
    std::string ** sHAddr; // hard addresses to the rest of the world, never sorted
    std::string ** aStrings; // sorted strings array for speed
};
 
CStrTbl::CStrTbl() {
    bIsUnique = bIfUnique_dflt;
    aStrings = NULL;
    sHAddr = NULL;
    iDynSize = 0;
    bErrFlag = false;
    bSpecFlag = false;
    bSrtRtrn = false;
    bSrtRtrnAutoFalse = true;
}
 
CStrTbl::CStrTbl(bool bIfUnique) {
    bIsUnique = bIfUnique;
    aStrings = NULL;
    sHAddr = NULL;
    iDynSize = 0;
    bErrFlag = false;
    bSpecFlag = false;
    bSrtRtrn = false;
    bSrtRtrnAutoFalse = true;
}
 
CStrTbl::~CStrTbl() {
    for (unsigned int i = 0; i < iDynSize; i++) {
        delete aStrings[i];
    }
    free(aStrings);
    free(sHAddr);
}
 
unsigned int CStrTbl::iGetSize() const {
    return iDynSize;
}
 
std::string * CStrTbl::operator[](unsigned int iX) {
    if ((iX > iDynSize) || (iX < 0)) {
        bErrFlag = true;
        return NULL;
    }
    if (bSrtRtrn) {
        if (bSrtRtrnAutoFalse) {
            bSrtRtrn = false;
        }
        return aStrings[iX];
    } else {
        bErrFlag = false;
        if(!sHAddr[iX]){
            bErrFlag = true;
            return NULL;
        }
        return sHAddr[iX];
    }
}
 
unsigned int CStrTbl::nFindHardPos(const std::string* sFndStr) {
    for (unsigned int i = 0; i < iDynSize; i++) {
        if (sHAddr[i] == sFndStr) {
            bSpecFlag = false;
            return i;
        }
    }
    bSpecFlag = true;
    return 0;
}
 
unsigned int CStrTbl::nFindInsPos(const std::string& sInsStr) {
    unsigned int start = 0, end = iDynSize;
    if (end == 0) {
        bSpecFlag = false;
        return 0;
    }
    if (sInsStr.std::string::compare(*aStrings[start]) < 0) {
        bSpecFlag = false;
        return 0;
    }
    if (sInsStr.compare(*aStrings[end - 1]) > 0) {
        bSpecFlag = false;
        return end;
    }
    unsigned int uiMid;
    int siCmpMidRes;
    while (start < end) {
        uiMid = start + (end - start) / 2;
        siCmpMidRes = sInsStr.compare(*aStrings[uiMid]);
        if ((siCmpMidRes < 0) || (!siCmpMidRes)) {
            end = uiMid;
        } else {
            start = uiMid + 1;
        }
    }
    int bCmpRes = sInsStr.compare(*aStrings[end]);
    if (bCmpRes < 0) {
        bSpecFlag = false;
        return end;
    }
    if (!bCmpRes) {
        bSpecFlag = true;
        return end;
    }
    return 0;
}
 
std::string * CStrTbl::pStrFind(const std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if (!bSpecFlag) {
        return NULL;
    }
    return aStrings[iX];
}
 
unsigned int CStrTbl::nStrFind(const std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if (!bSpecFlag) {
        bSpecFlag = true;
        return 0;
    }
    return iX;
}
 
bool CStrTbl::bIfExists(const std::string& sInsStr) {
    return ((bool)pStrFind(sInsStr)) && (bSpecFlag);
}
 
void CStrTbl::vChngHAddr(std::string* sFind, std::string* sReplace) {
    for (unsigned int i = 0; i < iDynSize; i++) {
        if (sHAddr[i] == sFind) {
            sHAddr[i] = sReplace;
            break;
        }
    }
}
 
std::string * CStrTbl::pStrAdd(std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if ((bIsUnique) && (!iX)&&(bSpecFlag)) {
        bSpecFlag = false;
        return NULL;
    }
    aStrings = (std::string**)realloc(aStrings, sizeof (std::string*)*(iDynSize + 1));
    if (!aStrings) {
        bErrFlag = true;
        return NULL;
    }
 
    aStrings[iDynSize] = new std::string;
    if (!aStrings[iDynSize]) {
        bErrFlag = true;
        return NULL;
    }
 
    sHAddr = (std::string**)realloc(sHAddr, sizeof (std::string*)*(iDynSize + 1));
    if (!aStrings) {
        bErrFlag = true;
        return NULL;
    }
 
    for (unsigned int i = iDynSize; i > iX; i--) {
        vChngHAddr(aStrings[i - 1], aStrings[i]);
        *aStrings[i] = *aStrings[i - 1];
    }
    *aStrings[iX] = sInsStr;
    sHAddr[iDynSize++] = aStrings[iX];
 
    return aStrings[iX];
}
 
bool CStrTbl::bStrDel(const std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if ((!iX) || (!bSpecFlag)) {
        return false;
    }
    unsigned int tmp=nFindHardPos(aStrings[iX]);
    sHAddr[tmp] = NULL;
    for (unsigned int i = iX; i < iDynSize - 1; i++) {
        vChngHAddr(aStrings[i + 1], aStrings[i]);
        *aStrings[i] = *aStrings[i + 1];
    }
    iDynSize--;
    std::cout << "!" << aStrings[iDynSize-1] << std::endl;
    
    delete aStrings[iDynSize]; //aStrings[iDynSize] = NULL;
        aStrings[iDynSize] = NULL;
    //delete sHAddr[iDynSize];    //sHAddr[iDynSize] = NULL;
    //std::cout<<"!"<<sHAddr[iDynSize-1]<<std::endl;
 
    aStrings = (std::string**)realloc(aStrings, sizeof (std::string*)*(iDynSize));
    //;
    if (!aStrings) {
        bErrFlag = true;
        return false;
    }
    //sHAddr[iDynSize + 1] = NULL;
    return true;
}
 
bool CStrTbl::bStrDel(const unsigned int& iNdx) {
    if (!sHAddr[iNdx]) {
        return false;
    }
    unsigned int iX = nFindInsPos(*sHAddr[iNdx]);
    const std::string *sInsStr = aStrings[iX];
    return bStrDel(*sInsStr);
}
 
int main(void) {
    CStrTbl arr_CompanyNames;
    std::string str = "0";
    std::cout << *arr_CompanyNames.pStrAdd(str) << std::endl;
    str = "4";
    std::cout << *arr_CompanyNames.pStrAdd(str) << std::endl;
    str = "1";
    std::cout << *arr_CompanyNames.pStrAdd(str) << std::endl;
    str = "3";
    std::cout << *arr_CompanyNames.pStrAdd(str) << std::endl;
    str = "2";
    std::cout << *arr_CompanyNames.pStrAdd(str) << std::endl;
    str = "5";
    std::cout << *arr_CompanyNames.pStrAdd(str) << std::endl;
    std::cout << std::endl;
 
    for (unsigned int i = 0; i < arr_CompanyNames.iGetSize(); i++) {
        arr_CompanyNames.bSrtRtrn = true;
        std::cout << *arr_CompanyNames[i] << std::endl;
    }
    std::cout << std::endl;
    for (unsigned int i = 0; i < arr_CompanyNames.iGetSize(); i++) {
        std::cout << *arr_CompanyNames[i] << std::endl;
    }
    std::cout << std::endl;
 
    std::cout << "!=" << *arr_CompanyNames[5] << std::endl;
    std::cout << std::endl;
    std::cout << arr_CompanyNames.bStrDel("4") << std::endl;
    std::cout << std::endl;
    std::cout << "!=" << *arr_CompanyNames[4] << std::endl;
    std::cout << std::endl;
    for (unsigned int i = 0; i < arr_CompanyNames.iGetSize(); i++) {
        arr_CompanyNames.bSrtRtrn = true;
        std::cout << *arr_CompanyNames[i] << std::endl;
    }
    std::cout << std::endl;
    for (unsigned int i = 0; i < arr_CompanyNames.iGetSize(); i++) {
 
        std::cout << *arr_CompanyNames[i] << std::endl;
    }
 
    return 0;
}

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define bIfUnique_dflt true // sets is object will store unique elements
 
//Provides base functionality for strings databaze, by default it will react to calls
//using unsorted strings array, where strings are in the same order
//flags bSrtRtrnAutoFalse and bSrtRtrn are used to kontrol output order of strings
//bErrFlag is set to true if error aquired
//bSpecFlag only used for special c.
//Has 2 constructors, default creates object storing only unique strings
//Using CStrTbl(bool bIfUnique) it is possible to create object which stores
//non-unique strings.
 
class CStrTbl {
public:
    CStrTbl();
    CStrTbl(bool bIfUnique);
    ~CStrTbl();
    std::string * pStrAdd(std::string& sInsStr); //adds string and returns pointer to it
    std::string * operator[](unsigned int iX); // access to strings using [] opearator, depends on bSrtRtrn flag
    std::string * pStrFind(const std::string& sInsStr); // returns pointer if sInsStr exists in object
    bool bStrDel(const std::string& sInsStr); //deletes sInsStr string if exists;
    bool bStrDel(const unsigned int& iNdx); //deletes string iX if Exists
    unsigned int nStrFind(const std::string& sInsStr); //returns index of sInsStr if exists
    unsigned int iGetSize() const; //returns number of elements
    bool bIfExists(const std::string& sInsStr);
    bool bErrFlag; //if error happened in last operation
    bool bSpecFlag; // special flag for temp purposes
    bool bSrtRtrnAutoFalse; // if set then every timy you call method which depends on bSrtRtrn, 
    //bSrtRtrn sets to false, by default is true
    bool bSrtRtrn; // WARNING USE IT FOR OUTPUT ONLY!!! if Object should be used as been sorted or unsorted, 
    //by default everytime after call automatically changes to false
    void Print(); //prints content
private:
    unsigned int * FreeBlocks; // indexes of free elements in sHAddr
    unsigned int FreeBlocksCount; // count of free blocks;
    void vChngHAddr(std::string* sFind, std::string* sReplace);
    unsigned int nFindInsPos(const std::string& sInsStr); //returns propriate index for sInsStr insertion in dynamic arr
    unsigned int nFindHardPos(const std::string* sFndStr); //returns propriate index for sFndStr insertion in hard arr
    bool bIsUnique; // if Object consists of unique values
    unsigned int iDynSize; //size of the strings array
    unsigned int iHardSize; //prints actual status
    std::string ** sHAddr; // hard addresses to the rest of the world, never sorted
    std::string ** aStrings; // sorted strings array for speed
};
 
CStrTbl::CStrTbl() {
    bIsUnique = bIfUnique_dflt;
    aStrings = NULL;
    sHAddr = NULL;
    iDynSize = 0;
    bErrFlag = false;
    bSpecFlag = false;
    bSrtRtrn = false;
    bSrtRtrnAutoFalse = true;
    FreeBlocksCount = 0;
    iHardSize = 0;
    FreeBlocks = NULL;
}
 
CStrTbl::CStrTbl(bool bIfUnique) {
    bIsUnique = bIfUnique;
    aStrings = NULL;
    sHAddr = NULL;
    iDynSize = 0;
    bErrFlag = false;
    bSpecFlag = false;
    bSrtRtrn = false;
    bSrtRtrnAutoFalse = true;
    FreeBlocksCount = 0;
    iHardSize = 0;
    FreeBlocks = NULL;
}
 
CStrTbl::~CStrTbl() {
    for (unsigned int i = 0; i < iDynSize; i++) {
        delete aStrings[i];
    }
    free(FreeBlocks);
    free(aStrings);
    free(sHAddr);
}
 
unsigned int CStrTbl::iGetSize() const {
    return iDynSize;
}
 
std::string * CStrTbl::operator[](unsigned int iX) {
    if ((iX > iDynSize) || (iX < 0)) {
        bErrFlag = true;
        return NULL;
    }
    if (bSrtRtrn) {
        if (bSrtRtrnAutoFalse) {
            bSrtRtrn = false;
        }
        return aStrings[iX];
    } else {
        bErrFlag = false;
        if (!sHAddr[iX]) {
            bErrFlag = true;
            return NULL;
        }
        return sHAddr[iX];
    }
}
 
unsigned int CStrTbl::nFindHardPos(const std::string* sFndStr) {
    for (unsigned int i = 0; i < iHardSize; i++) {
        if (FreeBlocksCount) {
            for (unsigned int j = 0; j < FreeBlocksCount; j++) {
                continue;
            }
        }
        if (sHAddr[i] == sFndStr) {
            bSpecFlag = false;
            return i;
        }
    }
    bSpecFlag = true;
    return 0;
}
 
unsigned int CStrTbl::nFindInsPos(const std::string& sInsStr) {
    unsigned int start = 0, end = iDynSize;
    if (end == 0) {
        bSpecFlag = false;
        return 0;
    }
    if (sInsStr.std::string::compare(*aStrings[start]) < 0) {
        bSpecFlag = false;
        return 0;
    }
    if (sInsStr.compare(*aStrings[end - 1]) > 0) {
        bSpecFlag = false;
        return end;
    }
    unsigned int uiMid;
    int siCmpMidRes;
    while (start < end) {
        uiMid = start + (end - start) / 2;
        siCmpMidRes = sInsStr.compare(*aStrings[uiMid]);
        if ((siCmpMidRes < 0) || (!siCmpMidRes)) {
            end = uiMid;
        } else {
            start = uiMid + 1;
        }
    }
    int bCmpRes = sInsStr.compare(*aStrings[end]);
    if (bCmpRes < 0) {
        bSpecFlag = false;
        return end;
    }
    if (!bCmpRes) {
        bSpecFlag = true;
        return end;
    }
    return 0;
}
 
std::string * CStrTbl::pStrFind(const std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if (!bSpecFlag) {
        return NULL;
    }
    return aStrings[iX];
}
 
unsigned int CStrTbl::nStrFind(const std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if (!bSpecFlag) {
        bSpecFlag = true;
        return 0;
    }
    return iX;
}
 
bool CStrTbl::bIfExists(const std::string& sInsStr) {
    return ((bool)pStrFind(sInsStr)) && (bSpecFlag);
}
 
void CStrTbl::vChngHAddr(std::string* sFind, std::string* sReplace) {
    for (unsigned int i = 0; i < iHardSize; i++) {
        if (!FreeBlocksCount) {
            for (unsigned int j = 0; j < FreeBlocksCount; j++) {
                if (i == FreeBlocks[j]) {
                    continue;
                }
            }
        }
        if (sHAddr[i] == sFind) {
            sHAddr[i] = sReplace;
            break;
        }
    }
}
 
std::string * CStrTbl::pStrAdd(std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if ((bIsUnique) && (!iX)&&(bSpecFlag)) {
        bSpecFlag = false;
        return NULL;
    }
    if (!FreeBlocksCount) {//if it is no free blocks
        aStrings = (std::string**)realloc(aStrings, sizeof (std::string*)*(iDynSize + 1));
        if (!aStrings) {
            bErrFlag = true;
            return NULL;
        }
        sHAddr = (std::string**)realloc(sHAddr, sizeof (std::string*)*(iHardSize + 1));
    }
    aStrings[iDynSize] = new std::string;
    if (!aStrings[iDynSize]) {
        bErrFlag = true;
        return NULL;
    }
    for (unsigned int i = iDynSize; i > iX; i--) {
        vChngHAddr(aStrings[i - 1], aStrings[i]);
        *aStrings[i] = *aStrings[i - 1];
    }
    *aStrings[iX] = sInsStr;
    if (FreeBlocksCount) {
        sHAddr[FreeBlocks[FreeBlocksCount - 1]] = aStrings[iX];
        FreeBlocksCount--;
        iDynSize++;
        return sHAddr[FreeBlocks[FreeBlocksCount]];
        //FreeBlocks = (unsigned int *) realloc(FreeBlocks, sizeof (unsigned int)*(FreeBlocksCount));
    } else {
        iHardSize++;
        sHAddr[iDynSize] = aStrings[iX];
        iDynSize++;
        return sHAddr[iDynSize - 1];
    }
    iDynSize++;
    return sHAddr[iDynSize - 1];
}
 
bool CStrTbl::bStrDel(const std::string& sInsStr) {
    unsigned int iX = nFindInsPos(sInsStr);
    if (!bSpecFlag) {
        return false;
    }
    unsigned int NewFreeIndex = nFindHardPos(aStrings[iX]);
    FreeBlocks = (unsigned int *) realloc(FreeBlocks, sizeof (unsigned int)*(FreeBlocksCount + 1));
    if (!FreeBlocks) {
        bErrFlag = true;
        return false;
    }
    FreeBlocks[FreeBlocksCount++] = NewFreeIndex;
    sHAddr[NewFreeIndex] = NULL;
    for (unsigned int i = iX; i < iDynSize - 1; i++) {
        vChngHAddr(aStrings[i + 1], aStrings[i]);
        *aStrings[i] = *aStrings[i + 1];
 
        //vChngHAddr(aStrings[i + 1], &tmp_str);
 
    }
    iDynSize--;
    delete aStrings[iDynSize];
 
    return true;
}
 
bool CStrTbl::bStrDel(const unsigned int& iNdx) {
    if (!sHAddr[iNdx]) {
        return false;
    }
    unsigned int iX = nFindInsPos(*sHAddr[iNdx]);
    const std::string *sInsStr = aStrings[iX];
    return bStrDel(*sInsStr);
}
 
void CStrTbl::Print() {
 
    std::cout << "Current status:" << std::endl;
    std::cout << std::endl;
    std::cout << "\tStrings in Dynamic array:\t\t" << iDynSize << std::endl;
    std::cout << "\tStrings in Hard Linked array:\t\t" << iHardSize << std::endl;
    std::cout << "\tNumber of UnUsed Indexes in HL Array:\t\t" << FreeBlocksCount << std::endl;
    std::cout << std::endl;
    std::cout << "\tDynamic array of strings:" << std::endl;
    std::cout << "\t\tIndex\t" << std::setw(9) << "Address\t" << std::setw(10) << "Value" << std::endl;
    for (unsigned int i = 0; i < iDynSize; i++) {
        std::cout << "\t\t" << i << "\t" << aStrings[i] << "\t" << *aStrings[i] << std::endl;
    }
    std::cout << std::endl;
    std::cout << "\tHard Linked array of strings:" << std::endl;
    std::cout << "\t\tIndex\t" << std::setw(9) << "Address\t" << std::setw(10) << "Value" << std::endl;
    for (unsigned int i = 0; i < iHardSize; i++) {
        if (FreeBlocksCount) {
            unsigned int j;
            for (j = 0; j < FreeBlocksCount; j++) {
                if (i == FreeBlocks[j]) {
                    std::cout << "\t\t" << i << "\t" << std::setw(9) << "NULL" << "\t" << "NULL" << std::endl;
                    j++;
                    break;
                }
            }
            if (i == FreeBlocks[j - 1]) {
                continue;
            }
        }
        std::cout << "\t\t" << i << "\t" << sHAddr[i] << "\t" << *sHAddr[i] << std::endl;
    }
    std::cout << std::endl;
    std::cout << "\tArray of HL free indexes:" << std::endl;
    std::cout << "\t\t" << std::setw(10) << "Index" << "\t" << std::setw(10) << "value\t" << std::endl;
    for (unsigned int i = 0; i < FreeBlocksCount; i++) {
        std::cout << "\t\t" << std::setw(10) << i << "\t" << std::setw(9) << FreeBlocks[i] << "\t" << std::setw(9) << "" << std::endl;
    }
    std::cout << std::endl;
 
}
 
int main(void) {
    CStrTbl arr_CompanyNames;
    std::string str = "fdgdfgdf gdfg dfgd fgdfg dfgdfg dgdf gd0dfgfdgdgdf";
    arr_CompanyNames.pStrAdd(str);
    str = "qknafsadvscdxeakowni";
    arr_CompanyNames.pStrAdd(str);
    str = "6735930425";
    arr_CompanyNames.pStrAdd(str);
    str = "(!%?@^+?+@?%*!@+-)+!()^?*)^+)?-!+)(!%!+)";
    arr_CompanyNames.pStrAdd(str);
    str = "XTdfEP?eB7gxc9jhk@gPZCvHdmATa0BXHE4*?3(AOdYQ*8XbY5";
    arr_CompanyNames.pStrAdd(str);
    str = "Kyk31ndmZdcm";
    arr_CompanyNames.pStrAdd(str);
 
 
    std::cout << "_____________________after all added:_________________________" << std::endl;
    arr_CompanyNames.Print();
 
 
 
 
 
    arr_CompanyNames.bStrDel("Kyk31ndmZdcm");
    std::cout << std::endl;
    std::cout << "_____________________after 4 deleted_________________________" << std::endl;
    arr_CompanyNames.Print();
 
    arr_CompanyNames.bStrDel("qknafsadvscdxeakowni");
    std::cout << std::endl;
    std::cout << "_____________________after 3 deleted_________________________" << std::endl;
    arr_CompanyNames.Print();
    
    str = "SLWCBODKEVBVFOVLHWOC";
    arr_CompanyNames.pStrAdd(str);
 
    arr_CompanyNames.bStrDel("2");
    std::cout << std::endl;
    std::cout << "_____________________after2 deleted_________________________" << std::endl;
    arr_CompanyNames.Print();
 
    arr_CompanyNames.bStrDel("0");
    std::cout << std::endl;
    std::cout << "_____________________after 0 deleted_________________________" << std::endl;
    arr_CompanyNames.Print();
 
    arr_CompanyNames.bStrDel("5");
    std::cout << std::endl;
    std::cout << "_____________________after5 deleted_________________________" << std::endl;
    arr_CompanyNames.Print();
    return 0;
}