C语言实现单链表（有源代码哦）

首先，第一次在学校里学习数据结构与算法的时候，大家可能会发现抄书上的代码建议无法实现相应的功能（至少小编是这样的，直到放寒假的时候才实现第一个算法）。

今天教大家手把手实现书上的单链表，希望能对大家数据结构的学习有所启发。

提示：书中的有些参考伪代码都是通过C++实现的，如果用C++实现会带来一些方便。

C语言实现顺序表的过程中的注意事项： 书中绪论1.3，抽象数据类型的表示与实现中，关于书中伪代码的相关介绍很重要不然都不知道里面的英文字符是什么意思。

代码如下图:

#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType ;
//这就是书上预定义的一些东西
//Status 表示函数返回值
//ElemType 代表元素的类型

 下面定义单链表的结构（每一种数据结构都有它的结构类型，其实就是一个结构体），代码如下:

typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;//对同一结构体指针类型起了两个名字 

接下来初始化单链表（前提是要现在主函数里定义一个指向第一个节点的指针(头指针)）看一下main函数代码（只看前两行代码即可，后面的需要定义其他函数之后在使用）：

int main()
{
	menu();//菜单
	LinkList L;//头指针 
                ......
}

 下面初始化单链表:

Status InitList(LinkList L)//初始化 
{
	L=(struct LNode *)malloc(sizeof(struct LNode)); //为头结点开辟一个节点大小的内存空间
	L->next=NULL;//L->等价于*(L).所以是把头指针指向的第一个接得按的指针域置空
	return OK;
}

 接下来创建单链表:

void CreateList(LinkList *L,int n)//创建单链表 
{	
	LNode *r,*p;
	*L=(struct LNode *)malloc(sizeof(struct LNode)); 
	(*L)->data=n;
	(*L)->next=NULL;
	int i;

	r=*L;
	for(i=0;idata));
		p->next=NULL;r->next=p;
		r=p;
	} 
	
}

 接下来大家还是看我下面的整体代码吧，我感觉本菜鸡已经写不下去了。

。

。

。

。

#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType ;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;//对同一结构体指针类型起了两个名字 

Status InitList(LinkList L)//初始化 
{
	L=(struct LNode *)malloc(sizeof(struct LNode)); 
	L->next=NULL;
	return OK;
}

void CreateList(LinkList *L,int n)//创建单链表 
{	
	LNode *r,*p;
	*L=(struct LNode *)malloc(sizeof(struct LNode)); 
	(*L)->data=n;
	(*L)->next=NULL;
	int i;

	r=*L;
	for(i=0;idata));
		p->next=NULL;r->next=p;
		r=p;
	} 
	
}

Status ListInsert(LinkList L,int i,ElemType e)//单链表插入 
{
	LNode *p;
	LNode *s;
	p=L;
	int j=0;
	while(p&&(jnext;
		++j; 
	}
	if(!p||j>i-1) return ERROR;
	s=(struct LNode *)malloc(sizeof(struct LNode)); 
	s->data=e;
	s->next=p->next;
	p->next=s;
	return OK;
}

LNode *LocateElem(LinkList L,ElemType e)//查找 *** 作 
{
	LNode *p;
	p=L->next;
	
	while(p && (p->data!=e))	
	{
		p=p->next;
	}
		
	return p;
}
Status GetElem(LinkList L,int i,ElemType *e)//取值 *** 作 
{
	LNode *p;
	p=L->next;
	int j=1;
	while(p&&jnext;
		++j;
	}
	if(!p||j>i) return ERROR;
	*e=p->data;
	return OK;
}

Status ListDelete(LinkList L,int i)//删除 *** 作 
{
	LNode *p,*q;
	p=L;
	int j=0;
	while((p->next)&&(jnext;
		++j;
	}
	if(!(p->next)||(j>i-1)) return ERROR;
	q=p->next;
	p->next=q->next;
	free (q);
	return OK;
}

void TraverseList(LinkList p)
{
	if(p)
	{
		printf("%d\n",p->data);//第一次遍历输出的是单链表长度 
		TraverseList(p->next);
	}
}

void menu()
{
	printf("*************\n1,初始化顺序表\n2,创建单链表\n3,插入\n4,结束\n5,查找\n6,删除\n7,取值\n8,递归输出各个节点\n*************\n");
}

int main()
{
	menu();
	LinkList L;//头指针 
//	LNode l;//头节点 
//	L=&l;
	
	int *z;
	int i,k,flag=1,e,n;
	while(flag)
	{
		printf("请输入指令\n");
		scanf("%d",&k);
		switch(k)
		{
			case 1:
				if(InitList(L)==OK)
					printf("内存分配成功\n");
				else
					printf("内存分配失败\n");
				break;
			case 2:
				printf("输入要创建的单链表的元素个数\n");
				scanf("%d",&n);
				printf("请输入各个元素 \n");
				CreateList(&L,n);
				printf("创建的单链表成功\n");
				printf("第二个元素值：%d\n",L->next->next->data);
				break;
			case 3:
				printf("请分别而输入插入位置和插入的数据\n");
				scanf("%d,%d",&i,&e);
				if(ListInsert(L,i,e)==OK)
					printf("插入成功\n");
				else
					 printf("插入失败\n");
					 break;
			case 4:
				flag=0;
				break;
			case 5: 
				printf("请输入要查找的数据:\n");
				scanf("%d",&e);
				if(LocateElem(L,e)==NULL)
					printf("查找失败\n");
				else
					printf("数据所在位置为%d\n",LocateElem(L,e));
				break;	
			case 6:
				printf("您要删除第几个数据:\n");
				scanf("%d",&i);
				if(ListDelete(L,i)==OK) 
					printf("删除成功\n");
				else
					printf("删除失败\n");
				break;
			case 7:
				z=&k;
				printf("您要取第几个数据:\n");
				scanf("%d",&i);
				if(GetElem(L,i,&k)==OK)
					printf("第%d个数据为:%d\n",i,k);
				else
					printf("取值失败\n");
				break;
			case 8:
				TraverseList(L);
				break;
			default:
				printf("输入有误\n");
				break;
		}
	}
}

代码中可能有一些错误或者定义了没有使用的变量，大家可以自己多研究一下。

大家一定要多敲多查才能慢慢理解，如果还有需要栈、队列、二叉树代码的小伙伴大家可以评论一下，我看有需要的话就分享给大家。

（我真是小菜鸡，本来还想写完，结果....呜呜呜）。