數(shù)據(jù)結(jié)構(gòu)第2、3章習題

1、Status Insert_Sq( SqList *La, ElemType x ) / 已知順序表La 中元素依值非遞減有序排列，本算法 / 插入新的元素 x 并保持原表的有序性,返回 OK; / 若順序表空間已滿，則不再插入并返回 OVERFLOW if (La-length = La-listsize) return OVERFLOW; i = 0; while (i length & x=La-elemi) i+; for ( j=La-length; ji; j- ) La-elemj = La-elemj-1; / 右移所有值x的元素 La-elemi = x; La-le

2、ngth+; return OK; /Insert_Sq2.2設(shè)順序表設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將中的數(shù)據(jù)元素遞增有序。試寫一算法，將x 插入到順序表的適當位置上，以保持該表的有序性。插入到順序表的適當位置上，以保持該表的有序性。 2.3試寫一算法，在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表試寫一算法，在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表 操作操作LOCATE(L, X)。 int LOCATE(LinkList L , ElemType X , Status(* compare)(ElemType , ElemType) /在帶頭結(jié)點的單鏈表L中查找第1個值與X滿足compare(

3、)的元素的位序,若找到，則返回其在L中的位序，否則返回0i = 1;p = L-next;while (p & ! (* compare)( p-data , X ) p=p-next ; i +; if (p) return i; else return 0;2.4已知指針已知指針ha和和hb分別指向兩個單鏈表的頭結(jié)點，并且已知分別指向兩個單鏈表的頭結(jié)點，并且已知 兩個鏈表的長度分別為兩個鏈表的長度分別為m和和n。試寫一算法，將這兩個鏈表。試寫一算法，將這兩個鏈表 連接在一起（即令其中一個表的首元結(jié)點連在另一個表的連接在一起（即令其中一個表的首元結(jié)點連在另一個表的 最后一個結(jié)點之后）

4、，假設(shè)指針最后一個結(jié)點之后），假設(shè)指針hc指向連接后的鏈表的頭指向連接后的鏈表的頭 結(jié)點，并要求算法以盡可能短的時間完成連接運算。請分結(jié)點，并要求算法以盡可能短的時間完成連接運算。請分 析你的算法的時間復雜度。析你的算法的時間復雜度。 Connect ( LinkList *ha , LinkList *hb , LinkList *hc , int m , int n)/根據(jù)給定的兩個鏈表的長度選擇較短的鏈表并找到其尾結(jié)點。根據(jù)給定的兩個鏈表的長度選擇較短的鏈表并找到其尾結(jié)點。 LinkList *p , *q; if (mnext) p=p-next; p-next=q-next; fre

5、e(q); /釋放頭結(jié)點釋放頭結(jié)點 ha=hb=NULL; 時間復雜度時間復雜度T(n)=O(min(m,n)題題2.5刪除有序表中所有其值大于 mink 且小于maxk的數(shù)據(jù)元素。首先分析需要刪除的結(jié)點需要刪除的結(jié)點的特點： mink =maxkpreqp修改指針修改指針: pre-next = p;釋放結(jié)點釋放結(jié)點: while (q!=p) s=q-next; free(q); q=s; void delete(LinkList &L, int mink, int maxk) / delete while (p & p-datanext; /查找第一個值mink的結(jié)點if

6、 (p) / ifq=pre-next; pre-next=p; / 修改指針while (q!=p) s=q-next; delete q; q=s; / 釋放結(jié)點空間p=L-next; while (p & p-datanext; / 查找第一個值 maxk 的結(jié)點返回返回2.6 試寫一算法，對單鏈表實現(xiàn)就地逆置，即利用原表的存儲 空間將線性表（a1，a2，an）逆置為 （an，an-1，a1）。 void invert(LinkList *head) LinkList *p,*q,*r; p=head; q=p-next; while(q!=NULL) /當L沒用后續(xù)節(jié)點時終止

7、r=q-next;q-next=p;p=q;q=r; /實現(xiàn)指針后移 head-next=NULL; head=p;/p指向L的最后一個結(jié)點，現(xiàn)改為頭結(jié)點2.7 假設(shè)某個單向循環(huán)鏈表的長度大于假設(shè)某個單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點，且表中既無頭結(jié)點 也無頭指針。已知也無頭指針。已知s為指向鏈表中某個結(jié)點的指針，試編寫為指向鏈表中某個結(jié)點的指針，試編寫 算法在鏈表中刪除指針算法在鏈表中刪除指針s所指結(jié)點的前驅(qū)結(jié)點。所指結(jié)點的前驅(qū)結(jié)點。 LinkList *delnode(LinkList *s) LinkList *q,*r; q=s; while(q-next!=s) q=q-ne

8、xt; r=q; while(r-next!=q) r=r-next; r-next=s; free(q); 2.8 已知有一個單向循環(huán)鏈表，其每個結(jié)點中含三個域：已知有一個單向循環(huán)鏈表，其每個結(jié)點中含三個域：prior， data和和next，其中，其中data為數(shù)據(jù)域，為數(shù)據(jù)域，next為指向后繼結(jié)點的指針為指向后繼結(jié)點的指針 域，域，prior也為指針域，但它的值為空（也為指針域，但它的值為空（NULL）。試編寫算）。試編寫算 法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使prior成為指向成為指向 前驅(qū)結(jié)點的指針域。前驅(qū)結(jié)點的指針域。 typedef

9、struct Lnode Elemtype data; struct Lnode *next,*prior;struct LinkList *trans(struct LinkList *head) struct LinkList *p,*q; p=head-next; q=head; while(p!=head) /依次從左向右通過每個結(jié)點，對每個結(jié)點置依次從左向右通過每個結(jié)點，對每個結(jié)點置prior值。值。 p-prior=q; p=p-next; q=q-next) head-prior=q;/此時此時q指向最后一個結(jié)點，將第一個結(jié)點的指向最后一個結(jié)點，將第一個結(jié)點的 prior域指向最

10、后一個結(jié)點。域指向最后一個結(jié)點。 return(head);3.1 寫出下列程序段的輸出結(jié)果（棧的元素類型寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType 為為char）。）。 void main() Stack S;char x, y;InitStack(S);x = c; y = k;Push(S, x); Push(S, a); Push(S, y); Pop(S, x); Push(S, t); Push(S, x);Pop(S, x); Push(S, s);while(!StackEmpty(S)Pop(S, y); printf(y);printf(x); 按照四則運算加

11、、減、乘、除和冪運算按照四則運算加、減、乘、除和冪運算（）優(yōu)先關(guān)系的慣例，并仿照教材例）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對下列算術(shù)表達式求值時的格式，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：操作數(shù)棧和運算符棧的變化過程： ABC/D+EF寫出下列程序段的輸出結(jié)果（隊列中的元素類型寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElem Type為為char）。）。void main( ) Queue Q; Init Queue (Q); Char x=e; y=c; EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q,y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ; Printf(x); 簡述以下算法的功能（棧和隊列的元素