二、实验原理、实验内容

三、实验仪器设备及材料

四、操作方法与实验步骤

五、实验数据记录及处理

六、实验结果分析及讨论

    一、实验目的

1．掌握用Visual C++6.0上机调试单链表的基本方法

2．掌握单链表的插入、删除、查找、求表长以及有序单链表的逆序算法的实现

   二、实现内容

    1、单链表基本操作的实现

[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。

[基本要求]用链式存储结构实现存储

[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。

   三、实验步骤

         1、定义节点类型

       2、进行单链表的初始化

       3、查看初始化的单链表

       4、使用switch-case结构进行选择操作

          5、采用递归，使选择操作可以持续进行

    四、实验代码

#include

using namespace std;

typedef int ElemType;

typedef struct Lnode

{

    ElemType data;

    struct Lnode *next;

}Lnode,*LinkList;

LinkList LinkListInit()

{

    Lnode *L;

    L=(Lnode *)malloc(sizeof(Lnode));

    if(L == NULL)

    {

        printf("申请内存空间失败\n");

    }

    L->next = NULL;

    return L;

}

LinkList CreateList()

{

    Lnode *L;

    ElemType x;

    L=(Lnode *)malloc(sizeof(Lnode));

L->next = NULL;

//    scanf("%d " ,&x);

cin>>x;

    while(x != -1)

    {

        Lnode *p;

        p=(Lnode *)malloc(sizeof(Lnode));

        p->data=x;

        p->next=L->next;

        L->next=p;

//        scanf("%d " ,&x);

        cin>>x;

    }

    return L;

}

LinkList CreateListNormal()

{

    Lnode *L,*Last;

    ElemType x;

    L=(Lnode *)malloc(sizeof(Lnode));

L->next = NULL;

    Last = L;

cin>>x;

    while(x != -1)

    {

        Lnode *p;

        p=(Lnode *)malloc(sizeof(Lnode));

        p->data=x;

        Last ->next = p;

        Last=p;

        cin>>x;

    }

Last->next = NULL;

    return L;

}

int GetLocate(LinkList L,ElemType e)

{

    LinkList p;

    int i=1;

p = L->next;

    while(p)

    {

        if(p->data == e)

        {

            return i;

        }

        else

        {

            p = p->next;

        }

        ++i;

    }

    return -1;

}

LinkList InsertElemType(LinkList L,int mIndex,ElemType e)

{

    Lnode *pre, *p;

    int j=0;

    pre = L;

for(j=1;j    {

        pre = pre->next;

    }

    p=(Lnode *)malloc(sizeof(Lnode));

p->data = e;

p->next = pre->next;

pre->next = p;

    return L;

}

LinkList DeleteElemType(LinkList L, int mIndex,ElemType e)

{

    Lnode *p , *s, *q;

    int j=0 , k=0;

    q=L;

    while(q)

    {

        q=q->next;

        k++;

    }

if(mIndex<1 || mIndex>k)

    {

        return NULL;

    }

for(p=L;jnext != NULL;j++)

    {

        p=p->next;        

    }

    s=p->next;    

p->next = s->next;

e = s->data;

    free(s);

    return L;

}

void PrintLinkListTranfer(LinkList L)

{

    LinkList p,s,print;

p = L->next;

L->next = NULL;

    while(p)

    {

        s = p;

        p = p->next;

        s->next = L->next;

        L->next = s;

    }

for(print = L->next;print !=NULL;print = print->next)

    {

        printf("%d    ",print->data);

    }

cout<}

void PrintLinkList(LinkList L)

{

    LinkList p;

for(p = L->next;p !=NULL;p = p->next)

    {

        printf("%d    ",p->data);

    }

cout<}

void LengthLinkList(LinkList L)

{

    int length=0;

    Lnode *Len;

    Len = L;

while(Len->next != NULL)

    {

        length++;

        Len = Len->next;

    }

    cout<<"单链表的长度是:"<}

int main()

{

    LinkList L ;

    int k,m,choice;

    ElemType x;

    cout<<"初始化单链表，输入-1结束"<    //L = CreateList();

    L = CreateListNormal();

    PrintLinkList(L);

    printf("\\n");

    cout<<"1.查找元素"<    cout<<"2.插入元素"<    cout<<"3.删除元素"<    cout<<"4.倒序输出"<    cout<<"5.单链表长度:"<    cout<<"0.退出"<    cin>>choice;

    while(choice != 0)

    {

        switch(choice)

        {

        case 1:

            cout<<"输入要查找的元素"<            scanf("%d", &x);

            m = GetLocate(L,x);

            if(m == -1)

            {

                cout<<"输入位置不正确"<            }

            else

            {

                cout<<"元素的位置是："<            }

            break;

        case 2:

            cout<<"输入插入的位置：";

            cin>>k;

            cout<<"输入插入的值"<            scanf("%d", &x);

            InsertElemType(L,k,x);

            cout<<"插入后的元素是："<            PrintLinkList(L);

            break;

        case 3:

            cout<<"输入删除的元素位置"<            //scanf("%d    ",&x);

            cin>>x;

            DeleteElemType(L,x,k);

            cout<<"删除后的元素是："<            PrintLinkList(L);

            break;

        case 4:

            PrintLinkListTranfer(L);

            break;

        case 5:

            LengthLinkList(L);

            break;

        default:

            cout<<"重新输入"<            break;

        }

        cin>>choice;

    }

    return 0;

}

    五、实验结果

                                                               教 师 签 字：

                                                                           年     月