CSCI104数据结构与面向对象设计讲义

需积分: 7 5 浏览量更新于2024-07-19 收藏 1.58MB PDF 举报

"CSCI104课程数据结构与面向对象设计讲义" 这些讲义源自2013年秋季南加州大学CSCI 104课程（“数据结构与面向对象设计”）的学生课堂笔记。这门课程通常在大一第二学期或大二第一学期进行，学生需要对C++编程语言的结构化编程、动态内存管理和递归有基本的了解。讲义开头简要回顾了这两个特定主题，并且通常会在每门课中用一堂课的时间进行复习，但对于不熟悉这些概念的学生来说，可能会在课程中遇到困难。这些讲义反映了讲师倾向于从实现数据结构的角度来引导学生理解面向对象设计的方法。可能比一般的本科编程密集型数据结构课程更注重分析，并且更多地提及高级主题。讲义内容包括但不限于： 1. **数据结构基础**：介绍各种基本的数据组织形式，如数组、链表、栈、队列、散列表等，以及它们在实际问题中的应用。 2. **抽象数据类型（ADT）**：强调ADT的概念，它是一种逻辑上的数据结构，定义了一组操作，但不考虑其具体实现细节。 3. **面向对象编程**：讲解类、对象、封装、继承和多态等核心概念，展示如何通过这些概念设计和实现复杂的数据结构。 4. **动态内存管理**：解释如何使用指针和动态分配内存，以及在数据结构中如何有效地管理内存。 5. **递归**：深入讨论递归的原理和在数据结构操作中的应用，如二分查找、排序算法（快速排序、归并排序）等。 6. **算法分析**：教授时间复杂度和空间复杂度的概念，以及如何评估算法的效率。 7. **高级主题**：可能涉及图论、树结构、搜索算法（深度优先搜索、广度优先搜索）和最短路径算法等，这些都是数据结构领域的重要内容。 8. **设计模式**：介绍一些常见的软件设计模式，如工厂模式、单例模式、装饰器模式等，帮助学生理解如何在实际开发中应用面向对象设计原则。通过这些讲义，学生不仅能够掌握数据结构的基本知识，还能学会如何使用面向对象的设计思想来解决实际问题，为未来更深入的计算机科学学习打下坚实的基础。

n x[0] x[5] m

Figure 2.1: The layout of memory on the stack for the declaration above.

was. When the function ﬁnishes, its memory block is made available for other purposes again. Again, for

statically allocated variables, the compiler can take care of all of this.

2.1 Scoping of Variables

While we are talking about local variables and the st ack, we should brieﬂy talk about the scope of a variable.

Global variables are, of course, accessible to any function or any block of code in your program. Local

variables in function or code blocks only exist while the execution is in the function or the code block. It is

typically stored on the stack. As soon as the funct ion or blo ck terminates, the variable is deallocated.

When the execution of a function is temporarily suspended, for i ns t ance because another function got

called inside this one, the variables are stored on the stack, but not active, so they cannot be accessed.

Consider the following example:

void foo (int x)

{

int y;

// do some stuff

}

void bar (int n)

{

int m;

foo (n+m);

// do more stuff

}

Here, when bar calls foo, the function foo cannot access the variables n or m. As soon as foo ﬁnishes,

the variables x and y are deallocated, and permanently lost. bar now resumes and has access to n and m,

but not to x or y.

You will sometimes have multiple variables ( in diﬀerent parts of your co d e) sharing the same name. For

instance, you may have both a global variable n and a local variable in a function called n. Or you could

have something like the following:

void foo (int n)

