【数据结构】线性表顺序结构的操作---C/C++语言

本博客所有文章均已迁入到http://www.coderbean.com

预编译部分

#include <stdio.h>
#include <stdlib.h>
#ifndef __functiongs_h
#define __functiongs_h
#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10
#define ElemType int
#endif

定义结构体

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

各个操作函数

int InitList(SqList *L)//构造一个新的线性表L
{
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	//为新表L开辟内存空间
	if(!L->elem)
		return -1;//储存分配失败返回-1
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return 1;//储存分配成功返回1
}
void DestroyList(SqList *L)
//销毁一个顺序表
{
	free(L->elem);
	L->length = 0;
	L->listsize = 0;
}

void ClearList(SqList *L)//清空表
{
	L->length = 0;
}

bool ListEmpty (SqList *L)//判断是否为空表
{
	return (L->length == 0);
}

int ListLength(SqList *L)
{
	return L->length;
}

int GetElem(SqList *L,int i, ElemType e)
{
	if(i < 0 || i >= L->length)
		return -1;
	*e = L->elem[i];  //注意这里一定要写*e，传进来的是指针，我们要把值赋给那块内存
	return 1;
}

int LocateElem(SqList *L, ElemType e, bool (*compare)(ElemType a, ElemType b))
 {
	int i;  
	for (i = 0; i < L->length; ++i) 
	{
        if (compare(L->elem[i], e))
           return i;
	}       
	return -1;
}

int PriorElem(SqList *L, ElemType cur_e, ElemType *pre_e)
 {
	int i;
	for (i = 1; i < L->length; ++i) 
	{
		if (cur_e == L->elem[i]) 
		{
			if(cur_e ==  L->elem[0])
			{
				return -1;
			}
			*pre_e = L->elem[i-1];
			return 0;
		}
	}
	return -1;
 }

int NextElem(SqList *L, ElemType cur_e, ElemType *next_e)
 {
	int i;
	for (i = 1; i < L->length; ++i) 
	{
		if (cur_e == L->elem[i]) 
		{
			if(cur_e ==  L->elem[L->length-1])
			{
				return -1;
			}
			*next_e = L->elem[i+1];
			return 0;
		}	
	}
	return -1;
 }


int ListInsert (SqList *L,int i, ElemType e)
{
	if(i < 0 || i >= L->length)
		return -1;
	if(L->length >= L->listsize)
		ElemType *newbase = (ElemType*)realloc(L->elem, sizeof(ElemType) * (L->listsize + LIST_INCREMENT));
	if(!newbase)
	{
		return -1;
	}
	L->elem = newbase;
	L->listsize += LIST_INCREMENT;

	ElemType *p,*q;
	p = L->elem +i;
	for(q = L->elem + L->length ; q > =p+1; q--)
		*(q) = *(q-1);
	*p = e;
	L->length += 1;
	return 0;
}

int ListDelete (SqList *L,int i, ElemType e)
{
	if(i < 0 || i >= L->length)
		return -1;
	ElemType *p,*q;
	p = L->elem +i;
	for(q = L->elem + i ; p < L->elem + L->length-1; q--)
		*(q) = *(q+1);
	L->length -= 1;
	return 0;
}


int ListTraverse(SqList *L, int (*visit)(ElemType e))
 {
     int i, ret;
     for (i = 0; i < L->length; ++i)
	 {
         ret = visit(L->elem[i]);
         if (ret != 0)//如果函数失败，则操作失败，停止遍历
             return ret;
    }       
    return 0;        
}