ThuatToan.Net: tháng 4 2015

Thứ Tư, 29 tháng 4, 2015

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




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

Chủ Nhật, 26 tháng 4, 2015

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

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

Thứ Bảy, 25 tháng 4, 2015

thư viện vector STL C++

SỬ DỤNG STL VECTOR TRONG C++

Nguyễn Trí Hải

11520094

KHMT06

I) Giới thiệu:

Lớp mảng động vector<T>có sẵn trong thư viện chuẩn STL của C++ cho phép định nghĩa một mảng động các phần tử kiểu T, vector có các tính chất sau:

- Không cần phải khai báo kích thước của mảng vector có thể tự động cấp phát bộ nhớ, bạn sẽ không phải quan tâm đến quản lý kích thước của nó.

- Vector còn có thể cho bạn biết số lượng các phần tử mà bạn đang lưu trong nó.

- Vector có các phương thức của stack.

- Hỗ trợ tất cả các thao tác cơ bản như chèn ,xóa, sao chép ..

II) Vì sao dùng Vector:

à…

Kiểu vector có thể coi là kiểu mảng trong lập trình C truyền thống. Mảng là tập hợp các giá trị cùng kiểu, được sắp xếp nối tiếp nhau. Các phần tử của mảng có thể được truy cập ngẫu nhiên qua chỉ số.

Vấn đề đặt ra: Nếu vector là mảng thì tại sao lại phải sử dụng vector khi bạn đã quá quen thuộc với mảng?

- Nếu bạn sử dụng mảng tĩnh: Mảng này luôn được khai báo với kích thước tối đa mà bạn có thể dùng dẫn đến tốn nhiều vùng nhớ thừa.

- Nếu bạn sử dụng mảng động: Bạn phải xin cấp phát bộ nhớ, làm việc với con trỏ. Con trỏ là

khái niệm hay trong C, C++, nhưng nó là nguyên nhân của rất nhiều rắc rối trong lập trình.

- Không thuận tiện trong việc truyền tham số kiểu mảng vào hàm hay trả lại kiểu mảng từ hàm.

- Nhược điểm quan trọng nhất: Nếu bạn sử dụng mảng vượt chỉ số vượt quá kích thước đã khai báo, C++ sẽ không thông báo lỗi, điều này dẫn đến lỗi dây chuyền do các lệnh lỗi đã tác động đến các biến khác trong chương trình

Vector là một container cung cấp khả năng sử dụng mảng mềm dẻo, có kiểm soát range check khi cần thiết, với kích thước tùy ý (mà không cần phải sử dụng con trỏ). Ngoài ra vector cho phép bạn chèn thêm hoặc xóa đi một số phần tử chỉ bằng 1 lệnh (không phải sử dụng vòng lặp như đối với mảng).

III) Cú pháp:

Để dùng vector thì cần thêm 1 header #include <vector>và phải có using std::vector; vì vector được định nghĩa trong STL (Standard Template Library)

Ví dụ:

vector<int> A;

Câu lệnh trên định nghĩa 1 vector có kiểu int. Kiểu vector được đặt trong 2 dấu ngoặc nhọn. Kích thước của vector có thể tự nâng lên nên không cần khai báo số phần tử hoặc nếu muốn khai báo thì bạn có thể khai báo như sau:

vector<int> A(10);

Câu lệnh trên khai báo A là 1 vector kiểu int có 10 phần tử. Mặc dù size của nó bằng 10 nhưng sử dụng hơn vẫn được.

Ta có thể khởi tạo giá trị mặc định cho vector:

vector<int> A(10,2);

Câu lệnh trên khai báo 10 phần tử vector A được khởi tạo bằng 2.Đồng thời ta cũng có thể khởi tạo cho 1 vector sẽ là bản sao của 1 hoặc 1 phần vector khác, ví dụ :

vector<int> A(10,2);

vector<int> B(A);

vector<int> C(A.begin(), A.begin() + 5 );

Để hiểu rõ vè vector, ta xem đoạn code sau:

#include<iostream> // Thư viện iostream phục vụ ghi dữ liệu ra màn hình

#include<vector> // Thư viện vector, sử dụng kiểu vector

usingnamespace std; // Sử dụng namespace std

int main()

