Bài giảng Lập trình C - Chương 2: Ngôn ngữ C - Con trỏ (Pointer)

Tập giá trị [-32768, 32767]
Tập các thao tác: +, -, *, /, %
 Kiểu con trỏ (của 1 kiểu dữ liệu T) cũng vậy gồm: 
Tập giá trị là tập địa chỉ của kiểu dữ liệu T tương ứng
Tập thao tác: tạo con trỏ đến đối tượng có kiểu T
 Ví dụ: con trỏ số nguyên được khai báo như sau
int *p;
// có kích thước cố định 2 hay 4 byte tùy vào NNLT, loại con trỏ
//Con trỏ kiểu int thì có thể lưu được địa chỉ của biến kiểu int. 
9/16/2008 T.P.Tuấn - LTC 10
 Biến động
 Không được khai báo tường minh
 Có thể được cấp pháp hoặc giải phóng bộ nhớ khi người sử dụng 
yêu cầu. 
 Các biến này không theo quy tắc phạm vi (tĩnh)
 Vùng nhớ của biến được cấp phát trong Heap. 
 Kích thước có thể thay đổi trong quá trình sống
 Con trỏ làm nhiệm vụ quản lý các biến này bằng cách lưu địa chỉ
vùng nhớ của chúng. 
 Ví dụ: 
int *p,*q;
p=new int; //xin cấp phát vùng nhớ kiểu int
q=new int[10]; //xin cấp phát 10 vùng kiểu int
…. //sử dụng các biến động ở đây
delete p; //trả lại vùng nhớ cho hệ thống
delete [ ]q; //trả lại vùng nhớ cho hệ thống
2. Con trỏ và kiểu dữ liệu động
Biến động
9/16/2008 T.P.Tuấn - LTC 11
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 12
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 13
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 14
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 15
2. Con trỏ và kiểu dữ liệu động
int x;
int *p, *q;
p=&x;
q=&x;
9/16/2008 T.P.Tuấn - LTC 16
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 17
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 18
2. Con trỏ và kiểu dữ liệu động
9/16/2008 T.P.Tuấn - LTC 19
2. Con trỏ và kiểu dữ liệu động
Ví dụ về việc xin cấp phát biến động: 
#include 
void main()
{
int *p;
p=new int; //xin cấp phát 1 vùng nhớ
*p=4;
printf(“Gia tri cua vung nho do p quan ly: %d”, *p);
delete p; //trả lại vùng nhớ sau khi đã sử dụng xong
}
9/16/2008 T.P.Tuấn - LTC 20
3. Cấu trúc và con trỏ
#include 
typedef struct PHANSO
{
int tu, mau;
}PHANSO; 
void main()
{
PHANSO x;
x.tu=3;x.mau=8;
printf(“%d/%d”,x.tu,x.mau);
PHANSO *a;
a=new PHANSO;
a->tu=5; // (*a).tu=5;
a->mau=7; // (*a).mau=7;
printf(“Phan so: %d/%d”,a->tu,a->mau);
delete a;
}
9/16/2008 T.P.Tuấn - LTC 21
4. Danh sách liên kết
 Mảng là một hình thức liên kết ngầm
 Các phần tử trong mảng được cấp phát vùng 
nhớ một cách liên tiếp nhau
 Với T là kiểu dữ liệu cho trước, xét mảng các 
phần tử kiểu T. Ta có: 
Address(i)=Address(0)+(i-1)*sizeoof(T). 
20459
43210
9/16/2008 T.P.Tuấn - LTC 22
4. Danh sách liên kết
 Có nhiều loại danh sách liên kiết như: 
 Danh sách liên kết đơn
 Danh sách liên kết kép
 Danh sách liên kết vòng
 ….
 Trong môn này ta tìm hiểu kỹ về danh 
sách liên kết đơn
9/16/2008 T.P.Tuấn - LTC 23
4. Danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 24
4. Danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 25
4. Danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 26
4. Danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 27
4. Danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 28
4. Danh sách liên kết đơn
 Tạo danh sách
 Khai báo danh sách liên kết
 Khởi tạo danh sách liên kết
 Tạo mới một phần tử để thêm vào danh sách liên kết
 Thêm vào đầu danh sách
 Thêm vào cuối danh sách
 Xuất dữ liệu của toàn bộ danh sách liên kết
 Thêm vào sau một phần tử cho trước
 Tìm kiếm
 Tìm một phần tử có khóa cho trước
 Tìm một phần tử đứng trước một phần tử cho trước
 Hủy danh sách
 Hủy một phần tử đầu danh sách
 Hủy một phần tử cuối danh sách
 Hủy một phần tử sau một phần tử cho trước
 Hủy một phần tử có khóa cho trước
 Hủy toàn bộ danh sách
