欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

不带头结点链表存在的问题

程序员文章站 2024-03-21 13:58:22
...

链表的每个结点由链域和值域组成,假设下面的链表的值域代表点的位置,于是链表的数据结构为

typedef struct POINT{
    int col;
    int row;
    struct POINT *next;
}POINT;

初始化链表的函数为

boolean initNoHead(POINT **head);

boolean initNoHead(POINT **head) {
	POINT *node;
	POINT *lastNode;
	boolean finished = FALSE;
	boolean ok = TRUE;
	int col;
	int row;
	
	if(*head != NULL){
		return FALSE;
	}else{
	printf("请输入行列坐标");
	scanf("%d%d", &row, &col);
	while(isData(row, col)) {
		node = newPointInstance();
		setPoint(node, row, col);
		if((*head) == NULL){
		(*head) = node; 
		lastNode = node;
		}
		else{
			lastNode->next = node;
			lastNode = lastNode->next;
		}
		printf("请输入行列坐标\n");
		scanf("%d%d", &row, &col);
	}
	return TRUE;
	}
}

主函数的调用为

int main(){
    POINT *NoNodeLink1 = NULL;
    POINT *NoNodeLink2 = NULL;
    
    if(TRUE ==  initNoHead(&NoNodeLink1)){
    showPoints(NoNodeLink1);
     }
    return 0;
}


为啥初始链表的参数为point **head,

我看到有人写链表的初始化链表的函数声明是是POINT *creatNode(........);

这样写有一些问题,比如主函数不小心万一下面这样

POINT *NoNodeLink1 = initNoHead(....);
POINT *NoNodeLink1 = initNoHead(....);

那么会出现很严重的内存泄漏,第一次申请的内存的地址被第二次覆盖,第一次的内存地址丢失了,无法从内存中释放,如果内存满了,程序会强制停止。

而参数为POINT **head的情况下,在主函数中

POINT *NoNodeLink1 = null;
initNoHead(&NoNodeLink1);

就算两次调用,由于NoNodeLink1的初始值为Null,可以在initNoHead函数中进行判断,如果NoNodeLink1的值不为null说明他已经是一个链表的头部了,如果为null,说明他还没初始化链表,这样就避免了上面出现的内存泄漏的问题。

销毁链表也要最后让其恢复为null

void destroy(POINT **head);

void destroy(POINT **head) {
	POINT *q;
	
	while(*head){
		q = *head;
		*head = q->next;
		free(q);
	}
	*head = NULL;
}
这样就增加了代码的鲁棒性了,其他的操作如下面展示。
#include<stdio.h>
#include<malloc.h>

#include"MecTool.h"

typedef struct POINT{
	int col;
	int row;
	struct POINT *next;
}POINT;

boolean initNoHead(POINT **head);
boolean isData(int row, int col);
POINT *newPointInstance();
void setPoint(POINT *node, int row, int col);
void showOnePoint(POINT *node);
void showPoints(POINT *head);
void destroy(POINT **head);
POINT *findPreNode(POINT *head, POINT targetnode, boolean (equals)(POINT,POINT));
boolean eq(POINT node1, POINT node2);
void insertNode(POINT **head);
void reMoveNode(POINT **head);
void AseOrderLink(POINT *head);

void AseOrderLink(POINT *head){
	POINT *i;
	POINT *j;
	int tmp;
	
	for(i = head; i; i = i->next)
		for(j = i->next; j; j = j->next){
			if((i->row) > (j->row)) {
				tmp = i->row;
				i->row = j->row;
				j->row = tmp;

				tmp = i->col;
				i->col = j->col;
				j->col = tmp;
			}
		}
}

void reMoveNode(POINT **head){
	POINT *oldNode;
	POINT *pre;
	int col;
	int row;
	POINT *q;

	printf("请输入要删除的点");
	scanf("%d%d",&row,&col);
	oldNode = newPointInstance();
	setPoint(oldNode,row, col);
	
	pre = findPreNode(*head, *oldNode,eq);
	if(pre == NULL) {
		q = *head;
		*head = q->next;
		free(q);
	}else if(pre->next == NULL) {
		printf("没找到该点");
		return;
	}else if(pre->next != NULL) {
		q = pre->next;
		pre->next = q->next;
		free(q);
	}

}

void insertNode(POINT **head) {
	POINT *oldNode;
	POINT *newNode;
	POINT *pre;
	int col;
	int row;

	printf("请输入要插位置的点");
	scanf("%d%d",&row,&col);
	oldNode = newPointInstance();
	setPoint(oldNode,row, col);
	printf("请输入要插入的点");
	scanf("%d%d",&row,&col);
	newNode = newPointInstance();
	setPoint(newNode,row, col);
	
	pre = findPreNode(*head, *oldNode,eq);
	if(pre == NULL){
		newNode->next = *head;
		*head = newNode;
	}else {
		newNode->next = pre->next;
		pre->next = newNode;
	}
}
//pre == NULL要找的在第一个节点
//pre! = NULL没找到
//pre->next! = NULL

boolean eq(POINT node1, POINT node2) {
	return node1.col == node2.col&&node1.row == node2.row;
}

POINT *findPreNode(POINT *head, POINT targetnode, boolean (equals)(POINT,POINT)) {
	POINT *q;
	POINT *pre = NULL;;

	for(q = head; q; q = q->next){
		if(TRUE == eq(*q, targetnode)) {
			break;
		}
		pre = q;
	}
	return pre;
}

void destroy(POINT **head) {
	POINT *q;
	
	while(*head){
		q = *head;
		*head = q->next;
		free(q);
	}
	*head = NULL;
}

void showPoints(POINT *head){
	POINT *q;
	for(q = head; q; q = q->next)
		showOnePoint(q);
}

void showOnePoint(POINT *node){
	printf("<%d,%d>\n",node->row, node->col);
}

void setPoint(POINT *node, int row, int col) {
	node->row = row;
	node->col = col;
}

POINT *newPointInstance() {
	POINT *head;

	head = (POINT *)calloc(sizeof(POINT), 1);

	return head;
}

boolean isData(int row, int col){
	return row >= 0&&row <=25&&col >= 0&&col <= 80;
}

boolean initNoHead(POINT **head) {
	POINT *node;
	POINT *lastNode;
	boolean finished = FALSE;
	boolean ok = TRUE;
	int col;
	int row;
	
	if(*head != NULL){
		return FALSE;
	}else{
	printf("请输入行列坐标");
	scanf("%d%d", &row, &col);
	while(isData(row, col)) {
		node = newPointInstance();
		setPoint(node, row, col);
		if((*head) == NULL){
		(*head) = node; 
		lastNode = node;
		}
		else{
			lastNode->next = node;
			lastNode = lastNode->next;
		}
		printf("请输入行列坐标\n");
		scanf("%d%d", &row, &col);
	}
	return TRUE;
	}
}

int main(){
	POINT *NoNodeLink1 = NULL;
	POINT *NoNodeLink2 = NULL;
	
	if(TRUE ==  initNoHead(&NoNodeLink1))
	showPoints(NoNodeLink1);
	insertNode(&NoNodeLink1);
	showPoints(NoNodeLink1);
	reMoveNode(&NoNodeLink1);
	showPoints(NoNodeLink1);
	AseOrderLink(NoNodeLink1);
	showPoints(NoNodeLink1);

	destroy(&NoNodeLink1);

	return 0;
}