Of Stack

C C++ linear table basic operation details

  • 2020-11-26 18:55:31
  • OfStack

preface

Linear table consists of two parts sequence table and linked list, which is the basis of data structure. This paper mainly analyzes and summarizes the algorithm, as a memory to understand, but does not do specific implementation.

Tip: The following is the text of this article, the following case for reference

1. The order sheet 


#define LISST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 0
#define OVERFLOW 1
typedef int ElemType;
typedef int Status;

1, define, 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;

2. Initialize the build 


Status InitList_Sq(SqList &l){
	L.elem =(ElemType *)malloc(LISST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
	exit(OVERFLOW);
	L.length=0;
	L.listsize=LISST_INIT_SIZE;
	return OK;

3. Insert operation

Insert the element e at i

1. Algorithm interpretation
Check the legality of i Check storage space Mark insertion location Move the element after the insert position down by 1 bit (note that you move it backwards to end the loop by moving it less than the insert position)
2. Algorithm implementation 

Status LIstInsert_Sq(Sqlist &L,int i, ElemType e){
SqList *newbase,*p,*q;
	// In the first i Insert the element e
	if(i<1||i>L.length+1)
	return ERROR;
	// Allocate storage space 
	if(L.length>L.listsize){
		newbase=(ElemType *)realloc(l.elem,		(Listsize+LISTINCREMENT)*sizeof(ELemType);
	if(!newbase)
	exit(OVERFLOW);
	L.elem=newbase;
	L.listsize+=LISTINCREMENT;
	}
// Record insertion location 
	q=&L.elem[i-1];
	for(p=L.elem[length-1];q<=p;p--)
	{
		*(p+1)=*p
	}
	*p=e;
	L.length++;// Update the long table 
	return OK;
}

4. Delete operation

Insert the element e at the i position

1. Algorithm interpretation
Check the legality of i The place where the record is deleted Find the deleted element and assign it to e Elements after deleted elements want to move up 1 bit (find the end of the table element and end the loop with the end table address greater than the end table address)
2. Algorithm implementation 

Status LIstDelete_Sq(Sqlist &L,int i, ElemType &e){
SqList *p,*q;
	// In the first i Delete element 
	if(i<1||i>L.length+1)
	return ERROR;
// Record deletion location 
	p=&L.elem[i-1];
	e=*p;
	// Footer element 
	q=&L.elem[L.length-1];
	for(++p;p<=q;p++)
	{
		*(p-1)=*p;
	}
	L.length--;// Update the long table 
	return OK;
}

5. Merge operation

The elements of La and Lb are known to merge in non-decreasing order and Lc in non-decreasing order

1. Algorithm interpretation
Record the operation addresses of La and Lb Calculate the length of Lc and allocate space for it Record the table end position of La and Lb Merge - compare the elements of two tables, with the smaller value stored in Lc (note: complete the loop with any 1 table stored in Lc) Check whether La and Lb have any remaining elements, and if so, store them in Lc
2. Algorithm implementation 

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
// Record the La , Lb The current operation address of 
SqList *pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=La.length+Lb.length;
pc=Lc.elem=(ElemType *)mallod(Lc.listsize*sizeof(ElemType);
if(!pc){
		exit(OVERFLOW);// Allocation failure 
		}
		// Record the address at the end of the sequence table 
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<pa_last&&pb<pb_last){
	if(*pa<*pb)
	{
	 //*pc++=*pa++;
		*pc=*pa
		pc++;
		pa++;
	}
	else
	{
	//*pc++=*pb++;
		*pc=*pb;
		pc++;
		pb++;
	}
	while(pa<pa_last)
	{
		*pc++=*pa++;
	}
	while(pb<pb_last)
	{
		*pc++=*pb++;
	}
}

2. List 


#define OK 0
#define OVERFLOW 1
typedef int ElemType;
typedef int Status;

1. The singly linked list

1, define, 

typedef int ElemType;
typedef struct LNode{
	ElemType date;
	struct LNode *next;
	}LNode,*LinkList;
2, insert,

Insert e before the i position in the head node L

1. Algorithm interpretation

Find the node i-1 and record it as P Determine if the node is found Generate new node S assignment for insertion into L

2. Algorithm implementation 


status ListInsert(LinkList &l,int i;ElemType e){
	LinkList p=L,S;
	int j=0;
	while(p&&j<i-1){
	p=p->next;
	j++;
	}
	if(!p||j>i-1)
	return ERROR;
	// Generate new nodes 
	S=(LinkList)malloc(sizeof(LNode));
	S->date=e;
	S->next=p->next;
	p->next=S;
	return OK;
	}
3, delete,

Delete the i element in the single linked list L of the lead node and return e

1. Algorithm interpretation

Record the position of the head node Find the i node and record its precursor with p Check the reasonableness of the deleted location Record the i node and assign its value to e Point the node i-1 to i+1 Release the i node

2. Algorithm implementation 


status ListDelete_L(LinkList &L,int i,ElemType &e){
LinkList p=L,q;
int j=0;
while(p->next&&j<i-1){
	p=p->next;
	j++;
}
if(!(p-next)||j>i-1)
return ERROR;
	q=p->next;
	p->next=q->next;
	e=q->date;
	free(q);
return OK;
4, find

The code is as follows (example) : Find the element at the i location and assign it to e

1. Algorithm interpretation

Point p to the first node Find the i node (null with p or j) > i closing loop) Determine whether the node i was found Take the element value of node i

2. Algorithm implementation 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;
0 5, merge the ordered linked list

It is known that La and Lb are non-decreasing by value and Lc is also non-decreasing by value (lead node)

1. Algorithm interpretation

Update the initial location of Pa, Pb, and Pc all point to the first node On the condition that both Pa and Pb are not null, compare their stored data. The smaller connection is on Lc, and update Pc and Pa (Pb) Insert residual node Release unused bear nodes

2. Algorithm implementation 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;
1 6. Create a linked list

Enter the values of n elements to establish a single linked list of the lead node L

1. Inverse bit order (head insertion)

Algorithm ideas

Create a header Loop insertion node Insert the new node behind the table header Update the next #### algorithm implementation of the table header

Algorithm implementation 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;
2

2. Sequential order (tail insertion)

Algorithm ideas

Create a header Loop insertion node Insert the new node into the end of the table Record and update the end of the table

Algorithm implementation 


void GreateList_L(LinkList &L,int n){
// Establish a header 
LinkList L,P;
L=(LinkList)malloc(sizeof(LNode);
L->next=NULL;
Q=L;
for(i=0;i<n;i++){
	P=(LinkList)malloc(sizeof(LNode);
	scanf("%d",&P->data);// Take integers, for example 
	Q->next=P
	Q=P;
	}
	q->next=NULL;
}

2. Circular linked lists

It is similar to the single linked list, except that next of the end node points to the head node. The cycle condition is whether it is equal to the head element, which is not specified in detail.

3. Bidirectional linked lists

1, define, 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;
4

2, insert,

The element e of node S is inserted before the i (P) in the bidirectional circular linked list L of the lead node

Algorithm ideas

Check the validity of i (1 < =i < = table length +1) insert

Algorithm implementation 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;
5

3, delete,

Delete the i node (P) in the bidirectional circular linked list L of the lead node and copy its data to the element e

Algorithm ideas

Check the legality of i (1 < =i < = long table) delete

Algorithm implementation 


typedef struct{
			int* elem; // Define the storage base address 
			int length; // Current sequence table length 
			int listsize; // The size of the current allocation 
			}SqList;
6

conclusion

Related articles: