Nội dung

c cơ bản

Mô tả kiểu dữ liệu

loại dữ liệu	Nền tảng 16 bit	Nền tảng 32-bit	Nền tảng 64-bit
char	1 byte	1 byte	1 byte
pointer	2 byte	4 byte	8 byte
short	2 byte	2 byte	2 byte
int	2 byte	4 byte	4 byte
float	4 byte	4 byte	4 byte
double	8 byte	8 byte	8 byte
long	4 byte	4 byte	8 byte
long long	8 byte	8 byte	8 byte

volatile

Volatile chỉ ra rằng biến có thể thay đổi bất cứ lúc nào và nó phải được đọc từ địa chỉ của biến mỗi khi nó được sử dụng. Do đó, mã hợp ngữ (ASM) do trình biên dịch tạo ra sẽ đọc lại dữ liệu từ địa chỉ của biến.

Thanh ghi phần cứng của các thiết bị song song,
Các biến không tự động (Biến không tự động) có thể được truy cập trong chương trình con dịch vụ ngắt có thể sử dụng bảo vệ vùng quan trọng
Các biến được chia sẻ bởi một số tác vụ trong các ứng dụng đa luồng có thể tắt lập lịch hệ thống

con trỏ – pointer

Con trỏ hàm – Function pointer

int (* vui) ( int * a);

Mảng con trỏ hàm – Function pointer array

int (* fun [ 10 ]) ( int * data, int size);

Hướng dẫn:

int (* sort_fun [ 5 ]) ( int * data, int size) = {
    quick_sort,      / * Quick sort * / 
    insert_sort,     / * Insert sort * / 
    bubble_sort,     / * Bubble sort * / 
    heap_sort,       / * Heap sort * / 
    selection_sort   / * selection sort * /
};
// or
sort_fun [ 0 ] = quick_sort;
sort_fun [ 1 ] = insert_sort;

Mảng con trỏ

int * a [ 10 ];

Con trỏ mảng

/ * a là biến con trỏ trỏ đến mảng một chiều có 10 phần tử. 
* () Mức độ ưu tiên cao, cho biết a là con trỏ và trỏ đến mảng một chiều số nguyên. 
* Khi a + 1, a phải vượt qua 10 Độ dài của một dữ liệu số nguyên * /
 int (* a) [ 10 ];

Con trỏ con trỏ

int ** a;

Giá trị trả về của hàm chính

0 nghĩa là chương trình thoát bình thường
Số âm có nghĩa là chương trình đã thoát bất thường

hằng số -const

const T

Để định nghĩa một hằng, nó phải được khởi tạo trong khi khai báo nó. Sau khi khai báo, giá trị này không thể thay đổi.

const  int constInt = 10 ;         // đúng 
constInt = 20 ;                   // lỗi, không thể thay đổi giá trị hằng 
const  int constInt3;             // lỗi, không được khởi tạo

const T *

Một con trỏ đến một hằng số không thể được sử dụng để thay đổi giá trị của đối tượng mà nó trỏ đến.

const  int i = 5 ;
const  int i2 = 10 ;
const  int * pInt = & i;            // đúng, trỏ đến một đối tượng const int, nghĩa là, địa chỉ của i 
// * pInt = 10;                  // sai, không thể thay đổi những gì nó tham chiếu Đối tượng 
pInt = &i2; //đúng, bạn có thể thay đổi giá trị của chính con trỏ pInt, lúc này pInt trỏ đến địa chỉ của i2 
const  int * p2 = new int ( 8 );      // đúng, trỏ đến địa chỉ của một đối tượng mới 
delete p2;                       // đúng 
// int * pInt = & i; // sai, i là kiểu const int, kiểu không khớp, bạn không thể khởi tạo const int * thành int * 
int nValue =15 ;
 const  int * pConstInt = & nValue;     // Đúng, bạn có thể gán int * cho const int *, nhưng pConstInt không thể thay đổi giá trị của đối tượng mà nó trỏ đến, tức là 
