Tuesday, May 12, 2015

lập trình c++ tính giá trị biểu thức toán học

lập trình c++ tính giá trị biểu thức toán học

viết chương trình tính giá trị của 1 biểu thức toán học thông thường với số thực, số nguyên đều được và các phép toán cộng + trừ - nhân * chia / và dấu ngoặc. thuật toán này được thiết kế code c++ bởi Trần Khánh Toàn, cái hay của bài này là tính được cả số thực, các biểu thức nếu máy tính fx-500ms tính được thì nó tính được, riêng phần báo lỗi thì nó không có, nhập biểu thức sai cú pháp thì nó chạy sai hoặc hệ thống báo không chạy được chương trình này, không gì là hoàn hảo cả nên t sẽ cố gắng cải tiến và update lên đây để mọi người học hỏi kinh nghiệm.

#include<iostream>
#include<string>
using namespace std;
bool check(string s)
{
for(int i=0;i<s.size();i++)
if(s[i]=='('||s[i]==')')
return true;
return false;
}
string itoa(float x)
{
string s;
int d=0,dem=0,a;
if(x==0) s.insert(0,"0");
if(x<0)
{
d=1;
x=-x;
}
while(float(x)-long(x)!=0)
{
dem++;
x*=10;
}
long z=long(x);
for(int i=0;i<dem;i++)
{
a=z%10;
z/=10;
switch(a)
{
case 0:s.insert(0,"0");break;
case 1:s.insert(0,"1");break;
case 2:s.insert(0,"2");break;
case 3:s.insert(0,"3");break;
case 4:s.insert(0,"4");break;
case 5:s.insert(0,"5");break;
case 6:s.insert(0,"6");break;
case 7:s.insert(0,"7");break;
case 8:s.insert(0,"8");break;
case 9:s.insert(0,"9");break;
}
}
if(dem>0)s.insert(0,".");
if(z==0) s.insert(0,"0");
while(z>0)
{
a=z%10;
z/=10;
switch(a)
{
case 0:s.insert(0,"0");break;
case 1:s.insert(0,"1");break;
case 2:s.insert(0,"2");break;
case 3:s.insert(0,"3");break;
case 4:s.insert(0,"4");break;
case 5:s.insert(0,"5");break;
case 6:s.insert(0,"6");break;
case 7:s.insert(0,"7");break;
case 8:s.insert(0,"8");break;
case 9:s.insert(0,"9");break;
}
}
if(d==1) s.insert(0,"-");
else s.insert(0,"+");
return s;
}
float lay1(string s)
{
long d=1;
float x=0;
for(int i=s.size()-1;i>=0;i--)
{
if(s[i]=='-' || s[i]=='+' || s[i]=='*' || s[i]=='/' || s[i]=='(' || s[i]==')')
{
if(s[i]=='-') x=-x;
break;
}
else if(s[i]=='.')
{
x/=d;
d=1;
}
else
{
switch(s[i])
{
case '0':break;
case '1':x+=d;break;
case '2':x+=2*d;break;
case '3':x+=3*d;break;
case '4':x+=4*d;break;
case '5':x+=5*d;break;
case '6':x+=6*d;break;
case '7':x+=7*d;break;
case '8':x+=8*d;break;
case '9':x+=9*d;break;
}
d*=10;
}
}
return x;
}
float lay2(string s)
{
long j=0,k=0,i;
float d;
float x=0;
if(s[0]=='+' || s[0]=='-') j=1;
for(i=j;i<s.size();i++)
{
if(s[i]>='0' && s[i]<='9')
{
switch(s[i])
{
case '0':x=x*10+0;break;
case '1':x=x*10+1;break;
case '2':x=x*10+2;break;
case '3':x=x*10+3;break;
case '4':x=x*10+4;break;
case '5':x=x*10+5;break;
case '6':x=x*10+6;break;
case '7':x=x*10+7;break;
case '8':x=x*10+8;break;
case '9':x=x*10+9;break;
}
}
else break;
}
if(i<s.size() && s[i]=='.')
{
d=10;
for(j=i+1;j<s.size();j++)
{
if(s[j]>='0' && s[j]<='9')
{
switch(s[j])
{
case '0':x+=0/d;break;
case '1':x+=1/d;break;
case '2':x+=2/d;break;
case '3':x+=3/d;break;
case '4':x+=4/d;break;
case '5':x+=5/d;break;
case '6':x+=6/d;break;
case '7':x+=7/d;break;
case '8':x+=8/d;break;
case '9':x+=9/d;break;
}
d*=10;
}
else break;
}
}
if(s[0]=='-') x=-x;
return x;
}
void xuly(string &s)
{
if(s[s.size()-1]=='+'||s[s.size()-1]=='-')
{
s.push_back('0');
}
if(s[s.size()-1]=='*'||s[s.size()-1]=='/')
{
bool p=false;
for(int i=s.size()-2;i>=0;i--)
if(s[i]=='+'||s[i]=='-')
{
p=true;
i++;
s.replace(i,s.size()-i,"0");
}
if(p==false)
{
s.erase(0,s.size());
s.insert(0,"0");
}
}
for(int i=0;i<s.size()-1;i++)
if(s[i]=='+' && s[i+1]=='+')
{
s.erase(i,1);
}
else if(s[i]=='+' && s[i+1]=='-')
{
s.erase(i,1);
}
else if(s[i]=='-' && s[i+1]=='+')
{
s.erase(i+1,1);
}
else if(s[i]=='-' && s[i+1]=='-')
{
s.erase(i,2);
s.insert(i,"+");
}
}
float tinh(string s)
{
xuly(s);
int p1,p2;
string a,c;
float x,y,t=0,p;
while(check(s))
{
p2=s.find(")");
if(p2>=0)
{
xuly(s);
p1=s.rfind("(",p2);
a=s.substr(p1+1,p2-p1-1);
p=tinh(a);
c=itoa(p);
s.replace(p1,p2-p1+1,c);
xuly(s);
}
}
loop:;
for(p=0;p<s.size();p++)
if(s[p]=='*' || s[p]=='/') break;
if(p!=s.size())
{
xuly(s);
a=s.substr(0,p);
c=s.substr(p+1,s.size()-p-1);
x=lay1(a);
y=lay2(c);
if(s[p]=='*') t=x*y;
else t=x/y;
for(p1=p-1;p1>=0;p1--)
if(s[p1]=='+' || s[p1]=='-'|| s[p1]=='*'|| s[p1]=='/'|| s[p1]=='('|| s[p1]==')') break;
if(p1==-1) p1++;
else if(s[p1]=='*' || s[p1]=='/') p1++;
for(p2=p+2;p2<s.size();p2++)
if(s[p2]=='+' || s[p2]=='-'|| s[p2]=='*'|| s[p2]=='/'|| s[p2]=='('|| s[p2]==')') break;
p2--;
a=itoa(t);
s.replace(p1,p2-p1+1,a);
xuly(s);
goto loop;
}
//dau +-
else
{
int k;
do{
k=0;
for(p=1;p<s.size();p++)
if(s[p]=='+' || s[p]=='-') break;
if(p<s.size())
{
xuly(s);
a=s.substr(0,p);
c=s.substr(p+1,s.size()-p-1);
x=lay1(a);
y=lay2(c);
if(s[p]=='+') t=x+y;
else t=x-y;
a=itoa(t);
for(p2=p+1;p2<s.size();p2++)
if(s[p2]=='+' || s[p2]=='-') break;
p2--;
s.replace(0,p2+1,a);
xuly(s);
k=1;
}
}while(k);
}
t=lay1(s);
return t;
}
void main()
{
string s;
getline(cin,s);
cout<<s<<" = ";
cout<<tinh(s)<<endl;
system("pause");
}

