本课程是面向有C语言经验的，并想要学习C++编程的程序员们。涉及到的例子和练习需要有对基础算法和面向对象软件的理解。
3.7 List
Loading...
來自 University of California, Santa Cruz 的課程
C++ For C Programmers, Part A
390 個評分
從本節課中
Module 3
Point: Default constructor and initializing syntax. Conversion Constructors. Copy Constructor. List and dynamic memory allocation. Deep Copy.
與講師見面
Ira PohlProfessor
Computer Science
Let's more generally look at the list which
makes use of the specific list element.
What we want to think about in the list and
again lists, really important to think pictorially.
So for a list, you tend to have some kind
of header pointer.
That's the head of the list.
You also might have a cursor.
A cursor is just something that tells you where you are in the list.
So you can imagine that a list
is something like this, etc.
Sometimes we draw as an electrical engineering, a little ground diagram.
We have a head.
So conceptually this is our list.
It has data in the first elements
And then it points to next all along the line.
And if we do interesting processing as a list,
then frequently when we go across the list.
When we crawl across the list, we'll either do it through iteration or
recursion.
And most frequently we want some cursor to tell us where we are.
For example, we might wanna do a find algorithm.
Let's say we wanna see if in our list,
we have a friend, we're looking up the friend.
Is John in our list?
Maybe there's data associated with John.
So we do a search, element by element for John's personal data until we find John.
And when we find John the cursor is pointing at John and we can stop.
Maybe we'll continue the search later on from the cursor.
So, an extra cursor sitting there, rather than restarting at
the head of the list can add to the efficiency of your operations.
Also we're going to see the notion of a cursor is generalized
in the standard template library.
Some of you should already be using the standard template library.
For example, I recommended earlier that Vector is a really important,
maybe the most important, container class in the standard template library.
And it's very easy to use for anybody who's already familiar with C.
It just replaces in most instances an ordinary C array.
So in the use of the standard template library.
There is a generalization of which you might call a cursor, and
those are called iterators.
And the standard template library is all based on the use of iterators.
I say, well talk about it extensively later on.
Again, everybody out there should know what that is.
Let me hear what you're saying.
Oh, there's somebody saying it's the default constructor.
It's a default constructor because
its signature again is void and
it creates a cursor that's empty.
Again this is older code, it will work on most of your compilers.
But I might prefer in the newer standard where it's
available to just use null point here.
Now I'm gonna have a number of methods, a number of member functions
that's going to make The functionality of a list available.
So one of the things about a list is a standard
operation is inserting at the front.
So we have a list.
We decide to manufacture a new element.
And we want that new element put on the front.
So we're gonna see how to write the code for
creating an element and sticking it on the front.
If we wanna get an element, the cursor is pointing at some element,
so get element is just return cursor d, d is a data type.
So d is an int.
Again later on I'm just going to give you some thought about this.
In a standard template library this is going to be
A template.
And as a template it's going to be able to substantiate regardless of type.
And so instead of int in the standard template library you're
gonna find that that's gonna be replaced by,
if you wanna think of it, a meta notion, the meta notion of type,
so that it can be used to generate containers for arbitrary values.
Here's advance, advance is very simple.
It's your basic list operation.
If I'm sitting at the cursor, this is next.
I look at next, assign the cursor's next value to the current cursor.
So that means cursor moves over to here.
And we'll also see how to do a print.
So let's look at prepend.
Remember what we wanna do.
There's two cases.
Now this is also again, idiomatic.
So if this is review for you or new for
you, it's really important to absorb it.
Because once you absorb this kind of idiom, you can do far more complicated
things cuz most of the things involved in aggregates involve ideas of this kind.
So we typically have two important cases.
We have the simplest case.
The simplest case is where we have an empty list.
What's an empty list?
An empty list, Is a pointer,
a head pointer, that is pointing at the null
pointer value, or the zero value.
So we can test it again.
If you wanna be consistent with C11.
Go better type safety, just test it against null pointer.
That's the empty list case.
If it's the empty list, we have to create the list.
So the list wasn't around.
So we create it by using new, again new is the keyword that lets us get to the heap.
It says get me a list element whose value, this is your data value,
Is n.
And this is the existing head.
So now we replace head with the existing head, which actually had a value.
And we also start the cursor there.
So at the end of this operation.
This transforms into, we get this off the heap.
N is stored there.
The old cursor, which is again a null pointer is here.
And now what was head is pointing there and
what was cursor is pointing there.
So that's the simple case.
But it needs to be checked on and done.
And then the general case is a pre-existing list.
And all we need to do there is we need to,
the cursor's left alone, and in the general case
we just replace the old head by the value of the new list element.
So let's look at that case.
Let's just draw a circle.
Maybe I'll get rid of this, so I can draw it again properly.
Draw it in blue.
So in the second case, we have head,
we have some general list.
We have a cursor which could be pointing anywhere in the list.
Now we manufacture the new element.
The new element And it has this value h stored in it.
Well h is just pointing there.
And then the real h is now assigned the address
to what's now the new first element.
I hope by now you're getting used to my terrible handwriting.
Okay, anyway.
Everybody should be able to draw this diagram.
It's really important when you are dealing with these kind of complex aggregates,
conceptually to know what they're doing.
Very helpful.
So that's prepend.
Let's take a quick quiz on that.
For yourself, draw how prepend of 5 would work.
If you had an element that would have value 5, how would that work.
And in that assume, there's a pre existing list that had two elements.
Take a second.
Okay.
Let me get back and see what they are.
There's 7 and 3 and the null element.
So let me draw it.
So here's the existing list.
With its head.
We now create a new element.
Data element 5.
And we're creating it with the old head.
So the old head is really this address.
And then we break that connection and assign that
address using the fact that new returns the address
on the heap where you manufactured that list element.
