2022.1.23

The linear table

1. Zero or more data elements Co., LTD. Sequence .

2. The relationship of each element in the sequence is one-to-one .

3. When passing an argument to a function , Whether this parameter will be changed within the function determines what parameter form to use .

        3.1 If it needs to be changed , You need to pass a pointer to this parameter ,

        3.2 If it doesn't have to be changed , You can pass this parameter directly .

4. Linear tables have a sequential storage structure （ Array ） And chain storage structure （ Linked list ）.

Linked list

Linked list

1. The difference between linked list and array ：

The array is convenient for finding data ,O(1), Deleting and adding data is complicated ,O(n);

Linked list lookup data is complex ,O(N), Deleting and adding data is simple ,O(1);

2. A linked list must have a header pointer .

3. A one-way linked list has a data field , A pointer field

struct node{
	int data;
	struct node *next;
}linklist; 

A two-way linked list has a data field , Two pointer fields

struct node{
	int data;
	struct node *next;
	struct node *pre;
}linklist; 

4. Insertion of linked list

int insert(linklist j,int i,int t)//i For the location to insert ,t Is the number to insert 
{
	int j;
	linklist p,t;
	p=j;
	j=1;
	while(p!=NULL&&j<i)
	{
		p=p->next;
		j++;	
	} 
	if(p==NULL||j>i)// The first i There are no elements 
	return 0;
	t=(linklist *)malloc(sizeof(struct node));
	t->data=e;
	t->next=p->next;// Backwards and forwards  
	p->next=t;
    return 1;
} 

The first interpolation

void creat(linklist p)
{
	int n,i,m;
	scanf("%d",&n);
	linklist t;
	p=(linklist *)malloc(sizeof(struct node));// To apply for space 
	p->next=NULL;// Establish a single linked list of leading nodes 
	for(i=0;i<n;i++)
	{
		scanf("%d",&m);
		t=(linklist *)malloc(sizeof(struct node));
		t->data=m;
		t->next=p->next;
		p->next=t;// Insert into the header 
	}
}

The tail interpolation

void creat(linklist p)
{
	int n,i,m;
	scanf("%d",&n);
	linklist t,r;
	p=(linklist *)malloc(sizeof(struct node));
	r=p;//r Point to the entire linked list  
	for(i=0;i<n;i++)
	{
		scanf("%d",&m);
		t=(linklist *)malloc(sizeof(struct node));
		r->next=t;
		r=t;// Link list  
	}
	r->next=NULL;// End of list , The next point of the last point should be NULL 
}

5. Deletion of linked list

int insert(linklist j,int i)//i For the location to insert 
{
	int j;
	linklist p,t;
	p=j;
	j=1;
	while(p->next!=NULL&&j<i)
	{
		p=p->next;
		j++;	
	} 
	if(p->next==NULL||j>i)// The first i There are no elements 
	return 0;
	t=p->next;
	p->next=t->next;
	free(t);
	return 1;
}