Requirements:

There are two sequential linear tables that store integer data, and the data in each sequential table is arranged from smallest to largest. Write a program that merges two tables to create a new order table, where the order is still from smallest to largest. For example: list1:1,2,4,8,10 list2:3,9,11 merged with list3:1,2,3,4,8,9,10,11

Tip: You should create the order table dynamically so that the length of list3 can be adjusted dynamically based on the length of List1 and List2. To merge two tables in ascending order, set pointer p1 and pointer p2 to two lists to be merged, and set pointer p3 to new list3 to store data to list3. Then compare the contents of p1 and p2 to list3. Place the smaller pointer to the storage unit of List3 that p3 points to, and then add +1 to the smaller pointer. Make it point to the next data in the table, and p3 also automatically +1. Repeat until list1, where the contents of one of the sequential lists in list2 are merged into list3. Finally, the subsequent contents of the partially merged order table are moved to list3 as a whole. Code:

#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
#include "conio.h"
typedef int ElemType;

typedef struct {
	int* elem;
	int length;
	int listsize;
}Sqlist;

// Initialize the sequence table
void InitSqlist(Sqlist *L,int size)
{
	L->elem = (int*)malloc(sizeof(ElemType)*size);			// Make space on the heap and pass the address pointer to ELEm
	if(! L->elem) {printf("Sequence table memory failed to open");
		exit(0);
	}
	L->length = 0;								// The initial table length is 0
	L->listsize = size;
}

// Insert elements into the sequence table
// Insert item into position I of sequence table L
void InsertElem(Sqlist* L,int i, ElemType item)
{
	// The new base after the memory is appended, the pointer to the insertion location, the intermediate variable of the pointer to move the data
	ElemType* base, * insertPtr, * p;
	if (i<1 || i>L->length + 1)		
	{
		printf("Unlawful penetration");
		exit(0);
	}
	if (L->length >= L->listsize)		// Order table space is not enough, append memory
	{
		base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));		// Pass the appending memory header to base
		L->elem = base;
		L->listsize = L->listsize + 100;
	}
	insertPtr = &(L->elem[i- 1]);		// The pointer points to the insertion position
	for (p = &L->elem[L->length - 1]; p >= insertPtr; p--) {// Move the data in the sequence table
		*(p+1) = *p;
	}
	*insertPtr = item;				// Insert data elements
	L->length++;
}
// Destroy the sequence table
void DestroySqlist(Sqlist* list)
{
	int* p = list->elem;
	free(p);
	list->elem = NULL;
	list->length = 0;
	list->listsize = 0;
}
// Merge the contents of two sequential tables, return a new list
Sqlist MergeList(Sqlist list1, Sqlist list2)
{
	// Merge the contents of list1 and list2 into list3 and return
	int* p1, * p2, * p3, * p1_last, * p2_last;
	Sqlist list3;

	p1 = list1.elem;		//p1 points to the first element of list1
	p2 = list2.elem;		//p2 points to the first element of list2

	// Initialize list3, whose length is the sum of list1 and list2
	InitSqlist(&list3,list1.length+list2.length);

	p3 = list3.elem;		//p3 points to the first element of list3
	p1_last = list1.length + list1.elem - 1;	//p1_last points to the end of list1
	p2_last = list2.length + list2.elem - 1;	//p2_last points to the end of list2

	// Implement merge
	while (p1<=p1_last && p2<=p2_last)		// A list is iterated between list1 and list2
	{
		if (*p1 <= *p2)	// When p1 is smaller than p2
		{
			*p3 = *p1;
			p3++;
			p1++;
		}
		else
		{
			*p3 = *p2;
			p3++;
			p2++;
		}
		list3.length++;
	}
	// add the remaining elements of list1 or list2 to list3
	if (p1 <= p1_last)		/ / p1 has a surplus
	{
		while(p1 <= p1_last) { *p3 = *p1; p3++; p1++; list3.length++; }}else
	{
		while(p2 <= p2_last) { *p3 = *p2; p3++; p2++; list3.length++; }}// Return to list3 when the move is complete
	return list3;
}
// Test the program
int main(a)
{
	Sqlist list1, list2, list3;		// Instantiate three order tables
	int n, i;					// Store list length intermediate variable, accumulator
	ElemType e;					// Insert the middle variable of the element
	printf("Please enter the length \n of list1");
	scanf("%d",&n);
	InitSqlist(&list1,n);
	printf("Please enter the element \n of list1");
	for (i=1; i<=n; i++) {scanf("%d",&e);
		InsertElem(&list1,i,e);
	}
	printf("Please enter the length \n of list2");
	scanf("%d", &n);
	InitSqlist(&list2, n);
	printf("Please enter the element \n of list2");
	for (i = 1; i <= n; i++) {scanf("%d", &e);
		InsertElem(&list2, i, e);
	}
	list3 = MergeList(list1,list2);
	printf("Output merged result \n");
	for (i = 0; i < list3.length; i++) {printf("%d ",list3.elem[i]);			// where %d is modified according to the ElemType type
	}
	// Destroy the list to free memory
	DestroySqlist(&list1);
	DestroySqlist(&list2);
	DestroySqlist(&list3);
	_getche();
	return 0;
}
Copy the code

Effect: