Bài giảng Cấu trúc dữ liệu và giải thuật - Danh sách - Nguyễn Văn Linh

nt = 0; }11Danh sách tuyến tính – Xác định số phần tử của danh sách Xây dựng hàm Length:Input : Danh sách LOutput: Số phần tử của danh sáchlong Length(List L){ return L.count; }12Danh sách tuyến tính – Kiểm tra danh sách đầy Xây dựng hàm isFull:Input : Danh sách LOutput: 1: Danh sách đầy0: Danh sách chưa đầyint isFull(List L){ if (L.count = = max) return 1; else return 0; }13Danh sách tuyến tính – Kiểm tra danh sách rỗng Xây dựng hàm isEmpty:Input : Danh sách LOutput: 1: Danh sách rỗng0: Còn phần tử trong danh sáchint isEmpty(List L){ if (L.count = = 0) return 1; else return 0; }14Danh sách tuyến tính – Loại bỏ phần tử ở vị trí thứ p trong danh sách 48335101264831012615Danh sách tuyến tính – Loại bỏ phần tử ở vị trí thứ p trong danh sách Thuật toán:Bước 1:Thực hiện kiểm tra nếu danh sách không rỗng và p chỉ vào một phần tử trong danh sách thì thực hiện bước 2, ngược lại thì dừng.Bước 2: Ta tịnh tiến các phần tử ở các vị trí p+1, p+2,đến các vị trí p,p+1 (tịnh tiến lên một vị trí)16Danh sách tuyến tính – Loại bỏ phần tử ở vị trí thứ p trong danh sách Xây dựng hàm DeleteInput:Danh sách L Vị trị phần tử cần xoá pTham biến q cho biết việc xoá có thành công hay không? Output:q =1 nếu việc xoá thành côngq = 0 nếu việc xoá không thành công17Danh sách tuyến tính – Loại bỏ phần tử ở vị trí thứ p trong danh sách void Delete(List &L, long p, int &q){int i;q = 0;if (p=p+1){	L.element[i] = L.element[i-1];	i--; } 22Danh sách tuyến tính – Chèn phần tử x vào danh sách sau vị trí p L.element[p] = x;L.count = L.count +1;q =1; }}23Danh sách tuyến tính – Chèn phần tử x vào danh sách trước vị trí p 48335101265048310126355024Danh sách tuyến tính – Chèn phần tử x vào danh sách trước vị trí p Thuật toán:Bước 1:Thực hiện kiểm tra nếu danh sách chưa đầy và p chỉ vào một phần tử trong danh sách thì thực hiện bước 2, ngược lại thì dừng.Bước 2: Ta tịnh tiến các phần tử ở các vị trí L.count, L.count -1,đến các vị trí L.count +1,L.count Bước 3: Chèn phần tử x vào vị trí p25Danh sách tuyến tính – Chèn phần tử x vào danh sách trước vị trí p Xây dựng hàm InsertBeforeInput:Danh sách L Vị trị pPhần tử x thuộc kiểu Item cần chèn Tham biến q cho biết việc chèn có thành công hay không? Output:q =1 nếu việc chèn thành côngq = 0 nếu việc chèn không thành công26Danh sách tuyến tính – Chèn phần tử x vào danh sách trước vị trí p void InsertBefore(List &L, long p,Item x, int &q){int i;q = 0;if (!isFull(L) && (p p){	L.element[i] = L.element[i-1];	i--; } 27Danh sách tuyến tính – Chèn phần tử x vào danh sách trước vị trí p L.element[p] = x;L.count = L.count +1;q =1; }}28Danh sách tuyến tính – Tìm kiếm phần tử x trong danh sách Ta sử dụng phương pháp tìm kiếm tuần tự xây dựng hàm SearchInput:Danh sách LPhần tử xTham biến found cho biết có tìm được hay không?Tham biến p cho biết vị trí của phần tử x trong danh sách nếu x có trong danh sách 29Danh sách tuyến tính – Tìm kiếm phần tử x trong danh sách (tiếp)Output:Found:1: nếu có x trong danh sách0: nếu không có x trong danh sáchP:Nếu found =1 p trả lại vị trí của x trong danh sáchNếu found =0, p =0;30Danh sách tuyến tính – Tìm kiếm phần tử x trong danh sách (tiếp)void Search(List &L, item x, int &found, long &p){	found=0;p=1;	while((!found) && (p0 then	Free:=Node[Free].Next;	else	 writeln(“Vùng lưu trữ rỗng”);	 End;49Chỉ sốDataNext1A02?33?44?55?66?77?88?0Free =2List =150Chỉ sốDataNext1A02B13?44?55?66?77?88?0Free =3List =251Danh sách liên kết – Cài đặt trên cơ sở mảng Xây dựng hàm ReleaseNode giải phóng một nút được trỏ bởi pprocedure ReleaseNode (P: PointerType);	Begin	Node[P].Next := Free;	Free :=P;	End; 52Chỉ sốDataNext1A32B03?44?55?66?77?88?0List =2Free =153Danh sách liên kết – Cài đặt trên cơ sở mảng Hàm tạo danh sách rỗngprocedure Create (var List: PointerType);	Begin	List:=0;	End;54Danh sách liên kết – Cài đặt trên cơ sở mảng Kiểm tra danh sách rỗngInput : Danh sách ListOutput: 1: Nếu List rỗng0: List đã có phần tửFunction isEmpty(List: PointerType):boolean;	Begin	isEmpty:= (List = 0);	End;55Danh sách liên kết – Cài đặt trên cơ sở mảng Chèn một phần tử vào danh sách:Chèn vào đầu danh sáchChèn vào sau một phần tử cho trước trong danh sách56Danh sách liên kết – Cài đặt trên cơ sở mảng Chèn vào đầu danh sách:ListTempListTemp57Danh sách liên kết – Cài đặt trên cơ sở mảng Chèn vào sau một nút chỉ bởi PrevPtr:PrevPtrTempPrevPtrTemp58Danh sách liên kết – Chèn phần tử vào danh sách Thuật toán chèn Item vào danh sách với nút đầu chỉ bởi List. PrevPtr chỉ đến nút đứng trước cần chèn.1. GetNote(Temp) // Lấy một nút mới2. Đặt Data(Temp) bằng Item3. Nếu PrevPtr = 0 làm các bước sau:Đặt Next(Temp) bằng ListĐặt List bằng Temp59Danh sách liên kết – Cài đặt trên cơ sở mảng Else làm các bước sau:Đặt Next(Temp) bằng Next(PrevPtr)Đặt Next(PrevPtr) bằng Temp	60Danh sách liên kết – Chèn phần tử vào danh sách Procedure Insert(var L : PointerType,element : Item, PrevPtr: PointerType);	Var Temp: PointerType;	Begin	GetNode(Temp); Node[Temp].Data := element;	if PrevPtr = 0 then 	 begin	Node[Temp].Next := L; L:= Temp;	 end;	else begin	Node[Temp].Next := Node[PrevPtr].Next	Node[PrevPtr].Next = Temp;	end;	End;61Danh sách liên kết – Xoá phần tử khỏi danh sách Thuật toán xoá nút từ danh sách với nút đầu chỉ bởi List. PrevPtr chỉ đến nút đứng trước nút cần xoá.1. Nếu danh sách không rỗng thực hiện các bước:Nếu PrevPtr = 0 Đặt Temp bằng List;Đặt List bằng Next(Temp).Else làm các bước:Đặt Temp bằng Next(PrevPtr)Đặt Next(PrevPtr) bằng Next(Temp)2. ReleaseNote(Temp)62Danh sách liên kết – Xoá phần tử khỏi danh sách Procedure Delete(var L: PointerType, PrevPtr: PointerType){	var Temp : PointerType;	Begin	if isEmpty(L) then halt	else	begin	if (PrevPtr = 0) then 	begin	Temp := L;	 	L := Node[Temp].Next;	end	63Danh sách liên kết – Xoá phần tử khỏi danh sách 	else	begin	Temp:= Node[PrevPtr].Next; 	Node[PrevPtr].Next := Node[Temp].Next;	end;	 ReleaseNode(Temp);	 end;End;64Danh sách liên kết – Tìm kiếm một phần tử trong danh sáchTìm phần tử x trong danh sách liên kết có nút đầu tiên được chỉ bởi List. Procedure Search(List : PointerType,x:Item, var PrevPtr : PointerType, var found : boolean);List : Con trỏ đến phần tử đầu tiênX : Phần tử cần tìmPrevPtr : Con trỏ chỉ đến phần tử đứng trước phần tử cần tìm hay là 0 nếu không tìm thấyFound : True nếu tìm thấy x trong danh sáchFalse nếu không tìm thấy x trong danh sách65Danh sách liên kết – Tìm kiếm một phần tử trong danh sách (tiếp)Procedure Search(List : PointerType; x: Item; var PrevPtr: PointerType; var found : boolean); 	var CurrPtr : PointerType;	Begin	found := false; CurrPtr:= List;PrevPtr := 0;	while(( not found) and (CurrPtr0)) do	begin	if Node[CurrPtr].Data = Item then found:=True;	else begin	PrevPtr:= CurrPtr;	CurrPtr:=Node[CurrPtr].Next;	 end;	end;	End;66Kiểu con trỏKiểu biến con trỏ dùng để tham chiếu đến vùng nhớ đang lưu trữ một dữ liệu nào đó.Biến con trỏ có giá trị là địa chỉ của vùng nhớKiểu con trỏ được khai báo:^ định danh kiểuTrong đó định danh kiểu đặc tả kiểu của dữ liệu.Ví dụ :Type Pointer = ^Node;Node = record	Data : ItemType;	Next: Pointer;	end;67Kiểu con trỏ (tiếp) Type 	String = array[1..8] of char;	PointerType = ^String;Var StringPtr: PointerType;Trên đây khai báo biến con trỏ StringPtr.Để cấp phát một vùng nhớ cho biến con trỏ sử dụng lệnh new(Tên biến con trỏ): new(StringPtr) sẽ gán địa chỉ vùng nhớ cho con trỏ StringPtr 68Kiểu con trỏ (tiếp) 1000 COMPUTERBộ nhớStringPtr100069Kiểu con trỏ (tiếp) Con trỏ StringPtr trỏ đến vùng nhớ có địa chỉ 1000 và lưu xâu ký tự “COMPUTER”Mỗi tham chiếu của thủ tục new đòi hỏi một vùng nhớ mới và gán địa chỉ của nó cho con trỏ. 1000 COMPUTERBộ nhớStringPtr100070Kiểu con trỏ (tiếp) Trong Pascal có con trỏ hằng đặc biệt nil dùng khi cần thiết phải gán một giá trị nào đó cho biết con trỏ để chỉ ra rằng nó không chỉ đến một vùng nhớ nào cả.Giá trị này có thể gán cho một con trỏ kiểu bất kỳ trong lệnh gán : Biến_con _trỏ := nill;Vì giá trị của con trỏ là địa chỉ vùng nhớ, chỉ có các phép gán ,so sánh =, .Nếu hai biến con trỏ Pointer1 và Pointer2 cùng kiểu dữ liệu thì lệnh gán Pointer1 := Pointer2 gán giá trị của pointer2 cho pointer1 điều đó có nghĩa hai con trỏ đều chỉ đến một vùng nhớ.71Kiểu con trỏ (tiếp) Vd: Pointer1 và Pointer2 cùng kiểu StringCOMPUTERPointer1MAYTINHPointer2Khi thực hiện lệnh Pointer1:= Pointer2;COMPUTERPointer1MAYTINHPointer272Kiểu con trỏ (tiếp) Để gán giá trị cho biến con trỏ ta dùng:Biến_con_trỏ ^:= Giá trị;Ví dụ: Biến con trỏ StringPtr có giá trị khác rỗng và có kiểu dữ liệu String. Khi đó ta có thể gán gía trị cho biến con trỏ này bằng lệnh:StringPtr^:= “COMPUTER”;Nếu hai biến con trỏ TempPtr, StringPtr cùng kiểu và khác rỗng khi đó ta có thể gán:TempPtr^:= StringPtr^;Khi đó TempPtr^ bằng “COMPUTER”73Kiểu con trỏ (tiếp) Nếu vùng nhớ chỉ bởi con trỏ không cần thiết nữa, nó có thể được giải phóng bởi thủ tục disposeDispose(Biến_con_trỏ)74Xây dựng danh sách liên kết trên cơ sở con trỏType	PointerType =^Node;	Node = record	Data : Item;	Next: PointerType;	end;Var List :PointerType; (* Con trỏ chỉ đến nút đầu tiên trong danh sách liên kết*) 75Xây dựng danh sách liên kết trên cơ sở con trỏ (tiếp)Tạo danh sách rỗngProcedure Create (var List: PointerType);Begin	List: =nil;End;76Xây dựng danh sách liên kết trên cơ sở con trỏ (tiếp)Kiểm tra danh sách rỗng?Function isEmpty (List: PointerType): boolean;Begin	isEmpty :=(List =nil);End;77Danh sách liên kết – Chèn phần tử vào danh sách Procedure Insert(var L : PointerType,element : Item, PrevPtr: PointerType);	Var Temp: PointerType;	Begin	new(Temp); Temp^.Data := element;	if PrevPtr = nil then 	 begin	Temp^.Next := L; L:= Temp;	 end;	else begin	Temp^.Next := PrevPtr^.Next	PrevPtr^.Next = Temp;	end;	End;78Danh sách liên kết – Xoá phần tử khỏi danh sách Procedure Delete(var L: PointerType, PrevPtr: PointerType){	var Temp : PointerType;	Begin	if isEmpty(L) then halt	else	begin	if (PrevPtr = nil) then 	begin	Temp := L;	 	L := Temp^.Next;	end	79Danh sách liên kết – Xoá phần tử khỏi danh sách 	else	begin	Temp:= PrevPtr^.Next; 	PrevPtr^.Next := Temp^.Next;	end;	 dispose(Temp);	 end;End;80