有序表

小灰灰 2023-08-17 15:15 110阅读 0赞

顺序表存储有序表

插入

void ListInsert(SqList*& L, ElemType e)
    {
    	int i = 0, j = L->length;
    	while (i < L->length && L->data[i] < e)
    		i++;
    	while (j > i)
    	{
    		L->data[j] = L->data[j - 1];
    		j--;
    	}
    	L->data[j] = e;
    	L->length++;
    }

归并

void UnionList(SqList* LA, SqList* LB, SqList*& LC)
    {
    	int i = 0, j = 0, k = 0;
    	LC = (SqList*)malloc(sizeof(SqList));
    	while (i < LA->length && j < LB->length)
    	{
    		if (LA->data[i] <= LB->data[j])
    		{
    			LC->data[k] = LA->data[i];
    			i++;
    		}
    		else
    		{
    			LC->data[k] = LB->data[j];
    			j++;
    		}
    		k++;
    	}
    	while (i < LA->length)
    	{
    		LC->data[k] = LA->data[i];
    		i++;
    		k++;
    	}
    	while (j < LB->length)
    	{
    		LC->data[k] = LB->data[j];
    		j++;
    		k++;
    	}
    	LC->length = k;
    }

找到两个等长升序的中位数

单链表

插入

void ListInsert(LinkNode*& L, ElemType e)
    {
    	LinkNode* pre = L;
    	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    	s->data = e;
    	
    	while (pre->next != NULL && pre->next->data < e)
    		pre = pre->next;
    	s->next = pre->next;
    	pre->next = s;
    
    
    }

归并

void UnionList(LinkNode* LA, LinkNode* LB, LinkNode*& LC)
    {
    	LinkNode* pa, * pb, * pc,* s;
    	pa = LA->next;
    	pb = LB->next;
    	LC = (LinkNode*)malloc(sizeof(LinkNode));
    	pc = LC;
    	s = (LinkNode*)malloc(sizeof(LinkNode));
    
    	while (pa != NULL && pb != NULL)
    	{
    		if (pa->data <= pb->data)
    		{
    			s = (LinkNode*)malloc(sizeof(LinkNode));
    			s->data = pa->data;
    			pa = pa->next;
    		}
    		else
    		{
    			s = (LinkNode*)malloc(sizeof(LinkNode));
    			s->data = pb->data;
    			pb = pb->next;
    		}
    		pc->next = s;
    		pc = s;
    	}
    	while (pa != NULL)
    	{
    		s = (LinkNode*)malloc(sizeof(LinkNode));
    		s->data = pa->data;
    		pa = pa->next;
    		pc->next = s;
    		pc = s;
    	}
    	while (pb != NULL)
    	{
    		s = (LinkNode*)malloc(sizeof(LinkNode));
    		s->data = pb->data;
    		pb = pb->next;
    		pc->next = s;
    		pc = s;
    	}
    	pc->next = NULL;
    }

三个单链表LA，LB，LC，操作后LA中仅含3个表中均包含结点

}
    void Commonnode(LinkNode*& LA, LinkNode* LB, LinkNode* LC)
    {
    	LinkNode* pa, * pb, * pc, * r,* q;
    	pa = LA->next;
    	pb = LB->next;
    	pc = LC->next;
    	LA->next = NULL;
    	r = LA;
    
    	while (pa != NULL)
    	{
    		while (pa->data > pb->data && pb != NULL)
    			pb = pb->next;
    		while (pa->data > pc->data && pc != NULL)
    			pc = pc->next;
    
    		if (pb != NULL && pc != NULL && pb->data == pa->data && pc->data == pa->data)
    		{
    			r->next = pa;
    			r = pa;
    			pa = pa->next;
    		
    		}
    		else
    		{
    			q = pa;
    			pa = pa->next;
    			free(q);
    		}
    		
    
    	}
    	r->next = NULL;
    }

删除值域重复结点

void dels(LinkNode*& L)
    {
    	LinkNode* p = L->next,* q;
    	
    	while (p->next != NULL)
    	{
    		if (p->next->data == p->data)
    		{
    			q = p->next;
    			p->next = q->next;
    			free(q);
    		}
    		else
    			p = p->next;
    	}
    }

转载于:https://www.cnblogs.com/KIROsola/p/11337719.html