Data structure and algorithm analysis and learning

Learning records: MOOC data structure Huazhong University of science and technology + Data Structure and Algorithms in C++ - etc

Day 1

2.2 definition of linear table sequential structure in C language

Static allocation: after a fixed size of hardware storage space is allocated to a type variable, if the inserted element exceeds the storage space, overflow will occur.

Example: the space occupied by elements and table length are combined into a structure type of C language

#define maxleng 100

typedef struct
{
ElemType elem[maxleng];	// Subscript: 0,1, maxleng-1
int lenth;								// Table length
} SqList;

SqList La;
...

Of which:
La.lenth: table length;
La.elem[0]: the first element (the logical index is 0), which is shown in the figure above a 1 a_1 a1
La.elem[La.lenth-1]: the last element (the logical index is n-1), in the figure above a n a_n an

In order to solve the problem of static allocation, dynamic allocation is introduced: when overflow occurs, find a larger space to reallocate the data.

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
ElemType *elem;			// Storage space base address
int length;					// Table length
int listsize;				// Currently allocated storage capacity
					// In sizeof(ElemType)
} SqList;
SqList Lb;

chap5 array based sequences

python "sequence" class, embedded list class (list), tuple class (tuple), string class (str). There are obvious commonalities among these classes: each class supports subscript access to sequence elements; Each class uses arrays to represent sequences. However, there are also differences: there are obvious differences in the abstraction represented by these classes and the way they are instantiated.

array
A set of related variables can be stored one by one in a continuous area of computer memory.

Each cell of the array must occupy the same number of bytes. The reason is that in order to allow the use of index values, any cell in the array can be accessed in constant time. (each position in the array is called a cell).

Example: a text string is stored as a character array.
The memory address of the required character can be calculated by start + cellsize*index.

Day 2

Linked list

Linked list composition

A linked list is composed of a series of connected nodes, each of which is a data structure.

The nodes of the linked list are usually dynamically allocated, used and deleted, allowing the linked list to increase or decrease when the program runs. If new information needs to be added to the linked list, the program only needs to assign another node and insert it into the series. If you need to delete a specific information block from the linked list, the program will delete the node containing the information.

Each node in the linked list consists of a data member and a pointer. Data members contain one or more members that hold data. The pointer points to the next node in the linked list.

Linked list access

The first node of a non empty linked list is called the head of the list. To access the nodes in the linked list, you need to have a pointer to the chain header. Starting from the chain header, you can access the remaining nodes in the chain list according to the subsequent pointers stored in each node. The subsequent pointer in the last node is set to nullptr to indicate the end of the linked list.

C + + implementation of linked list

Define node: assume that each node will store a data item of type double:

struct ListNode   	 	// ListNode is the type of node to be stored in the linked list
{
	double value;		// The structure member value is the data part of the node
	ListNode *next;	// Subsequent pointer to the next node
	};

The ListNode structure has an interesting property that contains a pointer to a data structure of the same type, so it can be said to be a type that contains a reference to itself. Types like this are called self referencing data types or self referencing data structures.

Initialize linked list: define a pointer used as the chain header and initialize it as nullptr:

ListNode *head = nullptr;

Create list: contains a node with a stored value of 1

head = new ListNode;		// Assign new node
head -> value = 1;
head -> next = nullptr;

Where new is the keyword, which is equivalent to the programmer manually requesting to allocate a piece of memory space to store the linked list.

Create a new node

ListNode *secondPtr = new ListNode；
secondPtr -> value = 2;
secondPtr -> next = nullptr;		// The second node is the end of the linked list
head -> next = secondPtr; 		// The first node points to the second node

Create a simple linked list

#include <iostream>
using namespace std;
struct ListNode
{
    double value;
    ListNode *next;
};

int main()
{
    ListNode *head = nullptr;
    // Create first node with 12.5
    head = new ListNode; // Allocate new node
    head->value = 12.5;    // Store the value
    head->next = nullptr; // Signify end of list
    // Create second node with 13.5
    ListNode *secondPtr = new ListNode;
    secondPtr->value = 13.5;
    secondPtr->next = nullptr; // Second node is end of list
    head->next = secondPtr; // First node points to second
    // Print the list
    cout << "First item is " << head->value << endl;
    cout << "Second item is " << head->next->value << endl;
    return 0;
}

http://c.biancheng.net/view/1570.html
https://blog.csdn.net/slandarer/article/details/91863177
https://blog.csdn.net/qq_33835307/article/details/82683475