Monday, May 11, 2015

Lập trình game trên mobile - Android - iOS - WinPhone

Dành cho các bạn đam mê lập trình game và muốn theo nghề lập trình game.
Yêu cầu cần có kiến thức cơ bản về lập trình, cơ bản Lập trình hướng đối tượng.

Ngôn ngữ sử dụng để viết game:
  • Android: Java (sủ dụng Engine Libgdx hoặc AndEngine )
  • iOS: Swift (sủ dụng Engine SpriteKit)

  • Đa nền tảng ( Android, iOS, Winphone, Win8, ...): C/C++  ( sử dụng Engine Cocos2d-x )
Kiến thức liên quan: OpenGL, kiến thức vật lý, cấu trúc file .json

Phát triển Game sử dụng Engine để build đa nền tản( Sử dụn 1 ngôn ngữ để viết code ở 1 project core sau đó build qua các nền tảng khác ( Android, iOS, Winphone, Win8, ...))
Sử dụng Engine để làm game đa nền tảng
Xem chi tiết các nội dung cần tìm hiểu:


CHƯƠNG TRÌNH LẬP TRÌNH GAME TRÊN ANDROID

1.      Giới thiệu về OpenGL trên Android, kỹ thuật đồ họa 2D,3D trên Android (2 buổi)
2.      Mô hình kiến trúc Lập trình Game (1 buổi)
3.      Các ý tưởng lập trình Game (1 buổi)
4.      Giới thiệu các thư viện sử dụng lập trình game trên Android (2 buổi)
5.      Làm việc với AndEngine để lập trình game (4 buổi)
6.      Nguyên tắc sử dụng Engine, Scene trong việc lập trình Game (2 buổi)
7.      Các đối tượng trên Game, Sprite, AnimatedSprite, Layer,Particle, Shape, Text (3 buổi)
8.      Audio trên Game (1 buổi)
9.      Nguyên tắc va chạm, chuyển động khi lập trình game (2 buổi)
10.  Sử lý hình ảnh trên Game (2 buổi)

11.  Viết các game cơ bản (3 buổi)

CHƯƠNG TRÌNH LẬP TRÌNH GAME ĐA NỀN TẢN ( ANDROID, IOS, WINPHONE, WIN 8 )  SỬ DỤNG ENGINE COCOS2D-X
Engine Cocos2d-x

1.      Ôn tập kiến thức C/C++ và lập trình hướng đối tượng (2 buổi)
2.      Mô hình kiến trúc Lập trình Game (1 buổi)
3.      Các ý tưởng lập trình Game (1 buổi)
4.      Giới thiệu Engine Cocos2d-x (2 buổi)
5.      Làm việc với Engine Cocos2d-x để lập trình game (4 buổi)
6.      Nguyên tắc sử dụng Engine, Scene trong việc lập trình Game (2 buổi)
7.      Các đối tượng trên Game, Sprite, AnimatedSprite, Layer,Particle (3 buổi)
8.      Audio trên Game (1 buổi)
9.      Nguyên tắc va chạm, chuyển động khi lập trình game (2 buổi)
10.  Sử lý hình ảnh trên Game (2 buổi)
11.  Viết các game cơ bản (3 buổi)

BẠN NÀO CÓ NHU CẦU TÌM HIỂU LÀM GAME CÓ THỂ COMMENT DƯỚI BÀI VIẾT NHÉ <3  AD page Học Lập Trình
Các bạn comment ở dưới bài viết để trao đổi nhé :D

Sunday, May 3, 2015

Internet of Things

1. Khái niệm Internet of Things
              Internet of Things (IoT) là một kịch bản của thế giới, khi mà mỗi đồ vật, mỗi đồ vật, con người được cung cấp một định danh của riêng mình, và tất cả có khả năng truyền tải, trao đổi thông tin, dữ liệu qua một mạng duy nhất mà không cần đến sự tương tác trực tiếp giữa người với người, hay người với máy tính. IoT đã phát triển từ sự hội tụ của công nghệ không dây, công nghệ vi cơ điện tử và Internet.
Khái niệm Internet of things


 2. Xu hướng của thế giới Internet of Things
 Như vậy có thể tạm hiểu, Internet of Things là khi tất cả mọi thứ đều được kết nối với nhau qua mạng Internet, người dùng (chủ) có thể kiểm soát mọi đồ vật của mình qua mạng mà chỉ bằng một thiết bị thông minh, chẳng hạn như smartphone, tablet, PC hay thậm chí chỉ bằng một chiếc smartwatch nhỏ bé trên tay.
