"> ');

C语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等

quange 2024-10-19 23 10/19

查找

#include <stdio.h>
void search(int a[],int n,int k)
{
	int i=n;
	a[0]=k;
	while(a[i]!=k)
		i--;
	if(i==0)
		printf("查找失败!\n");
	else 
		printf("数据是数组中的第%d个数\n",i);
}
void binary_search(int a[],int n,int k)
{
	int low,mid,high;
	int time=0;
	low=0;
	high=n-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		time=time+1;
		if(a[mid]==k)
		{
			printf("数据是数组中的第%d个数\n",mid);
			printf("查找次数为%d次\n",time);
			break;
		}
		else if(a[mid]<k)
			low=mid+1;
		else 
			high=mid-1;
	}
}
void main()
{
	int a[100];
	int i,key,n;
	printf("the length of number:");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	printf("输入要查找的数据:");
	scanf("%d",&key);
	binary_search(a,n,key); 
	search(a,n,key);  
}

二叉排序树

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 500
typedef struct Bnode
{
	int key;
	struct Bnode *left;
	struct Bnode *right;
}Bnode;
Bnode *btlnsert(int x,Bnode *root)
//root为二叉排排序树的根指针,x为新节点的关键字值
{
	Bnode *p,*q;
	int flag=0;//是否完成插入的标志
	p=(Bnode *)malloc(sizeof(Bnode));
	p->key=x;//为新节点关键字赋值
	p->right=NULL;//新节点要作为叶子结点插入
	p->left=NULL;
	if(root==NULL)
	{
		root=p;
		return p;
	}
	q=root;
	while(flag==0)//标志完成插入
	{
		if(q->key>x)
		{
			if(q->left!=NULL)
				q=q->left;
			else
			{
				q->left=p;//在左子数插入
				flag=1;
			}
		}
		else
		{
			if(q->right!=NULL)
				q=q->right;
			else
			{
				q->right=p;//在右子树插入
				flag=1;
			}
		}
	}
	return root;
}
void Inorder(struct Bnode *BD)
{
	if(BD!=NULL)
	{	
		Inorder(BD->left);
		printf("%5d", BD->key);
		Inorder(BD->right);
	}

}
void main()
{
	int i,length;
	int a[MAX];
	Bnode *root=NULL;
	printf("输入数组大小:");
	scanf("%d",&length);
	for(i=0;i<length;i++)
	{	
		scanf("%d",&a[i]);
		root=btlnsert(a[i],root);
	}
	printf("输出所给排序为:\n");
	Inorder(root);
}

二叉树层次遍历

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MS 50
struct BTreeNode
{
	char date;
	struct BTreeNode *lchild;
	struct BTreeNode *rchild;
};
typedef struct BTreeNode TNODE;
TNODE *creat(int n)
{
	int i,j;
	char x;
	TNODE *narr[100],*p,*t;
	for(j=1;j<=n;j++)
	{
		printf("input i,x:\n");
		scanf("%d,%c",&i,&x);
		p=(TNODE*)malloc(sizeof(TNODE));
		p->date=x;
		p->lchild=NULL;
		p->rchild=NULL;
		narr[i]=p;
		if(i==1)
			t=p;
		else
		{
			if(i%2==0)
				narr[i/2]->lchild=p;
			else 
				narr[i/2]->rchild=p;
		}
	}
	return(t);
}
void Inorder(struct BTreeNode *BT)
{
	if(BT!=NULL)
	{	
		Inorder(BT->lchild);
		printf("%5c", BT->date);
		Inorder(BT->rchild);
	}

}
void levelerder(struct BTreeNode *BT )
{
	struct BTreeNode *q[MS];
	int front=0,rear=0;
	if(BT!=NULL)
	{
		rear=(rear+1)%MS;
		q[rear]=BT;
	}
	while(front!=rear)
	{
		struct BTreeNode *p;
		front=(front+1)%MS;
		p=q[front];
		printf("%5c",p->date);
		if(p->lchild!=NULL)
		{
			rear=(rear+1)%MS;
			q[rear]=p->lchild;
		}
		if(p->rchild!=NULL)
		{
			rear=(rear+1)%MS;
			q[rear]=p->rchild;
		}
	}
}
void main()
{
	TNODE *t;
	int a;
	printf("input the number of BTreeNode\n");
	scanf("%d",&a);
	t=creat(a);
	Inorder(t);
	levelerder(t);
}

