算法一日一练 03
本帖最后由 故乡的风 于 2013-7-21 08:33 编辑(1)删除顺序表L1中所有值为x的元素
(2)使用递归算法,删除不带头节点的单链表L2中所有值为x的节点
(3)删除带头节点的单链表L3中所有值为x的节点
试着设计在时间及空间两方面都尽量高效的算法,将想法及源码贴出来(语言不限,最好C/C++),并写出各算法的时间复杂度及空间复杂度。我将适量给予评分,希望大家踊跃参与。
为规范数据结构与算法的设计,请定义类似如下的抽象数据类型,谢谢。
typedef int ElemType; // 元素类型
#define MAX_SIZE 50 // 定义线性表的最大长度
typedef struct {
ElemType data; // 顺序表的元素
int length; // 顺序表的当前长度
} SqList; // 顺序表的类型定义
typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList; // 单链表节点
呵呵,过来学习一下 第一题代码:时间复杂度为O(n),时间常数有点大
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
typedef int ElemType; // 元素类型
#define MAX_SIZE 50 // 定义线性表的最大长度
typedef struct {
ElemType data; // 顺序表的元素
int length; // 顺序表的当前长度
} SqList; // 顺序表的类型定义
int main()
{
SqList list;//顺序表的标识符
printf("请输入顺序表的长度:");
scanf("%d",&list.length);
printf("请输入顺序表的元素:\n");
for(int i=0;i<list.length;i++)
{
scanf("%d",&list.data);
}
printf("当前顺序表为:\n");
for(int i=0;i<list.length;i++)
printf("%d ",list.data);
printf("\n");
int x;
printf("请输入要删除的元素:");
scanf("%d",&x);
queue<int>q; //有点投机取巧,用stl的队列存储未删除的元素
for(int i=0;i<list.length;i++)
{
if(list.data!=x)
q.push(list.data);
}
list.length=0;
while(!q.empty()) //将未删除的元素重新加入顺序表中
{
list.data=q.front();
q.pop();
}
printf("删除后的顺序表为:\n");
for(int i=0;i<list.length;i++)
printf("%d ",list.data);
printf("\n");
return 0;
} 第二题代码:有两个小bug,解决起来比较麻烦,所以没调了,:L,复杂度O(n)
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
typedef int ElemType; // 元素类型
#define MAX_SIZE 50 // 定义线性表的最大长度
typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList; // 单链表节点
int n,x;
void delet(LNode* a) //删除操作
{
if(a==NULL)
return;
if(a->next==NULL)
{
if(a->data==x)
a=NULL;
return;
}
if(a->next->data==x)
{
LNode *b=a->next;
a->next=b->next; //递归
delet(a->next);
}
else
delet(a->next);
}
int main()
{
LNode L2;
scanf("%d",&n);//输入节点数
for(int i=0;i<n;i++)
{
scanf("%d",&L2.data); //输入数据
L2.next=&L2;
}
L2.next=NULL;
scanf("%d",&x); //输入待删除的数
LNode *head=&L2;
if(L2.data==x)
{
head=&L2;
}
delet(&L2);
while(head!=NULL)//打印操作后的链表
{
printf("%d ",head->data);
head=head->next;
}
printf("\n");
return 0;
} 第三题原理和第二题差不多,不过有了头结点,删除第一个元素就方便了,代码就不写了。。。 这里哪不对 王海伦 发表于 2013-7-21 16:29 static/image/common/back.gif
这里哪不对
c++写的你建c语言程序当然不对 王海伦 发表于 2013-7-21 16:29 static/image/common/back.gif
这里哪不对
你文件的后缀为.c,编译器会采用C标准进行编译,而代码并非使用C标准写的。将文件后缀改为.cpp结尾,应该就没问题了。 本帖最后由 故乡的风 于 2013-7-22 11:17 编辑
四季如春へ★ 发表于 2013-7-21 14:10 static/image/common/back.gif
第一题代码:时间复杂度为O(n),时间常数有点大
#include
#include
使用队列,虽然没有增加算法的时间复杂度,但是算法空间复杂度增加为O(n),不是最佳算法。不过,你能想到使用队列,想法很新颖。你写的代码经常能带来意想不到的方法,这点我很赞赏。
另外,鉴于我们主要讨论思想,使用STL带来的时空损失并没有严格讨论。我对STL不了解,它的实现方式也不清楚,元素入队列所需的时间也损失无法判断。你使用的时候可以考虑一下,在这里,我们不做其他考虑了。
四季如春へ★ 发表于 2013-7-21 15:19 static/image/common/back.gif
第三题原理和第二题差不多,不过有了头结点,删除第一个元素就方便了,代码就不写了。。。
其实这道题,我打算是让大家不用递归,直接删除元素的,毕竟这个是单链表操作的一个基础,也是很重要的,主要让大家练练手的。不过,你不写也没事,相信对你来说也没问题,就不用浪费时间了嘛。 学习了啊,呵呵 路过,随便看看,学习一下 好文章转过来方便自己看
页:
[1]