线性表链式存储-初始化、插入、删除、查找、读取操作（C语言）_链表的抽象数据类型定义为

一、单链表抽象数据类型定义：

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

#define  OK     1
#define  ERROR   0

typedef  int  Elemtype;//数据类型重定义 
typedef  int   Status;//状态类型重定义 
typedef struct LNode{
	Elemtype data;   //数据域 
	struct LNode *next;//指针域 
}LNode,*Linklist;

Status LengthList(Linklist *L); //函数声明 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、单链表的初始化：

/*单链表初始化 ，初始化成功返回1，否则返回0*/ 
Status Init_linklist(Linklist *L)
{
	*L=(Linklist)malloc(sizeof(LNode));//创建头结点 
	if(!(*L))                          //创建失败 
	{
		return ERROR;
	}
	(*L)->next=NULL;                    //将头结点的指针指向为空 
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11

三、尾插入构建单链表：

/*创建带头结点的单链表尾插法*/
void Creat_Linklist(Linklist *L,int n)
{
	Linklist p,q;
	int i;
	p = *L;
	for(i=0;i<n;i++)
	{
		printf("请输入链表第%d个元素：",i);
		q=(Linklist)malloc(sizeof(LNode));//创建新的节点 
		scanf("%d",&q->data);
		p->next=q;                      //头结点指针指向新生成的节点 
		p=q;                           //指针指向链尾 
	}
	p->next=NULL;                     //链尾节点的指针指向为空 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、单链表的插入：

/*带头结点的单链表插入，在i个位置前插入e，若成功则返回1，若失败则返回0*/
Status Insert_Linklist(Linklist *L,int i,Elemtype e)
{
	int j=1;
	Linklist p,q;
	p = *L;
	if(i<1||!p->next||i>LengthList(L))                       //插入位置不合理 
	{
		return ERROR;
	}
	while(p&&j<i)                     //找到插入点 
	{
		p=p->next;
		j++;
	}
	q=(Linklist)malloc(sizeof(LNode));//创建插入新节点 
	q->data=e;
	q->next=p->next;
	p->next=q;
	return OK;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、单链表的删除：

/*带头结点的单链表删除，删除第i个元素，并由e返回其值，删除成功则返回1，否则返回0*/
Status Delete_Linklist(Linklist *L,int i,Elemtype *e) 
{
	int j=1;
	Linklist p,q;
	p = *L;
	if(i<1||!p->next||i>LengthList(L))
	{
		return ERROR;
	}
	while(j<i&&p->next)
	{
		p=p->next;
		j++; 
	}
	
	q=p->next;
	*e=q->data;
	p->next=q->next; 
	free(q);
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

六、单链表的按值查找：

/*单链表按值查找*/
Status Locate_Linklist(Linklist *L,Elemtype e)
{
	int i=1;
	Linklist p,q;
	p = (*L)->next;
    while(p->data!=e&&p)
    {
    	p=p->next;
    	i++;
	}
	if(p->data!=e) return -1;
	else return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

七、单链表的按位读取：

/*单链表按序号查找,用e返回该序号元素的值,否则查找失败*/
Status Get_Linklist(Linklist *L,int i,Elemtype *e) 
{
	int j=1;
	Linklist p,q;
	p = *L;
	if(i<1||!p->next||i>LengthList(L)) 
	{
		return ERROR;
	}
	while(j<=i&&p)
	{
		p=p->next;
		j++;
	}
	if(j-1==i) 
	{
		 *e=p->data;
		 return OK;	
	}
	else  return ERROR;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

八、单链表表长：

/*单链表表长*/
Status LengthList(Linklist *L)
{
	int i=0;
	Linklist p,q;
	p = *L;
	if(p->next==NULL) return ERROR;
	while(p->next!=NULL)
	{
		i++;
		p=p->next;
	}
	return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

九、单链表的输出函数：

/*单链表输出函数*/
void Display(Linklist *L) 
{
	LNode *p;
	p=(*L)->next;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

十、主函数：

int main()
{
	int n,num,e,value;
	Linklist L;
	/*单链表的初始化*/
	value=Init_linklist(&L);
	if(value)
	printf("单链表初始化成功！\n");
	else return ERROR;
	printf("请输入单链表的长度:") ;
	scanf("%d",&n); 
	Creat_Linklist(&L,n);
	printf("单链表中各元素的值为：");
	Display(&L);
	
	/*单链表的插入*/
	printf("\n请输入插入的位置:");
	scanf("%d",&n);
	printf("请输入插入的元素：");
	scanf("%d",&num);
	Insert_Linklist(&L,n,num);
	printf("进行插入操作后\n单链表中各元素的值为：");
	Display(&L);
	
	/*单链表的删除操作*/
	printf("\n\n请输入删除的位置：");
	scanf("%d",&n);
	Delete_Linklist(&L,n,&e);
	printf("被删除元素的值为:%d",e);
	printf("\n进行删除操作后\n单链表中各元素的值为：");
	Display(&L);
	
	/*单链表按值查找*/
	printf("\n\n请输入要查找的值e= ");
	scanf("%d",&num);
	value=Locate_Linklist(&L,num);
	if(value>0) printf("该元素在线性表的位序位：%d",value);
	else printf("\n无该值，查找失败！");
	
	/*单链表按位查找*/
	printf("\n\n请输入要查找的位置：");
	scanf("%d",&n);
	value=Get_Linklist(&L,n,&e);
	if(value) printf("单链表中第%d位的值为%d",n,e);
	else printf("\nerror!") ;
	
	return 0; 	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

十一、运行效果截图：