線性表演算法題

⑴ 分治策略的典型例題

例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分之間的學生成績都在表的後部。