数据结构用C实现非递减有序单链表删除重复元素值

发表于 更新于 分类于 Waline：

参考文章C实现非递减有序数组删除重复元素值

具体实现代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <stdlib.h>
typedef struct Node //声明单链表
{
    int data;
    struct Node* next;
} Node, *LList;
void InitList(LList *L) //初始化单链表
{
    *L=(LList)malloc(sizeof(Node));
    (*L)->next=NULL;
}
void CFTail(LList L) //用尾插法建立单链表
{
    Node *r,*s;
    int flag=1;
    r=L;
    while(flag)
    {
        int c;
        scanf("%d",&c);
        if(c!=0)
        {
            s=(Node*)malloc(sizeof(Node));
            s->data=c;
            r->next=s;
            r=s;
        }
        else
        {
            flag=0;
            r->next=NULL;
        }
    }
}
void DelSameX(LList L) //删除重复的元素值
{
    Node *pre,*p;
    pre=L->next;
    //
    if(pre==NULL)
    {
        pre=L->next;
    }
    else
    {
        for(p=pre->next;p!=NULL;p=p->next)
        {
            if(p->data != pre->data)
            {
                pre->next=p;
                pre=pre->next;
            }
        }
    }
}
void print(LList L)
{
    while(L->next != NULL)
    {
        L=L->next;
        printf("%d ",L->data);
    }
}
int main()
{
    LList L;
    printf("jian li dan lian biao: \n");
    InitList(&L);
    CFTail(L);
    DelSameX(L);
    print(L);
    putchar('\n');
    system("pause");
    return 0;
}

实现效果如图：

这说明这个程序还是有些许bug，检查原因，发现还是在最后的结点处没有给它指向空，因此它又指向了原先的那个最后的结点，简单点说，就是没有断开原先的尾结点，改变后的程序如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <stdlib.h>
typedef struct Node //声明单链表
{
    int data;
    struct Node* next;
} Node, *LList;
void InitList(LList *L) //初始化单链表
{
    *L=(LList)malloc(sizeof(Node));
    (*L)->next=NULL;
}
void CFTail(LList L) //用尾插法建立单链表
{
    Node *r,*s;
    int flag=1;
    r=L;
    while(flag)
    {
        int c;
        scanf("%d",&c);
        if(c!=0)
        {
            s=(Node*)malloc(sizeof(Node));
            s->data=c;
            r->next=s;
            r=s;
        }
        else
        {
            flag=0;
            r->next=NULL;
        }
    }
}
void DelSameX(LList L) //删除重复的元素值
{
    Node *pre,*p;
    pre=L->next;
    //
    if(pre==NULL)
    {
        pre=L->next;
    }
    else
    {
        for(p=pre->next;p!=NULL;p=p->next)
        {
            if(p->data != pre->data)
            {
                pre->next=p;
                pre=p;
            }
        }
        pre->next=NULL;
    }
}
void print(LList L)
{
    while(L->next != NULL)
    {
        L=L->next;
        printf("%d ",L->data);
    }
}
int main()
{
    LList L;
    printf("jian li dan lian biao: \n");
    InitList(&L);
    CFTail(L);
    DelSameX(L);
    print(L);
    putchar('\n');
    system("pause");
    return 0;
}

运行结果如图：

还有一种写法，一并放在这里。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*删除递增有序单链表中的重复元素*/
/*包含头文件*/
#include <stdio.h>
#include <stdlib.h>
#include "ds.h"

/*定义ElemType类型和使用到的物理数据类型*/
typedef int ElemType;

typedef struct Node    /* 结点类型定义 */
{ ElemType data;
  struct Node  * next;
}Node, *LinkList;

//初始化单链表
LinkList InitList(LinkList *L)
{
	*L=(LinkList)malloc(sizeof(Node));
	(*L)->next=NULL;
}
/*声明物理数据类型的操作（函数）和使用到的其他功能函数*/
/*根据输入的任意次序的字符元素创建升序单链表*/
LinkList  CreateASCList(LinkList L);
/*打印链表*/
void LListPrint(LinkList L);
/*删除递增有序单链表中的重复元素*/
void  LListDelElem(LinkList L);
/*销毁单链表*/
void ListDestroy(LinkList L);


/*定义物理数据类型的操作（函数）和使用到的其他功能函数*/
/*根据输入的任意次序的字符元素创建升序单链表*/
LinkList  CreateASCList(LinkList L)
{
	printf("Please input int xing numbers and input -1 means end input: \n");
	int count=0;
	ElemType ch[MAXSIZE];
	do {
		scanf("%d",&ch[count]);
		count++;
	} while(ch[count-1]!=-1);
	int i,j;
	for(i=0;i<count-1;i++)
	{
		for(j=count-2;j>i;j--)
		{
			if(ch[j-1]>ch[j])
			{
				ElemType t=ch[j-1];
				ch[j-1]=ch[j];
				ch[j]=t;
			}
		}
	}
	Node *r,*s;
	r=L;
	i=0;
	do {
		s=(Node *)malloc(sizeof(Node));
		s->data=ch[i];
		r->next=s;
		r=s;
		i++;
	} while(i<(count-1));
	r->next=NULL;
	return L;
}

/*打印链表*/
void LListPrint(LinkList L)
{
	while((L->next)!= NULL)
    {
        L=L->next;
        printf("%d ",L->data);
    }
	putchar('\n');
}


/*删除递增有序单链表中的重复元素*/
void  LListDelElem(LinkList L)
{
	Node *pre,*p;
    pre=L->next;
    if(pre==NULL)
    {
        pre=L->next;
    }
    else
    {
        for(p=pre->next;p!=NULL;p=p->next)
        {
            if(p->data != pre->data)
            {
                pre->next=p;
                pre=pre->next;
            }
        }
		pre->next=NULL;
    }
}

/*销毁单链表*/
void ListDestroy(LinkList L)
{
	free(L);
}

/*定义主函数，通过主函数调用各物理数据类型的操作和功能函数*/
int main(){
	LinkList a;
	InitList(&a);
	a=CreateASCList(a);
	LListPrint(a);
	printf("shan chu chong fu yuan su hou\n");	
	LListDelElem(a);
	LListPrint(a);
	ListDestroy(a);
	system("pause");
	return 0; 
}

其中ds.h文件定义如下： 

1
2
3
4
5
#define		TRUE	1
#define		FALSE	0
#define		OK		1
#define		ERROR	0
#define		MAXSIZE	100

完！