[C++知识库]顺序表涉及移动元素的算法杂谈（C语言实现）

第一种算法
借助辅助数组

void move_elem(int a[],int n, int p)
{
	int *b = (int *)malloc(sizeof(int)*p);//定义辅助数组b[]
	for (int i = 0; i < n; i++)
	{
		if (i < p)
			b[i] = a[i];
		else
			a[i - p] = a[i];
	}
	for (int i = n-p,j=0; i < n; i++,j++)
	{
		a[i] = b[j];
	}
}

时间复杂度O(n),空间复杂度O( p)
第二种算法
使用翻转数组思想

void Reverse(int a[],int left,int right)
{
	int temp;
	for (int i = 0; i < (right - left + 1) / 2; i++)
	{
		temp = a[left + i];
		a[left + i] = a[right - i];
		a[right - i] = temp;
	}
}
void Converse(int a[], int n, int p)
{
	Reverse(a, 0, p - 1);
	Reverse(a, p, n - 1);
	Reverse(a, 0, n - 1);
}

时间复杂度O(n),空间复杂度O(1)

第三种算法
类似循环队列的思想

void move_elem(Seqlist *L,int p)
{
	int k = 0, i = 0, j, temp1, temp2;
	while(k!=L->len)
	{
		temp1 = L->data[i];
		j = i;
		do {
			j = (j + (L ->len) - p) % L->len;
			temp2 = L->data[j];
			L->data[j] = temp1;
			temp1 = temp2;
			k++;
		} while (j != i);
		i++;
	}
}

时间复杂度O(n),空间复杂度O(1)
第三种算法的测试代码

#include<stdio.h>
#define M 50
typedef struct {
	int  data[M];
	int len;
}Seqlist;
void Initlist(Seqlist *L,int n);
void move_elem(Seqlist *L, int p);
void Printlist(Seqlist *L);
void copylist(Seqlist *L, Seqlist *L2);
int main()
{
	Seqlist list1,list2;
	Seqlist *L=&list1;
	Seqlist *L2 = &list2;
	int n, m;//n是数组长度，m是移动位数
	for (n = 5; n <= 15; n++) {
		printf("初始长度为%d序列:\n",n);
		Initlist(L, n);
		Printlist(L);
		printf("--------------------------------------------------\n");
		for (m = 1; m <=n; m++) {
			copylist(L, L2);
			printf("向左移动%d位后的数列：\n",m);
			move_elem(L2, m);
			Printlist(L2);
			printf("---------------\n");
		}
	}
}
void move_elem(Seqlist *L,int p)
{
	int k = 0, i = 0, j, temp1, temp2;
	while(k!=L->len)
	{
		temp1 = L->data[i];
		j = i;
		do {
			j = (j + (L ->len) - p) % L->len;
			temp2 = L->data[j];
			L->data[j] = temp1;
			temp1 = temp2;
			k++;
		} while (j != i);
		i++;
	}
}
void Initlist(Seqlist *L,int n)
{
	for (int i = 0; i < n; i++)
	{
		L->data[i] = i+1;
	}
	L->len = n;
}
void Printlist(Seqlist *L)
{
	for (int i = 0; i < L->len; i++)
	{
		printf("%d ", L->data[i]);
	}
	printf("\n");
}
void copylist(Seqlist *L, Seqlist *L2) 
{
	for (int i = 0; i < L->len; i++)
	{
		L2->data[i] = L->data[i];
	}
	L2->len = L->len;
}