nValue * pConstInt = 40 ;                     // lỗi, bạn không thể thay đổi những gì nó trỏ đến giá trị Đối tượng

Sự khác biệt giữa const int * và int * const

Bản thân con trỏ là một loại đối tượng. Định nghĩa con trỏ như một hằng số là một con trỏ hằng, là kiểu int * const. Nó cũng có thể được viết dưới dạng int * const, phải được khởi tạo khi khai báo.

int nValue = 10 ;
 int * const p = & nValue;
 int * const p2 = & nValue;
 // Đối tượng được trỏ tới bởi con trỏ const int * không thể thay đổi, nhưng giá trị của chính con trỏ có thể thay đổi; giá trị của int * Bản thân con trỏ const không thể thay đổi, nhưng đối tượng mà nó trỏ tới có thể được thay đổi. 
int nValue1 = 10 ;
 int nValue2 = 20 ;
 int * const constPoint = & nValue1;
 // constPoint = & nValue2; // sai, bạn không thể thay đổi giá trị của chính 
constPoint * constPoint = 40 ;                    // đúng, bạn có thể thay đổi đối tượng được trỏ tới bởi constPoint, Tại thời điểm này nValue1 = 40


const  int nConstValue1 = 5 ;
 const  int nConstValue2 = 15 ;
 const  int * pPoint = & nConstValue1;
 // * pPoint = 55; // Sai, bạn không thể thay đổi giá trị của đối tượng được trỏ tới bởi 
pPoint pPoint = & nConstValue2;              // Đúng, bạn có thể thay đổi con trỏ pPoint Giá trị của chính nó, tại thời điểm này pPoint được liên kết với đối tượng nConstValue2, nghĩa là, pPoint là địa chỉ của nConstValue2

const int * const là một con trỏ hằng đến một đối tượng hằng, nghĩa là bạn không thể thay đổi giá trị của chính con trỏ, cũng như không thể thay đổi đối tượng được con trỏ trỏ tới.

const  int nConstValue1 = 5 ;
 const  int nConstValue2 = 15 ;
 const  int * const pPoint = & nConstValue1;
 // * pPoint = 55; // lỗi, không thể thay đổi giá trị của đối tượng được trỏ tới bởi 
pPoint // pPoint = & nConstValue2; // lỗi, không Thay đổi giá trị của chính pPoint

const mnemonic method

Đọc một statement từ phải sang trái. (* Phát âm là con trỏ tới)

char * const cp;   // cp là con trỏ const tới char 
const  char * p;    // p là con trỏ tới const char; 
char  const * p;    // Tương tự như trên, vì không có toán tử const * trong C ++, vì vậy const Chỉ có thể thuộc về kiểu trước đó.

Tiêu chuẩn C ++ quy định rằng từ khóa const là tương đương trước kiểu hoặc tên biến.

Tóm lại là:

char * const cp      // xác định hằng số con trỏ cho một ký tự, nghĩa là const con trỏ 
const  char * p        // định nghĩa một con trỏ tới một hằng ký tự 
char  const * p        // tương đương với const char * p 
const  char **        // là một con trỏ tới một con trỏ, con trỏ này lần lượt trỏ đến một hằng số chuỗi.   
char **              // Nó cũng là một con trỏ tới một con trỏ, đến lượt nó trỏ đến một biến chuỗi.

Phương pháp lưu trữ dấu chấm động

float chiếm 4 byte, 32bits

Ký bit	Số mũ	Phần Mantissa
1 bit	8 bit	23 bit

kép chiếm 8 byte, 64 bit

Ký bit	Số mũ	Phần Mantissa
1 bit	11 bit	52 bit

c title

giá trị trả về printf

# include  < stdio.h >
 int  main () {
   int i = 43 ;
   printf ( " % d \ n " , printf ( " % d " , printf ( " % d " , i)));
   return  0 ;
}

Đầu ra: 4321 Giá trị trả về của printf là số ký tự đầu ra (không bao gồm phần cuối của chuỗi \ x00)

