导航:首页 > 源码编译 > 线性表算法题

线性表算法题

发布时间:2025-05-24 12:03:34

⑴ 分治策略的典型例题

例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分之间的学生成绩都在表的后部。

阅读全文

与线性表算法题相关的资料

热点内容
python语法基础电子书 浏览:645
安卓手机怎么禁止调试 浏览:885
pcb编译视频 浏览:538
为什么app总闪退啊 浏览:517
网站建设服务器如何选择 浏览:284
夺灵者服务器说明什么 浏览:37
检查作业的叫什么app 浏览:674
反诈app下载页在哪里 浏览:215
安卓系统如何设置图片无水印 浏览:307
单片机贴片工艺 浏览:410
服务器列表更新什么意思 浏览:661
google香港服务器地址 浏览:91
看视频解压是什么意思 浏览:580
云服务器卡死进不去 浏览:214
解压咖啡屋完整版 浏览:869
服务器怎么样才能玩 浏览:274
linux服务器中ping服务器ip地址 浏览:857
autocad的快捷命令 浏览:451
手机安卓服务器无响应怎么办 浏览:560
建设银行app里的账户明细在哪里 浏览:129