[数据结构与算法]2.线性表的链式存储（单链表）

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//线性表（单链表存储实现）
//单链表节点定义--------------------------
typedef struct LNode{
	int data; //数据域
	struct LNode *next; //指针域 
}LNode, *LinkList;
//-------------------------------------------
//头插法建立单链表----------------------------
LinkList List_HeadInsert(LinkList &l){
	LNode *s;
	int x;
	l=(LinkList)malloc(sizeof(LNode)); //创建头节点
	l->next=NULL;   //初始链表 
	printf("请输入节点信息:");
	scanf("%d", &x);  //获取节点数据信息 
	while(x!=10086){ //当输入10086时链表建立结束
		s=(LNode*)malloc(sizeof(LNode)); //创建一个新节点
		s->data=x;   //给数据域赋值 
		s->next=l->next; //第一次插入是在头节点之后，所以第一个节点指针域为null,从第二个开始就不是null了 
		l->next=s; //将头节点指针指向插入节点 
		printf("请输入节点信息:");
		scanf("%d", &x); 
	} 
	return l;
}
//-------------尾插法建立单链表------------------------
LinkList List_EndInsert(LinkList &l){
	int x;
	l=(LinkList)malloc(sizeof(LNode)); //创建头节点
	LNode *s, *r=l;
	printf("请输入节点信息:");
	scanf("%d", &x);  //获取节点数据信息 
	while(x!=10086){ //当输入10086时链表建立结束
		s=(LNode*)malloc(sizeof(LNode)); //创建一个新节点
		s->data=x;   //给数据域赋值 
		r->next=s;  //前一个节点指向被插入节点 
		r=s; //尾指针指向链表尾部 
		printf("请输入节点信息:");
		scanf("%d", &x); 
	} 
	r->next=NULL; //插入完毕，尾指针设置为Null 
	return l;
	
} 
//-----------------------------------------------------
//按序号返回节点值, 返回数据为该节点指针值-----------------------------------
LNode *GetElem(LinkList &l, int i){
	int j=1;   //计数器，因为不能按下标获取元素，所以必须有这个计数器 
	LNode *p=l->next;  //获取头节点，用于遍历 
	if(i==0){   //输入值非法 
		return l;
	}
	if(i<1){  //输入值非法 
		return NULL;
	}
	while(p&&j<i){  //遍历链表，获取i所在位置指针 
		p=p->next;
		j++; 
	}
	return p;
} 
//----------------------------------------------------------- 
//---------按值查找表节点，返回该节点指针及位置--------------------
LNode *LocateElem(LinkList l, int e, int *s){
	LNode *p = l->next;  //获取头节点 
	int j=1;
	while(p!=NULL&&p->data!=e){ //遍历链表 
		p=p->next;
		j++;
	} 
	*s=j;
	return p; //返回该节点指针 
} 
//-----------------------------------------------
//-----按位置删除某一节点------------------------------
void DeleteNodePosition(LinkList &l, int i){
	LNode *p, *q;
	//查找前驱节点 
	p = GetElem(l, i-1);
	//找到被删除节点 
	q=p->next;
	//将前驱节点和被删除节点的后驱节点连接 
	p->next=q->next;
	//删除回收 
	free(q);	 
} 
//--------------------------------------------------------
//----按值删除第一个被查找的节点-------------------------
void DeleteNodeValue(LinkList &l, int e){
	LNode *p, *q;
	LNode *z;
	int s; 
	//找到被删除节点的位置 
	z = LocateElem(l, e, &s);
	//q为待删除节点的前驱节点的指针 
	p = GetElem(l, s-1);
	q=p->next;
	p->next=q->next;
	free(q);
}
//可以优化---------------------------------------------
//插入节点，在元素之前插入----------------------------
void HeadInsert(LinkList &l, int i, int e){
	//i为插入位置， e为插入元素
	LNode *p; 
	LNode *s; 
	//找到i的前驱节点
	p = GetElem(l, i-1);
	s=(LNode*)malloc(sizeof(LNode)); //创建一个新节点
	s->data=e;  //插入节点赋值 
	s->next=p->next; 
	p->next=s;
} 
//此处是找到插入节点的前一个节点插入，还可以直接在节点后插入，然后交换数据域即可（时间复杂度低）-----------------------------------------------

//---------------------求线性表长度----------------------
int LinkLength(LinkList &l){
	LNode *p = l->next;
	int length = 1;
	while(p!=NULL){
		p=p->next;
		length++;
	}
	return length-1;
} 
//-------------输出线性表信息--------------------------
void PrintfList(LinkList &l){
	LNode *p=l->next;
	while(p){
		printf("%d\t", p->data);
		p=p->next;
	}
}
//------------------------------------------------------- 
int main(){
}