欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序表算法

程序员文章站 2024-03-19 15:41:34
...
顺序表算法

【顺序表算法】设顺序表 A,元素的个数是 n,没有重复。如果 A 中前 k 个元
素有序,后 n-k 个元素有序,设计一个算法使得整个顺序表有序,要求算法的空
间复杂度为 O(1)

#include <stdio.h>
#include<stdlib.h>
#define ElemType int 
#define Status int
#define MaxSize 20
//顺序表数据结构
typedef struct
{
	ElemType data[MaxSize];
	int length, listsize;
}SeqList;

//插入元素
void ListInsert(SeqList & L, int i, ElemType e)
{
	for (int j = L.length - 1; j >= i; j--)
		L.data[j + 1] = L.data[j];
	++L.length;
	L.data[i] = e;
}

//删除元素
void Delete(SeqList & L, int i)
{
	for (int j = i; j <= L.length; j++)
		L.data[j] = L.data[j + 1];
	--L.length;
}

//输出函数
void PrintList(SeqList & L)
{
	printf("顺序表整体有序化:\n");
	//printf("\n");
	for (int i = 0; i < L.length + 1; i++)
	{
		printf("%d", L.data[i]);
	}
}

//排序函数,这里是对已知顺序表进行排序操作
void Sort(SeqList & La)
{
	int flag = 0;
	for (int i = 0; i < 4; i++)
	{
		int Lb2 = La.data[6 + i];
		//printf("输出得到的Lb2 的值:%d\n", Lb2);
		for (int j = flag; j < La.length; j++)
		{
			if (Lb2 < La.data[j])
			{
				ListInsert(La, j, Lb2);
				//printf("ok\n");
				break;
			}
			flag = j;
			//printf("输出flag的值:%d\n", flag);
			continue;
		}
		//printf("删除的是:%d\n", La.data[7 + i]);
		Delete(La, 7 + i);
		//PrintList(La);
		printf("\n");
	}
	PrintList(La);
}
//整体有序化,找到一个数的插入位置并插入后然后再删除
void SortAll(SeqList & La)
{
	int flag = 0;
	int Lb1 = La.data[5];
	if (Lb1 < La.data[0])
	{
		ListInsert(La, 0, Lb1);
		Delete(La, 6);
		//PrintList(La);
		//printf("\n");
		Sort(La);
	}
}

int main()
{
	SeqList La = { {1,2,4,7,8,0,3,5,6,9 },10 };
	SortAll(La);
	return 0;
}

运行结果示例:
顺序表算法

相关标签: 数据结构C语言版