DataStructure----LinerList,线性表C实现
//=============================================================================
//LinerList.h
//=============================================================================
//初始化队列的长度
#define LIST_INIT_SIZE 100
//队列长度不足重新申请空间的默认增长幅度
#define LISTINCREMENT 10
//若干信号量定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 'o'
#define OUTB -2 //越界错误
//状态返回值类型定义
typedef int Status;
//队列元素定义
typedef struct Elemtyp
{
//不同需要的元素修改此处
int elem;
}ElemType;
//队列的类型定义
typedef struct Sq
{
ElemType *head;
int length;
int listsize;
}Sqlist;
//==============================================================
//函数声明部分:
//==============================================================
//线性表操作的工具函数
//比较函数
Status Compare ( ElemType e1, ElemType e2);
//访问函数
void Visit (Sqlist);
//线性表复制函数，把L1复制到L2中
Status Copy ( Sqlist L1, Sqlist L2);
//线性表的初始化
Status Init_Sq ( Sqlist &L );
//线性表空间的释放
Status Destory_Sq (Sqlist &L );
//线性表的清空
Status Clear_Sq ( Sqlist &L );
//判断是否空表
Status IsEmpty_Sq ( Sqlist L );
//获取当前表长
int Length_Sq ( Sqlist L );
//获取表中指定元素的值
Status GetElem_Sq ( Sqlist L, int i, ElemType &e );
//确定指定元素在表当中的位置
int LocateElem_Sq ( Sqlist L, ElemType e);
//返回指定位置元素的前驱
Status PriorElem ( Sqlist L, ElemType cur_e, ElemType &pri_e);
//返回指定位置元素的后继
Status NextElem ( Sqlist L, ElemType cur_e, ElemType &nex_e);
//对线性表的插入操作
Status ListInsert ( Sqlist &L, ElemType e, int pos);
//对线性表的删除操作
Status ListDelete ( Sqlist &L, ElemType &e, int pos);
//对线性表的遍历
Status Traverse ( Sqlist L);
//===============================================================================
//LinerList.cpp
//===============================================================================
//线性表加载文件
#include "stdafx.h"
#include "LinerList.h" //线性表定义文件
#include <malloc.h>
//函数实现部分
Status Init_Sq ( Sqlist &L)
{
L.head = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if ( !L.head) return OVERFLOW;
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}//Init_Sq
Status Destory_Sq ( Sqlist &L)
{
if ( !L.head) return ERROR;
free(&L);
L.head=NULL;
return OK;
}//Destory_Sq
Status Clear_Sq ( Sqlist &L)
{
int i;//内循环计数
if ( !L.head) return ERROR;
for(i = 0; i<L.length; i++)
L.head[i].elem = 0;
return OK;
}//Clear_Sq
Status IsEmpty_Sq ( Sqlist L)
{
if( !L.head) return TRUE;
return FALSE;
}//IsEmpty_Sq
int Length_Sq ( Sqlist L)
{
return L.length;
}//Length_Sq
Status GetElme_Sq ( Sqlist L, int pos, ElemType &e)
{
if( !L.head) return ERROR;
else if( pos < 0 || pos >= L.length)
return OVERFLOW;
e = L.head[pos-1];
return OK;
}//GetElem_Sq
Status Compare ( ElemType e1, ElemType e2)
{
if( e1.elem == e2.elem)
return TRUE;
return FALSE;
}//Compare
int LocateElem_Sq ( Sqlist L, ElemType e)
{
int i=0;//计数并记录位置
Status s;//判断是否找到
if ( !L.head) return ERROR;
for ( ; i < L.length; i++)
{
s = Compare ( L.head [ i - 1 ], L.head [ i - 2] );
if ( s) break;
}
if( s) return i;
return -1;
}//LocateElem_Sq
Status PriorElem ( Sqlist L, ElemType cur_e, ElemType &pri_e)
{
int _pos = 0;
_pos = LocateElem_Sq ( L, cur_e);
if ( _pos == -1) return ERROR;
else if ( _pos == 0 ) return OUTB;
pri_e = L.head[ _pos-1 ];
return OK;
}//PriorElem
Status NextElem ( Sqlist L, ElemType cur_e, ElemType &nex_e)
{
int _pos = 0;
_pos = LocateElem_Sq ( L, cur_e);
if ( _pos == -1) return ERROR;
else if( _pos == L.length-1 ) return OUTB;
nex_e = L.head [ _pos+1 ];
return OK;
}//NextElem
Status Copy ( Sqlist L1, Sqlist &L2)
{
if ( L1.head || L2.head) return ERROR;
else if ( L1.length <= L2.length ) return ERROR;
for ( int i = 0; i < L1.length; i++)
L2.head [ i ] = L1.head [ i ];
return OK;
}//Copy
Status ListInsert ( Sqlist &L, ElemType e, int pos)
{
ElemType *newbase;
if ( !L.head) return ERROR;
else if ( pos < 1 || pos > L.length+1 ) return OUTB;
if ( L.length == L.listsize)
{
newbase = ( ElemType *)realloc( L.head, ( L.length+LISTINCREMENT)
* sizeof ( ElemType) );
L.head = newbase;
}
for (int i = L.length; i >= pos-1; --i)
L.head [ i + 1 ] = L.head [ i ];
L.head [ i ] = e;
L.length++;
return OK;
}//ListInsert
Status ListDelete ( Sqlist &L, ElemType &e, int pos)
{
if( !L.head) return ERROR;
else if ( pos < 0 || pos >= L.length ) return OUTB;
for ( int i = pos-1; i < L.length-1; i++)
L.head [ i ] = L.head [ i+1 ];
L.length--;
return OK;
}//ListDelete
void Visit ( Sqlist L)
{
for ( int i = 0; i < L.length-1; i++)
printf ( " %d \n", L.head [ i ].elem);
}//Visit
Status Traverse ( Sqlist L)
{
if ( !L.head) return ERROR;
Visit( L);
return OK;
}//Traverse
