C语言数据结构设计1

1、 Chapter 1 PROGRAMMING PRINCIPLES 1. Introduction:Problems with large programs 2. The Game of Life (acontinuing example 3. Programming style (aNames (bDocumentation and format (cRe?nement and modularity 4. Coding, testing, and further re?nement (aStubs (bInput and Output (cDrivers (dProgram Testing

2、5. References Problems of Large Programs 1. The patchwork approach 2. Problem speci?cation 3. Program organization 4. Data organization and data structures 5. Algorithm selection and analysis 6. Debugging 7. Testing 8. Maintenance Rules for the Game of Life 1. The neighbors of a given cell are the e

3、ight cells that touch it vertically, horizontally, or diagonally. Every cell is either living or dead. 2. A living cell stays alive in the next generation if it has either 2or 3living neighbors; it dies if it has 0, 1, 4, or more living neighbors. 3. A dead cell becomes alive in the next generation

4、if it has ex-actly three neighboring cells, no more or fewer, that are al-ready alive. All other dead cells remain dead in the next gen-eration. 4. All births and deaths take place at exactly the same time, so that a dying cell can help to give birth to another, but cannot prevent the death of other

5、s by reducing overcrowding, nor can cells being born either preserve or kill cells living in the previous generation. and Examples of Life Con?gurations (j(k (l Algorithm for the Life Game Initialize an array called map to contain the initial con?guration of living cells. Repeat the following steps

6、for as long as desired: For each cell in the array do the following: Count the number of living neighbors of the cell. If the count is 0, 1, 4, 5, 6, 7, or 8, then set the corresponding cell in another array called newmap to be dead; if the count is 3, then set the corresponding cell to be alive; an

7、d if the count is 2, then set the corresponding cell to be the same as the cell in array map (sincethe status of a cell with count 2does not change. Copy the array newmap into the array map . Print the array map for the user. Guidelines for Choosing Names 1. Give special care to the choice of names

8、for functions, con-stants, and all global variables and types used in different parts of the program. 2. Keep the names simple for variables used only brie?y and locally. 3. Use common pre?xes or suf?xes to associate names of the same general category. 4. Avoid deliberate misspellings and meaningles

9、s suf?xes to ob-tain different names. 5. Avoid choosing cute names whose meaning has little or noth-ing to do with the problem. 6. Avoid choosing names that are close to each other in spelling or otherwise easy to confuse. 7. Be careful in the use of the letter “ l ” (smallell, “ O ” (capital oh and

10、 “ 0” (zero. Programming Precept Always name your variables and functions with the greatest care, and explain them thoroughly. Documentation Guidelines 1. Place a prologue at the beginning of each function with (aIdenti?cation (programmers name, date, version. (bStatement of the purpose of the funct

11、ion and method used. (cChanges the function makes and what data it uses. (dReference to further documentation for the program. 2. When each variable, constant, or type is declared, explain what it is and how it is used. 3. Introduce each signi?cant part of the program with a state-ment of purpose. 4

12、. Indicate the end of each signi?cant section. 5. Avoid comments that parrot what the code does or that are meaningless jargon. 6. Explain any statement that employs a trick or whose meaning is unclear. Better still, avoid such statements. 7. The code itself should explain how the program works. The

13、 documentation should explain why it works and what it does. 8. Be sure to modify the documentation along with the program. Programming Precept Keep your documentation concise but descriptive. Programming Precept The reading time for programs is much more than the writing time. Make reading easy to

14、do. Re?nement and Modularity Top-down design and re?nement: Programming Precept Dont lose sight of the forest for its trees. Division of work among functions: Programming Precept Each function should do only one task, but do it well. Programming Precept Each function should hide something. Programmi

15、ng Precept Include precise preconditions and postconditions with every function that you write. Categories of Data Used in Functions Input parameters Output parameters Inout parameters Local variables Global variables Programming Precept Keep your connections simple. Avoid global variables whenever

16、possible. Programming Precept Never cause side effects if you can avoid it. If you must use global variables, document them thoroughly. Programming Precept Keep your input and output as separate functions, so they can be changed easily and can be custom-tailored to your computing system. Debugging a

17、nd Testing Methods for debugging: 1. Structured walkthrough 2. Snapshots 3. Scaffolding 4. Static analyzer Programming Precept The quality of test data is more important than its quantity. Programming Precept Program testing can be used to show the presence of bugs, but never their absence. Methods

18、for program testing: 1. The black-box method: (a Easy values (b Typical, realistic values (c Extreme values (d Illegal values 2. The glass-box method: Trace all the paths through the program. 3. The ticking-box method: Dont do anythingJust hope for the best! Debugging and Testing Transp. 11, Sect. 1

19、.4, Coding, Testing, and Further Renement 239 1997 Prentice-Hall, Inc., Upper Saddle River, N.J. 07458 Data Structures and Program Design In C, 2nd. ed. Execution Paths switch a case 1: x = 3; break; case 2: if (b = 0 x = 2; else x = 3; x = 4; break; case 3: while (c 0 process (c; break; a = 1 a = 2

20、 b = 0 b != 0 a = 3 x = 2; x = 4; while (c 0 process (c; a = 1 a = 2 b = 0 a = 2 b != 0 a = 3 x = 3; x = 2; x = 4; while (c 0 process (c; Path 1 Path 2 Path 3 Path 4 Execution Paths Transp. 12, Sect. 1.4, Coding, Testing, and Further Renement 240 1997 Prentice-Hall, Inc., Upper Saddle River, N.J. 07

21、458 Data Structures and Program Design In C, 2nd. ed. R Pentomino Cheshire Cat Virus Tumbler Barber Pole Harvester The Glider Gun Life congurations Transp. 13, Sect. 1.4, Coding, Testing, and Further Renement 241 1997 Prentice-Hall, Inc., Upper Saddle River, N.J. 07458 Data Structures and Program De

22、sign In C, 2nd. ed. Pointers and Pitfalls 1. Understand your problem before you decide how to solve it. 2. Understand the algorithmic method before you start to program. 3. Divide the problem into pieces and think of each part separately. 4. Keep your functions short and simple. 5. Include careful documentation with each function. 6. Write down precise preconditions