数据结构期末考试复习--2
算法设计题--2
six
顺序表中实现二分查找
struct record { int key; int others; }; int bisearch(struct record r[],int k) { int low = 0,mid,high = n-1; while(low<=high) { mid(low+high)/2; if(r[mid].key==k) return (mid+1); else if(r[mid].key>k) high = mid-1; else low = mid+1; } return 0; }
判断二叉树是否为二叉排序树
int minnum = -32768,flag = 1; typedef struct node { int key; struct node *lchild,*rchild; }bitree; void inoeder(bitree *bt) { if(bt!=0) { inoeder(bt->lchild); if(minnum>bt->key) flag = 0; minnum = bt->key; inoeder(bt->rchild); } }
链式结构上直接插入排序
void straightinsertsort(lklist *&head) { lklist *s,*p,*q; int t; if(head==0||head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next) { for(s=head;s!=q->next;s=s->next) if(s->data>p->data) break; if(s==q->next) q=p; else{ q->next=p->next; p->next=s->next; s->next=p; t=p->data; p->data=s->data; s->data=t; } } }
seven
链式结构实现简单选择排序
void simpleselectsorlklist(lklist *&head) { lklist *p,*q,*s; int min,t; if(head==0||head->next==0) return; for(q=head;q!=0;q=q->next) { min=q->data; s=q; for(p=q->next;p!=0;p->p->next) if(min>p->data){ min = p->data; s=p; } if(s!=q) { t=s->data; s->data=q->data; q->data=t; } } }
顺序表上实现求子串的算法
void substring(char s[],long start,long count,char t[]) { long i,j,length = strlen(s); if(start<1||start>length) cout<<"error\n"; else if(start+count-1>length) cout<<"error\n" else{ for (i=start-1,j=0;i<start+cout-1;i++,j++) { t[j]=s[i]; t[j]='\0'; } } }
求节点在二叉排序树中层次的算法
int lev=0; typedef struct node { int key; struct node *lchild,*rchild; }bitree; void level(bitree *bt,int x) { if(bt!=0) { lev++; if(bt->key==x) return; else if(bt->key>x) level(bt->lchild,x); else level(bt->rchild,x); } }
eight
求链式结构上二叉树节点个数
void countnode(bitree *bt,int &count) { if(bt!=0) { count++; countnode(bt->lchild,count); countnode(bt->rchild,count); } }
设计将无向图的邻接矩阵变为邻接表的算法
typedef struct { int vertex[m]; int edge[m][m]; }gadjmatix; typedef struct node1 { int info; int adjvertex; struct node1 *nextarc; }glinklisnode; typedef struct node2 { int vertexinfo; glinklisnode *firstarc; }glinkheadnode; void adjmatrixtoadilist(gadjmatix g1[],glinkheadnode g2[]) { int i,j; glinklisnode *p; for(i=0;i<=n;i++) { g2[i].firstarc=0; } for(i=0;i<=n;i++) { for(j=0;j<=n-1;j++) { if(g1.edge[i][j]==1) { p=(glinklisnode *)malloc(sizeof(glinklisnode)); p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklisnode *)malloc(sizeof(glinklisnode)); p->adjvertex=i; p->next=g[i].firstarc; g[i].firstarc=p; } } } }
nine
求二叉树上所有节点之和
void sum(bitree *bt,int &s) { if(bt!=0) { s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s); } }
设计将所有奇数移到偶数之前的算法
void quickpss(int r[],int s,int t) { while(i<j) { while(i<j&&r[j]%2==0) j=j-1; if(i<j) { r[i]=r[j]; i=i+1; } while(i<j&&r[j]%2!=0) i=i+1; { if(i<j) { r[j]=r[i]; j=j-1; } } } }
判断链表是否递增
int isriselk(lklist *head) { if(head==0||head->next==0) { return 1; }else{ for(q=head,p=head->next;p!=0;q=p,p=p->next) { if(q->data>p->data) return 0; } } return 1; }
ten
链式结构上合并排序
void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s = hc = 0; while(ha!=0&&hb!=0) { if(ha->data<hb->data) { if(s==0) hc=s=ha; else{ s->next = ha; ha=ha->next; } }else{ f(s==0) hc=s=hb; else{ s->next = hb; hb=hb->next; } } } if(ha==0){ s->next = hb; }else{ s->next=ha; } }
二叉排序树上查找节点 x
bitree *bisearch(bitree *t,int key) { bitree *p = t; while(p!=0) { if(p->key==key) return p; else if(p->key>key) p=p->lchild; else p=p->rchild; } return 0; }
设计算法将关键序列调整为堆
void adjustheap(int r[],int n) { int j=n,i=j/2;temp=r[j-1]; while(i>=1) if(temp>=r[i-1]) break; else{ r[j-1]=r[i-1]; j=i; i=i/2; } r[j-1]=temp; }
相关推荐
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30