单链表基本运算的实现

不带表头结点的单链表

#include
#include
typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct node
{
	ElemType element; //结点的数据域
	struct node* link;//结点的指针域
}Node;

typedef struct singleList
{
	Node* first;
	int n;
}SingleList;

//单链表的初始化
Status Init(SingleList *L)
{
	L->first = NULL;
	L->n = 0;
	return OK;
}


Status Find(SingleList L,int i,ElemType *x)
{
	Node* p;
	int j;
	if (i<0 || i>L.n - 1) //对i进行越界检查
		return ERROR;
	p = L.first;
	for (j = 0; j < i; j++)
		p = p->link; //从头结点开始查找a（i）
	*x = p->element;//通过x返回a（i）的值
	return OK;

}


Status Insert(SingleList *L,int i,ElemType x)
{
	Node* p, * q;
	int j;
	if (i<-1 || i>L->n - 1)
		return ERROR;
	p = L->first;
	for (j = 0; j < i; j++) p = p->link; //从头结点开始查找a（i）
		q = (Node*)malloc(sizeof(Node));//生成新结点q
	q->element = x;
	if (i>-1)
	{
		q->link = p->link; //新结点插在p所指结点之后
		p->link = q;
	}
	else
	{
		q->link = L->first; //新结点插在头结点之前，成为新的头结点
		L->first = q;
	}
	L->n++;
	return OK;
}


Status Delete(SingleList *L,int i)
{
	int j;
	Node* p, * q;
	if (!L->n)
		return ERROR;
	if (i<0 || i>L->n - 1)
		return ERROR;
	q = L->first;
	p = L->first;
	for (j = 0; j < i - 1; j++)
		q = q->link;
	if (i == 0)
		L->first = L->first->link;//删除的是头结点
	else
	{
		p = q->link;//p指向a（i）
		q->link = p->link;//从单链表中删除p所指向的结点

	}
	free(p);//释放p所指结点的存储空间
	L->n--;
	return OK;
}



Status Output(SingleList* L)
{
	Node* p;
	if (!L->n) //判断顺序表是否为空
		return ERROR;
	p = L->first;
	while (p)
	{
		printf("%d",p->element);
		p = p->link;
	}
	return OK;
}


void Destory(SingleList *L)
{
	Node* p;
	while (L->first)
	{
		p = L->first->link;//保存后继结点地址，防止"断链"
		free(L->first);//释放first所指结点的存储空间
		L->first = p;
	}
}



void main()
{
	int i;
	int x;
	SingleList list;
	Init(&list);//初始化线性表
	for (i = 0; i < 9; i++)
		Insert(&list,i-1,i);//线性表中插入新元素
	printf("the linklist is:");
	Output(&list);
	Delete(&list,0);
	printf("nthe linklist is:");
	Output(&list);
	Find(list,0,&x);
	printf("nthe value is:");
	printf("%d",x);
	Destory(&list);



}

输出结果

带表头结点的单链表

typedef struct headerList
{
	Node *head;
	int n;
}HeaderList;

typedef struct node
{
	ElemType element; //结点的数据域
	struct node* link;//结点的指针域
}Node;

//初始化
Status Init(HeaderList *h)
{
	h->head=(Node *)malloc(sizeof(Node));//生成表头结点
	if(!head)
		return ERROR;
	h->head->link=NULL;//设置单链表为空表
	h->n=0;
	return OK;
	
}

//插入
Status Insert(HeaderList *h,int i,ElemType x)
{
	Node *p,*q;
	int j;
	if(i<-1||i>h->n-1)
		return ERROR;
	p=h->head;
	for(j=0;j<=i;j++)//找到a（i）
		p=p->link;
	q=(Node *)malloc(sizeof(Node));
	q->element=x;
	q->link=p->link;
	p->link=q;
	h->n++;
	return OK;
}

//删除
Status Delete(HeaderList *h,int i)
{	
	int j;
	Node *p,*q;
	if(!h->n)
		return ERROR;
	if(i<0||i>h->n-1)
		return ERROR;
	q=h->head;
	for(j=0;jlink;
	p=q->link;
	q->link=p->link;//从单链表中删除p所指结点
	free(p);//释放p所指结点的存储空间
	h->n--;
	return OK;
	
}