Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn
tải về 1.56 Mb.
|
- Điều hướng trang này:
- 2. Cài đặt hàng đợi sử dụng mảng
- 3. Cài hàng đợi sử dụng con trỏ
- 4. Một số ứng dụng của hàng đợi
- 2. Truy cập
III. Hàng đợi1. Khái niệmHàng đợi là cấu trúc dữ liệu tương tự ngăn xếp nhưng nguyên tắc đưa vào và lấy ra các phần tử theo thứ tự phần tử đưa vào trước sẽ lấy ra trước FIFO (First In First Out). Qui luật này thể hiện các mô hình trong thực tế như hàng đợi mua vé, hàng hóa trong kho, … Do các phần tử vào trước được lấy ra trước nên cần phải xây dựng danh sách có hai đầu, đầu vào và đầu ra. 
Put(s,’F’) Get(s)
2. Cài đặt hàng đợi sử dụng mảngCó thể sử dụng mảng để lưu trữ dữ liệu, vì thế có thể sử dụng để mô tả hàng đợi. Do hàng đợi có hai đầu nên cần phải có hai chỉ số để đánh dấu. Do việc lấy dữ liệu và đưa dữ liệu vào trong danh sách đều tăng chỉ số nên cần phải kiểm tra trong trường hợp chỉ số vượt qua giới hạn của mảng cần phải chuyển chỉ số về 0. 
Khai báo typedef struct queue { int head, tail; int storage[MAX]; };
void init(queue *s) { s->tail=0; s->head=0; }
///0: empty int empty(queue *s) { int d=s->head-s->tail; if(d<0) d+=MAX;
return d; }
///0:full int full(queue *s) { int nh=s->head+1; if(nh==s->tail || (nh + MAX)%MAX==s->tail) { return 0; } return 1; }
//-1 full of queue int put(queue *s, int value) { if(full(s)==0) return -1; s->storage[s->head]=value; s->head++; s->head=s->head%MAX; return s->head; }
//-1: try to pop the empty queue int get(queue *s, int *out) { if(empty(s)==0) return -1; *out=s->storage[s->tail]; s->tail++; s->tail=s->tail%MAX; return s->tail; }
Sử dụng hai con trỏ là đầu và đuôi. Khi thêm nối vào sau con trỏ đuôi, và khi lấy ra sẽ từ con trỏ đầu. 
Khai báo typedef struct queueNode { int item; queueNode *next; }; typedef struct queue{ queueNode* head, *tail; };
void init(queue *s) { s->head=NULL; s->tail=NULL; }
///0: empty int empty(queue *s) { if(s->head==NULL) { return 0; } else
{ return 1; } }
///-1: cant push to queue int put(queue *s,int value) { queueNode *a; a=(queueNode*)malloc(sizeof(queueNode)); if(a==NULL) { return -1; } a->item=value; a->next=NULL; if(s->tail==NULL) { s->tail=a; s->head=a; } s->tail->next=a; s->tail=a; return 0; }
///-1: pop empty queue int get(queue *s,int *out) { queueNode *a; if(s->head==NULL) { return -1; } *out=s->head->item; a=s->head; s->head=s->head->next; if(s->head==NULL) { s->tail=NULL; } free(a);
} 4. Một số ứng dụng của hàng đợi- Hàng đợi được sử dụng trong mô phỏng các mô hình hàng đợi thực tế trong các bài toán - Sử dụng trong bài toán duyệt theo chiều rộng IV. Kiểu hợp1. Khai báoKiểu hợp cũng có nhiều thành phần nhưng các thành phần sử dụng chung nhau một vùng nhớ. Do vậy kích thước của một kiểu hợp là độ dài của trường lớn nhất và việc thay đổi một thành phần sẽ ảnh hưởng đến tất cả các thành phần còn lại. union Danh sách các thành phần; }; 2. Truy cậpCú pháp truy cập đến các thành phần của hợp cũng tương tự như kiểu cấu trúc, tức cũng sử dụng toán tử lấy thành phần (dấu chấm . hoặc → cho biến con trỏ kiểu hợp). Dưới đây là một ví dụ minh hoạ việc sử dụng khai báo kiểu hợp để tách byte thấp, byte cao của một số nguyên.
void main() { union songuyen { int n; unsigned char c[2]; } x; printf("Nhap so nguyen:"); scanf(“%d”,&x.n); printf("Byte thap:%d, byte cao:%d",x.c[0],x.c[a]); }
union {
struct { unsigned a, b ; } s; struct { unsigned n1: 1; unsigned: 15; unsigned n2: 1; unsigned: 7; unsigned n3: 8; } t ;
} u; với khai báo trên đây khi nhập u.s thì nó cũng ảnh hưởng đến u.t, cụ thể − u.t.n1 là bit đầu tiên (0) của thành phần u.s.a − u.t.n2 là bit 0 của thành phần u.s.b − u.t.n3 là byte cao của u.s.b
Каталог: files -> FileMonHoc FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon FileMonHoc -> Khoa cntt cộng hòa xã HỘi chủ nghĩa việt nam tải về 1.56 Mb. Chia sẻ với bạn bè của bạn:
|