为什么输入的集合输出来是逆序的

Question

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -1
#define OK 1;

typedef int Status; /**Status是函数类型，其值是函数结果状态代码，如OK等**/
typedef int ElemType; 
struct LNode               /* 结点定义 */     
{
    ElemType data;
    int Length;
    struct LNode *next;
};
typedef struct LNode *LinkList; /* 表的头指针类型 */

LinkList La,Lb;



//构造一个新的线性表,头指针
Status InitList(LinkList *L)
{
 
    *L=(LinkList)malloc(sizeof(struct LNode));
 
    if(!*L) exit(OVERFLOW);
    
    (*L)->next=NULL;
    // (*L)->data=-1;
    return OK;
}

/*

bool InitList(LinkList &L)//初始化链表  构建一个空的线性表 
{
L = (LNode *)malloc(sizeof(LNode));
if (L == NULL)
return false;
L->next = NULL;//定义头结点 
return true;
}

*/





//判断链表是否为空
/*
bool Empty(LinkList L)//判断链表是否为空 
{
    if (L->next == NULL)//若L为空，返回true，否则返回false 
        return true;
    return false;
}



*/






int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        p=p->next;
        i++;
    }
    return i;
}

/*

int Length(LinkList L)//求链表长度 
{
int j=0;
LNode *p = L;
while(1)//建立死循环，以尾结点指向NULL为判断条件，使循环break 
{
p = p->next;
j++;
if(p->next==NULL)
break;
}
return j;//返回链表长度 
}

*/










Status GetElem(LinkList L,int i,ElemType *e)
{ 
    int j=1; /* j为计数器 */
    LinkList p=L->next; /* p指向第一个结点 */
    while(p&&j<i) 
    {
        p=p->next;
        j++;
    }     
    if(!p||j>i)   /* 第i个元素不存在 */
        return ERROR;
    *e=p->data;   /* 取第i个元素 */
    return OK;
}

/*
int GetElem(LinkList L,int i)//查找第i位的值，并返回第i的值 
{
int j;
LNode *p = L;//创建一个结点并指向头结点 
for(j=0;j<i;j++)//利用循环，是p结点指向第i位 
p = p->next;
return p->data;//返回第i的值 
}


*/








int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(compare(p->data,e)) return i;
        p=p->next;
    }
    return 0;
}




Status ListEmpty(LinkList L)
{ /* 初始条件：链式存储的表L已存在。*/
    /*操作结果：若L为空表，则返回TRUE，否则返回FALSE */
    if(L->next)
        return FALSE;
    else
        return TRUE;
}

/*


Status ListInsert(LinkList *L,int i,ElemType e)//哭死
{
    printf("%d\n",e);
    int j=0;
    LinkList p=*L,s;
    while(p&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(!p||j>i-1) return ERROR;
    
    s=(LinkList)malloc(sizeof(struct LNode));
    s->data=e;

    s->next=p->next;
    p->next=s;


    return OK;
}


*/



Status ListInsert(LinkList *L,int i,ElemType e)//哭死
{
    printf("%d\n",e);
    int j=0;
    LinkList p=*L,s;
    while(p&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(!p||j>i-1) return ERROR;
    
    s=(LinkList)malloc(sizeof(struct LNode));
    s->data=e;
    
    s->next=p->next;
    p->next=s;
    
    
    return OK;
}







void CreateLise(LinkList *L)
{
    char ch='1';
    int inlist=FALSE;
    LinkList p;
    int data;
    int l=ListLength(*L);

    while(ch!='\n')
    {
        scanf("%d",&data);
        scanf("%c",&ch);
        p=*L;
        while(p)
        {
            if(p->data==data)
            {
                inlist=TRUE;
                break;
            }
            else inlist=FALSE;
            p=p->next;
        }
        if(inlist==FALSE) 
        {
                //printf("%d\n",ch);
            ListInsert(L,l+1,data);
        }                
    }
}




Status equal(ElemType a,ElemType b)
{
    if(a==b) return TRUE;
    else return FALSE;
}



void Union(LinkList *La, LinkList Lb) 
{ // 将所有在表Lb（代表B集合）中但不在La（代表A集合）中的数据元素插入到La中
    ElemType e;
    int La_len,Lb_len;
    int i;
    La_len=ListLength(*La); // 求表La的长度
    Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e); // 取表Lb中第i个数据元素赋给变量e
        //printf("%d\n",e);
        if(!LocateElem(*La,e,equal)) // 表La中不存在和e相同的元素,则将e插入La中
            ListInsert(La,La_len+1,e);
            
    }
}



