Một ví dụ về link list trong c++

Chào các bạn hôm nay mình có một ví dụ về link list theo mình thấy khá hay :)

Ta có một structure sau :

struct NODE{
int _data;
NODE* _next;
};


và đoạn code :

        NODE* head = new NODE;
NODE* tail = head;

head = NULL;

NODE* newNode = new NODE;
newNode->_data = 3;
newNode->_next = head;
head = newNode;

tail = head;

newNode->_data = 4;
newNode->_next = tail->_next;

tail->_next = newNode;


và khi debug trên visual C++ thì ra một kết quả khá hay : trong list do head quản ly có vô số các NODE khác nhau và đều có data = 4 và con trỏ _next thì có giá trị chính bằng địa chỉ trong head tức và nó trỏ vào đầu list.




Chúng ta cùng phân tích :

Ta có các bức ảnh miêu tả các bước thực hiện :


Bước 1
        NODE* head = new NODE;
NODE* tail = head;
   
Biến head được khai báo và cho ô nhớ bên stack, sau đó được cấp phát bên heap, tail tương tự.

Bước 2
        head = NULL;


NODE* newNode = new NODE;
newNode->_data = 3;
newNode->_next = head;

Bước 3
       head = newNode;


tail = head;

newNode->_data = 4;
newNode->_next = tail->_next;
        tail->_next = newNode;

Bây giớ ta đã thấy bản chất của vấn đề : 3 con trỏ head, tail, newNode đều trỏ hay quản lý cùng một vùng nhớ, cái mà ban đầu được cấp phát cho newNode. Và sau đó qua một vài bước next ponter chưa luôn địa chỉ của vùng nhớ đó hay nói cách khác nó trỏ luôn vào vùng nhớ đang chứa chính nó. Điều này như là đệ quy, đây là lý do tại sao trong 3 con trỏ head, tail, newNode quản lý vúng nhớ gồm vô số các phần tử giống nhau và fied next pointer của nó lại là địa chỉ của vùng nhớ mà 3 con trỏ này quản lý.

Hi vọng bug trên giúp ích cho các bạn. Cảm ơn các bạn :)

Cách hoạt động của bitwise ~ trong C++

bitwise "~" là phép toán thao tác trực tiếp trên các bit. Cụ thể : ~0 == 1 và ~1 == 0
Nhưng trong một số trường hợp khi in ra phép toán ~ ra  màn hình lại cho kết quả âm : cout << ~1; // -2.
Lý do là : mỗi số được biểu diễn qua hệ nhị phân thông qua 8 bit (tức là 1 byte)

1 : 0000 0001
khi thao tác phép toán ~ trên 1 ta được như sau :
1   :  0000 0001
~1 :  1111 1110 = 254

Và các trình dịch thường trừ nó đi 256. Tức là ~1 = 254 - 256 = -2.

Cảm ơn các bạn đã xem :) .

Hàm và sự thay đổi của con trỏ

Chào các bạn, như đã biết để thay đổi giá trị của một biến qua hàm thì ta có cách truyền vào địa chỉ của nó , nhưng bên cạnh đó có thể có một số hiểu nhầm .Hôm nay mình trình bày sự kết hợp giữa hàm và con trỏ :

ví dụ ta có code :

void test(int *p){
int a = 9;
p = &a;
}

int main(){
int a = 5;
int *p = &a;

cout << p << " " << *p << endl; // 0x0002 5
test(p);
cout << p << " " << *p << endl;// 0x0002 5

       // dễ thấy giá trị của biến p không bị thay đổi

return 0;
}

Ta thấy khi gọi hàm test(int *p) chương trình tạo ra một biến kiểu int* copy nông (shadow copy) giá trị của biến p. Trong thân hàm test các thao tác được thực hiện trên ban sao của p, nên khi ta gán p cho một địa chỉ khác thực chất là gán bản sao của p, p không thay đổi. Chính vì thế nên giá trị của p không bị thay đổi.

Qua đây ta cũng có thể hiểu kĩ hơn bản chất của việc thay đổi giá trị của một biến bằng cách truyền vào đia chỉ của nó.

