CHUỖI VÀ CÁC BÀI TOÁN TRÊN CHUỖI part 2

Chia sẻ: Pham Duong | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

74
lượt xem 15
download

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

Chuỗi là một dãy các ký tự được chứa trong một vùng liên tục của bộ nhớ. Các ký tự này có thể là ký tự chữ, ký tự số hoặc ký tự đặc biệt. Chuỗi ký tự (text string) có thể được xem như là dãy các chữ, các số và các ký tự đặc biệt. Một loại chuỗi khác là chuỗi nhị phân (binary string), đó là một dãy các kí tự 0 và 1.

Chủ đề:

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

Lưu

Nội dung Text: CHUỖI VÀ CÁC BÀI TOÁN TRÊN CHUỖI part 2

begin writeln(‘chuoi can tim la:’,p); end; Function Bmsearch (p,a:st):integer; Var i,j,m,n:integer; skip :array[1..charno]of interger; procedure Initskip; var i:1..charno; j:integer; begin for i:=1 to charno do skip[i]=m; for j:=1 to m do if skip[ord(p[j])]=m then skip[ord(p[j])]=m-j; end; begin m:=length(p); n:=length(a); i nitskip; i :=m; j :=m; repeat if a[i]=p[j] then begin i:=i-1; j:=j-1; end; begin if m-j+1>skip[ord(a[i])] then i :=i+m-j+1 else i:=i+skip[ord(a[i])]; j:=m; end; until (jn); if j
begin clrscr; init; bmsearch(a,p); write(‘vi tri cua ky tu dau cua chuoi p trong a la :’,bmsearch(p,a):2) ; writeln ; result ; readln ; end. c. Phân tích giải thuật Số lần so sánh : Cmax=m+n Số bước thực hiện trong trường hợp bộ ký tự không nhỏ và chuỗi p không lớn là: S=n/m {$M $4000,0,0} Program Bai_tap_tren_xau; uses crt; type m= array [1..9] of string; const menu:m=(' 1. Dao nguoc xau ',' 2. Tinh chieu dai cua xau',' 3. Chi so cua xau',' 4. Lay xau ky tu con', ' 5. In xau khong de quy',' 6. In xau de quy',' 7. Bai 5.2',' 8. Bai 5.5',' 9. Thoat'); type infor=char; ref=^elemen; elemen=record info:infor; link:ref; 13 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
end; var first:ref; const max=1000; type stacks=record index:integer; data:array[1..max] of integer; End; stackc=record index:integer; data:array[1..max] of char; end; stackR=record index:integer; data:array[1..max] of real; End; var step:integer; d,g:ref; ch1,h,c1:char; i1,n,f,e,b1,b2:integer; i:integer; s:string; stack:stackc; kt:boolean; t:real; nu,r: integer; stack1:stacks; {---------------------------------------------------------} 14 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
function themdau(var first:ref;NewInfo:Infor):ref; var p:ref; begin new(p); p^.info:=NewInfo; p^.link:=first; first:=p; themdau:=p; end; {--------------------------------------------------------} function themcuoi(var q:ref;NewInfo:Infor):ref; var p,scan:ref; begin New(p); p^.Info:=NewInfo; p^.link:=nil; if q = nil then q :=p else Begin scan:=q; while scan^.linknil do scan:=scan^.link; scan^.link:=p; End; themcuoi:=p; end; 15 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
{--------------------------------------------------------} procedure xoadau(var first:ref); var p:ref; begin if firstnil then b egin p:=first; first:=p^.link; dispose(p); end; end; {-----------------------------------------------------} procedure xoacuoi(var first:ref); var p,q:ref; begin q :=first; p :=q^.link; if(first=nil)then exit; if(p=nil)then b egin dispose(q); first:=nil; end else b egin while(p^.linknil) do 16 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
begin p:=p^.link; q:=q^.link; end; d ispose(p); q ^.link:=nil; end; end; {----------------------------------------------------------} procedure inra(first:ref); var p:ref; begin p:=first; while(pnil) do begin write(p^.info); p:=p^.link; end; end; {---------------------------------------------------------} procedure dao(var first:ref); var a,b,c:ref; begin if(first=nil) then exit else if (first^.link=nil) then 17 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
exit else a:=nil; b:=first; c:=first^.link; while(cnil) do begin b^.link:=a; a:=b; b:=c; c:=c^.link; end; b ^.link:=a; first:=b; end; {-----------------------------------------------------------} function chieudai(first:ref):integer; var d em:integer; p :ref; begin p:=first; dem:=0; while(pnil) do begin p:=p^.link; dem:=dem+1; end; 18 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
chieudai:=dem; end; {-----------------------------------------------------------} function chiso(first:ref;d:integer):infor; var p:ref; dem:integer; begin p:=first; dem:=1; while(dem
begin q:=q^.link; inc(dem); end; if(q=nil) then begin xaukitucon:=nil; exit; end; n ew(daumoi); daumoi^.info:=q^.info; duoimoi:=daumoi; for i:=2 to n do begin q:=q^.link; if(qnil) then begin new(temp); temp^.info:=q^.info; duoimoi^.link:=temp; duoimoi:=temp; end else break; end; duoimoi^.link:=nil; xaukitucon:=daumoi; end; {------------------------------------------------------------} 20 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
procedure inxau(first:ref); {khong de quy} var p:ref; begin p:=first; while(pnil) do begin write(p^.info); p:=p^.link; end; end; {----------------------------------------------------------} procedure inxaudq(first:ref); var p:ref; begin p:=first; if(first=nil) then exit else begin write(p^.info); inxaudq(p^.link); end; end; {-----------------------------------------------------} procedure writestacks(stack:stacks); var i:integer; 21 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh
begin for i:=0 to stack.index do write(stack.data[i]); end; {--------------------------------------------------------} procedure lnits(var stack:stacks); begin stack.index:=0; end; {---------------------------------------------------------} function emptys(var stack:stacks):boolean; begin if stack.index=0 then emptys:=true else emptys:=false; end; {-------------------------------------------------------------} function Pushs(var stack:stacks;dt:integer):boolean; Begin if stack.index=max+1 then pushs:=false else Begin inc(stack.index); pushs:=true; stack.data[stack.index]:=dt; end; End; {--------------------------------------------------------} function pops(var stack:stacks;var dt:integer):boolean; begin 22 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh