单链表的操作

文档声明

本链表仅有的特殊之处就是设置了一个尾指针，以便达到前插法、后插法插入数据之前不会重置表的目的，简单说就是一个表，按照书上的写法，前插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;
}