kiểu liệt kê – enum enumeration type

#include <stdio.h>
int main() {
  enum color{
    RED,
    BLUE,
    GREEN = -2,
    YELLOW,
    PINK
  };
  printf("%d %d\n", BLUE, PINK);
  return 0;
}

Đầu ra: 1 0 enum bắt đầu từ 0 theo mặc định, do đó RED = 0, BLUE = 1, GREEN = -2, YELLOW = -1, PINK = 0;

Hàm đa dạng – Variadic function

#include "stdarg.h"

char buf[512] = {0};

int func(const char *fmt, ...)
{
  va_list args;
  va_start(args, fmt);
  vsprintf(buf, fmt, args);
  va_end(args);
}

Big and small endian

union data {
     int a;
     char b; 
}; 

struct def {
     union data mine; 
}; 

struct def endian; 

int main ( int argc, char **argv) 
{ 
     endian. mine . a = 0x12345678 ;
     printf ( " %02X \ n " , endian. mine . b );
     return 0 ; 
}
/ * In 78 có nghĩa là little endian, 12 có nghĩa là big endian * /

Danh sách liên kết – Linked list

////////////////////////////////////////////
// Khởi tạo danh sách liên kết đơn Tạo, chèn, tìm, xóa. // 
// Tác giả: Wang Yong // 
// Ngày: 2010.8.19
////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
////////////////////////////////////////////
// Xác định loại nút (Node)
typedef struct Node
{
    ElemType data;              // Trường dữ liệu
    struct Node *next;          // Trường con trỏ của danh sách được liên kết đơn
}Node,*LinkedList;
////////////////////////////////////////////
// Khởi tạo danh sách liên kết đơn 
LinkedList LinkedListInit()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));    // Áp dụng cho không gian nút
    if(L == NULL)  // Xác định xem có đủ không gian bộ nhớ hay không (có được cấp phát bộ nhớ hay không)
        printf("Failed to apply for memory space/n");
    L->next = NULL;//đặt next (pointer) là NULL, danh sách liên kết đơn được khởi tạo với độ dài là 0
}
////////////////////////////////////////////
// Thiết lập liên kết đơn danh sách 1. Tạo một danh sách được liên kết duy nhất
LinkedList LinkedListCreatH()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   // Áp dụng cho không gian nút đầu 
    L->next = NULL;                      // Khởi tạo danh sách liên kết trống
    
    ElemType x;                        // x là dữ liệu trong trường dữ liệu danh sách liên kết 
    while(scanf("%d",&x) != EOF)
    {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   // áp dụng cho một nút mới 
        p->data = x;                     // gán trường dữ liệu nút 
        p->next = L->next;                  // thay đổi nút Chèn vào tiêu đề L -> | 2 | -> | 1 | -> NULL 
        L->next = p; 
    }
    return L;
}
////////////////////////////////////////////
// Thiết lập liên kết đơn danh sách 2. Phương pháp nội suy đuôi tạo một danh sách liên kết đơn 
LinkedList LinkedListCreatT()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   // Áp dụng cho không gian nút đầu 
    L->next = NULL;                 // Khởi tạo danh sách liên kết trống
    Node *r;
    r = L;                          // r luôn trỏ đến nút đầu cuối, lúc đầu nó trỏ đến nút đầu 
    ElemType x;                       // x là dữ liệu trong trường dữ liệu danh sách liên kết 
    while(scanf("%d",&x) != EOF)
    {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   // áp dụng cho một nút mới 
        p->data = x;                     // gán trường dữ liệu nút 
        r->next = p;                 // chèn nút vào bảng Head L -> | 1 | -> | 2 | -> NULL
        r = p;
    }
    r->next = NULL;
    
    return L;
}
////////////////////////////////////////////
// Chèn liên kết đơn danh sách, Chèn phần tử của x vào vị trí thứ i của danh sách liên kết
LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)
{  
    Node *pre;                     // pre là nút tiền nhiệm
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++)
        pre = pre->next;                 // Tìm nút tiền nhiệm của vị trí thứ i 
    Node *p;                                // Nút được chèn là p 
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;

    return L;
}
////////////////////////////////////////////
// xóa một danh sách , Xóa phần tử 
LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
    Node *p,*pre;                  // pre là nút tiền nhiệm và p là nút được tìm kiếm. 
    p = L->next;
    while(p->data != x)              // Tìm phần tử có giá trị là x
    {
        pre = p;
        p = p->next;
    }
    pre->next = p->next; //Thao tác xóa và trỏ người tiền nhiệm của nó đến bên cạnh người kế nhiệm của nó. 
    free(p);
    return L;
}
/////////////////////////////////////////////
int main()
{
    LinkedList list,start;
/*  printf("Please enter the data of the singly linked list:");
    list = LinkedListCreatH();
    for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
    printf("/n");
*/  printf("Please enter the data of the singly linked list:");
    list = LinkedListCreatT();
    for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
    printf("/n");
    int i;
    ElemType x;
    printf("Please enter the location to insert the data:");
    scanf("%d",&i);
    printf("Please enter the value of the inserted data:");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
    printf("/n");
    printf("Please enter the value of the element to be deleted:");
    scanf("%d",&x);
    LinkedListDelete(list,x); 
    for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
    printf("/n");

    return 0;
}

