[数据结构与算法]数据结构-线性表的单链表存储和运算

其实也没什么好说的，是关于链表的数据结构的实现。
我觉得唯一需要提醒的一个点是：在函数里面不要直接调用L指针
最好新建新的指针（只在函数内使用）会避免很多问题的出现。

如何帮助我们更好地思考如何构建呢？
我觉得最好边想边画很好（至少很适合我）
要是没想清楚插入操作，你先画一下大致过程，照着写程序就好了。

为什么开始更新呢？（是因为在用链表写一元稀疏多项式地加减法orz）
写颓了来写文章换换心情orz
这是去年用数组写的：

点击这里！！去年的数组形式的一元稀疏多项式！！
【问题描述】

设计并实现线性表的单链表存储和运算。

【基本要求】

实现单链表的插入、删除和遍历运算，每种操作用一个函数实现。

插入操作：将一个新元素插入表中指定序号的位置。

删除操作：将指定序号的元素从表中删除。

遍历操作：从表头按次序输出所有元素的值，若是空表，则输出信息“empty list!”。

【实现提示】

1.程序运行时，首先在main函数中创建空的、带头结点的单链表。然后多次调用实现插入操作的函数（每次都将元素在序号1位置上插入），将元素依次插入表中，最后调用实现遍历操作的函数输出所有元素。之后再多次调用实现删除操作的函数将表还原为空表（每次都删除第1个元素，每删除一个元素后，将表中剩余元素都输出一次）。

2.单链表结点类型定义：

 typedef int ElemType;  //为简化起见，元素类型定义为整型

 typedef struct Node{

     ElemType data;

     struct Node *next;

 }Node, *LinkList;

3.为了简化指针参数传递，使用c++的引用参数，存储源程序时注意后缀名应为cpp。 （其他实验题目在此处的处理相同）

4．创建链表时，可以多次调用插入函数（插入函数的功能是在链表的第i个元素结点前插入一个新结点），通过不断地在链表中增加结点来实现，也可以定义一个专门创建链表的函数，调用一次该函数就完成链表中所有结点的创建（当然，此后需要在链表中插入一个新结点时调用前述的插入函数即可）。

【我的代码】（不要直接抄哦！

#include<bits/stdc++.h>
using namespace std;
//单链表的简单运算1.插入2.删除3.遍历
//单链表结点类型的定义
typedef struct Node{
	int data;
	struct Node *next;
}Node,*LinkList; 

int ListEmpty(LinkList &L){//判断链表是否为空：空返回1 
	if(L->next)return 0;//非空
	else return 1; 
}

void readList(LinkList &L){
	LinkList s=new Node;
	s=L->next;
	cout<<"【链表】："; 
	if(ListEmpty(L)){
		cout<<"Empty!"<<endl;
		return;
	}else{//链表不是空的，可能只有一个数据 
		while(s!=NULL){
			cout<<s->data<<" ";
			s=s->next;
		}
		cout<<endl;
	}
}

void ListInsert(LinkList &L,int num){//利用头插法
	//插入新的元素多次调用实现插入操作的函数（每次都将元素在序号1位置上插入）
	LinkList p=new Node;//p = (Node *)malloc(sizeof(Node));
	p->data=num;
	p->next=L->next;
	L->next=p;
	//cout<<"success!"<<L->next->data<<endl;
	readList(L);
} 

void ListDelete(LinkList &L){//删除操作的函数将表还原为空表
	//（每次都删除第1个元素，每删除一个元素后，将表中剩余元素都输出一次）。
	LinkList q=new Node;
	q=L->next;
	L->next=L->next->next;
	free(q);
	readList(L);
}

void menu(){
	cout<<"链表操作："<<endl<<"1.插入元素"<<endl<<"2.删除元素"<<endl;
	cout<<"按0退出;请选择："<<endl; 
}

int main(){
	//初始化 
	//L=(LinkList)malloc(sizeof(Node));
	LinkList L=new Node;
	L->next=NULL;
	
	int n=0;
	menu();
	scanf("%d",&n);
	while(n){
		if(n==1){
			int num,number; 
			cout<<"输入插入元素个数："<<endl;
			cin>>num;
			cout<<"现在请输入元素： "<<endl;
			while(num--){
				cin>>number;
				ListInsert(L,number);
			}
			
		}else if(n==2)ListDelete(L);
		
		menu();
		scanf("%d",&n);
		//system("cls");
	}
	return 0;
}