sqlist.cpp

链表的实现程序

#include "SqList.h"
#include <iostream>
using namespace std;

// // // // // // // // // // // // // // // // // 初始化
Status SqList::InitList_Sq(SqList &L)
{
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;
}

// // // // // // // // // // // // // // // // // 插入元素
Status SqList::ListInsert_Sq(SqList &L,int i,ElemType e)
{    
	if(i<1||i>L.length+1) return ERROR;

	ElemType *newbase, *p , *q;  
	if(L.length >= L.listsize)// 增配空间
	{
		newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
		if(!newbase) exit(OVERFLOW);
		L.elem = newbase;
		L.listsize+=LIST_INIT_SIZE;
	}

	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 SqList::ListDelete_Sq(SqList &L, int i, ElemType &e)
{
	if(i<1||i>L.length) return ERROR;
	
	ElemType *p;
	p= &(L.elem[i-1]);
	e=*p;// 保留被删除的元素

	for(;p<=L.elem+L.length-2;p++)
	{
		*p = *(p+1);
	}
	L.length--;// 表长减一
	return OK;
}

// // // // // // // // // // // // // // // // //
Status SqList::compare(ElemType x, ElemType y)
{
	if(x==y)
		return OK;
	else
		return 0;
}

// // // // // // // // // // // // // // // // //返回e第一次出现时的位置，如果不存在，返回0
int SqList::LocateElem_Sq(SqList L,ElemType e)
{
	ElemType i, *p;
	i=1;
	p=L.elem;
	while(i<=L.length&&!compare(*p,e))
	{
		i++;
		p++;
	}
	if(i<=L.length)
		return i;
	else
		return 0;
}

// // // // // // // // // // // // // // // // // 输出线性表
void SqList::display(SqList L)
{
	if(0==L.length)
	{
		cout<<"这是一个空表";
	}
		else
	{
		int i=0;
		for(i=0;i<=L.length-1;i++)
		{
			if(0!=(i+1)%10)// if语句控制每10个字符换行输出
				cout<<L.elem[i]<<" ";
			else
				cout<<L.elem[i]<<endl;
		}
	}
		cout<<endl<<endl;
}