线性表抽象数据类型的带头结点单链表实现

/*线性表抽象数据类型的带头结点单链表实现*/

#include

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define OVERFLOW -2

#define MAXSIZE 100

#define NULL 0

typedef int status;

typedef int elemtype;

typedef struct lnode{

elemtype data;

struct lnode *next;

}lnode,*linklist;

/*初始化*/

status initlist(linklist *l){

*l=(linklist)malloc(sizeof(lnode));

if(*l) {(*l)->next=NULL;

return OK;

}

else return OVERFLOW;

}

/*销毁*/

status destroylist(linklist *l){

linklist p;

while(*l){

p=*l;

*l=(*l)->next;

free(p);

}

return OK;

}

/*置空*/

status clearlist(linklist *l){

linklist p,q;

p=(*l)->next;

(*l)->next=NULL;

while(p){

q=p;

p=p->next;

free(q);

}

return OK;

}

/*求单链表长度*/

int listlength(linklist l){

linklist p;

int i=0;

p=l->next;

while(p){

i++;

p=p->next;

}

return i;

}

/*单链表空否*/

status listempty(linklist l){

if(l->next) return FALSE;

else return TRUE;

}

/*查找*/

int locateelem(linklist l,elemtype e){

int i=0;

linklist p;

p=l->next;

while(p){

i++;

if (p->data==e) return i;

p=p->next;

}

return 0;

}

/*读第i个元素*/

status getelem(linklist l,int i,elemtype *e){

int j=1;

linklist p;

p=l->next;

while(p&&(jj++;

p=p->next;

}

if (!p|| (j>i)) return ERROR;

*e=p->data;

return OK;

}

/*求前驱元素*/

status priorelem(linklist l,elemtype cur_e,elemtype *pre_e){

linklist p,q;

if(l->next&&(l->next->data==cur_e)) return ERROR;

q=l->next;

p=q->next;

while(p&&(p->data!=cur_e)){

q=p;

p=p->next;

}

if(!p) return ERROR;

*pre_e=q->data;

return OK;

}

/*求后继元素*/

status nextelem(linklist l,elemtype cur_e,elemtype *next_e){

linklist p;

p=l->next;

while(p&&(p->data!=cur_e))

p=p->next;

if(!p) return ERROR;

*next_e=p->next->data;

return OK;

}

/*在第i个位置插入元素e*/

status listinsert(linklist *l,int i,elemtype e){

int j=0;

linklist p,s;

p=*l;

while(p &&jj++;

p=p->next;

}

if(!p||(j>i-1)) return ERROR;

s= (linklist) malloc (sizeof(lnode));

s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

/*删除第i个元素*/

status listdelete(linklist *l, int i, elemtype *e) {

linklist p,q;

int j;

p=*l;

j=0;

while ( p->next&& jp=p->next;

++j;

}

if (!(p->next)||j>i-1) q=p->next;

p->next=q->next;

*e=q->data;

free(q);

return OK;

}

return ERROR;

/*遍历单链表*/

status listtraverse(linklist l){

linklist p;

p=l->next;

while(p){

printf(\"%d \

p=p->next;

}

printf(\"\\n\");

return OK;

}

/*尾插法建立顺序单链表*/

status listcreate(linklist *l){

linklist p,r,s;

elemtype e;

p=(linklist)malloc(sizeof(lnode));

r=p;

printf(\"input data(end by -1):\");

scanf(\"%d\

while(e!=-1){

s=(linklist)malloc(sizeof(lnode));

s->data=e;

r->next=s;

r=s;

scanf(\"%d\

}

r->next=NULL;

*l=p;

return OK;

}

/*主函数*/

main(){

linklist la,lb,lc;

int i;

elemtype e,pre_e,next_e;

listcreate(&la);

listtraverse(la);

printf(\"the length of the list is %d\\n\

printf(\"input i and e for insert:\");

scanf(\"%d %d\

if(listinsert(&la,i,e)) listtraverse(la);

else printf(\"i is error!\\n\");

printf(\"input i :\");

scanf(\"%d\

getelem(la,i,&e);

printf(\"the element is %d ,\

priorelem(la,e,&pre_e);

nextelem(la,e,&next_e);

printf(\"prior is %d,\

printf(\"next is %d\\n\

listdelete(&la,i,&e);

listtraverse(la);

}