8/4/2020
20
39
1.2.2 Ngôn ngữ diễn đạt giải thuật
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int max(int *x,int n)
{ int result = x[0];
for (int i=1;i<n;i++)
if (result<x[i])
result=x[i];
return result;
}
void main()
{
int n,*a;
printf("nhap so phan tu:"); scanf("%d",
&n);
a=(int*)malloc(n*sizeof(int));
if (a==NULL)
{
printf("khong du bo nho");
exit(0);
}
printf("\n nhap cac phan tu cua day:\n");
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("gia tri max cua day
la:%d",max(a,n));
getch();
}
Cấu trúc dữ liệu và giải thuật
Chương 2 (12t)
2.1 Mảng
2.2 Danh sách
2.3 Ngăn xếp
2.4 Hàng đợi
Cấu trúc dữ liệu và giải thuật 40
8/4/2020
21
2.1 Mảng (Array)
2.1.1 Khái niệm
2.1.2 Một số phép toán trên mảng
2.1.3 Cài đặt mảng 1 và 2 chiều
Cấu trúc dữ liệu và giải thuật 41
2.1.1 Khái niệm
❖Khái niệm:mảng là một tập có thứ tự gồm một số cố
định các phần tử cùng kiểu dữ liệu
→là một cấu trúc dữ liệu
❖Mỗi phần tử được xác định và truy cập bởi tên mảng và
chỉ số của phần tử đó (là thứ tự của phần tử)→truy cập
ngẫu nhiên
❖Kiểu dữ liệu mảng: 1chiều, nhiều chiều
❖Ví dụ:vectơ, ma trận
Cấu trúc dữ liệu và giải thuật 42
8/4/2020
22
2.1.1 Khái niệm
❖Cấu trúc lưu trữ mảng: là hình thức lưu trữ kế
tiếp
▪Địa chỉ các phần tử liên tiếp nhau
▪Các phần tử được sắp xếp theo hàng
▪Bộ nhớ cố định
❖Đặc điểm:
▪Cấu trúc đơn giản, truy cập nhanh
▪Thiếu mềm dẻo trong các phép toán như xóa, chèn
Cấu trúc dữ liệu và giải thuật 43
2.1.2 Một số phép toán trên mảng
❖Tạo lập mảng
❖Nhập/xuất mảng
❖Cập nhập phần tử mảng
❖Duyệt mảng (tìm kiếm một phần tử của mảng)
❖Không có phép toán thêm/bớt phần tử
( Sinh viên tự cài đặt)
Cấu trúc dữ liệu và giải thuật 44
8/4/2020
23
2.1.3 Cài đặt mảng 1 chiều và 2 chiều
#define N 10
void main() { // cài đặt một mảng có kích thước cho
trước
clrscr();
int a[N];// khai bao mang kich thuoc N
for(int i=0; i<N; i++) {
printf("nhap gia tri cho phan tu thu %d: ",i);
scanf("%d", &a[i]); }
for(int j=0; j<N; j++) {
printf(" %d, ",a[j]); }
getch();
}
Cấu trúc dữ liệu và giải thuật 45
2.1.3 Cài đặt mảng 1 chiều và 2 chiều
#define N 10
#define M 5
void main() { //cài đặt một mảng 2 chiều, kích thước cho trước
int a[N][M];// khai bao mang kich thuoc NxM
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
printf("nhap gia tri cho phan tu thu %d %d: ",i , j);
scanf("%d", &a[i][j]); } }
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
printf(" %d, ",a[i][j]);} }
}
Cấu trúc dữ liệu và giải thuật 46
8/4/2020
24
2.2 Danh sách (List)
2.2.1 Khái niệm
2.2.2 Phân loại danh sách
2.2.4 Cài đặt danh sách liên kết
2.2.5 Các phép toán trên danh sách liên kết
Cấu trúc dữ liệu và giải thuật 47
2.2.1 Khái niệm
❖Khái niệm :danh sách là tập có thứ tự các phần tử cùng
kiểu
▪Số phần tử biến động
▪Các phần tử được sắp xếp theo thứ tự trước – sau
❖Danh sách tuyến tính:thể hiện quan hệ lân cận giữa các
phần tử
▪Hoặc là danh sách rỗng hoặc có dạng (a1, a2,…, an)
▪n: độ dài / kích thước của danh sách
▪Mỗi phần tử thường là một bản ghi bao gồm một hoặc nhiều
trường (field)
❖Ví dụ:danh sách sinh viên, danh mục điện thoại
Cấu trúc dữ liệu và giải thuật 48