数据结构实验课：实验二、链表的实现及应用-阿里云开发者社区

数据结构实验课：实验二、链表的实现及应用

2022-11-30 204

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构实验课：实验二、链表的实现及应用

一、实验目的

了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：（1）建立一个线性表；（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。

三、程序代码：

#include <stdio.h>/该文件包含printf()等函数/
#include <stdlib.h>/该文件包含exit()等函数/
#include <malloc.h>/该文件包含malloc()等函数/
typedef int DataType;/定义DataType为int/
typedef struct Node
{
DataType data;
struct Node *next;
} SLNode;
void ListInitiate(SLNode **head)/初始化/
{
/如果有内存空间，申请头结点空间并使头指针head指向头结点/
if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
(*head)->next = NULL;/*置链尾标记NULL */
}
int ListLength(SLNode head) / 单链表的长度*/
{
SLNode *p = head;/p指向首元结点/
int size = 0;/size初始为0/
while(p->next != NULL)/循环计数/
{
p = p->next;
size ++;
}
return size;
}
int ListInsert(SLNode *head, int i, DataType x)
/在带头结点的单链表head的数据元素ai（0 ≤ i ≤ size）结点前/
/插入一个存放数据元素x的结点/
{
SLNode *p, *q;
int j;
p = head; /p指向首元结点/
j = -1;/j初始为-1/
while(p->next != NULL && j < i - 1)
/最终让指针p指向数据元素ai-1结点/
{
p = p->next;
j++;
}
if(j != i - 1)
{
printf(“插入位置参数错！”);
return 0;
}
/生成新结点由指针q指示/
if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
q->data = x;
//此段程序有一处错误
p->next = q->next;/给指针q->next赋值/
p->next = q;/给指针p->next重新赋值/
return 1;
}
int ListDelete(SLNode *head, int i, DataType *x)
/删除带头结点的单链表head的数据元素ai（0 ≤ i ≤ size - 1）结点/
/删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0/
{
SLNode *p, *s;
int j;
p = head; /p指向首元结点/
j = -1;/j初始为-1/
while(p->next != NULL && p->next->next!= NULL && j < i - 1)
/最终让指针p指向数据元素ai-1结点/
{
p = p->next;
j++;
}
if(j != i - 1)
{
printf(“删除位置参数错！”);
return 0;
}
//此段程序有一处错误
s->next = p; /指针s指向数据元素ai结点/
*x = s->data;/把指针s所指结点的数据元素域值赋予x/
p->next = s->next;/把数据元素ai结点从单链表中删除/
free(s);/释放指针s所指结点的内存空间/
return 1;
}
int ListGet(SLNode *head, int i, DataType *x)
/取数据元素ai和删除函数类同，只是不删除数据元素ai结点/
{
SLNode *p;
int j;
p = head;
j = -1;
while(p->next != NULL && j < i)
{
p = p->next;j++;
}
if(j != i)
{
printf(“取元素位置参数错！”);
return 0;
}
//此段程序有一处错误
*x = p->next;
return 1;
}
void Destroy(SLNode **head)
{
SLNode *p, *p1;
p = *head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
*head = NULL;
}
void main(void)
{
SLNode *head;
int i , x;
ListInitiate(&head);/初始化/
for(i = 0; i < 10; i++)
{
if(ListInsert(head, i, i+1) == 0) /插入10个数据元素/
{
printf(“错误! \n”);
return;
}
}
if(ListDelete(head, 4, &x) == 0) /删除数据元素5/
{
printf(“错误! \n”);
return;
}
for(i = 0; i < ListLength(head); i++)
{
if(ListGet(head, i, &x) == 0) /取元素/
{
printf(“错误! \n”);
return;
}
else printf("%d ", x);/显示数据元素/
}
Destroy(&head);
}

三、实验任务

1.改正上述程序中的错误。

2.编写合并函数，将两个有序的单链表合并成一个有序单链表。

3.完成实验报告的撰写。

代码如下

