删除线性表节点(线性表)
时间: 1ms 内存:128M
描述:
本题只需要提交填写部分的代码已知长度为n的线性表A采用链式存储结构,请写一时间复杂度为0(n)、空间复杂度为0(1)的算法,该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)。代码:#include <iostream>
using namespace std;
struct node
{
int data;
node *next;
};
node *createlist(node *head,int n)
{
node *previous; //前驱结点
node *current; //当前结点
if(n<1)
{
return NULL; //建立空链表
}
previous=head=new node; //建立首结点
cin>>head->data; //输入数据
while(--n)
{
current=new node; //建立新结点
cin>>current->data; //输入数据
previous->next=current; //新节点挂在表尾
previous=current;
}
previous->next=NULL; //置表尾结束标志
return head; //返回首结点指针
}
node *listdel(node *head,int item)
{
node *temp;
/* 从头找到第一个不等于item的结点 */
while(head!=NULL&&head->data==item)
{
temp = head;
head=head->next;
delete temp; //删除该节点
}
if(head==NULL)
return NULL;
node *previous=head; //前驱结点
node *current = head->next; //当前结点
while(current!=NULL)
{
/* 删除连续相同的结点*/
while(current!=NULL&¤t->data==item)
{
/*
请在该部分填写缺少的代码
*/
}
previous->next=current; //重新连接结点
if(current==NULL)
break;
previous=current;
current=current->next; //当前结点后移
}
return head;
}
void output(node *head)
{
node *current=head;
while(current!=NULL)
{
cout<<current->data<<" "; //输出结点数据
current=current->next; //结点指针后移
}
}
int main()
{
node *head=NULL;
int n,item;
cin>>n;
head=createlist(head,n);
cin>>item;
head=listdel(head,item);
output(head);
return 0;
}
输入:
输入 n:6
输入数据:1 2 3 4 5 6
输入 item:5
输出:
输出:1 2 3 4 6
示例输入:
10
1 2 3 4 5 6 7 8 9 10
8
示例输出:
1 2 3 4 5 6 7 9 10
提示:
参考答案:
解锁文章
文章评论