Xoá phần tử thứ N trong Danh sách liên kết con trỏ bằng C

Đây là chương trình xoá phần tử thứ n trong danh sách liên kết, chương trình được viết bằng C, các bạn cùng tham khảo.

#include
#include
#include
#include

typedef struct tagsl {
int key;
struct tagsl *next;
} SL;

SL *first, *last;

void initialize()
{
first = last = NULL;
}

void cleanup()
{
SL *f;

while (first != NULL)
{
f = first;
first = first->next;
free(f);
}
first = last = NULL;
}

void insert(int key)
{
SL *s;

s = (SL *)malloc(sizeof(SL));
s->key = key;
s->next = NULL;
if (first == NULL)
first = last = s;
else
{
last->next = s;
last = last->next;
}
}

void inds()
{
SL *f;
printf(“\nDanh sach : “);
f = first;
while (f != NULL)
{
printf(“%3d”, f->key);
f = f->next;
}
}

int xoa_n(int n)
{
SL *f, *a;
int i = 0;
a = NULL;
f = first;
while (inext;
}
if (f == NULL)
return 0;
else
{
if (a == NULL)
{
first = f->next;
free(f);
}
else if (f->next == NULL)
{
last = a;
last->next = NULL;
free(f);
}
else
{
a->next = f->next;
free(f);
}
return 1;
}
}

void main()
{
int i, n;
initialize();
randomize();
for (i=0; i<20; i++)
insert(random(20));
inds();
do {
printf(“\nXoa phan tu thu (<0 de thoat) : “); scanf(“%d”, &n); if (n>-1)
{
if (xoa_n(n))
inds();
else
printf(“Danh sach co it hon %d phan tu”, n+1);
}
} while (n > -1);
cleanup();
}

Cùng chạy chương trình và xem kết quả thế nào nhé.

Decode and Encode Base64 using C++

This is a code using when decode and encode base64 using c++ hope this help for you

#include “Base64.h”
#include <stdio.h>
const char b64_alphabet[] = “ABCDEFGHIJKLMNOPQRSTUVWXYZ”
        “abcdefghijklmnopqrstuvwxyz”
        “0123456789+/”;

/* ‘Private’ declarations */
inline void a3_to_a4(unsigned char * a4, unsigned char * a3);
inline void a4_to_a3(unsigned char * a3, unsigned char * a4);
inline unsigned char b64_lookup(char c);

int base64_encode(char *output, char *input, int inputLen) {
    int i = 0, j = 0;
    int encLen = 0;
    unsigned char a3[3];
    unsigned char a4[4];

    while(inputLen–) {
        a3[i++] = *(input++);
        if(i == 3) {
            a3_to_a4(a4, a3);

            for(i = 0; i < 4; i++) {
                output[encLen++] = b64_alphabet[a4[i]];
            }

            i = 0;
        }
    }

    if(i) {
        for(j = i; j < 3; j++) {
            a3[j] = ”;
        }

        a3_to_a4(a4, a3);

        for(j = 0; j < i + 1; j++) {
            output[encLen++] = b64_alphabet[a4[j]];
        }

        while((i++ < 3)) {
            output[encLen++] = ‘=’;
        }
    }
    output[encLen] = ”;
    return encLen;
}

int base64_decode(char * output, char * input, int inputLen) {
    int i = 0, j = 0;
    int decLen = 0;
    unsigned char a3[3];
    unsigned char a4[4];

    while (inputLen–) {
        if(*input == ‘=’) {
            break;
        }

        a4[i++] = *(input++);
        if (i == 4) {
            for (i = 0; i <4; i++) {
                a4[i] = b64_lookup(a4[i]);
            }

            a4_to_a3(a3,a4);

            for (i = 0; i < 3; i++) {
                output[decLen++] = a3[i];
            }
            i = 0;
        }
    }

    if (i) {
        for (j = i; j < 4; j++) {
            a4[j] = ”;
        }

        for (j = 0; j <4; j++) {
            a4[j] = b64_lookup(a4[j]);
        }

        a4_to_a3(a3,a4);

        for (j = 0; j < i – 1; j++) {
            output[decLen++] = a3[j];
        }
    }
    output[decLen] = ”;
    return decLen;
}

int base64_enc_len(int plainLen) {
    int n = plainLen;
    return (n + 2 – ((n + 2) % 3)) / 3 * 4;
}

