《数据结构（C语言版）》串的堆分配存储
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构（C语言版）
以下是本人对该紫皮书第四章串中4.2.2节串的堆分配存储表示的代码实现，把课本上提到的关于这一节的全部函数均实现了，函数部分与课本完全相同
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译，会帮你自动调整缩进）
（预计如果全部更新完会出一个代码合集的压缩包，附上链接以供下载，里面格式为.txt便于大家阅读，希望大家多多支持点个免费的赞）
代码如下：
//串的堆分配存储表示
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct
{
char* ch;//若是非空串，则按串长分配存储区，否则ch为NULL
int length;//串长度
}HString;
Status StrAssign(HString& T, char* chars);//生成一个其值等于串常量的串T
int StrLength(HString S);//返回S的元素个数，称为串的长度
int StrCompare(HString S, HString T);//依据ASCII码值比较两个字符串大小并返回其差值
Status ClearString(HString& S);//将S清为空串
Status Concat(HString& T, HString S1, HString S2);//用T返回S1和S2联接而成的新串
Status SubString(HString& Sub, HString S, int pos, int len);//返回串S的第pos个字符起长度为len的字串
void ShowString(HString S);//打印字符串
void Menu()
{
printf("************************\n");
printf("********0.退 出********\n");
printf("********1.生成串********\n");
printf("********2.求串长********\n");
printf("********3.比较串********\n");
printf("********4.清空串********\n");
printf("********5.连接串********\n");
printf("********6.求子串********\n");
printf("************************\n");
printf("请输入你想使用的功能：");
}
int main()
{
int option;
char strA[100];
char strB[100];
HString MyStringA;
MyStringA.ch = NULL;
MyStringA.length = 0;
HString MyStringB;
MyStringB.ch = NULL;
MyStringB.length = 0;
HString ConnectStr;
ConnectStr.ch = NULL;
ConnectStr.length = 0;
Menu();
while (scanf("%d", &option) != EOF)
{
while (getchar() != '\n');
switch (option)
{
case 1:
printf("请输入字符串A：");
scanf("%100s", strA);
StrAssign(MyStringA, strA);
printf("字符串A为：");
ShowString(MyStringA);
break;
case 2:
printf("字符串A的长度为%d\n", StrLength(MyStringA));
break;
case 3:
printf("请输入字符串B:");
scanf("%100s", strB);
StrAssign(MyStringB, strB);
printf("字符串A为：");
ShowString(MyStringA);
printf("字符串B为：");
ShowString(MyStringB);
printf("两者之差为：%d\n", StrCompare(MyStringA, MyStringB));
break;
case 4:
ClearString(MyStringA);
printf("字符串A已清空！\n");
break;
case 5:
printf("请输入字符串B:");
scanf("%100s", strB);
StrAssign(MyStringB, strB);
Concat(ConnectStr, MyStringA, MyStringB);
printf("连接后的字符串为：");
ShowString(ConnectStr);
break;
case 6:
printf("寻找A的给定长度的子串，请输入子串的位置和长度：");
int position, length;
scanf("%d%d", &position, &length);
HString sub;
sub.ch = NULL;
if (SubString(sub, MyStringA, position, length))
{
ShowString(sub);
}
else
{
printf("子串位置错误！\n");
}
break;
case 0:
printf("感谢使用！");
exit(0);
default:
printf("非法输入，请重试！\n");
}
Menu();
}
return 0;
}
Status StrAssign(HString& T, char* chars)//生成一个其值等于串常量的串T
{
if (T.ch)//释放T原有空间
{
free(T.ch);
}
int i;
char* c;
for (i = 0, c = chars; *c; i++, c++);//求chars的长度i
if (!i)//如果串常量为空
{
T.ch = NULL;
T.length = 0;
}
else
{
if (!(T.ch = (char*)malloc(i * sizeof(char))))
{
exit(OVERFLOW);
}
for (int j = 0; j < i; j++)
{
T.ch[j] = chars[j];
}
T.length = i;
}
return OK;
}
int StrLength(HString S)//返回S的元素个数，称为串的长度
{
return S.length;
}
int StrCompare(HString S, HString T)//依据ASCII码值比较两个字符串大小并返回其差值
{
for (int i = 0; i < S.length && i < T.length; i++)
{
if (S.ch[i] != T.ch[i])
{
return S.ch[i] - T.ch[i];
}
}
return S.length - T.length;
}
Status ClearString(HString& S)//将S清为空串
{
if (S.ch)
{
free(S.ch);
S.ch = NULL;
}
S.length = 0;
return OK;
}
Status Concat(HString& T, HString S1, HString S2)//用T返回S1和S2联接而成的新串
{
if (T.ch)
{
free(T.ch);
}
if (!(T.ch = (char*)malloc((S1.length + S2.length) * sizeof(char))))
{
exit(OVERFLOW);
}
for (int i = 0; i < S1.length; i++)
{
T.ch[i] = S1.ch[i];
}
T.length = S1.length + S2.length;
for (int i = S1.length; i < T.length; i++)
{
T.ch[i] = S2.ch[i - S1.length];
}
return OK;
}
Status SubString(HString& Sub, HString S, int pos, int len)//返回串S的第pos个字符起长度为len的字串
{
if (pos<1 || pos>S.length || len<0 || len>S.length - pos + 1)
{
return ERROR;
}
if (Sub.ch)
{
free(Sub.ch);
}
if (!len)
{
Sub.ch = NULL;
Sub.length = 0;
}
else
{
if (!(Sub.ch = (char*)malloc(len * sizeof(char))))
{
exit(OVERFLOW);
}
for (int i = 0; i < len; i++)
{
Sub.ch[i] = S.ch[i + pos - 1];//由于c语言数组从0开始存取，故要向前移一位
}
Sub.length = len;
}
return OK;
}
void ShowString(HString S)//打印字符串
{
if (!S.ch)
{
printf("该字符串为空串！\n");
}
for (int i = 0; i < S.length; i++)
{
putchar(S.ch[i]);
}
printf("\n");
}
