数据结构串的应用

南京信息工程大学南京信息工程大学数据结构数据结构实验 实习 报告实验 实习 报告 实验 实习 名称 串的应用 实验 实习 日期 2015 11 2 得分 指导教师 顾韵华 系 计软院 专业 计科 年级 2014 级 班次 2 一 一 实验目的实验目的 1 掌握串的用法 二 二 实验内容实验内容 1 设计一个算法 删去串 设计一个算法 删去串 s 中从第中从第 i 个字符开始的连续个字符开始的连续 j 个字符个字符 以堆分配法表示串以堆分配法表示串 2 若 若 x 和和 y 是两个以堆分配法表示的串 请设计一个算法 找出是两个以堆分配法表示的串 请设计一个算法 找出 x 中第一个不在中第一个不在 y 中出现的字符 中出现的字符 3 一个文本串可用事先给定的字母映射表进行加密 例如 设字母映射表为 一个文本串可用事先给定的字母映射表进行加密 例如 设字母映射表为 abcdefghij ngzqtcobmu klmnopqrst helkpdawxf uvwxyz yivrsj 则字符串则字符串 encrypt 被加密为被加密为 tkzwsdf 1 写一算法将输入的文本串进行加密后输出 写一算法将输入的文本串进行加密后输出 2 写一算法 将输入的已加密文本串进行解密后输出 写一算法 将输入的已加密文本串进行解密后输出 4 实现朴素的模式匹配算法 实现朴素的模式匹配算法 三 三 设计一个算法 删去串设计一个算法 删去串 s 中从第中从第 i 个字符开始的连续个字符开始的连续 j 个字符个字符 以堆分配法表示以堆分配法表示 串串 include include include define OK 1 define ERROR 0 typedef int Status typedef struct 堆分配法表示串的类型定义堆分配法表示串的类型定义 char ch 存储区基址存储区基址 int length 串长串长 HString Status strAssign HString char c if S ch free S ch for i 0 c chars c 0 i c 求串求串 chars 的长度的长度 存于存于 i if i chars 为空串为空串 S ch NULL S length 0 else if S ch char malloc i sizeof char return ERROR for j 0 jS length i 1 return ERROR for k i j 1 m i 1 k S length k m S ch m S ch k S ch m 1 0 S length S length j return OK void printString HString S int i for i 0 i S length i printf c S ch i printf n run this program using the console pauser or add your own getch system pause or input loop int main HString S char str This is a test string printf 创建字符串创建字符串 S n if strAssign S str ERROR printf 创建的字符串创建的字符串 S 失败 失败 n return 1 printf 创建的字符串创建的字符串 S 为 为 printString S printf 删除字符串删除字符串 S 从从 3 开始的开始的 4 个字符 个字符 n strDelete S 3 4 printf 删除字符后的字符串删除字符后的字符串 S 为 为 n printString S return 0 2 若若 x 和和 y 是两个以堆分配法表示的串 请设计一个算法 找出是两个以堆分配法表示的串 请设计一个算法 找出 x 中第一个中第一个 不在不在 y 中出现的字符中出现的字符 include include include include define OK 1 define ERROR 0 define OVERFLOW 1 typedef int Status typedef struct 堆分配法表示串的类型定义堆分配法表示串的类型定义 char ch 存储区基址存储区基址 int length 串长串长 HString Status strAssign HString char c if S ch free S ch for i 0 c chars c i c 求串求串 chars 的长度的长度 存于存于 i if i ars 为空串为空串 S ch NULL S length 0 else if S ch char malloc i sizeof char exit OVERFLOW for j 0 j i j S ch j chars j S length i return OK void strSearch HString for i 0 i S1 length i int m 0 for j 0 j S2 length j if S1 ch i S2 ch j break else m if m S2 length goto l l printf c n S1 ch i int main HString S1 S2 char str1 100 str2 100 printf 输入串输入串 X gets str1 printf 输入串输入串 Y gets str2 S1 ch NULL S2 ch NULL strAssign S1 str1 strAssign S2 str2 strSearch S1 S2 return 0 3 一个文本串可用事先给定的字母映射表进行加密一个文本串可用事先给定的字母映射表进行加密 include include include define OK 1 定义常量定义常量 define ERROR 0 typedef int Status typedef struct 堆分配法表示串的类型定义堆分配法表示串的类型定义 char ch 存储区基址存储区基址 int length 串长串长 HString Status StrLength HString s 求串长求串长 return s length Status strAssign HString char c if S ch free S ch for i 0 c chars c 0 i c 求串求串 chars 的长度的长度 存于存于 i if i chars 为空串为空串 S ch NULL S length 0 else if S ch char malloc i sizeof char return ERROR for j 0 j i j S ch j chars j S length i return OK void strencrypt HString int n n StrLength s while i n switch s ch i case a s ch i n break case b s ch i g break case c s ch i z break case d s ch i q break case e s ch i t break case f s ch i c break case g s ch i o break case h s ch i b break case i s ch i m break case j s ch i u break case k s ch i h break case l s ch i e break case m s ch i l break case n s ch i k break case o s ch i p break case p s ch i d break case q s ch i a break case r s ch i w break case s s ch i x break case t s ch i f break case u s ch i y break case v s ch i i break case w s ch i v break case x s ch i r break case y s ch i s break case z s ch i j break i for i 0 i n i printf c s ch i printf n void instrencrypt HString int n n StrLength s while i n switch s ch i case n s ch i a break case g s ch i b break case z s ch i c break case q s ch i d break case t s ch i e break case c s ch i f break case o s ch i g break case b s ch i h break case m s ch i i break case u s ch i j break case h s ch i k break case e s ch i l break case l s ch i m break case k s ch i n break case p s ch i o break case d s ch i p break case a s ch i q break case w s ch i r break case x s ch i s break case f s ch i t break case y s ch i u break case i s ch i v break case v s ch i w break case r s ch i x break case s s ch i y break case j s ch i z break i for i 0 i n i printf c s ch i printf n int main HString s t char str1 100 char str2 100 printf 请输入未加密的字符串 请输入未加密的字符串 gets str1 strAssign s str1 printf 加密后的字符串为加密后的字符串为 strencrypt s printf 请输入加密的字符串请输入加密的字符串 gets str2 strAssign t str2 printf 解密后的字符串为解密后的字符串为 instrencrypt t return 0 4 朴素模式的匹配 朴素模式的匹配 include 朴素的模式匹配朴素的模式匹配 include include include define OK 1 define ERROR 0 typedef int Status typedef unsigned char HString 100 Status strAssign HString char c for i 0 c chars c 0 i c 求串求串 chars 的长度的长度 存于存于 i if i chars 为空串为空串 S 0 0 else for j 0 j i j S j 1 chars j S 0 i return OK Status Index HString S HString T int pos 返回子串返回子串 T 在主串在主串 S 中第中第 Pos 个字符之后的位置个字符之后的位置 int i pos j 1 while i S 0 else return 0 int main HString s t char str1 100 str2 100 int n k printf 请输入主串 请输入主串 gets str1 printf 请输入子串 请输入子串 gets str2 printf 请输入位置 请输入位置 scanf d strAssign s str1 strAssign t str2 k Index s t n printf d n k return 0 四 四 程序调试程序调试 1 操作结果 2 若 x 和 y 是两个以堆分配法表示的串 请设计一个算法 找出 x 中第一个不在 y 中出现 的字符 3 操作结果 4 操作结果 5 实验总结实验总结 通过这次实验 我掌握了串的用法 在做第一个实验时我不怎么会用串 在老师的帮助下我慢慢理解了 通过这次实验 我掌握了串的用法 在做第一个实验时我不怎么会用串 在老师的帮助下我慢慢理解了 然后照着老师的指导做了第二题 做加密解密的时候 我最开始就想到了用