实验二 单链表的操作

1．实验性质：设计性实验

2．要求：

（1）编程实现单链表的以下基本操作：建立单链表，查找单链表，插入单链表，删除单链表。

（2）采用单链表结构编程实现：两个有序单链表的归并运算。

3．目的：

（1）掌握线性表的链式存储结构；

（2）掌握单链表及其基本操作的实现。

实验步骤

1. 编写一个提示信息输入的函数，在main函数中调用提示信息。
2. 定义单链表函数体。
3. 单链表初始化。
4. 根据需要的内容编写相应的函数体。
5. 通过函数调用，将所需的内容展示出来。
6. 调整代码，尽可能向所需内容靠近。

实验记录

先定义一个单链表并进行初始化

#define OK 1
#define ERROR 0

using namespace std;

typedef int ElemType;                //定义数据类型，相当于给int取别名为ElemType
typedef struct LNode                 //定义单链表
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
typedef int Status;                  //定义数据类型，相当于给int取别名为Status

Status InitList(LinkList &L)         //单链表初始化
{
    L = new LNode;
    L->next=NULL;                    //头指针为空
    return OK;
}

 1. 查找单链表

LinkList p;    //定义一个新的指针p
LNode *LocateElem(LinkList L,ElemType e)    //查找单链表
{
    p=L->next;
    while(p && p->data != e)
        p=p->next;
    cout << e << "的位置是" << p << endl;
    return p;
}

2.  插入单链表

Status ListInsert(LinkList &L,int i,ElemType e)   //插入
{
    int j;
    p=L;j=0;
    while(p && (jnext;
        ++j;
    }
    if(!p || j>i-1)
    {
        cout << "插入位置错误，请重新输入" << endl;
        return ERROR;
    }
    LinkList s;
    s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

3.  删除单链表

Status ListDelete(LinkList &L,int i)           //删除
{
    int j;
    p=L;j=0;
    while((p->next) && (jnext;
        ++j;
    }
    if(!(p->next) || j>i-1)
    {
        cout << "删除位置错误，请重新输入" << endl;
        return ERROR;
    }
    LinkList q;
    q=p->next;
    p->next=q->next;
    delete q;
    return OK;
}

4. 单链表的合并并显示

void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)    //单链表合并
{
    LinkList pa;
    LinkList pb;
    LinkList pc;
    pa=LA->next;pb=LB->next;
    LC=LA;
    pc=LC;
    while(pa && pb)
    {
        if(pa->data <= pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else
        {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    pc->next=pa?pa:pb;
    delete LB;
}

void Display_List(LinkList L)                 //显示合并后单链表信息
{
    p=L->next;
    while(p)
    {
        cout << p->data << " ";
        p=p->next;
    }
    cout << endl;
}

根据实验要求编写需要显示的信息函数

void show()
{
    cout << "1----在单链表指定位置插入元素" << endl;
    cout << "2----获取单链表中指定元素位置" << endl;
    cout << "3----删除单链表指定位置元素" << endl;
    cout << "4----两个有序单链表的归并" << endl;
    cout << "5----显示单链表" << endl;
    cout << "    退出，输入一个负数" << endl;
}

根据实验要求编写main函数

int main()
{
    show();
    int n;
    LinkList LA;
    LinkList LB;
    LinkList LC;
    InitList(LA);
    InitList(LB);
    int i;
    ElemType e;

    while(1)   //这里因为合并要使用两个单链表，因此在查找和插入数据的地方
               //就直接进行了两个单链表的操作，可以根据自己的需要进行修改，原理一样
    {
        cout << "请输入操作代码：";
        cin >> n;
        if(n==1)
        {
            cout << "请输入LA要插入的位置和元素：";
            cin >> i >> e;
            ListInsert(LA,i,e);
            cout << "请输入LB要插入的位置和元素：";
            cin >> i >> e;
            ListInsert(LB,i,e);
        }
        else if(n==2)
        {
            cout << "请输入LA要获取的元素：";
            cin >> e;
            *LocateElem(LA,e);
            cout << "请输入LB要获取的元素：";
            cin >> e;
            *LocateElem(LB,e);
        }
        else if(n==3)
        {
            cout << "请输入LA要删除的元素位置：";
            cin >> i;
            ListDelete(LA,i);
            cout << "请输入LB要删除的元素位置：";
            cin >> i;
            ListDelete(LB,i);
        }
        else if(n==4)
        {
            MergeList_L(LA,LB,LC);
            cout << "两个有序单链表归并之后是：";
            Display_List(LC);
        }
        else if(n==5)
        {
            cout << "The list of LA is:";
            Display_List(LA);
            cout << "The list of LB is:";
            Display_List(LB);
        }
        else if(n<0)
        {
            break;
        }

        else
            cout << "输入有误，请重新输入" << endl;
    }
}

---

实验中遇到的问题

1. 单链表的显示很难实现，只能通过类似顺序表的方式按照出现的顺序进行显示出来。

2. 单链表的存储位置是随机的，没有固定的位置来进行存储，在查找单链表元素的位置时没法直观的表示出来，显示出来的位置是一个地址。

3. 插入单链表的代码因前后逻辑顺序的缘故导致错误调试了很久，最后发现是顺序错误。

4. 删除单链表采用的是顺序位置，并不是采用的地址来删除。

5. 两个有序单链表的归并只适用于有序单链表的合并实现，对于无序的单链表没有办法得到想要的结果。