Sắp xếp hòa nháºp:
void Merge(int a[], int d1, int c1, int c2, int b[])
{
int i,j,k;
i=k=d1;
j=c1+1;
while ((i<=c1) && (j<=c2))
if (a[i]<a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
while (i<=c1)
b[k++]=a[i++];
while (j<=c2)
b[k++]=a[j++];
}
void mpass(int a[], int b[], int n, int l)
{
int i,j;
i=-1;
while (i+2*l<n)
{
Merge(a,i+1,i+l,i+2*l,b);
i+=2*l;
}
if (i+l<n-1)
Merge (a,i+1,i+l,n-1,b);
else
for (j=i+1;j<n;j++)
b[j]=a[j];
}
void mergesort(int a[], int n)
{
int l, b[100];
l=1;
while (l<n)
{
mpass(a,b,n,l);
l=2*l;
mpass(b,a,n,l);
l=2*l;
}
}
Sắp xếp lá»±a chá»n:
void selectsort(int a[], int n)
{
for (int i=1; i<=n-1; i++)
{
int jmin=i+1;
for (int j=i+2; j<=n;j++)
{
if (a[jmin]<a[j])
jmin=j;
}
doicho(a[min],a[i]);
}
}
Quick Sort
void quick(int l,int r, int a[])
{
if (l<r)
{
int i,j,x,tg;
x=a[(l+r)/2];
i=l;
j=r;
while (i<=j)
{
while (a[i]<x)
i++;
while (a[j]>x)
j--;
if (i<=j)
{
tg=a[i];
a[i]=a[j];
a[j]=tg;
i++;
j--;
}
}
quick(l,j,a);
quick(i,r,a);
}
}
Sắp xếp vun Ä'á»'ng:
void push(int i, int a[], int n)
{
int j, tg;
while (i<=n/2-1)
{
j=2*i+1;
if ((j<n-1) && (a[j]<a[j+1]))
j++;
if (a[j]>a[i])
{
tg=a[i];
a[i]=a[j];
a[j]=tg;
i=j;
}
else i=n;
}
}
void push2(int i, int a[], int n)
{
int j, tg=a[i];
while (i<=n/2-1)
{
j=2*i+1;
if ((j<n-1) && (a[j]<a[j+1]))
j++;
if (a[j]>a[i])
{
a[i]=a[j];
i=j;
}
else n=i;
}
a[i]=tg;
}
void heap(int a[], int n)
{
int i, tg;
for (i=n/2-1;i>=0;i--)
push(i,a,n);
for (i=n-1;i>0;i--)
{
tg=a[0];
a[0]=a[i];
a[i]=tg;
push(0,a,i);
}
}
void heap2(int a[], int n)
{
int i, tg;
for (i=n/2-1;i>=0;i--)
push(i,a,n);
for (i=n-1;i>0;i--)
{
tg=a[0];
a[0]=a[i];
a[i]=tg;
push(0,a,i);
}
}
Tìm kiếm cây nhị phân:
int tkcnp(int x, node *t)
{
while (t!=NULL)
{
if (t->key==x) return 1;
if (t->key>x) t=t->left;
else t=t->right;
}
return 0;
}
Tìm kiếm nhị phân:
int tkcnp(int x, node *t)
{
while (t!=NULL)
{
if (t->key==x) return 1;
if (t->key>x) t=t->left;
else t=t->right;
}
return 0;
}
Tìm kiếm trên cây nhị phân Ä'ã sắp:
int tktt4(int x, int a[], int n)
{
int i=0;
a[n]=x;
while (a[i]<x) i++;
if (i<n && a[i]==x) return 1;
return 0;
}
Tìm kiếm tuần tự:
int tktt(int x, int a[], int n)
{
int i=0;
while (i<n && a[i]!=x) i++;
if (i<n) return 1;
return 0;
}
int tktt2(int x, int a[], int n)
{
int i=0;a[n]=x;
while (a[i]!=x) i++;
if (i<n) return 1;
return 0;
}
int tktt3(int x, int a[], int n)
{
if (n==0) return 0;
if (a[n-1]==x) return 1;
return tktt3(x,a,n-1);
}
Danh sách móc ná»'i Ä'Æ¡n:
#include<conio.h>
#include<string.h>
#include<iostream.h>
#include<stdio.h>
#include<alloc.h>
#include<iomanip.h>
struct sv
{
char masv[10];
char hoten[20];
float dtb;
};
struct dssv
{
sv ptu;
dssv*next;
}*l;
void nhap (dssv*&l)
{
dssv*q;
char s[10];
l=new dssv; q=l;
cout<<"nhap ma sv:";
gets(l->ptu.masv);
cout<<"nhap ho ten:";
gets(l->ptu.hoten);
cout<<"nhap dtb:";
cin>>l->ptu.dtb;
cout<<"nhap ma sv:";
gets(s);
while (strcmp (s,""))
{
q->next=new dssv;
q=q->next;
strcpy (q->ptu.masv,s);
cout<<"nhap hoten:";
gets(q->ptu.hoten);
cout<<"nhap dtb:";
cin>>q->ptu.dtb;
cout<<"nhap masv:";
gets(s);
}
q-> next = NULL;
}
void hien(dssv*l)
{
while (l!= NULL)
{
cout<<l->ptu.masv<<setw(20)<<l->ptu.hoten;
cout<<setw(10)<<l->ptu.dtb<<"
";
l=l->next;
}
}
void sapxep(dssv*&l)
{
dssv*p,*q;sv tg;
if(l!=NULL)
{
p=l;
while(p->next!=NULL)
{
q=p->next;
while(q!=NULL)
{
if(p->ptu.dtb>q->ptu.dtb)
{
tg=q->ptu;
q->ptu=p->ptu;
p->ptu=tg;
}
q=q->next;
}
p=p->next;
}
}
}
void chend(dssv*&l)
{
dssv *q=new dssv;
cout<<"nhap ma sv:";
gets(q->ptu.masv);
cout<<"nhap ho ten:";
gets(q->ptu.hoten);
cout<<"nhap dtb:";
cin>>q->ptu.dtb;
q->next=l;
l=q;
}
void chenc(dssv*&l)
{
dssv *p,*q=new dssv;
cout<<"nhap ma sv:";
gets(q->ptu.masv);
cout<<"nhap ho ten:";
gets(q->ptu.hoten);
cout<<"nhap dtb:";
cin>>q->ptu.dtb;
q->next=NULL;
if (l==NULL) l=q;
else
{
p=l;
while(p->next!=NULL) p=p->next;
p->next=q;
}
}
void chensap(dssv*&l)
{
dssv *p,*q=new dssv;
cout<<"nhap ma sv:";
gets(q->ptu.masv);
cout<<"nhap ho ten:";
gets(q->ptu.hoten);
cout<<"nhap dtb:";
cin>>q->ptu.dtb;
if (l==NULL||q->ptu.dtb<l->ptu.dtb)
{
q->next=l;
l=q;
}
else
{
p=l;
while(p->next!=NULL&&p->next->ptu.dtb<q->ptu.dtb) p=p->next;
q->next=p->next;
p->next=q;
}
}
void delc(dssv*&l)
{
if(l!=NULL)
{
dssv*p=l,*q;
if (l->next==NULL)
{ delete l;l=NULL; }
else
{
while (p->next->next!=NULL) p=p->next;
q=p->next;
p->next=NULL;
delete q;
}
}
}
void deld(dssv*&l)
{
if(l!=NULL)
{
dssv*p=l;
l=l->next;
delete p;
}
}
void del(dssv *&l)
{
if(l!=NULL)
{
dssv*p=l,*q;
while (p->next!=NULL)
if (p->next->ptu.dtb<5)
{
q=p->next;p->next=q->next;delete q;
}
else p=p->next;
if(l->ptu.dtb<5)
{
q=l;l=l->next;delete q;
}
}
}
main()
{
nhap(l);
hien(l);
l=NULL;
cout<<"danh sach sau khi sap xep:
";
sapxep (l);hien(l);
cout<<"danh sach sau khi chen dau:
";
chend(l);hien(l);
cout<<"danh sach sau khi chen cuoi:
";
chenc(l);hien(l);
cout<<"danh sach sau khi chen phan tu la:
";
chensap(l);
cout<<"danh sach sau khi xoa la:
";
del(l);
deld(l);
delc(l);
hien(l);
getch();
}
Mảng 1 chiá»u
#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"
#include "iomanip.h"
//=====================================
//Nhap mang:
void nhap(int a[], int &n)
{
cout<<"
Nhap n:";
cin>>n;
for (int i=0; i<n; i++)
{
cout<<"
a["<<i<<"]=";
cin>>a[i];
}
}
//=====================================
//Xuat mang ra man hinh:
void hien(int a[], int n)
{
for (int i=0; i<n; i++)
cout<<setw(5)<<a[i];
}
//=====================================
//Tim phan tu max va dem so phan tu max:
void max(int a[], int n)
{
int m=a[0], dem=1;
for (int i=1; i<n; i++)
{
if (m==a[i])
dem++;
if (m<a[i])
{
m=a[i];
dem=1;
}
}
cout<<"
Max="<<m;
cout<<"
So phan tu max la:"<<dem;
}
//=====================================
//Xoa cac phan tu bang x:
void xoax(int a[], int &n)
{
int x;
cout<<"
Nhap x:";
cin>>x;
int d=0;
while (d<n && a[d]!=x)
d++;
for (int i=d+1; i<n; i++)
if (a[i]!=x)
{
a[d]=a[i];
d++;
}
n=d;
cout<<"
Sau khi xoa phan tu bang x:"<<endl;
for (int i=0; i<n; i++)
cout<<setw(5)<<a[i];
}
//=====================================
//Sap xep tang dan:
void saptang(int a[], int n)
{
cout<<"
Sap xep tang dan:"<<endl;
int tg;
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
if (a[i]>a[j])
{
tg=a[i];
a[i]=a[j];
a[j]=tg;
}
cout<<"
Sau khi sap xep tang dan:"<<endl;
for (int i=0; i<n; i++)
cout<<setw(5)<<a[i];
}
//=====================================
//Chen x vao mang da sap, thoa man thu tu sap:
void chenx(int a[], int &n)
{
int d=0;
int x;
cout<<"
Nhap phan tu x:";
cin>>x;
while (d<n && a[d]<x)
d++;
for (int i=n; i>d; i--)
a[i]=a[i-1];
a[d]=x;
n++;
cout<<"
Sau khi chen phan tu x:"<<endl;
for (int j=0; j<n; j++)
cout<<setw(5)<<a[j];
}
//Main:
main()
{
int a[1000], n;
nhap(a,n);
hien(a,n);
//max(a,n);
//xoax(a,n);
//saptang(a,n);
//chenx(a,n);
getch();
}
Danh sách liên kết Ä'Æ¡n:
struct sv
{
char masv[10];
char hoten[20];
float dtb;
};
struct node
{
sv ptu;
node *next, *pre;
};
struct dssv
{
node *l, *r;
}ds;
void nhap (dssv &ds)
{
char s[10];
ds.l=new node;
ds.r=ds.l;
ds.l->pre=NULL;
cout<<"Nhap ma sv: ";
{
fflush(stdin);
gets(ds.l->ptu.masv);
}
cout<<"Nhap ho ten: ";
{
fflush(stdin);
gets(ds.l->ptu.hoten);
}
cout<<"Nhap diem TB: ";
cin>>ds.l->ptu.dtb;
cout<<"Nhap ma sv: ";
{
fflush(stdin);
gets(s);
}
while (strcmp (s,""))
{
ds.r->next=new node;
ds.r->next->pre=ds.r;
ds.r=ds.r->next;
strcpy (ds.r->ptu.masv,s);
cout<<"Nhap ho ten: ";
{
fflush(stdin);
gets(ds.r->ptu.hoten);
}
cout<<"Nhap diem TB: ";
cin>>ds.r->ptu.dtb;
cout<<"Nhap ma sv: ";
{
fflush(stdin);
gets(s);
}
}
ds.r->next = NULL;
}
void hiennguoc(dssv ds)
{
while (ds.r!= NULL)
{
cout<<ds.r->ptu.masv<<setw(20)<<ds.r->ptu.hoten;
cout<<setw(10)<<ds.r->ptu.dtb<<"
";
ds.r=ds.r->pre;
}
}
void hienxuoi(dssv ds)
{
while (ds.r!= NULL)
{
cout<<ds.l->ptu.masv<<setw(20)<<ds.l->ptu.hoten;
cout<<setw(10)<<ds.l->ptu.dtb<<"
";
ds.l=ds.l->pre;
}
}
/*
void sapxep(dssv*&l)
{
node *p,*q;
sv tg;
if (ds.l!=NULL)
{
p=ds.l;
while(p->next!=NULL)
{
q=p->next;
while(q!=NULL)
{
if(p->ptu.dtb>q->ptu.dtb)
{
tg=q->ptu;
q->ptu=p->ptu;
p->ptu=tg;
}
q=q->next;
}
p=p->next;
}
}
}
void chend(dssv*&l)
{
dssv *q=new dssv;
cout<<"Nhap ma sv: ";
{
fflush(stdin);
gets(q->ptu.masv);
}
cout<<"Nhap ho ten: ";
{
fflush(stdin);
gets(q->ptu.hoten);
}
cout<<"Nhap diem TB: ";
cin>>q->ptu.dtb;
q->next=l;
l=q;
}
void chenc(dssv*&l)
{
dssv *p,*q=new dssv;
cout<<"Nhap ma sv: ";
{
fflush(stdin);
gets(q->ptu.masv);
}
cout<<"Nhap ho ten: ";
{
fflush(stdin);
gets(q->ptu.hoten);
}
cout<<"Nhap diem TB: ";
cin>>q->ptu.dtb;
q->next=NULL;
if (l==NULL) l=q;
else
{
p=l;
while(p->next!=NULL) p=p->next;
p->next=q;
}
}
void chensap(dssv*&l)
{
dssv *p,*q=new dssv;
cout<<"Nhap ma sv: ";
{
fflush(stdin);
gets(q->ptu.masv);
}
cout<<"Nhap ho ten: ";
{
fflush(stdin);
gets(q->ptu.hoten);
}
cout<<"Nhap diem TB: ";
cin>>q->ptu.dtb;
if (l==NULL||q->ptu.dtb<l->ptu.dtb)
{
q->next=l;
l=q;
}
else
{
p=l;
while(p->next!=NULL&&p->next->ptu.dtb<q->ptu.dtb) p=p->next;
q->next=p->next;
p->next=q;
}
}
void delc(dssv*&l)
{
if(l!=NULL)
{
dssv*p=l,*q;
if (l->next==NULL)
{
delete l;
l=NULL;
}
else
{
while (p->next->next!=NULL) p=p->next;
q=p->next;
p->next=NULL;
delete q;
}
}
}
void deld(dssv*&l)
{
if(l!=NULL)
{
dssv*p=l;
l=l->next;
delete p;
}
}
void del(dssv *&l)
{
if(l!=NULL)
{
dssv*p=l,*q;
while (p->next!=NULL)
if (p->next->ptu.dtb<5)
{
q=p->next;p->next=q->next;delete q;
}
else p=p->next;
if(l->ptu.dtb<5)
{
q=l;l=l->next;delete q;
}
}
}
Key:
#include <cstring>
#include <cmath>
#include <conio.h>
#include <iostream>
#include <cstdio>
using namespace std;
struct node
{
int key;
node *left, *right;
}*t;
void insert(int x, node *&t)
{
if (t==NULL)
{
t= new node;
t->key=x;
t->left=NULL;
t->right=NULL;
}
else if (x<t->key)
insert(x,t->left);
else
insert(x,t->right);
}
void nhap(node *&t)
{
int n,x;
t=NULL;
cout<<"
Nhap so nut:";
cin>>n;
for (int i=1;i<=n;i++)
{
cout<<"
Nhap nut thu "<<i<<" : ";
cin>>x;
insert(x,t);
}
}
void hienpre(node *t)
{
if (t!=NULL)
{
cout<<t->key<<" ";
hienpre(t->left);
hienpre(t->right);
}
}
void hienin(node *t)
{
if (t!=NULL)
{
hienin(t->left);
cout<<t->key<<" ";
hienin(t->right);
}
}
void hienpost(node *t)
{
if (t!=NULL)
{
hienpost(t->left);
hienpost(t->right);
cout<<t->key<<" ";
}
}
void del(int x,node *&t)
{
node *p,*q;
if (t!=NULL)
{
if (t->key==x)
if (t->left==NULL)
{
p=t;
t=t->right;
delete p;
}
else if (t->right==NULL)
{
p=t;
t=t->right;
delete p;
}
else
{
p=t->left;
if (p->right==NULL)
{
p->right=t->right;
q=t;
t=p;
delete q;
}
else
{
while (p->right->right!=NULL)
p=p->right;
q=p->right;
t->key=q->key;
p->right=q->left;
delete q;
}
}
else if(t->key>x)
del(x,t->left);
else
del(x,t->right);
}
}
int main()
{
freopen("input.in","r",stdin);
nhap(t);
//freopen("output.txt","w",stdout);
cout<<"
Hien dau:
";
hienpre(t);
cout<<"
Hien giua:
";
hienin(t);
cout<<"
Hien sau:
";
hienpost(t);
int x;
cout<<"
Nhap x:
";
cin>>x;
del(x,t);
cout<<"
Hien dau:
";
hienpre(t);
cout<<"
Hien giua:
";
hienin(t);
cout<<"
Hien sau:
";
hienpost(t);
getch();
return 0;
}
Bạn đang đọc truyện trên: Truyen2U.Pro