整理算法设计习题完整

1、精品文档本文算法设计题涉及的顺序表和线性链表的类型定义如下：#define LIST.INIT_.SIZE 100#define LISTINCREMENT 10tvpedef stmctElem Type *elem;intlength;intlistsize;JSqList;tvpedef stmct LNodeELem Type data;Struct LNode *next;LNode, *LnikList;算法设计习题1、设顺序表va中的数据元素递增有序.试写一算法,将x插入到顺序表的适当位置上,以 保持该表的有序性.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;増加存储容量for(i=L.length-1; (i>=0)&&(L.elemi>e); i-)L.elemi+1=L

3、.elemi; 人于e的元素依次后移L.elemi+1=e;插入 eL.length+;长度+12、设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).假设虫=琢=空表,那么A=B； 假设A,=空表,而空表,或者两者都不为空表,且A的首元小于3的首元,那么A<E；否 那么A>E.试写一个比拟A,E大小的算法(请注意：在算

4、法中,不要破坏原表A和E,并且, 也不一定先求得A,和少才进行比拟).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,>,; /以短表的长度作循环if(A.elemi < B.elemi)return,<,;if(Aength = B.

5、len gthjreturn-'if(A.length > Bength)return、：if(A.length < Blength)return'v：3、试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L).int length(LNode *head)int n=0;LNode *p;p=head;while(p!=NULL) 结点不为 NULL 的时候 n+p=p->next;n+;return(n);4、指针ha和hb分别指向两个单链表的头结点,并且两个链表的长度分别为m和 no试写一算法将这两个链表连接在一起(即令其中一个表的首结点连在

6、另一个表的最后一 个结点之后),假设指针he指向连接后的链表的头结点,并要求算法以尽可能短的时间完成 连接运算.请分析你的算法的时间复杂度.LinkList Link( LinkList &L1 , LinkList &L2 丄inkList &L3,int m,int n)将两个单链表连接在一起,m,n分别为L1与L2的长度LNode *p , *q ;p=L1.->next;,q=L2->next;if(m>=n)while ( q->next) q=q->next; 查找短链表终端结点q->next=p;/长的放在短的后面L3-

7、>next=L2->next;elsewhile ( p->next) p=p->next; 查找短链表终端结点p->n ext=q; 长的放在短的后面L3->next=L1->next;return L3 ;时间复杂度为o(min(m.n)5、指针la和lb分别指向两个无头结点单链表中的首结点.以下算法是从表la中删除 自第1个元素起共len个元素后,将它们插入到表lb中第j个元素之前.试问次算法是否正 确？假设有错,那么请改正之.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+;建立一个w的空链表来存放la的数据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个元素后,将len+1号元素移到第一个结点存放,其他元素向前移else w->next=q->next; 将删除了 len个元素后的其他元素跟前而链接起来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、、试写一算法,在无头结点的动态单链表上实现线性表操作INSERT(L,i,b),并和在带头结 点的动态链表上实现相同操作的算法进行比拟.Status Insert(LinkList &L,int i,int b)/在无头结点链表L的第i个元素之前插入元素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个元素的位

12、置/lnsert7、试写一个算法,实现顺序表的就地逆转,即利用原表的存储空间将线性表(山趣,.,)逆 置为(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、试写一算法,对单链表实现就地逆置.void reverse(LinkList &L)单链表的就地逆置LNode *p, *q；p=L->n ext;if(p=NULL| p->next=NULL)return O

13、K;/空表和表中只有个结点时,不用逆置.while(p->next!=NULL)q= p>next;p->next=q->next; 删除结点q,但未释放q->next=L->next;L->next=q;将q插入头结点之后/reverse可运行的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个元素递增排列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个元素

17、递增排列vb.elemjj;vb.length-H-;/vb与插入X的va比拟pnntf(MAn);printf(M%c,compare(va,vb);实现顺序表的就地逆转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时结束 int m=length(La);/ 长度定义有头结点单链表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时结束mt n=length(Lb);/ 长度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;增加存储容量for(i=L.length-l; (i>=0)&&(L.elemi>e); i)L.elemi+l=L.elemi; 大于e的元素依次后移L.elemi+l=e;插入 eL.length+;长度+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;以短表的长度作循坏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) 结点不为 NULL 的时候 n+p=p->next;n+;return(n);LinkList link( LNodeb &L1 , LNodeb &L2 ,LNoden)将两个单链表连接在一起,m,ii分别为L1与L2的长度LNode *p , *q ;p=L 1 .head->next;q=L2.head->next;if(m>=n)wlule ( q->next) q=q->next; 查找短链表终端结点q->next=py/长的放在短的后面 q->next=L 1 .h

24、ead->next;return L2.head > next;else wlule (p->next) p=p->next; 查找短链表终端结点p->next=qy/长的放在短的后面 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>/*顺序存储类型*/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;/*求顺序表长度*/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("当前顺序表中的元素为: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"请选择所要进行的操作n"printf"l.初始化2.清空3.求顺序表的长度4.检査顺序表是否为空n"printf"5.检査顺序表是否为满6.从顺序表中査找元素n"printfn7.查找与给定元素的位豊&向顺序表插入元素9.从顺序表删除元素n"printfwlO.i0 历顺序表n"printfMK它键退岀nu