数据结构实验一(2) 链表的基本操作

★观前提示：本篇内容为数据结构实验，代码内容经测试没有问题，但是可能会不符合每个人实验的要求，因此以下内容建议仅做思路参考。

①了解和掌握线性表的链式存储结构;

②掌握用C 语言上机调试线性表的基本方法;

③掌握线性表的基本操作:插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算,以及对相应算法的性能分析。

给定一段程序代码，程序代码所完成的功能为:

①建立一个线性表；

②依次输入数据元素 1,2,3,4,5,6,7,8,9,10；

③删除数据元素5；

④依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。

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

★温馨提示：以下代码均为改正过的代码，皆已经过测试。

#include 
#include 
#include 

typedef int DataType;


typedef struct Node
{
    DataType data;
    struct Node *next;
} SLNode;

void ListInitiate(SLNode **head)
{
    
    if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    (*head)->next = NULL;
}

int ListLength(SLNode *head)               
{
    SLNode *p = head;
    int size = 0;

    while(p->next != NULL)
    {
        p = p->next;
        size ++;
    }
    return size;
}

int ListInsert(SLNode *head, int i, DataType x)


{
    SLNode *p, *q;
    int j;

    p = head; 
    j = -1;
    while(p->next != NULL && j < i - 1)
        
    {
        p = p->next;
        j++;
    }

    if(j != i - 1)
    {
        printf("插入位置参数错！");
        return 0;
    }

    
    if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    q->data = x;

//此段程序有一处错误
    q->next = p->next;
    p->next = q;
    return 1;
}

int ListDelete(SLNode *head, int i, DataType *x)


{
    SLNode *p, *s;
    int j;

    p = head; 
    j = -1;
    while(p->next != NULL && p->next->next!= NULL && j < i - 1)
        
    {
        p = p->next;
        j++;
    }

    if(j != i - 1)
    {
        printf("插入位置参数错！");
        return 0;
    }

//此段程序有一处错误
    s = p->next; 
    *x = s->data;
    p->next = s->next;
    free(s);
    return 1;
}

int ListGet(SLNode *head, int i, DataType *x)

{
    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) 
        {
            printf("错误! n");
            return 0;
        }
    }
    if(ListDelete(head, 4, &x) == 0) 
    {
        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 
#include 
#include 

typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node *next;
} SLNode;

void ListInitiate(SLNode **head)
{
    
    if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    (*head)->next = NULL;
}

int ListLength(SLNode *head)               
{
    SLNode *p = head;
    int size = 0;

    while(p->next != NULL)
    {
        p = p->next;
        size ++;
    }
    return size;
}

int ListInsert(SLNode *head, int i, DataType x)


{
    SLNode *p, *q;
    int j;

    p = head; 
    j = -1;
    while(p->next != NULL && j < i - 1)
        
    {
        p = p->next;
        j++;
    }

    if(j != i - 1)
    {
        printf("插入位置参数错！");
        return 0;
    }

    
    if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
    q->data = x;

//此段程序有一处错误
    q->next=p->next;
    p->next = q;
    return 1;
}

int ListGet(SLNode *head, int i, DataType *x)

{
    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 Destory(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
        ListGet(head1,i,&ai);
        ListGet(head2,j,&bj);
        if(ai<=bj)
        {
            ListInsert(*head3,k++,ai);
            i++;
        }
        else
        {
            ListInsert(*head3,k++,bj);
            j++;
        }
    }
    while(i
        ListGet(head1,i++,&ai);
        ListInsert(*head3,k++,ai);
    }
    while(j
        ListGet(head2,j++,&bj);
        ListInsert(*head3,k++,bj);
    }
}
int main()
{
    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) 
        {
            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);
    }
    Destory(&head1);
	Destory(&head2);
	Destory(&head3);
	return 0;
}

• 通过本次实验，了解和掌握了线性表的顺序存储结构，对线性表有了进步的认识和了解。
• 通过多次尝试对线性表的代码实现，理解并掌握了用C语言上机调试线性表的基本办法
• 明白了线性表的代码实现逻辑，掌握了线性表的一些基本操作如：插入、删除、合并等

      对于顺序表和链表的基本操作，个人认为本章的难点在于对顺序表和链表的具象化理解，感觉将顺序表和链表看作一个思维图是一种较好的学习方法，还有一个难点就是编写算法的实现函数，初次编写的时候不知道要怎么去实现这种算法，通过查阅资料和了解算法本质，才逐渐明白了算法的实现过程。实验方案选择较为合理，同学们的热心帮助，老师的殷切指导无疑给我带来了很大的帮助，经过多方面努力算法设计正确及运行结果达到了预期。

2022.5.21记录：Code_流苏(CSDN)
如有任何疑问，评论回复，看到即回，欢迎大家多多交流学习！
★以上实验内容仅供参考。