单链表的运算

顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：

1.从键盘输入10个整数，产生顺序表，并输入结点值。

2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。

3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。

4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。

二、源程序及注释：

#include

#include

/*单链表的定义*/

typedef int DataType;    /*DataType可以是任何相应的数据类型如int, float或char*/

typedef struct node            /*结点类型定义*/

{    DataType data;            /*结点的数据域*/

    struct node *next;        /*结点的指针域*/

}ListNode;

typedef ListNode *LinkList;

void main()

{    int i;

    DataType key,x;

    LinkList head;

    ListNode *p;

    LinkList CreateList(void);

    void PrintList(LinkList head);

    LinkList LocateNode(LinkList head,DataType key);

    LinkList GetNode(LinkList head,int i);

    void InsertList(LinkList head,DataType x,int i);

    void DeleteList(LinkList head,int i);    

    head=CreateList();        /*建立单链表*/

    PrintList(head);        /*打印单链表*/

    printf("输入要查找的值：");

    scanf("%d",&key);

    p=LocateNode(head,key);    /*单链表查找*/

    printf("请输入欲插入元素的位置：");

    scanf("%d",&i);

    printf("请输入欲插入的元素：");

    scanf("%d",&x);

    InsertList(head,x,i);    /*单链表插入*/

    PrintList(head);        /*打印单链表*/

    printf("请输入欲删除结点的位置：");

    scanf("%d",&i);

    DeleteList(head,i);        /*单链表删除*/

    PrintList(head);        /*打印单链表*/

    }

/*单链表的建立,从后向前生成*/

LinkList CreateList(void)

{    LinkList p,head=NULL;        //定义指针p和头指针

        int x;    

        scanf("%d",&x);

        while(x!=0)

        {

        p=(LinkList) malloc (sizeof(ListNode));//建立单链表

     p->data=x;

     p->next=head;

        head=p;

        scanf("%d",&x);

        }

        return head;//返回头指针

}

/*单链表的打印*/

void PrintList(LinkList head)

{    LinkList p;//定义指针p

        p=head;  

        if(p==NULL)

            printf("单链表为空\\n");//判断单链表是否为空

        while(p!=NULL)

        {

         printf("%d",p->data);//输出单链表的值

         p=p->next;

        }

}

/*单链表的查找,输入一个整数，    显示该结点的位置*/

LinkList LocateNode(LinkList head,DataType key)

{

        LinkList p;//定义指针p

        p=head;

        while(p!=NULL)

        {

         if(p->data==key)

                break;//当找到要查找的数时停止

         p=p->next;

        }

        if(p==NULL)

        {

            printf("没找到\\n");//显示没找到要找的数

        }

        else

        {

            printf("找到了\\n");//显示找到要找的数

        }

        return p;

}

/*单链表的查找2，在不带头结点的单链表head中查找第i个结点*/

LinkList GetNode(LinkList head,int i)

{    LinkList p;//定义指针p

    int j=0;

    p=head;

if(i<=0)

    {

        printf("ERROR\\n");//判断单链表是否存在

        exit(1);

    }

    while(p!=NULL)

    {    

        j++;

        if(j==i)

            break;    //找到数后程序停止，并计算结点数                

     p=p->next;

    }

    if(p==NULL)

    {

        printf("没有第i个结点\\n");//显示没找到要找的数

    }    

    return p;

}

/*单链表的插入*//*将值为x的新结点插入到不带头结点的单链表head的第i个结点的位置上*/

void InsertList(LinkList head,DataType x,int i)

{

    ListNode *p,*s;

    p=GetNode(head,i-1);        //寻找第i-1个结点

    if(p==NULL)

    {

        printf("插入位置非法\\n");//单链表为空无法进行操作

        exit(0);

    }

    s=(ListNode *)malloc(sizeof(ListNode));    //插入数值

s->data=x;

s->next=p->next;

p->next=s;

}

/*单链表的删除，删除不带头结点的单链表中的第i个结点*/

void DeleteList(LinkList head,int i)

{ListNode *p,*r;

    p=GetNode(head,i-1);        //寻找第i-1个结点

if(p==NULL||p->next==NULL)

        exit(0);//判断能否进行删除操作

    else

r=p->next;

p->next=r->next;

    free(r);        //释放第i个结点        

}

三、运行输出结果：

四、调试和运行程序过程中产生的问题及采取的措施：

    1、在进行单链表的查找时，总是显示找到了或时找不到，主要原因是在找到要找到的数后没停止运行，而且编程时while和if循环掌握的不是很好；

    2、插入时会出现符号，原因是在输入数时没打空格，等于只输入一个数，使得不能进行插入操作；

    3、当删除第i（i>1）个结点时，删除的是地i+1个结点。原因是在删除时是删除的查找到的元素后面的元素。解决方案是在查找时直接查找第i-1个结点，这样删除的元素便是第i个。

五、思考题

申请一个新的结点q，然后产生头结点为空的链表

q=(LinkList) malloc (sizeof(ListNode));

q->next=head;    

head=q;

最后再将以后程序中的p=head;改为p=head->next即可。

修改如下：

/*单链表的建立,从后向前生成*/

LinkList CreateList(void)

{    LinkList p,q，head=NULL;        //定义指针p和头指针

        int x;    

        scanf("%d",&x);

        while(x!=0)

        {

        p=(LinkList) malloc (sizeof(ListNode));//建立单链表

     p->data=x;

     p->next=head;

        head=p;

        scanf("%d",&x);

        }

       q=(LinkList) malloc (sizeof(ListNode));

q->next=head;    

head=q;

        return head;//返回头指针

}

六、实验总结：

    通过这个实验也使我认识到自己编程能力较差，由于在平时中不多进行练习，也不好好看书，将以前学的c语言知识忘了很多；在以后的学习中，应该多看书，认真钻研，加强编程方面的学习。

    在实验时遇到一些问题时，通过问别人，往往使自己茅塞顿开，而且省了很多时间。所以在平时学习时我们应该多问，这样可以少走很多弯路。

    通过这个实验加深了我对单链表的认识，学会了简单单链表的建立，查找，插入和删除等基本运算，并对运用C语言上机调试单链表的基本方法有了初步了解。