​

directory

One, the introduction

1. Express unary polynomial directly with sequential storage structure

2. Use the sequential storage structure to represent its non-zero items

3. Use linked lists to store non-zero items

Two, linear table

I. Definition:

Second, the abstract data type of linear table is described as follows:

Third, the sequential storage of linear tables

1. Code implementation:

2. Basic operations – initialization

3. Basic operations – search

4. Basic operation – insert

5. Basic operations – Delete

Four, linear list chain storage implementation

1. Code implementation:

2, basic operation – find the table length

3. Basic operations – search

5. Basic operations – Delete

To sum up:

Fifth, generalized table

1. Definition:

2,

3,

4. Code implementation:

Multiple linked lists

Seven, the stack

1. Definition:

2. Concept:

Abstract data type of stack:

4. Code implementation:

5. Creation of sequential stack

6. Push operation

7. Pop out of the stack

8, stack chain storage implementation

9. Code implementation:

10. Basic operations – Create, judge, pass, delete

Viii. Queue:

I. Definition:

Abstract data types:

Third, the sequential storage of the queue

Fourth, the chain storage implementation of queue

One, the introduction

In the logical structure of data, a common and simple structure is linear structure, that is, data elements form an ordered sequence.

Here’s an example:

We did an example of unary polynomials, so let’s continue with that example, and we talked about computation, so let’s talk about storage in this video. How do we store the expression of a unary polynomial in the computer?

You may have a variety of ideas, let’s sort them out:

1. Express unary polynomial directly with sequential storage structure

We found that the indices of an array correspond to the indices of the array, and we can put coefficients in the space of the indices.

This method is fine for the general case, but if the index is large and there are many zeros in between, many of the subscripts are empty, it will cause a waste of space. Therefore, in the case of sparse polynomials, only non-zero items are stored in the end to avoid space waste.

2. Use the sequential storage structure to represent its non-zero items

Each non-zero term involves two pieces of information, exponents and coefficients, so a polynomial can be thought of as a set of binary groups. For computational convenience, we can also organize the binary in order of exponential decline. So, we can think of polynomials as ordered sequences of tuples. We can store this ordered sequence in a structured array. The size of an array depends on how many non-zero items there are.

In this way, for sparse polynomial representation can save a lot of space. But if the polynomial is not very sparse, the space savings are gone, and even more space is needed.

After the two methods above we know that the sequential storage structure is an array, so what’s wrong with the array representation?

The problem with both approaches is that you’re not flexible enough to know in advance how much data you need to process, so you can’t determine the size of the array, so you waste a lot of space.

3. Use linked lists to store non-zero items

It is very simple to use linked list, data field is two elements, and then add a pointer field, with linked list to represent, space utilization efficiency is higher, but the difficulty of operation has been greatly improved.

Therefore, we can make a conclusion: the design of data structure often needs to make a compromise between algorithm comprehensibility and time and space efficiency, and select the appropriate data structure and design the corresponding algorithm for specific problems.

Two, linear table

I. Definition:

A linear list is a linear structure consisting of ordered sequences of data elements of the same type. The total number of elements in a linear list is called the length of a linear list. A linear table with no elements (length 0) is called an empty table. The start position of a table is called the head, and the end position of a table is called the tail.

Second, the abstract data type of linear table is described as follows:

Type name: linear table

Set of data objects: A linear list is an ordered sequence of N (n>=0) elements, where the last element is called the direct successor of the previous element and the reverse is the direct precursor. The immediate precursor and immediate successor reflect the one-to-one adjacency logical relation between elements.

Action sets:

​

Third, the sequential storage of linear tables

Sequential storage of a linear table refers to the sequential storage of the elements of a linear table in a block of memory with contiguous addresses. So a one-dimensional array is the perfect place to store it.

Considering that linear tables have some basic operations, the length of the table is dynamically variable. So the size of the array should be large, but the actual size may not be that large, so we need to use a variable Last to record the position of the Last element in the array in the current linear table. That is, Last acts as a pointer (actually an array subscript, a variable) and always points to the Last element of the linear table, with Last=-1 when the table is empty.

1. Code implementation:

typedef int position; typedef struct LNode* PtrToLNode; struct LNode { ElementType Data[MAXSIZE]; //ElementType Any data type position Last; }; typedef PtrToLNode List;Copy the code

Since LNode is a structure containing an array, it is often more efficient to use structure Pointers, so we can define linear tables using lists.

2. Basic operations – initialization

To construct an empty table, first allocate the storage space required by the table structure dynamically, and then set the Last pointer to -1, indicating that there is no data element in the table.

List MakeEmpty() {
	List L;
	L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;
	return L;
}
Copy the code

3. Basic operations – search

#define ERROR -1 Position Find(List L,ElementType X) { position i = 0; while (i <= L->Last && L->Data[i] ! = X) i++; if (i > L->Last) return ERROR; else return i; }Copy the code

Returns the storage index if it is found, or an ERROR message if it is not.

4. Basic operation – insert

Bool Insert(List L, ElementType X, int I) {// Insert(List L, ElementType X, int I) {// Insert(List L, ElementType X, int I) { If (L->Last == MAXSIZE - 1) {printf(" MAXSIZE "); return false; } / / check the legitimacy of the insertion order, whether in 1 ~ n + 1. The number n to the current element, namely the Last + 1. If (I < 1 | | I > Last + 2) {printf (" order illegal "); reutrn false; } for (j = L->Last; j >= i - 1; j++) { L->Data[j + 1] = L->Data[j]; } L->Data[i - 1] = X; L->Last++; return true; }Copy the code

5. Basic operations – Delete

bool Delete(List L, int i) { position j; If (I < 1 | | I > Last + 2) {printf (" a sequence % d there is no element ", I); reutrn false; } for (j = i; j <= L->Last; j++) { L->Data[j = 1] = L->Data[j]; } L->Last--; return true; }Copy the code

Four, linear list chain storage implementation

Since the storage characteristic of sequential table is to use physical adjacency to realize logical adjacency, it requires sequential storage units to store each element in a linear table. Therefore, the execution efficiency of some basic operations will be greatly affected.

As for the chain storage structure, it does not need to use contiguous address storage units to achieve, because it does not require the two logically adjacent elements to be physically adjacent, it is through the chain to establish the logical relationship between data elements.

In order to access the linked list, it is necessary to find the first data unit of the linked list. Therefore, in practical applications, a pointer called “table header” is often used to point to the first unit of the linked list and represent a specific linked list.

** Note: ** We use the same interface to define linear tables for both sequential and chained storage, because both are implementations of the same abstract concept.

1. Code implementation:

typedef struct LNode* PtrTolNode;
struct LNode {
	ElementType Data;
	PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
Copy the code

2, basic operation – find the table length

int length(List L) { position p; int cnt = 0; // initialize counter p = L; While (p) {p = p->Next; cnt++; } return cnt; }Copy the code

3. Basic operations – search

There are two kinds of linear table lookups: FindKth and FindKth.

Search by serial number

ElementType FindKth(List L,int K) {
	position p;
	int cnt;
	p = L;

	while (p && cnt < K) {
		p = p->Next;
		cnt++;
	}
	if (cnt == k)
		return p->Data;
	else
		return ERROR;

}
Copy the code

According to the value lookup

List Find(List L,ElementType X) { List p = L; while (p && p->Data ! = x) { p = p->Next; } return p; }Copy the code

4. Basic operation – insert

List Insert(ElementType X, List PtrL) { List p, s; If (I == 1) {s = (List)malloc(sizeof(struct LNode)); s->Data = X; s->Next = PtrL; return s; P = FindKth(i-1, PtrL); If (p == NULL) {printf(" argument I wrong "); return NULL; Else {s = (List)malloc(sizeof(struct LNode)); s->Data = X; s->Next = p->Next; p->Next = s; Return PtrL; return PtrL; }}Copy the code

5. Basic operations – Delete

List Delete(int i, List PtrL) { List p, s; if (i == 1) { s = PtrL; if (PtrL ! = NULL) PtrL = PtrL->Next; else return NULL; free(s); return PtrL; } p = FindKth(i - 1, PtrL); If (P == NULL) {printf(" node %d does not exist ", i-1); return NULL; } else if (p->Next == NULL) {printf(" %d does not exist ", I); return NULL; } else { s = p->Next; p->Next = s->Next; free(s); return PtrL; }}Copy the code

To sum up:

1) When a node is inserted into a single linked list, its precursor node must be known.

2) The single linked list does not have the characteristic of random access by serial number, and can only be carried out one by one starting from the ab initio pointer.

Fifth, generalized table

1. Definition:

1) is a generalization of linear tables

2) Similar to a linear list, it is also an ordered sequence composed of N elements,

3) The element of a generalized table can be a single element or another generalized table

2,

Generalized tables can not only express simple linear sequential relations like linear tables, but also express more complex nonlinear multivariate relations.

3,

Because general table of the elements can have different structure (single element and generalized table), and therefore not suitable for said in a sequential storage way, usually adopt chain storage structure, also is to use a linked list of nodes to represent the general table, nodes corresponding to each element, if the element is a generalized table, through the node lead another list.

4. Code implementation:

typedef struct GNode* GList; struct GNode { int Tag; // Sublist is common to single element Data, i.e., public storage space ElementType Data; GList Sublist; }URegion; GList Next; // point to the next node};Copy the code

​

Multiple linked lists

Lists with nodes that belong to more than one chain are called multilinked lists. In general, multiple linked lists have multiple pointer fields per node. Some implementations of generalized tables, like the one mentioned above, contain two pointer fields, but a list containing two pointer fields is not necessarily a multiple list, for example: a bidirectional list, although there are multiple pointer fields, but every node still belongs to the same list.

Seven, the stack

1. Definition:

Stack is a linear structure and a special linear table.

2. Concept:

In the stack, data insertion is usually called on the stack, and data deletion is called on the stack. Because of this feature, the last data to be pushed on the stack will be the first to be popped, so the stack is also called last in first out table.

Abstract data type of stack:

Type name: Stack

Data object set: A finite linear table with zero or more elements.

** For a Stack S ∈Stack whose specific length is a positive integer MaxSize

​

4. Code implementation:

typedef struct SNode* Stack; struct SNode { ElementType Data[MAXSIZE]; Int Top; // stack top pointer int MAXSIZE; // Maximum stack size};Copy the code

5. Creation of sequential stack

Stack CreateStack(int MaxSize) { Stack S = (Stack)malloc(sizeof(struct SNode); S->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType)) S->Top = -1; S->MaxSize = MaxSize; return S; }Copy the code

6. Push operation

bool IsFull(Stack S) { return (S->Top == S->MaxSize - 1); } bool Push(Stack S,ElementType X) {if (IsFull(S)) {printf(" Stack full "); return false; } else { S->Data[++(S->Top)] = X; return true; }}Copy the code

7. Pop out of the stack

ElementType Pop(Stack PtrS) {if (PtrS->Top == -1) {printf(" Stack empty "); return ERROR; } else { return (PtrS->Data[(PtrS->Top)--]); }}Copy the code

8, stack chain storage implementation

The chain storage structure of a stack (linked stack) is similar to that of a single linked list, but operations are limited and can only be performed at the top of the stack. The Top pointer is the list’s head pointer.

9. Code implementation:

typedef struct SNode* Stack;
struct SNode {
	ElementType Data;
	struct SNode* Next;
};
Copy the code

10. Basic operations – Create, judge, pass, delete

Stack CreateStack() {// Build a Stack head node and return the pointer to that node Stack S; S = (Stack)malloc(sizeof(struct SNode)); S->Next = NULL; return S; } bool IsEmpty(Stack S) {return (S->Next == NULL); } void Push(ElementType X, Stack S) {struct SNode* TmpCell; TmpCell = (struct SNode*)malloc(sizeof(struct Snode)); TmpCell->Element = X; TmpCell->Next = S->Next; S->Next = TmpCell; } ElementType Pop(Stack S) { PtrToSNode FirstCell; ElementType TopElem; If (IsEmpty(S)) {printf(" empty "); return NULL; } else { FirstCell = S->Next; TopElem = FirstCell->Data; S->Next = FirstCell->Next; free(FirstCell); return TopElem; }}Copy the code

Viii. Queue:

I. Definition:

The queue is also an ordered linear table, but the insertion and deletion of the queue are performed at two different endpoints of the linear table. To be precise, the end of the team comes in data, the head of the team comes out data.

Abstract data types:

Type name: Queue

Data object set: A finite linear table with zero or more elements

Action sets:

​

Third, the sequential storage of the queue

1. The simplest way to represent a queue is in an array. There are many specific ways to store queues with arrays. It is generally possible to place the queue head at a lower index and the queue tail at a higher index, with two variables Front and Rear indicating the head and tail of the queue, respectively.

Note:

​

With the process of leaving the queue and joining the queue, the whole queue will move backward as a whole, as shown in the second picture above, the last pointer of the queue has moved to the end, and overflow will occur if any element enters the queue. In fact, the queue is not really full at this time, which is called false overflow.

In order to solve the problem that the end of the queue overflows but there is still space in the array, the sequential storage structure of the queue usually uses a circular queue: Rear and Front reach the end of the array and can be retraced back to the beginning of the array, which is equivalent to the end of the array, like a ring.

​

Using circular queues solves the false overflow problem we mentioned earlier, but in circular queues, how to determine whether the current queue is empty or full based on Front and Rear?

So in this case, when Front and Rear are equal, the queue could be empty or it could be full, and we can’t tell.

The basic reason is that we judge the number of queue elements based on the gap between Rear and Front, and the gap between Rear and Front can only be n cases (n is the size of the array) and queue elements can be n+1 cases (0 to n), so we cannot distinguish n+1 cases by relying on these two alone.

​

You can’t tell whether the queue is empty or full because Front and Rear don’t provide enough information. There are two solutions:

Method 1: Add another variable, such as size to record the number of elements in the current queue, or Flag to record whether the last operation is in or out of the queue.

Method 2: use one less element of space, the third figure in the figure above, and the queue is full. The state is that if you increment the tail pointer by 1 it will catch up with the head pointer, so the queue is full if (Rear+1) % is equal to Front. The team empty condition is: Rear==Front.

Let’s take the second approach to the loop queue,

Struct QNode {ElementType Data[MaxSize]; int Rear; int Front; }; typedef struct QNode* Queue;Copy the code

2. Basic operations – Create

Queue CreateQueue(int MaxSize)
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType)malloc(MaxSize * sizeof(ElementType));
	Q->Front = Q->Rear = 0;
	Q->MaxSize = MaxSize;
	return Q;
}
Copy the code

3. Basic operations – Enqueue

Void AddQ(Queue PtrQ, ElementType item) {if ((PtrQ->Rear + 1) % MaxSize == PtrQ->Front) {printf(" Queue full "); return; } PtrQ->Rear = (PtrQ->Rear + 1) % MaxSize; PtrQ->Data[PtrQ->Rear] = item; }Copy the code

4. Basic operation – Exit queue

ElementType DeleteQ(Queue PtrQ) {if (PtrQ->Front == PtrQ->Rear) {printf(" Queue empty "); return ERROR; } else { PtrQ->Front = (PtrQ->Front) % MaxSize; return PtrQ->Data[PtrQ->Front]; }}Copy the code

Fourth, the chain storage implementation of queue

1. Code implementation:

struct Node { ElementType Data; struct Node* Next; }; Struct QNode {// link queue struct Node* Rear; Struct Node* Front; }; typedef struct QNode Queue; Queue PtrQ;Copy the code

2. Queue in and queue out using chained storage is actually inserting nodes at the end of a linked list or deleting nodes at the head. Take the queuing operation as an example:

ElementType DeleteQ(Queue PtrQ) { struct Node* FrontCell; ElementType FrontElem; If (PtrQ->Front == NULL) {pritNF (" queue empty "); return ERROR; } FrontCell = PtrQ->Front; If (PtrQ->Front == PtrQ->Rear) {PtrQ->Rear = NULL; Else {PtrQ->Front = PtrQ->Front->Next; } FrontElem = FrontCell->Data; free(FrontCell); Return FrontElem; // Return the value of this object}Copy the code

So much for the linear structure, which is some basic content, I will put forward a few examples in the video explanation of STATION B, for you to learn and understand, I hope you support, are free, I only hope you pay attention to praise and support.

Forget pac-man’s personal space _bilibili _bilibili