线性表的顺序表示和实现 – 数据结构

欢迎访问我的新博客：http://www.milkcu.com/blog/

原文地址：http://www.milkcu.com/blog/archives/1368946860.html

基本概念

1. 线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素。
2. 线性表的顺序存储结构是一种随机存取的存储结构。
3. 通常用数组来描述数据结构中的顺序存储结构。

代码实现

算法2.3~2.7的类C代码实现如下：

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

typedef int ElemType;
typedef int Status;
typedef struct {
	ElemType * elem;
	int length;
	int listsize;
} SqList;
Status InitList_Sq(SqList & L);
Status ListInsert_Sq(SqList & L, int i, ElemType e);
Status ListDelete_Sq(SqList & L, int i, ElemType & e);
int LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType));
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc);
Status ShowList_Sq(SqList & L);
Status compare(ElemType a, ElemType b);

int main(void)
{
	//测试函数 
	SqList L;
	InitList_Sq(L);
	for(int i = 10; i > 0; i--) {
		ListInsert_Sq(L, 1, i);
	}
	ShowList_Sq(L);    //print L
	int e;
	ListDelete_Sq(L, 4, e);
	ShowList_Sq(L);    //print L
	printf("%d\n", LocateElem_Sq(L, 3, * compare));    //print location of 3
	//函数做参数如何传值呢？？ 
	SqList Lb;
	InitList_Sq(Lb);
	for(int i = 10; i > 0; i--) {
		ListInsert_Sq(Lb, 1, 2 * i);
	}
	ShowList_Sq(Lb);    //print Lb
	SqList Lc;
	InitList_Sq(Lc);
	ShowList_Sq(Lc);    //print Lc
	MergeList_Sq(L, Lb, Lc);
	ShowList_Sq(Lc);    //print Lc
	return 0;
}
Status InitList_Sq(SqList & L)
{
	//算法2.3 
	L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem) {
		exit(OVERFLOW);
	}
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;
}
Status ListInsert_Sq(SqList & L, int i, ElemType e)
{
	//算法2.4 
	//在顺序线性表L中第i个元素之前插入e 
	if(i < 1 || i > L.length + 1) {
		return ERROR;
	}
	if(L.length >= L.listsize) {
		ElemType * newbase = (ElemType *) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase) {
			exit(OVERFLOW);
		}
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	ElemType * q = & (L.elem[i - 1]);
	for(ElemType * 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)
{
	//算法2.5 
	if(i < 1 || i > L.length) {
		return ERROR;
	}
	ElemType * p = & (L.elem[i - 1]);
	e = * p;
	ElemType *q = L.elem + L.length - 1;
	for(++p; p <= q; ++p) {
		* (p - 1) = * p;
	}
	--L.length;
	return OK;
}
int LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType))
{
	//算法2.6 
	//指向函数的指针的使用 
	int i = 1;
	ElemType * p = L.elem;
	while(i <= L.length && !(* compare)(*p++, e)) {
		++i;
	}
	if(i <= L.length) {
		return i;
	} else {
		return 0;
	}
}
void MergeList_Sq(SqList La, SqList Lb, SqList & Lc)
{
	//算法2.7 
	//已知顺序线性表La和Lb的元素按值非递减排序，归并得到的Lc也按值亦是
	ElemType * pa = La.elem;
	ElemType * pb = Lb.elem;
	Lc.length = La.length + Lb.length;
	Lc.listsize = Lc.length;
	Lc.elem = (ElemType *) realloc(Lc.elem, Lc.listsize * sizeof(ElemType));
	ElemType * pc = Lc.elem;
	if(!Lc.elem) {
		exit(OVERFLOW);
	}
	ElemType * pa_last = La.elem + La.length - 1;
	ElemType * pb_last = Lb.elem + Lb.length - 1;
	while(pa <= pa_last && pb <= pb_last) {
		if(* pa <= * pb) {
			* pc = * pa; 
			pa++;
			pc++;
		} else {
			* pc = * pb;
			pb++;
			pc++;
		}
	}
	while(pa <= pa_last) {
		* pc = * pa;
		pa++;
		pc++;
	}
	while(pb <= pb_last) {
		* pc = * pb;
		pb++;
		pc++;
	}
}
Status ShowList_Sq(SqList & L)
{
	for(int i = 0; i < L.length; i++) {
		printf("%d  ", * (L.elem + i));
	}
	putchar('\n');
	return OK;
}
Status compare(ElemType a, ElemType b)
{
	return a == b;
}

注意：

• 函数作参数的传值方法；
• 指向函数的指针的使用。

参考资料

• 《数据结构：C语言版》（严蔚敏，吴伟民编著）

（全文完）