Úvod do programování 6. hodina

Úvod do programování 6. hodina RNDr. Jan Lánský, Ph.D. Katedra informatiky a matematiky Fakulta ekonomických studií Vysoká škola finanční a správní 2015

Umíme z minulé hodiny 

Algoritmy 

 



Syntax 





Třídění pole: Selection sort, Insertion sort, Bubble sort Třídění pole omezených hodnot: Counting sort Binární vyhledávání v setříděném poli Globální proměnné

Měření počtu operací Měření doby běhu programu

Jan Lánský

Úvod do programování 6. hodina

2

Cíle hodiny 

Syntax  



Algoritmy 

   



Znaky Textové řetězce

Vlastní implementace řetězcových algoritmů jsou výborné na procvičení schopností práce s polem

Lexikografické uspořádání Zřetězení, podřetězec Hledání indexu výskytu znaku, řetězce Vymazání, vložení a nahrazení znaku, řetězce Změna hodnoty znaku na pozici dané indexem

Naše vlastní řetězce

Jan Lánský


3

Znaky 

V některých programovacích jazycích bývá char 8 bitů ASCII

char - velikost 16 bitů – UTF16 znak 

Znakové konstanty uzavřeny v apostrofech 



Každé znakové konstantě odpovídá celočíselná hodnota 





Př.: char c1 = 'a';

Př.: int i = c1; Ale nedělat char c2 = (char) 40;

Uspořádané podposloupnosti: číslice, malá písmena, velká písmena

Jan Lánský


4

Znaky

Každá znaková konstanta má celočíselnou hodnotu

Kolikáté písmeno abecedy nebo kolikáté číslo ?

Převod písmen na velká písmena a na malá písmena. Nevyvolá chybu. Jan Lánský


5

Typy znaků 

 

    