#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/
typedef int DataType;/*定义DataType为int*/
typedef struct Node
{
    DataType data;
    struct Node *next;
} SLNode;
void ListInitiate(SLNode **head)/*初始化*/
{
    /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/
    if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    (*head)->next = NULL;/*置链尾标记NULL */
}
int ListLength(SLNode *head)               /* 单链表的长度*/
{
    SLNode *p = head;/*p指向首元结点*/
    int size = 0;/*size初始为0*/
    while(p->next != NULL)/*循环计数*/
    {
        p = p->next;
        size ++;
    }
    return size;
}
int ListInsert(SLNode *head, int i, DataType x)
/*在带头结点的单链表head的数据元素ai（0 ≤ i ≤ size）结点前*/
/*插入一个存放数据元素x的结点*/
{
    SLNode *p, *q;
    int j;
    p = head; /*p指向首元结点*/
    j = -1;/*j初始为-1*/
    while(p->next != NULL && j < i - 1)
        /*最终让指针p指向数据元素ai-1结点*/
    {
        p = p->next;
        j++;
    }
    if(j != i - 1)
    {
        printf("插入位置参数错！");
        return 0;
    }
    /*生成新结点由指针q指示*/
    if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    q->data = x;
//此段程序有一处错误
    q->next = p->next;/*给指针q->next赋值*/
    p->next = q;/*给指针p->next重新赋值*/
    return 1;
}
int ListDelete(SLNode *head, int i, DataType *x)
/*删除带头结点的单链表head的数据元素ai（0 ≤ i ≤ size - 1）结点*/
/*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/
{
    SLNode *p, *s;
    int j;
    p = head; /*p指向首元结点*/
    j = -1;/*j初始为-1*/
    while(p->next != NULL && p->next->next!= NULL && j < i - 1)
        /*最终让指针p指向数据元素ai-1结点*/
    {
        p = p->next;
        j++;
    }
    if(j != i - 1)
    {
        printf("插入位置参数错！");
        return 0;
    }
