字符串功能实现

字符串(C++)

/* 最后一个线性存储结构 */
/* 功能：
   初始化：生成一个任意长度的字符串
   展示：显示字符串的值
   复制：复制一个任意长度字符串的值到另外一个任意长度字符串
   连接：将两个任意长度的字符串连接成一个新和字符串
   比较：比较两个任意长度的字符串的大小
   截取：在一个字符串上截取一个子串
   插入：在一个字符串中插入另外一个任意长度的字符串
   判断包含：判断一个主串是否包含另外一个子串
*/


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

#define MAX_SIZE 5
#define INCREASE_SIZE 10

using namespace std;

typedef struct Node {
    char *data;
    int length;
    int maxSize;
} *String;

//declare the function
String initString();
void display(String);
void link(String , String);
void copyStr(String , String);
int compare(String , String);
String subStr(String , int , int);
void insert(String , String , int);
bool contain(String , String);

int main()
{
    cout << "---------------------Please input a String ..." << endl;
    String str = initString();

    cout << "---------------------Please input the next String ..." << endl;
    String str2 = initString();

    cout << "---------------------The value of the first String is ..." << endl;
    display(str);

    cout << "---------------------The value of the next String is ..." << endl;
    display(str2);

    //test the function of judage a String contain another String or not
    /*bool bRet = contain(str , str2);
    if(bRet) {
        cout << "contain..." << endl;
    } else {
        cout << "not contain..." << endl;
    }*/

    // test the function of insert a String
    /*cout << "---------------------Please input the index where you want to insert into ..." << endl;
    int iInsert;
    cin >> iInsert;
    insert(str , str2 , iInsert);
    cout << "---------------------the String value after insert another String ..." << endl;
    display(str);*/

    //test the function of substance
    /*int iIndex;
    int iLength;
    cout << "---------------------Please input the start index ..." << endl;
    cin >> iIndex;
    cout << "---------------------Please input the length you want to cut ..." << endl;
    cin >> iLength;
    String strSub = subStr(str , iIndex , iLength);
    cout << "---------------------the subString is ..." << endl;
    display(strSub);*/

    //test the compare function
    int iRes = compare(str , str2);
    if(iRes == 1) {
        cout << "bigger" << endl;
    } else if(iRes == -1) {
        cout << "lesser" << endl;
    } else {
        cout << "same" << endl;
    }


    //test copy a String into another String
    /*copyStr(str , str2);  //copy str2 to str1
    cout << "---------------------The value of the copy String is ..." << endl;
    display(str);*/

    //test the function which link two String
    /*link(str , str2);
    cout << "---------------------The value of the merge String is ..." << endl;
    display(str);*/

    return 0;
}

//initial a String
String initString() {
    String str = (String)malloc(sizeof(Node));

    //initial a MAX_SIZE capcity String
    str->data = (char *)malloc(MAX_SIZE * sizeof(char));
    str->length = 0;
    str->maxSize = MAX_SIZE;

    char in;
    cin.get(in);  //use this function can read in a space

    while(in != '\n') {

        /*when the length of String is less than the maxSize
          append the value into the String directly*/
        if(str->length < str->maxSize) {
            *(str->data + str->length) = in;
            str->length++;
            cin.get(in);
            continue;
        }

        /* when the length of String is bigger than the maxSize
           build a new Space and copy the original data into the new Space
           and then append the Value into the String
        */
        if(str->length >= str->maxSize) {
            str->data = (char *)realloc(str->data , (str->maxSize + INCREASE_SIZE) * sizeof(char));
            str->maxSize = str->maxSize + INCREASE_SIZE;
            *(str->data + str->length) = in;
            str->length++;
        }

        cin.get(in);
    }

    return str;
}

//insert a String into another String
void insert(String str , String s , int index) {
    //judge the index is fit
    if(index < 0 || index > str->length) {
        return;
    }

    /*if the length of the String is bigger than the maxSize
      build a new Space and copy the original into the new Space
    */
    if((str->length + s->length) > str->maxSize) {
        str->data = (char *)realloc(str->data , (str->maxSize + s->length) * sizeof(char));
        str->maxSize = str->maxSize + s->length;
    }

    /* move the value after index */
    for(int j = str->length - 1 ; j >= index; j--) {
        *(str->data + j + s->length) = *(str->data + j);
    }

    /* insert the value of child String into the main String */
    for(int i = 0; i < s->length; i++) {
        *(str->data + index + i) = *(s->data + i);
    }

    // update the length of the main String
    str->length = s->length + str->length;
}

