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

1、本文算法設(shè)計(jì)題涉及的順序表和線性鏈表的類(lèi)型定義如下：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef structElem Type *elem;intlength;intlistsize;SqList;typedef struct LNodeELem Type data;Struct LNode *next;LNode,*LinkList;算法設(shè)計(jì)習(xí)題1、設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。void Insert(Sqlist &L,int e) 把e插入到

2、遞增順序表 L中int i;int *newbase;if(L.length>=L.listsize) /va 空間不足newbase=(int *)malloc( LISTINCREMENT +L.listsize)*sizeof(int);分配空間if(!newbase) exit(OVERFLOW); 分配空間不成功貝U返回L.elem=newbase;新基址L.listsize=L.listsize+ LISTINCREMENT ; 增力口存儲(chǔ)容量 for(i=L.length-1; (i>=0)&&(L.elemi>e); i-)L.elemi+1=

3、L.elemi; 大于e的元素依次后移L.elemi+1=e; 插入 eL.length+;/ 長(zhǎng)度 +12、設(shè)A=(a1,.am)和B=(b1,bn)均為順序表,A'和B '分別為A和B中除去最大共同前 綴后的子表(例如，A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),則兩者中最大的共同前綴為(x,y,y,z),在兩表中除去最大共同前綴后的子表分別為A'=(x,z)和B'=(y,x,x,z)。若A，=B，=空表，則A=B ；若A'=空表，而B(niǎo)'#空表，或者兩者都不為空表，且A'的首元小于B'的首元，則A&

4、lt;B;否則A>B。試寫(xiě)一個(gè)比較 A,B大小的算法(請(qǐng)注意：在算法中，不要破壞原表A和B,并且，也不一定先求得A'和B'才進(jìn)行比較)。char compare(SqList A, SqList B)比較順序表 A,Bint shortest;int i = 0;if(A.length > B.length) shortest = B.length;else shortest = A.length;for(i = 0; i < shortest; i+)if(A.elemi > B.elemi)return'>'以短表的長(zhǎng)度作循環(huán)i

