sqlist.c

顺序表是线性表的一种最简单的存储结构。大家多多支持

/*
 * 作者：     antigloss
 * 修改日期： 05-8-13 15:20
 * 欢迎光临 蚂蚁的C/C++标准编程
 * cpp.ga-la.com
 */

#include <stdio.h>
#include <stdlib.h>
#include "../header/sqlist.h"

/* begin of InitList 05-8-13 0:30 */
int InitList( Sqlist *L ) /* 创建顺序表 */
{
	/* malloc 返回值为 void 类型，不需要显式转换 */
	L->elem = malloc( INITSIZE * sizeof *L->elem ); /* 分配初始空间 */
	if ( !L->elem ) {
		return 0; /* 创建失败返回 0 */
	}

	/* 创建成功，初始化字符串长度和顺序表长度 */
	L->length = 0;
	L->listsize = INITSIZE;

	return 1; /* 创建成功返回 1 */
} /* end of InitList */

/* begin of InputList 05-8-13 2:15 */
int InputList(Sqlist *L) /* 接受用户输入的字符串 */
{
	unsigned i;
	L->length = 0;

	for ( i = 0; ( L->elem[i]=getchar() ) != '\n' && L->elem[i] != EOF ; ++i ) {
		++L->length;
		if ( L->length == L->listsize ) { /* 如果顺序表已满 */
			ElemType *newbase = realloc( L->elem,   /* 增加空间 */
				                   ( L->listsize + INCREMENT ) * sizeof *L->elem );
			if ( newbase ) { /* 如果分配成功 */
				L->elem = newbase;      /* 将指针指向新分配好的空间 */
				L->listsize += INCREMENT; /* 增大 listsize 的值 */
			} else { /* 分配空间失败 */
				return 0; /* 增加空间失败，返回 0 */
			}
		}
	}

	return 1;
} /* end of InputList */

/* begin of InsertList 05-8-13 5:00 */
int InsertList(Sqlist *L, unsigned pos)  /* 插入数据 */
{
	Sqlist tmp;  /* 用于暂时存储用户输入的字符 */
	long i;

	if ( !InitList( &tmp ) ) {
		return 0;
	}
	if ( InputList( &tmp ) ) {
		if ( !tmp.length ) {
			free(tmp.elem);
			return 1;
		}
		if ( L->listsize - L->length < tmp.length ) {
			ElemType *newbase = realloc( L->elem,
				                   ( L->listsize + tmp.length ) * sizeof *L->elem );
			if ( newbase ) {
				L->elem = newbase;
				L->listsize += tmp.length;
			} else {
				free(tmp.elem);
				return 0;
			}
		}

		--pos;
		/* 移动字符 */
		for ( i = L->length - 1; i >= (long)pos; --i ) {
			L->elem[i + tmp.length] = L->elem[i];
		}
		i = 0;
		while ( i < (long)tmp.length ) {
			L->elem[pos++] = tmp.elem[i++];
		}
		L->length += tmp.length; /* 更新字符串长度 */

		free(tmp.elem);
		return 1;
	}
	
	free(tmp.elem);
	return 0;
} /* end of InsertList */

/* begin of DelList 05-8-13 12:00 */
void DelList(Sqlist *L, unsigned pos, unsigned size)
{
	for ( --pos; pos + size < L->length; ++pos ) {
		L->elem[pos] = L->elem[pos + size];
	}
	L->length -= size;
} /* end of DelList */

/* begin of Union 05-8-13 12:30 */
int Union(Sqlist *L1, Sqlist *L2){ /* 求顺序表并集 */
	unsigned k;

	/* 开始进行并集操作 */
	if ( L1 == L2 ) { /* 如果 L1 和 L2 为同一顺序表 */
		return 1;
	}
	for ( k = 0; k < L2->length; ++k ) {
		/* 在顺序表 L1 中找不到顺序表 L2 中的第k+1个元素，将第k+1个元素插入顺序表 L1 */
		if ( !Location( L1, L2->elem[k]) ) {
			if ( L1->length == L1->listsize ) { /* 如果顺序表已满 */
				ElemType *newbase = realloc( L1->elem,  /* 增加空间 */
					                   ( L1->listsize + INCREMENT ) * sizeof *L1->elem );
				if ( newbase ) {
					L1->elem = newbase;
					L1->listsize += INCREMENT;
				} else {
					return 0; /* 增加空间失败，返回 */
				}
			}
			L1->elem[ L1->length ] = L2->elem[k]; /* 插入到表 L1 */
			L1->length++; /* 表 L1 长度增加 */
		}
	}

	return 1; /* 无误返回 */
} /* end of Union */

