数据结构实验报告

时间:2021-05-07 10:47:27

实验一    顺序表、单链表基本操作的实现

 

实验目的

1、顺序表

(1)掌握线性表的基本运算。

(2)掌握顺序存储的概念,学会对顺序存储数据结构进行操作。

(3)加深对顺序存储数据结构的理解,逐步培养解决实际问题的编程能力。

 

实验内容

1、 顺序表

1、编写线性表基本操作函数:

(1)InitList(LIST *L,int ms)初始化线性表;

(2)InsertList(LIST *L,int item,int rc)向线性表的指定位置插入元素;                         

(3)DeleteList1(LIST *L,int item)删除指定元素值的线性表记录;

(4)DeleteList2(LIST *L,int rc)删除指定位置的线性表记录;

(5)FindList(LIST *L,int item)查找线性表的元素;

(6)OutputList(LIST *L)输出线性表元素;

2、调用上述函数实现下列操作:

(1)初始化线性表;

(2)调用插入函数建立一个线性表;

(3)在线性表中寻找指定的元素;

(4)在线性表中删除指定值的元素;

(5)在线性表中删除指定位置的元素;

(6)遍历并输出线性表;

 

实验结果

1、顺序表

(1)流程图

 
   

 

 

 

 

(2)程序运行主要结果截图

 

 

 

 

 

 

(3)程序源代码

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

struct LinearList/*定义线性表结构*/

{

    int *list;       /*存线性表元素*/

    int size;        /*存线性表长度*/

    int Maxsize;     /*存list数组元素的个数*/

};

typedef struct LinearList LIST;

void InitList(LIST *L,int ms)/*初始化线性表*/

{

    if((L->list=(int*)malloc(ms*sizeof(int)))==NULL)

       {

           printf("内存申请错误");

             exit(1);

       }

       L->size=0;

    L->Maxsize=ms;

}

int InsertList(LIST *L,int item,int rc)/*item记录值;rc插入位置*/

{

    int i;

    if(L->size==L->Maxsize)/*线性表已满*/

       return -1;

    if(rc<0)

        rc=0;

    if(rc>L->size)

        rc=L->size;

    for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/

       L->list[i+=1]=L->list[i];

       L->list[rc]=item;

       L->size++;

       return 0;

}

void OutputList(LIST *L)/*输出线性表元素*/

{

    int i;

    for(i=0;i<L->size;i++)

        printf("%d",L->list[i]);

        printf("\n");

}

int FindList(LIST *L,int item)/*查找线性元素,返回值>=0为元素的位置,返回-1为没找到*/

{

    int i;

    for(i=0;i<L->size;i++)

        if(item==L->list[i])

        return i;

    return -1;

}

int DeleteList1(LIST *L,int item)/*删除 指定元素值得线性表记录,返回值为>=0为删除成功*/

{

    int i,n;

    for(i=0;i<L->size;i++)

        if(item==L->list[i])

        break;

    if(i<L->size)

    {

        for(n=i;n<L->size-1;n++)

            L->list[n]=L->list[n+1];

        L->size--;

        return i;

    }

    return -1;

}

int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/

{

    int i,n;

    if(rc<0||rc>=L->size)

        return -1;

    for(n=rc;n<L->size-1;n++)

    L->list[n]=L->list[n+1];

    L->size--;

    return 0;

}

int main()

{

    LIST LL;

       int i,r;

       printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.size,LL.Maxsize);

       InitList(&LL,10);

       printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.list,LL.Maxsize);

 

       while(1)

       {

           printf("请输入元素值,输入0结束插入操作:");

           fflush(stdin);/*清空标准输入缓冲区*/

           scanf("%d",&i);

           if(i==0)

            break;

           printf("请输入插入位置:");

           scanf("%d",&r);

           InsertList(&LL,i,r-1);

           printf("线性表为:");

           OutputList(&LL);

       }

       while(1)

       {

           printf("请输入查找元素值,输入0结束查找操作:");

           fflush(stdin);/*清空标准输入缓冲区*/

           scanf("%d ",&i);

           if(i==0)

            break;

           r=FindList(&LL,i);

           if(r<0)

            printf("没有找到\n");

           else

             printf("有符合条件的元素,位置为:%d\n",r+1);

       }

       while(1)

       {

           printf("请输入删除元素值,输入0结束查找操作:");

           fflush(stdin);/*清楚标准缓存区*/

           scanf("%d",&i);

           if(i==0)

            break;

           r=DeleteList1(&LL,i);

            if(i<0)

                printf("没有找到\n");

            else{

                printf("有符合条件的元素,位置为:%d\n线性表为:",r+1);

                OutputList(&LL);

            }

        }

        while(1)

       {

           printf("请输入删除元素位置,输入0结束查找操作:");

           fflush(stdin);/*清楚标准输入缓冲区*/

           scanf("%d",&r);

           if(r==0)

            break;

           i=DeleteList2(&LL,r-1);

           if(i<0)

            printf("位置越界\n");

           else

           {

               printf("线性表为:");

               OutputList(&LL);

           }

       }

}

 

