初始化、求长度、取元素
上一节有了顺序表的结构SeqList,但还是手工往数组里放字符。这一节把2.2的五个操作在这个结构上做出来。
本节问题结构有了,
2.2的五个操作怎么在这个结构上做出来?
每个操作写成一个C函数。2.2只规定了操作"做什么",函数体要回答"怎么做"。
初始化。编辑器刚启动时,这一行一个字符都没有,程序要先有一个空表。空表就是长度为0的表:
text ┌───┬───┬───┬───┬───┐
data │ ? │ ? │ ? │ ? │ ? │ length = 0
└───┴───┴───┴───┴───┘
0 1 2 3 4
格子里画的问号,表示数组里原来有什么不知道,也无所谓。length为0,就表示没有任何格子是有效的。所以初始化只做一件事:把length设成0。
写成函数:不需要参数,没有返回值,只把表变成空表。
这一节先把顺序表定义成一个全局变量L,函数直接用它,不通过参数传递。下一节再把它改成参数。
cSeqList L; /* 全局的顺序表 */
void Init(void) {
L.length = 0;
}
函数名后面括号里的void,表示这个函数不需要参数。
求长度。显示cat时,程序要知道一共有几个字符。表里放着cat时是这样:
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
长度就记在length里,直接返回。
写成函数:不需要参数,返回长度,表不变。
cint Length(void) {
return L.length;
}
取第i个元素。显示时还要把字符一个一个取出来。还看上面这张图:第i个元素就在data[i]里,取第2个元素就是data[2],也就是t。一次下标运算就拿到,不管表有多长。
i必须在0到length−1之间。上图中data[3]、data[4]不是有效元素,取它们没有意义。
写成函数:需要位置i,返回那个元素,表不变。i不合法时,返回'\0'表示出错。
cchar Get(int i) {
if (i < 0 || i >= L.length) return '\0';
return L.data[i];
}
在第i个位置插入
在c|at里敲x,x要插在c和a之间,也就是第1个位置。这一步就是Insert(1, 'x'),结果应该是cxat。插入前:
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
x要放进data[1],可是data[1]被a占着。占着那个位置的元素怎么办?
为了保持"相邻的元素放在相邻的格子里",a和t都要往后挪一格,把data[1]腾出来。插入后:
text ┌───┬───┬───┬───┬───┐
data │ c │ x │ a │ t │ │ length = 4
└───┴───┴───┴───┴───┘
0 1 2 3 4
挪动的顺序很关键。如果从前往后挪,先把data[1]的a挪到data[2],data[2]原来的t就被覆盖,丢掉了。
所以必须从最后一个元素开始,倒着往后挪。先把t从data[2]挪到data[3],再把a从data[1]挪到data[2]。这样每次挪动的目标格子都已经空出来了。挪完,把x放进data[1],长度加1。
写成函数:需要位置i和字符x。插入可能失败,比如位置不合法、表满了,所以返回一个整数报告成败:1表示成功,0表示失败。成功时,数组和长度都变。
cint Insert(int i, char x) {
if (i < 0 || i > L.length) return 0; /* 位置不合法 */
if (L.length == MAXSIZE) return 0; /* 表满 */
for (int j = L.length; j > i; j--) /* 从后往前挪 */
L.data[j] = L.data[j - 1];
L.data[i] = x;
L.length++;
return 1;
}
带入Insert(1, 'x')走一遍。j从3开始:data[3] = data[2],把t挪到后一格。j=2:data[2] = data[1],把a挪到后一格。j=1时不满足j>1,循环结束。最后data[1] = 'x',长度变成4。
i可以等于length。这时循环一次都不执行,x直接放到末尾,就是追加。
插入的位置越靠前、表越长,要挪的元素就越多。2.7讲效率时会回来看这一点。
删除第i个元素
在cx|at里按退格,删掉的是光标前面的x。x在第1个位置,这一步就是Delete(1),结果应该回到cat。删除前:
text ┌───┬───┬───┬───┬───┐
data │ c │ x │ a │ t │ │ length = 4
└───┴───┴───┴───┴───┘
0 1 2 3 4
x删掉之后,data[1]空出一格。按"相邻的元素放在相邻的格子里",c的下一个应该是a,所以a要挪到data[1],t跟着挪到data[2]。删除后:
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ t │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
这次挪动的方向和插入相反,要从前往后。先把a从data[2]挪到data[1],直接覆盖掉要删的x,不需要先把x清空。再把t从data[3]挪到data[2]。挪完,长度减1。
注意data[3]里还留着一个t。它不用管:长度已经是3,data[3]在有效范围之外,下次插入会把它覆盖掉。有效范围靠长度来定,不靠格子里有没有东西。
写成函数:需要位置i。删除也可能失败,位置不合法时返回值为0,成功时返回值为1。成功时,数组和长度都变。
cint Delete(int i) {
if (i < 0 || i >= L.length) return 0; /* 位置不合法 */
for (int j = i; j < L.length - 1; j++) /* 从前往后挪 */
L.data[j] = L.data[j + 1];
L.length--;
return 1;
}
带入Delete(1)走一遍。j=1:data[1] = data[2],把a挪过来。j=2:data[2] = data[3],把t挪过来。j=3时不满足j<3,循环结束。长度变成3。
删除的位置越靠前、表越长,要挪的元素也越多,和插入一样。
把五个操作合起来
五个操作到齐了。用它们把2.2例题的每一步在机器上重放一遍:编辑器启动,敲c、a、t,在a和t之间敲x,再退格删掉x。
cint main(void) {
Init();
Insert(0, 'c'); /* (c) */
Insert(1, 'a'); /* (c, a) */
Insert(2, 't'); /* (c, a, t) */
Insert(2, 'x'); /* (c, a, x, t) */
Delete(2); /* (c, a, t) */
for (int i = 0; i < Length(); i++)
printf("%c", Get(i));
printf("\n"); /* 输出 cat */
return 0;
}
程序输出cat。前三次Insert都是追加到末尾,挪动循环一次都不执行;第四次插在中间,t往后挪了一格;Delete又把它挪了回来。
上一节的程序是手工往数组里放字符。这个程序只调用操作,没有碰L.data和L.length。以后都这样写。