{

int m = 10;

// do something

for (int i = 0; i < m; i ++)

{

int n = 3, m = 5;

// do something

cout << n << m;

}

Here, the cout << n << m statement would output the inner mos t versions, so the values 3 and 5. As

a general rule, when there are multiple variables wit h the same name, any reference is to the one in the

smallest code block enc losi ng the statement that contains that variable.

2.2 Dynamic allocation

Unfortunately, things aren’t qu it e as easy as statically allocated arrays when we don’t know at compile ti me

how much memory a variable will n ee d. Suppos e we want to do something like the following:

int n;

cin>>n;

// create an array a of n integers

Here, at compile time, the compiler does not know how much memory the array will need. It can therefore

not allocate room for a variable on the stack

. Instead, our p r ogram n e ed s to exp li cit ly ask the operating

system for the right amount of space at run-time. This memory is assigned from th e heap

space.

The diﬀerence between static and dynamic memory allocation is summarized in the f ollowing table. To

fully unders tand how dynamic memory allocation works, we need to spend some time on pointers.

Static allocation

Dynamic allocation

Size must be kn own at compile time Size may be unkn own at compile time

Performed at compile time Performed at run time

Assigned to the stack

Assigned to the heap

First in last out No particular order of assignment

Table 2.1: Diﬀerences between statically and dynamically allocated memory.

2.3 Pointers

A pointer is an “integer” that points to a location in memory — speciﬁcally, it is an address of a byte

In C/C++, pointer types are declared by placing a star ‘*’ behind a regular type name. Thus, int

*p; char *q; int **b; void *v; all declare pointers. In princ ipl e, all these ar e just addresses of some

memory location, and C/C++ d oes not care what we store there . Declaring them with a type (such as int)

is mostly for the programmer’s beneﬁt: it may prevent us from messing up the use of the data stored in the

location. It also aﬀects the way some arithmetic on memory locations is done, which we explain below.

Two of the ways in which “regular” variables and pointers often interact are the following:

1. We want to ﬁnd out where in memory a variable resides, i.e., get the pointer to that variable’s location.

2. We want to treat the location a pointer points to as a variable , i.e., access the data at that location,

by reading it or overwriting it.

The following piece of code illustrates some of these, as well as pitfalls we might run into.

Technically, this is not quite true. Some modern compilers let you deﬁne arrays even of dynamic sizes, bu t we advise against

using this functionality, and instead do things as we write in these notes.

This is called the heap space since it can be selected from any portion of the space that has not been allocated already.

While the stack remains nicely organized, memory in the heap tends to b e more messy and all over the place. Hence the name.

This means that all pointers are of the same size, and that the size of pointer used by a computer places a limit on the size

of memory it can address. For example, a computer using typical 32-bit pointers can only use up to 2

bytes or 4 gigabytes

of memory. The mod ern shift to 64-bit architectures turns this to 2

bytes, which will be enough for a while.

int* p, *q; //Pointers to two integers

int i, j;

i = 5; j = 10;

p = &i; //Obtain the address of i and save it to p

cout << p; //Prints the value of p (address of i)

cout << *p; //Prints the value of the integer that p points to (which is the value of i)

*p = j; // Overwrites the value of the location that p points to (so, i) with the value of j

*q = *p; // Overwrites the value of the location that q points to with the one that p points to

q = p; // Overwrites the pointer p with q, so they now point to the same location

A few things are worth noting here.

1. The last two commands both result in *p being equal to *q, but in diﬀerent ways. In the ﬁrst case, we

copy the value from one location to the other, while in the second, we make both point to the same

place.

2. The se cond -t o-last command is very risky, and will likely cause a run-time error. We have not initialized

q, so it points to an arbitrary memory location, quite possibly location 0. We are trying to overwrite it,

which most likely the program is not all owed to do. The location may b e long to the operating sys t em

or some other program

3. NULL is a special pointer we use for an uninitialized pointer variable, or to express that a pointer is not

pointing anywhere. If we try to writ e *p when p == NULL, we get a runtime error. In a sense, NULL is

really just another way of saying 0; we said above that pointers are just numbers, and the NULL pointer

points to memory location 0. In C++11, there is a new keyword for this, namely nullptr. If you set

the compiler ﬂags to compile C++11, you can/should use nullptr instead of NULL.

4. In fact, the earlier observation about the perils of uninitialized pointers suggests that whenever you

have a pointer variable, you always assign it NULL r i ght away as you declare it. So in our example,

we should have written int *p = NULL, *q = NULL; That way, if we later forget to assign it before

dereferencing, at least, it will cause a crash of our program, rather than possibly processing some

garbage that it reads from the location. This is good coding practice to reduce your debug time.

5. & and * are inverses of each other. Thus, &*p and *&p are the same as p. (The exception is that &*p

throws a runtime error when applied to p==NULL, instead of being equal to p.)

In general, it is quite easy to mess up with pointers. A few rules of thumb (which we dis cu s s ed in c lass )

will weed out common mistakes, but generally speaking, it is easy to forget to assign a pointer correctly,

resulting in run-time errors.

We discus se d before that pointers are basically just integers. They diﬀer in that arithmetic is somewhat

diﬀerent. W h en you h ave a pointer p to an int, and you wri te p+1, the compile r assumes that what you want

is the address where the next integer will start, which is 4 bytes later. Thus, the actual add r es s r ef er en c ed

by writing p+1 is actually 4 bytes after the address of p.

This is where the type of pointer matters, as we hinted at above. When you have a void*, t he n addition

really does refer to adding individual bytes. For all others, when you wr ite p+k for a pointer p and integer

k, this references memory location p+k*size(<type>), where <type> is the type of the pointer p.

2.4 Dynamic Memory Allocation

In order to dynamically allocate and deallocate memory, there are two pairs of functions, one in C style

and one in C++ style. In C, the fun ct ion for allocating memory is malloc, and for deallocation free. In

C++, the functions are new and delete. We will ﬁrst discuss the C style, as it is a little closer to the actual

low-level implementation; we’ll then see the C++ style, which shields us from s ome of the low-level details.

Fortunately, nowadays, all that happens is that your program throws a run-time error. In the past, the OS would often

allow you to do such an overwrite, in which case often some complete system crashes would happen.

2.4.1 C Style

The function void* malloc (unsigned int size) requests size bytes of memory from the operating sys-

tem, and returns the pointer to that location as a re s ul t. If for some reason, the OS f ailed to allocate the

memory (e.g., there was not enough memory available), NULL is returned instead. The function void free

(void* pointer) releases the memory located at pointer for reusing. A solution to our earlier problem of

a dynamically sized array could look as follows:

int n;

int* b;

cin >> n;

b = (int*) malloc(n*sizeof(int));

for (int i=0; i<n; i++)

cin >> b[i];

In order to re qu es t space for n integers, we need to ﬁgure out how many bytes that is. That’s why we

multiply with sizeof(int). Using sizeof(int) is much better than hard-coding the constant 4, which

may not be right on some hardware now or in the future.

Because malloc returns a void* (it does not know what we want to use the memory for), and we want

to use it as an array of integers, we need to cast it to an int*.

For good coding practice, we sh ould probably also check whether b==NULL before dereferenci ng it, but

this example is supp ose d to remain short.

Another t hin g to observe here is that we can reference b jus t like an array, and we write b[i]. The

compiler treats this ex act ly as *(b+i), and, as you probably remember from the part about pointer arith-

metic, this points to the i

entry of the array. In fact, that’s exactly how C/C++ internally treats all arrays

anyway; basically, they are just pointers.

If we wanted t o wr it e b[i] i n a complicated way by doing all th e pointer arithmetic by hand, we could

write instead *((int*) ((void*) b + i*sizeof(int))). Obviously, this is not what we like to type (or

have to understand), but if you understand everything that happens here, you are pr ob ably set with your

knowledge of pointer arithmetic and casting.

To return the memory t o the OS after we’re done using it, we use the function free, as follows:

free(b);

b = NULL;

Note that free does nothing to the pointer b i ts el f; it only deallocates the memory that b pointed to,

telling the operating system that it is available for reuse. Thus, it is recommended that you immediately set

the pointer to NULL so that your code does not attempt to tamper with invalid memory. If you reference b

somewhere, you’ll just get a runtime error. If you don’t set b=NULL, the OS may give the memory to another

variable, and you accidentally reference/overwrite that one. That kind of mistake can be much harder to

detect, and is easily avoided by setting the pointer to NULL immediately after deallocating it.

2.4.2 C++ Style

C++ provides the new() and delete() functions that provide some syntactic sugar to C’s malloc() and

free(). Basically, th ey relieve you from the calculations of the number of bytes needed, the casting of

pointers, and provide a more “array-like” syntax. Our example now looks as follows:

int n;

int *b;

cin >> n;

b = new int[n];

Notice that there are no parentheses, but instead, we have brackets for the number of items. new ﬁgures out

by itself how much memory is needed, and retur n s the correct type of pointer.

If we wanted space for just one integer, we could write int *p = new int; While this is not really very

useful for a single integer, it will become very central to allocating objects later, where we often allo c ate one

at a time d yn amically.

To release memory, the equivalent of free is the delete operator, used as follows:

delete [] b;

delete p;

The ﬁr s t example deallocates an array, while the second deallocates a single instance of a variable (a single

int in our example). Thi s deallocates the memory pointed to by the pointers. As with free, it still leaves

the pointers themselves pointing to the same memory location, so it is good style to write b = NULL or p =

NULL after the delete commands.

2.5 Memory Leaks

Let us look a little mor e at the things that can go wrong with dynamic memor y allocation.

double *x;

...

x = (double*) malloc(100*sizeof(double));

...

x = (double*) malloc(200*sizeof(double)); // We need a bigger array now!

...

free(x);

This code will compile just ﬁne, and most likely will not crash, at least not right away. We corre ct ly

allocate an ar r ay of 100 double, use it for some computation, and then allocate an array of 200 double when

we realize that we need more memory.

But notice what happens here. The moment we do the second allocation, x gets overwri tte n with a

pointer to the newly allocated memory blo ck. At that point, we have no more recollection of the pointer to

the previous memory block. That means we cannot read it, write it, or fr e e it. When at the end of the code

snippet, the program calls free(x), it s u cc es s fu lly frees up the second allocated block, but we are unable

to tell the operating system th at we don’t need the ﬁr s t block any more. Thus, those 800 bytes will never

become availabl e again (until our program terminates — but for all we know, it may run for several years

as a backend server somewhere).

This kind of situ ation is called a memory leak : available memory is slowly leaking out of the system. If

it goes on long enough, our program may run out of memory and crash for that reason. It could be quite

hard to diagnose why the crash happened if it does after a long time of running.

It is good practice to keep close track of the memory blocks you reserve, and make sure to free (or

delete) memor y pointed to by a pointer before reassigning it

. A better version of the code above would

be the following:

double *x;

...

x = (double*) malloc(100*sizeof(double));

...

free(x);

x = NULL;

There are tools for checking your code for memory leaks, and we recommend familiarizing yourself with them. The most

well-known one, for which the course web page contains some links, is called valgrind.

剩余243页未读，继续阅读

安静的攻城狮

粉丝: 3
资源: 6

CSCI104数据结构与面向对象设计讲义

Classnotes 开源OCR：手写扫描转文本新体验

掌握ClassNotes：高效笔记管理的秘诀

数据结构教学课件：第六章 - 通用树结构详解

PythonNotes:Python Notes，一些algorithmdatastruct和leetcode的答案

INTRODUCTION TO PYTHON SCRIPTING FOR MAYA ARTISTS.

Python3.7 dataclass入门与实战技巧

"学习C String与String Class的实现方法与操作符重载

白色简洁风格的韩国个人网页源码下载.zip

倒车雷达51单片机超声波测距（含仿真）

白色宽屏风格的室内设计公司整站网站源码下载.zip

最新资源