Sự tự tham chi ếu của cấu trúc trong C

Chia sẻ: Nguyen Nam | Ngày: | Loại File: PPT | Số trang:30

Thêm vào BST

Báo xấu

89
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

List là 1 cấu trúc dữ liệu mà nó lưu giữ thông tin tổng quát về vị trí của phần tử tiếp theo. Các phần tử của “single linked list ” chỉ có vị trí tiếp theo. Trong C con trỏ được sử dụng để trỏ tới phần tử tiếp theo. Array(mảng): ta có thể truy nhập ở bất kì vị trí nào trong mảng ngay lập tức. Linked list: ta có thể thay đổi số phần tử dữ liệu của nó.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sự tự tham chi ếu của cấu trúc trong C

Chủ đề Sự tự tham chiếu của cấu trúc trong C   Cấu trúc dữ liệu danh sách liên kết đơn (single linked list), danh sách liên kết đôi (double linked list): -Khởi tạo, thi hành. -Thuật toán quét dữ liệu -Thuật toán chèn, xoá.
Sự tự tham chiếu của cấu trúc 1 hoặc nhiều thành phần của nó là con trỏ tới chính  nó. struct list { char data; struct list *link; }; list item1, item2, item3; a b c item1.data=‘a’; item2.data=‘b’; item3.data=‘c’; item1.link=item2.link=item3.lik=NULL;
Thi hành list trong C là 1 cấu trúc dữ liệu mà nó lưu giữ thông tin  List tổng quát về vị trí của phần tử tiếp theo.  Các phần tử của “single linked list ” chỉ có vị trí tiếp theo  Trong C con trỏ được sử dụng để trỏ tới phần tử tiếp theo.  Array(mảng): ta có thể truy nhập ở bất kì vị trí nào trong mảng ngay lập tức.  Linked list: ta có thể thay đổi số phần tử dữ liệu của nó.
Khai báo linked list typedef ... elementtype;//kiểu dữ liệu phần tử typedef struct node{ elementtype element; node* next; }; node* root; node* cur; Hoặc: typedef ... elementtype; struct node{ elementtype element; struct node* next; }; struct node* root; struct node* cur;
Cấp phát bộ nhớ cho 1 phần tử cần cấp phát 1 khối bộ nhớ cho mỗi  Ta node(phần tử) qua 1 con trỏ. struct node * new; new = (struct node*) malloc(sizeof(structnode)); new->element = … new->next = null; • new->addr có nghĩa là (*new).addr. • “con trỏ biến cho bản ghi cấu trúc” ->”tên trường (field)”
Exercise 3.1 thiết kế “address list”(danh sách địa  Ta chỉ) cho các số điện thoại di động .  Phải tạo 1 bản ghi cấu trúc gồm có name, phone number và email address.  Phải tạo 1 chương trình có thể giải quyết với số lượng dữ liệu tuỳ ý.
Exercise 3.1 (tiếp)  Tạo 1 danh sách liên kết đơn chứa danh sách phone address.  Viết 1 hàm insert 1 phần tử vào list ngay sau phần tử hiện thời, sử dụng nó để thêm node vào list  Viết 1 hàm duyệt toàn bộ list và in ra thông tin chứa trong nó.  Viết hàm xoá 1 node khỏi list.
Gợi ý  Bạn có thể tổ chức các phần tử và cấu trúc dữ liệu theo bản ghi cấu trúc AddressList sau.Bạn tự định nghĩa 1 cấu trúc (Address) để chứ thông tin về địa chỉ. struct AddressList { struct AddressList *next; struct Address addr; };
Khai báo bản ghi cấu trúc struct AddressList { struct AddressList *next; struct Address addr; }; biến con trỏ trỏ tới phần tử tiếp  “next”: theo cũng có cùng cấu trúc AddressList.  “addr”: là 1 địa chỉ
3 thừa số quan trọng của 1 list đầu của list  Root:  NULL:giá trị của con trỏ.nó báo hiệu kết thúc của list.  Cur: biến con trỏ lưu giữ phần tử hiện tại. Cur Root (head) NULL
Link list : Insertion (chèn) ngay sau vị trí hiện tại:  Chèn create new_item //phần tử mới cur->next = new; cur = cur->next; Cur … root New_item
Link list : Insertion Chèn ngay sau vị trí hiện tại  new = ( struct AddressList * ) malloc( sizeof(struct AddressList ) ); new->addr = addr; new->next = NULL; if ( root == NULL ) { /* nếu không có phần tử nào */ root = new; cur = root; } else { cur->next = new; cur = cur->next; } }
Link list : Insertion vào trước vị trí hiện tại:  Chèn cur prev … root New_item
Duyệt 1 list  for ( cur = root; cur != NULL; cur = cur- >next ) { showAddress( cur->addr, stdout ); } //showAddress là hàm in ra dữ liệu (tự viết)
Duyệt 1 list đổi giá trị của biến con trỏ cur trong  Thay dãy  Các biến này được gọi là “biến lặp”  Hoàn thành duyệt khi giá trị cur = NULL
Deletion (xoá) xoá phần tử đầu tiên:  Khi del=root; root = del->next; free(del);  Khi xoá phần tử đầu tiên, ta chuyển con trỏ root tới vị trí next được chỉ ra bởi del.
Xoá phần tử ở giữa node đang được trỏ bởi cur.  Xoá  Xác định prev là con trỏ tới node ngay trước node cần xoá.  Sau đó thực hiện: prev->next = cur->next; free(cur);
Exercise 3.2  Tạo hàm insert, delete với tham số n (nguyên) chỉ ra vị trí của node bị tác động đến. Vị trí đầu tiên là 0 - n = 1: thêm phần tử vào sau phần tử đầu tiên. - n = 2: thêm phần tử vào sau phần tử thứ 2. - struct AddressList *insert (struct AddressList *root, struct Address ad, int n); struct AddressList *delete(struct AddressList *root, int n);
Giải phóng list to_free = root ;//to_free là biến lặp lưu vị trí node ta giải phóng while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }
Exercise 3.3 dựng 1 chương trình quản lí sinh viên đơn  Xây giản sử dụng linked list gồm node có cấu trúc như sau: typedef struct Student_t { char id[ID_LENGTH]; char name[NAME_LENGTH]; int grade; struct Student_t *next; } Student;