Lập trình C | Cơ bản về mảng

[hailoc12]

Kiến thức tổng quát trước khi đi vào các đề tài cụ thể

Chúng ta sẽ đối diện với nhiều lĩnh vực áp dụng khác nhau, cố gắng tập trung vào các thuật toán "cơ sở" quan trọng cần phải biết và thú vị để nghiên cứu.
Để học một thuật toán tốt, ta phải cài đặt và chạy nó để tiện cho các bạn trong diễn đàn, chúng ta sẽ sử dụng ngôn ngữ C++ để cài đặt nó. Tuy nhiên, do cái chúng ta đang bàn tới là giải thuật vì vậy chương trình của chúng ta có thể dễ dàng được dịch thành nhiều ngôn ngữ hiện đại khác.
Để học và thảo luận về giải thuật được tốt, có hiệu quả, các thành viên cần nắm được các kiến thức về những cấu trúc dữ liệu đơn giản dùng trong các thuật toán cơ sở như mảng, ngăn xếp, hàng đợi và cây, mặc dù các kiến thức này cũng sẽ được nhắc lại trong mục Cơ sở. Các bạn cũng cần có hiểu biết cơ sở về tổ chức máy, về ngôn ngữ lập trình và những khái niệm tin học cơ bản, chủ yếu dựa trên hệ điều hành DOS. Một vài lĩnh vực áp dụng mà ta sẽ gặp cần tri thức về số học cơ sở, hay các kiến thức toán học về đại số tuyến tính, hình học, toán rời rạc.

Khi viết một chương trình máy tính, ta thường cài đặt một phương pháp đã được nghĩ ra trước đó để giải quyết một vấn đề. Phương pháp này thường độc lập với một máy tính cụ thể sẽ được dùng: nó hầu như thích hợp như nhau cho nhiều máy tính. Trong bất kì trường hợp nào, thì phương pháp, chứ không phải là bản thân chương trình máy tính là cái phải đựơc nghiên cứu để học cách làm thế nào tấn công vào bài toán.
Hầu hết các thuật toán đáng chú ý cần đến các phương pháp tổ chức dữ liệu phức tạp trong lúc tính toán. Các đối tượng đựơc tạo ra theo cách này gọi là các cấu trúc dữ liệu, và chúng cũng là các đối tượng trung tâm cần nghiên cứu trong khoa học máy tính. Vì vậy các thuật toán và cấu trúc dữ liệu đi liền với nhau.
Khi giải quyết một bài toán lớn, ta sẽ phải bỏ nhiều công sức để hiểu được và định nghĩa được bài toán sẽ giải quyết, quản lý được độ phức tạp của nó, và phân rã nó thành các vấn đề nhỏ hơn mà nó có thể dễ dàng được cài đặt. Thực tế là nhiều bài toán đựơc yêu cầu, sau khi phân rã lại trở thành tầm thường khi cài đặt. Tuy nhiên,
Internet ngày càng phổ biến hơn và việc tìm được cài đặt thuật toán mình cần trên mạng đã trở nên dễ dàng. Tuy nhiên, việc cài đặt các phiên bản đơn giản của thuật toán cơ sở sẽ giúp chúng ta hiểu được chúng tốt hơn và vì vậy việc dùng các phiên bản nâng cao sẽ hiệu quả hơn.
Thông thường nhiều thuật toán khác nhau (hay về cài đặt khác nhau) là khả dụng để giải quyết cùng một bài toán. Việc chọn lựa thụât toán tốt nhất cho một công việc là một tiến trình rất phức tạp, thường cần đến sự phân tích toán học tinh vi.Nhiều thuật toán mà chúng ta sẽ nghiên cứu đã được chứng minh qua việc phân tích, là có hiệu năng rất tốt, trong khi các thuật toán đơn giản chỉ được biết đến là đã hoạt động tốt trong kinh nghiệm. Vì vậy không nên dùng một thụât toán mà không có một nhận xét nào đó về những tài nguyên mà nó có thể tiêu thụ. Vì vậy các bạn nên học qua một chút về cách phân tích độ phức tạp của thuật toán.

[hailoc12]

Các cấu trúc dữ liệu cơ bản
Một CTDL không phải là một đối tượng thụ động: chúng ta cũng phải xem xét các thao tác sẽ được thực hiện trên nó ( và những thụât toán dùng cho các thao tác này). Khái niệm này đựơc chuẩn hoá trong khái niệm của một kiểu dữ liệu trừu tượng .
Chúng ta sẽ xem xét mảng, xâu liên kết, ngăn xếp, hàng đợi, và các biến thể đơn giản khác. Đây là các CTDL cổ điển với tính ứng dụng rộng rãi: cùng với cây , chúng tạo thành nền tảng cho hầu như tất cả các thuật toán. Trong mục này, chúng ta xem xét cá biểu diễn cơ sở của các phương pháp cơ bản để sử dụng các cấu trúc này, thực hiện qua một số ví dụ đặc thù về tính ứng dụng của chúng, và thảo luận các chủ đề có liên quan như quản lý bộ nhớ.