Xu hướng của thế giới với Internet of Things

* Các giao thức giao tiếp không dây trong thế giới IoT được thiết kế để thỏa mãn các yêu cầu cơ bản: 
Tiêu tốn ít năng lượng cho việc thu/phát sóng, 
Tiêu tốn ít băng thông (để giảm gánh nặng cho router wireless và hệ thống mạng), hoạt động trong mạng mắt lưới…

* Một số thiết bị sẽ giao tiếp qua:
 -   Wi-fi
 -   Bluetooth,
 -   NFC
 -   Nhưng đa phần sẽ tận dụng các kết nối sử dụng dải tần của mạng không dây.
3. Ứng dụng của Internet of Things


  •               Dùng iPhone mở khóa MacBook:
              Knock, được phát triển bởi Knock Software Inc và đang bán trên Apple Store với giá 3.99 USD. 
           Công dụng của Knock là giúp bạn dùng iPhone để unlock (mở khóa) MacBook bằng cách cầm iPhone gõ hai cái lên đâu đó. 

  •       Nhà thông minh (Smart Home)
Ứng dụng BLE để điều khiển máy lạnh, TV, đèn, máy giặt… nói chung là mọi thiết bị trong ngôi nhà của bạn. Biến chiếc mobile của bạn thành chiếc remote đa năng, điều khiển đủ mọi thứ trong nhà và thậm chí không cần điều khiển, đèn vẫn có thể tự tắt.
ĐTDĐ của các bạn sẽ cần cài đặt một phần mềm để làm trung tâm điều khiển, 
Cứ mỗi thiết bị cần điều khiển sẽ gắn một thiết bị ngoại vi 
Cài đặt lệnh cho từng thiết bị ngoại vi ấy như là bấm lệnh gì thì thiết bị nào sẽ thực thi điều gì .
Không thì toàn bộ thiết bị điện trong nhà sẽ tắt hết, trừ tủ lạnh, chẳng hạn.
7. Hướng dẫn tìm hiểu Internet of things
http://www.intel.com/content/www/us/en/internet-of-things/overview.html
http://www.arduino.cc/
- http://www.visualmicro.com/ 
5. Xây dựng ứng dụng đầu tiên
Thiết kế xe điều khiển từ xa qua bluetooth
Xe điểu khiên bằng bluetooch
Cập nhập sau :)

Wednesday, April 29, 2015

phần mềm split and join file part,001,002

phần mềm split and join file part,001,002



