⑴ 分治策略的典型例题
例1：二分查找
在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏情况下需要n次比较。一般来说，如果没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较。下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？
如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x<L[i]，由于L是递增排序的，因此假如x在L中的话，x必然排在L[i]的前面，所以我们只要在L[i]的前面查找x即可；如果x>L[i]，同理我们只要在L[i]的后面查找x即可。无论是在L[i]的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。
于是我们得到利用分治法在有序表中查找元素的算法。
function Binary_Search(L,a,b,x);
begin
if a>b then return(-1)
else begin
m:=(a+b) div 2;
if x=L[m] then return(m)
else if x>L[m]
then return(Binary_Search(L,m+1,b,x));
else return(Binary_Search(L,a,m-1,x));
end;
end;
在以上算法中，L为排好序的线性表，x为需要查找的元素，b,a分别为x的位置的上下界，即如果x在L中，则x在L[a..b]中。每次我们用L中间的元素L[m]与x比较，从而确定x的位置范围。然后递归地缩小x的范围，直到找到x。
例2：快速排序
快速排序的基本思想是基于分治法的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
程序代码如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin b[i]:=b[j];i:=i+1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
例3：归并排序
归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。
程序代码如下：
program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
i:integer;
procere merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
i:=l;j:=m+1;k:=l-1;
while (i<=m)and (j<=n) do
begin
k:=k+1;
if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end
else begin r2[k]:=r[j];j:=j+1 end
end;
if i<=m then
for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
if j<=n then
for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procere mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
if s=t then r1[s]:=r[s] else
begin
k:=(s+t) div 2;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b[i]:9);
writeln;
end.
⑵ 线性表在顺序存储结构上的插入和删除操作 1问题描述 在一个有n个整数的递增序列上进行插入和删除操作，其
选择题是可以有技巧的
题目说的是n和i,也就是说n和i是具有通用性的,对任何数字都成立,那么
你想想长度为5的表,你要在第四位插入一个数,是什么样的结果呢?
就是前三位不动,然后你挤进去一个第四位数,原来的第四第五位数就只能往后移了,也就是移了两个
那么2当然应该是等于5-4+1
选B
请参考
⑶ 数据结构 线性表算法 实现怎么删除最后一个元素
线性表有两种，如果是顺序存储结构，只需l->length--即可；
如果是链式存储结构，则先找到最后一个节点
typedef struct node
{
int data;
struct node *next;
}*LinkList,Node;
……
void main()
{
LinkList L;
Node *p,*q;
p=L;
q=L;
while(p->next!=NULL)
{
q=p;
p=p->next;
}
if(p!=q) /*若相等，则表示为空链表*/
{
q->next=NULL;
free(p);
}
}
⑷ 数据结构-线性表问题（严蔚敏C语言版清华大学出版社）
很简单，写算法时，要返回的传地址，不需要返回的，传值
也可以这么说，要在函数中改变的，传地址，不需要改变的，传值
比如GetElem( L, i, &e)说明e的值在函数中会改变，需要返回到主函数中，因此要传地址，而i，L只是在函数中引用一下，不要返回到主函数中
实参传入函数中时，会在内存中另开辟一个空间，比如上面在主函数中调用
GetElem( L, i, &e)；
此时在内存中复制一份
L,i，&e，因此在内存中操作L,i,是不会改变主函数中的值，而e复制的是地址(指针)，照样指向主函数中的e，因此，改变*(&e)的内容，照样能改变主函数的e的值
-----------------------------
1正确
2你能不能把算法的功能简单的说下，还有函数的各个参数的用途
前面定义和本函数无关，只要在本函数中改变，就需要传地址
⑸ 数据结构 算法设计题 有一个学生成绩线性表，用顺序存储方式进行存储，请编写一个时间复杂度较小的算法，
如果是从头到尾，见到一个满足于60分~70分之间的学生成绩，就删除，显然时间复杂度大。
可以这样去做：
1、用一个指示器i，从前往后找出第一个满足于60分~70分之间的学生成绩；
2、再用另一个指示器j，从尾部开始，由后向前找出第一个不满足于60分~70分之间的学生成绩；3、将i,j所指元素交换一下，直到两指示器相撞，删除结束，删除的操作，利用表长来实现！也就是所有60分~70分之间的学生成绩都在表的后部。