5、f(A.elemi < B.elemi)return'<'if(A.length = B.length)return'='if(A.length > B.length)return'>'if(A.length < B.length)return'<'3、試寫(xiě)一算法在帶頭結(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

6、;n+;return(n);4、已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和no試寫(xiě)一算法將這兩個(gè)鏈表連接在一起(即令其中一個(gè)表的首結(jié)點(diǎn)連在另一個(gè)表的最后一個(gè)結(jié)點(diǎn)之后)，假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成 連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。LinkList Link( LinkList &L1 , LinkList &L2 ,LinkList &L3,int m,int n)將兩個(gè)單鏈表連接在一起,m,n分別為L(zhǎng)1與L2的長(zhǎng)度LNode *p , *q ;p=L1->next;q=L2->

7、;next;if(m>=n)while ( q->next ) q=q->next;查找短鏈表終端結(jié)點(diǎn)q->next=p; 長(zhǎng)的放在短的后面L3->next=L2->next;elsewhile ( p->next ) p=p->next;查找短鏈表終端結(jié)點(diǎn)p->next=q ;長(zhǎng)的放在短的后面L3->next=L1->next;return L3 ;時(shí)間復(fù)雜度為o(min(m.n)5、已知指針la和lb分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)單鏈表中的首結(jié)點(diǎn)。下列算法是從表la中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表lb中第j個(gè)元素之

8、前。試問(wèn)次算法是否正確？若有錯(cuò)，則請(qǐng)改正之。Status DeleteAndInsertSub (LinkedList la,LinkedList lb,int I,int j,int len)if(i<0|j<0|len<0) return INFEASIBLE;p=la;k=1;/p , q 沒(méi)有定義，ListNode *p , *q ;,while(k<i)p=p->next;k+;q=p;while(k<=len)q=q->next;k+;s=lb;k=1;while(k<j)s=s->next;k+;s->next=p;q-

9、>next=s->next;return OK;/DeleteAndInsertSub直接給出正確版本Status DeleteAndInsertSub(LinkList &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(i<=0|j<=0|len<=0) return INFEASIBLE;while(p&&a<i) w=p;p=p->next;a+;/建立一個(gè) w的空鏈表來(lái)存放

10、la的數(shù)據(jù)if(!p) return INFEASIBLE;q=p;while(q&&b<len) q=q->next; b+;if(!q) return INFEASIBLE;if(!w) la=q->next;/i=1的情況，刪除len個(gè)元素后，將len+1號(hào)元素移到第一個(gè)結(jié)點(diǎn)存放，其他元素向前移else w->next=q->next; 將刪除了 len個(gè)元素后的其他元素跟前面鏈接起來(lái)if(j=1) q->next=lb;lb=p;else while(s&&c<j-1)/如果只有j-1位，插在表后，如果有 j位，

11、插在j-1位后就是插在j位前。s=s->next;c+;if(!s) return INFEASIBLE;q->next=s->next;s->next=p; return OK;6、試寫(xiě)一算法，在無(wú)頭結(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)在無(wú)頭結(jié)點(diǎn)鏈表 L的第i個(gè)元素之前插入元素bp = L;q = (LinkList)malloc(sizeof(LNode);q.data = b;if (i = 1)q.ne

12、xt = p;L = q;插入在鏈表頭部elsewhile(-i>1) p=p->next;q->next = p->next;p->next = q;插入在第i個(gè)元素的位置/Insert7、試寫(xiě)一個(gè)算法，實(shí)現(xiàn)順序表的就地逆轉(zhuǎn)，即利用原表的存儲(chǔ)空間將線性表包,.,an)逆置為(an,an-1,.a)。void reverse(SqList &A)/順序表的就地逆置int q;for(i=0,j=A.length;i<j;i+,j-)q=A.elem i;A.elem i =A.elem j;A.elem j =q;/逆置8、試寫(xiě)一算法，對(duì)單鏈表實(shí)現(xiàn)就

13、地逆置。void reverse(LinkList &L)單鏈表的就地逆置LNode *p , *q ;p=L->next;if(p=NULL| p->next=NULL)return OK; 空表和表中只有一個(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 <std

14、lib.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OVERFLOW -2typedef structint *elem;int length;int listsize;SqList;typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;typedef struct LNodeb struct LNode *head;LNodeb;void insert(SqList &L,int e); 題目 1char compare(SqLi

15、st A, SqList B);/ 題目 2int length(LNode *head);/ 題目 3LinkList link( LNodeb &L1 , LNodeb &L2 ,LNode *p1,int m,int n);void reversea(SqList &A); 題目 7void reverse(LNodeb &L);/LNode* reverse(LinkList &L);/ 題目 8LNode *creat();單鏈表初始化int main()int *p1;int i;SqList va;p1=(int *)malloc(LIST

16、_INIT_SIZE*sizeof(int);va.elem=p1;va.listsize=LIST_INIT_SIZE;va.length=0;for(int j=0;j<10;j+)定義順序表va,并且初始化為0-9, 10個(gè)元素遞增排列va.elemj=j;va.length+; printf("please input X to insert:n"); scanf("%d",&i);insert(va,i);for(j=0;j<va.length;j+) printf("%d ",va.elemj);輸出插

17、入后的順序表int *p2;SqList vb;p2=(int *)malloc(LIST_INIT_SIZE*sizeof(int);vb.elem=p2;vb.listsize=LIST_INIT_SIZE;vb.length=0;for(j=0;j<10;j+)定義順序表vb,并且初始化為0-9, 10個(gè)元素遞增排列 vb.elemj=j;vb.length+;/vb與插入X的va比較printf("A");printf("%c",compare(va,vb);printf("Bn");實(shí)現(xiàn)順序表的就地逆轉(zhuǎn)reversea

18、(va);for(j=0;j<va.length;j+)printf("%d ",va.elemj);輸出逆置后的順序表LinkList La;LNode pa12;pa12.data=0;pa12.next=NULL;La=creat();/輸入La的元素 為0時(shí)結(jié)束int m=length(La);/ 長(zhǎng)度/定義有頭結(jié)點(diǎn)單鏈表La1LNodeb La1;La1.head=&pa12;pa12.next=La;reverse(Lal);pa=pa->next;LNode *pc1=La1.head->next;while(pc1!=NULL) p

19、rintf("%d ",pc1->data);pc1=pc1->next;/定義單鏈表LbLinkList Lb;LNode pa123;pa123.data=0;pa123.next=NULL;Lb=creat(); 輸入La的元素 為0時(shí)結(jié)束int n=length(Lb);/ 長(zhǎng)度LNodeb La2;La2.head=&pa123;pa123.next=Lb;/La和Lb連接在一起LNode *pa12345;pa12345=link(La1,La2,pa12345,m,n);while(pa12345!=NULL)printf("%d

20、 ",pa12345->data);pa12345=pa12345->next;return 0; void insert(SqList &L,int e) int i; int *newbase;if(L.length>=L.listsize) /va 空間不足分配空間 newbase=(int *)malloc(LISTINCREMENT+L.listsize)*sizeof(int); if(!newbase) exit(OVERFLOW);分配空間不成功貝U返回L.elem=newbase;新基址L.listsize=L.listsize+LISTI

21、NCREMENT;增力口存儲(chǔ)容量for(i=L.length-1; (i>=0)&&(L.elemi>e); i-)L.elemi+1=L.elemi; 大于e的元素依次后移L.elemi+1=e; 插入 eL.length+;/ 長(zhǎng)度 +1 char compare(SqList A, SqList B)int shortest;int i = 0;if(A.length > B.length) shortest = B.length;else shortest = A.length;for(i = 0; i < shortest; i+) if(A.

22、elemi > B.elemi)return'>'以短表的長(zhǎng)度作循環(huán)if(A.elemi < B.elemi)return'<'if(A.length = B.length)return'='if(A.length > B.length)return'>'if(A.length < B.length)return'<'LNode *creat()LNode *head,*p,*s;int x,cycle=1;head=(LNode*)malloc(sizeof(LNo

23、de); p=head;while(cycle)printf("nplease input the data:");scanf("%d",&x);if(x!=0)s=(LNode*)malloc(sizeof(LNode);s->data=x;printf("n %d",s->data);p->next=s;p=s;else cycle=0;head=head->next;p->next=NULL;return(head);int length(LNode *head)int n=0;LNode

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

25、ext=L1.head->next;return L2.head->next; elsewhile ( p->next ) p=p->next; 查找短鏈表終端結(jié)點(diǎn)p->next=q;/長(zhǎng)的放在短的后面p->next=L2.head->next;return L1.head->next; void reversea(SqList &A) /順序表的就地逆置int q；for(int i=0,j=A.length-1;i<j;i+,j-) q=A.elemi;A.elemi=A.elemj;A.elemj=q;/逆置void reve

26、rse(LNodeb &L)/單鏈表的就地逆置 LNode *p1,*p2,*p3;p1=L.head->next;if(p1=NULL|p1->next=NULL) ;p2=p1->next;while(p2) p3=p2->next;p2->next=p1;p1=p2;p2=p3;L.head->next->next=NULL;L.head->next=p1;/reverse/*分配總量*/typedef int ElemType;#define MAXSIZE 100 #define FALSE 0#define TRUE 1#in

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

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

29、i!=x)i+；if(i<L.length)return (i+1);elsereturn 0;/*遍歷順序表*/void ListTraverse(SeqList L) int i;if(L.length<=0)printf(" 順序表為空n");elseprintf("當(dāng)前順序表中的元素為:n");for(i=1;i<=L.length;i+)printf("%d,",L.datai-1);printf("n");/*向順序表中插入元素*/SeqList ListInsert(SeqList

30、L,int i,ElemType x)int q;if(ListFull(L)printf("overflow!n");return L;if( ListEmpty(L)L.data0=x;L.length=1;return L;if(i<0|i>L.length)printf("Not exist!n");return L;for(q=L.length-1;q>=i;q-)L.dataq+1=L.dataq;L.datai=x;L.length=L.length+1;return L;/*從順序表中刪除元素*/SeqList List

31、Delete(SeqList L,int i)int q；if(i<0|i>MAXSIZE-1)printf("Not exist! n");return L;for(q=i;q<L.length-1;q+)L.dataq=L.dataq+1;L.length=L.length-1;return L; int scan()int d;printf("請(qǐng)選擇所要進(jìn)行的操作n");printf("1.初始化2.清空3.求順序表的長(zhǎng)度 4.檢查順序表是否為空n");printf("5.檢查順序表是否為滿6.從順序表中查找元素n");printf("7.查找與給定元素的位置8.向順序表插入元素9.從順序表刪除元素n");printf("10.遍歷順序表 n");printf(" 其它鍵退出n");scanf("%d",&d);return(d);main() int quit=0;int i,location;ElemType e;SeqList L;printf("第一次操作需