#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>
void layten(char *duongdan,char *ten)
{
int d=0;
for(int i=strlen(duongdan)-1;i>=0;i--)
if(duongdan[i]!='/' && duongdan[i]!='\\') ten[d++]=duongdan[i];
else break;
ten[d]='\0';
for(int i=0;i<strlen(ten)/2;i++)
{
char c=ten[i];
ten[i]=ten[strlen(ten)-1-i];
ten[strlen(ten)-1-i]=c;
}
}
void bang(char *a,char *b)
{
for(int i=0;i<strlen(b);i++) a[i]=b[i];
a[strlen(b)-1]='\0';
}
int insertpass(char *duongdan,char *mk)
{
FILE *t=fopen(duongdan,"rb+");
FILE *f=fopen("logTKT.bin","wb+");
if(t==NULL || f==NULL) return 0;
fwrite(mk,8,1,f);
char s[2];
while(fread(s,1,1,t)) fwrite(s,1,1,f);
rewind(t);rewind(f);
while(fread(s,1,1,f)) fwrite(s,1,1,t);
fcloseall();
remove("logTKT.bin");
return 1;
}
int pass_ok(char *s)
{
int dem=0;
for(int i=0;i<strlen(s);i++)
if(s[i]>='0' && s[i]<='9') dem++;
if(dem!=strlen(s) || dem!=6) return 0;
s[6]=s[7]='#';
s[8]='\0';
return 1;
}
int split(char *duongdan,char *thumuc,int n)
{
char ten[100],duongdan2[100],a[10],*s=new char[2];
unsigned long dungluong,dem;
int i;
layten(duongdan,ten);
strcat(thumuc,"/");
strcat(thumuc,ten);
strcat(thumuc,".partt");
FILE *t=fopen(duongdan,"rb");
if(t==NULL)
{
printf("\nduong dan file khong hop le!");
return 0;
}
fseek(t,0,2);
dungluong=ftell(t)/n;
rewind(t);
for(i=1;i<n;i++)
{
bang(duongdan2,thumuc);
a[0]='\0';
itoa(i,a,10);
strcat(duongdan2,a);
FILE *f=fopen(duongdan2,"wb");
if(f==NULL)
{
printf("\nduong dan thu muc chua file ket qua khong hop le!");
return 0;
}
dem=0;
do{
fread(s,1,1,t);
fwrite(s,1,1,f);
dem+=1;
}while(dem!=dungluong);
fclose(f);
}
bang(duongdan2,thumuc);
a[0]='\0';
itoa(n,a,10);
strcat(duongdan2,a);
FILE *f=fopen(duongdan2,"wb");
if(f==NULL)
{
printf("\nduong dan thu muc chua file ket qua khong hop le!");
return 0;
}
while(fread(s,1,1,t)) fwrite(s,1,1,f);
fclose(f);
delete []s;
fclose(t);
return 1;
}
int join(char *duongdan,char *thumuc)
{
int i;
char ten[100],duongdanketqua[100],a[10],s[2],dd[100];
layten(duongdan,ten);
for(i=strlen(ten)-1;i>=0;i--)
if(ten[i]!='.') ten[i]='\0';
else break;
ten[i]='\0';
duongdanketqua[0]='\0';
strcat(duongdanketqua,thumuc);
if(strlen(duongdanketqua)>0)strcat(duongdanketqua,"/");
strcat(duongdanketqua,ten);
FILE *t=fopen(duongdanketqua,"wb");
if(t==NULL)
{
printf("\nduong dan thu muc chua file ket qua khong hop le!\n");
return 0;
}
for(i=strlen(duongdan)-1;i>=0;i--)
if(duongdan[i]>='0' && duongdan[i]<='9') duongdan[i]='\0';
else break;
i=1;
while(1)
{
a[0]='\0';
itoa(i++,a,10);
bang(dd,duongdan);
strcat(dd,"t");
strcat(dd,a);
FILE *f=fopen(dd,"rb");
if(i==1 && f==NULL)
{
printf("\nduong dan file khong hop le!");
return 0;
}
if(f==NULL) break;
while(fread(s,1,1,f)) fwrite(s,1,1,t);
fclose(f);
}
fclose(t);
return 1;
}
int split2(char *duongdan,char *thumuc,char *dl)
{
unsigned long dungluong=0,dem;
int i;
char a[100],ten[100],duongdan2[100],s[2];
layten(duongdan,ten);
if(strlen(thumuc)>0)strcat(thumuc,"/");
strcat(thumuc,ten);
strcat(thumuc,".partt");
for(i=0;i<strlen(dl);i++)
if(dl[i]>='0' && dl[i]<='9') a[i]=dl[i];
else break;
a[i]='\0';
dungluong+=atol(a);
if(dl[i]=='K') dungluong*=1024;
if(dl[i]=='M') dungluong*=1024*1024;
FILE *t=fopen(duongdan,"rb");
if(t==NULL)
{
printf("\nduong dan file khong hop le!");
return 0;
}
i=1;
while(!feof(t))
{
bang(duongdan2,thumuc);
a[0]='\0';
itoa(i++,a,10);
strcat(duongdan2,a);
FILE *f=fopen(duongdan2,"wb");
if(f==NULL)
{
printf("\nduong dan thu muc chua file ket qua khong hop le!");
return 0;
}
dem=0;
for(dem=1;dem<=dungluong;dem++)
if(fread(s,1,1,t)) fwrite(s,1,1,f);
else break;
fclose(f);
}
return 1;
}
int co_pass(char *duongdan,char *pass)
{
FILE *t=fopen(duongdan,"rb+");
if(t==NULL) return -1;
char s[10];
fread(s,8,1,t);
if(s[6]=='#' && s[7]=='#')
{
int i;
for(i=0;i<6;i++) pass[i]=s[i];
pass[i]='\0';
fclose(t);
return 1;
}
fclose(t);
return 0;
}
void xuly_pass(char *duongdan)
{
FILE *t=fopen(duongdan,"rb");
FILE *f=fopen("logTKT.bin","wb+");
char s[10];
fread(s,8,1,t);
while(fread(s,1,1,t)) fwrite(s,1,1,f);
rewind(f);fclose(t);
t=fopen(duongdan,"wb");
while(fread(s,1,1,f)) fwrite(s,1,1,t);
fcloseall();
remove("logTKT.bin");
}
void main()
{
char duongdan[100],thumuc[100],dungluong[100],pass[100];
int n,k=1,kt,kiemtrapass;
while(k!=0)
{
system("cls");
printf("\n\n________________MENU___________________\n");
printf("| 1. chia file thanh n part.(split1) |\n");
printf("| 2. chia file theo dung luong.(split2)|\n");
printf("| 3. gop file (join) |\n");
printf("| 0. Thoat. |\n");
printf("________________________________________\n");
scanf("%d",&k);



if(k==1)
{
kiemtrapass=0;
printf("\nnhap vao DUONG DAN FILE chua file can Split: ");fflush(stdin);gets(duongdan);
printf("\nnhap vao THU MUC chua file ket qua Split: ");fflush(stdin);gets(thumuc);
printf("\nnhap vao SO PART can Split: N=");scanf("%d",&n);
printf("\nDo you Set PassWord?? 1-yes; 0-no; : ");scanf("%d",&kt);
if(kt==1)
{
kiemtrapass=1;
int kc,kl;
do{
kc=0;
printf("\nnhap 6 chu so password: ");fflush(stdin);gets(pass);
kl=pass_ok(pass);
if(kl==0)
{
printf("\nnhap pass sai dinh dang! nhap lai!");
kc=1;
}
}while(kc==1);
printf("\ndang cai dat PassWord vao file! doi nhe! ...");
kc=insertpass(duongdan,pass);
if(kc==0)
{
printf("\nduong dan file khong hop le!");
goto ketthuc1;
}
}
printf("\nDANG XU LY! VUI LONG DOI! ...");
kt=split(duongdan,thumuc,n);
if(kiemtrapass==1)xuly_pass(duongdan);
if(kt==1) printf("\nOK - Da Xong!\n");
ketthuc1:;
system("pause");
}




else if(k==2)
{
kiemtrapass=0;
printf("\nnhap vao DUONG DAN FILE chua file can Split: ");fflush(stdin);gets(duongdan);
printf("\nnhap vao THU MUC chua file ket qua Split: ");fflush(stdin);gets(thumuc);

do{
kt=0;
printf("\nnhap vao DUNG LUONG 1 part can Split: dung luong =");fflush(stdin);gets(dungluong);
int dem=0;
for(int i=0;i<strlen(dungluong);i++)
if((dungluong[i]>='0' && dungluong[i]<='9') || dungluong[i]=='B' || dungluong[i]=='K' || dungluong[i]=='M')
dem++;
if(dem!=strlen(dungluong))
{
printf("\nkhong hop le!");
kt=1;
}
}while(kt);

printf("\nDo you Set PassWord?? 1-yes; 0-no; : ");scanf("%d",&kt);
if(kt==1)
{
kiemtrapass=1;
int kc,kl;
do{
kc=0;
printf("\nnhap 6 chu so password: ");fflush(stdin);gets(pass);
kl=pass_ok(pass);
if(kl==0)
{
printf("\nnhap pass sai dinh dang! nhap lai!");
kc=1;
}
}while(kc==1);
printf("\ndang cai dat PassWord vao file! doi nhe! ...");
kc=insertpass(duongdan,pass);
if(kc==0)
{
printf("\nduong dan file khong hop le!");
goto ketthuc2;
}
}
printf("\nDANG XU LY! VUI LONG DOI! ...");
kt=split2(duongdan,thumuc,dungluong);
if(kiemtrapass==1)xuly_pass(duongdan);
if(kt==1) printf("\nOK - Da Xong!\n");
ketthuc2:;
system("pause");
}



else if(k==3)
{
printf("\nnhap vao DUONG DAN FILE part1: ");fflush(stdin);gets(duongdan);
printf("\nnhap vao THU MUC chua file ket qua: ");fflush(stdin);gets(thumuc);
char lay_pass[100];
printf("\ndang xu ly! ...");
int mk=co_pass(duongdan,lay_pass);
if(mk==-1)
{
printf("\nduong dan file khong hop le!");
goto ketthuc3;
}
else if(mk==1)
{
char check_pass[100];
printf("\nnhap PASS de join file: ");fflush(stdin);gets(check_pass);
if(strcmp(lay_pass,check_pass)!=0)
{
printf("\nnhap pass sai!!!");
goto ketthuc3;
}
else xuly_pass(duongdan);
}
printf("\nDANG XU LY! VUI LONG DOI! ...");
kt=join(duongdan,thumuc);
if(kt==1) printf("\nOK - Da Xong!\n");
ketthuc3:;
system("pause");
}
else printf("\n\nTAM BIET!\n");
}
getch();
}
danh sách liên kết kép

