Linear table

I am stating ==
It's just a review for the postgraduate entrance examination dog. I usually write in java, but I'm a little confused when I suddenly switch to c, and my writing may not be standardized. Please correct me if I'm wrong, don't spray me with the glass heart! ! ! ! The algorithm and data structure of the java version of the black book may be sorted out later

Statement: I will not explain basic concepts, I want to read my own Baidu or buy my own books

The review materials (some non-full names) are:

"Royal Data Structure"

Tsinghua University Press "Data Structure (C Language Edition)" edited by Yan Weimin and Wu Weimin

Knowledge is valuable, this is just my collation of materials, and those who need to review or study well buy books by themselves! ! !

What a great book! ! ! Must buy it! ! buy it! ! buy it! !

1. Types and definitions of linear tables

1. Linear table abstract type definition

ADT List{
	data object:D={ai | ai ∈ ElementSet, i = 1,2,...,n,n≥0} 
	data relationship:R1={<ai-1,ai>|ai,ai∈ D,i = 2,...,n}
	Basic operation:
		InitList(&L)
			Operation result:Constructs an empty linear table;
			
		DestoryList(&L)
			Initial Conditions: Linear Table L existed;
			Result of the operation: Destroy the linear table L;
			
		ClearList(&L)
			Initial Conditions: Linear Table L existed;
			Operation result: the L reset to empty table;
			
		ListEmpty(L)
			Initial Conditions: Linear Table L existed;
			Operation result: if L is empty, return TRUE,otherwise return FALSE;
		
		ListLength(L)
			Initial Conditions: Linear Table L existed;
			Operation result: return L The number of data elements in;
		
		GetElem(L,i,&e)
			Initial Conditions: Linear Table L already exists, 1≤i≤ListLength(L)
			Operation result: with e return L The number of data elements in;
		
		LocateElem(L,e,compare())
			Initial Conditions: Linear Table L existed, compare()is the data element determination function;
			Operation result: return L The 1st and e Satisfaction relationship compare()The bit order of the data elements. If no such data element exists, the return value is 0;
		
		PriorElem(L,cur_e,&pre_e)
			Initial Conditions: Linear Table L existed;
			Operation result: if cur_e Yes L , and is not the first data element, use pre_e returns its predecessor, otherwise the operation fails, pre_e undefined;
			
		NextElem(L,cur_e,&next_e)
			Initial Conditions: Linear Table L existed;
			Operation result: if cur_e Yes L , and is not the last data element, use next_e returns its successor, otherwise the operation fails, next_e undefined;
			
		ListInsert(&L,i,e)
			Initial Conditions: Linear Table L already exists, 1≤i≤ListLength(L)+1;
			Operation result: in L B i Insert a new data element before positions e，L length+1
		
		ListDelete(&L,i,&e)
			Initial Conditions: Linear Table L exists and is not empty, 1≤i≤ListLength(L);
			Result of operation: delete L First i data elements, and use e returns its value, L length-1
			
		ListTraverse(L,visit())
			Initial Conditions: Linear Table L existed;
			Operation result: in turn L call the function for each data element of visit()，once visit()fails, the operation fails
			
} ADT List

Example 2-1 Combine two linear tables A and B to generate a new table A

​ Time complexity O(ListLength(LA) X ListLength(LB))

Title Assuming that two sets A and B are represented by two linear tables LA and LB respectively (that is, the data elements in the linear tables are members of the sets), a new set A= A∪B is required.

Analysis requires the following operations:

​ 1. Expand the linear table LA

​ 2. Insert what exists in the linear table LB but does not exist in the linear table LA into the linear table LA

​ As long as each data element is obtained from the linear table LB in turn, and is accessed in the linear table LA according to the value, if it does not exist, insert it

