This is the 23rd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

So first of all, let’s just kind of get a sense of what a linear list is.

Linear table: a finite sequence of zero or more data elements.

The 1-to-1 relationship of data elements is positional.

The number of linear table elements n (n>=0) is defined as the length of the linear table. When n=0, it is called an empty table.

 

Then we’ll look at data types and abstract data types

Data type

Why are there different data types? Quite simply, many things cannot be generalized, but require a more precise division. Computing 1+1 doesn’t require much space, but computing 10000000000+1000000000 requires a lot of space. Still can calculate decimals sometimes, the number of digits of decimals is different, the space that needs is different also. The number 1 and the letter A also needed to be distinguished, so the developers came up with the term “data type” to describe different sets of data.

The first data type I remember being exposed to was int. It was an int A; She just looked at me and she didn’t know why. A type like this is a basic data type. We used to think that data types were just a description of what data really is, but now we look at it and it’s a little shallow. A data type is a general term for a set of values and a set of operations defined in that set of values. A data type can also be thought of as an implemented “data structure.”

According to whether “value” can be decomposed, it can be divided into two categories:

Atomic types: Their values are not decomposable and are usually provided directly by the language, such as int,float,double, etc.

2. Structure type: its value can be decomposed into several parts (components), which are customized by the programmer, such as structure, class, etc.

Ps: For what is “atom”, you will often see “atomic operation”, “atomic type”, which generally means non-divisible.

Abstract data types

An abstract data type (ADT) is simply a mathematical model and a set of operations defined on the model. Usually an abstraction of data, defining a range of values and a set of operations on the data.

In fact, data types and abstract data types can be considered the same concept. For example, the integer type that all computers have is an abstract data type that has the same mathematical properties, although it is implemented in different ways.

Abstract data types are characterized by the separation of implementation from operation, thereby enabling encapsulation.

See someone cited the “Super Mario” example, feel very good writing, as follows:

For example, in “Super Mario”, the classic Nintendo game, the main character of the game is Mario. We defined the basic actions for him: forward, backward, jump, shoot bullets and so on. This is an abstract data type that defines a data object, the relationships among its elements, and operations on the data elements. As for which operation, it is up to the designer to decide according to the actual needs. Mario might only walk and jump at first, then realize that he should have a bullet action, and then hold the bullet button and then run. It all depends on the actual situation.

In fact, abstract data types embody the characteristics of problem decomposition and information hiding in programming. It breaks the problem down into smaller, manageable problems, and then implements each functional module as a separate unit, implementing the entire problem through one or more calls.

 

Finally, the sequential storage structure of linear tables

Definition 1:

The sequential storage structure of a linear table refers to the sequential storage of the data elements of a linear table with contiguous addresses.

 

2: stores attributes sequentially

I think a good example of this is arrays in a strong syntax language. A radish a pit, each element has its own fixed position.

(1) : indicates the start location of the storage space

(2) : maximum storage capacity of linear tables

(3) : the current length of the linear table

 

3: address calculation method

Notice here that the linear table starts at one.

Our subscript starts at 0.

 

 

Let’s write a small example of the linear table cis storage structure: I’m using C# here.

Examples are available for download at the end of the article.

First, define an interface class for a linear table sequential storage structure: ilinetotal.cs

/// < typeParam name="T"> Data type </ typeParam > interface ILineTotal<T> {/// <summary> /// Is empty /// </summary> /// < RETURNS ></ RETURNS > bool IsEmptyTableLine(); // </summary> T GetTableData(int index); // </summary> bool InsertTableData(T data, int Index); /// </summary> // is the maximum length /// </summary> /// <returns>true/false</ RETURNS > bool IsMaxSize(); / / / < summary > / / / / / / in the end of the insert data < / summary > / / / < param name = "data" > < param > / / / < returns > < / returns > bool InsertTableEndData(T data); /// <summary> /// /// </summary> /// <param name="index"></param> /// <returns></returns> bool DeleteTableData(int index); /// </summary> /// </returns> bool ClearTableData(); /// <summary> /// flip array /// </summary> /// < RETURNS ></ RETURNS > bool FlipTableLine(); / / / < summary > / / / return element index, if this element in the linear table / / / < summary > / / / < param name = "item" > < param > / / / < returns > < / returns > int ReturnDataIndex(T item); }Copy the code

 

Linear table sequential storage structure class: tableline.cs

