1.3 設n是正整數。試寫出下列程式段中用記號「△」標註的語句的頻度:
(2) i=1; k=0;
do while(i<=n-1)
當n=1時,執行1;
當n>=2時,執行n-1次;
(3) i=1; k=0;
do while(i==n);
當n=2時,執行2次;
當n!=2時,執行1次;
(4) i=1; j=0;
while(i+j≤n)
執行n次;
(5) x=n; y=0; //n是不小於1的常數
while(x>=(y+1)*(y+1))
執行向下取整)
(6) x=91; y=100;
while ( y>0 )
if(x>100)
else x++ ;
}if語句執行100次
(7) for( i=0; ifor( j=i; jfor( k=j; kx+=2;
過程:第二章2.3 已知順序表la中資料元素按非遞減有序排列。試寫乙個演算法,將元素x插到la的合適位置上,保持該錶的有序性。
思路:先判斷線性表的儲存空間是否滿,若滿返回error;否則從後向前先移動資料,找到合適的位置插入。
status insert_sqlist(sqlist &la,int x)//把x 插入遞增有序表la 中
//insert_sqlist
2.5 試寫乙個演算法,實現順序表的就地逆置,即在原表的儲存空間將線性表(a1,a2, ..., an-1,an)逆置為(an,an-1, ..., a2,a1)
//思路就是兩個指示變數i,j同時分別從順序表的開始和結尾處相向改變
void reverse(sqlist &a)//順序表的就地逆置
}//reverse
2.7 已知線性表l採用順序儲存結構存放,對兩種不同情況分別寫出演算法,刪除l中多餘的元素,使得l中沒有重複元素:(1)l中資料元素無序排列;(2)l中資料元素非遞減有序排列。
void delete_sameelem(sqlink &l, int l.length)//end while
}//end functoion
2.8 已知線性表l採用鏈式結構存放。對兩種不同情況分別寫出演算法,刪除l中值相同的多餘元素,使得l中沒有重複元素:
(1)l中資料元素無序排列;(2)l中資料元素非遞減有序排列。
(1)l中資料元素無序排列;
思路:由於是無序排列,需要線性表中每個元素都要相互進行比較。
status listdelete(linklist &l)//l是帶頭結點的線性表
//else
}//while
p=p->next;q=p->next;//開始後一結點的尋找
return ok;
}//listdelete
(2)l中資料元素非遞減有序排列。
思路:由於是有序的,遍歷一次線性表就行了
status listdelete (linklist &l)
//if
else //else
p->next=q;p=q;q=p->next;//刪除值重複的結點,並修改相應的指標
return ok;
}//listdelete
2.9 設有兩個非遞減有序的單鏈表a,b。請寫出演算法,將a和b就地歸併成乙個按元素值非遞增有序的單鏈表。
// 將合併逆置後的結果放在c表中,並刪除b表
status listmergeoppose_l(linklist &a,linklist &b,linklist &c)
else
}while(pa)
while(pb)
pb=b;
free(pb);
return ok;
}2.13 設以帶頭結點的雙向迴圈鍊錶表示的線性表l=(a1,a2,a3,...,an)。
試寫一時間複雜度為o(n)的演算法,將l改造為l=(a1,a3,...,an,...,a4,a2)。
void reform(dulinkedlist &l)//按1,3,5,...4,2 的順序重排雙向迴圈鍊錶l 中的所有結點
//p指向最後乙個奇數結點
if(p->next==l) //結點個數是奇數,使最後乙個奇數結點next指向最後乙個偶數結點
p->next=l->pre->pre;
else//結點個數是偶數,使最後乙個奇數結點next指向最後乙個偶數結點
p->next=l->pre;
p=p->next; //此時p 指向最後乙個偶數結點
while(p->pre->pre!=l)
p->next=l;//最後乙個結點next指向頭結點
調整了next 鏈的結構,此時pre 鏈仍為原狀
//調整pre 鏈的結構
for(p=l;p->next!=l;p=p->next) p->next->pre=p;
l->pre=p; //頭結點的pre指向a2結點
}//reform
第三章棧和佇列
3.6 試寫乙個演算法,識別依次讀入的乙個以@為結束符的字串行是否為形如「序列1&序列2」模式的字串行。其中,序列1和序列2中都不包含字元『&』,且序列2是序列1的逆序。
例如,「a+b&b+a」是屬於該模式的字串行,而「1+3&3-1」則不是。
演算法:int seqreverse()//判斷輸入的字串中'&'前和'&'後部分是否為逆串,是則返回1,否則返回0
//序列1輸入完畢
while( (e=getchar())!='@')
if(!stackempty(s))
return 0;//序列1元素還有剩餘
return 1;
}//isreverse
3.7 假設乙個算術表示式中可以包含三種符號:圓括號「(」和「)」、方括號「[」和「]」、花括號「」,且這三種括號可按任意次序巢狀使用。
編寫判別給定表示式中所含的括號是否正確配對的演算法(已知表示式已存入資料元素為字元的順序表中)。
演算法:status brackettest(char *str)//判別表示式中三種括號是否匹配
{initstack(s);
for(p=str;*p;p++)
{if(*ppp=='{' )
資料結構 C語言版
考試大綱將陸續公布 計算機應用基礎考試大綱 主要考查計算機應用基礎知識,參考參考用書課後練習內容。其它同型別的計算機應用基礎教材均可作為複習用書 高等數學考試大綱 一 函式 二 極限 1 數列極限的概念 2 數列極限的性質 3 函式極限的概念 4 函式極限的定理 5 無窮小量和無窮大量 6 兩個重要...
資料結構 c語言版 複習
積少成多,爭取每天進步一點。資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科 2.資料結構被形式地定義為 d r 其中d是資料元素的有限集合 r是d上的關係有限集合 3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運...
資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合,r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...