/*
用单链表保存m个整数,节点的结构为[data][next],且|data|<=n。现要求设计一个时间复杂度尽可能高效算法,
对于链表中绝对值相等的节点,仅保留第一次出现的节点而删除其余绝对值相等的节点。
分析:
中提到时间复杂度尽可能高效,其本上就是暗示我们采用空间换时间的方式。因为数据是小于等于n的,我们可以开辟一块
大小为n的数组,初始值为0,之后我们遍历链表,节点值既是我们寻找的下标,如果下标所在的数组值为0,则将值变为1,如果
数组值已经为1,则说明在此之前我们遇见过绝对值相同的元素,故将此节点删除。
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int value;
struct LNode *next;
}LNode,*Linklist;
Linklist list_TailInsert(Linklist &L)
{
LNode *head = L,*rear = L;
L = (Linklist)malloc(sizeof(LNode));
L->next = NULL;
L->value = NULL;
int x;
printf("请输入单链表结点的个数:");
scanf("%d",&x);
for(int i = 0; i < x; i++)
{
int value;
printf("请输入单链表第%d个结点的值:",i+1);
scanf("%d",&value);
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next = NULL;
rear->next = s;
rear = s;
}
rear->next = NULL;
return L;
}
void Display(Linklist &L)
{
LNode *p = L->next;
while(p != NULL)
{
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
int main()
{
Linklist L1;
list_TailInsert(L1);
Display(L1);
return 0;
}
生成链表的时候,返回的是头结点的值,所以应该写
Linklist L1 = list_TailInsert();
另外,引用是C++里的,Display函数要改成
void Display(Linklist L)
完整代码如下:
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
int value;
struct LNode *next;
}LNode,*Linklist;
Linklist list_TailInsert()
{
LNode *L = (Linklist)malloc(sizeof(LNode));
LNode *head = L,*rear = L;
L->next = NULL;
L->value = 0;
int x;
printf("请输入单链表结点的个数:");
scanf("%d",&x);
for(int i = 0; i < x; i++)
{
int value;
printf("请输入单链表第%d个结点的值:",i+1);
scanf("%d",&value);
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next = NULL;
rear->next = s;
rear = s;
}
rear->next = NULL;
return L;
}
void Display(Linklist L)
{
LNode *p = L->next;
while(p != NULL)
{
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
int main()
{
Linklist L1 = list_TailInsert();
Display(L1);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int value;
struct LNode *next;
}LNode,*Linklist;
Linklist list_TailInsert(Linklist &L)
{
L = (Linklist)malloc(sizeof(LNode));
LNode *head = L,*rear = L;
L->next = NULL;
L->value = NULL;
int x;
printf("请输入单链表结点的个数:");
scanf("%d",&x);
printf("x = %d",x);
for(int i = 0; i < x; i++)
{
int value;
printf("请输入单链表第%d个结点的值:",i+1);
scanf("%d",&value);
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next = NULL;
rear->next = s;
rear = s;
}
rear->next = NULL;
return L;
}
void Display(Linklist &L)
{
LNode *p = L->next;
while(p != NULL)
{
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
int main()
{
Linklist L1;
list_TailInsert(L1);
Display(L1);
return 0;
}