算法－数据结构－链表

/****************************************************************
Title : list.c
Author : 张龙
Time : 200508
*****************************************************************/




#include "stdio.h"
#include "stdlib.h"



typedef int ElementType;

typedef struct _listnode
{
ElementType data;
struct _listnode *next;
} listnode;

typedef struct _list
{
listnode *firstnode;
int count;
} list;




/*========================functions declaration===================*/
void init(list *l);
int FreeList(list *l);
int IsEmpty(list *l);
int length(list *l);
int insert(list *l,ElementType x,int position);
int delete(list *l,ElementType x);
ElementType find(list *l,int position);
int traverse(list *l);




/*====================function implementation================*/
void init(list *l)
{
l->firstnode=0;
l->count=0;
}

int FreeList(list *l)
{

}

int IsEmpty(list *l)
{
if(!l->firstnode)
return 1;
else
return 0;
}

int length(list *l)
{
return l->count;
}

int insert(list *l,ElementType x,int position)
{
int i;
listnode *node,*tmp;

if (!l->firstnode){
node=l->firstnode= (listnode *) malloc(sizeof(listnode));
node->data = x;
node->next = 0;
}
else{
if(position==0){
node = (listnode *) malloc(sizeof(listnode));
node->data = x;
node->next = l->firstnode;
l->firstnode=node;
}
else{
/*找到position处结点的父结点*/
for(i=0;i if(i==0){
tmp=l->firstnode;
}
else{
tmp=tmp->next;
}
}

node = (listnode *) malloc(sizeof(listnode));
node->data = x;
node->next = tmp->next;
tmp->next=node;
}

}

l->count++;

return l->count;
}

int delete(list *l,ElementType x)
{

}

ElementType find(list *l,int position)
{
int i;
listnode *node;

if(position==0){
node=l->firstnode;
}
else{
/*找到position处结点的父结点*/
for(i=0;i if(i==0){
node=l->firstnode;
}
else{
node=node->next;
}
}

node=node->next;
}

return node->data;
}

int traverse(list *l)
{
int i,j;
j=length(l);

listnode *tmp;

for(i=0;i if(i==0){
tmp=l->firstnode;
printf("%d ",tmp->data);
}
else{
tmp=tmp->next;
printf("%d ",tmp->data);
}
}

printf("\n");

return;
}


/*========================main function========================*/
int main(int argc,char*argv[])
{
int i,j;
list *mylist;

mylist=(list *)malloc(sizeof(list));

init(mylist);

for(i=0;i<100;i++){
j=i+3;
insert(mylist,j,i);
printf("%d ",find(mylist,i));
}

printf("\n");

printf("the length of list is %d\n",length(mylist));

traverse(mylist);

if(IsEmpty(mylist))
printf("the list is empty\n");
else
printf("the list is not empty\n");

j=find(mylist,15);
printf("the 15th element of list is %d\n",j);

}