【数据结构】串的堆分配表示与实现

采用堆分配存储表示的串被称为堆串，，与顺序串相比，地址空间仍是连续，但空间是在程序执行时动态分配的。

程序中会使用到的realloc函数：

//realloc ：（void *）reelloc (void *ptr,unsigned newsize);//使用： char *str;// str = (char *)realloc(str,20);

代码实现如下：

#pragma once#include<iostream>using namespace std;#define MAX_SZIE 30typedef struct{char *str;int length;}HeapString;/*判断空*/bool IsEmpty(HeapString *s);/*初始化*/void InintString(HeapString *s);/*求长度*/int Length(HeapString *s);/*用字符串给串赋值*/bool StrAssign(HeapString *s, char cstr[]);/*打印*/void StrPrint(HeapString *s);/*在S的pos位置插入串T*/bool StrInsert(HeapString *S, int pos, HeapString *T);/*在S的pos位置删除长度为len的子串*/bool StrDelete(HeapString *S, int pos, int len);/*清空串*/void ClearString(HeapString *s);/*摧毁*/void Destroy(HeapString *s);/*从S的pos位置截取长为len的子串sub*/bool SubString(HeapString *sub, HeapString *s, int pos, int len);/*拼接*/bool StringConcat(HeapString *T, HeapString *S, HeapString *S2); /*拷贝*/bool StrCopy(HeapString *T, HeapString *S);/*比较*/int StrCompare(HeapString *T, HeapString *S);/*从S的pos位置开始定位子串T的初始位置*/int StrIndex(HeapString *S, int pos, HeapString *T);/*将S中的子串T全部用V替换*/bool StrReplace(HeapString *S, HeapString *T, HeapString *V);

#include "string.h"/*堆串*/void InintString(HeapString *s){s->length = 0;s->str = '\0';}bool IsEmpty(HeapString *s){return s->length == 0;}int Length(HeapString *s){return s->length;}void PrintString(char T[]){cout << T << endl;} bool StrAssign(HeapString *s, char cstr[]){int i = 0;int len = 0;if (s->str)free(s->str);for (i = 0; cstr[i] != '\0'; i++);len = i;if (!i){s->str = '\0';s->length = 0;}else{s->str = (char *)malloc(sizeof(char)*len);if (s->str == NULL)return false;for (i = 0; i < len; i++){s->str[i] = cstr[i];}s->length = len;}s->str[i] = cstr[i];s->length = i;}void StrPrint(HeapString *S){int i = 0;for (i = 0; i < S->length; i++){cout <<S->str[i];}cout << endl;}void ClearString(HeapString *s){if (s->str)free(s->str);s->str = '\0';s->length = 0;}void Destroy(HeapString *s){if (s->str)free(s->str);s->str == NULL;}bool SubString(HeapString *sub, HeapString *s, int pos, int len){if (sub->str)free(sub->str);if (pos < 0 || pos > s->length || len <= 0 || len > s->length – pos + 1)return false;sub->str = (char *)malloc(sizeof(char)*len);if (sub->str == NULL)return false;int i = 0;for (; i < len; i++){sub->str[i] = s->str[i + pos – 1];}sub->str[len] = '\0';sub->length = len;}bool StringConcat(HeapString *T, HeapString *S1, HeapString *S2){T->str = (char *)realloc(T->str, sizeof(char)*(S1->length + S2->length));if (T->str == NULL)return false;int i = 0;for (; i < S1->length; i++){T->str[i] = S1->str[i];}for (i = 0; i < S2->length; i++){T->str[S1->length + i] = S2->str[i];}T->str[S1->length + S2->length] == '\0';T->length = S1->length + S2->length;return true;}bool StrCopy(HeapString *T, HeapString *S){if (S->str == '\0')return false;T->str = (char *)realloc(T->str, sizeof(char)*(S->length));if (T->str == NULL)return false;for (int i = 0; i < S->length; i++)T->str[i] = S->str[i];T->length = S->length;return true;}int StrCompare(HeapString *T, HeapString *S){int i = 0;for (; i < T->length && i < T->length; i++){if (T->str[i] != S->str[i]){if (T->str[i] > S->str[i])return 1;return -1;}}if (T->length > T->length)return 1;else if (T->length < T->length)return -1;return 0;}bool StrDelete(HeapString *S, int pos, int len){int i = 0;char *p;if (pos<0 || pos > S->length || len < 0 || len > S->length – pos + 1)return false;p = (char*)malloc(S->length – len);if (p == NULL)return false; for (i = 0; i <pos – 1; i++){p[i] = S->str[i];}for (i = pos – 1; i < S->length – len; i++){p[i] = S->str[i+len];}S->length = S->length – len;S->str = p;return true;}int StrIndex(HeapString *S, int pos, HeapString *T){if (pos < 0 || pos > S->length || IsEmpty(T))return 0;int i = pos – 1;int j = 0;while (i < S->length && j < T->length ){if (S->str[i] == T->str[j]){i++;j++;}else{i = i – j + 1;j = 0;}}if (j >= T->length)return i – j + 1;elsereturn -1;}bool StrInsert(HeapString *S, int pos, HeapString *T){int i = 0;int s_len = S->length;int t_len = T->length;if (pos < 0 || pos – 1 >= S->length)return false;S->str = (char *)realloc(S->str, (S->length + T->length)*sizeof(char));if (S->str == NULL){cout << "内存分配失败" << endl;return false;}for (i = S->length – 1; i >= pos – 1; i–){S->str[i + T->length ] = S->str[i];}for (i = 0; i<T->length; i++){S->str[pos – 1 + i] = T->str[i];}S->length += T->length;//S[i] = '\0';return true;}bool StrReplace(HeapString *S, HeapString *T, HeapString *V){int i = 1;int flag;if (IsEmpty(T))return false;do{i = StrIndex(S, i, T);if (i){StrDelete(S, i, Length(T));int flag = StrInsert(S, i, V);if (!flag)return false;i += Length(V);}} while (i);return true;}#include "string.h"void main(){HeapString s1, s2, sub,T;char ch[MAX_SZIE+1];char a[] = "abcdefdeg";char b[] = "de";char c[] = "XY";InintString(&s1);//cout <<"请输入第1个串:"<< endl;//gets_s(ch);//StrAssign(&s1, ch);StrAssign(&s1, a);cout << "输出串s1: " << endl;StrPrint(&s1);//SubString(&sub, s1, 2, 3);//StrPrint(&sub);InintString(&s2);//cout << "请输入第2个串:" << endl;//gets_s(ch);StrAssign(&s2, b);cout << "输出串s2: " << endl;StrPrint(&s2);cout << endl;//InintString(&T);//StringConcat(&T, &s1, &s2);//StrPrint(&T);//StrCopy(&s1, &s2);//StrPrint(&s1);//cout << StrCompare(&s1, &s2) <<endl;//StrDelete(&s1, 2, 3);cout<<StrIndex(&s1, 2, &s2)<<endl;InintString(&sub);StrAssign(&sub, c);StrPrint(&sub);StrReplace(&s1,&s2,&sub);//StrInsert(&s1, 2, &sub);StrPrint(&s1);getchar();}运行结果如下：

勤奋，它是一块可以吸引到一切美好事物的天然磁石，它比黄金珍贵，

相关文章：

你感兴趣的文章：

标签云：