链表基本操作

实验目的

2、链表

(1)掌握链表的概念,学会对链表进行操作。

(2)加深对链式存储数据结构的理解,逐步培养解决实际问题的编程能力。

 

实验内容

  1、编写链表基本操作函数:

(1)InitList(LIST *L,int ms)初始化链表;

(2)InsertList1(LIST *L,int item,int rc)向链表的指定位置插入元素;

(3)InsertList2(LIST *L,int item,int rc)向有序链表的指定位置插入元素;

(4)DeleteList(LIST *L,int item)删除指定元素值的链表记录;

(5)FindList(LIST *L,int item)查找链表中的元素;

(6)OutputList(LIST *L)输出链表中的元素;

2、调用上述函数实现下列操作:

(1)初始化链表;

(2)调用插入函数建立一个链表;

(3)在链表中寻找指定的元素;

(4)在链表中删除指定值的元素;

(5)遍历并输出链表;

 

实验结果

(1)、流程图:

 

 

 

 

 

 

 

 

 

 

(2)程序运行主要结果截图:

 

 

 

 

 

 

 

 

(3)程序源代码:

#include<stdio.h>

#include<malloc.h>

typedef struct list

{

    int data;

    struct list *next;

}LIST;

void initlist(LIST **p)

{

    *p=NULL;

}

void insertlist1(LIST **p,int item,int rc)

{

    int i;

    LIST *u,*q,*r;

    u=(LIST*)malloc(sizeof(LIST));

    u->data=item;

    for(i=1,r=*p;i<rc&&r!=NULL;i++)

    {

        q=r;

        r=r->next;

    }

    if(r==*p)

        *p=u;

    else

        q->next=u;

        u->next=r;

}

void insertlist2(LIST **p,int item)

{

    LIST *u,*q,*r;

    u=(LIST*)malloc(sizeof(LIST));

    u->data=item;

    for(r=*p;r!=NULL&&r->data<item; q=r,r=r->next)

       if(r==*p)

         *p=u;

       else

           q->next=u;

           u->next=r;

 

}

int deletelist(LIST **p,int item)

{

    LIST *q,*r;

    q=*p;r=q;

    if(q==NULL)

        return 1;

    if(q->data==item)

    {

        *p=q->next;

        free(r);

        return 0;

    }

    for( ;q->data!=item&&q->next!=NULL;r=q,q=q->next)

    if(q->data==item)

    {

        r->next=q->next;

        free(q);

        return 0;

    }

    return 1;

}

int findlist(LIST *p,int item)

{

    int i;

    for(i=1;p->data!=item&&p!=NULL;p=p->next,i++)

    return(p==NULL)?-1:i;

}

void outputlist(LIST *p)

{

    while(p!=NULL)

    {

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

        p=p->next;

    }

    printf("\n");

}

void freelist(LIST **p)

{

    LIST *q,*r;

    for(q=*p;q!=NULL;)

    {

        r=q;

        q=q->next;

        free(r);

    }

    *p=NULL;

}

int main()

{

    LIST *p;

    int op,i,rc;

    initlist(&p);

    while(1)

    {

        printf("---------------\n");

        printf("- 1:指定位置追加\n");

        printf("- 2:升序追加\n");

        printf("- 3:查找结点\n");

        printf("- 4:删除结点\n");

        printf("- 5:输出链表\n");

        printf("- 6:清空链表\n");

        printf("- 0:退出\n");

        printf("--------------\n");

        printf("请输入0~6 进行操作:");

        fflush(stdin);

        scanf("%d",&op);

        switch(op)

        {

        case 0:

            return -1;

        case 1:

            printf("请输入新增结点的键值和位置:");

            scanf("%d%d",&i,&rc);

            insertlist1(&p,i,rc);

            break;

        case 2:

            printf("请输入新增结点的键值:");

            scanf("%d",&i);

            insertlist2(&p,i);

            break;

        case 3:

            printf("请输入要查找结点的键值:");

            scanf("%d",&i);

            rc=findlist(p,i);

            if(rc>0)

               printf("  位置位 %d\n",rc);

            else

                printf("没有找到\n");

            break;

        case 4:

            printf("请输入要删除的结点的键值:");

            scanf("%d",&i);

            rc=deletelist(&p,i);

            if(rc==0)

                printf("删除成功!\n",rc);

            else

                printf("没找到!\n");

            break;

        case 5:

            printf("\n 链表内容为:\n");

            outputlist(p);

            break;

        case 6:

            freelist(&p);

            break;

        }

    }

}