单链表的基本操作

1. 定义结点的数据类型

#include<stdio.h>
#include<stdlib.h>

#define ERROR 0
#define OK 1

typedef int Status;
typedef int ElemType;
typedef struct LNode
{
	ElemType data; //数据域
	struct LNode *next; //指针域，由于指向整个结点，所以数据类型是struct LNode
}LinkNode;

2. 初始化链表（建立头结点）

LinkNode* InitList()
{
	LinkNode *L; 
    L =  (LinkNode *)malloc(sizeof(LinkNode));	
	L->next = NULL; //清空头结点指针域
	
	return L;  //返回头结点地址
}

3. 头插法

void List_HeadInsert(LinkNode *L,ElemType a[],int n)
{
	LinkNode *s;
	for (int i = 0;i<n;i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		s->next = L->next;
		L->next = s; 
	}
} 

4. 尾插法

void List_TailInsert(LinkNode *L,ElemType a[],int n) 
{
	LinkNode *s;
	LinkNode *r; //r指向链表的尾结点 
	r = L;
	
	for (int i=0;i<n;i++)
	{
		s = (LinkNode *)malloc(sizeof(LinkNode));
		s->data = a[i];
		r->next = s;
		r = r->next; 
	}
	r->next = NULL; //尾结点的指针域设为NULL 
}

5.遍历链表

void List_Show(LinkNode *L)
{
	LinkNode *p = L->next;
	
	while (p)
	{	
		printf("%d ",p->data);
		p = p->next; 
	 }
	printf("\n");
}

6. 判断链表是否为空

bool is_empty(LinkNode *L)
{
	return(L->next == NULL);
}

7. 求链表长度

int ListLength(LinkNode *L)
{
	LinkNode *p = L;
	int i = 0;
	
	while (p->next != NULL)
	{
		p = p->next;
		i++;
	 } 
	
	return(i);
}

8. 获取链表中第i个结点元素值

Status GetElem(LinkNode *L,int i,ElemType *e)
{//获取链表中第i个结点(不包括头结点)元素值
	LinkNode *p = L;
	int j=0;

	if (i<=0)
	{
		return ERROR;
	 }
    while (j<i && p)
    {
    	p=p->next;
    	j++;
	}

	if (p==NULL)
		return ERROR;
	*e = p->data;
	return OK;
}

9. 按元素值查找结点位置

int LocateElem(LinkNode *L,ElemType e)
{//按元素值查找结点位置
	int i = 0;
	LinkNode *p = L->next;

	while(p)
	{
		i++;
		if (p->data == e)
			return i;
		else
			p = p->next;
	 }

	 if(p==NULL)
	 	return 0;
}

10. 删除第i个结点

Status DeleteElem(LinkNode *L,int i, ElemType *e)
{//删除第i个结点，先要指向i-1个结点
	LinkNode *p = L;
	LinkNode *r;
	int j = 0;

	if(i<=0)
		return ERROR;

	while (j<i-1 && p)
	{
		p=p->next;
		j++;
	}

	if (!p)
		return ERROR;

	r = p->next;
	*e = r->data;
	p->next = r->next;
	free(r);
	return OK;
}

11. 在第i个结点处插入元素e

Status InsertElem(LinkNode *L,int i, ElemType e)
{//在第i个结点处插入元素e,先要找到i-1个结点
	LinkNode *p = L;
	LinkNode *s;
	int j = 0;

	if(i<=0)
		return ERROR;

	while (j<i-1 && p)
	{
		p=p->next;
		j++;
	}

	if (!p)
		return ERROR;

	s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = e;
	s->next = p->next;
	p->next =s;

	return OK;
}

12. 调用示例

int main()
{
	LinkNode *L = NULL;
	ElemType e,e2;
	ElemType a[] = {11,12,13,14,15};
    int length,i;

    L = InitList(); //把头结点的地址返回给L
	List_TailInsert(L,a,5);
	//List_HeadInsert(L,a,5);
	List_Show(L);
	is_empty(L);
	length = ListLength(L);
	printf("长度为：%d\n",length);


	GetElem(L,3,&e);
	printf("获取第5个元素的值为：%d\n",e);

	printf("请输入元素的值:");
	scanf("%d",&i);
	i = LocateElem(L,i);
	printf("元素的位置为：%d\n",i);


	printf("请输入要删除的元素的位置:");
	scanf("%d",&i);
    DeleteElem(L,i,&e2);
	printf("元素的值为：%d\n",e2);
	List_Show(L);

//	printf("请输入要插入的元素的位置:");
//	scanf("%d",&i);
//	printf("请输入要插入的元素的值:");
//	scanf("%d",&e2);
//    InsertElem(L,i,e2);
//	List_Show(L);

	return 0;
 }