删除带头结点的单链表最小值结点

向右看齐 2023-10-17 23:54 112阅读 0赞

## 删除带头结点的单链表最小值结点 ##

王道19数据结构 P44  
删除带头结点的单链表最小值结点（假设最小值结点唯一）

书上给的答案无法应对单链表为空的情况  
因为指针为空时，无法访问其结构体成员

#### 课本代码 ####

LinkList DelMin(LinkList &L){
        
    	LNode *pre = L, *p=pre->next; //L==NULL时此处报错
    	LNode *minpre = pre, *min = p;
    	while (p != NULL){
        
    		if (p->data < min->data){
        
    			min = p;
    			minpre = pre;
    		}
    		pre = p;
    		p = p->next;
    	}
    	minpre->next = min->next; //L->next==NULL时此处报错
    	free(min);
    	return L;
    }

#### 改进代码 ####

加入空链表判断

LinkList DelMin(LinkList &L){
        
    	if (L == NULL){
        
    		return NULL;
    	}
    	if (L ->next == NULL){
        
    		return NULL;
    	}
    	LNode *pre = L, *p=pre->next;
    	LNode *minpre = pre, *min = p;
    	while (p != NULL){
        
    		if (p->data < min->data){
        
    			min = p;
    			minpre = pre;
    		}
    		pre = p;
    		p = p->next;
    	}
    	minpre->next = min->next; 
    	free(min);
    	return L;
    }

#### 结构体定义 ####

typedef char ElemType;
    typedef struct LNode{
        
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;

#### 打印单链表 ####

void printList(LinkList &L){
        
    	LNode *p = L;
    	if (p == NULL){
        
    		printf("NULL1");
    	}
    	else if (p->next == NULL){
        
    		printf("NULL2");
    	}
    	else{
        
    		while (p != NULL){
        
    			printf("%c ", p->data);
    			p = p->next;
    		}
    	}
    	printf("\n");
    }

#### 头文件及主函数 ####

#include <iostream> 
    void main(){
        
    	LNode *Head = (LNode*)malloc(sizeof(LNode)); //头结点
    	LNode *A = (LNode*)malloc(sizeof(LNode));
    	LNode *B = (LNode*)malloc(sizeof(LNode));
    	LNode *C = (LNode*)malloc(sizeof(LNode));
    	LNode *D = (LNode*)malloc(sizeof(LNode));
    	LNode *E = (LNode*)malloc(sizeof(LNode));
    	LNode *F = (LNode*)malloc(sizeof(LNode));
    	LNode *G = (LNode*)malloc(sizeof(LNode));
    	LNode *H = (LNode*)malloc(sizeof(LNode));
    	LNode *I = (LNode*)malloc(sizeof(LNode));
    	Head->data = '>';	Head->next = A;
    	A->data = 'A';	A->next = B;
    	B->data = 'B';	B->next = C;
    	C->data = 'C';	C->next = D;
    	D->data = 'D';	D->next = E;
    	E->data = 'E';	E->next = F;
    	F->data = 'F';	F->next = G;
    	G->data = 'G';	G->next = H;
    	H->data = 'H';	H->next = I;
    	I->data = 'I';	I->next = NULL;
    	LinkList L = (LinkList)malloc(sizeof(LNode));
    	L = Head;
    	//L->next = NULL;
    	//L = NULL;
    	DelMin(L);
    	printList(L);
    }