Article From:

20172310 2017-2018-2″ program design and data structure “Tenth weeks learning summary

the summary of the content of the teaching material

this week we learn the thirteenth chapter.

  • Set and data structure
    • A collection is an object, similar to a repository for saving other objects. We often use collections to represent an object that is dedicated to preserving elements, and it also provides management such as adding, deleting, and so on.
      The service of the saved element.
    • The set is isomorphic, implying that the collection holds all the same objects of the type; others are heterogeneous, that is, the collection can hold all kinds of objects.
    • Separation interface and Implementation:
      1、An abstract data type (ADT) is a set of data and concrete operations implemented on that data. A ADT has a name,
      A range and a set of operations that are allowed to be executed. The details of ADT how to save data and execute methods are separated from their concepts. In essence, “set” and “abstract data type” are interchangeable equivalent concepts.
      2、Objects have well-defined interfaces, thus becoming a perfect mechanism for implementing collections.
  • Dynamic representation of data structure

    • Arrays are one way to represent lists, but arrays can only have fixed size and not dynamic during their existence.
    • The size of dynamic data structure grows and shrinks with demand.
    • A dynamic data structure is implemented in a chain.
    • By saving and updating object reference, we can manage a linked list.
  • Linear data structure
    Queues and stacks

    • Queue (queue): similar to the list, but the queue element access mode has limited, queues take advanced first out (FIFO) access, that is similar to the situation we queued in life, we are from the end of the team, the team first out of the team.

    • Stack (stack): the stack is similar to the queue, and the difference lies in the way the element is accessed. It is an access to the forward first out (LIFO), that is, the stack element enters and moves out of the stack at the same end of the stack, and the last move is the first emigration.
  • Nonlinear data structure
    Tree and graph

    • Tree (tree): a nonlinear data structure consisting of a node and multiple nodes of a structured hierarchical structure (all nodes outside the root node are called internal nodes without subnodes.
      Note that from top to bottom a tree, the root node is at the top level, and the leaf nodes are at the bottom.
      Key concept: tree is a kind of non data structure that organizes data based on hierarchical structure.
    • There are no more than two sub nodes per node on the binary tree (two tree).

    • Figure (graph): there is no initial entry point similar to the root node in the graph. In a graph, the connection between one node and another node is called edge, and the number of edges of each node in a graph is not limited.

Nonlinear structure diagram of data structure

  • JavaCollection class API
    • JavaThe collection class API is a set of classes in the Java standard class library, representing different types of aggregation. In this group, most of the class names show the set type and its basic implementation methods. Such as ArrayList and LinkedList. –
    • Generics: the class defined in the Java collection class API is defined as generics, which means that the type of objects managed by a set is determined when the collection object is instantiated.
    • Generics ensure compatibility of object types in collections.
    • When setting up a collection, if the type of objects that may be stored in the collection is not specified, the default is defined as the Object type, that is, the set can store any type of object.

problems and solutions in textbook learning

  • Question 1: why is the object especially suitable for the abstract data type? When I see this problem, I think I may not have enough understanding of the concept of “object”.
  • Problem 1 solution: the previous understanding is that a class is a collection of entities with some common features, which is an abstract data type, and it is an abstraction of the same characteristic entity. In object-oriented programming languages, classes are abstractions of the properties and behaviors of a class of things.
    The object is a real world entity, the object and the entity are one-to-one correspondence, meaning that every entity in the real world is an object, so the object is a specific concept.
    Class is a collection of objects, objects are instances of classes; objects are generated by new className, and are used to call classes.
    This understanding is right, but I do not see the way behind him to achieve it more fundamentally.
    ADTIt is a set of operations that contain data and apply them to these data types.Objects are actually entities that encapsulate related variables and related methods.。The object hides the implementation details behind ADT and separates the interface from the underlying implementation, so that the interface will not be affected if the implementation changes.

  • Question 2:class Node { int info; Node next; }

    Instantiate two Node objects and make the variable next of a Node object point to another Node object, thus two
    The objects are linked together. The reference variable next of the second objects can point to more three Node objects.
    Take a chain list.

I thought I understood the sentence and understood the structure of the chain, but when I realized the method of inserting and deleting the list, I found that I didn’t understand it at all. (;´д`)ゞ
So how does the list understand? And what’s the relationship between the linked list and the LinkedList? What are the advantages of using linked lists for data management?

  • Problem 2 solution:

    • For the first question mark: I had a good look at some of the examples in the textbook, and I felt that the key I didn’t understand was to understand the concept of pointers and next. The linked list is the same type of structure with its own pointer (pointer is just a function of instruction, my understanding is to show that now.Where a node is located, where the next operation is going to take place, and a chain connected in a certain sequence. Give a simple example for analogy: structnode{inta; structnode*next;}; put the structure of the list node strucTnode is regarded as a human being. The next pointer in the structure is regarded as a hand of a human being. This hand can only be used to point to people (others or themselves). If there are many people in a row, each person raises his right hand to the right person, and forms a linked list of one person.
    • LinkedListClass (link list)
      LinkedListThe List interface is implemented and the null element is allowed. But in addition to all the methods in List, there are methods such as get, remove, insert, and the beginning and the most ending elements, which make LinkedList a stack, queUE and double-end queue (Deque).
      LinkedListEach object is stored in a separate memory space, and the index of the next link is also kept in each space (if it is a two-way chain, it also saves the index of the last link. ” Java is a two-way chain list.)

Sequential access is optimized, inserting and deleting List in the middle is not expensive, and random access is relatively slow (because LinkedList must be searched from scratch and replaced by ArrayList). It has methods addFirst () (), addLast (), getFirst (), getLast (), removeFirst (), removeLast (), linkedList are also not synchronized.

Give you a detailed reference to the Linked List chain.

  • A linked list is a dynamic structure, usually comparing it to a static array.

    Relative to the array:
    Advantages: the array elements can be accessed quickly through index (array subscript).
    Disadvantages: insert / delete elements need to adjust the array, which is inefficient.

And the list:
Advantages: insert / delete is fast and does not need to adjust the whole list.
Disadvantages: can only be accessed sequentially, and can not be accessed randomly (using subscript like arrays).

And gave me a little experience. I must pay attention to the conditions of circulation.

code trusteeship

the summary of the wrong questions in last week’s examination

  • The wrong question 1 and its reasons and understanding

If J equals the length of a, returns false; if the length of the j=b is not equal to the length of a and returns true; neither the length of a nor the length of B is not equal to the length of B, then the recursive computation (a, B, j+1) is called. My interpretation at that time was reversed, only when the length of a was greater than that.The length of the B will return to true.

  • The wrong question 2 and its reasons and understanding

The case of recursion is to call your own method with the same parameters, so n will not change, so if (n-0) is initially correct, it is still correct. But when n&gt, 0, it can never be the basic situation. I understand logic, but the options are not well understood.

  • The wrong question 3 and its reasons and understanding

    AOption means that when a method calls itself, direct recursion occurs, and indirect recursion occurs when there is intervention.
    There was no understanding of what intervention was at the time.
    Direct recursion means that a method calls itself directly instead of using an intermediate method. Indirect recursion occurs when there are one or more intermediate methods before the original method is called again.

this time.Most of the topics are to see if we can understand the logic of the code, so this time is a long time, because it’s a little bit clear about what the code is going to do step by step. This time it is easy to make mistakes because the logic is not clear. When you write your own code to achieve recursion, you must design it well.

pairing and mutual evaluation

review template:

  • What is worth learning or problems in the blog:
    • The summary of this week’s textbook is relatively simple, but the key points are summarized.
    • Each blog has good teaching materials and is worth learning.
  • What is worth learning or problems in the code:
    • The process description is very clear and the problem is solved well.
  • Reference examples

  • This week’s pair of pair learning
    • 20172309

    • Pair learning content
      • Experiment three agile development and XP practice
      • The thirteen chapter of the textbook
  • Blog comments on each other last week
    • 20172309
    • 20172310

learning progress bar”

Number of lines of code (New / cumulative)Blogs (New / cumulative)Learning time (New / cumulative)Important growth
target5000That’s ok30piece400hour
First week127/1271/125/25
Second weeks278/4051/220/45
Third weeks442/8471/320/65
The fourth week1063/19102/530/95
Fifth weeks840/27501/627/122
Sixth weeks631/33811/720/142
Seventh weeks914/42951/820/162
Eighth weeks2534/68292/1030/192
Ninth weeks252/70813/1326/218
Tenth weeks630/77111/1427/245


  • 《JavaCourse of program design and data structure (Second Edition)

  • 《JavaTutorial of program design and data structure (Second Edition)

  • Nonlinear structure diagram of data structure

Leave a Reply

Your email address will not be published. Required fields are marked *