//judge a String is contain another String or not
bool contain(String str , String s) {
    bool bReturn = false;

    // if the child String's length bigger than the main String , return false
    if(str->length < s->length) {
        return bReturn;
    }

    //judge the main String ocntain the child String or not
    int i = 0 , j = 0;
    while(i < str->length && j < s->length) {

        //when the current value is not same
        if(*(str->data + i) != *(s->data + j)) {
            i++;

            /* if the index on the child String is not at the first
               udpate the index as the first place
               begin a new compare with the left String value of the main String
             */
            if(j != 0) {
                j = 0;
            }
        } else {
            i++;
            j++;
        }
    }

    if(j == s->length && *(str->data + i - 1) == *(s->data + j - 1)) {
        bReturn = true;
    }

    return bReturn;
}

//substance the String
String subStr(String str , int index , int length) {
    //judge the varible is fit or not
    if(index < 0 || length == 0 || index > str->length) {
        return NULL;
    }

    /* build a new String as the return value of the function */
    String strReturn = (String)malloc(sizeof(Node));
    strReturn->maxSize = length > MAX_SIZE ? length : MAX_SIZE;
    strReturn->data = (char *)malloc(strReturn->maxSize * sizeof(char));
    strReturn->length = 0;

    /* if the length requestd is bigger than the value length after index
       cut the String vlaue from index to the end of the main String as a result
     */
    if(length > str->length - index) {

        for(int i = index; i < str->length; i++) {
            *(strReturn->data + strReturn->length) = *(str->data + i);
            strReturn->length++;
        }
    } else {

        for(int i = 0 ; i < length; i++) {
            *(strReturn->data + strReturn->length) = *(str->data + index + i);
            strReturn->length++;
        }
    }

    return strReturn;
}

//display the String
void display(String str) {

    for(int i = 0; i < str->length; i++) {
        cout << *(str->data + i);
    }
    cout << endl;
}

//compare two String
int compare(String str1, String str2) {

    int index = 0;

    while(index < str1->length && index < str2->length) {

        /* if the current value is equal compare the next vlaue of the two String */
        if(*(str1->data + index) == *(str2->data + index)) {
            index++;
        } else if(*(str1->data + index) < *(str2->data + index)) {
            return -1;
        } else {
            return 1;
        }
    }

    /* if the child String is over and the main String is not return 1 */
    if(index == str1->length && index != str2->length) {
        return -1;
    } else if(index == str2->length && index != str1->length) {
        /* if the main String is over and the child String is not return -1 */
        return 1;
    } else {
        /* else the main String is equals the child String */
        return 0;
    }
}

//copy the String into another String
void copyStr(String str1 , String str2) {

    // if the capcity is abundant copy the child String's value into the main String
    if(str1->maxSize >= str2->length) {
        str1->length = 0;

        for(int i = 0; i < str2->length; i++) {
            *(str1->data + str1->length) = *(str2->data + i);
            str1->length++;
        }
    } else {
        /* if the length of the main String is less than the child String's length
           build a new Space
           with cpcity of the main String's capcity plus the length of the child String
        */
        str1->data = (char *)realloc(str1->data , (str1->maxSize + str2->length) * sizeof(char));
        str1->length = 0;
        str1->maxSize = str1->maxSize + str2->length;

        for(int i = 0; i < str2->length; i++) {
            *(str1->data + str1->length) = *(str2->data + i);
            str1->length++;
        }
    }
}

//link two String
void link(String strB , String strE) {

    /* when the capcity is not abundant
       build a new Space and copy the original value into the new Space
     */
    if(strB->length + strE->length > strB->maxSize) {
        strB->data =
            (char *)realloc(strB->data , (strB->maxSize + strE->length) * sizeof(char));
        strB->maxSize = (strB->maxSize + strE->length);

        /* append the value of the child String to the main String */
        for(int i = 0; i < strE->length; i++) {
            *(strB->data + strB->length) = *(strE->data + i);
            strB->length++;
        }

    } else {

        for(int i = 0; i < strE->length; i++) {
            *(strB->data + strB->length) = *(strE->data + i);
            strB->length++;
        }
    }
}