Bài 1. Danh sách đặc

Mô hình

Lý thuyết

Source Code

arrayList.h

KHỞI TẠO

#define Max_length 50
typedef struct{
    int Data[Max_length];
    int Size;
}List;

KHỞI TẠO RỖNG

void makeNullList(List *L){
    L->Size = 0;
}

HIỂN THỊ DANH SÁCH

void displayList(List L){
    for (int i = 0; i < L.Size; i++){
        printf("%d ",L.Data[i]);
    }
}

THÊM N PHẦN TỬ TRONG LIST

void InputList(int n,List *L){
    makeNullList(L);
    for(int i = 0; i < n ; i++){
        scanf("%d",&L->Data[i]);
        L->Size++;
    }
}

XOÁ PHẦN TỬ TẠI VỊ TRÍ P TRONG LIST

void deleteListbyPos(int p,List *L){
    for(int i = p; i < L->Size - 1; i++){
        L->Data[i] = L->Data[i+1];
    }
    L->Size--;
}

XOÁ PHẦN TỬ X TRONG LIST

void deleteListbyID(int x, List *L){
    for(int i = 0; i < L->Size; i++){
        if(L->Data[i] == x){
            deleteListbyPos(i,L);
        }
    }
}

TRẢ VỀ VỊ TRÍ ĐẦU TIÊN CỦA X TRONG LIST

int locateList(int x,List L){
    for(int i = 0 ; i < L.Size ; i++){
        if(L.Data[i] == x){
            return i;
        }
    }
    return -1;
}

KIỂM TRA X TRONG LIST

int memberList(int x,List L){
    if(locateList(x,L) != 1){
        return 1;
    }
    return 0;
}

TỐI ƯU DANH SÁCH (`1 2 3` -> `1 2`)

void optimizeList(List *L){
    int  i = 0;
    int j;
    while (i != L->Size){
        j = i + 1;
        while (j != L->Size){
            if(L->Data[i] == L->Data[j]){
                deleteListbyPos(j,L);
            }
            else{
                j++;
            }
        }
        i++;
    }  
}

THÊM X TẠI VỊ TRÍ P TRONG LIST

void insertList(int x,int p,List *L){
    if(L->Size == Max_length){
        printf("Full List!!!");
    }
    else if(p < 0 || p > L->Size){
        printf("Position Invalid!!!");
    }
    else{
        for(int i = L->Size; i >= p ; i--){
            L->Data[i]=L->Data[i-1];
        }
        L->Size++;
        L->Data[p] = x;
    }
}

CHUYỂN DANH SÁCH QUA DANH SÁCH MỚI

void changeList(List L1,List *L){
    for(int i = 0 ; i < L1.Size ; i++){
        insertList(L1.Data[i],L->Size,L);
    }
}

GỘP 2 DANH SÁCH VÀO MỘT

void mergeList(List L1,List L2,List *L){
    changeList(L1,L);
    changeList(L2,L);
}

LỌC PHẦN TỬ CHẲN HOẶC LẺ QUA MỘT DANH SÁCH

void filter_evenNumber(List L1,List *L){
    int k = 0;
    for(int i = 0 ; i < L1.Size; i++){
        if(L1.Data[i] % 2 == 0){
            insertList(L1.Data[i],k,L);
            k++;
        }
    }
}

void filter_oddNumber(List L1,List *L){
    int k = 0;
    for (int i = 0; i < L1.Size; i++){
        if(L1.Data[i] % 2 != 0){
            insertList(L1.Data[i],k,L);
            k++;
        }
    }
}

TÍNH TRUNG BÌNH CÁC PHẦN TỬ TRONG DANH SÁCH

double averageList(List L){
    double result = 0;
    for (int i = 0; i < L.Size; i++){
        result += L.Data[i];
    }
    return result/L.Size;
}

searchList.h

TÌM KIẾM TUYẾN TÍNH

// không cần sắp xếp
int linearSearch(int x,List L){
    for (int i = 0; i < L.Size; i++){
        if(L.Data[i] == x){
            return i;
        }
    }
    return 1;
}

TÌM KIẾM NHỊ PHÂN