{

vector<int> V(3);

// V kiểu vector số nguyên (sử dụng giống mảng int[3])

V[0] = 5;

// Gán giá trị cho các phần tử của biến V

V[1] = 6;

// Sử dụng dấu móc [] hoàn toàn giống với mảng

V[2] = 7;

for (int i=0; i<V.size(); i++)

// Ghi giá trị các phần tử của V ra màn hình

cout << V[i] << endl;

// Nếu sử dụng mảng, bạn phải có biến lưu kích thước

}

Ví dụ trên cho bạn thấy việc sử dụng vector rất đơn giản, hoàn toàn giống với mảng nhưng bộ nhớ được quản lý tự động, bạn không phải quan tâm đến giải phóng các vùng bộ nhớ đã xin cấp phát.

Trường hợp xác định kích thước mảng khi chương trình đang chạy, chúng ta dùng hàm dựng mặc định (default constructor) để khai báo mảng chưa xác định kích thước, sau đó dùng phương thức resize() để xác định kích thước của mảng khi cần. Chương trình sau đây nhập vào n từ (word) mỗi từ là một chuỗi kiểu string:

#include<iostream>

#include<string>

#include<vector>

usingnamespace std;

int main()

{

int iWordNum;

vector<string> arrWords;

cout <<"Enter number of words = ";

cin >> iWordNum;

arrWords.resize(iWordNum);

for (int i = 0; i < arrWords.size(); i ++)

{

cout <<"Enter word "<< i <<" = ";

cin >> arrWords[i];

}

cout <<"After entering data..."<< endl;

for (int i = 0; i < arrWords.size(); i ++)

cout << arrWords[i] << endl;

}

Ouput:

Enter number of words = 3

Enter word 1 = hello

Enter word 1 = c++’s

Enter word 1 = world

After entering data...

hello

c++’s

world

Press any key to continue . . .

IV) Các phương thức:

Các phương thức của stack: push_back() và pop_back()

#include<iostream>

#include<vector>

usingnamespace std;

int main()

{

int i;

vector<int> V;

for (i=0; i<5; i++)

// Lặp 5 lần, mỗi l ần đưa thêm 1 số vào vector

V.push_back(i);

// Như vậy, vector có thể được sử dụng như stack

cout << endl <<"Mang ban dau:"<< endl;

for (i=0; i<V.size(); i++)

// Ghi lại nội dung của mảng ra màn h.nh

cout << V[i] << endl;

V.pop_back( ); // Xóa phần tử vừa chèn vào đi

cout << endl <<"Xoa phan tu cuoi:"<< endl;

for (i=0; i<V.size(); i++)

// In nội dung của vector sau khi xóa

cout << V[i] << endl;

return 0;

}

Với ví dụ trên, bạn có thể thấy ta có thể sử dụng vector như 1 stack:

- Không nên dùng toán tử [] để truy xuất các phần tử mà nó không tồn tại, nghĩa là ví dụvector size = 10, mà bạn truy xuất 11 là sai. Để thêm vào 1 giá trị cho vector mà nó không có size trước hoặc đã full thì ta dùng hàm thành viên push_back(), hàm này s ẽ thêm 1 phần tửvào cuối vector.

- Tương tự với thao tác xóa một phần tử ở cuối ra khỏi vector, bạn cũng chỉ cần sử dụng 1 lệnh: pop_back( )

Xóa tại vị trí bất kỳ, xóa trắng:

#include<iostream>

#include<vector>

usingnamespace std;

template<classT>

void print(constvector<T>&v)

{

for (int i =0; i <v.size(); i++)

cout <<v[i] << endl;

}

int main()

{

char *chao[] = {"Xin", "chao", "tat", "ca", "cac", "ban"};

int n = sizeof(chao)/sizeof(*chao);

vector<char*> v(chao, chao + n);

//đây là 1 cách khởi tạo vector

cout <<"vector truoc khi xoa"<< endl;

print(v);

v.erase(v.begin()+ 2, v.begin()+ 5);

//xóa từ phần tử thứ 2 đến phần tử thứ 5

v.erase( v.begin()+1 );

//xóa phần tử thứ 1

cout <<"vector sau khi xoa"<< endl;

print(v);

v.clear();//Xóa toàn bộ các phần tử

cout <<"Vector sau khi clear co "

<< v.size() <<" phan tu"<< endl;

return 0;

}

Output:

vector truoc khi xoa

Xin

chao

tat

cac

ban

vector sau khi xoa

xin

ban

Vector sau khi clear co 0 phan tu

Phương thức chèn

iterator insert ( iterator position, const T& x );

void insert ( iterator position, size_type n, const T& x );

void insert ( iterator position, InputIterator first, InputIterator last );

Ví dụ:

// inserting into a vector

#include<iostream>

#include<vector>

usingnamespace std;

int main ()

{

vector<int> v1(4,100);

v1.insert ( v1.begin()+3 , 200 );

//chèn 200 vào trước vị trí thứ 3

v1.insert ( v1.begin()+2 ,2,300);

//chèn 2 lần 300 vào trước vị trí thứ 2

vector<int> v2(2,400);

int a [] = { 501, 502, 503 };

v1.insert (v1.begin()+2, a, a+3);

//chèn mảng a (3 phần tử) vào trước vị trí thứ 2

v1.insert (v1.begin()+4,v2.begin(),v2.end());

//chèn v2 vào trước vị trí thứ 4

cout <<"v1 contains:";

for (int i =0; i < v1.size(); i ++)

cout <<" "<< v1[i];

return 0;

}

Output:

v1 contains: 100 100 501 502 400 400 503 100 200 300 300 100

Một số hàm khác và chức năng

Những toán tử so sánh: được định nghĩa cho vector: ==, <, <=, !=, >, >=

Tham chiếu back(), front()

template<class _TYPE, class _A>

reference vector::front( );

template<class _TYPE, class _A>

reference vector::back( );

Trả về tham chiếu đến phần tử đầu và cuối vector:

v.front()  v[0] và v.back()  v[v.size()-1]

#include<iostream>

#include<vector>

usingnamespace std;

int main ()

{

int a[] = {3,2,3,1,2,3,5,7};

int n = sizeof(a)/sizeof(*a);

vector<int> v(a, a+n);

cout <<"phan tu dau la "<< v.front() << endl;

cout <<"phan tu cuoi la "<< v.back() << endl;

cout <<"gan phan tu cuoi la 9 ..."<< endl;

v.back() = 9;

cout <<"gan phan tu dau la 100 ..."<< endl;

v.front() = 100;

cout <<"kiem tra lai vector: ";

for (int i =0; i < v.size(); i++)

cout << v[i] << “ “;

cout << endl;

return 0;

}

Output:

phan tu dau la 3

phan tu cuoi la 7

gan phan tu cuoi la 9 ...

gan phan tu dau la 100 ...

kiem tra lai vector: 100 2 3 1 2 3 5 9

Press any key to continue …

Hàm thành viên empty()

Để xác định vector có rỗng hay không ta dùng hàm thành viên empty(), hàm này trả về true nếu vector rỗng, và false ngược lại. Cú pháp :

if(v.empty() == true) {

cout <<"No values in vector \n";

}

- capacity() : Trả về số lượng phần tử tối đa mà vector được cấp phát, đây là 1 con s ố có thể thay đổi do việc cấp phát bộ nhớ tự động hay bằng các hàm như reserve() và resize()

Sự khác biệt giữa 2 hàm size() và capacity() :

#include<vector>

#include<iostream>

int main(int argc , char **argc)

{

vector<int>so1,so2[10];

so1.reserve(10);

cout <<"Kich thuoc toi da:"<<so1.capacity();

cout <<"\n Kich thuoc hien tai cua mang 2 "<<so2.size()<<endl;

return 0 ;

}

- reserve(): cấp phát vùng nhớ cho vector, giống như realloc() của C và không giống vector::resize(), tác dụng của reserve để hạn chế vector tự cấp phát vùng nhớ không cần thiết.Ví dụ khi bạn thêm 1 phần tử mà vượt quá capacity thì vector sẽ cấp phát thêm, việc này lặp đi lặp lại sẽ làm giảm performance trong khi có những trường hợp ta có thểước lượng được cần sử dụng bao nhiêu bộ nhớ.

Ví dụ nếu ko có reserve() thì capacity sẽ là 4 :

#include<iostream>

#include<vector>

usingnamespace std;

int main()

{

vector<int> my_vect;

my_vect.reserve( 8 );

my_vect.push_back( 1 );

my_vect.push_back( 2 );

my_vect.push_back( 3 );

cout << my_vect.capacity() <<"\n";

return 0;

}

- swap(); hoán đổi 2 container v ới nhau (gi ống việc hoán đổi giá trị của 2 biến kiểu số). Ví dụ : v1.swap(v2);

V.Kiểm tra tràn chỉ số mảng:

Có một vấn đề chưa được đề cập đến từ khi ta làm quen với vector, đó là khả năng kiểm tra tràn chỉ số mảng (rangecheck), để biết về khả năng này, chúng ta lại ti ếp tục với một ví dụmới :

#include<iostream>

#include<vector>

#include<conio.h>

usingnamespace std;

int main()

{

try { // sử dụng try...catch để bẫy lỗi

vector<long> V(3, 10);

// Khởi tạo vector gồm 3 thành phần

// Tất cả gán giá trị 10

cout <<"V[0]="<< V[0] << endl;

// Đưa thành phần 0 ra màn hình

cout <<"V[1]="<< V[1] << endl;

// Đưa thành phần 1 ra màn hình

cout <<"V[2]="<< V[2] << endl;

// Đưa thành phần 2 ra màn hình

cout <<"V[3]="<< V[3] << endl;

// Thành phần 3 (lệnh này hoạt động không

// đúng vì V chỉ có 3 thành phần 0,1,2

cout <<"V[4]="<< V[4] << endl;

// Thành phần 4 (càng không đúng)

// Nhưng 2 lệnh trên đều không gây lỗi

cout <<"V[0]="<< V.at(0) << endl;

// Không sử dụng [], dùng phương thức at

cout <<"V[1]="<< V.at(1) << endl;

// Thành phần 1, OK

cout <<"V[2]="<< V.at(2) << endl;

// Thành phần 2, OK

cout <<"V[3]="<< V.at(3) << endl;

// Thành phần 3: Lỗi, chương trình dừng

cout <<"V[4]="<< V.at(4) << endl;

getchar();

} catch (exception&e) {

cout <<"Tran chi so ! "<< endl;

}

return 0;

}

Trong ví dụ này, chúng ta lại có thêm một số kinh nghiệm sau:

- Nếu sử dụng cú pháp biến_vector[chỉ _số], chương trình sẽ không tạo ra lỗi khi s ử dụng chỉ số mảng nằm ngoài vùng hợp lệ (giống như mảng thường). Trong ví dụ, chúng ta mới chỉ lấy giá trị phần tử với chỉ số không hợp lệ, trường hợp này chỉ cho kết quả sai. Nhưng nếu chúng ta gán giá trị cho phần tử không hợp lệ này, hậu quả sẽnghiêm trọng hơn nhiều vì thao tác đó sẽ làm hỏng các giá trị khác trên bộ nhớ.

- Phương thức at(chỉ _số) có tác dụng tương tự như dùng ký hiệu [], nhưng có một sự khác biệt là thao tác này có kiểm tra chỉ số hợp lệ. Minh chứng cho nhận xét này trong ví dụ khi chương trình chạy đến vị trí lệnh V.at(3), lệnh này không cho ra kết quả mà tạo thành thông báo lỗi.

VI.Mảng 2 chiều với Vector:

#include<iostream>

#include<vector>

usingnamespace std;

int main()

{

vector<vector<int>> matrix(3, vector<int>(2,0));

//chu y viet >> de khong nham voi toan tu >>

for(int x = 0; x < 3; x++)

for(int y = 0; y < 2; y++)

matrix[x][y] = x*y;

for(int x = 0; x < 3; x++)

for(int y = 0; y < 2; y++)

cout << matrix[x][y];

cout <<'\n';

return 0;

}

Ví dụ này minh họa việc sử dụng mảng 2 chiều, thực chất đây là một vector của vector. Mảng 2 chiều sử dụng biện pháp này có thể có kích thước khác nhau giữa các d.ng (ví dụ mảng 2 chiều là nửa trên của ma trận)

VII.Sử dụng iterator

Container ( thùng chứa ) : Một kiểu cấu trúc dữ liệu dùng để lưu trữthông tin. Ví dụ: mảng (array), list, vector, deque...

Container nào cũng có các phương thức sau đây

Phương thức	Mô tả
size()	Số lượng phần tử
empty ()	Trả về 1 nếu container rỗng, 0 nếu ngược lại.
max_size()	Trả về số lượng phần tử tối đa đã được cấp phát
==	Trả về 1 nếu hai container giống nhau
!=	Trả về 1 nếu hai v khác nhau
begin()	Trả về iterator đầu tiên của container
end()	Trả về iterator lặp cuối cùng của container
front()	Trả về tham chiếu đến phần tử đầu tiên của container
back()	Trả về tham chiếu đến phần tử cuối cùng của container
swap()	Hoán đổi 2 container với nhau (giống việc hoán đổi giá trị của 2 biến)

Trong thư viện STL thì người ta tích hợp lớp đối tượng Iterator (bộ lặp hay biến lặp) cùng với các container.Tư tưởng đó thể hiện như sau:

o Các đối tượng Iterator là các con trỏ đến các đối tượng của lớp lưu trữ:

typedef__gnu_cxx::__normal_iterator <pointer,vector_type> iterator;

o Khai báo lớp Iterator như là 1 lớp nằm trong lớp lưu trữ.

o Xác định trong lớp lưu trữ các phương thức thành phần như:

+ begin() – trả lại con trỏ kiểu đối tượng Iterartor đến phần tử đầu tiên của nằm trong đối tượng lớp lưu trữ.

+ end() – trả lại con trỏ kiểu Iterator trỏ đến 1 đối tượng nào đó bên ngoài tập các phần tử được lưu trữ. Đối tượng bên ngoài nào đó có thể có các định nghĩa khác nhau.Trong trường hợp cụ thể như vector ta có thể hiểu là trỏ đến phần tử sau phần tử cuối cùng.

o Xác định trong lớp đối tượng kiểu Iterator các toán tử như sau:

++p hoặc p++ : chuyển iterator p đến phần tử kế tiếp.

--p hoặc p-- : chuyển iterator p đến phần tử đằng trước nó.

*p : xác định giá trị của phần tử mà iterator p trỏ đến.

Như bạn biết, mảng và con trỏ có mối quan hệ chặt chẽ với nhau trong C++. Một mảng có thể được truy xuất thông qua con trỏ. Sự tương đương này trong STL là mối quan hệ giữa iterator và vector, mà tổng quát hơn là với container. Nó cung cấp cho chúng ta khả năng xử lý theo chu kì thông qua nội dung của container theo một cách giống như là bạn sử dụng con trỏ để tạo xử lý chu kỳ trong mảng.

Bạn có thể truy xuất đến các thành phần của một container bằng sử dụng một iterator:

<container> coll;

for (<container>::iterator it = coll.begin(); it != coll.end(); ++it)

{

*it;

//……..

}

Dưới đây chúng ta xét 1 ví dụ làm việc với thư viện STL với lớp vector và con trỏ kiểu iterator như sau:

#include<iostream>

#include<vector>

using std::vector;

void main()