Thuật toán sắp xếp – Sorting Algorithm

Các thuật toán sắp xếp là:

Chọn sắp xếp

Sắp xếp nhanh chóng

Loại đồi

Sắp xếp bong bóng

Sắp xếp chèn

Sắp xếp đống

Hợp nhất sắp xếp

So sánh thuật toán sắp xếp:

Chọn sắp xếp – Select sort

Sắp xếp có chọn lọc là một thuật toán sắp xếp đơn giản và trực quan. Bất kể dữ liệu nào được nhập vào, nó đều có độ phức tạp về thời gian là O (n²). Vì vậy, khi sử dụng nó, kích thước dữ liệu càng nhỏ càng tốt. Ưu điểm duy nhất có thể là nó không chiếm thêm dung lượng bộ nhớ.

thời gian phức tạp – time complexity

Average: O(n2) Best: O(n2) Worst: O(n2)

Không gian phức tạp – Space complexity

O(1)

Các bước thuật toán

Đầu tiên tìm phần tử nhỏ nhất (lớn) trong dãy chưa được sắp xếp và lưu trữ nó ở đầu dãy đã sắp xếp
Sau đó, tiếp tục tìm phần tử nhỏ nhất (lớn) từ các phần tử chưa được sắp xếp còn lại, rồi đưa nó vào cuối dãy đã sắp xếp.
Lặp lại bước thứ hai cho đến khi tất cả các phần tử được sắp xếp.

Demo hoạt ảnh

/ * Sắp xếp lựa chọn trực tiếp * /
void selection_sort(int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (x[j] < x[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            swap(x,i,min);
        }
    }
}

Sắp xếp chèn – Insertion sort

Mặc dù việc triển khai mã của sắp xếp chèn không đơn giản và thô sơ như sắp xếp bong bóng và sắp xếp lựa chọn, nhưng nguyên tắc của nó phải dễ hiểu nhất, bởi vì bất kỳ ai đã chơi poker đều có thể hiểu nó trong vài giây. Sắp xếp chèn là thuật toán sắp xếp đơn giản và trực quan nhất. Nguyên tắc hoạt động của nó là xây dựng một chuỗi có thứ tự. Đối với dữ liệu chưa được sắp xếp, hãy quét từ sau ra trước trong chuỗi đã sắp xếp để tìm vị trí tương ứng và chèn. Sắp xếp chèn, giống như sắp xếp bong bóng, cũng có một thuật toán tối ưu hóa được gọi là chèn phân nửa.

thời gian phức tạp

Average: O(n2) Best: O(n) Worst: O(n2)

Không gian phức tạp

O(1)