Trên đây mình ví dụ một ví dụ cơ bản về việc hiểu nhầm chút ít trong việc kết hợp hàm và con trỏ. Có vài trường hợp khác như sau (trong linked list) :

1. void WrongPush(struct node* head, int data) {
2.      struct node* newNode = malloc(sizeof(struct node));
3.      newNode->data = data;
4.      newNode->next = head;
5.      head = newNode;
6. }

   (Nguồn : congdongcviet.com)
cái này sai ở : head = newNode;
vì giá trị của con trỏ head không bị thay đổi.

Cách khắc phục :
dùng con trỏ đa cấp :)

1. /*
2. Takes a list and a data value.
3. Creates a new link with the given data and pushes
4. it onto the front of the list.
5. The list is not passed in by its head pointer.
6. Instead the list is passed in as a "reference" pointer
7. to the head pointer -- this allows us
8. to modify the caller's memory.
9. */
10. void Push(struct node** headRef, int data) {
11.      struct node* newNode = malloc(sizeof(struct node));
12.      newNode->data = data;
13.      newNode->next = *headRef; // The '*' to dereferences back to the real head
14.      *headRef = newNode;          
15. }

Cảm ơn các bạn đã xem :) . 

Bản chất của kiểu string , arr trong bộ nhớ

 Đây là bài viết nói về bản chất của việc ta dùng string và arr trong vùng nhớ :
 khi ta gọi hàm getline, getstring( ) ... cho biến string s đã khai báo từ trước, bản chất của nó là tạo một vùng nhớ lưu các giá trị của những kí tự mình nhập vào (liên tiếp nhau) sau đó lấy địa chỉ đầu tiên của vùng nhớ đó (kí tự đầu tiên) đưa cho s, hay nói cách khác s là một con trỏ mà nó có giá trị là địa chỉ của kí tự đầu tiên trong vùng nhớ.

Như vậy thật không ổn khi so sánh 2 xâu bằng cách : s1 == s2 ;
 Chỉ là so sánh 2 địa chỉ đâu tiên trong một vùng nhớ nào đó.

Sự khác nhau giữa typedef và #define

- Như chúng ta đã biết define là một macro , trong code nó sẽ tìm đến những chỗ có text định nghĩa và thay thế .
VD : khi khai báo #define nguyen int

trong code(chưa compile) tất cả những chỗ nào có nguyen nó sẽ thay thế hết là int. Điều này dẫn đến một lỗi : Nếu như ta khai báo một biến nguyen trong hàm cục bộ thì nó cũng thay hết nguyen bằng int (ảnh)

Còn một lỗi nữa là :

#define intpnt int*

intpnt a, b;

// câu lệnh intpnt a, b được hiểu là :

// int* a; int b;

Và người ta thường dùng typedef để định nghĩa một type mới như một cách rõ ràng hơn

Introduction size_t

First, we have definition of size_t from cplusplus.com :

Unsigned integral type

Alias of one of the fundamental unsigned integer types.

It is a type able to represent the size of any object in bytes: size_t is the type returned by the sizeof operator and is widely used in the standard library to represent sizes and counts.

source

What the different between size_t and int ?

Then , we have link of stackoverflow :

The stdlib.h and stddef.h header files define a datatype called size_t which is used to represent the size of an object. Library functions that take sizes expect them to be of type size_t, and the sizeof operator evaluates to size_t.

The actual type of size_t is platform-dependent; a common mistake is to assume size_t is the same as unsigned int, which can lead to programming errors, particularly as 64-bit architectures become more prevalent.
Full

Last , I have a question : "Why size_t matter ?" and :) solve the problem :

Using size_t appropriately can improve the portability, efficiency, or readability of your code. Maybe even all three.

Numerous functions in the Standard C library accept arguments or return values that represent object sizes in bytes. For example, the lone argument in malloc(n) specifies the size of the object to be allocated, and the last argument in memcpy(s1, s2, n)specifies the size of the object to be copied. The return value of strlen(s) yields the length of (the number of characters in) null-terminated character array s excluding the null character, which isn't exactly the size of s, but it's in the ballpark.

