一屹篓、題目描述
????????已知單鏈表L疙渣，寫一算法，刪除其中的重復(fù)節(jié)點(diǎn)堆巧。
二妄荔、分析解答
2.1 知識點(diǎn)分析
????????本題主要考察鏈表的相關(guān)知識點(diǎn)泼菌，其中包括：單鏈表的結(jié)構(gòu)、創(chuàng)建啦租、遍歷哗伯、刪除等操作。要想熟練的使用鏈表篷角，必須對這些有著清楚的認(rèn)識焊刹。
鏈表是線性結(jié)構(gòu)的一種物理實(shí)現(xiàn)，除此之外内地，線性結(jié)構(gòu)還可以使用順序存儲結(jié)構(gòu)來實(shí)現(xiàn)。順序存儲是使用內(nèi)存中的一塊地址連續(xù)空間順序存放線性表中的每一個元素赋除，每個元素在物理上相鄰阱缓，而鏈?zhǔn)酱鎯Y(jié)構(gòu)則不會要求物理上的元素相鄰，它通過節(jié)點(diǎn)的指針域指向下一個元素举农。
線性結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的幾種常見邏輯結(jié)構(gòu)之一荆针，在數(shù)據(jù)結(jié)構(gòu)中，常見的邏輯結(jié)構(gòu)有：集合結(jié)構(gòu)颁糟、線性結(jié)構(gòu)航背、樹結(jié)構(gòu)、圖結(jié)構(gòu)棱貌。這幾種邏輯結(jié)構(gòu)玖媚，如果要在計(jì)算機(jī)上實(shí)現(xiàn)出來，可以采用順序存儲結(jié)構(gòu)婚脱、鏈?zhǔn)酱鎯Y(jié)構(gòu)今魔、索引結(jié)構(gòu)、散列結(jié)構(gòu)四種障贸。從理論上講错森，任何一種邏輯結(jié)構(gòu)都可以采用任何一種物理結(jié)構(gòu)來實(shí)現(xiàn)。
在單鏈表的創(chuàng)建過程中篮洁，根據(jù)新元素插入位置的不同涩维，可以有頭插法和尾插法兩種。這兩種創(chuàng)建方式創(chuàng)建出來的單鏈表在性質(zhì)上沒有什么不同袁波。
為了方便單鏈表元素的統(tǒng)一操作瓦阐，也可以在單鏈表的頭部附加一個結(jié)點(diǎn)，我們稱之為 頭結(jié)點(diǎn)篷牌。頭結(jié)點(diǎn)中的數(shù)據(jù)域可以存放和鏈表有關(guān)的信息垄分，例如節(jié)點(diǎn)的個數(shù)。要注意頭結(jié)點(diǎn)和頭指針在邏輯上的區(qū)別娃磺，鏈表中第一個正式數(shù)據(jù)元素的節(jié)點(diǎn)叫做首元結(jié)點(diǎn)薄湿，在此節(jié)點(diǎn)之前附加的一個節(jié)點(diǎn)叫做頭結(jié)點(diǎn)，頭結(jié)點(diǎn)中數(shù)據(jù)域存儲的信息在性質(zhì)上和鏈表中數(shù)據(jù)元素節(jié)點(diǎn)中數(shù)據(jù)域存儲的內(nèi)容不同，頭指針是指向整個鏈表中的第一個節(jié)點(diǎn)的地址豺瘤，可能是頭結(jié)點(diǎn)的地址吆倦，也可能會是首元結(jié)點(diǎn)的地址。
2.2 代碼分析
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*PNode;
//頭插法建立帶有頭結(jié)點(diǎn)的單鏈表
PNode creat_list(){
//申請頭結(jié)點(diǎn)
PNode head = (PNode)malloc(sizeof(Node));
head->next = NULL;
scanf("%d",&(head->data)); // 頭結(jié)點(diǎn)的數(shù)據(jù)域可以存放總結(jié)點(diǎn)數(shù)
//新增元素
PNode p = NULL;
int i;
for(i=0;i<(head->data);i++){
p = (PNode)malloc(sizeof(Node));
scanf("%d",&(p->data));
//這是頭插法的關(guān)鍵所在
p->next = head->next;
head->next = p;
}
return head;
}
//刪除重復(fù)節(jié)點(diǎn)
void del_repeated_node(PNode head){
PNode k = head->next, pre_p = k, p = pre_p->next;
//遍歷單鏈表的每一個節(jié)點(diǎn)
while(k && k->next != NULL){
//判斷k后面的節(jié)點(diǎn)是否與k的值域重復(fù)坐求，如果重復(fù)蚕泽，則刪去。
while(p){
if(k->data == p->data){
//刪除重復(fù)的p節(jié)點(diǎn)
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 結(jié)果截圖