danh sách liên kết kép




Cấu Trúc Dữ Liệu



Cấu trúc dữ liệu 1 nút
typedef struct tagDnode
{ Data Info;
struct tagDnode *pPre;
struct tagDnode *pNext;
}DNode;


Cấu trúc List kép
Typedef struct tagDList
{ DNode *pHead;
DNode *pTail;
}DList;
void CreateDList(DList &l)
{
l.DHead=NULL;
l.DTail=NULL;
}



Tạo 1 Nút Có Thành Phần Dữ Liệu = X
DNode *CreateDNode(int x)
{ DNode *tam;
tam=new DNode;
if(tam==NULL)
{ printf("khong con du bo nho");
exit(1);
}
else
{ tam->Info=x;
tam->pNext=NULL;
tam->pPre=NULL;
return tam;
}
}


Cài Đặt Thêm 1 Nút Vào Đầu Danh Sách
void AddFirst(DList &l, DNode *tam)
{
if(l.pHead==NULL)//xau rong
{
l.pHead=tam;
l.pTail=l.pHead;
}
else
{
tam->pNext=l.pHead;
l.pHead->pPre=tam;
l.pHead=tam;
}
}


Cài Đặt Thêm 1 Nút Vào Cuối Danh Sách
void AddEnd(DList &l,DNode *tam)
{
if(l.pHead==NULL)
{
l.pHead=tam;
l.pTail=l.pHead;
}
else
{
tam->pPre=l.pTail;
l.pTail->pNext=tam;
tam=l.pTail;
}
}


Cài Đặt Thêm 1 Nút Vào Sau Nút Q
void AddLastQ(DList &l,DNode *tam, DNode *q)
{
DNode *p;
p=q->pNext;
if(q!=NULL)//them vao duoc
{
tam->pNext=p;
tam->pPre=q;
q->pNext=tam;
if(p!=NULL)
p->pPre=tam;
if(q==l.pTail) //them vao sau danh sach lien ket.
l.pTail=tam;
}
else
AddFirst(l,tam);
}


Cài Đặt Thêm 1 Nút Vào Trước Nút Q
void AddBeforeQ(DList &l,DNode *tam,DNode *q)
{ DNode *p;
p=q->pPre;
if(q!=NULL)
{
tam->pNext=q;
q->pPre=tam;
tam->pPre=p;
if(p!=NULL)
p->pNext=tam;
if(q==l.pHead)
l.pHead = tam;
}
else
AddEnd(l,tam);
}


Xoá Phần Tử Đầu Danh Sách
void DeleteFirst(DList &l)
{
DNode *p;
if(l.pHead!=NULL)
{
p=l.pHead;
l.pHead=l.pHead->pNext;
l.pHead->pPre=NULL;
delete p;
if(l.pHead==NULL)
l.pTail=NULL;
}
}


Xoá 1 Phần Tử Cuối Danh Sách
void DeleteEnd(DList &l )
{
DNode *p;
if(l.pHead!=NULL) //tuc xau co hon mot phan tu
{
p=l.pTail;
l.pTail=l.pTail->Pre;
l.pTail->pNext=NULL;
delete p;
if(l.pTail==NULL)
l.pHead=NULL;
}
}


Hủy 1 Nút Sau Nút Q
void DeleteLastQ(DList &l,DNode *q)
{
DNode *p;//luu node dung sau node q
if(q!=NULL)
{
p=q->pNext;
if(p!=NULL)
{
q->pNext=p->pNext;
if(p==l.pTail)//xoa dung nu't cuoi
l.pTail=q;
else //Nut xoa khong phai nut cuoi
p->pNext->pPre=q;
delete p;
}
}
else
DeleteFirst(l);
}


Huỷ 1 Nút Đứng Trước Nút Q
void DeleteBeforeQ(DList &l,DNode *q)
{
DNode *p;
if(q!=NULL) //tuc ton tai node q
{
p=q->pPre;
if(p!=NULL)
{
q->pPre=p->pPre;
if(p==l.pHead)//p la Node dau cua danh sach
l.pHead=q;
else //p khong phai la node dau
p->pPre->pNext=q;
delete p;
}
}
else
DeleteEnd(l);
}


Xoá 1 Phần Tử Có Khoá = X
int DeleteX(DList &l,int x)
{
DNode *p;
DNode *q;
q=NULL;
p=l.pHead;
while(p!=NULL)
{
if(p->Info==x)
break;
q=p;//q la Node co truong Info = x
p=p->pNext;
}
if(q==NULL) return 0;//khong tim thay Node nao co truong Info =x
if(q!=NULL)
DeleteLastQ(l,q);
else
DeleteFirst(l);
return 1;
}


Sắp Xếp
void DoiChoTrucTiep(DList &l)
{ DNode *p,*q;
p=l.pHead;
while(p!=l.pTail)
{
q=p->pNext;
while(q!=NULL)
{
if(p->Info>q->Info)
HV(p,q);
q=q->pNext;
}
p=p->pNext;
}}