9/16/2008 T.P.Tuấn - LTC 29
4. Danh sách liên kết đơn
typedef struct NODE
{
int data; // 2 byte (dos)
NODE* next; // 2 byte (dos)
}NODE;
typedef struct LIST
{
NODE* pHead;
NODE* pTail;
}LIST;
Khai báo danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 30
4. Danh sách liên kết đơn
void KhoiTao(LIST &l)
{
l.pHead=NULL;
l.pTail=NULL;
}
Khởi tạo danh sách liên kết
Việc khởi tạo danh sách liên kết nhằm xác định 
danh sách ban đầu mới tạo ra là rỗng
9/16/2008 T.P.Tuấn - LTC 31
4. Danh sách liên kết đơn
NODE* GetNode(int x)
{
NODE* p;
p=new NODE;
p->next=NULL;
p->data=x;
return p;
}
Tạo mới một phần tử để thêm vào danh sách
9/16/2008 T.P.Tuấn - LTC 32
4. Danh sách liên kết đơn
Thêm một phần tử vào đầu danh sách liên kết
1. Danh sách rỗng
2. Danh sách đã có phần tử
9/16/2008 T.P.Tuấn - LTC 33
4. Danh sách liên kết đơn
void AddHead(LIST &l, NODE* add)
{
if(l.pHead==NULL)
{
l.pHead=l.pTail=add;
}
else
{
add->next=l.pHead;
l.pHead=add;
}
}
Thêm một phần tử vào đầu danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 34
4. Danh sách liên kết đơn
Thêm một phần tử vào cuối danh sách liên kết
1. Danh sách rỗng
2. Danh sách đã có phần tử
9/16/2008 T.P.Tuấn - LTC 35
4. Danh sách liên kết đơn
void AddTail(LIST &l, NODE* add)
{
if(l.pHead==NULL)
{
l.pHead=l.pTail=add;
}
else
{
l.pTail->next=add;
l.pTail=add;
}
}
Thêm một phần tử vào cuối danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 36
4. Danh sách liên kết đơn
void PrintfList(LIST l)
{
NODE* p;
p=l.pHead;
while(p!=NULL)
{
printf(“-->%d”,p->data);
p=p->next;
}
}
Xuất dữ liệu của danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 37
4. Danh sách liên kết đơn
Thêm một phần tử vào sau một phần tử cho trước
1. Danh sách rỗng
2. Danh sách đã có phần tử
q
9/16/2008 T.P.Tuấn - LTC 38
4. Danh sách liên kết đơn
void AddAfter(LIST &l, NODE* q, NODE* add)
{
if(q!=NULL)
{
add->next=q->next;
q->next=add;
if(q==l.pTail)
l.pTail=add;
}
else
{
AddHead(l,add);
}
}
Thêm một phần tử vào sau một phần tử cho trước
9/16/2008 T.P.Tuấn - LTC 39
4. Danh sách liên kết đơn
Tìm một phần tử trong danh sách liên kết khi biết khóa (data)
Sử dụng 1 con trỏ phụ p để duyệt tất cả
các phần tử trong danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 40
4. Danh sách liên kết đơn
NODE* Search(LIST l, int data)
{
NODE* p=l.pHead;
while((p!=NULL) && (p->data!=data))
p=p->next;
return p;
}
Tìm một phần tử trong danh sách liên kết khi biết khóa (data)
Kết quả trả về là NULL tức là không tìm thấy phần tử có khóa data
Ngược lại nếu tìm thấy thì nó sẽ trả về địa chỉ của phần tử đầu tiên 
có khóa data trong danh sách liên kết. 
9/16/2008 T.P.Tuấn - LTC 41
4. Danh sách liên kết đơn
NODE* SearchPre(LIST l, NODE* s)
{
NODE* p=l.pHead;
while((p!=NULL) && (p->next!=s))
p=p->next;
return p;
}
Tìm một phần tử đứng trước một phần tử cho trước
9/16/2008 T.P.Tuấn - LTC 42
4. Danh sách liên kết đơn
Hủy phần tử đầu trong danh sách liên kết
1. Tách phần tử đầu ra khỏi danh sách
2. Xóa phần tử này
9/16/2008 T.P.Tuấn - LTC 43
4. Danh sách liên kết đơn
void RemoveHead(LIST &l)
{
if(l.pHead!=NULL)
{
p=l.pHead;
l.pHead=l.pHead->next;
delete p;
if(l.pHead==NULL)
l.pTail=NULL;
}
} 
Hủy phần tử đầu trong danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 44
4. Danh sách liên kết đơn
Hủy phần tử cuối trong danh sách liên kết
1. Tách phần tử cuối ra khỏi danh sách
2. Gán pTail = địa chỉ của phần tử kế cuối
3. Xóa phần tử này
9/16/2008 T.P.Tuấn - LTC 45
4. Danh sách liên kết đơn
void RemoveTail(LIST &l)
{
if(l.pHead==NULL)
return;
NODE *p=l.pTail;
l.pTail=SearchPre(l,l.pTail);
delete p;
if(l.pTail!=NULL)
l.pTail->next=NULL;
else
l.pHead=NULL;
} 
Hủy phần tử cuối trong danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 46
4. Danh sách liên kết đơn
Hủy phần tử sau phần tử q trong danh sách liên kết
1. Tách phần tử p ra khỏi danh sách liên kết
2. Xóa phần tử này
q
9/16/2008 T.P.Tuấn - LTC 47
4. Danh sách liên kết đơn
void RemoveAfter(LIST &l, NODE* q)
{
NODE* p;
if(q!=NULL)
{
p=q->next;
if(p!=NULL)
{
if(p==l.pTail)
l.pTail=q;
q->next=p->next;
delete p;
}
}
else
RemoveHead(l);
} 
Hủy phần tử sau phần tử q trong danh sách liên kết
Lưu ý: q là phần tử trong 
danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 48
4. Danh sách liên kết đơn
Hủy phần tử có khóa k cho trước
1. Tìm phần tử p có khóa k và phần tử q trước nó
2. Tách phần tử p ra khỏi danh sách liên kết
3. Xóa nó
q
K=39
9/16/2008 T.P.Tuấn - LTC 49
4. Danh sách liên kết đơn
void Remove (LIST &l, int k)
{
NODE* p=l.pHead,*q=NULL;
while((p!=NULL)&&(p->data!=k))
{
q=p; p=p->next;
}
if(p==NULL) return;
if(q!=NULL)
{
if(p==l.pTail)
{
l.pTail=q;
l.pTail->next=NULL;
}
q->next=p->next;
delete p;
}
else // p là phần tử đầu tiên (pHead)
RemoveHead(l);
}
Hủy phần tử có khóa k cho trước
9/16/2008 T.P.Tuấn - LTC 50
4. Danh sách liên kết đơn
Cách 1: 
void RemoveList (LIST &l, int k)
{
while(l.pHead!=NULL)
RemoveHead(l);
}
Cách 2: 
void RemoveList (LIST &l)
{
while(l.pHead!=NULL)
{
p=l.pHead;
l.pHead=l.pHead->next;
delete p;
}
l.pTail=NULL;
}
Hủy toàn bộ danh sách liên kết
9/16/2008 T.P.Tuấn - LTC 51
5. Sắp xếp trên danh sách liên kết
void ListSelectionSort (LIST &l)
{ 
NODE* min; //trỏ đến pt có data min
NODE* i,*j; 
for(i = l.pHead;i->next!=NULL;i=i->next)
{
min=i;
for(j=i->next;j!=NULL;j=j->next)
if(j->datadata)
min=j;
HoanVi(min->data,i->data);
}
}
Selection Sort – Hoán vị nội dung phần dữ liệu (data)
9/16/2008 T.P.Tuấn - LTC 52
5. Sắp xếp trên danh sách liên kết
void ListSelectionSort (LIST &l)
{ 
NODE *i,*j,*min, *minpre=NULL;
LIST lresult;KhoiTao(lresult);
while(l.pHead!=NULL) //danh dách chưa hết
{
min=l.pHead;minpre=NULL;
for(j=min,i=min->next;i!=NULL;j=i,i=i->next)
if(i->datadata)
{
min=i;
minpre=j;
}
if(minpre==NULL)
{
l.pHead=l.pHead->next;if(min==l.pTail) l.pTail=NULL;
}
else
{
if(min==l.pTail) l.pTail=minpre;minpre->next=min->next;
}
min->next=NULL;
AddTail(lresult,min);
}
l=lresult;
}
Selection Sort – Thay đổi mối liên kết
1. Tìm pt min có data nhỏ nhất
2. Tách min ra khỏi danh sách
3. Thêm min vào đầu ds mới
9/16/2008 T.P.Tuấn - LTC 53