高校问答美剧亡者归来:关于数据库结构的一个问题！
来源：百度文库 编辑：高校问答 时间：2024/04/27 22:04:54
2. 给定链表头指针h，删除尾结点
分析上述功能要求；写出相应的函数实现（需在程序中加入与分析相对应的注释）；分析算法复杂度
注意，一定要先分析再实现，在程序中要有和分析相应的注释。
大家帮忙看下 这个题目该怎么做 谢谢
第1题
//分析
//题目所给的参数是，链表头指针h，和插入新节点的值
//item，所以函数的参数确定了
//之后，进行链表的插入
//参数说明
//&h 表示传入链表的一个引用，即在函数内更改的链
//表，就是原来的链表
//item 是Value类型的，表示链表的值
ListInsert(LinkList &h, Value item){
//复制表头指针，这里p是链表类型的指针
p = h;
//创建新的节点，其中LinkNode是节点类型
s = (*LinkNode)malloc(sizeof(LinkNode));
//为新节点赋值
s->value = item;
//新节点的下一项指向原头指针的下一项
s->next = p->next;
//源头指针的下一项指向新的节点，插入完毕
p->next = s;
}
第2题
//分析
//由题目确定传入参数为链表头指针h，之后进行链表
//尾部节点的删除
//参数说明
//&h 表示传入链表的一个引用，即在函数内更改的链
//表，就是原来的链表
ListDelete(LinkList &h)
{
//复制表头指针，这里p是链表类型的指针
p = h;
//保存p的前驱指针q，q是p所指向节点的前一个节点
//因为刚开始p前没有节点，所以q = p
q = p;
//遍历链表，当p所指向的节点的下一个节点为空
//则找到了链表的尾部。p为链表的尾节点
while(p->next != NULL )
{
//保存p的前驱指针
q = p;
//p指向下一个节点
p = p->next;
}
//让p的前一个节点的下一个节点为空
q->next = NULL;
//释放p所指向节点的空间，为节点删除完毕
free(p);
}