You might reasonably expect these parameters and return types that represent sizes to be declared with type int (possibly long and/or unsigned), but they aren't. Rather, the C standard declares them as type size_t. According to the standard, the declaration for malloc should appear in <stdlib.h> as something equivalent to:

void *malloc(size_t n);

and the declarations for memcpy and strlen should appear in <string.h> looking much like:

void *memcpy(void *s1, void const *s2, size_t n);
size_t strlen(char const *s);

The type size_t also appears throughout the C++ standard library. In addition, the C++ library uses a related symbol size_type, possibly even more than it uses size_t.

In my experience, most C and C++ programmers are aware that the standard libraries use size_t, but they really don't know what size_t represents or why the libraries usesize_t as they do. Moreover, they don't know if and when they should use size_tthemselves.

In this column, I'll explain what size_t is, why it exists, and how you should use it in your code.

A portability problem
Classic C (the early dialect of C described by Brian Kernighan and Dennis Ritchie in The C Programming Language, Prentice-Hall, 1978) didn't provide size_t. The C standards committee introduced size_t to eliminate a portability problem, illustrated by the following example.

Let's examine the problem of writing a portable declaration for the standard memcpyfunction. We'll look at a few different declarations and see how well they work when compiled for different architectures with different-sized address spaces and data paths.

Recall that calling memcpy(s1, s2, n) copies the first n bytes from the object pointed to by s2 to the object pointed to by s1, and returns s1. The function can copy objects of any type, so the pointer parameters and return type should be declared as "pointer to void." Moreover, memcpy doesn't modify the source object, so the second parameter should really be "pointer to const void." None of this poses a problem.

The real concern is how to declare the function's third parameter, which represents the size of the source object. I suspect many programmers would choose plain int, as in:

void *memcpy(void *s1, void const *s2, int n);

which works fine most of the time, but it's not as general as it could be. Plain int is signed--it can represent negative values. However, sizes are never negative. Usingunsigned int instead of int as the type of the third parameter lets memcpy copy larger objects, at no additional cost.

On most machines, the largest unsigned int value is roughly twice the largest positiveint value. For example, on a 16-bit twos-complement machine, the largest unsigned int value is 65,535 and the largest positive int value is 32,767. Using an unsigned int as memcpy's third parameter lets you copy objects roughly twice as big as when using int.

Although the size of an int varies among C implementations, on any given implementation int objects are always the same size as unsigned int objects. Thus, passing an unsigned int argument is always the same cost as passing an int.

Using unsigned int as the parameter type, as in:

void *memcpy(void *s1, void const *s2, unsigned int n);

works just dandy on any platform in which an sunsigned int can represent the size of the largest data object. This is generally the case on any platform in which integers and pointers have the same size, such as IP16, in which both integers and pointers occupy 16 bits, or IP32, in which both occupy 32 bits. (See the sidebar on C data model notation.)



Thank you .

Game caro đơn gian viết bằng C++

Chào các bạn, C++ là một ngôn ngữ lập trình rất phổ biến và mạnh. Hôm nay mình post game caro viết bằng C++ trên console :) .

Đây là code :)
#include<iostream>

#include<windows.h>

#include<conio.h>

using namespace std;

#define UP   119  // w

#define DOW  115  // s

#define LE   97   // a

#define RI   100  // d

#define OK   13   // enter

int a[100][100];

int luot = 0;

int x = 12;

int y = 6;

int p1 = 0;

int p2 = 0; // p1,p2 la ti so cua 2 player

int thaydoiluot = 0;

struct ToaDo{

int x;

int y;

};

ToaDo mang[4];

void txtColor(int color);

void gotoxy(int x,int y);

void khung();

void play();

int thang();

void tiso();

void khungtiso();

void huongdan();

int main(){

SetConsoleTitle("Game : Ca-ro . Developer : Nguyen Dinh Tuan");

khung();

khungtiso();

gotoxy(x,y);

play();

getch();

return 0;

}

