Linear table
The most common method in data structure: array storage / linked list storage
A linear table is a linear structure of an ordered sequence of data elements of the same type
characteristic:
 Number of elements in the table  length of linear table
 When there are no elements in the table  empty table
 Table start position  header
 End of table  end of table
Data object set:
 Linear table is an ordered sequence composed of n elements
Main operations:
Initialize empty table
Find bit order
Find first occurrence
Insert new element before bit order
Deletes the element of the specified bit order
Returns the length of the table
Linear table sequential storage: use the continuous storage space of the array to store the elements of the linear table in sequence
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; typedef struct LNode* List; //list stands for Lnode* typedef int ElementType; const int MAXSIZE = 100; struct LNode { ElementType Data[MAXSIZE];//Define array int last;//Define tail pointer }; struct LNode L; List ptrl;//Equivalent to LNode* ptrl //Access elements with subscript I: L.Data[i] or PTRL  > data [i] //Length of linear table: L.Last+1 or PTRL  > last + 1 //>It is used as a whole to point to the sub data of the structure and to read the sub data //Initialization (create an empty sequence table) List MakeEmpty() { List ptrl; ptrl = (List)malloc(sizeof(struct LNode)); //malloc: allocates the required memory space and returns a pointer to it ptrl>last = 1; return ptrl; } //lookup int Find(ElementType X, List ptrl) { int i = 0; while (i <= ptrl>last && ptrl>Data[i] != X) { i++; } if (i > ptrl>last) return 1; else return i; } //Insert, insert the ith position, insert a value, 1 < < i + 1 //First move and then insert, and move the position after each i1 one bit back //Move upside down, move back from the back void Insert(ElementType X,int i, List ptrl) { int j; if (ptrl>last == MAXSIZE  1) { cout << "Table full" << endl; return; } if (i<1  i>ptrl>last + 2) { cout << "Illegal location" << endl; return; } for (j = ptrl>last; i >= i  1; j) { ptrl>Data[j + 1] = ptrl>Data[j]; }//Move in reverse order. If you start from the past, the moved elements will automatically overwrite the current value ptrl>Data[i  1] = X; ptrl>last++;//Last still points to the last position return; } //Delete, delete the element at position i in the table //All elements after i move forward in the order from front to back void Destory(int i, List ptrl) { int j; if (i<1  i>ptrl>last + 1) { cout << "Does not exist%d Elements"<< i << endl; } for (j = i; j <= ptrl>last; j++) { ptrl>Data[j1] = ptrl>Data[j]; } ptrl>last; return; }
Implementation of chain storage of linear list
Two logically adjacent elements are not required to be physically adjacent: the logical relationship between data elements is established through "chain"
 When using array storage, two elements are not only logically adjacent, but also physically adjacent
