线性表（顺序串）习题2015
说明：
（1）这次的作业任意选择，组合满15分即可。
（2）如无特殊说明，这里的字符串均为C语言Null-Terminated（NT）字符串！
（3）字符串可能很短，也可能来自一个文本文件，如一篇小说。
（4）除测试部分用printf打印结果外，程序中不得出现任何库函数。
（5）涉及判读字符类型的部分，可以复习一下ASCII码表。
（6）各题必须有头文件（Ex##.H）和C文件（Ex##.C），“##”为题号。
（7）应自己分析算法的时间和空间复杂度，写在程序开头部分。
（8）每一题必须附有进行功能测试的 main() 函数，能够独立编译成 exe 文件。
以下Ex01-03需要自己写出完整的函数原型，可能有难度。自告奋勇提前提交函数原型部分（*.H）供大家参考的同学，一旦被选中作为标准模板，额外奖励5分。
Ex01（本题2分）：用以下定义的SEQ_STRING字符串类型代替NT字符串，分别写出与Ansi-C标准库函数功能相应的处理函数。
Ansi-C库函数 | SEQ_STRING的处理函数 | 功能说明 |
strlen | SeqString_Length | 求串长 |
strcpy | SeqString_Copy | 串拷贝 |
strcat | SeqString_Cat | 串连接 |
strstr | SeqString_SearchStr | 子串 |
strchr | SeqString_SearchChr | 字符 |
#define MAXLEN 65535
typedef struct {
size_t len; // 串长
char data[MAXLEN+1]; // 字符数组
} SEQ_STRING;
Ex02（本题2分）：同上题，但将字符串类型定义改为如下。
#define MAXLEN 65535
typedef struct {
size_t last; // 尾字符下标
char data[MAXLEN+1]; // 字符数组
} SEQ_STRING;
Ex03（本题3分）：基于NT字符串，或Ex01或Ex02的字符串定义，写出如下函数。
函数名 | 功能说明 | |
1 | SeqString_InsertStr | 在串str的指定位置pos（从0开始）插入子串 |
2 | SeqString_DeleteStr | 在串str的指定位置pos（从0开始）删除子串 |
3 | SeqString_Sort | 将串str中字符重新排序，以参数dir指定正排序（dir=+1）或逆排序（dir=-1） |
Ex04（本题4分）：上一题，设分配给串str的空间有限，为MAXSIZE（字节数，结尾的0字符也算在内），插入后有可能超出，重写对应函数，保证不发生非法内存访问。
Ex05（本题1分）：编写字符串检查函数String_Check，查是否字符串 str 中所有字符都属于字符串 range，如果有字符不属于，返回第一个不属于的字符的指针，否则返回NULL。
Ex06（本题1分）：编写字符串对齐函数String_Align，将字符串s变为指定长度n的右对齐字符串，结果放在字符数组t中。如果s较短，在左侧填充适当数量的空格。如果s过长，截断右侧超出部分，并在尾部放一个问号“？”。问号算在长度n里。假设分配给t的空间足够。
Ex07（本题2分）：写一个函数String_Stat统计在字符串 str 中各个不同字符出现的频度并将每种字符（重复出现的字符算1种）按频度从大到小排序，存放在整数数组 freq_list 中。假设freq_list 空间足够。函数返回值为字符的种类数，也就是 freq_list 的实际长度。
Ex08（本题2分）：写函数 String_TestType 按C语言语法规则判断一个字符串的类型，用枚举类型 STRTYPE 表示。类型包括：
KEYWORD（关键字）
IDENTIFIER（标识符）
SYMBOL（符号，指{}[](),;和各种运算符）
NUMBER（数字，只考虑整数，负数前面的负号算SYMBOL，不用考虑）
CHAR（字符常量，用单引号括起来的，不用考虑转义字符）
STRINGC（字符串常量，用双引号括起来的，不用考虑转义字符）
Ex09（本题2分）：设计文本字符串编码函数String_Encode，listSrcCode和listDstCode是连个线性表，两表中元素均为字符串且一一对应，将给定字符串str中所有与listSrcCode中元素匹配的片段替换为listDstCode中相应的元素。
Ex10（本题4分）：设计一个单行文本匹配函数 String_Match，出字符串 str 中与表达式 exp 匹配的“第一个”子串，返回子串指针，NULL表示未到。参数 dir 表示查方向：dir=+1，正向（头→尾）；dir=-1，逆向（尾→头）。表达式 exp 支持通配符：“？”表示任一个字符，“*”表示从该位置开始的0到任意多个任意字符。例如：“abc*”，表示前3个是“ab
c”，之后为任意多个任意字符；“abc*def”跟“abc*”其实没有任何不同！“abc?”表示前3个是“abc”，之后为某个任意字符。
Ex11（本题5分）：设计一个字符串命令解释函数String_Process，按字符串 cmd 给出的命令对字符串 str 进行处理，结果存放在字符数组 result 里。cmd 由一串命令字符组成。4种命令字符如下：
“>”：“光标”右移1个字符。“光标”起始位置为0。如果光标已到末尾，再右移无效。
“<”：“光标”左移1个字符。如果“光标”已经到0，再左移无效。
“^”：插入。“^”之后直到下一个命令字符或串尾的字符全部插入 str 中当前位置。插入后光标自动移动到插入部分尾部。
“\”：删除。“\”后跟1个数字n，表示删除当前位置开始的n个字符。
例如：原本 str = “AA”，经过命令串“^abc<^def>^gh<<\”处理后，经过如下几步（“|”表示光标当前位置，红代表每执行一步命令后相对前一步的变化）：
|AA
^abc abc|AA
< ab|cAA
^def abdef|cAA
> abdefc|AA
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论