Mảng
(array)

Có lẽ CTDL cơ bản nhất là mảng, được định nghĩa như là cấu trúc nguyên sơ trong Pascal và hầu hết các ngôn ngữ lập trình khác. Một mảng là một số cố định các mẫu dữ liệu được chứa một cách liên tục và có thể đựơc truy xuất bởi một chỉ mục (index). Chúng ta coi phần tử thứ i của một mảng như là a[i]., Trách nhiệm của người lập trình là chứa một cái gì đó có nghĩa trong vị trí mảng a[i] trước khi tham khảo tới nó; sao lãng điều này là một trong nhưngx lỗi lập trình phổ biến nhất.
Một ví dụ đơn giản của việc dùng một mảng cho bởi chương trình sau, mà nó in ra tất cả các số nguyên tố nhỏ hơn 1000. Phương pháp được sử dụng, ra đời từ thế kỉ thứ3 trước Công nguyên, được gọi là " sàng Eratosthenes":

#include "stdio.h"#include "stdlib.h"void main(){  #define N 101  int a[N], i, j;  a[1]= 0; // false  for(i=2; i<=N; i++) a[i]=1; //true  for(i=2; i<= div(N, 2).quot; i++)    for (j=2; j<= div(N, i).quot; j++) a[i*j]=0; //false  for(i=1; i<= N; i++)    if(a[i]) printf("%4d", i);}

Nếu bạn chưa sử dụng thành thạo mảng trong C,có thể tham khảo thêm tại đây: Học lập trình C Online | Tự học C qua Cộng đồng C Việt

Chương trình này sử dụng một mảng có kiểu các phần tử đơn giản nhất, là các giá trị luận lý. Mục đích của chương trình là đặt a[i] về đúng (khác0) nếu i là số nguyên tố, "sai" (bằng 0) nếu không. Nó làm điều này bằng cách, với mõi i, đặt phần tử mảng tương ứng với một bội số của i là "sai" vì bất kì một số nào mà là một bội của bất kì một số khác thì không thể là số nguyên tố. Sau đó nó đi dọc theo mảng một lần nữa, in ra các số nguyên tố. Có thể cải tiến bằng cách thêm lệnh kiểm tra if a[i] trước vòng lặp for cho j, vì nếu i không là nguyên tố, thì tất cả các bội của nó đã phải được đánh dấu rồi. Lưu ý đầu tiên mảng đựơc khởi tạo giá trị bằng cách gán tất cả đều là "đúng". Thuật toán sẽ đặt về "sai" các phần tử mảng tương ứng với các chỉ mục không nguyên tố.
Sàng Eratothenes là trường hợp đặc trưng trong số các thuật toán khai thác đặc tính có thể truy xuất phần tử mảng một cách hiệu quả. Thuật toán cũng truy xuất các phần tử của mảng một cách tuần tự, cái này sau cái kia.
Tính chất cơ bản của mảng là có kích thước cố định và phải được biết trước khi chúng đựơc sử dụng dù rằng ở một số ngôn ngữ như vb có hỗ trợ mảng động có kích thước thay đổi trong khi chạy.
Mảng là các CTDL cơ bản trong đó chúng có một sự tương ứng trực tiép với các hệ thống bộ nhớ trên hầu hết các máy tính. Để nhận được nội dung một từ (word) của bộ nhớ trong ngôn ngữ máy, chúng ta cung cấp một địa chỉ. Vì vậy, ta có thể nghĩ về toàn thể bộ nhớ như là một mảng, với các địa chỉ bộ nhớ tương ứng với các chỉ mục mảng.
Một cách khác tương tự để cấu trúc các thông tin là dùng một bảng số hai chiều đựơc tổ chức thành hàng và cột. Ví dụ, một bảng điểm của các sinh viên trong một học trình có thể có một hàng cho mỗi sinh viên, một cột cho mỗi điểm. Việc sử dụng các mảng trên 3 chiều cũng là dễ dàng.
Mảng cũng tương ứng trực tiếp với các vector, một thuật ngữ toán học dùng cho một danh sách các đối tượng có chỉ mục. Tương tự, các mảng hai chiều tương ứng với các ma trận.