void txtColor(int color)

{

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);

}

void gotoxy(int x, int y)

{

COORD coord;

coord.X = x;

coord.Y = y;

SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);

}

void start(){

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

for(int j=0 ;j<100 ;j++){

a[i][j] = 0;

}

}

}

void khung(){

int d=1;

txtColor(6);

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

gotoxy(10+i,3);

cout << char(220);

gotoxy(10+i,20);

cout << char(223);

}

for(int i=4 ;i<=19 ;i++){

gotoxy(10,i);

cout << char(219);

gotoxy(49,i);

cout << char(219);

}

int k=1;

for(int i=11; i<=48 ;i++){

for(int j=4 ;j<=19 ;j++){

if(i%2==0){

if(j%2==0){

gotoxy(i,j);

txtColor(0);

cout << char(219);

}

else{

gotoxy(i,j);

txtColor(7);

cout << char(219);

}

}

else{

if(j%2==0){

gotoxy(i,j);

txtColor(7);

cout << char(219);

}

else{

gotoxy(i,j);

txtColor(0);

cout << char(219);

}

}

}

}

txtColor(14);

gotoxy(10,21);

cout << "Developer : Nguyen Dinh Tuan . ";

gotoxy(10,22);

cout << "Mail      : theiron1997@gmail.com";

huongdan();

}

void play(){

tiso();

gotoxy(x,y);

//int (*fthang)() = thang;

if(thang()){

gotoxy(10,1);

cout << "                                                              ";

gotoxy(10,1);

cout << "Nguoi choi " << thang() << " da thang.";

if(thang()==1) p1++; else p2++;

for(int k = 0;k<4 ;k++){

gotoxy(mang[k].x,mang[k].y);

txtColor(13);

if(thang()==1){

cout << "o";

}

else{

cout << "x";

}

}

getch();

gotoxy(10,1);

cout << "                                                  ";

gotoxy(10,1);

cout << "Co muon tiep tuc danh (c/k)";

char ch = getch();

if((ch=='c')||(ch=='C')){

gotoxy(10,1);

thaydoiluot++;

   if(thaydoiluot%2==0) luot = 0;

   else luot = 1;

   cout << "                                  ";

start();

khung();

khungtiso();

gotoxy(x,y);

play();

}

else{

exit(0);

}

}

char ch = getch();

// Nen su dung switch();

if(ch==104){

txtColor(10);

if(luot%2==0){ // nguoi 2 cau hoa

gotoxy(15,1);

cout << "Nguoi choi 2 co dong y khong ? c/k";

char CHAR = getch();

if((CHAR=='c')||(CHAR=='C')){

gotoxy(10,1);

   thaydoiluot++;

   if(thaydoiluot%2==0) luot = 0;

   else luot = 1;

       cout << "                                                 ";

   start();

   khung();

   khungtiso();

   gotoxy(x,y);

   play();

}

else{

gotoxy(15,1);

cout << "                                              ";

gotoxy(15,1);

cout << "Nguoi choi 2 khong dong y ";

gotoxy(15,1);

getch();

cout << "                                        ";

//gotoxy(15,1);

//system("pause");

cout << "                                                                     ";

   }

}

else{

gotoxy(15,1);

cout << "Nguoi choi 1 co dong y khong ? c/k";

char CHAR = getch();

if((CHAR=='c')||(CHAR=='C')){

gotoxy(10,1);

   thaydoiluot++;

   if(thaydoiluot%2==0) luot = 0;

   else luot = 1;

       cout << "                                                  ";

   start();

   khung();

   khungtiso();

   gotoxy(x,y);

   play();

}

else{

gotoxy(15,1);

cout << "                                              ";

gotoxy(15,1);

cout << "Nguoi choi 1 khong dong y . ";

getch();

gotoxy(15,1);

cout << "                                        ";

gotoxy(15,1);

//system("pause");

//getch();

//gotoxy(15,1);

cout << "                                                                     ";

   }

       }

    }

if(ch==116){

if(luot%2==0){

gotoxy(15,1);

txtColor(10);

cout << "Nguoi choi 1 da thua ";

getch();

p2++;

gotoxy(10,1);

//luot = 0; // <- nen nang cap cho nay

thaydoiluot++;

   if(thaydoiluot%2==0) luot = 0;

   else luot = 1;

   cout << "                                  ";

start();

khung();

khungtiso();

gotoxy(x,y);

play();

}

else{

gotoxy(15,1);

txtColor(10);

cout << "Nguoi choi 2 da thua ";

getch();

p1++;

gotoxy(10,1);

//luot = 0; // <- nen nang cap cho nay

thaydoiluot++;

   if(thaydoiluot%2==0) luot = 0;

   else luot = 1;

   cout << "                                  ";

start();

khung();

khungtiso();

gotoxy(x,y);

play();

}

}

if(ch==UP){

if(y<=4){

y = 19;

gotoxy(x,y);

play();

}

else{

y--;

gotoxy(x,y);

play();

}

}

if(ch==27){

gotoxy(15,0);

cout << "Ban co muon thoat c/k";

char C = getch();

if((C=='c')||(C=='C')){

exit(0);

}

else{

gotoxy(15,0);

   cout << "                                ";

}

}

if(ch==DOW){

if(y>=19){

y = 4;

gotoxy(x,y);

play();

}

else{

y++;

gotoxy(x,y);

play();

}

}

if(ch==RI){

if(x>=48){

x = 11;

gotoxy(x,y);

play();

}

else{

x++;

gotoxy(x,y);

play();

}

}

if(ch==LE){

if(x<=11){

x = 48;

gotoxy(x,y);

play();

}

else{

x--;

gotoxy(x,y);

play();

}

}

if(ch==OK){

// Neu ma da co gia tri

if(a[x][y]!=0){

gotoxy(15,1);

txtColor(10);

cout << "O nay khong trong. Ban hay chon o khac ...";

getch();

gotoxy(15,1);

cout << "                                            ";

gotoxy(x,y);

play();

}

// luc nay da chon o khong co gia tri

luot++;

if(luot%2==0){  // luot nguoi 2

    a[x][y] = 2;

    gotoxy(x,y);

    txtColor(10);

    cout << "x";

    gotoxy(15,1);

    txtColor(11);

    cout << "Den luot nguoi 1 - " ;

    txtColor(12);

    cout << "o";

    play();

}

else{ // luot nguoi 1

a[x][y] = 1 ;

gotoxy(x,y);

txtColor(12);

cout << "o";

gotoxy(15,1);

txtColor(11);

   cout << "Den luot nguoi 2 - " ;

   txtColor(10);

   cout << "x";

play();

}

}

play(); // luc an phim khac

}

