Chapter 5 String and Matrix

String

◼ string: List consists of characters

◼ S=‘a1a2…an’(n0)
◼ S：name of the string
◼ a1a2…an value of the string

◼ ai（1≤i≤n）can be letters、numbers or
other character

a=‘BEI’ b=‘JING’
c=‘BEIJING’ d=‘BEI JING’
 basic concepts of string S=‘a1a2…an’(n0)

1. length: number of the characters n

2. null/empty string：length=0 /
3. substring：part of the string，must be continuous
characters
4. substring’s position：position of the first
character of the substring
 a=‘BEI’ b=‘JING’
c=‘BEIJING’ d=‘BEI JING’

① length of these strings？

a =3，b =4，c = 7，d=8

② which string’s substring is a? ？where is the position?

a is c and d’s substring, both position is 1

③ which string’s substring is b? ？where is the position?

b is c and d’s substring, position in c is 4,position in d is 5.
 pattern matching of string
➢ locate the substring
➢ s：string
➢ t：substring
➢ search and locate the ‘t’in ‘s’
 BF alg.
main String S:“acabaabaabcacaabc”
sub String t:“abaabcac”
if（s[i]==t[j]）
{i++；j++；}
i=1
s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=1 if（s[i]！=t[j]）
{i back to the next of start point；
j back to 1；}
i=2
s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=2
 i=2
s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=1

i=3 i=4 i=5 i=6 i=7 i=8

s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=1 j=2 j=3j=4 j=5 j=6

i=4
s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=1
 i=5 i=6
s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=1 j=2
i=6i=7 i=8 i=9 i=10i=11i=12i=13i=14
s： a c a b a a b a a b c a c a a b c
t： a b a a b c a c
j=1j=2j=3 j=4 j=5 j=6 j=7 j=8j=9
BF algorithm：
➢loop condition？
➢when the pointers need to go back？
➢how to calculate i & j？
➢when to be done？
➢how to find the position？
 Exam & Experiment project
• two courses
• INFO3L3901 Data structures/3902 Experiment
• the online part will finish on July 9th/ upload the rest class
• paper exam
• when？I don’t know！
• level of these points
➢description
➢program
Huffman tree
– optimal decision tree
– minimum time

letter E D C B A 40
C
Grade 0~59 60~69 70~79 80~89 90~100 30
B
% 0.05 0.15 0.40 0.30 0.10
15
D
Y a<60 Y 70a<80 5 10
A E
E N C N
Y a<70 Y 80a<90
D N B N
Y a<80 Y 60a<70
C N D N
Y a<90 Y a<60
B N E N
A A
Huffman tree
• a weighted path length of the smallest binary tree
• path：from a node to another node
• path length： the number of edges on the path
• weight：describe sth‘s property as value/number(percentage、
priority lever…)
w={5, 29, 7, 8, 14, 23, 3, 11} 29 29 42
14 15 23 19
5 29 7 8 14 23 3 11 7 8 11 8
29 7 8 14 23 11 8
5 3
5 3
42 58
29 14 23 11 8 15
23 19 29 29
5 3 7 8
11 8 14 15
29 14 23 15 19
5 3 7 8
7 8 11 8
100
5 3
29 23 19 29 42 58
11 8 14 15 23 19 29 29
5 3 7 8 11 8 14 15
5 3 7 8
Tree Traversals
• 遍历
• 普遍 经历
• visiting every element
• why don’t we discuss “traversal” in List？
• simple：predecessor/successor
• only one way in List(linear)
• multiple successor
• how to choose your way？
• purpose：nonlinear to linear
• L：visit the left subtree
• D：visit the root
• R：visit the right subtree
• How many possible order？
• 6：LDR、LRD、DLR、DRL、RLD、RDL
• left first，then 3 left：
• DLR：preorder traversal
• LDR：inorder traversal
• LRD：postorder traversal
preorder traversal

inorder traversal

postorder traversal

what‘s the common point of 3 results？

order of the leaves

• Experiment Part
• Session4-Part2
• write a program to input a Binary Tree，and output the preorder、
inorder、postorder traversal results
• test data： preorder input ABC^^DE^G^^F^^^
• Experiment Part
• Session4-Part1
• write a program to implement Binary Search
• INFO3L3902 Experiment
• project reports
• deadline：August 5th
• send the reports to my Email：yihu5@126.com
• word/PDF
• 12 reports（11+1）
• Each report includes at least these parts：problem、solution、
code、result（screen capture）
• Session1-Part1：array insertion
• Session1-Part2：linked list insertion
• Session2-Part1：Josephus problem/circle-array
• Session2-Part2：Josephus problem/circle-circularly linked list
• Session3-Part1：create a linked list
• Session3-Part2：Head insertion/ Tail insertion
• Session4-Part1：Binary Search
• Session4-Part2：Binary Tree traversal
• Session5-Part1：stack
• Session5-Part2： Infix to Postfix
• Session6-Part1：pattern matching
• Final project：Graph
Matrix
• high dimension matrix
• special matrix
high dimension matrix

1-D matrix：array
2-D matrix
3-D matrix？？？？
• How to save high dimension matrix？
• Dimension reduction （降维）
• 2D-> 1D
• row major order
• column major order
• Lists
sparse matrix
• suppose the Matrix A（m × n） has t non zero elements；
• t far less than the elements in the matrix
• t≦m×n
• A is a sparse array

• we don’t need to save all the zero

➢Triples
➢Multi lists
Triples
i j e
1 2 8
0 8 − 1 0 0 0
0 0 0 0 4 0
1 3 -1
 2 5 4
M = − 1 0 0 0 0 0
  3 1 -1
0 0 0 7 0 0
4 4 7
 0 0 3 0 8 0
5 3 3

row : 5 5 5 8
col : 6
Multi lists 十字链表 i j e
down right

3 0 0
0 5 4
A=  
0 0 0
 
8 0 0
• Experiment Part
• Session6-Part1
• wright a program to implement the pattern matching
• locate the substring
• count the times