数据结构基础--单链表的基本操作(创建，插入，删除和查找)C++

使用的头文件：

#include<iostream>
#include<malloc.h>
using namespace std;

单链表的结构体定义：

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

插入操作：

//在单链表的第i个位置插入元素e 
int insertLinklist(Linklist &L,int i,int e){
	Linklist p = L;
	int j = 0;
	while(p && j < i - 1){
		p = p->next;
		j++;
	} 
	if(p == NULL||i - 1 < j) return 0;//检查插入位置是否合法
	Linklist s;
	s = (Linklist)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

创建单链表：

//n为初始创建单链表时插入元素的个数,由于头插法，逆序输入N个元素的值进行插入 
void createLinklist(Linklist &L,int n){
	L = (Linklist)malloc(sizeof(LNode));//建立一个带有头结点的单链表
	L->next = NULL;
	Linklist p;
	for(int i = n;i > 0;i--){
		p = (Linklist)malloc(sizeof(LNode));
		cin>>p->data;
		p->next = L->next;
		L->next = p;
	} 
}

删除操作：

//删除位置i上的元素，并由e返回删除的元素 
int deletLinklist(Linklist &L,int i,int &e){
	Linklist p,q;
	p = L;
	int j = 0;
	while(p->next && i - 1 > j){//使p指向i位置的前驱 
		p = p->next;
		j++;
	} 
	if(!(p->next)||j > i - 1) return 0;//删除位置不合法
	q = p->next;
	p->next = q->next;
	e = q->data;
	free(q);//删除q
	return 1; 
}

输出链表中的元素：

void printLinklist(Linklist L){
	Linklist p;
	p = L->next;
	while(p->next != NULL){
		cout<<p->data<<endl;
		p = p->next;
	}
}

查询操作：

int getElem(Linklist L,int i,int &ee){
	Linklist  p;
	p = L->next;
	int j = 1;
	while(p && j < i){
		p = p->next;
		j++;
	}
	if(!p || j > i) return 0;
	ee = p->data;
	return 1;
}

主函数：

int main(){
	Linklist L;
	createLinklist(L,3);//创建一个长度为3的单链表
	insertLinklist(L,2,8);//向第二个位置插入8
	printLinklist(L);
	int e;
	deletLinklist(L,1,e);//删除第一个位置的元素
	cout<<"删除后的单链表"<<endl;
	printLinklist(L);
	int ee;
	getElem(L,2,ee);
	cout<<"查找的元素为："; 
	cout<<ee;
	return 0;
}