一、题目描述
已知单链表L，写一算法，删除其中的重复节点。
二、分析解答
2.1 知识点分析
本题主要考察链表的相关知识点，其中包括：单链表的结构、创建、遍历、删除等操作。要想熟练的使用链表，必须对这些有着清楚的认识。
链表是线性结构的一种物理实现，除此之外，线性结构还可以使用顺序存储结构来实现。顺序存储是使用内存中的一块地址连续空间顺序存放线性表中的每一个元素，每个元素在物理上相邻，而链式存储结构则不会要求物理上的元素相邻，它通过节点的指针域指向下一个元素。
线性结构是数据结构的几种常见逻辑结构之一，在数据结构中，常见的逻辑结构有：集合结构、线性结构、树结构、图结构。这几种逻辑结构，如果要在计算机上实现出来，可以采用顺序存储结构、链式存储结构、索引结构、散列结构四种。从理论上讲，任何一种逻辑结构都可以采用任何一种物理结构来实现。
在单链表的创建过程中，根据新元素插入位置的不同，可以有头插法和尾插法两种。这两种创建方式创建出来的单链表在性质上没有什么不同。
为了方便单链表元素的统一操作，也可以在单链表的头部附加一个结点，我们称之为 头结点。头结点中的数据域可以存放和链表有关的信息，例如节点的个数。要注意头结点和头指针在逻辑上的区别，链表中第一个正式数据元素的节点叫做首元结点，在此节点之前附加的一个节点叫做头结点，头结点中数据域存储的信息在性质上和链表中数据元素节点中数据域存储的内容不同，头指针是指向整个链表中的第一个节点的地址，可能是头结点的地址，也可能会是首元结点的地址。
2.2 代码分析
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
| #include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*PNode;
PNode creat_list(){
PNode head = (PNode)malloc(sizeof(Node));
head->next = NULL;
scanf("%d",&(head->data));
PNode p = NULL;
int i;
for(i=0;i<(head->data);i++){
p = (PNode)malloc(sizeof(Node));
scanf("%d",&(p->data));
p->next = head->next;
head->next = p;
}
return head;
}
void del_repeated_node(PNode head){
PNode k = head->next, pre_p = k, p = pre_p->next;
while(k && k->next != NULL){
while(p){
if(k->data == p->data){
PNode temp = p;
pre_p ->next= p->next;
p = pre_p->next;
free(temp);
}else{
pre_p = pre_p->next;
p = pre_p->next;
}
}
k = pre_p = k->next;
p = pre_p->next;
}
}
void print_list(PNode head){
PNode p = head->next;
while(p){
printf("p->data: %d \t",p->data);
p = p->next;
}
printf("\n");
}
int main(){
PNode head = creat_list();
print_list(head);
del_repeated_node(head);
print_list(head);
return 0;
}
|
2.3 结果截图