int base64_dec_len(char * input, int inputLen) {
    int i = 0;
    int numEq = 0;
    for(i = inputLen – 1; input[i] == ‘=’; i–) {
        numEq++;
    }

    return ((6 * inputLen) / 8) – numEq;
}

inline void a3_to_a4(unsigned char * a4, unsigned char * a3) {
    a4[0] = (a3[0] & 0xfc) >> 2;
    a4[1] = ((a3[0] & 0x03) << 4) + ((a3[1] & 0xf0) >> 4);
    a4[2] = ((a3[1] & 0x0f) << 2) + ((a3[2] & 0xc0) >> 6);
    a4[3] = (a3[2] & 0x3f);
}

inline void a4_to_a3(unsigned char * a3, unsigned char * a4) {
    a3[0] = (a4[0] << 2) + ((a4[1] & 0x30) >> 4);
    a3[1] = ((a4[1] & 0xf) << 4) + ((a4[2] & 0x3c) >> 2);
    a3[2] = ((a4[2] & 0x3) << 6) + a4[3];
}

inline unsigned char b64_lookup(char c) {
    if(c >=’A’ && c <=’Z’) return c – ‘A’;
    if(c >=’a’ && c <=’z’) return c – 71;
    if(c >=’0′ && c <=’9′) return c + 4;
    if(c == ‘+’) return 62;
    if(c == ‘/’) return 63;
    return -1;
}
int main()
{
    char input[] =”aaaaaaaa”;
    char output[]=””;
    int a = base64_encode(output,input,8);
    printf(output);
    //char *output
    return 0;
}

C Structure

Introducing to C structure

In some programming contexts, you need to access multiple data types under a single name for easier data manipulation; for example you want to refer to address with multiple data like house number, street, zip code, country. C supports structure which allows you to wrap one or more variables with different data types. A structure can contain any valid data types like int, char, float even arrays or even other structures. Each variable in structure is called a structure member.

Defining structure

To define a structure, you use struct keyword. Here is the common syntax of structure definition:

 

struct struct_name{ structure_member };

 

The name of structure follows the rule of variable name. Here is an example of defining address structure:

 

struct address{
      unsigned int house_number;
      char street_name[50];
      int zip_code;
      char country[50];
    };

The address structure contains house number as an positive integer, street name as a string, zip code as an integer and country as a string.

Declaring structure

The above example only defines an address structure without creating any structure instance. To create or declare a structure instance, you can do it in two ways:

The first way is to declare a structure followed by structure definition like this :

 

struct struct_name {
      structure_member;
      …
    } instance_1,instance_2 instance_n;

 

In the second way, you can declare the structure instance at a different location in your source code after structure definition. Here is structure declaration syntax :

struct struct_name instance_1,instance_2 instance_n;

 

Complex structure

If a structure contains arrays or other structures, it is called complex structure. For example address structure is a structure. We can define a complex structure called customer which contains address structure as follows:

 

struct customer{
      char name[50];
      structure address billing_addr;
      structure address shipping_addr;
    };

 

Accessing structure member

To access structure members we can use dot operator (.) between structure name and structure member name as follows:

structure_name.structure_member

For example to access street name of structure address we do as follows:

 

struct address billing_addr;
billing_addr.country = "US";

 

If the structure contains another structure, we can use dot operator to access nested structure and use dot operator again to access variables of nested structure.

 

struct customer jack;
jack.billing_addr.country = "US";

 

Initializing structure

C programming language treats a structure as a custom data type therefore you can initialize a structure like a variable. Here is an example of initialize product structure:

 

struct product{
      char name[50];
      double price;
    } book = { "C programming language",40.5};

In above example, we define product structure, then we declare and initialize book structure with its name and price.

Structure and pointer

A structure can contain pointers as structure members and we can create a pointer to a structure as follows:

struct invoice{
        char* code;
        char date[20];
    };
    struct address billing_addr;
    struct address *pa = &billing_addr;

 

Shorthand structure with typedef keyword

To make your source code more concise, you can use typedef keyword to create a synonym for a structure. This is an example of using typedef keyword to define address structure so when you want to create an instance of it you can omit the keyword struct

typedef struct{
          unsigned int house_number;
          char street_name[50];
          int zip_code;
          char country[50];
    } address;
    address billing_addr;
    address shipping_addr;

 

Copy a structure into another structure

One of major advantage of structure is you can copy it with = operator. The syntax as follows

 

struct_intance1 = struct_intance2

be noted that some old C compilers may not supports structure assignment so you have to assign each member variables one by one.

Structure and sizeof function

