数据结构期末考试复习--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
";
	else if(start+count-1>length) cout<<"error
"
	else{
		for (i=start-1,j=0;i<start+cout-1;i++,j++)
		{
			t[j]=s[i];
			t[j]='';
		}
	}
}

求节点在二叉排序树中层次的算法

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;
}