Sunday, April 26, 2015

danh sách liên kết đơn

danh sách liên kết đơn

Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách
Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần
Thành phần dữ liệu: Lưu trữ thông tin về bản thân phần tử
Thành phần liên kết: Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách.
Cấu trúc dữ liệu của 1 nút trong List đơn
typedef   struct  tagNode 
{ Data    Info;   // Lưu thông tin bản thân
  struct  tagNode  *pNext; //Lưu địa chỉ của Node đứng sau
}Node; 
Cấu trúc dữ liệu của DSLK đơn
typedef   struct  tagList 
{ Node  *pHead;//Lưu địa chỉ Node đầu tiên trong List
  Node  *pTail; //Lưu địa chỉ của Node cuối cùng trong List
}LIST;    // kiểu danh sách liên kết đơn

*các thao tác cơ bản trên danh sách liên kết
Tạo 1 danh sách liên kết đơn rỗng
Tạo 1 nút có trường Infor bằng x
Tìm một phần tử có Info bằng x
Thêm một phần tử có khóa x vào danh sách
Hủy một phần tử trong danh sách
Duyệt danh sách
Sắp xếp danh sách liên kết đơn

*khởi tạo danh ách liên kết
Địa chỉ của nút đầu tiên, địa chỉ của nút cuối cùng đều không có
  void CreateList(List &l) 
  {   
    l.pHead=NULL;
    l.pTail=NULL;
  }
*tạo 1 phần tử mới
Hàm trả về địa chỉ phần tử mới tạo
Node* CreateNode(Data x) // trong bài học là int
{ Node *p;
  p = new Node;//Cấp phát vùng nhớ cho phần tử
  if ( p==NULL)  exit(1); 
  p ->Info = x;   //gán dữa liệu cho nút
  p->pNext = NULL;
  return p; 
   }
*thêm 1 phần tử vào sánh sách liên kết
Nguyên tắc thêm: Khi thêm 1 phần tử vào List thì có làm cho pHead, pTail thay đổi?
Các vị trí cần thêm 1 phần tử vào List:
+)Thêm vào đầu List đơn
Thêm nút p vào đầu danh sách liên kết đơn
  Bắt đầu:
    Nếu List rỗng thì
      + pHead = p;
      + pTail = pHead;
    Ngược lại
      + p->pNext = pHead;
      + pHead = p
void AddHead(LIST &l, Node* p)
{
    if (l.pHead==NULL) 
    { 
      l.pHead = p; 
      l.pTail = l.pHead; 
    }
    else
    { 
      p->pNext = l.pHead;
        l.pHead = p;  
    }
}

+)Thêm vào cuối List
Ta cần thêm nút p vào cuối list đơn
  Bắt đầu:
    Nếu List rỗng thì
      + pHead = p;
      + pTail = pHead;
    Ngược lại
      + pTail->pNext=p;
      + pTail=p
  void AddTail(LIST &l, Node *p)
  {
    if (l.pHead==NULL)  
    { 
      l.pHead = p; 
      l.pTail = l.pHead; 
    }
    else
    { 
      l.pTail->Next = p;  
        l.pTail = p; 
    }
  }

+)Thêm vào sau 1 phần tử q trong list
Ta cần thêm nút p vào sau nút q trong list đơn
  Bắt đầu:
    Nếu (q!=NULL) thì
      B1: p->pNext = q->pNext
      B2:
    + q->pNext = p
        + nếu q = pTail thì
          pTail=p

  void InsertAfterQ(List &l, Node *p, Node *q)
  {
    if(q!=NULL)
    {
    p->pNext=q->Next;
    q->pNext=p;
    if(l.pTail==q) 
      l.Tail=p;
   }
   else
    AddHead(l,p);// thêm q vào đầu list
}

*hủy phần tử trong sanh sách liên kết
Nguyên tắc: Phải cô lập phần tử cần hủy trước hủy.
Các vị trị cần hủy
Hủy phần tử đứng đầu List
Hủy phần tử có khoá bằng x
Huỷ phần tử đứng sau q trong danh sách liên kết đơn
Ở phần trên, các phần tử trong DSLK đơn được cấp phát vùng nhớ động bằng hàm new, thì sẽ được giải phóng vùng nhớ bằng hàm delete.
 Bắt đầu:
Nếu (pHead!=NULL) thì
B1: p=pHead
B2:
+ pHead = pHead->pNext
+ delete (p)
B3:
 Nếu pHead==NULL thì pTail=NULL

Hủy được hàm trả về 1, ngược lại hàm trả về 0
  int   RemoveHead(List &l, int &x)
  { Node *p;
    if(l.pHead!=NULL)
    { p=l.pHead; 
      x=p->Info; //lưu Data của nút cần hủy 
      l.pHead=l.pHead->pNext;
      delete p;
      if(l.pHead==NULL)
        l.pTail=NULL;
      return 1;
    }
    return 0;
  }
Hủy phần tử sau phần tử q trong List
Bắt đầu
Nếu (q!=NULL) thì //q tồn tại trong List
B1: p=q->pNext;// p là phần tử cần hủy
B2: Nếu (p!=NULL) thì // q không phải là phần tử cuối
      + q->pNext=p->pNext;// tách p ra khỏi xâu
      + nếu (p== pTail) // nút cần hủy là nút cuối
        pTail=q;
      + delete p;// hủy p
      
  int RemoveAfterQ(List &l, Node *q, int &x)
  { Node *p;
    if(q!=NULL)
    { p=q->pNext; //p là nút cần xoá
      if(p!=NULL) // q không phài là nút cuối
      { if(p==l.pTail) //nút cần xoá là nút cuối cùng 
          l.pTail=q;// cập nhật lạ pTail
        q->pNext=p->pNext; x=p->Info;
        delete p;
      }
      return 1;
    }
    else 
         return 0;  }
Thuật toán hủy phần tử có khoá x
Bước 1:
    Tìm phần tử p có khoá bằng x, và q đứng trước p
Bước 2:
    Nếu (p!=NULL) thì //tìm thấy phần tử có khoá bằng x
      Hủy p ra khỏi List bằng cách hủy phần tử    đứng sau q
    Ngược lại
      Báo không tìm thấy phần tử có khoá
