用c++编写一个函数创建单链表,编写一个函数,实现删除单链表中指定位置的元素x。编写主函数调用这些函数,并分析算法的时间复杂度。
删除单链表中指定位置的元素x
==这句有问题啊。一般要么删除指定元素x,要么删除指定位置的节点;你这个需求,如果指定位置的元素不是x,该怎么处理?
复杂度为 O(n)
#include <iostream>
using namespace std;
typedef int ElemType; //元素值域类型为int型
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
void Create(LinkList &L); //正序构建单链表,返回其头指针
void del_x_list(LinkList &L, ElemType x); //删除所有值下标为x的结点
void print(LinkList L); //输出链表元素
int main()
{
LinkList L;
int x;
Create(L);
cout << "输入要删除的元素的位置:";
cin >> x;
del_x_list(L, x);
print(L);
return 0;
}
void Create(LinkList &L)
{
L = (LinkList)malloc(sizeof(LNode));
//r始终指向尾结点,初始指向L,即头结点
LNode *r = L;
LNode *s;
int size;
cout << "输入链表大小:";
cin >> size;
for (int i = 1; i <= size; i++)
{
s = (LinkList)malloc(sizeof(LNode));
int x;
cout << "输入第" << i << "个元素:";
cin >> x;
s->data = x;
r->next = s;
r = s;
}
r->next = NULL;
}
void del_x_list(LinkList &L, int index)
{
int j = 0;
LNode *p = L->next, *pre = L, *tmpNode;
if (index <= 0)
return;
//循环条件:p不为空
//若为NULL说明已遍历完成
while (p)
{
j++;
if (j < index)
{
pre = pre->next;
p = p->next;
}
else if (j == index)
{
tmpNode = p; //tmpNode指向该结点
p = p->next;
pre->next = p; //删除*tmpNode结点
free(tmpNode); //释放*tmpNode结点
}
else
{
break;
}
}
}
void print(LinkList L)
{
//输出链表元素值,每个值后输出一个空格
LinkList p = L->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}