// cần sắp xếp
int binarySearch(int x,List L){
    int left = 0;
    int right = L.Size - 1;
    int mid;
    while(right >= left){
        mid = left + ((right - left) / 2);
        if(L.Data[mid] == x){
            return mid;
        }
        else if(L.Data[mid] > x){
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    return -1;
}

sortList.h

HOÁN ĐỔI 2 SỐ

void swap(int *a,int *b){
  int temp = *a;
  *a = *b;
  *b = temp;
}

SẮP XẾP TRỰC TUYẾN

void interchangeSort(List *L){
  for (int i = 0; i < L->Size - 1; i++){
    for (int j = i + 1; j < L->Size; j++){
      if(L->Data[i] > L->Data[j]){
        swap(&L->Data[i],&L->Data[j]);
      }
    }
  }
}

SẮP XẾP CHỌN

void selectionSort(List *L){
  for(int i = 0 ; i < L->Size - 1; i++){
    int min = i;
    for (int j = i + 1; j < L->Size; j++){
      if(L->Data[min] > L->Data[j]){
        min = j;
      }
    }
    if(min != i){
      swap(&L->Data[min],&L->Data[i]);
    }
  }
}

SẮP XẾP NỔI BỌT

void bubbleSort(List *L){
  for (int i = 0; i < L->Size; i++){
    for (int j = L->Size - 1; j >= 0; j--){
      if(j > i){
        if(L->Data[j] < L->Data[j-1]){
          swap(&L->Data[j],&L->Data[j-1]);
        }
      }
    }
  }
}

SẮP XẾP CHÈN

void insertionSort(List *L){
  int x;
  int pos;
  for (int i = 1; i < L->Size; i++){
    pos = i - 1;
    x = L->Data[i];
    while (pos >= 0 && L->Data[pos] > x){
      L->Data[pos + 1] = L->Data[pos];
      pos--;
    }
    L->Data[pos+1] = x;
  }
}

SẮP XẾP CÂY NHỊ PHÂN

void heaplify(int i,int n,List *L){
  while (i <= (n / 2) - 1){
    int left = (2 * i) + 1;
    int right = (2 * i) + 2;
    int max = left;
    if(right < n && L->Data[right] > L->Data[max]){
      max = right;
    }
    if(L->Data[i] < L->Data[max]){
      swap(&L->Data[i],&L->Data[max]);
    }
    i = max;
  }
}

void heapSort(List *L){
  for(int i = (L->Size - 1) / 2; i >= 0 ; i--){
      heaplify(i,L->Size,L);
  }
  for(int i = L->Size - 1 ; i >= 0 ; i--){
    swap(&L->Data[0],&L->Data[i]);
    heaplify(0,i,L);
  }
}

SẮP XẾP SHELL

void shellSort(List *L){
  int x,pos;
  int divide = 2; // có thể thay đổi vách chia
  for(int h = L->Size / divide; h > 0 ; h /= divide){
    for(int i = h ; i < L->Size ; i++){
      x = L->Data[i];
      pos = i - h;
      while (pos >= 0 && L->Data[pos] > x){
        L->Data[pos + h] = L->Data[pos];
        pos -= h;
      }
        L->Data[pos+h] = x;
    }
  }
}

SẮP XẾP NHANH

void quickSort(List *L,int start,int end){
  int pivot = L->Data[(start + end) / 2]; // tuỳ chọn pivot
  int left = start;
  int right = end;
  while(left <= right){
    while(L->Data[left] < pivot){
      left++;
    }
    while(L->Data[right] > pivot){
      right--;
    }
    if(left <= right){
      swap(&L->Data[left],&L->Data[right]);
      left++;
      right--;
    }
  }
  if(right > start){
    quickSort(L,start,right);
  }
  if(left < end){
    quickSort(L,left,end);
  }
}

SẮP XẾP GỘP

void merge(List *L,int left,int mid,int right){
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int M1[n1],M2[n2];
  for (int i = 0; i < n1; i++){
    M1[i] = L->Data[left + i];
  }
  for (int i = 0; i < n2; i++){
    M2[i] = L->Data[mid + 1 + i];
  }
  int i = 0;// mảng R
  int j = 0;// mảng Q
  int k = left;
  while (i < n1 && j < n2){
    if (M1[i] <= M2[j]){
      L->Data[k] = M1[i];
      i++;
    }
    else{
      L->Data[k] = M2[j];
      j++;
      k++;
    }
  }
  while (i < n1){
    L->Data[k] = M1[i];
    i++;
    k++;
  }
  while (j < n2){
    L->Data[k] = M2[j];
    j++;
    k++;
  }
}

void mergeSort(List *L,int start,int end){
  if(start < end){
    int half = start + ((end - start) / 2);
    mergeSort(L,start,half);
    mergeSort(L,half + 1,end);
    merge(L,start,half,end);
  }
}