本链表仅有的特殊之处就是设置了一个尾指针，以便达到前插法、后插法插入数据之前不会重置表的目的，简单说就是一个表，按照书上的写法，前插1,2,3，后插1,2,3之后链表是1 2 3。我的写法链表会是3->2->1->1->2->3。
创建单链表
1.头文件及宏定义
#include<iostream>
#include<stdio.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
2.定义链表结构体及类型重定义
typedef int Status;
typedef struct LNode{
int x;
struct LNode *next;
}LNode,*LinkList;
//上边那步可以分解为
/*
struct LNode{
int x;
struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
*/
3.声明函数以及定义全局变量
LinkList t;//尾指针
Status initList(LinkList &L);//初始化链表
void CreateList_L(LinkList &L,int n);//左（前）插法插入n个数据
void CreateList_R(LinkList &L,int n);//右（后）插法插入n个数据
Status GetElem(LinkList L,int i);//返回第i个结点的值
Status ListDelete(LinkList &L,int i);//删除第i个结点
void ListPrint(LinkList L);//遍历链表
void insert(LinkList &L,int i);//在第i个结点后插入一个结点
Status findMax(LinkList L);//找出这个链表中的最大值
Status print();//菜单界面
4.主函数
int main(){
int x=0,n=0;
LinkList L;
while(1){
print();
cin>>x;
switch(x){
case 1:initList(L);break;
case 2:cin>>n;
CreateList_L(L,n);break;
case 3:cin>>n;
CreateList_R(L,n);break;
case 4:cin>>n;
cout<<GetElem(L,n)<<endl;break;
case 5:ListPrint(L);break;
case 6:cin>>n;
insert(L,n);break;
case 7:cout<<findMax(L)<<endl;break;
case 8:cin>>n;
ListDelete(L,n);break;
case 9:return 0;
}
}
return 0;
}
5.initList
Status initList(LinkList &L){
L=new LNode;
L->next=NULL;
t=L;
return OK;
}
6.CreateList_L
void CreateList_L(LinkList &L,int n){
for(int i=0;i<n;++i){
LinkList p=new LNode;
if(t==L){
t=p;
}
cin>>p->x;
p->next=L->next;
L->next=p;
}
}
7.CreateList_R
void CreateList_R(LinkList &L,int n){
LinkList r=t;
for(int i=0;i<n;++i){
LinkList p=new LNode;
cin>>p->x;
p->next=NULL;
r->next=p;
r=p;
}
t=r;
}
8.GetElem
Status GetElem(LinkList L,int i){
LinkList p=L->next;
int j=1;
while(p&&j<i){
p=p->next;
++j;
}
if(!p||j>i){
cout<<"您要查找的元素不合法\n错误:";
return -1;
}
return p->x;
}
9.ListDelete
Status ListDelete(LinkList &L,int i){
LinkList p=L;
int j=0;
while((p->next)&&(j<i-1)){
p=p->next;
++j;
}
if(!(p->next)||(j>i-1)){
cout<<"您要删除的元素不合法\n错误:-1\n";
return -1;
}
LinkList q=p->next;
p->next=q->next;
delete q;
return OK;
}