catalogue

2.1 definition and characteristics of linear table

2.2 case introduction

2.3 type definition of linear table

2.4 sequential representation and implementation of linear table

2.4 supplement: parameter transfer in C + +

Implementation of basic operation of sequence table

Write after:

2.1 definition and characteristics of linear table

A linear list is a finite sequence of data elements with the same characteristics

• The elements in the same linear table must have the same characteristics and have a linear relationship with each other
• There is only one start node and one end node, and the internal nodes have only one direct forward trend and one direct successor

2.2 case introduction

• Polynomials can be expressed in the form of arrays, but sparse polynomials will cause a great waste of storage space. Multiple data items can be recorded for each element
• There are some problems in sequential storage structure: inflexible storage space allocation and high space complexity of operation
• Here, the chain structure can be used for the addition of polynomials

• Select the appropriate storage structure to realize the basic operations on the storage structure and use the basic operations to complete the functions
• The types of data elements in a linear table can be simple or complex
• The basic operations are very similar, and there is no need to write a program one-to-one

2.3 type definition of linear table

The basic operations are:

• InitList(&L), DestroyList(&L), Clear(&L)
• ListEmpty(L), ListLength(L)
• GetElem(L,i,&e), LocateElem(L,e,compare())
• PriorElem(L,cur_e,&pre_e), NextElem(L,cur_e,&next_e)
• ListInsert(&L,i,e)
• ListDelete(&L,i,&e), ListTraverse(&L,visited)

2.4 sequential representation and implementation of linear table

• Should pursue sequential storage, address continuity, no vacancy
• You can calculate the address LOCation of other elements from the address of one element

Specific implementation:

• Element type is the type of data element you need. It can be existing or structure
• Arrays can be allocated statically or dynamically

//Static allocation
typedef struct{
	ElemType data[Maxsize];
	int length;
}Sqlist

//Dynamic allocation
typedef struct{
	ElemType *data;
	int length;
}Sqlist

//For dynamic:
Sqlist L;
L.data=(ElemType*)malloc(sizeof(ElemType)*Maxsize);
//(ElemType *) is a cast type, which tells the type, divides the space, and returns a pointer
//malloc(m) is to open up an address space of M bytes and return the first address of this space
//The calculated length of the variable (si x) is
//free(p), release the storage space of the variable indicated by pointer p, that is, completely delete a variable
//Dynamically allocate space for all members of ElemType type in sequential Table L, ending the release
//Need to load header file: < stdlib h>

2.4 supplement: parameter transfer in C + +

Example 1: no change

Example 2: changed

#include <iostream>
#include <string>
void swap(float *m, float *n){
    float t;
    std::cout<<*m<<'\t'<<*n<<'\n';
    std::cout<<m<<'\t'<<n<<'\n';
    t=*m;
    *m=*n;
    *n=t;
		std::cout<<*m<<'\t'<<*n<<'\n';
    std::cout<<m<<'\t'<<n<<'\t'<<t<<'\n'<<'\n';//Output 2345 lines
    }
int main()
{
    float a,b,*p1,*p2;
    std::cin>>a>>b;
    p1=&a;p2=&b;
    std::cout<<p1<<'\t'<<p2<<'\n'<<'\n';//Output line 1
    swap(p1,p2);
    std::cout<<a<<'\t'<<b<<'\n';
    std::cout<<p1<<'\t'<<p2<<'\n';//Output 6, 7 lines
}

//Operation results
3 5//Input for this behavior
0x7f3675add6f8	0x7f3675add6fc

3	5
0x7f3675add6f8	0x7f3675add6fc
5	3
0x7f3675add6f8	0x7f3675add6fc	3

5	3
0x7f3675add6f8	0x7f3675add6fc

Example 3: no change

#include <iostream>
#include <string>
void swap(float *m, float *n){
    float *t;
    std::cout<<*m<<'\t'<<*n<<'\n';
    std::cout<<m<<'\t'<<n<<'\n';
    t=m;
    m=n;
    n=t;
		std::cout<<*m<<'\t'<<*n<<'\n';
    std::cout<<m<<'\t'<<n<<'\t'<<t<<'\t'<<*t<<'\n'<<'\n';
    }
int main()
{
    float a,b,*p1,*p2;
    std::cin>>a>>b;
    p1=&a;p2=&b;
    std::cout<<p1<<'\t'<<p2<<'\n'<<'\n';
    swap(p1,p2);
    std::cout<<a<<'\t'<<b<<'\n';
    std::cout<<p1<<'\t'<<p2<<'\n';
}

//Operation results
3 5//Input for this behavior
0x7af8d56def88	0x7af8d56def8c

3	5
0x7af8d56def88	0x7af8d56def8c
5	3
0x7af8d56def8c	0x7af8d56def88	0x7af8d56def88	3

3	5
0x7af8d56def88	0x7af8d56def8c

The author understands that in examples 2 and 3, a,b,m.n can return values, and p1,p2,m,n can return addresses. The things referenced in local functions are used temporarily, and they are thrown away when the function ends. For example, if a=3,b=5, and the formal parameters are m=a,n=b, then a or 3, b or 5 after the end of the function; The formal parameters are m = p1 and N = P2. No matter how mn changes, p1 and P2 remain unchanged after the function is executed. But if you use the referenced things to point to who did what in the process, you can keep it. For example, in example 2, the value pointed to by mn is changed, but in example 3, the mn address is simply changed, so it is true that the value pointed to by mn is ba or ab, but after execution, the address of p1p2 does not change, and the value pointed to does not change.

Example 4: it is better to use the reference type as a formal parameter for large-scale data - if there is a change, it can be regarded as m and N, which are the references of a and B respectively (in fact, the transmitted address). Compared with a person's big name and small name in life, it can not be distinguished.

Implementation of basic operation of sequence table

• For the search algorithm of sequential table, the average search length ASL should be (n+1)/2

• For the insertion algorithm of sequence table, i=1-length+1, the average number of moves should be n/2

 

• For the deletion algorithm of sequence table, i=1-n, the average number of moves should be (n-1)/2

• Advantages of sequential table: high storage density and random access to any element in the table
• Disadvantages of sequence table: some operations need to move a large number of elements; Waste storage space (length < maxsize); It belongs to static storage form, and the number of elements cannot be expanded freely

The corresponding points of these sequential tables are just solved by the linked list mentioned by the latter.

Write after:

This note is data structure and algorithm by Mr. Wang Zhuo of Qingdao University. It is a very suitable video course for postgraduate entrance examination or self-study. I will make a brief excerpt here for you to learn and communicate. Readers are very welcome to ask questions and questions, or you can contact my email for anything zqc867342167@gmail.com