数据结构——链表——不带头节点的单链表
程序员文章站
2022-03-15 18:13:44
...
不带头节点的单链表
/*
功能:创建一个链表
参数:无
返回值:
返回链表的第一个节点的地址
*/
Node * createLkList()
{
ElemType data;
Node * p = NULL;//用来保存新节点的地址
Node * first = NULL;//用来保存 链表的第一个元素的 地址
Node * last = NULL;//用来保存 链表的最后一个元素的 地址
Node n;
while(1)
{
//0,获取用户输入
scanf("%d",&data);
if(data == 0)//约定,用户输入0代表结束
{
break;
}
//不是0就把data加入 链式线性表 (链表)
//1,分配空间
p = (Node *)malloc(sizeof(Node));
//为什么不像下面这样分配命名空间,而要用malloc动态分配
/*
p = &n;
p->data = data;
p->next = NULL;
*/
//2,保存数据
p->data = data;
p->next = NULL;
//3,把该节点加入到 链表 中
if(first == NULL)//当前是第一个节点
{
first = p;
//p是右值,那就是 新分配的节点地址
//first 在这是左值 ,整个的意思就是把新分配的节点的地址保存到指针变量first中去
//那么我们就是 first指向了这个节点
last = p;
}
else
{
#if 1
//尾插法:每次把用户新输入的数据节点插入到链表的末尾
//尾插法完成之后,链表的顺序就是用户输入的顺序
//1 2 3
//1----> 2 ----> 3
last->next = p;//原来的last的指针域保存新节点的地址
last = p;//新的节点就是last了
#else
//头插入:每次把用户新输入的数据节点插入到链表的头
//头插法完成之后,链表的顺序就是用户输入顺序的逆序
//1 2 3
//3----> 2 ----> 1
p->next = first;
first = p;
#endif
}
}
return first;//返回此链表的第一个节点的地址,不然的话,找不到这个链表
}
/*
功能:输出一个链表的所有节点数据
参数:
@first 这个链表的首地址
返回值:
无
*/
void printfLkList(Node * first)
{
Node * p = first;
while(p != NULL)
//while(p->next != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
void freeLkList(Node * first)
{
Node * p = first;
while(p!=NULL)
{
first = p->next;//保存p下一个地址
p->next = NULL;//free只是表示这段空间不是我的了,别人可以用了,但是里面的内容并没有
//清空,也就是说还可以通过它的next找到下一个节点,比较危险
//为了避免这种清空,free之前需要把它的指针域清空
free(p);//释放当前这个节点p
p = first;//指向新的first,准备下一次循环
}
}
/*
功能:在一个链表中查找是否存在值为 x的元素
参数:
@first 链表的首地址
@x需要查找的元素
返回值
查到返回1
没查到返回0
*/
int find(Node * first,ElemType x)
{
while(first)
{
if(first->data == x)
{
return 1;
}
first = first->next;
}
return 0;
}
/*
功能:往有序链表中插入一个元素,使之仍然有序
参数:
@first 链表的首地址
@x 需要插入的元素
返回值:
*/
Node* insert(Node * first,ElemType x)
{
Node * q = first;//用来循环
Node * r = NULL;//用来保存q前面的那个节点
//1,构造新节点
Node * p = (Node *)malloc(sizeof(Node));
p->data = x;
p->next = NULL;
//2,先找位置
while(q)
{
if(q->data > x)
{
break;//找到了break,如果一直找不到,靠 q == NULL 结束while循环
}
r = q;
q = q->next;
}
//3,判断是否找到
if(q == NULL)//没找到,插入到末尾
{
r->next = p;
//p->next = NULL;
}
else if(r == NULL)//找到了,并且第一个就比我大,插入到第一个前
{
p->next = first;
first = p;
}
else
{
r->next = p;
p->next = q;
}
//因为有插入在第一个节点前的情况,所有first是改变了的,需要返回新的first
return first;
}
/*
功能:删除链表中第一个值为x的元素
参数:
@first 链表首地址
@x 要删除的节点的值
返回值
返回新链表的first
*/
Node * delete(Node * first,ElemType x)
{
Node * p = first;//p保存要删除的那个节点
Node * r = NULL;//用来保存p前面的那个节点
//1,查找
while(p)
{
if(p->data == x)
{
break;
}
r = p;
p = p->next;
}
//2,判断找没找到
if(p == NULL)//没找到
{
return first;
}
else//找到了
{
//分情况讨论
if(p == first)//p是第一个节点
{
//删除第一个节点
first = first->next;//保存新的first
p->next = NULL;//释放一个节点之前,把它的指针域清空
free(p);
}
else if(p->next == NULL)//p是最后一个节点
{
//最后一个节点已经删除,r就是最后一个节点
r->next = NULL;
p->next = NULL;
free(p);
}
else
{
r->next = p->next;
p->next = NULL;
free(p);
}
}
return first;
}
/*
功能:删除链表中所有值为x的元素
参数:
@first 链表首地址
@x 要删除的节点的值
返回值
返回新链表的first
*/
Node * deleteAll(Node * first,ElemType x)
{
Node * p = first;//p保存要删除的那个节点
while(1)
{
Node * r = NULL;//用来保存p前面的那个节点
//1,查找
while(p)
{
if(p->data == x)
{
break;
}
r = p;
p = p->next;
}
//2,判断找没找到
if(p == NULL)//没找到
{
return first;
}
else//找到了
{
//分情况讨论
if(p == first)//p是第一个节点
{
//删除第一个节点
first = first->next;//保存新的first
p->next = NULL;//释放一个节点之前,把它的指针域清空
free(p);
}
else if(p->next == NULL)//p是最后一个节点
{
//最后一个节点已经删除,r就是最后一个节点
r->next = NULL;
p->next = NULL;
free(p);
}
else
{
r->next = p->next;
p->next = NULL;
free(p);
}
}
if(r!=NULL)
{
p = r->next;
}
else
{
p = first;
}
}
//return first;
}
上一篇: Prometheus安装