Xem mẫu
- 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;
nguon tai.lieu . vn
