Giáo trình môn Cấu trúc dữ liệu và giải thuật (Phần 2)

If Kt_nt(A[i]) then dem := dem +1; return dem; End; b. Bổ sung phần tử vào dãy đã sắp xếp Procedure Bosung(A, n, x) {Bổ sung phần tử có giá trị bằng x vào dãy A đã được sắp xếp không giảm dần} Begin n := n+1; i := n; while (i>1) and (A[i-1]>x) do Begin A[i] := A[i-1]; i := i-1; End; A[i] := x; End; c. Loại bỏ phần tử trong dãy để dãy không có hai phần tử có giá trị bằng nhau Procedure Thanh_loc( A, n) Begin i := 1; while i <n do Begin j := i+1; while ( j  n) do if A[j] = A[i] then Begin for k := j to n-1 do A[k] := A[k+1]; n := n-1; End; else j := j+1; i := i+1; End; End; d. Tìm phần tử xuất hiện nhiều nhất Function Tim(A, n) {Hàm tìm phần tử xuất hiện nhiều nhất trong dãy A} Begin dm :=0; for i:= 1 to n-1 do Begin d :=0; for j :=i+1 to n do if A[i]=A[j] then d := d+1; if d > dm then Begin dm := d; pt := A[i]; End; return pt; End; e. Tìm vị trí xuất hiện đầu tiên và vị trí xuất hiện cuối cùng của số lớn nhất Procedure Tim_vt(A, n) Begin start := 1; finish := 1; for i := 2 to n do if A[i]> A[start] then start := i else if A[i]=A[start] then finish := i; writeln('So lon nhat xuat hien o:'); writeln('Vi tri dau tien:', start); writeln('Vi tri cuoi cung:', finish); End; f. Tìm tất cả các phần tử lớn hơn tổng các phần tử đứng trước nó Procedure Tim_pt(A, n) Begin S := A[1]; k := 1; B[k] := 1; for i:=2 to n do Begin if S < A[i] then Begin k := k+1; B[k] := i; End; S := S+A[i]; End; writeln(' Cac phan tu lon hon tong cac phan tu dung truc no:'); for j := 1 to k do write(A[B[j]]:5); End; g. Tìm vị trí của phần tử đầu tiên bằng một phần tử bất kỳ đứng trước nó trong dãy. Function Tim_vt_pt(A, n) Begin vitri := 0; i := 2; while(i  n) and (vitri = 0) do Begin j := 1; while (j < i) and (vitri = 0) do if A[i] = A[j] then vitri := i else j := j+1; i := i+1; End; return vitri End; h. Tìm ước số chung lớn nhất của các phần tử trong dãy Function USCLN( A, n) { Tìm ước số chung lớn nhất của các phần tử trong dãy} Begin x := USC(A[1], A[2]); for i :=3 to n do Begin y := USC(x, A[i]); x := y; End; return x; End; i. Tìm số lớn thứ nhì Function Max_2( A, n) Begin i := 1; while(i<n) and (A[i]=A[i+1]) do i := i+1; if (i < n) then Begin if A[i] < A[i+1] then Begin M1 := A[i+1]; M2 := A[i]; End; else Begin M1 := A[i]; M2 := A[i+1]; End; for j := i+2 to n do if A[j] > M1 then Begin M2 := M1; M1 := A[j]; End; else if A[j] > M2 then M2 := A[j]; return M2; End; else write(' Khong co so lon thu nhi'); End; 14. Cho một danh sách nối đơn nút đầu trỏ bởi L, mỗi nút trong danh sách lưu trữ thông tin một điểm trong mặt phẳng. Viết các giải thuật thực hiện các công việc sau: a. Tạo danh sách b. Hiển thị danh sách c. Đếm số điểm trong danh sách d. Tìm khoảng cách xa nhất từ các điểm trong danh sách đến gốc toạ độ e. Sắp xếp danh sách theo chiều tăng dần của khoảng cách từ điểm đến gốc toạ độ f. Bổ sung điểm có toạ độ nhập từ bàn phím sao cho danh sách vẫn đảm bảo tính sắp xếp. g. Xoá khỏi danh sách điểm có toạ độ trùng với gốc toạ độ h. Tách ra khỏi danh sách L, danh sách những điểm nằm trên một trục toạ độ nào đó và cho P trỏ vào đầu danh sách đó. Giải: a. Tạo danh sách Procedure Taods(L) Begin L = null; repeat new(p); read(info(p).x); read(info(p).y); link(p) = null; if L = null then L = p else begin link(p) = L; L = p; end; until.. end; b. Hiển thị danh sách Procedure HT(L) Begin p = L; while p ≠ null do begin write(info(p).x,info(p).y); p = link(p) end; end; c. Đếm số điểm trong danh sách Function Dem_nut(L) Begin dem = 0; p = L; while p ≠ null do begin dem = dem +1; p = link(p) end; return dem; end; d. Tìm khoảng cách xa nhất từ các điểm đến gốc toạ độ Function KC_max(L) Begin If L = null then write(„Danh sach rong‟); Else Begin Max := sqrt(info(L).x*info(L).x+info(L).y*info(L).y); p = link(L); while (p ≠ null) do begin kc := sqrt(info(p).x*info(p).x+info(p).y*info(p).y); if max > kc then max := kc; p = link(p); end; return max; end; e. Sắp xếp danh sách điểm theo thứ tự tăng dần khoảng cách từ điểm đến gốc toạ độ Procedure Sapxep( L) Begin If (L = null) or (link(L)=null) then return Else begin p = L; while (link(p) ≠ null) do begin q = link(p); kc1 := sqrt(info(p).x*info(p).x+info(p).y*info(p).y); while q ≠ null do begin kc2 := sqrt(info(q).x*info(q).x+info(q).y*info(q).y); if kc1 > kc2 then begin tg := info(p); info(p) := info(q); info(q):=tg; end; q := link(q); end; p := link(p); end; end; end; f. Bổ sung một điểm mới vào danh sách sao cho vẫn đảm bảo tính sắp xếp Procedure Bo_sung_vao_sau( L, a, b) Begin new <= AVAIL; Info(new).x := a; Info(new).y :=b; Link(new) := null; p := L; kc := sqrt(a*a+b*b); while (p ≠ null) and ( kc > sqrt(info(p).x*info(p).x+info(p).y*info(p).y)) do begin q := p; p := link(p); end; if p = L then begin link(new) := L; L:= new; End else begin link(new) :=p; link(q) := new; end; end; g. Loại bỏ điểm có toạ độ trùng với gốc toạ độ Procedure Loai_bo( L) Begin if (L = null) then return else if (info(L).x=0) and (info(L).y=0) then begin q:= L; L := link(L); q=>Avail; End else begin q := L; p = link(L); while (p ≠ null) do begin if (info(p).x=0) and (info(p).y=0) then begin link(q):=link(p); p=>Avail; p := link(q); end else begin q := link(q); p = link(p); end; end; end; end; h. Tách danh sách Procedure Tach( L, P) Begin P := null; if (L = null) then return else begin while (L ≠ null) and ((info(L).x=0) or (info(L).y=0)) then begin q := L; L := link(L); link(q):= P; P := q; End; r:= L; q = link(L); while (q ≠ null) do begin if (info(q).x=0) or (info(q).y=0) then begin link(r) := link(q); link(q):= P; P := q; q := link(r); end else begin q := link(q); r := link(r); end; end; end; end; 15. Viết các giải thuật thực hiện các công việc sau trên danh sách nối kép có nút cực trái và nút cực phải lần lượt được trỏ bởi L và R: a. Tạo danh sách. b. Đếm số nút có trong danh sách. c. Tìm tới nút thứ k trong danh sách, nếu có nút thứ k thì cho ra địa chỉ nút đó, nếu không thì cho ra địa chỉ null. d. Bổ sung một nút có info = x vào sau nút thứ k. e. Loại bỏ nút đứng trước nút thứ k. Giải: a. Tạo danh sách Procedure Create(L, R) Begin L := R := null; repeat P <= Avail; Read(Info(P)); if L = null then begin L := R := P; LPTR(P) := RPTR(P) := null; end else begin RPTR(R) := P; LPTR(P) := R; R := P; RPTR(R) := null ; end; until End; b. Đếm số nút trong danh sách Function Dem_nut(L, R) Begin P:= L; Dem :=0; While P  null do Begin Dem := Dem +1; P := RPTR(P); End; Return Dem; End; c. Tìm tới nút thứ k Function Search(L, R, k) {Tìm nút thứ k trong danh sách nối kép có nút cực trái và cực phải lần lượt được trỏ bởi các con trỏ L và R} Begin if L = null then return null else Begin dem := 1; P := L; while (P  null) and (dem < k) do P := RPTR(P); return P; End; End; d. Bổ sung một nút có info = x vào sau nút thứ k. Procedure Add(L, R, k, x) { Bổ sung nút có Info = x vào sau nút thứ k trong danh sách nối kép có nút cực trái và cực phải lần lượt được trỏ bởi các con trỏ L và R} Begin P := Search(L, R, k); New <= Avail; Info(New) := x; LPTR(New) := RPTR(New) := null; if (P = null) then if L = null then L := R := New else Begin write('Khong bo sung'); return ; End else if P = R then {Bổ sung vào cuối- thành nút cực phải} Begin RPTR(R) := New; LPTR(New) := R; R := New; End; else {Bổ sung vào giữa} Begin RPTR(New) := RPTR(P); LPTR(New) := P; LPTR(RPTR(P)) := New; RPTR(P) := New; End; End; e. Loại bỏ nút đứng trước nút thứ k. Procedure Remove(L, R, k) { Loại bỏ nút đứng trước nút thứ k trong danh sách nối kép có nút cực trái và cực phải lần lượt được trỏ bởi các con trỏ L và R} Begin P := Search(L, R, k); if (P = null) or (P = L) then Begin write('Khong co nut loai bo'); return ; End else Begin Q := LPTR(P); if Q = L then {Loại bỏ nút cực trái} Begin L := RPTR(L); LPTR(L) := null; End else {Loại bỏ nút ở giữa} Begin RPTR(LPTR(Q)) := RPTR(Q);LPTR(RPTR(Q)) := LPTR(Q); End; Q => Avail; End; End; 16. Cho cây nhị phân cài đặt kiểu móc nối, có nút gốc được trỏ bởi T. Viết các giải thuật thực hiện các công việc sau: a. Xác định số nút có trên cây. b. Xác định số nút lá. c. Xác định chiều sâu(cao) của cây. Giải: a. Xác định số nút có trên cây Function Count_node( T) { Đếm số nút trên cây nhị phân có nút gốc trỏ bởi T} Begin Dem := 0; if T  null then Begin TOP := 0; PUSH (S, TOP, T ); While TOP > 0 do Begin P : = POP (S, TOP); While P  null do Begin Dem := Dem +1; if RPTR (P)  null then PUSH (S, TOP, RPTR (P)) ; P : = LPTR(P); End; End; End; return Dem; End; b Xác định số nút lá cây Function Count_leaf( T) { Đếm số nút trên cây nhị phân có nút gốc trỏ bởi T} Begin Dem := 0; if T  null then Begin TOP := 0; PUSH (S, TOP, T ); While TOP > 0 do Begin P : = POP (S, TOP); While P  null do Begin If (LPTR (P) = null) and (RPTR (P) =null) then Dem := Dem +1; if RPTR (P)  null then PUSH (S, TOP, RPTR (P)) ; P : = LPTR(P); End; End; End; return Dem; End; c. Xác định chiều sâu(cao) của cây. Function Height( T) { Tìm chiều cao của cây nhị phân có nút gốc trỏ bởi T} Begin if T = null then return 0 else if Height(LPTR(T)) > Height(RPTR(T)) then return 1+ Height(LPTR(T)) else return 1+ Height(RPTR(T)); End; 17. Cho cây nhị phân có các nút được duyệt theo thứ tự trước và thứ tự giữa là: Duyệt trước: ABDHKECFG Duyệt giữa : HDKBEAFCG Hãy vẽ cây nhị phân đó. Giải: Từ thứ tự duyệt trước, ta xác định được gốc của cây là A. Từ thứ tự duyệt giữa ta xác định được: - Các nút thuộc cây con trái của cây nút gốc A gồm: Duyệt trước: BDHKE Duyệt giữa : HDKBE - Các nút thuộc cây con phải của cây nút gốc A gồm: Duyệt trước: CFG Duyệt giữa : FCG Thực hiện đệ quy đối với các cây con trái, con phải cho tới khi không còn nút nào ta thu được cây sau: 18. Cho dãy khóa: 30, 10, 25, 8, 40, 6, 17, 50, 35, 45. Vẽ cây nhị phân tìm kiếm ứng với dãy khóa trên. Giải: Theo nguyên tắc tổ chức của cây nhị phân tìm kiếm, mỗi khi bổ sung một nút vào cây ta cần so sánh khoá của nút đó với khoá của các nút có trên cây theo thứ tự từ gốc xuống và bổ sung nút mới vào vị trí thích hợp. Với nguyên tắc trên ta thu được cây nhị phân tìm kiếm như sau: 30, 10, 25, 8, 40, 6, 17, 50, 35, 45. A B C D E F G H K 30 10 40 8 25 45 50 6 17 19. Cho cây nhị phân tìm kiếm có nút gốc được trỏ bởi T. Viết các giải thuật thực hiện các công việc sau a. Tìm giá trị nhỏ nhất của các khoá trên cây b. Hiển thị dãy khoá trên cây theo thứ tự giá trị tăng dần Giải: a. Tìm giá trị nhỏ nhất của các khoá trên cây Theo nguyên tắc tổ chức của cây nhị phân tìm kiếm, ta nhận thấy, nếu cây không rỗng thì nút cực trái trên cây chính là nút chứa khoá có giá trị nhỏ nhất trong tất cả các giá trị khoá trên các nút còn lại. Vậy giải thuật tìm giá trị nhỏ nhất của các khoá trên cây có nút gốc trỏ bởi T như sau: Function Min(T) Begin If T = null then Begin Write(„Cay rong‟); return; End Else Begin P := T; While(LPTR(p) null) do p:= LPTR(p); Return Key(p); End; End; b. Hiển thị dãy khoá trên cây theo thứ tự giá trị tăng dần Procedure Hienthi(T ) {Thủ tục hiển thị dãy khoá trên cây theo thứ tự giá trị tăng dần} Begin if T = null then Begin write ( ' cây rỗng ') ; return; End ; else Begin TOP := 0; P := T; Repeat While P  null do Begin Push(S, TOP, P); P := LPTR(P); End; if TOP > 0 then Begin P : = POP (S, TOP); write(INFO(P)); P := RPTR(P); continue := true; End else continue := false; Until not continue; End; End; 20. Cho dãy khoá: 42 87 3 96 4 0 53 12 66. Cho biết kết quả 5 bước thực hiện sắp xếp đầu tiên dãy khoá trên theo giải thuật sắp xếp: a. Sắp xếp kiểu lựa chọn b. Sắp xếp kiểu thêm dần c. Sắp xếp kiểu nổi bọt d. Sắp xếp kiểu phân đoạn (sắp xếp nhanh) e. Sắp xếp kiểu vun đống Giải: a. Sắp xếp kiểu lựa chọn Ban đầu: 42 87 3 96 4 0 53 12 66 Bước 1: 0 87 3 96 4 42 53 12 66 Bước 2: 0 3 87 96 4 42 53 12 66 Bước 3: 0 3 4 96 87 42 53 12 66 Bước 4: 0 3 4 12 87 42 53 96 66 Bước 5: 0 3 4 12 42 87 53 96 66 b. Sắp xếp kiểu thêm dần Ban đầu: 42 87 3 96 4 0 53 12 66 Bước 1: 42 87 3 96 4 0 53 12 66 Bước 2: 3 42 87 96 4 0 53 12 66 Bước 3: 3 42 87 96 4 0 53 12 66 Bước 4: 3 4 42 87 96 0 53 12 66 Bước 5: 0 3 4 42 87 96 53 12 66 c. Sắp xếp kiểu nổi bọt Ban đầu: 42 87 3 96 4 0 53 12 66 Bước 1: 0 42 87 3 96 4 12 53 66 Bước 2: 0 3 42 87 4 96 12 53 66 Bước 3: 0 3 4 42 87 12 96 53 66 Bước 4: 0 3 4 12 42 87 53 96 66 Bước 5: 0 3 4 12 42 53 87 66 96 d. Sắp xếp kiểu phân đoạn Ban đầu: 42 87 3 96 4 0 53 12 66 Bước 1: (4 12 3 0) 42 (96 53 87 66) Bước 2: (3 0) 4 (12) 42 (96 53 87 66) Bước 3: (0) 3 4 (12) 42 (96 53 87 66) Bước 4: 0 3 4 (12) 42 (96 53 87 66) Bước 5: 0 3 4 12 42 (96 53 87 66) e. Sắp xếp kiểu vun đống * Cây ban đầu: * Cây sau khi vun thành đống 42 87 3 96 4 0 53 12 22 66 96 87 53 66 4 0 3 12 22 42 * Kết quả thực hiện 4 bước sắp xếp đầu tiên Bước 1. Dãy đã sắp: 96, kích thước của đống n = 8, đống chưa sắp: Bước 2. Dãy đã sắp: 87 96 , kích thước của đống n = 7, đống chưa sắp: Bước 3. Dãy đã sắp: 66 87 96, kích thước của đống n = 6, đống chưa sắp: Bước 4. Dãy đã sắp:53 66 87 96, kích thước của đống n = 5, đống chưa sắp: 21. Viết thuật toán sắp xếp ba số hạng đầu tiên của một dãy các số nguyên có chiều dài tuỳ ý theo thứ tự tăng dần. 22. Viết giải thuật tìm cả số lớn nhất và số nhỏ nhất trong dãy hữu hạn các số nguyên. 87 66 53 42 2 4 0 3 12 22 66 42 53 12 2 4 0 3 53 42 3 12 2 4 0 42 12 3 0 4 23. Viết thuật toán tìm từ dài nhất trong một câu tiếng Anh (từ là một xâu các chữ cái, còn câu là một bảng liệt kê các từ cách nhau một khoảng trống) 24. Viết giải thuật tìm kiếm tam phân xác định vị trí một phần tử trong dãy hữu hạn các số nguyên đã được sắp xếp theo thứ tự tăng dần. 25. Viết giải thuật tìm trong dãy hữu hạn các số nguyên số hạng đầu tiên bằng một số hạng nào đó đứng trước nó trong dãy. 26. Viết giải thuật tìm trong dãy hữu hạn các số nguyên tất cả các số hạng lớn hơn tổng tất cả các số hạng đứng trước nó trong dãy. MỘT SỐ CHƢƠNG TRÌNH CÀI ĐẶT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT BẰNG NGÔN NGỮ LẬP TRÌNH C 1. CHƢƠNG TRÌNH ĐỔI CƠ SỐ SỬ DỤNG STACK Chương trình đổi một số nguyên dương n từ hệ thập phân sang hệ đếm cơ số a, sử dụng Stack cài đặt kiểu kế tiếp (n và a nhập từ bàn phím). #include"conio.h" #include"stdio.h" #define max 100 char s[max]; int top; int full(char s[max],int top) { if(top>=max) return 1; else return 0; } int empty(char s[max],int top) { if(top<=0) return 1; else return 0; } void push(char s[max],int &top,char x) { if(full(s,top)==1) printf("\n stack day"); else { top++; s[top]=x; } } char pop(char s[max],int &top) { if(empty(s,top)==1) printf("\n stack rong"); else { top--; return(s[top+1]); } } void doics(int n,int a) { top=0; do { push(s,top,n%a); n=n/a; } while(n>0); while(empty(s,top)==0) printf("%X",pop(s,top)); } void main() { int a,n; clrscr(); printf("\n nhap he dem co so a="); scanf("%d",&a); printf("\n nhap vao so can doi:"); scanf("%d",&n); printf(“ %d o he dem co so %d la:”,n,a);doics(n,a); getch(); } 2. BIỂU DIỄN ĐA THỨC BẰNG DANH SÁCH NỐI ĐƠN Chương trình biểu diễn đa thức bậc n bằng danh sách nối đơn và thực hiện các phép toán sau: - Nhập đa thức từ bàn phím - Hiển thị đa thức ra màn hình - Tính giá trị đa thức - Nhân đa thức với một số - Rút gọn đa thức - Tính tổng hai đa thức - Tính hiệu hai đa thức - Tính tích hai đa thức - Tính đạo hàm bậc nhất, đạo hàm bậc hai của đa thức - Tìm nguyên hàm của đa thức - Tính tích phân xác định của đa thức #include"math.h" #include"stdio.h" #include"alloc.h" #include"conio.h" #include"stdlib.h" struct dt { int somu; float heso; dt*link; }; //Nhap da thuc dt *nhap() { dt *l,*p, *q; float hs; l=NULL; do { printf("\nHe so:"); scanf("%f",&hs); if (hs!=0) { p=(dt*)calloc(1,sizeof(dt)); p->heso = hs; printf("So mu:"); scanf("%d",&p->somu); p->link=NULL; if(l==NULL) l=p; else q->link=p; q = p; } }while(hs!=0); return(l); } //Hien thi da thuc void hienthi(dt *l) { dt *p; p = l; while(p!=NULL) { if((p->link!=NULL)&&((p->link)->heso>0)) printf("%5.2fx^%d+",p->heso,p->somu); else printf("%5.2fx^%d",p->heso,p->somu); p=p->link; } } //Tinh gia tri da thuc float Gia_tri(dt *l,float x) { dt *p; float value=0; p = l; while(p!=NULL) { value+=p->heso*pow( x,p->somu); p=p->link; } return value; } //Bo sung so hang dt *Bosung(dt *k, float hs, int sm) { dt *d; d=(dt*)calloc(1,sizeof(dt)); d->somu=sm; d->heso=hs; if(k==NULL) { k=d; k->link=NULL; } else { d->link=k; k=d; } return k; } //Cong hai da thuc dt *tong(dt*a,dt*b) { dt *p,*q,*c,*k; p=a; q=b; c=NULL; while((p!= NULL)&&(q!=NULL)) { if(p->somu==q->somu) { if((p->heso+q->heso)!=0) c=Bosung(c,p->heso+q->heso,p->somu); p=p->link; q=q->link; } else if(p->somu>q->somu) { c=Bosung(c,p->heso,p->somu); p=p->link; } else { c=Bosung(c,q->heso,q->somu); q=q->link; } } if(q==NULL) while(p!=NULL) { c=Bosung(c,p->heso,p->somu); p=p->link; } else while(q!=NULL) { c=Bosung(c,q->heso,q->somu); q=q->link; } return c; } //Tinh hieu hai da thuc dt *hieu(dt *a,dt *b) { dt *p,*q,*c,*k; p=a; q=b; c=NULL; while((p!= NULL)&&(q!=NULL)) { if(p->somu==q->somu) { if((p->heso-q->heso)!=0) c=Bosung(c,p->heso-q->heso,p->somu); p=p->link; q=q->link; } else if(p->somu>q->somu) { c=Bosung(c,p->heso,p->somu); p=p->link; } else { c=Bosung(c,-q->heso,q->somu); q=q->link; } } if(q==NULL) while(p!=NULL) { c=Bosung(c,p->heso,p->somu); p=p->link; } else while(q!=NULL) { c=Bosung(c,-q->heso,q->somu); q=q->link; } return c; } dt *tich(dt*a,dt*b) { dt *p,*q,*c,*k; p=a; c=NULL; while(p!= NULL) { q=b; while(q!=NULL) { k=c; while((k!=NULL)&&(k->somu!=p->somu+q->somu)) k=k->link; if(k!=NULL) k->heso=k->heso+p->heso*q->heso; else c=Bosung(c,p->heso*q->heso,p->somu+q->somu); q=q->link; } p=p->link; } return c; } //Dao ham bac nhat dt *Dao_ham(dt*a) { dt *p,*c; p=a; c=NULL; while(p!= NULL) { if(p->somu>0)c=Bosung(c,p->heso*p->somu,p->somu-1); p=p->link; } return c; } //Nguyen ham dt *Nguyen_ham(dt*a) { dt *p,*c; p=a; c=NULL; while(p!= NULL) { c=Bosung(c,p->heso/(p->somu+1),p->somu+1); p=p->link; } return c; } void main() { dt *a,*b,*c; int chon; float x; do { clrscr(); printf("\n1. Dao ham bac nhat"); printf("\n2. Nguyen ham"); printf("\n3. Tinh gia tri da thuc"); printf("\n4. Tong hai da thuc"); printf("\n5. Hieu hai da thuc"); printf("\n6. Tich hai da thuc"); printf("\n7. Ket thuc chuong trinh"); printf("\nChon chuc nang(1->7):"); scanf("%d",&chon); switch(chon) { case 1: printf("\nNhap da thuc can tinh:"); a=nhap(); b=Dao_ham(a); printf("\nDao ham cua da thuc la:");hienthi(b); getch(); break; case 2: printf("\nNhap da thuc can tinh:"); a=nhap(); b=Nguyen_ham(a); printf("\nNguyen ham cua da thuc la:");hienthi(b); getch(); break; case 3: printf("\nNhap da thuc can tinh:"); a=nhap(); printf("x=");scanf("%f",&x); printf("\nGia tri cua da thuc tai x=%5.2f la:%5.2f",x,Gia_tri(a,x)); getch(); break; case 4: printf("\nNhap da thuc thu nhat:"); a=nhap(); printf("\nNhap da thuc thu hai:"); b=nhap(); c=tong(a,b); printf("Tong hai da thuc la:");hienthi(c); getch(); break; case 5: printf("\nNhap da thuc thu nhat:"); a=nhap(); printf("\nNhap da thuc thu hai"); b=nhap(); c=hieu(a,b); printf("Hieu hai da thuc la:");hienthi(c); getch(); break; case 6: printf("\nNhap da thuc thu nhat:"); a=nhap(); printf("\nNhap da thuc thu hai"); b=nhap(); c=tich(a,b); printf("Tich hai da thuc la:");hienthi(c); getch(); break; case 7:exit(1); } }while (chon!=7); } 3. CÀI ĐẶT ĐA DANH SÁCH BIẺU DIỄN MA TRẬN THƢA Chương trình cài đặt cấu trúc đa danh sách biểu diễn ma trận thưa, nhập vào từ bàn phím 2 ma trận thưa, tính tích hai ma trận và in ma trận kết quả ra màn hình. Chƣơng trình minh hoạ #include #include #include struct node { node *left,*up; int v,r,c; }; node *arow[10],*acol[10],*brow[10],*bcol[10],*crow[10],*ccol[10]; struct mt { int m,n,k; }; void input(mt &A) { printf("So hang:");scanf("%d",&A.m); printf("So cot:");scanf("%d",&A.n); printf("So phan tu khac khong:");scanf("%d",&A.k); } void createA(mt A) { int i,value,row,col; node *p,*q; for(i=1;i<=A.m;i++) { arow[i]=(node*)calloc(1,sizeof(node)); arow[i]->c=0; arow[i]->left=arow[i]; } for(i=1;i<=A.n;i++) { acol[i]=(node*)calloc(1,sizeof(node)); acol[i]->r=0; acol[i]->up=acol[i]; } for(i=1;i<=A.k;i++) { printf("Gia tri phan tu:");scanf("%d",&value); printf("Chi so hang:");scanf("%d",&row); printf("Chi so cot:");scanf("%d",&col); p=(node*)calloc(1,sizeof(node)); p->v=value; p->r=row; p->c=col; q=arow[p->r]; while(p->cleft)->c) q=q->left; p->left=q->left; q->left=p; q=acol[p->c]; while(p->rup)->r) q=q->up; p->up=q->up; q->up=p; } } void createB(mt B) { int i,value,row,col; node *p,*q; for(i=1;i<=B.m;i++) { brow[i]=(node*)calloc(1,sizeof(node)); brow[i]->c=0; brow[i]->left=brow[i]; } for(i=1;i<=B.n;i++) { bcol[i]=(node*)calloc(1,sizeof(node)); bcol[i]->r=0; bcol[i]->up=bcol[i]; } for(i=1;i<=B.k;i++) { printf("Gia tri phan tu:");scanf("%d",&value); printf("Chi so hang:");scanf("%d",&row); printf("Chi so cot:");scanf("%d",&col); p=(node*)calloc(1,sizeof(node)); p->v=value; p->r=row; p->c=col; q=brow[p->r]; while(p->cleft)->c) q=q->left; p->left=q->left; q->left=p; q=bcol[p->c]; while(p->rup)->r) q=q->up; p->up=q->up; q->up=p; } } void display(node *q) { node *p; p=q->left; while(p!=q) { printf("%3d cot %d;",p->v,p->c); p=p->left; } } void ht(mt A) { int i; for(i=1;i<=A.m;i++) { printf("\nCac phan tu tren hang %d\n",i); display(arow[i]); } } void multi(mt A, mt B, mt &C) { node *p,*q,*t; int i,j,result; if(A.n==B.m) { C.m=A.m; C.n=B.n; for(i=1;i<=C.m;i++) { crow[i]=(node*)calloc(1,sizeof(node)); crow[i]->c=0; crow[i]->left=crow[i]; } for(i=1;i<=C.n;i++) { ccol[i]=(node*)calloc(1,sizeof(node)); ccol[i]->r=0; ccol[i]->up=ccol[i]; } for(i=1;i<=A.m;i++) for(j=1;j<=B.n;j++) { p=arow[i]->left; q=bcol[j]->up; result=0; while((p->c!=0)&&(q->r!=0)) if(p->c>q->r) p=p->left; else if(p->cr) q=q->left; else { result+=p->v*q->v; p=p->left; q=q->up; }