《T1323-4-08-周磊-第七章作业》由会员分享,可在线阅读,更多相关《T1323-4-08-周磊-第七章作业(13页珍藏版)》请在金锄头文库上搜索。
1、第七章串的索引储存一.摘要:对于字符串的操作主要分为三个级别:1.字符级别;2.字符串级别;3 行级别1. 字符级别(1 ) 插入:数据区中申请空闲区来储存插入新字符后的整行字符串,修改索引表中该行的起始地址(StartAdress)以及串长;(2 ) 删除:数据区中删除的字符用该行中该字符后的所有字符前移来将删除的字符给覆盖掉,在索引结构中更改该行的串长;(3 ) 修改:数据区中直接找到地址修改某个字符,索引不变2. 字符级别(1 ) 插入:数据区中申请空闲区来储存插入字符串后的新行字符串,索引表中修改起始地址和串长;(2 ) 删除:数据区中删除字符串,然后用改行中删除字符串后的所有字符前移
2、覆盖掉删除的字符串,在索引表中修改串长;(3 ) 修改:如果修改的字符串和待修改的字符串等长,则数据区中直接替换,索引表不变;如果修改的字符串比待修改的字符串长,则在数据区中申请空闲区来存放修改后的字符串,索引表中改变起始地址和串长如果修改的字符串比待修改的字符串短,则在数据区中将字符串替换掉,后面还有字符则前移,索引表中修改串行。3. 行级别:插入:数据区中申请空闲区来储存新行字符串,在索引表中按照排序效果插入新的索引项,填入正确的行号,起始地址和串长。为了避免索引表中后面的索引项的移动,一般用链式储存来储存索引表;删除:数据区中不变,索引表中删除改行的索引项;修改:及对整行进行替换,故对于
3、行级别的修改即为对改行进行先删除,后再插入新行的综合实现。综上所述:串的索引储存最主要的目的是“将字符的移动控制在本行,避免移动其它行的数据,从而提高效率” 。二.串的索引储存各级别的演示:错误代码及对应的正确代码错误代码 编辑后希望的正确代码100200 300400500600700800900#include /需将字符 n 改为 mvoidy mai() /需将字符 y 删除将 n 插入int x,y; /需插入字符 ,z/需插入 cinxy;行串x+y; /需插入字符串 s=y=s-y+x; /需删除字符串+xcinvoid main()int x,y,z;cinxy;s=x+y;y
4、=s-y;cout20 21 22 23 24 25 26 27 28 29 v o i d y m a i30 31 32 33 34 35 36 37 38 39( ) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y + x ; c i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d y m a i30 31 32 33 34 35 36 37 38 39( ) i n t x
5、 ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y + x ; c i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y + x ; c i n60 6
6、1 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y + x ; c i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38
7、 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y + x ; c i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y ; c
8、 i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y ; c i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 3
9、7 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y ; c i n60 61 62 63 64 65 66 67 68 6920 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y ; c
10、 i n60 61 62 63 64 65 66 67 68 69xy;这一行到行号为 350 的新行插入后的堆空间状态图如下00 01 02 03 04 05 06 07 08 09# i n c l u d e 20 21 22 23 24 25 26 27 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y ; c i n60 61 62 63 64 65 66
11、67 68 69150 151 1512 153 154 155 156 157 158 159x y ; 插入后的索引状态图串名 串头位置 串长 串名 串头位置 串长100 00 21200 99 13300 112 11350 145 10400 123 7500 48 7600 130 15700 71 15800 87 10900 97 2 将最后一行 return 0;删除,注:只需将索引表中改行的索引删除即可,堆空间状态不变删除后的堆空间状态图如下00 01 02 03 04 05 06 07 08 09# i n c l u d e 20 21 22 23 24 25 26 27
12、 28 29 v o i d m a i (30 31 32 33 34 35 36 37 38 39) i n t x ,40 41 42 43 44 45 46 47 48 49y ; x + y ; y =50 51 52 53 54 55 56 57 58 59s - y ; c i n60 61 62 63 64 65 66 67 68 69150 151 1512 153 154 155 156 157 158 159x y ; 删除后索引表状态如下:串名 串头位置 串长 串名 串头位置 串长100 00 21200 99 13300 112 11350 145 10400 123 7500 48 7600 130 15700 71 15900 97 2