【C语言】【数据结构】顺序线性表（建表、插入、删除、遍历、合并、逆置）

创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历的基本操作，合并两个表，逆置顺序表。

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int Status;

typedef int ElemType;
typedef struct{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

Status InitList_Sq(SqList & );							//空表
Status ListInsert_Sq(SqList & , int i, ElemType );		//插入（第几个） 
Status ListDelete_Sq(SqList & , int i, ElemType & );	//删除（第几个） 
Status Load_Sq(SqList );								//遍历打印
Status MergeList_Sq(SqList , SqList , SqList & );		//合并
Status InvertList_Sq(SqList & );						//倒置
Status ListDelete_Sq1(SqList & , ElemType ); 			//删除（值为几）
void Josephus(SqList & , int , int , int );				//数数出列问题 


int main()
{
	SqList La, Lb, Lc;
	int i, n;
	ElemType e;
	
	printf("请输入线性表A的元素个数：\n");
	scanf("%d", &n);
	if(!InitList_Sq(La)) printf("Create Error!\n");
	printf("请输入线性表A的元素（非递减），用空格隔开：\n");
	for(i=1; i<=n; i++)
	{
		scanf("%d", &e);
		if(!ListInsert_Sq(La,i,e)) printf("Insert Error!\n");
	}
	printf("List A: ");
	Load_Sq(La);
	
	printf("请输入线性表B的元素个数：\n");
	scanf("%d", &n);
	if(!InitList_Sq(Lb)) printf("Create Error!\n");
	printf("请输入线性表B的元素（非递减），用空格隔开：\n");
	for(i=1; i<=n; i++)
	{
		scanf("%d", &e);
		if(!ListInsert_Sq(Lb,i,e)) printf("Insert Error!\n");
	}
	printf("List B: ");
	Load_Sq(Lb);
	
	MergeList_Sq(La, Lb, Lc);
	printf("List C: ");
	Load_Sq(Lc);
	
	InvertList_Sq(Lc);
	printf("Turned List C: ");
	Load_Sq(Lc);
	
	return OK;
}

Status InitList_Sq(SqList &L)
{
	L.elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem) return ERROR;
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;
}

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
	ElemType *p, *q;
	
	if(i<1 || i>L.length+1) return ERROR;
	if(L.length>=L.listsize)
	{
		L.elem = (ElemType *) realloc (L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!L.elem) return ERROR;
		L.listsize += LISTINCREMENT;
	}
	q = &(L.elem[i-1]);
	for(p=&(L.elem[L.length-1]); p>=q; p--)
		*(p+1) = *p;
	*q = e;
	L.length++;
	return OK;
}

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
	ElemType *p, *q;
	
	if(i<1 || i>L.length) return ERROR;
	e = L.elem[i-1];
	q = &(L.elem[L.length-1]);
	for(p=&(L.elem[i]); p<=q; p++)
		*(p-1) = *p;
	L.length--;
	return OK;
}

Status Load_Sq(SqList L)
{
	int i;
	
	if(L.length==0)
		printf("The list is empty!\n");
	else
		for(i=0; i<L.length; i++)
			printf("%d ", L.elem[i]);
	printf("\n");
	return OK;
}

Status MergeList_Sq(SqList La, SqList Lb, SqList &Lc)	//非递减 
{
	ElemType *pa, *pb, *pc;
	pa = La.elem; pb = Lb.elem;
	Lc.length = La.length + Lb.length;
	Lc.listsize = Lc.length;
	Lc.elem = (ElemType *) malloc (Lc.listsize * sizeof(ElemType));
	if(!Lc.elem) return ERROR;
	pc = Lc.elem;
	while(pa<=&(La.elem[La.length-1]) && pb<=&(Lb.elem[Lb.length-1]))
	{
		if(*pa <= *pb) *pc++ =*pa++;
		else *pc++ = *pb++;
	}
	while(pa <= &(La.elem[La.length-1])) *pc++ = *pa++;
	while(pb <= &(Lb.elem[Lb.length-1])) *pc++ = *pb++;
	return OK;
}

Status InvertList_Sq(SqList &L)
{
	ElemType temp;
	int i, j;
	
	for(i=0, j=L.length-1; i<j; i++, j--)
	{
		temp = L.elem[i];
		L.elem[i] = L.elem[j];
		L.elem[j] = temp;
	}
	return OK;
}

删除线性表中所有值为e的元素

Status ListDelete_Sq1(SqList &L, ElemType e)
{
	int i=0, j;
	while(i<L.length)
	{
		if(L.elem[i] == e)
		{
			for(j=i+1; j<L.length;j++)
				L.elem[j-1] = L.elem[j];
			L.length--;
		}
		else i++;
	}
}

Josephus问题：设有n个人围在一个圆桌周围，现从第s个人开始报数，数到第m个人又出列…如此反复直到所有的人全部出列为只止。对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。

void Josephus(SqList &L, int n, int s, int m)	//n个人围在一个圆桌周围，现从第s个人开始报数，数到第m个人出列 
{
	int i, j;
	ElemType e;
	i=s; j=1;
	while(L.length!=0)
	{
		if(j==m)
		{
			if(!ListDelete_Sq(L, i, e)) printf("Delete Error!\n");
			printf("%d ", e);
			j=1;
		}
		else
		{
			j++; 
			if(i>=L.length) i=1;
			else i++;
		}
	}
}