不带头结点链表存在的问题
程序员文章站
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;
}