算法设计习题(完整)

1、本文算法设计题涉及的顺序表和线性链表的类型定义如下：#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;算法设计习题1、设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。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 ; 增力口存储容量 for(i=L.length-1; (i>=0)&&(L.elemi>e); i-)L.elemi+1=

3、L.elemi; 大于e的元素依次后移L.elemi+1=e; 插入 eL.length+;/ 长度 +12、设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'#空表，或者两者都不为空表，且A'的首元小于B'的首元，则A&

4、lt;B;否则A>B。试写一个比较 A,B大小的算法(请注意：在算法中，不要破坏原表A和B,并且，也不一定先求得A'和B'才进行比较)。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'>'以短表的长度作循环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、试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。int length(LNode *head)int n=0;LNode *p;p=head;while(p!=NULL)结点不为 NULL 的时候 n+p=p->next

6、;n+;return(n);4、已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和no试写一算法将这两个链表连接在一起(即令其中一个表的首结点连在另一个表的最后一个结点之后)，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成 连接运算。请分析你的算法的时间复杂度。LinkList Link( LinkList &L1 , LinkList &L2 ,LinkList &L3,int m,int n)将两个单链表连接在一起,m,n分别为L1与L2的长度LNode *p , *q ;p=L1->next;q=L2->

7、;next;if(m>=n)while ( q->next ) q=q->next;查找短链表终端结点q->next=p; 长的放在短的后面L3->next=L2->next;elsewhile ( p->next ) p=p->next;查找短链表终端结点p->next=q ;长的放在短的后面L3->next=L1->next;return L3 ;时间复杂度为o(min(m.n)5、已知指针la和lb分别指向两个无头结点单链表中的首结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之

8、前。试问次算法是否正确？若有错，则请改正之。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 没有定义，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+;/建立一个 w的空链表来存放

10、la的数据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个元素后，将len+1号元素移到第一个结点存放，其他元素向前移else w->next=q->next; 将删除了 len个元素后的其他元素跟前面链接起来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、试写一算法，在无头结点的动态单链表上实现线性表操作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.ne

12、xt = p;L = q;插入在链表头部elsewhile(-i>1) p=p->next;q->next = p->next;p->next = q;插入在第i个元素的位置/Insert7、试写一个算法，实现顺序表的就地逆转，即利用原表的存储空间将线性表包,.,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、试写一算法，对单链表实现就

13、地逆置。void reverse(LinkList &L)单链表的就地逆置LNode *p , *q ;p=L->next;if(p=NULL| p->next=NULL)return OK; 空表和表中只有一个结点时，不用逆置。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 <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个元素递增排列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个元素递增排列 vb.elemj=j;vb.length+;/vb与插入X的va比较printf("A");printf("%c",compare(va,vb);printf("Bn");实现顺序表的就地逆转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时结束int m=length(La);/ 长度/定义有头结点单链表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时结束int n=length(Lb);/ 长度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;增力口存储容量for(i=L.length-1; (i>=0)&&(L.elemi>e); i-)L.elemi+1=L.elemi; 大于e的元素依次后移L.elemi+1=e; 插入 eL.length+;/ 长度 +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'>'以短表的长度作循环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)结点不为 NULL 的时候 n+p=p->next;n+;return(n);LinkList link( LNodeb &L1 , LNodeb &L2 ,LNode *p1,int m,int n)将两个单链表连接在一起，m,n分别为L1与L2的长度LNode *p , *q ;p=L1.head->next;q=L2.head->next;if(m>=n)while ( q->next ) q=q->next; /查找短链表终端结点q->next=p;/长的放在短的后面q->n

25、ext=L1.head->next;return L2.head->next; elsewhile ( p->next ) p=p->next; 查找短链表终端结点p->next=q;/长的放在短的后面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>/*顺序存储类型*/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;/*求顺序表长度*/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("当前顺序表中的元素为: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("请选择所要进行的操作n");printf("1.初始化2.清空3.求顺序表的长度 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("第一次操作需