Některé znaky jsou zároveň řídící a oddělovače slov (například znaky pro odřádkování

char.IsLetterOrDigit – písmeno nebo číslo char.IsLetter – písmeno char.IsLower – malá písmena (a, b, c, …) char.IsUpper – velká písmena (A, B, C, …) char.IsDigit – číslice (0, 1, 2, …) char.IsControl – řídící znaky ( …) char.IsPunctuation – interpunkce (? : , …) char.IsWhiteSpace – oddělovače slov (mezera, …) char.IsSymbol – symboly (< = + …)

Jan Lánský


6

Typy Znaků

Tabulka prvních 256 znaků včetně typu znaku. Prvních 128 znaků společné i 8-bitovým znakovým sadám

Výpis abecedy malých písmen v cyklu Analogicky: velká písmena, čísla Jan Lánský


7

Textové řetězce 

string – pole znaků s konstantní hodnotou     





Hodnoty uzavřeny v uvozovkách char uzavírá hodnoty Př.: string a = "ahoj"; a[0] až a[3] do apostrofů Př.: prázdný řetězec string s = "" Př.: string s =Console.ReadLine() Nelze přímo modifikovat prvky přes []. Pomocí funkcí vytváříme nové řetězce (s použitím již existujících řetězců

StringBuilder – pole znaků s nekonstantní hodnotou (nebudeme probírat) Jan Lánský


8

Textové řetězce

Inicializace řetězce Načtení řetězce z klávesnice

Převod řetězce na pole znaků Převod pole znaků na řetězec Délka řetězce Získání hodnoty znaku s daným indexem

Neovlivní s2

Pole konstantních hodnot. Mohu přiřadit celé nové pole, ale ne modifikovat hodnoty prvků pole

Jan Lánský

Přístup ke konkrétnímu znaku je jen pro čtení, hodnota znak nejde modifikovat pomocí []


9

Funkce vracející bool Test, zda obsahuje zadaný řetězec

Test rovnosti řetězců Test nerovnosti řetězců

s2.Contains("ova"); true

"Novak" != "novak"; true

'o' 'v' 'a' 'N' 'o' 'v' 'a' 'k'

'n' 'o' 'v' 'a' 'k' 'N' 'o' 'v' 'a' 'k'

Jan Lánský


10

Lexikografické uspořádání string.Compare Nalezne nejnižší index, na kterém se hodnoty znaků liší. Menší znak určil menší řetězec.

0 – řetězce se rovnají -1 první řetězec je menší 1 první řetězec je větší Compare("doga", s1); -1

'd' 'r' 'u' 'h' 'd' 'o' 'g' 'a' Jan Lánský

Pokud je jeden řetězec prodloužením druhého řetězce, pak delší řetězec je větší

Lexikografické = podobné abecedě. Ale liší se (malá, velká písmena) Compare("druhy", s1); 1

'd' 'r' 'u' 'h' 'd' 'r' 'u' 'h' 'y'


11

Indexy

Index prvního (posledního) výskytu řetězce (znaku) v řetězci. Možno omezit pozice od které hledám a délku prohledávaného úseku První výskyt znaku

První 'b' od pozice 3 v úseku délky 1 nenalezeno

První výskyt řetězce Poslední výskyt První 'u' od pozice 2 je na 3 Poslední 'b' 4 Předposlední řádek: omezení pozice od které hledám Poslední řádek: navíc omezena i délka prohledávaného úseku

První "ubu " 1 První 'u' 1

'b' 'b' 'b' 'b' 'b' 0

'u' 'u' 'u' 'u' 'u' 1

První pozice má index 0 Jan Lánský


'b' 'b' 'b' 'b' 'b' 2

'u' 'u' 'u' 'u' 'u' 3

'b' 'b' 'b' 'b' 'b' 4

'u' 'u' 'u' 'u' 'u' 5

Indexy pole s1 12

Počet výskytů

Taková funkce není, vytvoříme si jí Index posledního výskytu Hledáme od posledního výskytu doprava

Šlo by testovat přímo poslední v hlavičce cyklu

Jan Lánský


Končíme, nenalezli jsme další výskyt

13

Převod na malá a velká Převod = konverze písmena ToUpper - velká písmena ToLower - malá písmena Nevyvolá chybu, co nejde převést nechá být Lze volat i řetězcové hodnotě

Aplikováno na s4, ale výsledek stejný jako by bylo aplikováno na s1 Jan Lánský

Volání funkcí: řetězec tečka funkce

'p' 'a' 'v' 'e' 'l' 'P' 'A' 'V' 'E' 'L' 'P' 'a' 'v' 'e' 'l' Úvod do programování 6. hodina

s4 "pavel" s4 "PAVEL" s1 "Pavel"

14

Zřetězení = konkatenace: Nový řetězec obsahuje první zadaný řetězec následovaný druhým zadaným řetězcem

Zřetězení

+ operátor zřetězení

Zřetězit lze i řetězec se znakem s2 "Novak"

s1 "Pavel"

'N' 'o' 'v' 'a' 'k' ''

'P' 'a' 'v' 'e' 'l' 'P' 'a' 'v' 'e' 'l'

""

' ' 'N' 'o' 'v' 'a' 'k'

s1 + " " + s2 Jan Lánský


15

Podřetězec – souvislá část řetězce

Podřetězec

Podřetězec začínající na pozici zadané indexem a končící na konci řetězce Podřetězec začínající na pozici zadané indexem a mající zadanou délku Chyba: pokud index + délka > Length

s3.Substring(6,3) "Nov" s3.Substring(6) "Novak"

'P' 'a' 'v' 'e' 'l' 0 1 2 3 4 První pozice má index 0 Jan Lánský

'N' 'N' ' ' 'N' 5 6

'o' 'o' 'o' 7

'v' 'v' 'a' 'k' 'v' 'a' 'k' 8 9 10

Indexy pole s3 Úvod do programování 6. hodina

s3 "Pavel Novak" 16

Vložení: na pozici zadanou indexem vloží zadaný řetězec. Znaky původního řetězce posune.

Vložení

Vložení doprostřed řetězce

Vložení nakonec řetězce s3.Insert(6, "je") "Pavel je Novak"

'P' 'a' 'v' 'e' 'l' 'P' 'a' 'v' 'e' 'l' 0 1 2 3 4 První pozice má index 0 Jan Lánský

' ' 'j' 'e' ' ' 'N' 'o' 'v' 'a' 'k' ' ' 'N' 'o' 'v' 'a' 'k' 5 6 7 8 9 10 11 12

Indexy pole s3

Zelená – posun Červená - vložení


s3 "Pavel Novak" 17

Odstranění

Odstranění: V řetězci nalezne podřetězec určený svým začátkem (a délkou). Nalezený řetězec odstraní. Zbylé znaky posune. Zadaný index začátku odstraňovaného řetězce Zadaný index začátku a délka odstraňovaného podřetězce

Zelená – posun

'P' 'P' 'P' 0

'a' 'a' 'a' 1

Chyba: pokud index + délka > Length

' ' 'N' 'o' 'v' 'a' 'k' s3.Remove(2, 3) "Pa Novak" s3.Remove(5) "Pavel" 'v' 'e' 'l' 'v' 'e' 'l' ' ' 'N' 'o' 'v' 'a' 'k' 2 3 4 5 6 7 8 9 10

První pozice má index 0 Jan Lánský

Indexy pole s3 Úvod do programování 6. hodina

s3 "Pavel Novak" 18

Nula nahrazení není chyba

Vymazání: Replace("retezec", "")

Nahrazení

Nahrazení: V řetězci nalezne podřetězec určený hodnotou, ten odstraní a na místo jeho bývalého začátku vloží jiný podřetězec. Opakuje pro všechny výskyty. První podřetězec je nahrazen druhým

Stejné jako předchozí řádek Místo řetězců můžou být jen znaky

s3.Replace("Pavel", "Petr")

s3.Replace('v', 'w')

'P' 'a' 'w' 'e' 'l' ' ' 'N' 'o' 'w' 'a' 'k' 'P' 'e' 't' 'r' ' ' 'N' 'o' 'v' 'a' 'k' 'P' 'a' 'v' 'e' 'l' ' ' 'N' 'o' 'v' 'a' 'k' s3 "Pavel Novak" Jan Lánský


Zelená – posun Červená - výměna

19

Změna hodnoty znaku v řetězci 

String je pole znaků s konstantní hodnotou  



Nelze použít zápis s[0] = 'a' Přesto chceme hodnoty znaků někdy měnit

Tři možná řešení   

Naše volba

Využití funkce Substring Konverze na pole znaků a zpět Konverze na StringBuilder a zpět Jan Lánský


20

Změna hodnoty znaku Podřetězec, který začíná na začátku řetězce a končí před zadaným indexem

Vše spojíme s1 'a' … 'a' … 'a' … 0 Jan Lánský…

'v' 'v' 'v' -1

Podřetězec, který začíná na za zadaným indexem a končí na konci řetězce

hodnota 's' 'e' 's' 'e' 's' index +1 Úvod do programování 6. hodina

' s2' '' '' …

'o' 'o' 'o' Len

21

Změna hodnoty znaku Ukázka Novak  Horal

index = 2 hodnota 'r' s1 Od pozice 0 počet prvků 2

Jan Lánský

'H' 'o' 'r' 'a' 'k' 'H' 'o' 'v' 'a' 'k' 0 1 2 3 4 Úvod do programování 6. hodina

s2 Od pozice 3 do konce řetězce

22

Funkce Split 

string[] string.Split(char[]) 





Nyní nebudeme ještě používat, až později

Rozdělí řetězec na disjunktní podřetězce podle oddělovačů zadaných v poli Tj. pole polí. Na nás Vrací pole řetězců

Problém 

zatím moc složité

Při dělení na slova, čísla nejde vyjmenovat všechny myslitelné oddělovače. 

Znak, se kterým jsme nepočítali.

Jan Lánský


23

Ukázkový příklad 



… spíše antipříklad

V zadaném řetězci převeďte každé liché slovo na velká písmena a každé sudé slovo na malá písmena. Řešení na následujícím slajdu 



Není řešeno obecně, ale pro konkrétní řetězec (s hlavičkou by se nevešlo na slajd) Časová složitost může být vysoká (dle přesné implementace stringu) 

Jan Lánský

Iterativní přidávání znaků na konec Úvod do programování 6. hodina

24

Ukázkový příklad řešení

Až zkončí písmena bude změna velikosti

velke – zda je nyní slovo z velkých písmen prvni – zda čekáme na první písmeno řetězce zmena – zda při příštím nepísmenu máme změnit proměnnou velke

Při prvním nepísmenu změna velikosti,

Jan Lánský


Vytváříme nový řetězec přidáváním znaků nakonec 25

Naše řetězce char[] 





Pole znaků char[] může odsimulovat string Se znalostí minulých hodin snadno vytvoříme jednotlivé funkce, co má string Ukážeme si několik funkcí, zbytek bude na cvičení

Jan Lánský


26

Naše řetězce char[] Výpis na obrazovku znak po znaku

Převod řetězce string na náš řetězec char[]

Zřetězení, bude další slide

Jan Lánský


27

Naše řetězce char[] Vytvořit pole potřebné délky Do nového řetězce nakopírujeme první řetězec Druhý řetězec kopírujeme s posunem o délku prvního pole Jan Lánský


28

Zpětná vazba 

Objevili jste ve slajdech chyby? 



Nechápete nějaký slajd? 





Je příliš obtížný, nesrozumitelný?

Máte nějaký nápad na vylepšení? Anonymní formulář 



Včetně pravopisných

Odeslání za pár vteřin

http://goo.gl/forms/WxkZqBsZLs

Jan Lánský


29

Úvod do programování 6. hodina

Recommend Documents