因为马上要毕业找工作了,平时从事dsp等底层软件的开发,根本没有学习数据结构。前段时间被网易游戏鄙视了,现在下定决心要认真学习数据结构。
贴上用vs2010写的代码,记录学习过程,参考用书为严蔚敏的c数据结构。
为方便输出,都使用c++的io流。
#include
#include
using namespace std;
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 5
#define FALSE 0
#define TRUE 1
#define ERROR 0
#define OK 1
#define INFEASIBLE -1
typedef int Status;
typedef int ElemType;
typedef Status (*Compare)(ElemType x,ElemType y);
typedef Status (*Visit)(ElemType* x);
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status CreatSqList(SqList* sql);
Status DestroySqList(SqList* sql);
Status ClearSqList(SqList* sql);
Status EmptySqList(const SqList* sql);
int LengthSqList(const SqList* sql);
Status GetElemSqList(const SqList *sql,int i,ElemType* e);
Status SetElemSqList(SqList* sql,int i,ElemType e);
int LocateElemSqList(const SqList *sql,ElemType e,Compare compare);
Status PriorElemSqList(const SqList *sql,ElemType eCur,ElemType* ePre);
Status NextElemSqList(const SqList *sql,ElemType eCur,ElemType* eNext);
Status InsertSqList(SqList* sql,int i,ElemType e);
Status DeleteSqList(SqList* sql,int i,ElemType* e);
Status TraverseSqList(SqList* sql,Visit visit);
void PrintSqList(const SqList* sl);
int main(void)
{
SqList sql;
if (CreatSqList(&sql)!=OK)
{
cout<<"creat error"<elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (sql->elem==NULL)
{
return OVERFLOW;
}
sql->length=0;
sql->listsize=LIST_INIT_SIZE;
return OK;
}
Status DestroySqList(SqList* sql)
{
free( sql->elem);
sql->length=0;
sql->listsize=0;
return OK;
}
Status ClearSqList(SqList* sql)
{
sql->length=0;
return OK;
}
Status EmptySqList(const SqList* sql)
{
if (sql->length>0)
{
return FALSE;
}
return TRUE;
}
int LengthSqList(const SqList* sql)
{
return sql->length;
}
Status GetElemSqList(const SqList *sql,int i,ElemType* e)
{
if (sql->elem==NULL)
{
return ERROR;
}
if (i<1||i>sql->length)
{
return ERROR;
}
*e=sql->elem[i-1];
return OK;
}
Status SetElemSqList(SqList* sql,int i,ElemType e)
{
if (sql->elem==NULL)
{
return ERROR;
}
if (i<1||i>sql->length)
{
return ERROR;
}
sql->elem[i-1]=e;
return OK;
}
int LocateElemSqList(const SqList *sql,ElemType e,Compare compare)
{
int i=1;
if (sql->elem==NULL)
{
return ERROR;
}
while((compare(sql->elem[i-1],e)!=TRUE)&&(sql->length>=i))
{
i++;
}
if (i>sql->length)
{
return FALSE;
}
return i;
}
Status PriorElemSqList(const SqList *sql,ElemType eCur,ElemType* ePre)
{
int i=1;
if (sql->elem==NULL)
{
return ERROR;
}
while(ilength&&sql->elem[i]!=eCur)
{
i++;
}
if (i>=sql->length)
{
return FALSE;
}
*ePre=sql->elem[i-1];
return OK;
}
Status NextElemSqList(const SqList *sql,ElemType eCur,ElemType* eNext)
{
int i=0;
if (sql->elem==NULL)
{
return ERROR;
}
while(i<(sql->length-1)&&sql->elem[i]!=eCur)
{
i++;
}
if (i>=(sql->length-1))
{
return FALSE;
}
*eNext=sql->elem[i+1];
return OK;
}
Status InsertSqList(SqList* sql,int i,ElemType e)
{
if (sql->elem==NULL)
{
return ERROR;
}
if (i<1||i>sql->length+1)
{
return ERROR;
}
if (sql->length>=sql->listsize)
{
sql->listsize+=LISTINCREMENT;
sql->elem=(ElemType*)realloc(sql->elem,sql->listsize*sizeof(ElemType));
}
for (int j=sql->length;j>=i;j--)
{
sql->elem[j]=sql->elem[j-1];
}
sql->length++;
sql->elem[i-1]=e;
return OK;
}
Status DeleteSqList(SqList* sql,int i,ElemType* e)
{
if (sql->elem==NULL)
{
return ERROR;
}
if (i<1||i>sql->length)
{
return ERROR;
}
*e=sql->elem[i-1];
for (int j=i;jlength;j++)
{
sql->elem[j-1]=sql->elem[j];
}
sql->length--;
return OK;
}
Status TraverseSqList(SqList* sql,Visit visit)
{
if (sql->elem==NULL)
{
return ERROR;
}
for (int i=0;ilength;i++)
{
if (visit(&sql->elem[i])==FALSE)
{
return FALSE;
}
}
return OK;
}
void PrintSqList(const SqList* sql)
{
for (int i=0;ilength;i++)
{
cout<elem[i]<<" ";
if ((i+1)%10==0)
{
cout<