C++第3版《数据结构教程》：Nell Dale 著

需积分: 4 137 浏览量更新于2024-07-28 1 收藏 10.08MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

资源详情

资源推荐

6.5 A Linked List as an Array of Records 358

6.6 Polymorphism with Virtual Functions 368

6.7 A Specialized List ADT 373

Case Study: Implementing a Large Integer ADT 379

Summary 392

Exercises 392

Programming with Recursion 399

7.1 What is Recursion? 400

7.2 The Classic Example of Recursion 401

7.3 Programming Recursively 404

7.4 Verifying Recursive Functions 407

7.5 Writing Recursive Functions 408

7.6 Using Recursion to Simplify Solutions 411

7.7 Recursive Linked List Processing 412

7.8 A Recursive Version of Binary Search 416

7.9 Recursive Versions of

InsertItem and DeleteItem 418

7.10 How Recursion Works 420

7.11 Tracing the Execution of Recursive Function

Insert 429

7.12 Debugging Recursive Routines 432

7.13 Removing Recursion 432

7.14 Deciding Whether to Use a Recursive Solution 436

Case Study: QuickSort 438

Summary 446

Exercises 447

Binary Search Trees 455

8.1 Trees 456

8.2 Logical Level 460

8.3 Application Level 463

8.4 Implementation Level 463

8.5 Recursive Binary Search Tree Operations 464

8.6 Iterative Insertion and Deletion 496

8.7 Comparing Binary Search Trees and Linear Lists 504

8.8 A Nonlinked Representation of Binary Trees 506

Case Study: Building an Index 510

Contents | xv

2 | Chapter 1: Software Engineering Principles

At this point in your computing career, you have completed at least one semester of

computer science course work. You can take a problem of medium complexity, write an

algorithm to solve the problem, code the algorithm in C++, and demonstrate the correct-

ness of your solution. At least, that’s what the syllabus for your introductory class said

you should be able to do when you complete the course. Now that you are starting your

second (or third?) semester, it is time to stop and review those principles that, if adhered

to, guarantee that you can indeed do what your previous syllabus claimed.

In this chapter, we review the software design process and the verification of soft-

ware correctness. In Chapter 2, we review data design and implementation.

1.1

The Software Process

When we consider computer programming, we immediately think of writing a program

for a computer to execute—the generation of code in some computer language. As a

beginning student of computer science, you wrote programs that solved relatively sim-

ple problems. Much of your initial effort went into learning the syntax of a program-

ming language such as C++: the language’s reserved words, its data types, its constructs

for selection (if-else and switch) and looping (while, do while, and for), and its

input/output mechanisms (cin and cout).

You may have learned a programming methodology that took you from the problem

description that your instructor handed out all the way through the delivery of a good

software solution. Programmers have created many design techniques, coding standards,

and testing methods to help develop high-quality software. But why bother with all that

methodology? Why not just sit down at a computer and write programs? Aren’t we

wasting a lot of time and effort, when we could just get started on the “real” job?

If the degree of our programming sophistication never had to rise above the level of

trivial programs (like summing a list of prices or averaging grades), we might get away

with such a code-first technique (or, rather, lack of technique). Some new programmers

work this way, hacking away at the code until the program works more or less cor-

rectly—usually less.

As your programs grow larger and more complex, however, you must pay attention

to other software issues in addition to coding. If you become a software professional,

someday you may work as part of a team that develops a system containing tens of

thousands, or even millions, of lines of code. The activities involved in such a software

project’s whole “life cycle” clearly go beyond just sitting down at a computer and writ-

ing programs. These activities include

• Problem analysis Understanding the nature of the problem to be solved

• Requirements elicitation Determining exactly what the program must do

• Requirements definition Specifying what the program must do (functional

requirements) and any constraints on the solution approach (nonfunctional

requirements such as what language to use)

• High- and low-level design Recording how the program meets the requirements,

from the “big picture” overview to the detailed design

1.1 The Software Process | 3

• Implementation of the design Coding a program in a computer language

• Testing and verification Detecting and fixing errors and demonstrating the cor-

rectness of the program

• Delivery Turning over the tested program to the customer or user (or instructor!)

• Operation Actually using the program

• Maintenance Making changes to fix operational errors and to add or modify

the program’s function

Software development is not simply a matter of going through these steps sequen-

tially. Rather, many activities take place concurrently. We may code one part of the

solution while we design another part, or define requirements for a new version of a

program while we continue testing the current version. Often a number of people may

work on different parts of the same program simultaneously. Keeping track of all these

activities is not an easy task.

We use the term software engineering to

refer to the discipline concerned with all

aspects of the development of high quality

software systems. It encompasses all varia-

tions of techniques used during the software

life cycle plus supporting activities such as

documentation and teamwork. A software

process is a specific set of interrelated soft-

ware engineering techniques, used by a per-

son or organization to create a system.

What makes our jobs as programmers or

software engineers challenging is the ten-

dency of software to grow in size and complexity and to change at every stage of its

development. A good software process uses tools to manage this size and complexity

effectively. Usually a programmer takes advantage of several toolboxes, each containing

tools that help to build and shape a software product.

Hardware One toolbox contains the hardware itself: the computers and their

peripheral devices (such as monitors, terminals, storage devices, and printers), on which

and for which we develop software.

Software A second toolbox contains various software tools: operating systems to

control the computer’s resources, text editors to help us enter programs, compilers to

translate high-level languages like C++ into something that the computer can execute,

interactive debugging programs, test-data generators, and so on. You’ve used some of

these tools already.

Ideaware A third toolbox is filled with the shared body of knowledge that

programmers have collected over time. This box contains the algorithms that we use to

solve common programming problems as well as data structures for modeling the

Software engineering The discipline devoted to the

design, production, and maintenance of computer pro-

grams that are developed on time and within cost esti-

mates, using tools that help to manage the size and

complexity of the resulting software products

Software process A standard, integrated set of software

engineering tools and techniques used on a project or by

an organization

剩余832页未读，继续阅读

阿莱

粉丝: 2
资源: 99

C++第3版《数据结构教程》：Nell Dale 著

C＋＋_Plus_Data_Structures.3rd_Edition.ND.[EN].pdf

vctpath.push_back

上述代码的问题Traceback (most recent call last): File "1.py", line 14, in <module> C_positions += structure.positions[structure.get_chemical_symbols() == 'C'] ValueError: operands could not be broadcast together with shapes (0,) (0,35,3)

detectron2 mask训练代码

python opls-da

创建大学数据库多表查询

LinkedList ad

A program counts the number of words in a string read from the user,and then exits. __ pattern is most suitable for implementing this specification

pos=nx.spring_layout

python代码学生选课管理系统

python实现学生选课系统

我需要制作一个沙盒冒险生存游戏的代码

最新资源