Yisohoo’s Blog!

 
/*
@author Yisohoo
@date 2009.5.18
@content:
顺序表的数据结构,包括:
初始化操作 initList(&L),
插入操作 listInsert(&L,i,e),
删除操作 listDelete(&L,i,&e),
合并操作 listMerge(la,lb,&lc)
@compiled by gcc 3.4.2
*/
 
 
#include<stdio.h>
//成功代码1
#define OK 1
#define YES 1
 
//错误代码0
#define ERROR 0
#define NO 0
 
//顺序表初始大小
#define LIST_INIT_SIZE 100
 
//线性表递增大小
#define LISTINCREMENT 10
 
//返回状态OK(1) or ERROR(0)
typedef int Status;
 
//顺序表的元素类型
typedef int ElemType;
 
//定义顺序表的结构体
typedef struct {
    //头指针
	ElemType *elem;
    //长度
	int listLength;
	//大小
	int listSize;
}SqList;
 
//顺序表初始化函数
Status initList(SqList *L) {
	//为头指针分配内存
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	//失败,返回错误代号0
	if(!L->elem) return ERROR;
    //把顺序表的元素长度设为初始长度0(没有元素)
	L->listLength = 0;
	//把线性表的大小设置为初始化设定的大小LIST_INIT_SIZE
	L->listSize = LIST_INIT_SIZE;
	//返回成功初始化线性表代码1
	return OK;
}
 
//判断是不是空表
Status listEmpty(SqList L) {
	if(L.listLength == 0)
	return YES;
	else
	return NO;
}
 
 
//顺序表插入操作
Status listInsert(SqList *L,int i,ElemType e) {
 
	//判断i是否合法
	if(i < 1 || i > L->listLength+1) {
		printf("sorry,the wrong argument i in listInsert\n");
		return ERROR;
	}
 
	//判断顺序表的长度是否大于它的容量,如果是,为表重新分配内存.
	if(L->listLength >= L->listSize) {
		ElemType *newBase = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
		if(!newBase) {
			printf("new mem for list error in listInsert\n");
			return ERROR;
		}
		L->elem = newBase;
		L->listSize += LISTINCREMENT;
	}
 
	//插入操作
 
	//声明两个临时ElemType型指针变量
	ElemType *p,*q;
 
	//p指向要插入的位置
	p = &(L->elem[i-1]);
 
//q开始指向最后一个元素,然后开始从q到p进行遍历,逐个把q指向的元素赋值给q+1指向的元素
	for(q = &(L->elem[(L->listLength)-1]); q >= p; --q) {
		*(q+1) = *q;
	}
 
	//在p处插入元素e
	*p = e;
 
	//表长度加1
	++L->listLength;
 
	return OK;
}
 
//删除操作
Status listDelete(SqList *L,int i,ElemType *e) {
 
	//判断i的合法性
	if(i<1 || i>L->listLength) {
		printf("wrong argument in listDelete");
		return ERROR;
	}
 
    //找到第i个元素
    ElemType *p;
	ElemType *q;
    p = &(L->elem[i-1]);
 
    //把要删除的元素赋值给e
    *e = *p;
    //q从要删除的元素开始左移
    for(q = p;q<&(L->elem[L->listLength]);q++) {
		*q = *(q+1);
	}
	L->listLength--;
 
	free(p);
	return OK;
}
 
//合并顺序表(la和lb是非递减顺序表)
Status listMerge(SqList la,SqList lb,SqList *lc) {
	int lengthLa,lengthLb,listLengthLc,listSizeLc;
	ElemType *laElem;
	ElemType *lbElem;
	ElemType *laLast;
	ElemType *lbLast;
	ElemType *lcElem;
	lengthLa = la.listLength;
	lengthLb = lb.listLength;
	laElem = la.elem;
	lbElem = lb.elem;
	laLast = &(la.elem[la.listLength-1]);
	lbLast = &(lb.elem[lb.listLength-1]);
	lc->listLength = lc->listSize = lengthLa + lengthLb;
	lcElem = lc->elem = (ElemType *)malloc(lc->listLength*sizeof(ElemType));
	if(!lc->elem) {
		printf("allocate mem ERROR in listMerge\n");
		return ERROR;
	}
	while(laElem <= laLast && lbElem <= lbLast) {
		if(*laElem <= *lbElem){
			*lcElem = *laElem;
			laElem++;
			lcElem++;
		}
		else {
			*lcElem = *lbElem;
			lbElem++;
			lcElem++;
		}
	}
	while(laElem <= laLast) {
		*lcElem = *laElem;
		lcElem++;
		laElem++;
	}
	while(lbElem <= lbLast) {
		*lcElem = *lbElem;
		lcElem++;
		lbElem++;
	}
	return OK;
}
 
//打印操作
void printList(SqList L) {
	int i;
	for(i=0;i<L.listLength;i++) {
		printf("%d\n",L.elem[i]);
	}
}
 
Status main() {
 
    //声明一个顺序表
	SqList la,lb,lc;
	int i;
	ElemType e;
 
	//初始化
	initList(&la);
	initList(&lb);
 
	//插入
	for(i = 0;i<=9;i++)
	listInsert(&la,i+1,i);
	printf("SqList la:\n");
    //打印
	printList(la);
 
    //插入
    for(i = 9;i<=19;i++)
	listInsert(&lb,i-8,i);
    //打印
	printf("SqList lb:\n");
	printList(lb);
 
    //从3号位置插入然后打印验证
	listInsert(&la,3,234);
	printf("SqList la append 234 at position 3:\n");
	printList(la);
 
    //从位置3删除然后打印验证
	listDelete(&la,3,&e);
	printf("the value you have deleted is %d\n",e);
	printList(la);
 
    //合并la和lb并打印验证
	printf("merging ... \n");
	listMerge(la,lb,&lc);
	printList(lc);
 
	getchar();
	return OK;
}