设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 15道简单算法题(附源代码第一部分)
返回列表 发新帖
查看: 2905|回复: 9

[技术交流] 15道简单算法题(附源代码第一部分)

[复制链接]
H9enRy
发表于 2014-8-1 01:06:29 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x


　1:合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;

　　2:合并两个单链表;

　　3:倒序打印一个单链表;

　　4:给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;

　　5:找到链表倒数第K个节点;

　　6:反转单链表;

　　7:通过两个栈实现一个队列;

　　8:二分查找;

　　9:快速排序;

　　10:获得一个int型的数中二进制中的个数;

　　11:输入一个数组，实现一个函数，让所有奇数都在偶数前面;

　　12:判断一个字符串是否是另一个字符串的子串;

　　13:把一个int型数组中的数字拼成一个串，这个串代表的数字最小;

　　14:输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;

　　15:输入两个链表，找到它们第一个公共节点;

　　下面简单说说思路和代码实现。

[backcolor=white !important][size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em][size=1em]//链表节点
[size=1em]struct NodeL
[size=1em]{
[size=1em]    int value;
[size=1em]    NodeL* next;
[size=1em]    NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
[size=1em]};
[size=1em]//二叉树节点
[size=1em]struct NodeT
[size=1em]{
[size=1em]    int value;
[size=1em]    NodeT* left;
[size=1em]    NodeT* right;
[size=1em]    NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
[size=1em]};



　　1:合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;

　　合并排序一般的思路都是创建一个更大数组C，刚好容纳两个数组的元素，先是一个while循环比较，将其中一个数组A比较完成，将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中，再将A中剩下的数存入C中，但这里是已经有一个数组能存下两个数组的全部元素，就不用在创建数组了，但只能从后往前面存，从前往后存，要移动元素很麻烦。

[backcolor=white !important][size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em]29

[size=1em]30

[size=1em]31

[size=1em]32

[size=1em]33

[size=1em]34

[size=1em]35

[size=1em]36

[size=1em][size=1em]//合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素
[size=1em]void MergeArray(int a[],int alen,int b[],int blen)
[size=1em]{
[size=1em]    int len=alen+blen-1;
[size=1em]    alen--;
[size=1em]    blen--;
[size=1em]    while (alen>=0 && blen>=0)
[size=1em]    {
[size=1em]        if (a[alen]>b[blen])
[size=1em]        {
[size=1em]            a[len--]=a[alen--];
[size=1em]        }else{
[size=1em]            a[len--]=b[blen--];
[size=1em]        }
[size=1em]    }

[size=1em]    while (alen>=0)
[size=1em]    {
[size=1em]        a[len--]=a[alen--];
[size=1em]    }
[size=1em]    while (blen>=0)
[size=1em]    {
[size=1em]        a[len--]=b[blen--];
[size=1em]    }
[size=1em]}

[size=1em]void MergeArrayTest()
[size=1em]{
[size=1em]    int a[]={2,4,6,8,10,0,0,0,0,0};
[size=1em]    int b[]={1,3,5,7,9};
[size=1em]    MergeArray(a,5,b,5);
[size=1em]    for (int i=0;i<sizeof(a)/sizeof(a[0]);i++)
[size=1em]    {
[size=1em]        cout<<a[i]<<" ";
[size=1em]    }
[size=1em]}



　　2:合并两个单链表;

　　合并链表和合并数组，我用了大致相同的代码，就不多少了，那本书用的是递归实现。

[backcolor=white !important][size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em]29

[size=1em]30

[size=1em]31

[size=1em]32

[size=1em]33

[size=1em]34

[size=1em]35

[size=1em]36

[size=1em]37

[size=1em]38

[size=1em]39

[size=1em]40

[size=1em]41

[size=1em]42

[size=1em]43

[size=1em]44

[size=1em]45

[size=1em]46

[size=1em]47

[size=1em]48

[size=1em]49

[size=1em]50

[size=1em]51

[size=1em]52

[size=1em]53

[size=1em]54

[size=1em]55

[size=1em]56

[size=1em]57

[size=1em]58

[size=1em]59

[size=1em]60

[size=1em]61

[size=1em]62

[size=1em]63

[size=1em]64

[size=1em]65

[size=1em]66

[size=1em]67

[size=1em]68

[size=1em]69

[size=1em]70

[size=1em]71

[size=1em]72

[size=1em]73

[size=1em]74

