【数据结构】单链表的c语言实现

定义单链表结构体

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

单链表的初始化

void init(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
}

尾插法创建单链表

void CreateListTail(LinkList &L){
	int n,e;
	LNode *temp = L;
	printf("以下使用尾插法创建单链表n输入要输入元素的个数n");
	scanf("%d",&n);
	for(int i=0;i
		LNode *a = (LNode *)malloc(sizeof(LNode));
		scanf("%d",&e);
		a->data = e;
		temp->next = a;
		a->next = NULL;
		temp=temp->next;
	}
}

前插法创建单链表

void CreateListHead(LinkList &L){
	int n,e;
	L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
	printf("以下使用前插法创建单链表n输入要输入元素的个数n");
	scanf("%d",&n);
	for(int i=0;i
		LNode *temp = (LNode *)malloc(sizeof(LNode));
		scanf("%d",&e);
		temp->data = e;
		temp->next = L->next;
		L->next = temp;
	}
}

删除单链表中某个元素

void DeleteList(LinkList &L,int i,int e){
//删除单链表L中第i个元素
	LNode *p,*q;
	int j=1;
	p=L;
	while(p->next && j
		p = p->next;
		j++;
	}
	if(!(p->next) || j>i)
		printf("删除元素失败n");
	q=p->next;
	p->next = q->next;
	e=q->data;
	free(q);	
}

计算单链表的长度

void LengthList(LinkList &L){
	int length = 0;
	LNode *p;
	p = L->next;
	while(p!=NULL){
		length++;
		p = p->next;
	}
	printf("链表长度:%dn",length);
}

单链表的整表删除

void ClearList(LinkList &L){
	LNode *p,*q;
	p=L->next;
	while(p!=NULL){
		q=p->next;
		free(p);
		p=q;
	}
	L->next = NULL;
}

输出整个单链表

void show(LinkList &L){
	LNode *p;
	p = L->next;
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("n");
}

完整程序

#include 
#include 

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//初始化单链表 
void init(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
}

//输出整个单链表 
void show(LinkList &L){
	LNode *p;
	p = L->next;
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("n");
}

//尾插法创建单链表 
void CreateListTail(LinkList &L){
	int n,e;
	LNode *temp = L;
	printf("以下使用尾插法创建单链表n输入要输入元素的个数n");
	scanf("%d",&n);
	for(int i=0;i
		LNode *a = (LNode *)malloc(sizeof(LNode));
		scanf("%d",&e);
		a->data = e;
		temp->next = a;
		a->next = NULL;
		temp=temp->next;
	}
}

//前插法创建单链表 
void CreateListHead(LinkList &L){
	int n,e;
	L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
	printf("以下使用前插法创建单链表n输入要输入元素的个数n");
	scanf("%d",&n);
	for(int i=0;i
		LNode *temp = (LNode *)malloc(sizeof(LNode));
		scanf("%d",&e);
		temp->data = e;
		temp->next = L->next;
		L->next = temp;
	}
}

//新元素插入单链表 
void InsertList(LinkList &L,int i,int e){
//在单链表L中第i个位置插入元素e 
	LNode *p,*s;
	int j=1;
	p=L;
	while(p!=NULL && j
		p = p->next;
		j++;
	}
	if(!p || j>i)
		printf("插入失败n");
	s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
}

//删除单链表中某个元素 
void DeleteList(LinkList &L,int i,int e){
//删除单链表L中第i个元素
	LNode *p,*q;
	int j=1;
	p=L;
	while(p->next && j
		p = p->next;
		j++;
	}
	if(!(p->next) || j>i)
		printf("删除元素失败n");
	q=p->next;
	p->next = q->next;
	e=q->data;
	free(q);	
	
}

//获取单链表中的元素 
void GetElem(LinkList &L,int i,int *e){
//使用变量e返回单链表L中的第i个元素值 
	int j=1;
	LNode *p;
	p=L->next;
	while(p!=NULL && j
		p=p->next;
		j++;
	}
	if(!p || j>i)
		printf("查询不到该元素n");
	*e=p->data;
}

//计算单链表的长度 
void LengthList(LinkList &L){
	int length = 0;
	LNode *p;
	p = L->next;
	while(p!=NULL){
		length++;
		p = p->next;
	}
	printf("链表长度:%dn",length);
}

//单链表的整表删除 
void ClearList(LinkList &L){
	LNode *p,*q;
	p=L->next;
	while(p!=NULL){
		q=p->next;
		free(p);
		p=q;
	}
	L->next = NULL;
}

int main(){
	LNode *L,*K;
	init(L);
	init(K);
	
	int m;
	int i,x;
	
	CreateListHead(L);
	printf("使用头插法创建的单链表:n");
	show(L);
	LengthList(L);
	printf("在i位置上输入一个值为x的元素:n");

	scanf("%d%d",&i,&x);
	InsertList(L,i,x);
	show(L);
	printf("在i位置上删除一个值为x的元素:n");
	scanf("%d%d",&i,&x);
	DeleteList(L,i,x);
	show(L);
	printf("在i位置上得到一个值为x的元素:n");
	scanf("%d",&i);
	GetElem(L,i,&m);
	printf("得到的元素值为:%dn", m);
	
	
	CreateListTail(K);
	printf("使用尾插法创建的单链表:n");
	show(K);
	LengthList(K);
	printf("在i位置上输入一个值为x的元素:n");
	scanf("%d%d",&i,&x);
	InsertList(K,i,x);
	show(K);
	printf("在i位置上删除一个值为x的元素:n");
	scanf("%d%d",&i,&x);
	DeleteList(K,i,x);
	show(K);
	printf("在i位置上得到一个值为x的元素:n");
	scanf("%d",&i);
	GetElem(K,i,&m);
	printf("得到的元素值为:%dn", m);
	
	return 0;
}