Question

设计一个在带头结点的单链表中删除第i个结点的算法

Answer 1

//删除节点 删除第i个节点
int Delete_Positon_LL(LinkList *phead,int i)
{
LinkList p,q;//p为值是x的节点,q是p的前一个节点
int j;

if((*phead)->next == NULL)//如果链表为空，做下溢处理
{
printf("单链表为空!\n");

return 0;
}
if(i == 1) //如果是表头,表头后移
{

p=(*phead)->next;
(*phead)->next=(*phead)->next->next;
free(p);//释放表头

扩展资料：

链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

参考资料来源：百度百科-单链表

Answer 2

//删除节点 删除第i个节点
int Delete_Positon_LL(LinkList *phead,int i)
{
LinkList p,q;//p为值是x的节点,q是p的前一个节点
int j;

if((*phead)->next == NULL)//如果链表为空，做下溢处理
{
printf("单链表为空!\n");
return 0;
}
if(i == 1) //如果是表头,表头后移
{
p=(*phead)->next;
(*phead)->next=(*phead)->next->next;
free(p);//释放表头
}
else //从第二个节点查找值是x的
{
q=(*phead)->next;
p=(*phead)->next->next;
j=2;
//注意先p !=NULL，否则将出现非法访问操作
while(p !=NULL && j<i )
{
q=p;
p=p->next;
j++;
}

if(p!=NULL)//找到了
{
q->next=p->next;//让前一个节点指向p的后继节点
free(p);//删除节点p
}
else
{
printf("删除第%d个节点超出范围.\n",i);
return 0;
}
}

return 1;

}

Answer 3

//删除节点 删除第i个节点
int Delete_Positon_LL(LinkList *phead,int i)
{
LinkList p,q;//p为值是x的节点,q是p的前一个节点
int j;

if((*phead)->next == NULL)//如果链表为空，做下溢处理
{
printf("单链表为空!\n");
return 0;
}
if(i == 1) //如果是表头,表头后移
{
p=(*phead)->next;
(*phead)->next=(*phead)->next->next;
free(p);//释放表头
}
else //从第二个节点查找值是x的
{
q=(*phead)->next;
p=(*phead)->next->next;
j=2;
//注意先p !=NULL，否则将出现非法访问操作
while(p !=NULL && j<i )
{
q=p;
p=p->next;
j++;
}

if(p!=NULL)//找到了
{
q->next=p->next;//让前一个节点指向p的后继节点
free(p);//删除节点p
}
else
{
printf("删除第%d个节点超出范围.\n",i);
return 0;
}
}

return 1;

}

Answer 4

第一总算法
设两个指针p,q
p<-head
repeat
{
q<-p.next
repeat
{
if (p.data=q.data)
else q<-q.next
}until q=nul
p<-p.next
}until (p=null) or (p.next=null)
时间为O(n*n) 空间O(1)
还有一种算法
设一个指针p
数组 hash[1..maxnumber] as type byte
p<-head
repeat
{
if (hash[p.data]=1 ) else
}until p=null
时间为O(n) 空间O(m)
另外,站长团上有产品团购,便宜有保证