for i=1 to n j←1
for k=j+1 to n x← x+1 end(k) end(i)
执行次数：n*（n-1）
2.6 数据的存储结构主要有哪两种?它们之间的本质区别是什么？ 数据的存储结构：向量和链表。 本质区别：
向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。
链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。
2.8已知线性表L(a1, a2, … , an ) 元素按递增有序排列。用向量作为存储结构，试编写算法：删除表中值在c与d之间(c<=d)的元素 大于等于c 序号4 大于d
序号11
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13a14 a15
找到第1个大于等于c的元素，序号为s 找到第一个大于d的元素，序号为t L[s] ← L[t]
L[s+1] ← L[t+1]…
L[s+m] ← L[t+m] // s+m = t -1 m = t – s - 1 L[s + i ] ← L[t + i ] // i = 0 to t-s-1
i=1; // i 从1 循环到n
s = -1; // 第1个大于等于c的元素序号 t = -1; // 第1个大于d的元素序号 for i = 1 to n step -1
if s ==-1 and L[i]>=c // 找到第1个大于等于c的元素 s = i
if t == -1 and L[i] >d // 找到第1个大于d的元素 t = i ; end (i)
if s != -1 and t !=-1 i = s
while i < t and i + t – s <=n L[i] = L [i + t – s ] i++ end(while) else
return(错误 没有找到 元素在c和d之间) end(if)
for j=c to n-d+c
L[j]<--L[j+d-c]//把j+d-c项给j End(j)
N<--n-d+c//所有项数减少 Return
2.9 线性表A，B中的元素为字符串类型，用向量结构存储，试编写算法，判断B是否为A的子序列（例如A=ENGLISH ，B=LIS ，则B为A的子序列）
A[m] B[n]
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13a14 a15 A：
B： b1 b2 b3 b4 b5 b6
i=1 检查A中第1个元素开始的字符串是否与B匹配 i=2 检查A中第2个元素开始的字符串是否与B匹配 … …
i= m – n + 1 检查 A中 第(m-n+1)个元素开始的字符串是否与B匹配
A[m] B[n]
if ( m if j>n then return( A字符串中第i个字符开始的子串与B匹配 ) end(i) renturn (找不到匹配的子串) 设A，B两个线性表的元素个数为m，n If (m<=n)then{return} For i=0 to n-1 a=A[i] for j=0 to m-1 if(a=B[j])then{b++} end(j) end(i) if(b=m)then{B 为A的子集} return 2.11写一个将向量L（a1 ，a2， an）倒置的算法。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13a14 a15 对L(a1，a2, ... ..., an ) 如果是奇数个元素，则 1, 15 交换 1, n 交换 2，14 交换 2, n-1 交换 3，13 交换 3，n-2 交换 4，12 交换 4，n-3 交换 5，11 交换 5，n-4 交换 6，10 交换 6，n-5 交换 7，9 交换 7，n-6 交换 8，8 交换 8，n-7 交换 9，7 交换 9，n-8 交换？ 停止！！！ a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13a14 a15 如果是偶数个元素，则 1，14 交换 1, n 交换 2，13 交换 2, n-1 交换 3，12 交换 3，n-2 交换 4，11 交换 4，n-3 交换 5，10 交换 5，n-4 交换 6，9 交换 6，n-5 交换 7，8 交换 7，n-6 交换 8，7 交换？ 8，n-7 交换？ 停止！！！！ 小结：n个元素倒置的算法是， i = 1 while ( i a[i] 与 a[n-i+1] 交换 i++ end(while) 2.12试编写算法求已知单链表长度，并考虑表空的情况。 head p = head i = 0 While(p!=nil) //表不为空 P<-- next(p)//移动到下一个元素 i++ End(while) Return i //返回数据的个数 2.13试编写算法删除单链表中第k个结点。GETNODE(q) GETNODE(p) q<-head For i=1 to k-1 q<-next(q) End(i) P<-next(q);next(q)<-next(p) Ret(p) Return ^
相关推荐：
loading