sizeof is used to get the size of any data types even with any structures. Let’s take a look at simple program:

 

#include <stdio.h>
 
typedef struct __address{
    int house_number;// 4 bytes
    char street[50]; // 50 bytes
    int zip_code; // 4 bytes
    char country[20];// 20 bytes
 
} address;//78 bytes in total
 
void main()
{
    // it returns 80 bytes
    printf("size of address is %d bytes\n",sizeof(address));
}

You will never get the size of a structure exactly as you think it must be. The sizeof function returns the size of structure larger than it is because the compiler pads struct members so that each one can be accessed faster without delays. So you should be careful when you read the whole structure from file which were written from other programs.

Source code example of using C structure

In this example, we will show you how to use structure to wrap student information and manipulate it by reading information to an array of student structure and print them on to console screen.

 

#include <stdio.h>
 
typedef struct _student{
    char name[50];
    unsigned int mark;
} student;
 
 
 
void print_list(student list[], int size);
void read_list(student list[], int size);
 
 
 
void main(){
 
    const int size = 3;
    student list[size];
    
    read_list(list,size);
 
    print_list(list,size);
 
 
}

void read_list(student list[], int size)
{
    printf("Please enter the student information:\n");
 
    for(int i = 0; i < size;i++){
        printf("\nname:");
        scanf("%S",&list[i].name);
 
        printf("\nmark:");
        scanf("%U",&list[i].mark);
    }
 
}

void print_list(student list[], int size){
    printf("Students' information:\n");
    
    for(int i = 0; i < size;i++){
        printf("\nname: %s, mark: %u",list[i].name,list[i].mark);
    }
}

Here is program’s output

 

Please enter the student information:

name:Jack

mark:5

name:Anna

mark:7

name:Harry

mark:8
Students' information:

name: J, mark: 5
name: A, mark: 7
name: H, mark: 8

Heapsort

Heapsort algorithm is a comparison-based sorting algorithm. The heap sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.
Heapsort inserts the input list elements into a heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap’s invariant is preserved after each extraction, so the only cost is that of extraction.
During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)
Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.

 
#include <stdlib.h> 
#include <stdio.h>
 
 
#define uint unsigned int
 
typedef int (*compare_func)(int, int);

 
void heap_sort(int This[], compare_func func_pointer, uint len)
{
  /* heap sort */

  uint half;
  uint parents;

  if (len <= 1)
    return;

  half = len >> 1;
  for (parents = half; parents >= 1; --parents)
  {
    int tmp;
    int level = 0;
    uint child;

    child = parents;
    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < len) &&
          ((*func_pointer)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    tmp = This[parents - 1];
    for (;;)
    {
      if (parents == child)
        break;
      if ((*func_pointer)(tmp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parents to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = tmp;
  }

  --len;
  do
  {
    int tmp;
    int level = 0;
    uint child;

    /* move max element to back of array */
    tmp = This[len];
    This[len] = This[0];
    This[0] = tmp;

    child = parents = 1;
    half = len >> 1;

    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < len) &&
          ((*func_pointer)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parents == child)
        break;
      if ((*func_pointer)(tmp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parents to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = tmp;
  } while (--len >= 1);
}

 
#define ARRAY_SIZE 250000
 
int my_array[ARRAY_SIZE];
 
void init()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
}
 
int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}
 
int main()
{
  int indx;
 
  init();
 
  heap_sort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  return(0);
}
 
 

Binary Search

Binary search is an algorithm for finding the location of an element in a sorted list. First, it checks the middle element of the sort list; if that element is equal to the sought value then the location has been found; Othewise, the lower half or upper half is chosen for next searching based on the sought value less than or greater than the middle element. By doing so, this binary search reduces the number of elements to be checked by a factor of two each time searching and find the element in logarithmic time.

ImageHandler2

Binary Search implemented in C.

int binary_search(int sorted_list[], int low, int high, int element) {
    while (low <= high) {
        int middle = low + (high - low)/2;
        if (element > sorted_list[middle])
            low = middle + 1;
        else if (element < sorted_list[middle])
			high = middle - 1;
        else
            return middle;
    }
    return -1;
}

Binary Search in using recursion technique.

int binary_search(int sorted_list[], int low, int high, int element) {
    if (high < low)
        return -1;
    int middle = low + (high - low)/2;
    if (element < sorted_list[middle])
        return binary_search(sorted_list, low, middle-1, element);
    else if (element > sorted_list[middle])
        return binary_search(sorted_list, middle+1, high, element);
    else
        return middle;
}