/* begin of Purge 05-8-13 13:00 */
void Purge(Sqlist *L) /* 删除表中重复元素 */
{
	unsigned i, j, k;

	for ( i = 0; i < L->length; i++ ) {
		for ( j = i+1; j < L->length; ) {
			if ( L->elem[i] == L->elem[j] ) { /* 若找到重复元素 */
				for ( k = j; k < L->length; k++ ) { /* 删除重复元素 */
					L->elem[k] = L->elem[k+1];
				}
				L->length--; /* 顺序表长度减1 */
			}
			else {
				j++;
			}
		}
	}
} /* end of Purge */

/* begin of Purge2 05-8-13 13:20 */
void Purge2(Sqlist *L)  /* 删除表中重复元素 */
{
	Sqlist T = *L;
	unsigned i;

	T.length = 1;
	for ( i = 1; i < L->length; i++ ) {
		if ( !Location( &T, L->elem[i] ) ) { /* 若找不到重复元素 */
			T.elem[T.length] = L->elem[i]; /* 插入 */
			T.length++; /* 更新长度 */
		}
	}
	L->length = T.length; /* 更新长度 */
} /* end of Purge2 */

/* begin of Bubble 05-8-13 14:10 */
void Bubble(Sqlist *L, unsigned ascend)
{
	ElemType temp;
	unsigned i, j, k = L->length - 1;
	unsigned l;

	if ( !L->length ) {
		return;
	}
	for ( l = 1; l; k-- ) {
		l = 0;
		for ( i = 0, j = 1; i < k; i++, j++ ) {
			/* 根据 ascend 的值进行升序或者降序排列 */
			if ( ( L->elem[i] < L->elem[j] ) ^ ascend ) {
				temp = L->elem[i];
				L->elem[i] = L->elem[j];
				L->elem[j] = temp;
				l = 1;
			}
		}
	}
} /* end of Bubble */

/* begin of Compare 05-8-13 14:40 */
int Compare(Sqlist *L1, Sqlist *L2) /* 比较两个顺序表 */
{
	unsigned k;

	if ( L1 == L2 )	{
		return 0;
	}
	for ( k = 0; k < L1->length && k < L2->length; k++ ) {
		if ( L1->elem[k] > L2->elem[k] ) {
			return 1;
		}
		if ( L1->elem[k] < L2->elem[k] ) {
			return -1;
		}
	}

	return L1->length - L2->length;
} /* end of Compare */

/* begin of Exchange 05-8-13 15:10 */
void Exchange(Sqlist *L, unsigned i)   /* 前N个元素和后M个元素互换 */
{
	/* 三次逆转 */
	Three( L, 0, i-1 );
	Three( L, i, L->length-1 );
	Three( L, 0, L->length-1 );
} /* end of Exchange */

/* begin of Three 05-8-13 14:55 */
void Three(Sqlist *L, unsigned i, unsigned j) /* 三次逆转法 */
{
	ElemType temp;

	for (; i < j; i++, j-- ) {
		temp = L->elem[i];
		L->elem[i] = L->elem[j];
		L->elem[j] = temp;
	}
} /* end of Three */

/* begin of Location 05-8-13 12:10 */
int Location(Sqlist *L, ElemType elem) /* 求元素位置 */
{
	unsigned l;

	for ( l=0; l < L->length && L->elem[l] != elem; l++ ) {
		;
	}
	if ( l == L->length ) { /* 在顺序表中找不到elem */
		return 0;    /* 返回0 */
	}

	return ++l; /* 找到则返回元素位置 */
} /* end of Location */

/* begin of Disp 05-8-13 15:20 */
void Disp( Sqlist *L, unsigned total_lists ) /* 显示顺序表信息 */
{
	unsigned short i;
	unsigned j;

	printf( "\n当前一共有 %u 个顺序表。每个表的数据如下：\n", total_lists );
	for ( i = 0; i < total_lists; i++ ) {
		printf( "\n顺序表 %d ：", i+1 );
		for ( j = 0; j < L[i].length; j++ ) {
			printf( "%c", L[i].elem[j] );
		}
		printf( "\n字符串长度：%u  顺序表长度：%u\n", L[i].length, L[i].listsize);
	}
} /* end of Disp */