二叉树非递归遍历

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MS 50
struct BTreeNode
{
	char date;
	struct BTreeNode *lchild;
	struct BTreeNode *rchild;
};
typedef struct BTreeNode TNODE;
TNODE *creat(int n)
{
	int i,j;
	char x;
	TNODE *narr[100],*p,*t;
	for(j=1;j<=n;j++)
	{
		printf("input i,x:\n");
		scanf("%d,%c",&i,&x);
		p=(TNODE*)malloc(sizeof(TNODE));
		p->date=x;
		p->lchild=NULL;
		p->rchild=NULL;
		narr[i]=p;
		if(i==1)
			t=p;
		else
		{
			if(i%2==0)
				narr[i/2]->lchild=p;
			else 
				narr[i/2]->rchild=p;
		}
	}
	return(t);
}
void Preorder(struct BTreeNode *BT)
{
	if(BT!=NULL)
	{	
		printf("%5c", BT->date);
		Preorder(BT->lchild);
		Preorder(BT->rchild);
	}

}
void Inorder(struct BTreeNode *BT)
{
	if(BT!=NULL)
	{	
		Inorder(BT->lchild);
		printf("%5c", BT->date);
		Inorder(BT->rchild);
	}

}
void Postorder(struct BTreeNode *BT)
{
	if(BT!=NULL)
	{	
		Postorder(BT->lchild);
		Postorder(BT->rchild);
		printf("%5c", BT->date);
	}

}
void PreorderN(struct BTreeNode *BT)
{
	struct BTreeNode *s[20];
	int top=-1;
	struct BTreeNode *p=BT;
	while(top!=-1||p!=NULL)
	{
		while(p!=NULL)
		{
			top++;
			s[top]=p;
			printf("%5c",p->date);
			p=p->lchild;
		}
		if(top!=-1)
		{
			p=s[top];
			top--;
			p=p->rchild;
		}
	}
}
void InorderN(struct BTreeNode *BT)
{
	struct BTreeNode *s[20];
	int top=-1;
	struct BTreeNode *p=BT;
	while(top!=-1||p!=NULL)
	{
		while(p!=NULL)
		{
			top++;
			s[top]=p;
			p=p->lchild;
			
		}
		if(top!=-1)
		{
			p=s[top];
			top--;
			printf("%5c",p->date);
			p=p->rchild;
		}
	}
}
void PostorderN(struct BTreeNode *BT)
{
	struct BTreeNode *s[20];
	int top=-1,flag=1;
	struct BTreeNode *p=BT,*q;
	do{
    	while(p!=NULL)
			{
				top++;
				s[top]=p;
			    p=p->lchild;
			}

		q=NULL;
		flag=1;
			while(top!=-1&&flag)
			{
				p=s[top];	
				if(p->rchild==q)
				{
					printf("%5c",p->date);	          
					top--;
					q=p;
				}
				else
				{
				    p=p->rchild;	
					flag=0;
				}	
			}
	}while(top!=-1);
}
void main()
{
	TNODE *t;
	int a;
	printf("input the number of BTreeNode\n");
	scanf("%d",&a);
	t=creat(a);
	printf("中序遍历:");
	Inorder(t);
	printf("\n");
	InorderN(t);
    printf("\n");
	printf("先序遍历:");
	Preorder(t);
	printf("\n");
	PreorderN(t);
	printf("\n");
	printf("后序遍历:");
	Postorder(t);
	printf("\n");
	PostorderN(t);
	printf("\n");
}

二叉树建立

void preorder1(bitree *root)
{
	bitree *p,*s[100];
	int top=0;
	p=root;
	while((p!=NULL)||(top>0))
	{
		while(p!=NULL)
			(cout<<p->data<<" ";
		s[++top]=p;//
		p=p->lchild;
	}
	p=s[top--];
	p=p->rchild;
}
}
void inorder1(bitree *root)
{
	bitree *p,*s[100];
	int top=0;
	p=root;
while((p!=NULL)||(top>0))
{
	while(p!=NULL)
	{
		s[++top]=p;p=p->lchild;
	}
	{
		p=s[top--];
		cout<<p->data<<"";
		p=p->rchild;
	}
}
}
void postorder1(bitree *root)
{
	bitree *p,*s1[100];
	ints2[100],top=0,b;
	p=root;
	do
	{
		while(p!=NULL)
		{
			s1[top]=p;s2[top++]=0;
			p=p->lchild;
		}
		if(top>0)
		{
			b=s2[--top];
			p=s1[top];
			if(b==0)
			{
				s1[top]=p;
				s2[top++]=1;
				p=p->rchild;
			}
			else
			{
				cout<<p->data<<" ";
				p=NULL;
			}
		}
	}while(top>0);
}
void main()
{
	bitree *root;
	root=create();
	cout<<"先序遍历的结果"<<endl;
	preorder1(root);cout<<end1;
	cout<<"中序遍历的结果"<<end1;
	inorder1(root);cout<<end1;
	cout<<"后序遍历的结果"<<end1;
	postorder1(root);cout<<end1;
}