Các bước thuật toán

Phần tử đầu tiên của dãy đầu tiên được sắp xếp được coi là một dãy có thứ tự, và phần tử thứ hai đến phần tử cuối cùng được coi là một dãy không được sắp xếp.
Quét dãy chưa được sắp xếp từ đầu đến cuối, chèn từng phần tử đã quét vào vị trí thích hợp của dãy đã sắp xếp. (Nếu phần tử được chèn bằng một phần tử trong dãy có thứ tự, phần tử cần chèn sẽ được chèn sau phần tử bằng nhau.)

Demo hoạt ảnh

/ * Sắp xếp chèn trực tiếp * /
 void  inserttion_sort ( int n)
{
    for ( int i = 1 ; i <n; i ++)
    {
        int t = x [i];
         int j;
         for (j = i; j> 0 && x [j- 1 ]> t; j--)
        {
            x [j] = x [j- 1 ];
        }
        x [j] = t;
    }
}

Loại đồi – Hill sort

Sắp xếp theo đồi, còn được gọi là thuật toán sắp xếp tăng dần, là một phiên bản sắp xếp chèn hiệu quả và cải tiến hơn. Nhưng Hill sắp xếp là một thuật toán sắp xếp không ổn định. Sắp xếp theo kiểu Hill đề xuất một phương pháp cải tiến dựa trên hai thuộc tính sau của sắp xếp chèn:

Sắp xếp chèn có hiệu quả cao khi hoạt động trên dữ liệu gần như đã được sắp xếp, tức là nó có thể đạt được hiệu quả của sắp xếp tuyến tính;
Nhưng sắp xếp chèn thường không hiệu quả, vì sắp xếp chèn chỉ có thể di chuyển dữ liệu từng bit một; ý tưởng cơ bản của sắp xếp Hill là: trước tiên chia toàn bộ chuỗi bản ghi được sắp xếp thành nhiều chuỗi con để sắp xếp chèn trực tiếp. , Khi các bản ghi trong toàn bộ chuỗi được “sắp xếp về cơ bản”, thì toàn bộ các bản ghi sẽ được chèn trực tiếp và sắp xếp theo trình tự.

thời gian phức tạp

Average: O(n1.5) Best: O(n) Worst O(n2)

Không gian phức tạp

O(1)

Các bước thuật toán

Chọn một dãy số tăng dần t1, t2, …, tk, trong đó ti> tj, tk = 1;
Sắp xếp thứ tự k lần theo số thứ tự tăng dần k;
Trong mỗi lần sắp xếp, theo số gia tăng tương ứng, trình tự sắp xếp được chia thành nhiều dãy con có độ dài m, và mỗi bảng con được chèn và sắp xếp trực tiếp. Chỉ khi hệ số gia tăng là 1, toàn bộ dãy được coi là một bảng và độ dài của bảng là độ dài của toàn bộ dãy.

/ * Sắp xếp đồi * /
 void  shell_sort ( int n)
{
    for ( int inc = n / 3 ; inc> = 1 ; inc / = 3 )
    {
        for ( int i = inc; i <n; i ++)
        {
            int t = x [i];
             int j;
             for (j = i; j> = inc && x [j-inc]> t; j - = inc)
            {
                x [j] = x [j-inc];
            }
            x [j] = t;
        }
    }
}

Sắp xếp bong bóng – Bubble Sort

thời gian phức tạp

Average: O(n2) Best: O(n) Worst: O(n2)

Không gian phức tạp

O(1)

Các bước thuật toán

So sánh các phần tử liền kề. Nếu cái đầu tiên lớn hơn cái thứ hai, hãy hoán đổi hai cái đó.
Làm công việc tương tự cho từng cặp phần tử liền kề, từ cặp đầu tiên ở đầu đến cặp cuối cùng ở cuối. Sau khi thực hiện xong bước này, phần tử cuối cùng sẽ là số lớn nhất.
Lặp lại các bước trên cho tất cả các phần tử ngoại trừ phần tử cuối cùng.
Tiếp tục lặp lại các bước trên cho ngày càng ít phần tử hơn mỗi lần cho đến khi không còn cặp số nào để so sánh. Demo hoạt ảnh