{

vector<int> v;

for(int i = 10; i < 15; i++) v.push_back(i );

vector<int>::iterator it = v.begin();

while(it != v.end())

{

cout << *it <<" ";

it++;

}

Vì iterator định nghĩa bên trong các container – thế nào là “phần tử đầu”, “phần tử cuối”, “phần tử tiếp theo” … nên nó “chứa” thông tin cấu trúc phục vụ cho việc duyệt container. Nó che đi cấu trúc bên trong và cho phép ta viết các đoạn mã tổng quát để duyệt hay chọn phần tử trên các container khác nhau mà không cần biết cấu trúc của container đó ra sao.

Trong các reversible container như vector còn định nghĩa thêm reverse_iterator (cái tên nói lên chức năng: iterator nghịch đảo) là nested class với các “hằng” tương ứng:

vector<T>::reverse_iterator rbegin();

vector<T>::reverse_iterator rend();

Ví dụ : duyệt vector theo 2 chiều

#include<iostream>

#include<algorithm>

#include<stdlib.h>

#include<vector>

usingnamespace std;

int main()

{

int A[] = {3,2,3,1,2,3,5,3};

int n = sizeof(A)/sizeof(*A);

vector<int> V;

for (int i=0; i<n; i++){

V.push_back(A[i]);

vector<int>::iterator vi;

cout << endl <<"Duyet chieu xuoi"<< endl;

for (vi=V.begin(); vi!=V.end(); vi++)

cout << *vi << endl;

vector<int>::reverse_iterator rvi;

cout << endl <<"Duyet theo chieu nguoc"<< endl;

for (rvi=V.rbegin(); rvi!=V.rend(); rvi++)

cout << *rvi << endl;

getchar();

}

Chuyển đổi qua lại giữa reverse_iterator và iterator:

+ Hàm thành viên base(): trả về một iterator trỏ đến phần tử hiện tại của reverse_iterator.

+ Tạo reverse_iterator từ iterator: Contructor reverse_iterator(RandomAccessIterator i);

Ví dụ:

vector<int> v;

vector<int>::iterator it (v.begin());

vector<int>:: reverse_iterator ri(v.rbegin());

//goi contructor

assert(ri.base()==v.end()-1);

ri=v.begin();

//goi contructor

assert(ri.base()==it);

*Lệnh assert(); dùng để kiểm tra một biểu thức điều kiện.

Iterator là 1 trong 4 thành phần chính của STL (container, iterator, algorithm và functor).Container và algorithm giao tiếp qua nó: nhiều hàm và algorithm trong STL nhận các đối số là iterator.Iterator gắn liền với tất cả các loại container, đây là khái ni ệm bạn cần nắm rất vững nếu muốn làm việc tốt với STL

Bảng: các hàm thành viên lớp vector

Hàm thành phần	Mô tả
template<class lnlter> void assign(lnlter start, lnlter end);	Gán giá trị cho vector theo trình tự từ start đến end.
Template<class Size, class T) Void assign(Size num, const T &val = T());	Gán giá trị của val cho num phần tử của vector.
Reference at(size_type l); Const_reference at(size_type l) const;	Trả về một tham chiếu đến một phần tử được chỉ định bởi i.
Reference back(size_type l); Const_reference at(size_type l) const;	Trả về một tham chiếu đến phần tử cuôi cùng của vector.
Iterator begin(); Const _iterator begin() const;	Trả về một biến lặp chỉ định phần tử đầu tiên của vector.
Size_type capacity() const;	Trả về dung lượng hiện thời của vector. Đây là số lượng các phần tử mà nó có thể chứa trước khi nó cần cấp phát thêm vùng nhớ.
Void clear();	Xóa tất cả các phần tử trong vector.
Bool empty() const;	Trả về true nếu vector rỗng và trả về false nếu ngược lại.
Iterator end(); Const_iterator end() const;	Trả về một biến lặp để kết thúc một vector.
iterator erase(iterator i);	Xóa một phần tử được chỉ bởi i. Trả về một biến lặp chỉ đến phần tử sau phần tử được xóa.
Iterator erase(iterator start, iterator end);	Xóa những phần tử trong dãy từ start đến end. Trả về một biến lặp chỉ đến phần tử sau cùng của vector.
Reference front(); Const_reference front() const;	Trả về một tham chiếu đến phần tử đầu tiên của vector.
Allocator_type get_allocator() const;	Trả về vùng nhớ được cấp phát cho vector.
Iterator insert(iterator I, const T&val=T());	Chèn val trực tiếp vào trước thành phần được chỉ định bởi i. biến lặp chỉ đến phần tử được trả về.
Void insert(iterator I, size_type num, const T&val);	Chèn num val một cách trực tiếp trước phần tử được chỉ định bởi i.
Template<class lnlter> Void insert(iterator I, lnlter start, lnltr end);	Chèn chuỗi xác định từ start đến end trực tiếp trước một phần tử được chỉ định bởi i.
Size_type max_size() const;	Trả về số lượng phần tử lớn nhất mà vector có thể chứa.
Reference operator[](size_type i) const; Const_reference operator[] (size_type i) const;	Trả về một tham chiếu đến phần tử được chỉ định bởi i.
Void pop_back();	Xóa phần tử cuối cùng trong vector.
Void push_back(cons T&val);	Thêm vào một phần tử có giá trị val vào cuối của vector.
Reverse_iterator rbegin(); Const_reverse_iterator rbegin() const;	Trả về biến lặp nghịch chỉ điểm kết thúc của vector.
Reverse_iterator rend(); Const_reverse_iterator rend() const;	Trả về một biến lặp nghịch chỉ điểm bắt đầu của vector.
Void reverse (size_type num);	Thiết lập kích thước của vector nhiều nhất là bằng num.
Void resize (size_type num, T val =T());	Chuyển đổi kích thước của vector được xác định bởi num. Nếu như kích thước của vector tăng lên thì các phần tử có giá trị val sẽ được thêm vào cuối vector.
Size_type size() const;	Trả về số lượng các phần tử hiện thời của trong vector.
Vois swap(vector<T, Allocator>&ob)	Chuyển đổi những phần tử được lưu trong vector hiện thời với những phần tử trong ob.

VIII.Dùng 1 số hàm cơ bản trong thư viện algorithm

Khởi tạo:

Bạn có thể sử dụng lệnh fill của thư viện <algorithm> để tô một vùng giá trị của 1 container (thường là 1 mảng, 1 vector)

// fill algorithm example

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespace std;

void printint(constint&i)

{

cout << i << endl;

}

int main ()

{

vector<int> v(8); // v: 0 0 0 0 0 0 0 0

fill(v.begin(),v.begin()+4,5); // v: 5 5 5 5 0 0 0 0

fill(v.begin()+3,v.end()-2,8); // v: 5 5 5 8 8 8 0 0

cout <<"vector contains:";

for_each( v.begin(), v.end(), printint );

return0;

}

template<classForwardIterator, classGenerator>

void generate(ForwardIterator first, ForwardIterator last, Generator gen);

Hàm generate sẽ “sinh” từng phần tử trong khoảng nào đấy của vector bằng cách gọi hàm được chỉ định ( một hàm

trả về cùng kiểu và không có đối số)

Ví dụ với hàm rand():

vector<int> V;

srand( time(NULL) );

//...

generate( V.begin(), V.end(), rand );

Copy iterator ( tương tựmemcpy() đối với pointer )

int a[] = {1, 2, 3, 4, 5, 6};

int n = sizeof(a)/sizeof(*a);

vector<int> v1(a, a+n);

vector<int> v2(n);

copy(v1.begin(), v1.end(), v2.begin());

//copy_n(v1.begin(), v1.size(), v2.begin());

for (int i =0; i <n; i++)

cout << v2[i] <<" ";

// The output is "1 2 3 4 5 6".

Đảo ngược (reverse) vector

Bạn có thể sử dụng lệnh reverse trong <algorithm> để đảo ngược container (ở đây là 1 vector)

// reverse algorithm example

#include<iostream>

#include<algorithm>

#include<vector> tr.nh C++ Nguyễn Phú Quảng

#include<conio.h>

usingnamespace std;

int main ()

{

vector<int> a;

// set some values:

for (int i=1; i<10; ++i) a.push_back(i); // 1 2 3 4 5 6 7 8 9

reverse(a.begin(),a.end()); // 9 8 7 6 5 4 3 2 1

// print out content:

cout <<"a contains:";

int i, n = a.size();

for (i=0; i<n; i++)

cout << a[i] <<" ";

cout << endl;

getchar();

}

Thay thế các giá trị (replace)

Lệnh replace tìm kiếm 1 giá trị trong container, ở đây là vector thay thế giá trị tìm được bởi giá trị mới.

// replace algorithm example

#include<iostream>

#include<algorithm>

#include<vector>

#include<conio.h>

usingnamespace std;

int main ()

{

int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20 };

vector<int> a (myints, myints+8); // 10 20 30 30 20 10 10 20

replace(a.begin(), a.end(), 20, 99); // 10 99 30 30 99 10 10 99

cout <<"a contains: ";

int i, n;

for (i=0, n=a.size(); i<n; i++)

cout << a[i] <<" ";

getchar();

}

Thay thế các giá trị theo điều kiện (replace_if)

Các hàm có hậu tố _if như remove_if, replace_if, find_if, count_if … sử dụng 1 con trỏ hàm hoặc 1 functor để làm tiêu chí tìm kiếm (dạng của con trỏ hàm hoặc functor tùy vào mục đích sử dụng)

Lệnh replace_if cho phép tìm giá trị theo điều kiện do một hàm trả về. Để sử dụng lệnh này bạn phải khai báo 1 hàm có giá trị trả về là bool nhận tham số là giá tr ị của 1 element. Khi hàm trả về true, giá trị tương ứng sẽ bị thay thế bởi giá trị mới. Hàm ki ểm tra nên khai báo inline để tốc độ nhanh hơn.

// replace_if example

#include<iostream>

#include<algorithm>

#include<vector>

#include<conio.h>

usingnamespace std;

inlinebool SoLe(int i) { return ((i%2)==1); }

int main ()

{

vector<int> a;

// set some values:

for (int i=1; i<10; i++) a.push_back(i); // 1 2 3 4 5 6 7 8 9

replace_if(a.begin(), a.end(), SoLe, 0); // 0 2 0 4 0 6 0 8 0

cout <<"a contains: ";

int i, n;

for (i=0, n=a.size(); i<n; i++)

cout << a[i] <<" ";

getchar();

}

Xóa với remove và remove_if

Ví dụ 1:

//remove

int A[] = {3,1,4,1,5,9};

int N = sizeof(A)/sizeof(*A);

vector<int> V(A, A+N);

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));

//The output is "3 1 4 1 5 9".

cout << endl;