//打印链表
void printList(LinkList L){
    
    LinkList head = L->next;
    while(head){
        printf("%d ",head->data);
        head=head->next;
    }
    
    
    printf("\n");
    int l=ListLength(L);
    if(l!=0) printf("该集合的元素个数：%d\n",l);
    else printf("该集合为空集合\n");
}



void Index_Sq()
{
 
    InitList(&La);
    printf("请输入你的第一个集合:");
    CreateLise(&La);
    printf("集合A为");
    printList(La); 
    
    
    
    InitList(&Lb);
    printf("请输入你的第二个集合:");
    CreateLise(&Lb);
    printf("集合B为");
    printList(Lb); //实现表LB的操作
    
    
    
    Union(&La,Lb);
    printf("集合A与集合B的并集为:");
    printList(La); //实现表LA与表LB并集的操作
    printf("\n");
    
}


int main()
{
      
    Index_Sq();    
    
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

在C语言中，我们可以实现逆序链表的方法基于递归结构，通过两种方式来处理： 方法一：迭代链表 首先，我们从头节点开始遍历整个链表，找到最后一个节点（即倒数第二个节点），然后将其指向前一个节点的下一个节点。接下来，我们跳过前一个节点，继续遍历后续的节点。重复这个过程，直到遍历完链表的所有节点。

以下是具体步骤：

1. 创建一个空指针prev，用于记录当前节点的前一个节点。
2. 定义一个辅助指针current，用于记录当前节点。
3. 使用一个循环，每次循环从头节点开始。
4. 当遇到最后一个节点时，更新prev和current指向下一个节点的指针，并停止循环。
5. 否则，继续执行循环。
6. 在循环内部，访问当前节点的下一个节点next，并将它更新为prev->next，同时记录下当前节点的索引。
7. 遍历完成后，检查current是否已经指向了prev（因为循环结束时，current会指向prev）。如果 current 已经指向了prev，说明当前节点在后半部分的链表中，我们需要调用getPrev()函数获取prev节点的前一个节点prev->prev，然后再返回。

以下是对应的代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef int Status;/**Status是函数类型，其值是函数结果状态代码，如OK等**/
typedef int ElemType; 

struct LNode               /* 结点定义 */     
{
    ElemType data;
    int Length;
    struct LNode *next;
};
typedef struct LNode *LinkList; /* 表的头指针类型 */

LinkList La,Lb;

Status InitList(LinkList *L)
{
 
    *L=(LinkList)malloc(sizeof(struct LNode));
 
    if(!*L) exit(OVERFLOW);
    
    (*L)->next=NULL;
    // (*L)->data=-1;
    return OK;
}

Status getPrev(Node* current)
{
    if(current)
    {
        Node* prev = current->prev;
        while(prev)
        {
            prev = prev->prev;
        }
        return prev;
    }
    return NULL;
}

int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        p=p->next;
        i++;
    }
    return i;
}

Status GetElem(LinkList L,int i,ElemType *e)
{ 
    int j=1; /* j为计数器 */
    LinkList p=L->next; /* p指向第一个结点 */
    while(p&&j<i) 
    {
        p=p->next;
        j++;
    }     
    if(!p||j>i)   /* 第i个元素不存在 */
        return ERROR;
    *e=p->data;   /* 取第i个元素 */
    return OK;
}

Status Equal(ElemType a,ElemType b)
{
    if(a==b) return TRUE;
    else return FALSE;
}

Status Union(LinkList *La, LinkList Lb) 
{ // 将所有在表Lb（代表B集合）中但不在La（代表A集合）中的数据元素插入到La中
    // 初始化指针数组以跟踪每个集合的元素数量
    int arr[2]; // 一个整型数组，存储两个集合中元素的数量

    // 获取并更新两个集合的长度
    int La_len,Lb_len;
    int i;
    La_len=ListLength(*La); // 求表La的长度
    Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        arr[i] = LA_len-i;
    }

    // 找到列表B中不存在于列表A中的元素
    for(i=1;i<=Lb_len;i++)
    {
        int elementIndex = Arr[i];
        if(elementIndex > 0 && Arr[elementIndex] < 0)
        {
            arr[elementIndex]--;
            continue; // 保留元素在列表A中
        }
        
        // 如果元素在列表A中且比列表B少，直接插入到列表A中
        if(arr[elementIndex] >= 0 && arr[elementIndex] <= La_len)
        {
            ElementType elem = *(ElemType*)(&arr[elementIndex]);
            Lb.InsertElement(elem,elementIndex+1);
            arr[elementIndex] = 0; // 更新列表A中的元素数量
            arr[elementIndex]-=1; // 删除列表A中的元素
            arr[elementIndex+1]+=1; // 保证元素的数量在列表A中
        }
    }
}

