Shulou(Shulou.com)06/02 Report--

When we talk about linear tables, many people may not quite understand. So let's take an example. In kindergarten, teachers always let children travel in the same party order. The essence of this example is linear tables.

So what does the linear table (List) look like? In line with the following characteristics: 1, a collection of zero or more data elements; 2, data elements are arranged in order in position; 3, the number of data elements is limited; 4, the type of data elements must be the same. So how is the abstract definition of a linear table defined? A linear table is a finite sequence of n (≥ 0) data elements of the same type. As follows

Let's take a look at the essence of List: 1, a0 is the first element of the linear table, with only one successor; 2, an-1 is the last element of the linear table, with only one precursor; 3, in addition to a0 and an-1, other elements ai, both precursor and successor; 4, direct support for itemized access and sequential access. Let's take a look at some common operations of the linear table: a > insert the element into the linear table; b > delete the element from the linear table; c > get the value of the element at the target location; d > set the value of the element at the target location; d > get the length of the linear table; e > empty the linear table.

Linear tables are represented as a special data type in the program. The definition is as follows

# ifndef LIST_H#define LIST_H#include "Object.h" namespace DTLib {template

Class List: public Object {public: List () {} virtual bool insert (const T & e) = 0; virtual bool insert (int I, const Te) = 0; virtual bool remove (int I) = 0; virtual bool set (int I, const T & e) = 0; virtual bool get (int I, T & e) const = 0; virtual int length () const = 0; virtual void clear () = 0;} # endif / / LIST_H

Let's take a look at the definition of sequential storage: the sequential storage structure of a linear table, which refers to the sequential storage of data elements in a linear table with a contiguous address. As follows

So how do we design it? One-dimensional array can be used to implement the sequential storage structure. The storage space is T * m array; the current length is int m length; the definition is as follows

Template

Class SeqList: public List {protected: T* masked array; int masks; /}

So how to implement the element acquisition operation of the sequential storage structure? One is to judge whether the target location is legal, and the other is to use the target location as an array subscript to obtain elements. The definition is as follows

Bool SeqList::get (int I, Te) const {bool ret = (0

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.