void union(List &La,List Lb) {
	//Insert all data elements in linear table Lb but not in La into La
	
	//Length of linear table LA
	La_len = ListLength(La);
	
	//Length of linear table LB
	Lb_len = ListLength(Lb);
	
	//As long as each data element is obtained in turn from the linear table LB, and is accessed in the linear table LA according to the value, if it does not exist, insert it.
	for(i=1;i<=Lb_len;i++){
	
		//Get the i-th data element in Lb and assign it to e
		GetElem(Lb,i,e);
		
		//Traverse La, if there is no data element same as e in La, insert it
		if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);
	}
}

Example 2-2 Merge A.B to generate ordered table C

The time complexity is O(ListLength(LA) + ListLength(LB))

Title Knowing that the data elements in the linear tables LA and LB are arranged in non-decreasing order by value, it is now required to merge LA and LB into a new linear table LC, and the elements in LC are still in non-decreasing order by value.

To analyze data elements in LC or data elements in LA, or data elements in LB, as long as LC is an empty table first, then insert the elements in LA or LB into LC one by one

Operation In order to arrange the elements in LC in non-decreasing order by value, two pointers i and j can be set to point to an element in LA and LB respectively.

// Code from the book, but me as a working dog. . . I feel that a judgment needs to be added to LA and LB. . . That non-empty comment. . emmm. . .

void MergeList(List La,List Lb,List &Lc){
	//The data elements in the known linear tables La and Lb are arranged non-decreasingly by value
	//Merge La and Lb to obtain a new linear table Lc, and the data elements of Lc are also arranged in non-decreasing value;
	
	//Constructs a new empty table Lc
	InitList(Lc);
	
	//define variables i,j,k
	i = j = 1; 
	k = 0;
	
	//Length of linear table LA
	La_len = ListLength(La);
	
	//Length of linear table LB
	Lb_len = ListLength(Lb);
	
	while((i <= La_len)&&(j<= Lb_len)){//Both La and Lb are non-null
	
		//Get the i-th data element in La and assign it to ai
		GetElem(La,i,ai);
		
		//Get the j th data element in Lb and assign it to bj
		GetElem(Lb,j,bj);
		
		//Judgmental Interpolation
		if(ai<= bj) {
			ListInsert(Lc,++k,ai);
			++i;
		}else{
			ListInsert(Lc,++k,bj);
			++j;
		}
	}
	while(i<= La_len){
		//Get the i-th data element in La and assign it to ai
		GetElem(La,i,ai);
		
		ListInsert(Lc,++k,ai);
	}
	while(j<= Lb_len){
		//Get the j th data element in Lb and assign it to bj
		GetElem(Lb,j,bj);
		ListInsert(Lc,++k,bj);
	}
}

Added the judgment non-empty

void MergeList(List La,List Lb,List &Lc){
	//The data elements in the known linear tables La and Lb are arranged non-decreasingly by value
	//Merge La and Lb to obtain a new linear table Lc, and the data elements of Lc are also arranged in non-decreasing value;
	
	//Constructs a new empty table Lc
	InitList(Lc);
	
	//define variables i,j,k
	i = j = 1; 
	k = 0;
	
	if(ListEmpty(La) || ListEmpty(Lb)){
		prinf("Error,list is empty");
		exit;
	}else{
		
		//Length of linear table LA
		La_len = ListLength(La);
	
		//Length of linear table LB
		Lb_len = ListLength(Lb);
	
		while((i <= La_len)&&(j<= Lb_len)){//Both La and Lb are non-null
	
			//Get the i-th data element in La and assign it to ai
			GetElem(La,i,ai);
		
			//Get the j th data element in Lb and assign it to bj
			GetElem(Lb,j,bj);
		
			//Judgmental Interpolation
			if(ai<= bj) {
				ListInsert(Lc,++k,ai);
				++i;
			}else{
				ListInsert(Lc,++k,bj);
				++j;
			}
		}
		while(i<= La_len){
			//Get the i-th data element in La and assign it to ai
			GetElem(La,i,ai);
		
			ListInsert(Lc,++k,ai);
		}
		while(j<= Lb_len){
		
			//Get the j th data element in Lb and assign it to bj
			GetElem(Lb,j,bj);
			
			ListInsert(Lc,++k,bj);
		}
	}	
}