方法二：动态分配内存的链表

对于递归方法不适用于一次性处理大量数据的情况，可以考虑使用动态分配内存的方式来实现逆序链表。这种方式主要涉及到以下几个步骤：

1. 初始化数组：首先，初始化两个大小相等的整型数组arr1和arr2，分别存储集合A和集合B中元素的数量。
2. 计算两个集合元素数量之差：对arr1和arr2进行比较，计算出它们之间元素数量的差异，表示需要从哪个集合中删除某些元素。
3. 从列表B中删除特定数量的元素：选择列表B中较小的元素数量作为移动目标，遍历arr1数组。当找到要移除的元素时，从arr1数组中移除该元素，然后更新arr1数组和arr2数组对应位置的元素数量。
4. 添加新的元素到另一个集合中：从列表A中随机选取一个元素，将其插入到列表B中对应的后继位置，同时在原集合A中记录其下标，并增加对应位置的元素数量。由于这个操作是在动态内存中进行的，所以不需要显式地释放动态分配的内存。
5. 再次计算剩余元素数量：重新计算arr1和arr2数组中剩余元素的数量，确保所有元素都成功移到正确的位置。
6. 确定移除元素的集合：根据剩余元素数量的不同，可以选择从arr1数组或arr2数组中移除具有相同编号的元素，例如所有具有正负号编号的元素。
7. 合并集合：通过合并两个集合中具有相同编号的元素，实现从大集合到小集合的顺序交换，最终得到逆序的链表。

以下是动态数组初始化的C代码示例：

#include <stdio.h>
#include <stdlib.h>

typedef int Status;/**Status是函数类型，其值是函数结果状态代码，如OK等**/
typedef int ElemType; 

struct LNode               /* 结点定义 */     
{
    ElemType data;
    int Length;
    struct LNode *next;
};
typedef struct LNode *LinkList; /* 表的头指针类型 */

LinkList La,Lb;

Status InitList(LinkList *L)
{
    static int count[2] = {0}; // 堆栈，记录每个集合的元素数量

    if(!*L) exit(OVERFLOW);
    
    (*L)->next=NULL;
    // (*L)->data=-1;
    return OK;
}

Status pop(int index)
{
    if(index >= sizeof(count)/sizeof(count[0])) return ERROR;
    
    // 从堆栈弹出指定元素及其对应的集合
    LinkList temp;
    temp.next = *L;
    temp.data = count[index];

    // 清空堆栈
    count[index] = 0;
    
    // 返回临时集合的指针
    return temp.next;
}

Status deleteElement(ElemType elem, int index)
{
    if(index < 0 || index >= sizeof(count)/sizeof(count[0]))
    {
        return ERROR;
    }

    // 从堆栈弹出具有指定编号的元素，并更新相应集合的元素数量
    LinkList temp;
    temp.next = *L;
    temp.data = count[index];

    // 清空堆栈
    count[index] = 0;
    
    // 从列表A中移除具有相同编号的元素
    if(index % 2 == 0)
    {
        if(index/2 <= La_len)
        {
            Lb.DeleteElement(elem, index/2);
        }
    }
    else
    {
        if(index/2 < La_len)
        {
            La.DeleteElement(elem, index/2);
        }
    }

    // 将临时集合的指针置回链表头部
    *L = temp.next;
    
    return OK;
}

Status ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        p=p->next;
        i++;
    }
    return i;
}

Status GetElem(LinkList L,int i,ElemType *e)
{ 
    int j=1; /* j为计数器 */
    LinkList p=L->next; /* p指向第一个结点 */
    while(p&&j<i) 
    {
        p=p->next;
        j++;
    }     
    if(!p||j>i)   /* 第i个元素不存在 */
        return ERROR;
    *e=p->data;   /* 取第i个元素 */
    return OK;
}

Status Equal(ElemType a