数据结构实验二

我就是我 2022-06-06 05:56 228阅读 0赞

# 实验目录 #

1、编写函数slnklist delx(linklist head, datatype x)，删除不带头结点单链表head中第一个值为x 的结点。  
并构造测试用例进行测试。

2、假设线性表（a1,a2,a3,…an）采用不带头结点的单链表存储，  
请设计算法函数linklist reverse1(linklist head)和  
void reverse2(linklist \*head)将不带头结点的单链表head就地倒置，  
使表变成（an,an-1,…a3.a2,a1）。并构造测试用例进行测试。

3、假设不带头结点的单链表head是升序排列的，设计算法函数linklist insert(linklist head,datatype x)，  
将值为x的结点插入到链表head中，并保持链表有序性。  
分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。

4、编写算法函数linklist delallx(linklist head, int x)，删除不带头结点单链表head中所有值为x的结点。

## 实验一 ##

/*编写函数slnklist delx(linklist head, datatype x)，删除不带头结点单链表head中第一个值为x 的结点。
    并构造测试用例进行测试。
    */
    /**********************************/
    /*文件名称：lab2_01.c             */
    /**********************************/
    
    // #include "slnklist.h"
    /*请将本函数补充完整，并进行测试*/
    linklist delx(linklist head,datatype x)
    {
        linklist p=head,q,pre=NULL;
        while(p&&p->info!=x)
        {
            pre=p;
            p=p->next;
        }
        if(p)
        {
            if(!pre) head=head->next;
            else pre->next=p->next;
            free(p);
        }
        return head;
    }
    
    int main()
    {
        datatype x;
        linklist head;
        head=creatbyqueue();		/*尾插入法建立单链表*/
        print(head);
        printf("请输入要删除的值：");
        scanf("%d",&x);
        head=delx(head,x);			/*删除单链表的第一个值为x的结点*/
        print(head);
        delList(head);				/*释放单链表空间*/
        return 0;
    }

## 实验二 ##

/**********************************/
    /*文件名称：lab2_02.c                 */
    /**********************************/
    /*
    假设线性表（a1,a2,a3,…an）采用不带头结点的单链表存储，
    请设计算法函数linklist reverse1(linklist  head)和
    void reverse2(linklist *head)将不带头结点的单链表head就地倒置，
    使表变成（an,an-1,…a3.a2,a1）。并构造测试用例进行测试。
    */
    //#include "slnklist.h"
    /*请将本函数补充完整，并进行测试*/
    linklist reverse1(linklist head)
    {
        linklist p=head,q,pre=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            q->next=pre;
            pre=q;
        }
        return pre;
    }
    void reverse2(linklist *head)
    {
        linklist p=*head,pre=NULL;
        while(p!=NULL)
        {
            *head=p->next;
            p->next=pre;
            pre=p;
            p=*head;
        }
        *head=pre;
    }
    int main()
    {   datatype x;
        linklist head;
        head=creatbystack();		/*头插入法建立单链表*/
        print(head);				/*输出原链表*/
        head= reverse1(head);		/*倒置单链表*/
        print(head);				/*输出倒置后的链表*/
        reverse2(&head);			/*倒置单链表*/
        print(head);
        delList(head);
        return 0;
    }

## 实验三 ##

/*
    假设不带头结点的单链表head是升序排列的，设计算法函数linklist insert(linklist head,datatype x)，
    将值为x的结点插入到链表head中，并保持链表有序性。
    分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
    */
    /**********************************/
    /*文件名称：lab2_03.c                 */
    /**********************************/
    //#include "slnklist.h"
    /*请将本函数补充完整，并进行测试*/
    linklist insert(linklist head ,datatype x)
    {
        linklist pre=NULL,p=head,q,h;
        h=(node*)malloc(sizeof(node));
        h->info=x;
        while(p&&p->info<x)
        {
            pre=p;
            p=p->next;
        }
        if(pre==NULL)
        {
            h->next=head;
            head=h;
        }
        else if(p!=NULL)
        {
            h->next=p->next;
            p->next=h;
        }
        else
        {
            pre->next=h;h->next=NULL;
        }
        return head;
    }
    int main()
    {   datatype x;
        linklist head;
        printf("输入一组升序排列的整数：\n");
        head=creatbyqueue();				/*尾插入法建立单链表*/
        print(head);
        printf("请输入要插入的值：");
        scanf("%d",&x);
        head=insert(head,x);				/*将输入的值插入到单链表适当位置*/
        print(head);
        delList(head);
        return 0;
    }

## 实验四 ##

/*
    编写算法函数linklist delallx(linklist head, int x)，删除不带头结点单链表head中所有值为x的结点。
    */
    /**********************************/
    /*文件名称：lab2_04.c                 */
    /**********************************/
    //#include "slnklist.h"
    /*请将本函数补充完整，并进行测试*/
    linklist delallx(linklist head,int x)
    {
        linklist p=head,pre=NULL,q;
        do
        {
            while(p&&p->info!=x)
            {
                pre=p;
                p=p->next;
            }
            if(p){
                if(!pre) head=head->next,pre=NULL;
                else pre->next=p->next;
            }
            p=p->next;
        }while(p);
        return head;
    }
    int main()
    {
        datatype x;
        linklist head;
        head=creatbyqueue();				/*尾插入法建立单链表*/
        print(head);
        printf("请输入要删除的值：");
        scanf("%d",&x);
        head=delallx(head,x);
        print(head);
        delList(head);
        return 0;
    }