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 interpretationCheck 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 interpretationCheck 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 interpretationRecord 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 L2. 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 node2. 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 i2. 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 nodes2. 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 headerAlgorithm 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 tableAlgorithm 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) insertAlgorithm 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) deleteAlgorithm 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