/// / linear table sequential storage structure class (generic class) /// </summary> class tableLine<T> :ILineTotal<T> {/// <summary> // define an array /// </summary> public T[] TArray = null; // </summary> public int MaxSize = 0; // </summary> public int lastDataIndex = 0; /// </summary> // </summary> // < PARam name="lenght"> </ PARAM > public tableLine(int Length) {MaxSize = length - 1; // define a linear table TArray = new T[length]; } /// <summary> // Whether the linear table is empty /// </summary> /// < RETURNS ></ RETURNS > public bool IsEmptyTableLine() {try {if (TArray.GetLength(0) > 0) { return false; } else { return true; }} Catch (Exception) {console. WriteLine("IsEmptyTableLine error "); return false; } // </summary> public T GetTableData(int index) {T data = TArray[index]; // </summary> public T GetTableData(int index) {T data = TArray[index]; return data; } /// <summary> // insert data in the middle // </summary> // <param name="data"> Data to be inserted </param> // <param name="Index"> Insert subscript </param> public bool InsertTableData(T data, int Index) {try {if (IsMaxSize()) {console. WriteLine(" array is full "); return false; } lastDataIndex++; For (int I = lastDataIndex + 1; int I = lastDataIndex + 1; i > Index; i--) { TArray[i] = TArray[i - 1]; } // insert TArray[Index] = data; return true; } catch (Exception) {console. WriteLine(" Error inserting data in middle "); return false; }} /// <summary> // Is the maximum length /// </summary> /// < RETURNS ></ RETURNS > public bool IsMaxSize() {if (lastDataIndex >= MaxSize) { return true; } else { return false; /// </summary> public bool InsertTableEndData(T data) {try {// If the array exceeds the maximum length if (IsMaxSize()) { return false; } lastDataIndex++; TArray[lastDataIndex] = data; return true; } catch (Exception) {console. WriteLine(" Error inserting data at end "); return false; Public bool DeleteTableData(int index) {// dataLength int dataLength = TArray.Length; If (index > datalength-1) {console. WriteLine(" Incoming subscript out of array range "); return false; } for (int i = index; i < lastDataIndex; i++) { TArray[i] = TArray[i + 1]; } TArray[lastDataIndex] = default(T); lastDataIndex--; return true; } /// </summary> public bool ClearTableData() {try {if (tarray.length <= 0) { Console.WriteLine(" data table is empty "); } Array.Clear(TArray, 0, TArray.Length); return true; } catch (Exception) {console. WriteLine(" Error emptying linear tables "); return false; }} /// </summary> // </summary> public bool FlipTableLine() {array.reverse (TArray); return true; } /// <summary> // returns the index of the element if the element is in a linear table /// </summary> public int ReturnDataIndex(T item) {int index = Array.IndexOf(TArray, item); Return index; return index; }}Copy the code

 

Client call: program.cs

Static void Main(string[] args) {// The index of the last data int lastDataIndex = 0; // instantiate a linear table tableLine< INT > tableLineObj = new tableLine<int>(10); lastDataIndex = tableLineObj.TArray.Length - 3; for (int i = 0; i < tableLineObj.TArray.Length - 2; i++) { tableLineObj.TArray[i] = i + 1; Console.WriteLine(tableLineObj.TArray[i]); } / / last subscript assignment tableLineObj lastDataIndex = lastDataIndex; / / check to see if the linear list is empty Boolean isEmpty = tableLineObj. IsEmptyTableLine (); Console.WriteLine(" linear table empty: "+ isEmpty); Console.WriteLine("================================================================="); int fiveData = tableLineObj.GetTableData(4); Console.WriteLine(" fifth number: "+ fiveData); Console.WriteLine("================================================================="); Bool insertRes = tableLineObj. InsertTableData (100, 4); Console.WriteLine(" insert data: "+ insertRes); for (int i = 0; i < tableLineObj.TArray.Length; i++) { Console.WriteLine(tableLineObj.TArray[i]); }//*/ Console.WriteLine("================================================================="); bool insertEnd = tableLineObj.InsertTableEndData(50); Console.WriteLine(" add data to end: "+ insertEnd); for (int i = 0; i < tableLineObj.TArray.Length; i++) { Console.WriteLine(tableLineObj.TArray[i]); } Console.WriteLine("================================================================="); bool deleteRes = tableLineObj.DeleteTableData(3); Console.WriteLine(" delete specified subscript data: "+ deleteRes); for (int i = 0; i < tableLineObj.TArray.Length; i++) { Console.WriteLine(tableLineObj.TArray[i]); } Console.WriteLine("================================================================="); bool flipRes = tableLineObj.FlipTableLine(); Console.WriteLine(" reverse linear table: "+ flipRes); for (int i = 0; i < tableLineObj.TArray.Length; i++) { Console.WriteLine(tableLineObj.TArray[i]); } Console.WriteLine("================================================================="); int dataIndex = tableLineObj.ReturnDataIndex(100); Console.WriteLine("100 corresponds to subscript: "+ dataIndex); Console.WriteLine("================================================================="); /*bool clearRes = tableLineObj.ClearTableData(); Console.WriteLine(" Clear linear tables: "+ clearRes); for (int i = 0; i < tableLineObj.TArray.Length; i++) { Console.WriteLine(tableLineObj.TArray[i]); } Console.WriteLine("================================================================="); //*/ Console.ReadKey(); }Copy the code

 

That’s probably the case.

Finally, the advantages and disadvantages of sequential storage:

* * advantages:

1: No additional storage is required for logical relationships between elements in the table.

2: You can quickly access any element in the table. **

Disadvantages:

1: Insert and delete operations need to move a large number of elements

2: When the length of a linear table varies greatly, it is difficult to determine the capacity of the storage space

3: Fragmentation of storage space

For good suggestions, please enter your comments below.

Welcome to my blog guanchao.site

Welcome to applets: