数据结构线性表的链式存储的基本操作

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
typedef long long elemtype;
typedef long long ll;
typedef struct node{
	elemtype data;
	struct node *next;
}Node,*Linklist;
//创建单链表 
void init(Linklist &head){
	head=(Linklist)malloc(sizeof(Node));//头结点
	head->data=0;//头结点的数据域代表链表的长度 
	head->next=NULL;
}
//在链表中正向输入n个数
void read_1(Linklist &head,ll n){
	head->data+=n;
	Linklist q=head,p;
	for(ll i=0;i<n;i++){
		p=(Linklist)malloc(sizeof(Node));
		q->next=p;
		p->next=NULL;
		scanf("%lld",&p->data);
		q=p;
	}
}
//在链表中反向输入n个数
void read_2(Linklist &head,ll n){
	head->data+=n;
	Linklist p;
	for(ll i=0;i<n;i++){
		p=(Linklist)malloc(sizeof(Node));
		p->next=head->next;
		scanf("%lld",&p->data);
		head->next=p;
	}
}
//输出链表中的元素
void output(Linklist head){
	Linklist p=head->next;
	while(p){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
	cout<<"此时链表的长度:"<<head->data<<endl;
} 
//查找单链表中第i个节点的数据并且存在一个变量中 
ll getelem_head(Linklist head,ll i,ll &e){
	Linklist p=head->next;
	ll j=1;
	while(p&&j<i){//寻找要求位置的节点------下同 
		p=p->next;
		j++;//j是用来计数 
	}
	if(j>i||p==NULL)return 0;//不合法的i值---(越界或者i<0)----下同 
	e=p->data;
	return 1;
}
//在链表的第i个位置插入一个节点;
ll Linklist_insert(Linklist &head,ll i,elemtype e){
	head->data+=1;
	Linklist p,q;
	p=head;
	ll j=1;
	while(p&&j<i){
		p=p->next;
		j++;
	}
	if(p==NULL||j>i)return 0;
	q=(Linklist)malloc(sizeof(Node));
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
} 
//在链表中删除第i个位置的节点
ll Linklist_delete(Linklist &head,ll i){
	head->data-=1;
	Linklist p,q;
	p=head;
	ll j=1;
	while(p&&j<i){
		p=p->next;
		j++;
	}
	if(p->next==NULL||j>i)return 0;
	q=p->next;
	p->next=q->next;
	free(q);
	return 1;
} 
//销毁链表
void Linklist_destroy(Linklist &head){
	Linklist p;
	while(head){
		p=head->next;
		free(head);
		head=p;
	}
} 
 
int main(){
	Linklist head;
	init(head);
	ll n;
	cout<<"输入要输入的元素的个数：";
	cin>>n;
	ll select;
	cout<<"输入1表示正向读入，2表示返向读入:";
	cin>>select;
	if(select==1){
	cout<<"正向读入："; 
	read_1(head,n);
	}
	else {
		cout<<"反向读入："; 
		read_2(head,n);
	}
	cout<<"此时链表的元素：";
	output(head);
	cout<<"输入要找的元素的位序1-n:";
	ll i,e;
	cin>>i;
	if(getelem_head(head,i,e)==0){
		cout<<"此元素不存在"<<endl;
	}
	else cout<<"此元素值为:"<<e<<endl;
	cout<<"输入要插入的元素:";
	cin>>e;
	cout<<"输入要插入的位置:";
	cin>>i;
	if(Linklist_insert(head,i,e)){
		cout<<"插入成功"<<endl;
		cout<<"此时链表的元素：";
		output(head);
	}
	else cout<<"不合法的位置"<<endl;
	cout<<"输入要删除元素的位置:";
	cin>>i;
	if(Linklist_delete(head,i)){
		cout<<"删除成功"<<endl;
		cout<<"此时链表的元素：";
		output(head);
	}
	else cout<<"不合法的位置"<<endl;
	Linklist_destroy(head);
	if(head==NULL)
	cout<<"销毁链表成功"<<endl; 
	else cout<<"销毁链表失败"<<endl;
	return 0;
}