算法一日一练 03

故乡的风

(1)删除顺序表L1中所有值为x的元素
(2)使用递归算法，删除不带头节点的单链表L2中所有值为x的节点
(3)删除带头节点的单链表L3中所有值为x的节点

试着设计在时间及空间两方面都尽量高效的算法，将想法及源码贴出来（语言不限，最好C/C++），并写出各算法的时间复杂度及空间复杂度。我将适量给予评分，希望大家踊跃参与。

为规范数据结构与算法的设计，请定义类似如下的抽象数据类型，谢谢。

typedef int ElemType;   // 元素类型

#define MAX_SIZE 50     // 定义线性表的最大长度
typedef struct {
    ElemType data[MAX_SIZE];    // 顺序表的元素
    int length;                 // 顺序表的当前长度
} SqList;                       // 顺序表的类型定义

typedef struct LNode {
    ElemType data;          // 数据域
    struct LNode *next;     // 指针域
} LNode, *LinkList;     // 单链表节点

yuqiuwangzi

呵呵，过来学习一下

四季如春へ★

第一题代码：时间复杂度为O（n），时间常数有点大
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

typedef int ElemType;   // 元素类型

#define MAX_SIZE 50     // 定义线性表的最大长度
typedef struct {
    ElemType data[MAX_SIZE];    // 顺序表的元素
    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[i]);
        }
        printf("当前顺序表为：\n");
        for(int i=0;i<list.length;i++)
                printf("%d ",list.data[i]);
        printf("\n");
        int x;
        printf("请输入要删除的元素：");
        scanf("%d",&x);
        queue<int>q;           //有点投机取巧，用stl的队列存储未删除的元素
        for(int i=0;i<list.length;i++)
        {
                if(list.data[i]!=x)
                        q.push(list.data[i]);
        }
        list.length=0;
        while(!q.empty())    //将未删除的元素重新加入顺序表中
        {
                list.data[list.length++]=q.front();
                q.pop();
        }
        printf("删除后的顺序表为：\n");
        for(int i=0;i<list.length;i++)
                printf("%d ",list.data[i]);
        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[MAX_SIZE];
        scanf("%d",&n);  //输入节点数
        for(int i=0;i<n;i++)
        {
                scanf("%d",&L2[i].data); //输入数据
                L2[i].next=&L2[i+1];
        }
        L2[n-1].next=NULL;
        scanf("%d",&x);    //输入待删除的数
        LNode *head=&L2[0];
        if(L2[0].data==x)
        {
                head=&L2[1];
        }
        delet(&L2[0]);
        while(head!=NULL)  //打印操作后的链表
        {
                printf("%d ",head->data);
                head=head->next;
        }
        printf("\n");
        return 0;
}

四季如春へ★

第三题原理和第二题差不多，不过有了头结点，删除第一个元素就方便了，代码就不写了。。。

王海伦

这里哪不对

四季如春へ★

王海伦 发表于 2013-7-21 16:29

                               
登录/注册后可看大图

这里哪不对

c++写的你建c语言程序当然不对

故乡的风

王海伦 发表于 2013-7-21 16:29

                               
登录/注册后可看大图

这里哪不对

你文件的后缀为.c，编译器会采用C标准进行编译，而代码并非使用C标准写的。将文件后缀改为.cpp结尾，应该就没问题了。

故乡的风

四季如春へ★ 发表于 2013-7-21 14:10

                               
登录/注册后可看大图

第一题代码：时间复杂度为O（n），时间常数有点大
#include
#include

使用队列，虽然没有增加算法的时间复杂度，但是算法空间复杂度增加为O(n)，不是最佳算法。不过，你能想到使用队列，想法很新颖。你写的代码经常能带来意想不到的方法，这点我很赞赏。
另外，鉴于我们主要讨论思想，使用STL带来的时空损失并没有严格讨论。我对STL不了解，它的实现方式也不清楚，元素入队列所需的时间也损失无法判断。你使用的时候可以考虑一下，在这里，我们不做其他考虑了。

故乡的风

四季如春へ★ 发表于 2013-7-21 15:19

                               
登录/注册后可看大图

第三题原理和第二题差不多，不过有了头结点，删除第一个元素就方便了，代码就不写了。。。

其实这道题，我打算是让大家不用递归，直接删除元素的，毕竟这个是单链表操作的一个基础，也是很重要的，主要让大家练练手的。不过，你不写也没事，相信对你来说也没问题，就不用浪费时间了嘛。

晨风吹过

学习了啊，呵呵

风吹绿野

路过，随便看看，学习一下

猪猪BBUn咕咕

好文章转过来方便自己看