/ * Sắp xếp bong bóng * /
void bubble_sort(int n)
{
    bool change = true;
    for (int i = n-1; i >= 1 && change; i--)
    {
        change = false;
        for (int j = 0; j < i; j++)
        {
            if(x[j] > x[j + 1])
            {
                swap(x, j, j + 1);
                change = true;
            }
        } 
    } 
}

Sắp xếp nhanh chóng – Quick sort

Sắp xếp nhanh là một thuật toán sắp xếp được phát triển bởi Tony Hall. Trung bình, cần Ο (nlogn) so sánh để sắp xếp n mục. Trong trường hợp xấu nhất, cần phải so sánh Ο (n2), nhưng trường hợp này không phổ biến. Trên thực tế, quicksort thường nhanh hơn đáng kể so với các thuật toán Ο (nlogn) khác, bởi vì vòng lặp bên trong của nó có thể được triển khai hiệu quả trên hầu hết các kiến trúc. Sắp xếp nhanh sử dụng chiến lược chia để phân chia danh sách thành hai danh sách con.

Sắp xếp nhanh là một ứng dụng điển hình của phép chia và phép chia trong các thuật toán sắp xếp. Về cơ bản, sắp xếp nhanh nên được coi là một phương pháp chia và trị đệ quy dựa trên sắp xếp bong bóng.

Tên của Quick Sort rất đơn giản và thô lỗ, bởi vì một khi bạn nghe thấy tên này, bạn sẽ biết ý nghĩa của nó, tức là nó nhanh và hiệu quả! Nó là một trong những thuật toán sắp xếp nhanh nhất để xử lý dữ liệu lớn. Mặc dù độ phức tạp thời gian của Trường hợp tồi tệ nhất đã đạt đến O (n²) nhưng nó rất tuyệt vời. Trong hầu hết các trường hợp, nó hoạt động tốt hơn thuật toán sắp xếp có độ phức tạp thời gian trung bình là O (n logn). Nhưng tại sao? Tôi cũng không biết. May mắn thay, tôi lại mắc phải một chứng rối loạn ám ảnh cưỡng chế khác. Tôi đã kiểm tra thêm thông tin và cuối cùng đã tìm ra câu trả lời thỏa đáng trong “Cuộc thi Tin học và Nghệ thuật Thuật toán”:

Ví dụ: trường hợp xấu nhất của quicksort là O (n²), sắp xếp nhanh của chuỗi tuần tự. Nhưng thời gian dự kiến khấu hao của nó là O (nlogn), và hệ số không đổi ẩn trong ký hiệu O (nlogn) là rất nhỏ, nhỏ hơn nhiều so với sắp xếp hợp nhất có độ phức tạp ổn định và bằng O (nlogn). Do đó, đối với hầu hết các số ngẫu nhiên có trình tự yếu hơn, sắp xếp nhanh luôn tốt hơn sắp xếp hợp nhất.

thời gian phức tạp

Average: O(nlogn) Best: O(nlogn) Worst: O(n2)

Không gian phức tạp

O(nlogn) for method stack

Các bước thuật toán

Chọn một phần tử từ chuỗi và gọi nó là “pivot”;
Sắp xếp lại trình tự, tất cả các phần tử nhỏ hơn giá trị điểm chuẩn được đặt ở phía trước điểm chuẩn và tất cả các phần tử lớn hơn giá trị điểm chuẩn được đặt phía sau điểm chuẩn (cùng một số có thể nằm ở hai bên). Sau khi phân vùng thoát ra, điểm chuẩn nằm ở giữa chuỗi. Đây được gọi là hoạt động phân vùng;
Sắp xếp đệ quy các dãy con của các phần tử nhỏ hơn giá trị tham chiếu và các dãy con của các phần tử lớn hơn giá trị tham chiếu; trường hợp cuối cùng của đệ quy là kích thước của dãy bằng 0 hoặc một, nghĩa là nó đã được sắp xếp mãi mãi. Mặc dù nó đã được đệ quy, nhưng thuật toán này sẽ luôn thoát ra, bởi vì trong mỗi lần lặp, nó sẽ đặt ít nhất một phần tử đến vị trí cuối cùng của nó.