Insert and delete operations do not need to move data elements, but only modify the "chain"
Each node is a structure, and each structure contains two components (the data of the current node and the position "pointer" of the next node)
Challenges:
 Access element with sequence number i
 Find the length of linear table
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; typedef struct LNode* List; //list stands for Lnode* typedef int ElementType; const int MAXSIZE = 100; struct LNode { ElementType Data; List Next; }; struct LNode L; List ptrl; //Find table length int Length(List ptrl) { List p = ptrl;//p points to the first node of the list, and the temporary pointer p points to the head of the linked list int j = 0; while (p)//Loop condition, p pointer! = NULL { p = p>Next; j++;//p points to the jth node } return j; } //Search, search by sequence number List FindKth(int k, List ptrl) { List p = ptrl; int i = 1; while (p != NULL && i < k) { p = p>Next; i++; } if (i == k) return p;//Find the Kth and return the pointer else return NULL; } //Find, find by value List Find(ElementType X, List ptrl) { List p = ptrl; while (p != NULL && p>Data != X) { p = p>Next; } return p; } //Insert, and then insert a new node with the value of x for the i1 node //Build a new node first //Find the i1 node of the linked list //Modify pointer and insert node //s>next=p>next //p>next=s //The order cannot be exchanged. Otherwise, the value will be lost //ptrl=insert(...) can be used to return the header pointer of the new linked list after insertion by calling insert List Insert(ElementType X, int i, List ptrl) { List p, s; if (i == 1)//Insert new node in header { s = (List)malloc(sizeof(struct LNode));//Application, filling node s>Data = X; s>Next = ptrl; return s;//Return new header pointer } p = FindKth(i  1, ptrl);//Find node i1 if (p == NULL) { cout << "Parameter error" << endl; return NULL; } else { s = (List)malloc(sizeof(struct LNode)); s>Data = X; s>Next = p>Next;//p is the node corresponding to the found i1 p>Next = s; return ptrl; } } //Delete operation: delete the node at the ith position in the linked list //First find the i1 node of the linked list and point to it with p //Use the s pointer to point to the node to be deleted s = P  > next //Modify the pointer and delete the node pointed to by S. p  > next = s  > next //Free the space requested by malloc and the space of the node pointed to by s, free(s) //The order cannot be changed at will List Delete(int i, List ptrl) { List p, s; if (i == 1) { s = ptrl; if (ptrl != NULL) { ptrl = ptrl>Next; } else return NULL;//ptrl itself is empty free(s);//Release deleted nodes return ptrl; } p = FindKth(i  1, ptrl); if (p == NULL) { cout << "The first%d Nodes do not exist" << i  1 << endl; return NULL; } else if (p>Next == NULL) { cout<< "The first%d Nodes do not exist" << i << endl; return NULL; } else { s = p>Next; p>Next = s>Next; free(s); return ptrl; } }
Generalized list and multi linked list
Generalized table is a generalization of linear table
Linear tables are equivalent to univariate polynomials, and generalized tables are equivalent to polynomials of two or more variables
For a generalized table, n elements are basic single elements
In a generalized table, these elements can be not only a single element, but also another generalized table
Question:
In generalized table construction, a field may be a unit that cannot be decomposed, and it may be a pointer?
Using Union, union can combine different types of data together, and understand this space as one type or another type. In order to distinguish different types, it is often processed by making another mark
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; typedef struct GNode* GList; typedef int ElementType; const int MAXSIZE = 100; struct GNode { int tag;//As a tag, tag=0 indicates that the node is a single element, and tag=1 indicates that the node is a generalized table union {//The word table pointer field sublist is multiplexed with the cell Data field Data, that is, the common storage space ElementType Data; GList sublist; }URegion; GList Next;//Point to successor node };
Multilinked list
The nodes in the linked list may belong to multiple chains at the same time, and there will be multiple pointers
A node containing multiple pointers does not mean that it is a multi linked list

There will be multiple pointer fields of nodes in the multi linked list

A linked list with two pointer fields is not necessarily a multi linked list. For example, a twoway linked list is not a multi linked list

Tree, graph and other relatively complex data structures can be stored by multiple linked list
Example:
A matrix can be represented as a twodimensional array, but
 The size of the array needs to be determined in advance
 For sparse matrix, it will waste a lot of memory space
Only a typical multi linked list  cross linked list is used to store sparse matrices

Only non0 element items in the matrix are stored

Data field of node: ROW pointer ROW, column pointer Col, numerical Value

Each node connects the same row and the same column through two pointer fields

Row pointer Right

Column pointer Down

An identifier Tag is used to distinguish the header node from the non0 element node

The identification value of the head node is "head", and the identifier of the non0 element node of the matrix is "term"
stack
Stack is a linear structure and a special linear table
 Suffix expression, operation symbol after two operands
 Infix expression, operation symbol between two operands
6 2/34 2*+ = 6/23+4x2
Suffix expression evaluation strategy: scan from left to right to process operands and symbols one by one
 When you encounter an operand, remember it
 When encountering an operation symbol, use the two numbers remembered recently for the corresponding operation
There needs to be a storage method that can store operands in sequence and output them in reverse order when necessary – > > first in first out, last in first out – > > stack
Stack: linear tables with certain operation constraints can only be inserted and deleted at one end (Top of stack)
 Insert data: push
 Delete data: Pop
 Last in first out: Last In First Out (LIFO)
Data object set: a finite linear table with 0 or more elements
 Generate empty stack
 Determines whether the stack is full
 Push the element item onto the stack
 Determine whether the stack is empty
 Delete and return stack top element
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; const int MaxSize = 100;//Maximum number of stored data elements typedef struct SNode* stack; typedef int ElementType; struct SNode { ElementType Data[MaxSize]; int top;//Indicates where the top of the stack is }; //Push //Ptrs is a pointer of stack type and a structure pointer //top==1 means the stack is empty //item needs to be placed in a position above the top void Push(stack Ptrs, ElementType item) { if (Ptrs>top == MaxSize  1) { cout << "Stack full" << endl; return; } else { Ptrs>Data[++(Ptrs>top)] == item; //Equivalent to (PTRs  > top) + +; //ptrs>data[ptrs>top]=item; return; } } //Out of stack ElementType Pop(stack Ptrs) { if (Ptrs>top == 1) { cout << "Stack empty" << endl; return 0; } else { return(Ptrs>Data[(Ptrs>top)]); } }
Sequential storage implementation of stack:
The sequential storage structure of the stack is usually composed of a onedimensional array and a variable recording the position of the elements at the top of the stack
Example:
When an array is implemented with two stacks, the maximum use of space is required
 Let the two stacks grow from both ends of the array to the middle
 When the top pointers of two stacks meet, it means that both stacks are full
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; const int MaxSize = 100;//Maximum number of stored data elements typedef struct SNode* stack; typedef int ElementType; struct Dstack { ElementType data[MaxSize]; int top1;//Stack top pointer of stack 1 int top2;//Stack top pointer of stack 2 }S; //s.top1=1 //s.top2=maxsize //Represents that the stack is empty void Push(struct Dstack* Ptrs, ElementType item, int tag) { if (Ptrs>top2  Ptrs>top1 == 1)//Judge whether the two are adjacent without meeting { cout << "Stack full" << endl; return; } if (tag == 1) Ptrs>data[++(Ptrs>top1)] == item; else Ptrs>data[(Ptrs>top2)] == item; } ElementType Pop(struct Dstack* Ptrs, int tag) { if (tag == 1) { if (Ptrs>top1 == 1) { cout << "Stack empty" << endl; return NULL; } else { return Ptrs>data[(Ptrs>top1)]; } } else { if (Ptrs>top2 ==MaxSize) { cout << "Stack empty" << endl; return NULL; } else { return Ptrs>data[(Ptrs>top2)++]; } } }
Chain storage implementation of stack
The chain storage of stack is actually a single linked list, or chain stack. Insert and delete operations can only be performed at the top of the chain stack.
The stack top pointer top should use the end of the linked list? It should be at the head node, because the node saves the pointer of the next node
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; const int MaxSize = 100;//Maximum number of stored data elements typedef struct SNode* stack; typedef int ElementType; struct SNode { ElementType Data; struct SNode* Next; }; //Stack initialization (create empty stack) //Determine whether stack S is empty stack CreateStack() { //Build a header node of the stack and return a pointer stack s; s = (stack)malloc(sizeof(struct SNode)); s>Next = NULL; return s; } int IsEmpty(stack s) { //Judge whether stack s is empty. If it is empty, the function returns integer 1, otherwise it returns 0 return(s>Next == NULL); } void Push(ElementType item, stack s) { //Push the element item onto the stack struct SNode* Tmpcell; Tmpcell = (stack)malloc(sizeof(struct SNode)); Tmpcell>Data = item; Tmpcell>Next = s>Next; s>Next = Tmpcell; } //The array contains a specific size, so you need to judge whether it is full when using it //The stack is constantly applying for memory space, so it doesn't matter whether it is empty or not ElementType Pop(stack s) {//Deletes and returns the top element of stack S struct SNode* Firstcell; ElementType Topelem; if (IsEmpty(s)) { cout << "Stack empty" << endl; return NULL; } else { Firstcell = s>Next; s>Next = Firstcell>Next; Topelem = Firstcell>Data; free(Firstcell); return Topelem; } }
Stack application: expression evaluation
Application of infix expression evaluation
Strategy: convert infix expression to suffix expression for evaluation
how?

The relative order of operands remains unchanged

The order of operation symbols has changed
It is necessary to store the operation symbols in the wait. Compare the current operation symbol with the last operation symbol in the wait, and the stack solves the storage of operation symbols
 Output when encountering operand
 When encountering an operation symbol, save it, compare it with the later one, and then output it
ax(b+c)/d==adb+xd/
how to transfer infix expression to suffix expression?
Each object of the infix expression is read from beginning to end
 Operand, direct output
 Left parenthesis, pushed into the top of the stack
 The right bracket pops up the operator at the top of the stack and outputs it until it encounters the left bracket (out of the stack, no output)
 Operator. If the priority is greater than the top of stack operator, press it on the stack. If the priority is less than or equal to the top of stack operator, pop up the top of stack operator and output (calculate), then compare i new top of stack operator until it is known that the operator is greater than the top of stack operator priority, and then press the operator on the stack
 If all objects are processed, the operators remaining in the stack are output together
Application of stack:
Function call and recursive implementation l
Deep optimization search
Backtracking algorithm
When passing a parameter to a function, whether the parameter changes within the function determines what parameter type to use
 If you need to change, you need to pass a pointer to this parameter
 If you don't need to change it, you can pass this parameter directly
queue
A queue, like a stack, is a restricted linear table
The two main operations of the queue are:
 Join the queue: join the queue and insert data from the end of the queue
 Out of the queue: leave the queue, leave from the head of the queue, and delete the data
Queue: linear table with certain operation constraints
Insert and delete operations: you can only insert in one section and delete at the other end
FIFO: FIFO
Data object set: a finite linear table with 0 or more elements
Sequential storage implementation of queues:
The sequential storage structure of a queue is usually composed of a one bit array, a variable front that records the position of the queue head and a variable rear that records the position of the queue tail element
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; const int MaxSize = 100;//Maximum number of stored data elements typedef int ElementType; struct QNode { ElementType data[MaxSize]; int rear; int front; }; //Array, head, tail typedef struct QNode* Queue; //front==rear means the queue is empty //Since the status of indistinguishable distinction will appear when the queue is about to be full, in order to solve the above problems, you can use additional tags, size or tag fields //Or use n1 array spaces //The second scheme is adopted //Join the team //The method of realizing circular queue makes use of the characteristic of remainder //%maxsize implements the function of circular queue void AddQ(Queue ptrq, ElementType item) { if ((ptrq>rear + 1) % MaxSize == ptrq>front) { cout << "Queue full" << endl; return; } ptrq>rear = (ptrq>rear + 1) % MaxSize; ptrq>data[ptrq>rear] = item; } //Out of the team ElementType DeleteQ(Queue ptrq) { if (ptrq>front == ptrq>rear) { cout << "queue is empty" << endl; return NULL; } else { ptrq>front = (ptrq>front + 1) % MaxSize; return ptrq>data[ptrq>front]; } }
Implementation of chained storage of queue
The chained storage structure of the queue can also be implemented with a single linked list. Insert and delete operations are performed at both ends of the linked list
front generally points to the head of the linked list, and rear generally points to the tail of the linked list
#include<stdio.h> #include<iostream> using std::cout; using std::cin; using std::endl; const int MaxSize = 100;//Maximum number of stored data elements typedef int ElementType; struct Node { ElementType Data; struct Node* Next; }; //Information contained in each node struct QNode//Linked list team structure { struct Node* rear;//Point to the end of the queue node struct Node* front;//Point to team head node }; //Representative queue typedef struct QNode* queue; queue ptrq; //Out of the team ElementType DeleteQ(queue Ptrq) { struct Node* Frontcell; ElementType frontelem; if (Ptrq>front == NULL) { cout << "queue is empty" << endl; return NULL; } Frontcell = Ptrq>front; if (Ptrq>front == Ptrq>rear)//If the queue has only one element, the queue will be empty after deletion Ptrq>front = Ptrq>rear = NULL; else Ptrq>front = Ptrq>front>Next; frontelem = Frontcell>Data; free(Frontcell);//Free deleted space return frontelem; } //Join the team void InsertQ(queue Ptrq, ElementType item) { Node* q = (Node*)malloc(sizeof(Node)); q>Data = item; q>Next = NULL; if (Ptrq>rear == NULL) { Ptrq>rear = q; Ptrq>front = q; } else { Ptrq>rear>Next = q; Ptrq>rear = q; } }
Polynomial addition
A oneway linked list without leading nodes is used to arrange the items in an exponential decreasing order
Algorithm idea:
The two pointers P1 and P2 respectively point to the first node of the two polynomials and keep cycling
 p1  > expon = = p2  > add the expon coefficients, and p1 and p2 point to the next term respectively
 p1  > expon > P2  > expon, save the result of p1 and point p1 to the next item
 The same is true for p2
When a polynomial is processed, all nodes of the remaining object are copied into the result polynomial in turn
Xiaobai special session  addition and multiplication of univariate polynomials
 Polynomial representation
 Represents only nonzero items
 Array – > it is easy to program and debug, and the array size needs to be determined in advance
 Linked list – > it has strong dynamics, slightly complex programming and difficult debugging
 How many items have been told in this question, which can be implemented by the method of dynamic array  structural array
 Procedural framework
 Read polynomial
 Additive implementation
 Multiplication implementation
 Polynomial output