int RemoveX(List &l, int x)
{ Node *p,*q = NULL; p=l.Head;
  while((p!=NULL)&&(p->Info!=x)) //tìm
  { q=p;
    p=p->Next;
  }
  if(p==NULL) //không tìm thấy phần tử có khoá bằng x
    return 0;
  if(q!=NULL)//tìm thấy phần tử có khoá bằng x
    DeleteAfterQ(l,q,x);
  else //phần tử cần xoá nằm đầu List 
    RemoveHead(l,x);
  return 1;
}
Hàm tìm 1 phần tử trong DSLK đơn
  Hàm tìm phần tử có Info = x, hàm trả về địa chỉ của nút có Info = x, ngược lại hàm trả về NULL
Node *Search(LIST l, Data  x) 

    Node    *p;
    p = l.pHead;
    while((p!= NULL)&&(p->Info != x)) 
      p = p->pNext;
   return p;
}
Duyệt danh sách
Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu cần xử lý các phần tử trong danh sách như:
Đếm các phần tử trong danh sách
Tìm tất cả các phần tử trong danh sách thảo điều kiện
Hủy toàn bộ danh sách

Bước 1:
p = pHead;// p lưu địa chỉ của phần tử đầu trong List
Bước 2:
Trong khi (danh sách chưa hết) thực hiện
    + xử lý phần tử p
    + p=p->pNext;// qua phần tử kế

  void PrintList(List l)
  {
    Node *p;
    p=l.pHead;
    while(p!=NULL)
    { printf(“%d     ”, p->Info);
      p=p->pNext;
    }
  }
Hủy danh sách liên kết đơn
Bước 1:
Trong khi (danh sách chưa hết) thực hiện
B11:
  p = pHead;
  pHead = pHead->pNext;// cập nhật pHead
B12:
Hủy p
Bước 2:
  pTail = NULL;// bảo toàn tính nhất quán khi xâu rỗng

  void RemoveList(List &l)
  { 
    Node *p;
    while(l.pHead!=NULL)//còn phần tử trong List
    {
      p = l.pHead;
      l.pHead = p->pNext;
      delete p;
    }
  } 
Sắp xếp danh sách
Có hai cách tiếp cận
Cách 1: Thay đổi thành phần Info

Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn)
Thay đổi thành phần Info (dữ liệu)
Ưu: Cài đặt đơn giản, tương tự như sắp xếp mảng
Nhược:
Đòi hỏi thêm vùng nhớ khi hoán vị nội dung của 2 phần tử -> chỉ phù hợp với những xâu có kích thước Info nhỏ
Khi kích thước Info (dữ liệu) lớn chi phí cho việc hoán vị thành phần Info lớn
Làm cho thao tác sắp xếp chậm
Thay đổi thành phần pNext
Ưu:
Kích thước của trường này không thay đổi, do đó không phụ thuộc vào kích thước bản chất dữ liệu lưu tại mỗi nút.
Thao tác sắp xếp nhanh
Nhược: Cài đặt phức tạp
void SelectionSort(LIST &l)
{
    Node *p,*q,*min;
    p=l.pHead;
    while(p!=l.pTail)
   {
  min=p;
  q=p->pNext;
  --------------------------------------
  while(q!=NULL)
  { 
  if(q->Info<p->Info)
    min=q;
  q=q->pNext;
  }
  HV(min->Info,p->Info);
  p=p->pNext;
  }
    }

    Các thuật toán sắp xếp hiệu quả trên List
Các thuật toán sắp xếp xâu (List) bằng các thay đổi thành phần pNext (thành phần liên kết) có hiệu quả cao như:
Thuật toán sắp xếp Quick Sort
Thuật toán sắp xếp Merge Sort
Thuật toán sắp xếp Radix Sort

Thuật toán sắp xếp Quick Sort
Bước 1:
Chọn X là phần tử đầu xâu L làm phần tử cầm canh
Loại X ra khỏi L
Bước 2:
Tách xâu L ra làm 2 xâu L1(gồm các phần tử nhỏ hơn hoặc bằng x) và L2 (gồm các phần tử lớn hơn X)
Bước 3: Nếu (L1 !=NULL) thì QuickSort(L1)
Bước 4: Nếu (L2!=NULL) thì QuickSort(L2)
Bước 5: Nối L1, X, L2 lại theo thứ tự ta có xâu L đã được sắp xếp
Sắp xếp L1
Sắp xếp L2
Chọn x=6 cầm canh, và tách L2 thành L21 và L22
void QuickSort(List &l)
{ Node *p,*X;//X lưu địa chỉ của phần tử cầm canh
  List l1,l2;
  if(l.pHead==l.pTail) return;//đã có thứ tự
  CreateList(l1);
  CreateList(l2);
  X=l.pHead;
  l.pHead=X->pNext;
  while(l.pHead!=NULL)//tách L = L1 va L2
  { p=l.pHead;
    l.pHead=p->pNext;
    p->pNext=NULL;
    if(p->Info<=X->Info)
      AddHead(l1,p);
    else
      AddHead(l2,p);
  }
  QuickSort(l1);//Gọi đệ quy sắp xếp L1
  QuickSort(l2);//Gọi đệ quy sắp xếp L2
  if(l1.pHead!=NULL)//nối l1, l2 va X vao l
  {
    l.pHead=l1.pHead;
    l1.pTail->pNext=X;//nối X vào
  }
  else
    l.pHead=X;
  X->pNext=l2.pHead;
  if(l2.pHead!=NULL) //l2 có trên một phần tử
    l.pTail=l2.pTail;
  else  //l2 không có phần tử nào 
    l.pTail=X;
}


Thuật tốn sắp xếp Merge Sort
Bước 1: Phân phối luân phiên từng đường chạy của xâu L vào 2 xâu con L1 và L2.
Bước 2: Nếu L1 != NULL thì Merge Sort (L1).
Bước 3: Nếu L2 != NULL thì Merge Sort (L2).
Bước 4: Trộn L1 và L2 đã sắp xếp lại ta có xâu L                đã được sắp xếp.
Không tốn thêm không gian lưu trữ cho các dãy phụ


Cài đặt hàm main()
Yêu cầu: Viết chương trình thành lập 1 xâu đơn, trong đó thành phần dữ liệu của mỗi nút là 1 số nguyên dương.
Liệt kê tất thành phần dữ liệu của tất cả các nút trong xâu
Tìm 1 phần tử có khoá bằng x trong xâu.
Xoá 1 phần tử đầu xâu
Xoá 1 phần tử có khoá bằng x trong xâu
Sắp xếp xâu tăng dần theo thành phần dữ liệu (Info)
Chèn 1 phần tử vào xâu, sao cho sau khi chèn xâu vẫn tăng dần theo trường dữ liệu
..vv
  void main()
  {   LIST  l1; Node *p; int x;
    CreateList(l1);
    do{
      printf(“nhap x=”); scanf(“%d”,&x);
      if(x>0)  
      {   p = CreateNode(x);
        AddHead(l1,x);
      } 
    }while(x>0);
    printf(“Danh sách mới thành lập là\n”);
    PrintList(l1);
    printf(“nhập x cần tìm x=”); scanf(“%d”,&x);
  
    p = Search(l1,x);
    if(p==NULL) printf(“không tìm thấy”);
    else printf(“tìm thấy”); 
    RemoveHead(l1,x);
    printf(“danh sách sau khi xóa\n”);
    PrintList(l1);
    printf(“nhập khoá cần xoá\n”);
    scanf(“%d”,&x);
    RemoveX(l1,x);

    printf(“danh sách sau khi xoá”);
    PrintfList(l1);
    SelectionSort(l1);
    printf(“Danh sách sau khi sắp xếp”);
    PrintfList(l1);
    RemoveList(l1);
}

sắp xếp trộn run sắp xếp ngoại

sắp xếp trộn run sắp xếp ngoại

 Phương pháp trộn Run
Khái niệm cơ bản:
 Run là một dãy liên tiếp các phần tử được sắp thứ tự. Ví dụ 2  4  7  12  50 là một run gồm có 5 phần tử
 Chiều dài run chính là số phần tử trong Run. Chẳng hạn, run trong ví dụ trên có chiều dài là 5.
 7 8 5 3 9 12 4 23 78 90 45 54


Giải thuật: Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau: Input: f0 là tập tin cần sắp thứ tự. Output: f0 là tập tin đã được sắp thứ tự. Gọi f1, f2 là 2 tập tin trộn. Các tập tin f0, f1, f2 có thể là các tập tin tuần tự (text file) hay có thể là các tập tin nhị phân.

 Bước 1:
 - Giả sử các phần tử trên f0 là:  24 12 67 33 58 42 11 34 29 31
 - Khởi tạo f1, f2 rỗng
 - Thực hiện phân bố m=1 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 24 67 58 11 29 f2: 12 33 42 34 31
 Trộn f1, f2 thành f0:
 f0: 12 24 33 67 42 58 11 34 29 31

 Bước 2:
 -Phân bố m=2 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 12 24 42 58 29 31
f0: 12 24 33 67 42 58 11 34 29 31
f2: 33 67 11 34
- Trộn f1, f2 thành f0: f1: 12 24 42 58 29 31 f0: 12 24 33 67 11 34 42 58 29 31 f2: 33 67 11 34

Bước 3: - Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và f2, kết quả thu được như sau: f1: 12 24 33 67 29 31 f2: 11 34 42 58 - Trộn f1, f2 thành f0: f0: 11 12 24 33 34 42 58 67 29 31

Bước 4: - Phân bố m=8 phần tử lần lượt từ f0 vào f1 và  f2: f1: 11 12 24 33 34 42 58 67 f2: 29 31 - Trộn f1, f2 thành f0: f0: 11 12 24 29 31 33 34 42 58 67

Bước 5: Lặp lại tương tự các bước trên, cho đến khi chiều dài m của run cần phân bổ lớn hơn chiều dài n của f0 thì dừng.

void chia(FILE *a,FILE *b,FILE *c,int p) void main (void) { FILE *a,*b,*c; tao_file(); xuat_file(); p = 1; while (p < n) { chia(a,b,c,p); tron(b,c,a,p); p=2*p; } }

void chia(FILE *a,FILE *b,FILE *c,int p) while (!feof(a)) { /*Chia p phan tu cho b*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(b,"%3d",x); dem++; }

 dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }
 void tron(FILE *b,FILE *c,FILE *a,int p) int stop,x,y,l,r; a=fopen("d:\ctdl\sortfile\bang.int","wb"); b=fopen("d:\ctdl\sortfile\bang1.int","rb"); c=fopen("d:\ctdl\sortfile\bang2.int","rb"); while ((!feof(b)) && (!feof(c))) { l=0;/*so phan tu cua b da ghi len a*/ r=0;/*so phan tu cua c da ghi len a*/ fscanf(b,"%3d",&x); fscanf(c,"%3d",&y); stop=0;

while ((l!=p) && (r!=p) && (!stop)) { if (x<y) { fprintf(a,"%3d",x); l++; if ((l<p) && (!feof(b))) /*chua du p phan tu va chua het file b*/ fscanf(b,"%3d",&x); else { fprintf(a,"%3d",y); r++; if (feof(b)) stop=1; } }

else
{
fprintf(a,"%3d",y); r++; if ((r<p) && (!feof(c))) /*chua du p phan tu va chua het file c*/ fscanf(c,"%3d",&y); else {

fprintf(a,"%3d",x); l++; if (feof(c)) stop=1; } } } //Chep phan con lai cua p phan tu tren b len a
while ((!feof(b)) && (l<p)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); l++; }

//Chep phan con lai cua p phan tu tren c len a while ((!feof(c)) && (r<p)) { fscanf(c,"%3d",&y); fprintf(a,"%3d",y); r++; } } if (!feof(b)) { /*chep phan con lai cua b len a*/ while (!feof(b)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); } }

{
fscanf(c,"%3d",&x); fprintf(a,"%3d",x);
} } fclose(a);  fclose(b);  fclose(c); }

 /*Chia p phan tu cho c*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }