第四章线性代数第四节.ppt

4.4 串操作应用举例----文本编辑 main(){ float a,b,max; scanf(%f,%f,a,b); if (ab) max=a; else max=b; }; 文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，是把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。例如把源程序看成是一个文本。 为了编辑的方便，利用换行符把文本划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中。在输入程序的同时，文本编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映象。串值存放在文本工作区，而将页号和该页中的起始行号存放在页表中，行号、串值的存储起始地址和串的长度记录在行表，由于使用了行表和页表，因此新的一页或一行可存放在文本工作区的任何一个自由区中，页表中的页号和行表中的行号是按递增的顺序排列的. 文本编辑程序中设立页指针、行指针和字符指针分别指向当前操作的页、行和字符。若在某行内插入或删除若干字符，则要修改行表中该行的长度。若该行的长度超出了分配给它的存储空间，则要为该行重新分配存储空间，同时还要修改该行的起始地址。若要插入或删除一行，就要涉及行表的插入或删除。若被删除的行是所在页的起始行，要修改页表中相应页的起始行号为下一行行号。 行、页表按行、页号递增顺序存储，因此插入和删除运算需移动操作位置以后的全部表项。由于访问是以页表和行表作为索引的，所以在做行和页的删除操作时，可以只对行表和页表做相应的修改，不必删除所涉及的字符。 恺撒密码 通过将信息中每个字母在字母表中向后移动常量k，以实现加密。即映射关系为: F（a）＝（a十k）mod n 其中，a是要加密的字母，k是移动的位数，n是字母表长度。 要解密信息，则将每个字母向前移动k个字符即可。例如k=3，对于密文frpsxwhu vbvwhpv，解为computer systems。 设要加密的信息为一个串，组成串的字符均取自ASCII码中的小写英文字母（a的ASCII码值是97） ，串采用定长顺序存储，串的长度存放在数组的0号单元，串值从1号单元开始存放，写出恺撒密码的加密、解密算法。 线性表结构总结 带头结点的单链表与不带头结点的单链表的区别 增加了程序的复杂性和出现bug的机会。 例1． 判断非空单链表是否递增有序。 设头指针为first，结点由data和next两个数据项。 步骤1：p=first-next 步骤2: 当p-next不等于空，循环执行步骤3到步骤4，否则执行步骤5 步骤3: q=p-next 步骤4: 如果p-dataq-data 则 p=q 否则 返回“否” 步骤5: 返回“是” 例2、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值各不相同。 先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。 void Delsomenode(LinkList head){ ???? p=head-next;???? while(p!=NULL){????????? ?q=p;? ? r=q-next;????????? ?while(r!=NULL)?{???????????? ?? ?if(r-data==p-data)?????? ?????? ? {??q-next=r-next; free( r );? ?r=q-next;? }??????????????? else????????????? ? {? q=r;?? ?r=r-next; ?}}???????? ??p=p-next;???? ?} ?}? 例3．写一个算法，识别依次输入的一个以@为结束符的字符串的字符序列是否为形如“序列1序列2”模式的字符序列。其中序列1和序列2中都不含字符“”,且序列2是序列1的逆序列。如“a+bb+a”是属于该模式的序列，而“1+33-1”则不是。 int IsReverse() {??InitStack(s);??while((e=getchar())!=)??{????if(e==’@’) return 0;//不允许在’’之前出现’@’????push(s,e); ?? }??while( (e=getchar())!=@)??{????if(StackEmpty(s)) return 0;????pop(s,c);