Demo hoạt ảnh

/ * Sắp xếp nhanh * /
void quick_sort(int l, int u)
{
    if (l >= u)
        return;
    int m = l;
    for (int i = l+1; i<= u; i++)
    {
        if(x[i] < x[l])
            swap(x, ++m, i);
    }
    swap(x, l, m);
    quick_sort(l, m-1);
    quick_sort(m+1, u);
}

thuật toán băm – hash algorithm

phương pháp xây dựng băm

Phương pháp định địa chỉ trực tiếp: Lấy từ khóa hoặc giá trị hàm tuyến tính của từ khóa làm địa chỉ băm. Nghĩa là, H (key) = key hoặc H (key) = a? Key + b, trong đó a và b là hằng số (loại hàm băm này được gọi là hàm riêng của nó)
Phân tích số: Phân tích một tập hợp dữ liệu, chẳng hạn như ngày sinh của một nhóm nhân viên. Lúc này, chúng tôi thấy rằng một số chữ số đầu tiên của ngày sinh gần giống nhau. Trong trường hợp này, xác suất xung đột sẽ là rất cao, nhưng chúng tôi nhận thấy Một vài chữ số cuối cùng của năm, tháng và ngày cho biết số tháng và ngày cụ thể. Nếu các chữ số sau được sử dụng để tạo địa chỉ băm, xác suất xung đột sẽ giảm đáng kể. Do đó, phương pháp phân tích kỹ thuật số là tìm ra quy luật của các con số và sử dụng những dữ liệu này càng nhiều càng tốt để tạo ra một địa chỉ băm với xác suất xung đột thấp hơn.
Phương pháp bình phương giữa: Lấy các chữ số ở giữa sau khi từ khóa được bình phương làm địa chỉ băm.
Phương pháp gấp: chia từ khóa thành nhiều phần có cùng số bit, và phần cuối cùng của số bit có thể khác nhau, sau đó lấy chồng chất và (bỏ phần mang) của các phần này làm địa chỉ băm.
Phương pháp số ngẫu nhiên: Chọn một hàm ngẫu nhiên và lấy giá trị ngẫu nhiên của từ khóa làm địa chỉ băm. Phương pháp này thường được sử dụng trong các trường hợp độ dài của từ khóa khác nhau.
Phương pháp chia và để lại phần dư: lấy phần dư có được sau khi chia từ khóa cho một số p không lớn hơn độ dài m của bảng bảng băm làm địa chỉ băm. Tức là, H (key) = key MOD p, p <= m. Từ khóa không chỉ có thể được điều chỉnh trực tiếp mà còn sau các thao tác gấp và bình phương. Việc lựa chọn p là rất quan trọng, nói chung, các số nguyên tố hoặc m được sử dụng, nếu p không được chọn tốt, các từ đồng nghĩa có khả năng được tạo ra.

Xung đột băm và cách giải quyết

Lý do xung đột:

Liên quan đến hàm băm, giá trị của một hàm băm tốt phải được phân phối đồng đều nhất có thể.
Nó liên quan đến hàm băm xung đột giải quyết xung đột.
Và kích thước của hệ số tải trọng. Quá lớn không nhất thiết là tốt và việc lãng phí không gian là nghiêm trọng. Hệ số tải và hàm băm được liên kết với nhau.

Giải quyết xung đột

Phương pháp định địa chỉ mở: phương pháp thăm dò tuyến tính, phương pháp thăm dò vuông, phương pháp chuỗi giả ngẫu nhiên, phương pháp hàm băm kép.
Phương pháp Zipper: Kết nối tất cả các từ đồng nghĩa, nghĩa là, các bản ghi có cùng giá trị băm, với một danh sách được liên kết đơn lẻ.

