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 i-1 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[j-1] = 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 j-th 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 K-th 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 i-1 node
//Build a new node first
//Find the i-1 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 i-1
	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 i-1
		p->Next = s;
		return ptrl;
	}

}


//Delete operation: delete the node at the ith position in the linked list
//First find the i-1 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 two-way 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 two-dimensional 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 non-0 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 non-0 element node

• The identification value of the head node is "head", and the identifier of the non-0 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/3-4 2*+ = 6/2-3+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 one-dimensional 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 n-1 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 one-way 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 non-zero 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