整理算法設(shè)計(jì)習(xí)題完整

1、精品文檔本文算法設(shè)計(jì)題涉及的順序表和線性鏈表的類型定義如下：#define LIST.INIT_.SIZE 100#define LISTINCREMENT 10tvpedef stmctElem Type *elem;intlength;intlistsize;JSqList;tvpedef stmct LNodeELem Type data;Struct LNode *next;LNode, *LnikList;算法設(shè)計(jì)習(xí)題1、設(shè)順序表va中的數(shù)據(jù)元素遞增有序.試寫一算法,將x插入到順序表的適當(dāng)位置上,以 保持該表的有序性.void lnsert(Sqlist &L,int e)

2、把e插入到遞増順序表L中int i;int *newbase;if(L.length>=L.listsize) /va 空間缺乏newbase=(int *)malloc(LISTINCREMENT+L.listsize)*sizeof(int); 分配空間 if(!newbase) exit(OVERFLOW); 分配空間不成功那么返回L.elem=newbase;新基址L.listsize=L.listsize+LISTINCREMENT;増加存儲(chǔ)容量for(i=L.length-1; (i>=0)&&(L.elemi>e); i-)L.elemi+1=L

3、.elemi; 人于e的元素依次后移L.elemi+1=e;插入 eL.length+;長(zhǎng)度+12、設(shè)A=(ai,am)和B=(bi,bj均為順序表,A,和皮分別為A和B中除去最大共同前 綴后的子表(例如,A=(x,y,y,z,x,z),E=(x,y,y,z,y,x,x,z),那么兩者中最人的共同前綴為(x,y,y,z),在 兩表中除去最大共同前綴后的子表分別為A,=(x,z)和B,=(y»x,x,z).假設(shè)蟲=琢=空表,那么A=B； 假設(shè)A,=空表,而空表,或者兩者都不為空表,且A的首元小于3的首元,那么A<E；否 那么A>E.試寫一個(gè)比擬A,E大小的算法(請(qǐng)注意：在算

4、法中,不要破壞原表A和E,并且, 也不一定先求得A,和少才進(jìn)行比擬).char compare(SqList A, SqList B) 比擬順序表 A,Bint shortest;int i = 0;if(A.length > B.length) shortest = B.length;else shortest = Aength;for(i = 0; i < shortest; i+)if(A.elemi > B.elemi)return,>,; /以短表的長(zhǎng)度作循環(huán)if(A.elemi < B.elemi)return,<,;if(Aength = B.

5、len gthjreturn-'if(A.length > Bength)return、：if(A.length < Blength)return'v：3、試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH(L).int length(LNode *head)int n=0;LNode *p;p=head;while(p!=NULL) 結(jié)點(diǎn)不為 NULL 的時(shí)候 n+p=p->next;n+;return(n);4、指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn),并且兩個(gè)鏈表的長(zhǎng)度分別為m和 no試寫一算法將這兩個(gè)鏈表連接在一起(即令其中一個(gè)表的首結(jié)點(diǎn)連在

6、另一個(gè)表的最后一 個(gè)結(jié)點(diǎn)之后),假設(shè)指針he指向連接后的鏈表的頭結(jié)點(diǎn),并要求算法以盡可能短的時(shí)間完成 連接運(yùn)算.請(qǐng)分析你的算法的時(shí)間復(fù)雜度.LinkList Link( LinkList &L1 , LinkList &L2 丄inkList &L3,int m,int n)將兩個(gè)單鏈表連接在一起,m,n分別為L(zhǎng)1與L2的長(zhǎng)度LNode *p , *q ;p=L1.->next;,q=L2->next;if(m>=n)while ( q->next) q=q->next; 查找短鏈表終端結(jié)點(diǎn)q->next=p;/長(zhǎng)的放在短的后面L3-

7、>next=L2->next;elsewhile ( p->next) p=p->next; 查找短鏈表終端結(jié)點(diǎn)p->n ext=q; 長(zhǎng)的放在短的后面L3->next=L1->next;return L3 ;時(shí)間復(fù)雜度為o(min(m.n)5、指針la和lb分別指向兩個(gè)無頭結(jié)點(diǎn)單鏈表中的首結(jié)點(diǎn).以下算法是從表la中刪除 自第1個(gè)元素起共len個(gè)元素后,將它們插入到表lb中第j個(gè)元素之前.試問次算法是否正 確？假設(shè)有錯(cuò),那么請(qǐng)改正之.Status DeleteAndliisertSub (LnikedList la,LuikedList lbjnt L

8、int j,mt len)if(i<0|j<0|len<0) leturn INFEASIBLE;p=la;k=l;p, q 沒有定義,ListNode *p , *qwhile(k<i)p=p->next;k+;q=p;while(k<=len) q=q->next;k+;s=lb;k=l;while(k<j) s=s->next;k+;s->next=p;q->next=s->next;return OK;/DeleteAiidIiisertSub直接給出正確版本Status DeleteAndlnsertSub(Li

9、nkList &la, LinkList &lb, int i, int j, int len) LinkList p,s,q,w;p=la;s=lb;w=NULL;int a=1,b=1,c=1;if(j<=O|j<=O|len<=O) return INFEASIBLE;while(p&&avi)w=p;p=p->next;a+;建立一個(gè)w的空鏈表來存放la的數(shù)據(jù)if(!p) return INFEASIBLE;q=p;while(q&&b<len)q=q>next; b+;if(!q) return IN

10、FEASIBLE;if(!w) la=q->next; /i=1的情況,刪除len個(gè)元素后,將len+1號(hào)元素移到第一個(gè)結(jié)點(diǎn)存放,其他元素向前移else w->next=q->next; 將刪除了 len個(gè)元素后的其他元素跟前而鏈接起來ifO=1)q>next=lb;lb=p;else while(s&&c<j-1)如果只有卜1位,插在表后,如呆有j位,插在j-1位后就是插在j位前.s=s->n ext;c+;if(!s) return INFEASIBLE;q->n ext=s-ext;s>n ext=p;return OK;6

11、、試寫一算法,在無頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作INSERT(L,i,b),并和在帶頭結(jié) 點(diǎn)的動(dòng)態(tài)鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比擬.Status Insert(LinkList &L,int i,int b)/在無頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素bP = L;q = (LinkList)malloc(sizeof(LNode);q.data = b;if (i = 1)q.next = p;L = q;插入在鏈表頭部elsewhile(i>1)p=p->n ext;q->n ext = p->n ext;p->next = q;插入在第i個(gè)元素的位

12、置/lnsert7、試寫一個(gè)算法,實(shí)現(xiàn)順序表的就地逆轉(zhuǎn),即利用原表的存儲(chǔ)空間將線性表(山趣,.,)逆 置為(anan-l 31)ovoid reverse(SqList &A) 順序表的就地逆置int q;for(i=0,j=A.length;i<j;i+,j)q=A.elem i;A.elem 訂=A.elem j;A.elem j =q; 逆置8、試寫一算法,對(duì)單鏈表實(shí)現(xiàn)就地逆置.void reverse(LinkList &L)單鏈表的就地逆置LNode *p, *q；p=L->n ext;if(p=NULL| p->next=NULL)return O

13、K;/空表和表中只有個(gè)結(jié)點(diǎn)時(shí),不用逆置.while(p->next!=NULL)q= p>next;p->next=q->next; 刪除結(jié)點(diǎn)q,但未釋放q->next=L->next;L->next=q;將q插入頭結(jié)點(diǎn)之后/reverse可運(yùn)行的C程序代碼如下：#include <stdio.h>#include <stdlib.h>define LIST_INIT_SIZE 100define LISTINCREMENT 10define OVERFLOW -2tvpedef stmctiiit *elem;mt lengt

14、h;mt listsize;JSqList;tvpedef stmct LNodemt data;stmct LNode *next; LNode, *LnikList;tvpedef stmct LNodebstmct LNode *head; LNodeb;void insert(SqList &L.int e); 題目 1char conipare(SqList A, SqList E);/題目 2int length(LNode *head);/題目 3LinkList link( LNodeb &L1 , LNodeb &L2 ,LNoden);void re

15、versea(SqList &A)題目 7void reverse(LNodeb &L);/LNode* reverse(LuikList &L);題目 8LNode *cieat();/單鏈表初始化mt mam()mt *pl;inti;SqList va;pl=(int *)malloc(LIST_INIT_SIZE*siz亡of(int);va.elem=pl;va.listsize=LIST INIT SIZE:Zva.length=O;foi(mtj=0;j<10;j-H-)定義順序表va,并且初始化為0-9, 10個(gè)元素遞增排列va.elemjj;va

16、.length-H-;pnntH'please mput X to msert:iin);scanfC%d,&i);msert(va4)；fbr(j=0 ;j <va .length J+)pnntf(M%d 'va.elem|j)；輸出插入后的順序表iiit *p2;SqList vb;p2=(int *)nialloc(LIST_INIT_SIZE*sizeof(iiit);vb.elem=p2;vb.listsize=LIST INIT SIZE:Zvb.length=0;for(j=0;j<10j +)定義順序表vb,并且初始化為0-9, 10個(gè)元素

17、遞增排列vb.elemjj;vb.length-H-;/vb與插入X的va比擬pnntf(MAn);printf(M%c,compare(va,vb);實(shí)現(xiàn)順序表的就地逆轉(zhuǎn)reversea(va);fbr(j=0 ;j <va .length J+)pnntf(M%d 'va.elem|j)；輸出逆置后的順序表LinkList La;LNode pal2;pal2.data=0;pal2 .next=NULL;La=creat(); 輸入La的元素 為0時(shí)結(jié)束 int m=length(La);/ 長(zhǎng)度定義有頭結(jié)點(diǎn)單鏈表LalLNodeb Lal;Lal.head=&pa

18、l2; pal2.next=La;reverse(Lal);/pa=pa->next;LNode *pc l=La 1 .head->next;wliile(pc 1 !=NULL)printf(M%d 役 pc 1 ->data); pcl=pcl->next;定義單鏈表LbLinkList Lb;LNode pal23;pal23.data=O;pa 123.next=NULL;Lb=creat(); 輸入La的元素 為0時(shí)結(jié)束mt n=length(Lb);/ 長(zhǎng)度LNodeb La2;La2.head=&pal23;pal23.next=Lb;/La和L

19、b連接在一起LNode *pa!2345;pal2345=lHik(Lal,La2,pal23454iui)；wlule(pal2345!=NULL)printf(M%d 役 pa 12345->data); pa 12345=pa 12345->next;return 0;void uisert(SqList &L.int e) int i;mt *newbase;if(L. length>=L. listsize) /va 空間缺乏 newbase=(mt *)malloc(LISTINCREMENT+L.listsize)*sizeof(mt); 分配空間 if

20、(»newbase) exit(OVERFLOW);分配空間不成功那么返回L.elem=newbase;新基址Llistsize=L.listsize4-LISTINCRENIENT;增加存儲(chǔ)容量for(i=L.length-l; (i>=0)&&(L.elemi>e); i)L.elemi+l=L.elemi; 大于e的元素依次后移L.elemi+l=e;插入 eL.length+;長(zhǎng)度+1char conipare(SqList A, SqList B)mt shortest;mt 1 = 0;if(Aength > B.length) shor

21、test = B.length;else shortest = A.length;fbr(i = 0; i < shortest; i+)if(A.elemi > B.elemi)ieturn>r;以短表的長(zhǎng)度作循壞if(A.elemi < B.elemHjieturn1;if(Aength = B.length)retum,;if(A.length > B.length)retuint>,;if(A.length < B.length)retuni,<,;LNode *creatQLNode *head,*p.*s;iiit x,cvcle=l

22、;head=(LNode*)nialloc(sizeof(LNode); p=head;while(cycle)printf(Miiplease mput the data/*);scanfC%cr；&x);if(x!=O)s=(LNode*)nialloc(sizeof(LNode); s->data=x;printff'Xn %d*s->data);next=s;p=s;else cycle=O;head=head->next; p->next=NULL;return(head);mt length(LNode *head)iiit n=0;LNod

23、e *p;p=head;wlule(p?=NULL) 結(jié)點(diǎn)不為 NULL 的時(shí)候 n+p=p->next;n+;return(n);LinkList link( LNodeb &L1 , LNodeb &L2 ,LNoden)將兩個(gè)單鏈表連接在一起,m,ii分別為L(zhǎng)1與L2的長(zhǎng)度LNode *p , *q ;p=L 1 .head->next;q=L2.head->next;if(m>=n)wlule ( q->next) q=q->next; 查找短鏈表終端結(jié)點(diǎn)q->next=py/長(zhǎng)的放在短的后面 q->next=L 1 .h

24、ead->next;return L2.head > next;else wlule (p->next) p=p->next; 查找短鏈表終端結(jié)點(diǎn)p->next=qy/長(zhǎng)的放在短的后面 p->next=L2 .head->next;return L1 .head > next;void ieversea(SqList &A) /順序表的就地逆置mt q；fbr(mt i=O,j=A length-1 ;iq；i+,j)q=A.elemi;A elemi=A.elemj ;A.elemj=q;逆置void reverse(LNodeb &a

25、mp;L)單鏈表的就地逆置LNode *pl,*p2,*p3;pl=L.head->next;if(p 1 NULLilp 1 ->next=NULL)p2=pl->next;while(p2)p3=p2->next; p2->next=pl; pl=p2;p2=p3;L.head->next->next=NULL; L.head->next=pl;/ieverse typedef int ElemType;#define MAXSIZE 100 /*分配總址*/#define FALSE 0#define TRUE 1#in clude<

26、stdio.h>/*順序存儲(chǔ)類型*/typedef struct ElemType dataMAXSIZE;int length;SeqList;/*初始化順序表*/SeqList SeqListInit() SeqList L;L.length=0;return L;/*清空順序表*7SeqList ListClear(SeqList L) L.length=0;return L;/*求順序表長(zhǎng)度*/int ListLength(SeqList L) return(L.length);/*檢査順序表是否為空*/int ListEmpty(SeqList L) if(L.length)

27、return(FALSE);elsereturn(TRUE);/*檢査順序表是否為滿*/int ListFull(SeqList L) if(L.length= = MAXSIZE) return(TRUE);elsereturn(FALSE);/*從順序表中査找元素*/ElemType ListGet(SeqList LJnt i) ElemType e;e=L.datai-l;return(e);/*相同元素在順序表中的位迓*/int ListLocate(SeqList L,int x) int i=0;while(i<L.length&&L.datai!=x)i+

28、；if(i<L.length)return (i+1);elsereturn 0;/*遍歷順序表*/void ListTraverse(SeqList L) int i；if(L.length<=0)printfC順序表為空亍)；elseprintf("當(dāng)前順序表中的元素為:n)；for(i=l;i<=L.length;i+)printf(d丄datai-l);printfCW)；/*向順序表中插入元素*/SeqList Listinsert(SeqList LntElemType x)int q;if(ListFull(L)printfCoverflowiXn&q

29、uot;);return L;if( ListEmpty(L)L.data0=x;Len gth=l;return L;if(i<0| |i>L.length)printf("Not exist!n"); return L;for(q=L len gth l;q >=i;qL.dataq+l=L.dataq;L.datai=x;Len gth=Len gth+1; return L;/*從順序表中刪除元素*/SeqList ListDelete(SeqList Lfint i) int q；if(i<O|i>MAXSIZE-l)printf(&

30、quot;Not exist! nM); return L;for(q=i;q<L Jen gth-l;q+)L.dataq=L.dataq+l;L.length=L.length-l; return L;int sean int d;printf"請(qǐng)選擇所要進(jìn)行的操作n"printf"l.初始化2.清空3.求順序表的長(zhǎng)度4.檢査順序表是否為空n"printf"5.檢査順序表是否為滿6.從順序表中査找元素n"printfn7.查找與給定元素的位豊&向順序表插入元素9.從順序表刪除元素n"printfwlO.i0 歷順序表n"printfMK它鍵退岀nu