int thang(){

int Thang = 1; // thang . 0 la chua thang

for(int i=1 ;i<=50 ;i++){

for(int j=1 ;j<=50 ;j++){

if((a[i][j]==a[i+1][j])&&(a[i][j]==a[i+2][j])&&(a[i][j]==a[i+3][j])/*&&(a[i+4][j]==a[i][j])*/&&(a[i][j]!=0)){

Thang = 1;

for(int h=0;h<=50 ;h++){

if(i-h <= 1){

break;

}

else{

if ((a[i - h][j] != a[i][j]) && (a[i - h][j] != 0)){

Thang = 0;

break;

}

}

}

for(int h=0;h<=50 ;h++){

if(i+h >= 50){

break;

}

else{

if ((a[i + h + 3][j] != a[i][j]) && (a[i + h + 3][j] != 0)){

Thang = 0;

break;

}

}

}

if(Thang==1){

for(int k=0 ;k<4 ;k++){

mang[k].y = j;

mang[k].x = i+k; 

}

return a[i][j];

} 

}

if((a[i][j]==a[i][j+1])&&(a[i][j]==a[i][j+2])&&(a[i][j]==a[i][j+3])/*&&(a[i][j]==a[i][j+4])*/&&(a[i][j]!=0)){

Thang = 1;

for(int h=0 ;h<=50 ;h++){

if(j+h>=50){

break;

}

else{

if((a[i][j+3+h]!=0)&&(a[i][j+3+h]!=a[i][j])) Thang = 0;

}

}

for(int h=0 ;h<=50 ;h++){

if(j-h<=1){

break;

}

else{

if((a[i][j-h]!=0)&&(a[i][j-h]!=a[i][j])) Thang = 0;

}

}

if(Thang==1){

for(int k=0 ;k<4 ;k++){

mang[k].x = i;

mang[k].y = j+k; 

}

return a[i][j];

} 

}

if((a[i][j]==a[i+1][j+1])&&(a[i][j]==a[i+2][j+2])&&(a[i][j]==a[i+3][j+3])/*&&(a[i][j]==a[i+4][j+4])*/&&(a[i][j]!=0)){

Thang = 1;

for(int h=0; h<=50 ;h++){

if((i+h>=50)||(j+h)>=30) break;

else{

if((a[i+h+3][j+h+3]!=a[i][j])&&(a[i+h+3][j+h+3]!=0)) Thang = 0;

}

}

for(int h=0; h<=50 ;h++){

if((i-h<=1)||(j-h)<=1) break;

else{

if((a[i-h][j-h]!=a[i][j])&&(a[i-h][j-h]!=0)) Thang = 0;

}

}

if(Thang==1){

for(int k=0 ;k<4 ;k++){

mang[k].x = i+k;

mang[k].y = j+k; 

}

return a[i][j];

} 

} 

if((a[i][j]==a[i-1][j+1])&&(a[i][j]==a[i-2][j+2])&&(a[i][j]==a[i-3][j+3])/*&&(a[i][j]==a[i-4][j-4])*/&&(a[i][j]!=0)){

Thang = 1;

for(int h=1; h<=50 ;h++){

if((i+h>=50)||(j-h)<=1) break;

else{

if((a[i+h][j-h]!=a[i][j])&&(a[i+h][j-h]!=0)) Thang = 0;

}

}

for(int h=0; h<=50 ;h++){

if((i-h<=1)||(j+h)>=50) break;

else{

if((a[i-4-h][j+h+4]!=a[i][j])&&(a[i-h-4][j+h+4]!=0)) Thang = 0;

}

}

if(Thang==1){

for(int k=0 ;k<4 ;k++){

mang[k].x = i-k;

mang[k].y = j+k; 

}

return a[i][j];

} 

} ;

}

}

return 0;

}