//此段程序有一处错误
    s = p->next; /*指针s指向数据元素ai结点*/
    *x = s->data;/*把指针s所指结点的数据元素域值赋予x*/
    p->next = s->next;/*把数据元素ai结点从单链表中删除指*/
    free(s);/*释放指针s所指结点的内存空间*/
    return 1;
}
int ListGet(SLNode *head, int i, DataType *x)
/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/
{
    SLNode *p;
    int j;
    p = head;
    j = -1;
    while(p->next != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    if(j != i)
    {
        printf("取元素位置参数错！");
        return 0;
    }
//此段程序有一处错误
    *x = p->data;
    return 1;
}
void Destroy(SLNode **head)
{
    SLNode *p, *p1;
    p = *head;
    while(p != NULL)
    {
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}
int main()
{
    SLNode *head;
    int i, x;
    ListInitiate(&head);/*初始化*/
    for(i = 0; i < 10; i++)
    {
        if(ListInsert(head, i, i+1) == 0) /*插入10个数据元素*/
        {
            printf("错误! \n");
            return 0;
        }
    }
    if(ListDelete(head, 4, &x) == 0) /*删除数据元素5*/
    {
        printf("错误! \n");
        return 0;
    }
    for(i = 0; i < ListLength(head); i++)
    {
        if(ListGet(head, i, &x) == 0) /*取元素*/
        {
            printf("错误! \n");
            return 0;
        }
        else printf("%d    ", x);/*显示数据元素*/
    }
    Destroy(&head);
    return 0;
}

第二题

#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/
/*=====================================*/
typedef int DataType;/*定义DataType为int*/
typedef struct Node
{
    DataType data;
    struct Node *next;
} SLNode;
void ListInitiate(SLNode **head)/*初始化*/
{
    /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/
    if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    (*head)->next = NULL;/*置链尾标记NULL */
}
int ListLength(SLNode *head)               /* 单链表的长度*/
{
    SLNode *p = head;/*p指向首元结点*/
    int size = 0;/*size初始为0*/
    while(p->next != NULL)/*循环计数*/
    {
        p = p->next;
        size ++;
    }
    return size;
}
int ListInsert(SLNode *head, int i, DataType x)
/*在带头结点的单链表head的数据元素ai（0 ≤ i ≤ size）结点前*/
/*插入一个存放数据元素x的结点*/
{
    SLNode *p, *q;
    int j;
    p = head; /*p指向首元结点*/
    j = -1;/*j初始为-1*/
    while(p->next != NULL && j < i - 1)
        /*最终让指针p指向数据元素ai-1结点*/
    {
        p = p->next;
        j++;
    }
    if(j != i - 1)
    {
        printf("插入位置参数错！");
        return 0;
    }
    /*生成新结点由指针q指示*/
    if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    q->data = x;
//此段程序有一处错误 zjyigai
    q->next=p->next;/*给指针q->next赋值*/
    p->next = q;/*给指针p->next重新赋值*/
    return 1;
}
int ListGet(SLNode *head, int i, DataType *x)
/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/
{
    SLNode *p;
    int j;
    p = head;
    j = -1;
    while(p->next != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    if(j != i)
    {
        printf("取元素位置参数错！");
        return 0;
    }
//此段程序有一处错误 zjyigai
    *x = p->data;
    return 1;
}
void Destroy(SLNode **head)
{
    SLNode *p, *p1;
    p = *head;
    while(p != NULL)
    {
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}
void MergeList(SLNode *head1,SLNode *head2,SLNode **head3)
{
    int i=0,j=0,k=0,ai,bj;
    int La_len=ListLength(head1),Lb_len=ListLength(head2);
    while(i<La_len && j<Lb_len)
    {
        ListGet(head1,i,&ai);
        ListGet(head2,j,&bj);
        if(ai<=bj)
        {
            ListInsert(*head3,k++,ai);
            i++;
        }
        else
        {
            ListInsert(*head3,k++,bj);
            j++;
        }
    }
    while(i<La_len)
    {
        ListGet(head1,i++,&ai);
        ListInsert(*head3,k++,ai);
    }
    while(j<Lb_len)
    {
        ListGet(head2,j++,&bj);
        ListInsert(*head3,k++,bj);
    }
}
int main(void)
{
    SLNode *head1,*head2,*head3;
    int i , x;
    ListInitiate(&head1);/*初始化*/
    ListInitiate(&head2);
    ListInitiate(&head3);
    for(i = 0; i < 10; i++)
    {
        if(ListInsert(head1, i, i*2) == 0) /*插入10个数据元素*/
        {
            printf("错误! \n");
            return 1;
        }
        if(ListInsert(head2,i,i*2+1)==0)
        {
            printf("错误！\n");
            return 1;
        }
    }
    printf("head1:");
    for(i = 0; i < ListLength(head1); i++)
    {
        if(ListGet(head1, i, &x) == 0) /*取元素*/
        {
            printf("错误! \n");
            return 1;
        }
        else printf("%d ", x);/*显示数据元素*/
    }
    printf("\nhead2:");
    for(i = 0; i < ListLength(head2); i++)
    {
        if(ListGet(head2, i, &x) == 0) /*取元素*/
        {
            printf("错误! \n");
            return 1;
        }
        else printf("%d ", x);/*显示数据元素*/
    }
    MergeList(head1,head2,&head3);
    printf("\nhead3:");
    for(i = 0; i < ListLength(head3); i++)
    {
        if(ListGet(head3, i, &x) == 0) /*取元素*/
        {
            printf("错误! \n");
            return 1;
        }
        else printf("%d ", x);/*显示数据元素*/
    }
    Destroy(&head1);
    Destroy(&head2);
    Destroy(&head3);
}

数据结构实验课：实验二、链表的实现及应用

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构实验课：实验二、链表的实现及应用

热门文章

最新文章

相关课程

相关电子书