快速排序

#include<stdio.h>
void quicksort(int a[],int start,int end)
{
	int i,j;
	int mid;
	if(start>=end)
		return;
	i=start;
	j=end;
	mid=a[i];
	while(i<j)
	{
		while(i<j&&a[j]>mid)
			j--;
		if(i<j)
		{
			a[i]=a[j];
			i++;
		}
		while(i<j&&a[i]<=mid)
			i++;
		if(i<j)
		{
			a[j]=a[i];
			j--;
		}
	}
	a[i]=mid;
	quicksort(a,start,i-1);
	quicksort(a,i+1,end);
}
void scan(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
}
void print(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%5d",a[i]);
	}
}
void main()
{
	int a[1000];
	int s;
	int start=1,end;
	printf("输入数组长度:");
	scanf("%d",&s);
	end=s;
	scan(a,s);
	quicksort(a,start,end);
	print(a,s);
}

括号匹配

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
struct node
{
	char date;
	struct node *next;
};
struct node *top;
void push (char x)
{
	struct node *p;
	p=(struct node *)malloc(sizeof(struct node));
	p->date=x;
	p->next=top;
	top=p;
}
char pop()
{
	struct node *p;
	char x;
	if (top==NULL)
		printf("栈下溢错误!\n");
	p=top;
	x=p->date;
	top=top->next;
	free(p);
	return(x);
}
void main()
{
	char x,y; 
	printf("括号匹配,请输入括号:\n");
	scanf("%c",&x);
	while(x!='\n')
	{
		if(x=='('||x=='['||x=='{')
		{
			push(x);
			scanf("%c",&x);
		}	
		if(x==')'||x==']'||x=='}')
		{
			if (top==NULL)
			{
				printf("不匹配!\n");
				exit(1);
			}
			y=pop();
			if((y=='('&&x==')')||(y=='['&&x==']')||(y=='{'&&x=='}'))
			{	
			   scanf("%c",&x);
			}
			else
			{
				printf("不匹配!\n");
				exit(0);
			}
		}
		
	}
	if (top!=NULL)
	{
		printf("不匹配!\n");
		exit(1);
	}
	printf("括号匹配成功!\n");
}

冒泡排序

#include<stdio.h>
void bsort(int a[],int n)
{
	int temp;
	int i,j,flag;
	for(j=1;j<=n-1;j++)
	{
		flag=0;
		for(i=1;i<=n-j;i++)
			if(a[i]>a[i+1])
			{
				flag=1;
				temp=a[i];
				a[i]=a[i+1];
				a[i+1]=temp;
			}
		if(flag==0)break;
	}
}
void scan(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
}
void print(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%5d",a[i]);
	}
}
void main()
{
	int a[1000];
	int s;
	printf("输入数组长度:");
	scanf("%d",&s);
	scan(a,s);
	bsort(a,s);
	print(a,s);
}

直接插入排序

#include<stdio.h>
void selsort(int a[],int n)
{
	int i,j;
	int temp;
	for (i=1;i<=n;i++)
	{
		temp=a[i];
		j=i-1;
		while(j>=0&&temp<a[j])
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;
	}
}
void scan(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
}
void print(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%5d",a[i]);
	}
}
void main()
{
	int a[1000];
	int s;
	printf("输入数组长度:");
	scanf("%d",&s);
	scan(a,s);
	selsort(a,s);
	print(a,s);
}

直接选择排序

#include <stdio.h>
void selsort(int a[],int n)
{
	int i,j,k;
	int temp;
	for(i=1;i<=n-1;i++)
	{
		k=i;
		for (j=i+1;j<=n;j++)
			if(a[j]<a[k])
				k=j;
		if(i!=k)
		{
			temp=a[i];
			a[i]=a[k];
			a[k]=temp;
		}
	}
}
void scan(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
}
void print(int a[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%5d",a[i]);
	}
}
void main()
{
	int a[1000];
	int s;
	printf("输入数组长度:");
	scanf("%d",&s);
	scan(a,s);
	selsort(a,s);
	print(a,s);
}

- THE END -
最后修改:2024年10月19日
1

版权声明:
一、本站致力于为软件爱好者提供国内外软件开发技术和软件共享,着力为用户提供优资资源。
二、本站提供的所有下载文件均为网络共享资源,请于下载后的24小时内删除。如需体验更多乐趣,还请支持正版。
三、我站提供用户下载的所有内容均转自互联网。如有内容侵犯您的版权或其他利益的,请编辑邮件并加以说明发送到站长邮箱。站长会进行审查之后,情况属实的会在三个工作日内为您删除。

共有 0 条评论