[size=1em][size=1em]//链表节点
[size=1em]struct NodeL
[size=1em]{
[size=1em]    int value;
[size=1em]    NodeL* next;
[size=1em]    NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
[size=1em]};

[size=1em]//合并两个单链表
[size=1em]NodeL* MergeList(NodeL* head1,NodeL* head2)
[size=1em]{
[size=1em]    if (head1==NULL)
[size=1em]        return head2;
[size=1em]    if (head2==NULL)
[size=1em]        return head1;

[size=1em]    NodeL* head=NULL;
[size=1em]    if (head1->value<head2->value)
[size=1em]    {
[size=1em]        head=head1;
[size=1em]        head1=head1->next;
[size=1em]    }else{
[size=1em]        head=head2;
[size=1em]        head2=head2->next;
[size=1em]    }
[size=1em]    NodeL* tmpNode=head;
[size=1em]    while (head1 && head2)
[size=1em]    {
[size=1em]        if (head1->value<head2->value)
[size=1em]        {
[size=1em]            head->next=head1;
[size=1em]            head1=head1->next;
[size=1em]        }else{
[size=1em]            head->next=head2;
[size=1em]            head2=head2->next;
[size=1em]        }
[size=1em]        head=head->next;
[size=1em]    }
[size=1em]    if (head1)
[size=1em]    {
[size=1em]        head->next=head1;
[size=1em]    }
[size=1em]    if (head2)
[size=1em]    {
[size=1em]        head->next=head2;
[size=1em]    }
[size=1em]    return tmpNode;
[size=1em]}

[size=1em]void MergeListTest()
[size=1em]{
[size=1em]    NodeL* head1=new NodeL(1);
[size=1em]    NodeL* cur=head1;
[size=1em]    for (int i=3;i<10;i+=2)
[size=1em]    {
[size=1em]        NodeL* tmpNode=new NodeL(i);
[size=1em]        cur->next=tmpNode;
[size=1em]        cur=tmpNode;
[size=1em]    }
[size=1em]    NodeL* head2=new NodeL(2);
[size=1em]    cur=head2;
[size=1em]    for (int i=4;i<10;i+=2)
[size=1em]    {
[size=1em]        NodeL* tmpNode=new NodeL(i);
[size=1em]        cur->next=tmpNode;
[size=1em]        cur=tmpNode;
[size=1em]    }
[size=1em]    NodeL* head=MergeList(head1,head2);
[size=1em]    while (head)
[size=1em]    {
[size=1em]        cout<<head->value<<" ";
[size=1em]        head=head->next;
[size=1em]    }
[size=1em]}



　　3:倒序打印一个单链表;

　　递归实现，先递归在打印就变成倒序打印了，如果先打印在调用自己就是顺序打印了。

[backcolor=white !important][size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em][size=1em]//倒序打印一个单链表
[size=1em]void ReversePrintNode(NodeL* head)
[size=1em]{
[size=1em]    if (head)
[size=1em]    {
[size=1em]        ReversePrintNode(head->next);
[size=1em]        cout<<head->value<<endl;
[size=1em]    }
[size=1em]}
[size=1em]void ReversePrintNodeTest()
[size=1em]{
[size=1em]    NodeL* head=new NodeL();
[size=1em]    NodeL* cur=head;
[size=1em]    for (int i=1;i<10;i++)
[size=1em]    {
[size=1em]        NodeL* tmpNode=new NodeL(i);
[size=1em]        cur->next=tmpNode;
[size=1em]        cur=tmpNode;
[size=1em]    }
[size=1em]    ReversePrintNode(head);
[size=1em]}






想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

cable5881
发表于 2014-8-4 18:01:47 | 显示全部楼层
儿飞飞飞飞威风威风
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

cable5881
发表于 2014-8-11 17:38:38 | 显示全部楼层
谢谢楼主分享！！！！！！！！！！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

tlwangxd
发表于 2014-11-18 09:30:16 | 显示全部楼层
学习
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

leslie初见
发表于 2014-11-26 20:08:06 | 显示全部楼层

必须得顶下
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

tlwangxd
发表于 2014-12-3 08:51:29 | 显示全部楼层
路过
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

微逻辑
发表于 2014-12-9 00:17:35 | 显示全部楼层
好
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

tlwangxd
发表于 2014-12-10 09:04:16 | 显示全部楼层
看看
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zjc7836
发表于 2015-1-14 20:40:38 | 显示全部楼层
楼主nb
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

zjc78361
发表于 2015-1-21 20:10:52 | 显示全部楼层
代码在哪？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 07:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表