数据结构与算法-链表

#include <iostream>
#include <iomanip>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOWE -2

typedef int Status;
typedef int ElemType;

struct LNode{
    ElemType data;
    struct LNode* next;
};

typedef struct LNode* LinkList;

int length;

Status InitList_L(LinkList& L){
    L = new LNode;
    L->next=NULL;
    return OK;
}

void CreateList_R(LinkList& L,int n){
    LinkList p,r;
    L = new LNode;
    L->next=NULL;
    r=L;
    length = 0;
    cout<<"请输入"<<n<<"个整数,用空格隔开:"<<endl;
    for(int i=0;i<n;i++){
        p = new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
        length++;
    }
}

void CreateList_L(LinkList& L,int n){
    LinkList p;
    L = new LNode;
    L->next=NULL;
    length=0;
    cout<<"请输入"<<n<<"个整数,用空格隔开:"<<endl;
    for(int i=0;i<n;i++){
        p = new LNode;
        cin>>p->data;
        p->next=L->next;
        L->next=p;
        length++;
    }
}


Status GetElem_L(LinkList L,int i,ElemType& e){
    int j=1;
    LinkList p;
    p=L->next;
    while (j<i&&p){
        p = p->next;
        j++;
    }
    if (!p || j>i)
        return ERROR;
    e=p->data;
    return OK;
}

LinkList LocateElem_L(LinkList L,ElemType e){
    LinkList p;
    p=L->next;
    while (p&&p->data!=e)
        p = p->next;
    return p;
}

Status ListInsert_L(LinkList& L,int i,ElemType e){
    int j=0;
    LinkList p,s;
    p = L;
    while (p&&j<i-1){
        p = p->next;
        j++;
    }
    if(!p||j>i-1)
        return ERROR;
    s=new LNode;
    s->data = e;
    s->next=p->next;
    p->next=s;
    length++;
    return OK;
}

Status ListDelete_L(LinkList& L,int i){
    LinkList p,q;
    int j=0;
    p = L;
    while (p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1)
        return ERROR;
    q = p->next;
    p->next=q->next;
    delete q;
    length--;
    return OK;
}

int main(){
    int a,n,choose;
    ElemType e;

    LinkList L,p;
    cout<<"1.建立\n";
    cout<<"2.输入\n";
    cout<<"3.取值\n";
    cout<<"4.查找\n";
    cout<<"5.插入\n";
    cout<<"6.删除\n";
    cout<<"7.输出\n";
    cout<<"0.退出\n";
    choose = -1;
    while (choose!=0)
    {
        cout<<"请输入选项的数字:";
        cin>>choose;
        switch (choose){
            case 1:
                if(InitList_L(L))
                    cout<<"成功建立单链表\n\n";
                break;
            case 2:
                cout<<"请输入要创建的链表的长度:";
                cin>>n;
                CreateList_R(L,n);
                cout<<"输入信息完毕"<<endl;
                break;
            case 3:
                cout<<"请输入一个位置来取值:";
                cin>>a;
                if(GetElem_L(L,a,e))
                    cout<<"查找成功"<<endl<<"第"<<a<<"个元素的值是:"<<e<<endl;
                else
                    cout<<"查找失败\n"<<endl;
                break;
            case 4:
                cout<<"请输入要查找的元素值:";
                cin>>e;
                if(LocateElem_L(L,e)!=NULL)
                    cout<<"查找成功"<<endl<<"该值为:"<<LocateElem_L(L,e)->data<<endl;
                else
                    cout<<"查找失败!值"<<e<<"没有找到"<<endl;
                break;
            case 5:
                cout<<"请输入要插入的元素位置和元素值:";
                cin>>a>>e;
                if(ListInsert_L(L,a,e))
                    cout<<"插入成功\n"<<endl;
                else
                    cout<<"插入失败\n"<<endl;
                break;
            case 6:
                cout<<"请输入要删除元素的位置:";
                cin>>a;
                if(ListDelete_L(L,a))
                    cout<<"删除成功!位置"<<a<<"的值已经被删除"<<endl;
                else
                    cout<<"删除失败"<<endl;
                break;
            case 7:
                cout<<"当前链表的信息为:\n";
                p=L->next;
                while (p){
                    cout<<p->data<<" ";
                    p=p->next;
                }
            cout<<endl<<endl;
            default:
                break;
        }
    }
    return 0;
}

下面是带有注释解释版本,解释每行话的作用

#include <iostream>
#include <iomanip>//包含输入输出流的格式化操作
using namespace std;//用于命名空间

#define OK 1
#define ERROR 0
#define OVERFLOWE -2//宏定义

typedef int Status;//表示函数的返回状态
typedef int ElemType;//定义链表中的元素

struct LNode{   //定义结点的结构体
    ElemType data; //结点的数据域
    struct LNode* next;//结点的指针域
};

typedef struct LNode* LinkList; //使用自定义关键字将LinkList与LNode*等同,可以使用LinkList定义LNode型的指针变量

int length;//用于表示链表的长度

