Program design tools
| English | Chinese | Pinyin |
|---|---|---|
| structure chart | 结构图 | jié gòu tú |
| state-transition diagram | 状态转换图 | zhuàng tài zhuǎn huàn tú |
| pseudocode | 伪代码 | wěi dài mǎ |
| decomposition | 分解 | fēn jiě |
| subroutines | 子程序 | zi chéng xù |
| parameters | 参数 | cān shù |
| top-down design | 自顶向下设计 | zì dǐng xiàng xià shè jì |
| states | 状态 | zhuàng tài |
The year software became engineering
- In October 1968, fifty of the world's leading programmers met in Garmisch, Germany, to discuss why large programs were failing: late, over budget, unreliable. They coined a phrase for what was missing: software engineering.
- The complaint was simple. Builders draw before they build. Engineers calculate before they cut. Programmers were typing code before anyone had drawn what the program was.
- The drawings that came out of that decade are the ones you will use in the design stage: the structure chart 结构图, which shows how a program is broken into parts, and the state-transition diagram 状态转换图, which shows how it behaves.
- This lesson is how to read them, how to construct them, and how to turn a structure chart into pseudocode.
What design decides
- Analysis said what the program must do. Design decides how: the data structures, the algorithms, the modules and the interface.
- The design stage produces drawings a programmer can code from: a flowchart for the logic of one algorithm, pseudocode 伪代码 for the same thing in text, a structure chart for the modules, and a state-transition diagram for the behaviour.
- Each tool answers a different question, and the exam asks which one fits.
One algorithm's logic, drawn before it is coded
Software process lab
Classify development examples by the stage or tool they belong to.
The structure chart
- A structure chart shows the hierarchical decomposition 分解 of a program into modules, its subroutines 子程序, and the parameters 参数 passed between them. This top-down design 自顶向下设计 breaks one large problem into smaller sub-problems, each of which becomes a module.
- Each module is a rectangle. A line joins a caller, above, to the module it calls, below. Modules on the same level are called from left to right.
- Small arrows beside the lines carry data: a parameter passed down into the module, a result returned up to the caller. A diamond marks a selection, a curved arrow a loop.
Hierarchy on the lines, data on the arrows
A structure chart shows:
A structure chart is the hierarchical breakdown into modules, with parameters down and results up.
Breaking a problem into modules from the top down is called:
Top-down design produces a modular solution.
Worked example: read the signatures off the chart
CalculatePay
/ | \
GetEmployee CalculateBonus CalculateTax
returns: takes: sales takes: gross
employeeID returns: bonus returns: tax
GetEmployeereceives nothing and returns an employee ID:FUNCTION GetEmployee() RETURNS INTEGER.CalculateBonustakes the sales figure down and sends the bonus back:FUNCTION CalculateBonus(Sales : REAL) RETURNS REAL.CalculateTaxtakes the gross pay and returns the tax. Every arrow on the chart is a parameter or a return value in the header; a header with a parameter the chart does not show is wrong.
On a structure chart, a small arrow pointing down from the caller into a module shows a ____ passed to it.
Downward arrows are parameters going in; upward arrows are results returned. Together they give the module's header.
Worked example: construct a structure chart
- A program reads a student's marks, calculates the average, and outputs a grade. Draw a structure chart.
- Top module:
ProcessStudent. Below it, left to right:ReadMarks, which returns the array of marks;CalculateAverage, which takes the marks array down and returns the average;OutputGrade, which takes the average down and returns nothing. - Three things score: the hierarchy with the main task at the top, the sub-tasks in the order they run, and named parameters on the arrows in the right direction. An unlabelled arrow is half a mark at best.
From structure chart to pseudocode
- The top module becomes the main program; each rectangle below it becomes a procedure or function whose header is read off the arrows; the main program calls them in left-to-right order.
PROCEDURE ProcessStudent()
DECLARE Marks : ARRAY[1:10] OF INTEGER
DECLARE Average : REAL
Marks ← ReadMarks()
Average ← CalculateAverage(Marks)
CALL OutputGrade(Average)
ENDPROCEDURE
- A returned value means a
FUNCTION … RETURNS; a module that returns nothing is aPROCEDURE. The parameter list is exactly the downward arrows.
Put the steps of designing a program with a structure chart in order.
Top down: task, sub-tasks, data flow, headers, calls. The chart is finished before the first line of code.
A module whose structure-chart arrows show a value returned upwards should be written as a PROCEDURE.
A returned value makes it a FUNCTION … RETURNS. A PROCEDURE returns nothing.
The state-transition diagram
- A state-transition diagram documents the behaviour of a system: the states 状态 it can be in and the events that move it from one state to another.
- Each state is a circle or rounded box; each transition is an arrow labelled with the event that causes it, sometimes with the action taken. A marker shows the start state.
- It suits systems that wait for events and react: a vending machine, a traffic light, a door lock, a user interface.
Every state, every event, every arrow
A state-transition diagram shows:
States are circles; transitions are event-labelled arrows. Ideal for vending machines, locks, traffic lights.
What does a state-transition diagram show? Select all that apply.
States, labelled transitions and the start marker. Timing is not part of the diagram.
Worked example: read the door-lock diagram
- The lock opens on the code 2, 5, 9. Start in Locked. Pressing 2 moves to One digit correct; pressing 5 from there moves to Two digits correct; pressing 9 from there moves to Unlocked.
- Any other key from any of the waiting states returns to Locked: the diagram shows those arrows too, and a diagram that leaves them out has a gap. What happens if 2 is pressed while Unlocked? If no arrow says, the design has not decided.
- That is what the diagram is for: every state must say what happens on every event, so the missing transitions are found on paper and not by a customer.
A state-transition diagram makes missing or unhandled transitions easy to spot, because every state and the events between them are laid out.
Seeing every state and event reveals cases you have not handled — e.g. an unexpected second coin in a vending machine.
Choosing the tool
- To show how a program is broken into modules and what passes between them: a structure chart.
- To show how a system behaves over time in response to events, especially a machine or an interface with modes: a state-transition diagram.
- To show the step-by-step logic of one algorithm: a flowchart or pseudocode. Say which and why.
Match each design tool to what it shows.
Each tool views the design differently — structure (modules), behaviour (states), flow (flowchart) or steps (pseudocode).
A traffic-light controller must respond to a timer and a pedestrian button. Which design tool documents its behaviour best?
Red, red-and-amber, green, amber are states; the timer and the button are events. A structure chart would show the modules, not the behaviour.
Marks that slip away
- A structure chart is not a flowchart. It shows hierarchy and parameters, not the sequence of decisions inside a module.
- Label every arrow with the name of the parameter or result and point it the right way. A bare arrow says nothing.
- A state is a condition the system is in, waiting; an event is what happens to it. "Press 5" is an event, not a state.
- The pseudocode headers must match the chart: same parameters, same return values, same order of calls.
You've got it
- a structure chart shows top-down decomposition into modules, with the parameters passed down and the results returned up on labelled arrows
- read the pseudocode headers off it: downward arrows are the parameter list, an upward arrow makes it a
FUNCTION … RETURNS, and the main module calls left to right - a state-transition diagram shows the states and the events that move between them, and exposes the transitions nobody has decided
- decomposition → structure chart; behaviour → state-transition diagram; one algorithm's logic → flowchart or pseudocode