vector<int>::iterator new_end =

remove(V.begin(), V.end(), 1);

V.resize(new_end - V.begin());

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));

// The output is "3 4 5 9".

Ví dụ 2:

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespace std;

bool IsOdd(int x){

return x%2;

}

int main()

{

int a[] = {3,1,4, 8, 5, 2, 9};

int n = sizeof(a)/sizeof(*a);

vector<int> vec(a, a+n);

vector<int>::iterator new_end =

remove_if( vec.begin(), vec.end(), IsOdd );

vec.erase(new_end, vec.end());

copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));

// The output is "4 8 2".

return 0;

}

Các hàm có hậu tố _copy như remove_copy, remove_if_copy, replace_copy, replace_if_copy, reverse_copy sử dụng tương tự nhưng tạo ra và thao tác trên bản sao container

Sắp xếp container (ở đây là vector)

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespace std;

void printint(constint&i)

{

cout << i << endl;

}

int main()

{

int A[] = {3,2,3,1,2,3,5,3};

int n = sizeof(A)/sizeof(*A);

vector<int> V(A, A+n);

cout << endl <<"Danh sach ban dau"<< endl;

for_each( V.begin(), V.end(), printint );

V.sort();

vector<int>::iterator vi;

cout << endl <<"Danh sach sau khi sap xep"<< endl;

for_each( V.begin(), V.end(), printint );

getchar();

}

Trong ví dụ trên ta học được cách sử dụng hàm for_each() và sort() để thao tác với 1 container.

Tìm kiếm tuyến tính

// lineal search

#include<iostream.h>

#include<algorithm>

#include<vector>

usingnamespace std;

bool IsOdd(int x)

{

return x%2;

}

int main()

{

int a[] = {2,4,2,6,9,1,2,3,2,3,4,5,6,4,3,2,1};

int n = sizeof(a)/sizeof(*a);

vector<int> v(a, a+n);

int first = find(a, a+n, 1) - a;

//các hàm thuật toán hoàn toàn có thể thao tác trên mảng & con trỏ thường

cout <<"[array] so thu tu cua phan tu dau tien = 1: "<< first << endl;

first = find(v.begin(),v.end(), 1) - v.begin();

cout <<"[vector] so thu tu cua phan tu dau tien = 1: "<< first << endl;

//find_if

vector<int>::iterator it;

it = find_if(v.begin(),v.end(), IsOdd );

first = it - v.begin();

cout <<"Phan tu le dau tien la "<< *it <<" o vi tri thu "<< first << endl;

return 0;

}

Ngoài ra còn có nhiều hàm tìm kiếm khác: hàm search() dùng để so khớp 1 chuối liên tiếp các phần tử cho trước, hàm search_n tìm kiếm với số lần lặp xác định, hàm find_end tìm kết quả cuối cùng, find_first_not_of(), find_last_not_of() …

Đếm & tìm min max

//counting

#include<iostream>

#include<vector>

#include<algorithm>

usingnamespace std;

bool IsOdd(int x)

{

return x%2;

}

int main()

{

int a[] = {3,2,3,1,2,4,5,3};

int n = sizeof(a)/sizeof(*a);

vector<int> v(a, a+n);

cout <<"So luong so 3 trong mang: "<< count(v.begin(),v.end(), 3) << endl;

cout <<"So luong so le trong mang: "<< count_if(v.begin(),v.end(), IsOdd) << endl;

cout <<"So nho nhat trong mang: "<< *min_element(v.begin(),v.end()) << endl;

cout <<"So lon nhat trong mang: "<< *max_element(v.begin(),v.end()) << endl;;

return 0;

}

Hàm chuyển đổi hàng lo ạt transform()

Một trong những giải thuật thú vị hơn là transform(), phần tử được sửa đổi từng cái trong một phạm vi theo một chức năng mà bạn cung cấp.

#include<vector>

#include<algorithm>

usingnamespace std;

template<class T>

T inc(T x )

//hàm dùng để chuyển đổi

{

return x+1;

}

int main()

{

int a[] = {3,2,3,1,2,3,5,3};

int n = sizeof(a)/sizeof(*a);

vector<int> v(a, a+n);

transform(v.begin(), v.end(), v.begin(), inc<int> );

copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

// The output is "4 3 4 2 3 4 6 4".

return 0;

}

Ngoài ra còn nhiều hàm thuật toán khác có thể tham khảo trong tài liệu reference của c++