void khungtiso(){

gotoxy(52,3);

txtColor(10);

cout << char(220) << char(220) << char(220) << char(220) << char(220) << char(220) << char(220) << char(220) ;

txtColor(13); 

cout << " Ti so ";

txtColor(10);

cout  << char(220)  << char(220) << char(220) << char(220) << char(220) << char(220) << char(220);

gotoxy(54,4);

txtColor(14);

cout << "player1    player2";

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

gotoxy(52+i,4+18);

txtColor(10);

cout << char(223);

}

for(int i=4 ; i<= 21 ;i++){

gotoxy(52,i);

cout << char(219);

gotoxy(52+16+5,i);

cout << char(219);

gotoxy(52+8+2,i);

cout << char(219);

} 

tiso();

}

void tiso(){

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

gotoxy(52+2,6+i);

txtColor(12);

cout << "o";

}

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

gotoxy(52+13,6+i);

txtColor(11);

cout << "x";

}

}

void huongdan(){

txtColor(10);

gotoxy(1,0);

txtColor(9);

cout << "Esc - Thoat";

txtColor(10);

gotoxy(1,3);

cout << "a : " << char(283);

gotoxy(1,4);

cout << "d : " << char(282);

gotoxy(1,5);

cout << "w : " << char(280);

gotoxy(1,6);

cout << "s : " << char(281);

gotoxy(1,8);

txtColor(13);

cout << "t : xin ";

gotoxy(1,9);

txtColor(13);

cout << "    thua";

gotoxy(1,10);

txtColor(10);

txtColor(13);

cout << "h : cau ";

gotoxy(1,11);

cout << "    hoa";

}