Các hàm băm thường được sử dụng

unsigned int RSHash(char* str, unsigned int len)
{
    unsigned int b   = 378551;
    unsigned int a   = 63689;
    unsigned int hash = 0;
    unsigned int i   = 0;

    for(i = 0; i < len; str++, i++)
    {
        hash = hash * a + (*str);
        a    = a * b;
    }

    return hash;
}
/* End Of RS Hash Function */

unsigned int JSHash(char* str, unsigned int len)
{
    unsigned int hash = 1315423911;
    unsigned int i	 = 0;

    for(i = 0; i < len; str++, i++)
    {
        hash ^= ((hash << 5) + (*str) + (hash >> 2));
    }

    return hash;
}
/* End Of JS Hash Function */

unsigned int ELFHash(char* str, unsigned int len)
{
    unsigned int hash = 0;
    unsigned int x	 = 0;
    unsigned int i	 = 0;

    for(i = 0; i < len; str++, i++)
    {
        hash = (hash << 4) + (*str);
        if((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
        }
        hash &= ~x;
    }

    return hash;
}
/* End Of ELF Hash Function */

unsigned int DJBHash(char* str, unsigned int len)
{
    unsigned int hash = 5381;
    unsigned int i	 = 0;

    for(i = 0; i < len; str++, i++)
    {
        hash = ((hash << 5) + hash) + (*str);
    }

    return hash;
}
/* End Of DJB Hash Function */

kiểu dữ liệu javascript

Chuỗi số boolean mảng đối tượng không xác định null

js chỉ có một kiểu số là không xác định: khi biến được khai báo không được khởi tạo, giá trị của biến này là không xác định, Null nghĩa là một đối tượng chưa tồn tại.

nguồn : https://github.com/xiaowenxia/embedded-notes/blob/master/c%E5%9F%BA%E7%A1%80.md

C căn bản

Nội dung

c cơ bản

Mô tả kiểu dữ liệu

volatile

con trỏ – pointer

Con trỏ hàm – Function pointer

Mảng con trỏ hàm – Function pointer array

Mảng con trỏ

Con trỏ mảng

Con trỏ con trỏ

Giá trị trả về của hàm chính

hằng số -const

const T

const T *

Sự khác biệt giữa const int * và int * const

const mnemonic method

Đọc một statement từ phải sang trái. (* Phát âm là con trỏ tới)

Tiêu chuẩn C ++ quy định rằng từ khóa const là tương đương trước kiểu hoặc tên biến.

Phương pháp lưu trữ dấu chấm động

c title

giá trị trả về printf

kiểu liệt kê – enum enumeration type

Hàm đa dạng – Variadic function

Big and small endian

Danh sách liên kết – Linked list

Thuật toán sắp xếp – Sorting Algorithm

Chọn sắp xếp – Select sort

thời gian phức tạp – time complexity

Không gian phức tạp – Space complexity

Các bước thuật toán

Demo hoạt ảnh

Sắp xếp chèn – Insertion sort

thời gian phức tạp

Không gian phức tạp

Các bước thuật toán

Demo hoạt ảnh

Loại đồi – Hill sort

thời gian phức tạp

Không gian phức tạp

Các bước thuật toán

Sắp xếp bong bóng – Bubble Sort

thời gian phức tạp

Không gian phức tạp

Các bước thuật toán

Sắp xếp nhanh chóng – Quick sort

thời gian phức tạp

Không gian phức tạp

Các bước thuật toán

Demo hoạt ảnh

thuật toán băm – hash algorithm

phương pháp xây dựng băm

Xung đột băm và cách giải quyết

Lý do xung đột:

Giải quyết xung đột

Các hàm băm thường được sử dụng

kiểu dữ liệu javascript

Chia sẻ:

Có liên quan

Bình luận về bài viết này Hủy trả lời