Status InitList_L(LinkList& L){ //初始化,链表的初始化函数名:InitList_L
    //分配结点
	L = new LNode; //生成新结点作为头结点,用头指针指向头结点
    L->next=NULL; //头结点的指针域置空
    return OK;
}
//尾插法建立单链表
void CreateList_R(LinkList& L,int n){
    LinkList p,r;//定义两个指针变量p、r,用于指向列表中的结点
    L = new LNode;//用new动态分配内存,创建新结点作为头结点,并将头指针L指向头结点。
    L->next=NULL;//建立一个带头结点的空链表
    r=L;//尾指针指向头结点
    length = 0;//初始化线性表的长度为0
    cout<<"请输入"<<n<<"个整数,用空格隔开:"<<endl;
    for(int i=0;i<n;i++){
        p = new LNode;//生成新节点
        cin>>p->data; //输入元素值赋值给新节点p的数据域
        p->next=NULL; //将p的指针域置空,因为p是新结点
        r->next=p;//将新结点p插入尾结点r之后
        r=p;//修改新的尾结点,r指向新的尾结点p
        length++;
    }
}
//前插法
void CreateList_L(LinkList& L,int n){
    LinkList p;
    L = new LNode;
    L->next=NULL;//置空
    length=0;
    cout<<"请输入"<<n<<"个整数,用空格隔开:"<<endl;
    for(int i=0;i<n;i++){
        p = new LNode;//分配空间
        cin>>p->data;//填上数据
        p->next=L->next;//头插,将新结点的指针域指向第一个结点
        L->next=p;
        length++;
    }
}

//按序号取值
Status GetElem_L(LinkList L,int i,ElemType& e){
    int j=1;//初始化,p指向第一个结点时j为1
    LinkList p;//定义了指向链表结点的指针变量p
    p=L->next;//将p赋值为指向链表中的第1个结点
    while (j<i&&p){
        p = p->next;//p后移,指向下一个结点
        j++;
    }
    if (!p || j>i)  //i值不合法,i>n或者i<0
        return ERROR;
    e=p->data; //取第i个结点得我数据域
    return OK;
}
//查找
LinkList LocateElem_L(LinkList L,ElemType e){
    LinkList p;
    p=L->next;
    while (p&&p->data!=e)
        p = p->next;
    return p;//返回指针
}
// 插入函数
Status ListInsert_L(LinkList& L,int i,ElemType e){
    int j=0;//计数器
    LinkList p,s;//s指向新插入的结点
    p = L; //p定义为头结点
    while (p&&j<i-1){
        p = p->next;
        j++;
    }
    if(!p||j>i-1)
        return ERROR;
    s=new LNode;
    s->data = e;
    s->next=p->next;//p指向的是前一个。比如s是第三个,p就是第二个
    p->next=s;//让p的下一个等于s,就是p指针后移
    length++;
    return OK;
}
// 删除
Status ListDelete_L(LinkList& L,int i){
    LinkList p,q;//q保存要删的元素
    int j=0;//计数器
    p = L;
    while (p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1)
        return ERROR;
    q = p->next;
    p->next=q->next;
    delete q;
    length--;
    return OK;
}

int main(){
    int a,n,choose;
    ElemType e;

    LinkList L,p;//定义了两个指向链结点的指针变量
    cout<<"1.建立\n";
    cout<<"2.输入\n";
    cout<<"3.取值\n";
    cout<<"4.查找\n";
    cout<<"5.插入\n";
    cout<<"6.删除\n";
    cout<<"7.输出\n";
    cout<<"0.退出\n";
    choose = -1; //将选择变量初始化为-1
    while (choose!=0)
    {
        cout<<"请输入选项的数字:";
        cin>>choose;
        switch (choose){ //根据用户的选择进入不同的分支
            case 1:
                if(InitList_L(L))
                    cout<<"成功建立单链表\n\n";
                break;
            case 2:
                cout<<"请输入要创建的链表的长度:";
                cin>>n;//从用户输入中读取链表长度
                CreateList_R(L,n);
                cout<<"输入信息完毕"<<endl;
                break;
            case 3://单链表按序号取值
                cout<<"请输入一个位置来取值:";
                cin>>a;
                if(GetElem_L(L,a,e))
                    cout<<"查找成功"<<endl<<"第"<<a<<"个元素的值是:"<<e<<endl;
                else
                    cout<<"查找失败\n"<<endl;
                break;
            case 4:
                cout<<"请输入要查找的元素值:";
                cin>>e;
                if(LocateElem_L(L,e)!=NULL)
                    cout<<"查找成功"<<endl<<"该值为:"<<LocateElem_L(L,e)->data<<endl;
                else
                    cout<<"查找失败!值"<<e<<"没有找到"<<endl;
                break;
            case 5:
                cout<<"请输入要插入的元素位置和元素值:";
                cin>>a>>e;
                if(ListInsert_L(L,a,e))
                    cout<<"插入成功\n"<<endl;
                else
                    cout<<"插入失败\n"<<endl;
                break;
            case 6:
                cout<<"请输入要删除元素的位置:";
                cin>>a;
                if(ListDelete_L(L,a))
                    cout<<"删除成功!位置"<<a<<"的值已经被删除"<<endl;
                else
                    cout<<"删除失败"<<endl;
                break;
            case 7:
                cout<<"当前链表的信息为:\n";
                p=L->next;
                while (p){
                    cout<<p->data<<" ";
                    p=p->next;//输出整个链表
                }
            cout<<endl<<endl;
            default:
                break;
        }
    }
    return 0;
}

评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注