Job 7.25 sorting and searching

1. Use hash storage to store data in hash table , And find

1、 A set of keyword sequences is known as (25,51,8,22,26,67,11,16,54,41)
2、 Its hash address space is [0…12]
3、Hash The function is defined as :H(key) = key MOD 13
4、 Use the chain address method to deal with conflicts , Draw the corresponding hash table , And coding implementation

function code

Initialize hash table function

// Initialize hash table 
void init_hash(Node *hash[])
{
    
	for(int i=0;i<P;i++)
	{
    
		hash[i]=NULL;
	}
	printf(" Successful initialization \n");
}

Store elements in hash table function

// Store elements in hash table 
int insert_hash(Node *hash[],int x)
{
    
	int index=x%P;   // Locate the linked list to store 
	// Encapsulating data into nodes  
	Node *q=(Node*)malloc(sizeof(Node));
	if(NULL==q)
	{
    
		printf(" Space application failed \n");
		return -1;
	}
	q->data=x;
	q->next=NULL;

	// Use the head insertion method to put the nodes into the linked list 
	q->next=hash[index];
	hash[index]=q;
	return 0;
}

View hash table functions

// View hash table functions 
void show_hash(Node **hash)
{
    
	for(int i=0;i<P;i++)
	{
    
		printf("%d:",i);
		Node *q=hash[i];  // Define traversal pointer 
		while(q!=NULL)
		{
    
			printf("%d->",q->data);
			q=q->next;
		}
		printf("NULL\n");
	}
}

Hash lookup function

// Define hash lookup function 
void search_hash(Node **hash,int key)
{
    
	int index=key%P; // Locate the linked list of values to be searched 
	// Define traversal pointer traversal linked list 
	Node *q=hash[index];
	while(q!=NULL&&q->data!=key)
	{
    
		q=q->next;
	}

	// Judge the found node 
	if(NULL==q)
	{
    
		printf(" To find the failure \n");
	}
	else
	{
    
		printf(" The data you are looking for %d In the table \n",key);
	}
}

Main function code

#include "hash.h"
int main(int argc, const char *argv[])
{
    
	int arr[N]={
    25,51,8,22,26,67,11,16,54,41};
	Node *hash[P];   // Hashtable 
	init_hash(hash);   // Initialize hash table 
	for(int i=0;i<N;i++)    // Store elements 
	{
    
		insert_hash(hash,arr[i]);
	}
	// Call the view function 
	show_hash(hash);
	// Call lookup function 
	search_hash(hash,41);
	return 0;
}

Running results

Initialize hash table , Then save the keyword sequence into the hash table , Complete the construction of hash table
Print out the hash table
Find keywords 41 Whether it is in the hash table
Find the , Display the found data 41 In the table

2. Use bubble sort 、 Selection sort 、 Insertion sort 、 Quick sort to complete the following cases

Case renderings

The case requires
2） Use bubble sort 、 Selection sort 、 Insertion sort 、 Quick sort sequence {198,289,98,357,85,170,232,110} Sort from small to large
3） Output correctly according to the effect picture after sorting
4） Add comments to the function code
5） Analyze time complexity

function code

Bubble sort

// Bubble sort 
void pop_sort(int *arr,int n)
{
    
	for(int i=0;i<n-1;i++)    // The outer loop controls the number of trips 
	{
    
		int flag=0;           // Set up a flag before sorting 
		for(int j=0;j<n-i-1;j++)   // Control element subscript , And the number of comparisons 
		{
    
			if(arr[j]>arr[j+1])    // Large rise and small fall 
			{
    
				int temp=arr[j];   // Three glasses of water 
				arr[j]=arr[j+1];
				arr[j+1]=temp;
				flag=1;
			}
		}
		if(flag=0)   It indicates that there is no data exchange in the current trip , It also reflects that the sequence of numbers has been ordered , There is no need to row later  
		{
    
			break;
		}
	}
}

Selection sort

// Selection sort 
void select_sort(int *arr,int n)
{
    
	for(int i=0;i<n;i++)       // Traverse all the elements 
	{
    
		int index=i;          // Take the subscript of the first element to be sorted as the minimum subscript 
		for(int j=i+1;j<n;j++)   // Find the minimum value from the sequence to be sorted 
		{
    
			if(arr[index]>arr[j])
			{
    
				index=j;          Update minimum subscript 
			}
		}
		// Determine whether the minimum subscript is the first element of the sequence to be sorted 
		if(index!=i)
		{
    
			// Exchange Trilogy 
			int temp=arr[index];
			arr[index]=arr[i];
			arr[i]=temp;
		}
	}
}

Insertion sort

void insert_sort(int *arr,int n)
{
    
	for(int i=1;i<n;i++)        // Before and after   Traverse the sequence to be sorted 
	{
    
		int temp=arr[i];
		int j;
		for(j=i;j>0&&temp<arr[j-1];j--)    //  From back to front   Traverse the sorted sequence  
		{
    
			arr[j]=arr[j-1];
		}
		arr[j]=temp;
	}
}

Quick sort

int part(int *arr,int low,int high)
{
    
	int x=arr[low];    // Selected datum 
	while(low<high)    // The control cycle will not end after one pass 
	{
    
		while(arr[high]>=x&&low<high)  // prevent low exceed high
		{
    
			high--;
		}
		arr[low]=arr[high];
		while(arr[low]<=x&&low<high)   // prevent low exceed high
		{
    
			low++;
		}
		arr[high]=arr[low];
	}
	arr[low]=x;           // Put the benchmark in the middle  
	return low;           // Return the position of the datum to 
}


void quick_sort(int *arr,int low,int high)
{
    
	if(low<high)
	{
    
		int mid=part(arr,low,high);  // Call a quick sort 
		quick_sort(arr,low,mid-1);   // Quickly sort the sequence on the left side of the benchmark 
		quick_sort(arr,mid+1,high);  // Quickly sort the sequence on the right side of the benchmark  
	}
}

Main function code

#include "sort.h"
int main(int argc, const char *argv[])
{
    
	int arr[8]={
    198,289,98,357,85,170,232,110};
	printf(" Before ordering ：\n");
	output(arr,8);
	printf(" After ordering ：\n");
	pop_sort(arr,8);
	printf(" Bubble sort ：");
	output(arr,8);
	printf(" Selection sort ：");
	select_sort(arr,8);
	output(arr,8);
	printf(" Insertion sort ：");
	insert_sort(arr,8);
	output(arr,8);
	printf(" Quick sort ：");
	quick_sort(arr,0,7);
	output(arr,8);
	//int a=half_search(arr,6,45);
	//printf("%d\n",a);
	return 0;
}

Running results