第二章 栈、队列、链表(解密QQ号,回文、纸牌游戏、模拟链表)_dengjiongao3127的博客-程序员宝宝

深刻理解这些数据结构的思想,数据结构与算法是紧密联系在一起的

一、队列

新学期开始了,小哈是小哼的新同,小哼向小哈询问QQ号,小哈当然不会直接告诉小哼。所以小哈给了小哼一串加密过的数字,同时小哈也告诉了小哼解密规则。规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数再放到这串数的末尾,再将第5个数删除……直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一起就是小哈的QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。解密后小哈的QQ号应该是“6 1 5 9 4 7 2 8 3”。

使用数组模拟队列

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 void array_sort(int q[],int n)
 4 {
 5     int *temp = (int *)malloc(sizeof(int)*n);
 6     int head=0, tail=n,i=0;
 7     while (head<tail)
 8     {
 9         temp[i++] = q[head];
10         head++;
11         q[tail] = q[head];
12         tail++;
13         head++;
14     }
15     for (i = 0;i < n;i++)
16         q[i] = temp[i];
17     free(temp);
18 }
19 int main()
20 {
21     int n = 18,i;
22     int q[18] = {
     6,3,1,7,5,8,9,2,4};
23     array_sort(q,n/2);
24     for (i = 0;i < n/2;i++)
25     {
26         printf("%d ",q[i]);
27     }
28     printf("\n");
29     return 0;
30 }
View Code

  使用结构体模拟队列,队列结构的扩展

 1 #include <stdio.h>
 2 struct queue
 3 {
 4     int tail;
 5     int head;
 6     int data[1000];
 7 };
 8 void struct_sort(struct queue *q, int n)
 9 {
10     int i = 0;
11     struct queue temp;
12     q->head = 0;
13     q->tail = n;
14     while (q->head < q->tail)
15     {
16         temp.data[i] = q->data[q->head];
17         (q->head)++;
18         q->data[q->tail]= q->data[q->head];
19         (q->head)++;
20         (q->tail)++;
21         i++;
22     }
23     for (int i = 0;i < n;i++)
24     {
25         q->data[i] = temp.data[i];
26     }
27 }
28 int main()
29 {
30     int n = 18, i;
31     struct queue q;
32     int a[9] = { 6,3,1,7,5,8,9,2,4 };
33     for (i = 0;i < 9;i++)
34     {
35         q.data[i] = a[i];
36     }
37     struct_sort(&q,n/2);
38     for (i = 0;i < n / 2;i++)
39     {
40         printf("%d ", q.data[i]);
41     }
42     printf("\n");
43     return 0;
44 }
View Code

二、栈

  队列,它是一种先进先出的数据结构。还有一种是后进先出的数据结构它叫做栈。栈限定只能在一端进行插入和删除操作。比如说有一个小桶, 小桶的直径只能放一个小球,我们现在向小桶内依次放入2号、1号、3号小球。假如你现在需要拿出2号小球,那就必须先将3号小球拿出,再拿出1号小球,最 后才能将2号小球拿出来。在刚才取小球的过程中,我们最先放进去的小球最后才能拿出来,而最后放进去的小球却可以最先拿出来。这就是后进先出,也可以称为 先进后出。

  我们生活中还有很多这样的例子,比如我们在吃桶装薯片的时候,要想吃掉最后一片,就必须把前面的全部吃完(貌似现在的桶装薯片为了减少分量,在桶里 面增加了一个透明的抽屉);再比如我们浏览网页时候需要退回到之前的某个网页,我们需要一步步的点击后退键。还有手-枪的弹夹,在装子弹的时候,最后装的 一发子弹,是被第一个打出去的。栈的实现也很简单,只需要一个一维数组和一个指向栈顶的变量top就可以了。我们通过变量top来对栈进行插入和删除操 作。
        这种特殊的数据结构栈究竟有哪些作用呢?我们来看一个例子。“xyzyx”是一个回文字符串,所谓回文字符串就是指正读反读均相同的字符序列,如 “席主席”、“记书记”、“aha”和“ahaha”均是回文,但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。
 1 //使用数组模拟栈
 2 #include <stdio.h>
 3 #include <string.h>
 4 int main()
 5 {
 6        char a[102],s[102];
 7        //s为栈
 8        int i,len,j,mid,next;
 9        gets(a);
10        len=strlen(a);
11        mid=len/2;
12        //栈初始化
13        for(i=0;i<mid;i++)
14        {
15               s[i]=a[i];
16        }
17        if(len%2)
18               next=mid+1;
19        else
20               next=mid;
21        for(j=next;j<len;j++)
22        {
23               if(a[j]!=s[--i])
24                      break;
25        }
26        if(i==0)
27               printf("YES\n");
28        else
29               printf("NO\n");
30     
View Code

//星期天小哼和小哈约在一起玩桌游,他们在玩一个非常古怪的扑克游戏
//游戏规则:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌子上,然后小哈也拿出手中的第一张扑克牌
//并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。
//出牌时,如果某人打出的牌与桌子上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走
//并依次放在自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜
//输入:2 4 1 2 5 6
// :3 1 3 5 6 4
//结果:赢
// 输的人手中的牌是
// 桌上的牌是

  1 //按逻辑关系来就可以了
  2 //数据结构
  3 //两个队列,出牌是出队列,赢牌是入队列
  4 //一个栈,放牌是入栈,有人赢牌是出栈
  5 
  6 //对于在桌上的牌,假设牌的种类为10,使用标记,对桌上的牌进行标记
  7 //灵活的使用标记
  8 #include <stdio.h>
  9 struct queue
 10 {
 11     int head;
 12     int tail;
 13     int data[100];
 14 };
 15 struct stack
 16 {
 17     int data[10];//桌上的牌不会超过其种类
 18     int top;
 19 };
 20 int main()
 21 {
 22     int i,j,temp,mid;
 23     int book[10];
 24     struct queue q1, q2;
 25     struct stack s;
 26     s.top = 0;q1.head = 0;q1.tail = 0;q2.head = 0;q2.tail = 0;
 27     for (i = 0;i < 6;i++)
 28         scanf("%d",&q1.data[q1.tail++]);
 29     for (i = 0;i < 6;i++)
 30         scanf("%d", &q2.data[q2.tail++]);
 31     for (i = 0;i < 10;i++)
 32         book[i] = 0;
 33     while (q1.head < q1.tail&&q2.head < q2.tail)
 34     {
 35         //q1先出牌
 36         temp = q1.data[q1.head];
 37         if (book[temp])//q1赢牌
 38         {
 39             q1.head++;
 40             q1.data[q1.tail++] = temp;
 41             while (s.data[s.top]!=temp)
 42             {
 43                 book[s.data[s.top]] = 0;
 44                 q1.data[q1.tail++] = s.data[s.top--];
 45             }
 46         }
 47         else//q1出牌
 48         {
 49             q1.head++;
 50             s.top++;
 51             s.data[s.top] = temp;
 52             book[temp] = 1;
 53         }
 54         //q2后出牌
 55         temp = q2.data[q2.head];
 56         if (book[temp])//q2赢牌
 57         {
 58             q2.head++;
 59             q2.data[q2.tail++] = temp;
 60             while (s.data[s.top] != temp)
 61             {
 62                 book[s.data[s.top]] = 0;
 63                 q2.data[q2.tail++] = s.data[s.top--];
 64             }
 65         }
 66         else//q2出牌
 67         {
 68             q2.head++;
 69             s.top++;
 70             s.data[s.top] = temp;
 71             book[temp]=1;
 72         }
 73     }
 74     if (q1.head < q1.tail)
 75     {
 76         printf("q2 win!\n");
 77         printf("q1:");
 78         for (i = q1.head;i < q1.tail;i++)
 79         {
 80             printf("%d ",q1.data[i]);
 81         }
 82         printf("\n");
 83         if (s.top > 0)
 84         {
 85             printf("desk:");
 86             for (i = 1;i <= s.top;i++)
 87                 printf("%d ", s.data[i]);
 88             printf("\n");
 89         }
 90     }
 91     else
 92     {
 93         printf("q1 win!\n");
 94         printf("q2:");
 95         for (i = q2.head;i < q2.tail;i++)
 96         {
 97             printf("%d ", q2.data[i]);
 98         }
 99         printf("\n");
100         if (s.top > 0)
101         {
102             printf("desk:");
103             for (i = 1;i <= s.top;i++)
104                 printf("%d ", s.data[i]);
105             printf("\n");
106         }
107     }
108     return 0;
109 }
View Code

三、链表

引入链表的原因:数组的长度需要事先知道,且不能更改;当发生数据移动时,资源消耗大,链表只需要指针指向改变下就可以了
 
该文章写的还是比较清楚的
指针:存储地址
C语言中“*”的3中用法:
1、乘号
2、声明一个指针 int *p;
3、间接运算符printf("%d\n",*p);
动态申请空间:malloc
          int *p;
          p=(int *)malloc(sizeof(int));
          sizeof(int)=4;int为4个字节大小
          malloc(4);申请4字节大小的内存,p为返回申请的内存的地址
//程序功能:输入数据,建立链表,并按顺序进行遍历
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct node
 4 {
 5     int data;
 6     struct node *next;
 7 }node,*link;
 8 int main()
 9 {
10     link head, p,q,temp;
11     int i, n,t;
12     scanf("%d",&n);
13     head = NULL;
14     for (i = 0;i < n;i++)
15     {
16         scanf("%d", &t);
17         link p = (link)malloc(sizeof(node));
18         p->data = t;
19         p->next = NULL;
20         if (head == NULL)
21         {
22             head = p;
23         }
24         else
25         {
26             q->next = p;
27         }
28         q = p;
29     }
30     temp = head;
31     while (temp != NULL)
32     {
33         printf("%d ",temp->data);
34         temp = temp->next;
35     }
36     printf("\n");
37     return 0;
38 }
View Code
//程序功能:输入从小到大的数,建立链表
//               输入一个数,插入到链表中,使链表的数据还是保持从小到大的顺序
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct node
 4 {
 5     int data;
 6     struct node *next;
 7 }node,*link;
 8 int main()
 9 {
10     int n, i,a;
11     link head, p, q,temp,t;
12     head = NULL;
13     scanf("%d",&n);
14     for (i = 0;i < n;i++)
15     {
16         scanf("%d",&a);
17         temp = (link)malloc(sizeof(node));
18         temp->data = a;
19         temp->next = NULL;
20         if (head == NULL)
21         {
22             head = temp;
23         }
24         else
25         {
26             p->next = temp;
27         }
28         p = temp;
29     }
30     //插入数据
31     scanf("%d",&a);
32     temp = (link)malloc(sizeof(node));
33     temp->data = a;
34     temp->next = NULL;
35     t = head;
36     while (t != NULL)
37     {
38         if (head->data > a)
39         {
40             temp->next = head;
41             head = temp;
42             break;
43         }
44         else if (t->next->data > a)
45         {
46             temp->next = t->next;
47             t->next = temp;
48             break;
49         }
50         t = t->next;
51     }
52     t = head;
53     while (t != NULL)
54     {
55         printf("%d ",t->data);
56         t = t->next;
57     }
58     return 0;
59 }
View Code
模拟链表:用数组模拟链表(用两个数组)
               一个数组存储序列中的数
               另一个数组存储当前位置数的右边数的位置
如    1   2    3    4
data 2   3    5    6
right 2   3    4    0
插入 4后
          1     2     3     4     5
data   2     3     5     6     4
right   2     5     4     0     3
//输入从小到大的一个序列
//插入一个数,序列还是爆出从小到大,并输出
 1 #include <stdio.h>
 2 int main()
 3 {
 4     int n, i,t,len;
 5     int a[100], right[100];
 6     scanf("%d",&n);
 7     len = n;
 8     for (i = 1;i <= n;i++)
 9     {
10         scanf("%d", a + i);
11         right[i] = i + 1;
12     }
13     right[n] = 0;
14     scanf("%d",&t);
15     len++;
16     a[len] = t;
17     i = 1;
18     while (i != 0)
19     {
20         if (a[right[i]] > t)
21         {
22             right[len] = right[i];
23             right[i] = len;
24             break;
25         }
26         i = right[i];
27     }
28     i = 1;
29     while (i != 0)
30     {
31         printf("%d ",a[i]);
32         i = right[i];
33     }
34     return 0;
35 }
View Code

转载于:https://www.cnblogs.com/naglish/p/6911393.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dengjiongao3127/article/details/101396834

智能推荐

小牛vs小客 小牛再战 两篇小博弈_追逐星辰的光的博客-程序员宝宝

题目描述小牛和小客玩石子游戏,他们用n个石子围成一圈,小牛和小客分别从其中取石子,谁先取完谁胜,每次可以从一圈中取一个或者相邻两个,每次都是小牛先取,请输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)(1 2 3 4 取走 2 13 不算相邻)输入描述:输入包括多组测试数据每组测试数据一个n(1≤n≤1e9)输出描述:每组用一行输出胜利者的名字(小牛获胜输出XiaoNiu...

加入购物车动画-UIBezierPath曲线的实用_Devil_MayCare的博客-程序员宝宝

作者:嘿晴天原文链接:http://www.jianshu.com/p/bd650158d44c交互动画,是一款吸引用户的装逼神技,这是最近弄了一个加入购物车的交互动画,并封装了一下,效果图如下1 原理这里是给屏幕 添加了一个 关键帧动画 和旋转动画的图层(1)关键帧动画

Web开发之三:前后端开发任务量分析与比较_junli_chen的博客-程序员宝宝_一个项目前后端人数比例

这一年来的项目,无论是个人中心、文库还是学科测评,每次都会被一个问题所困扰,那就是如何估量前后端的任务量、如何确定前后端的人员比。    在采用分工模式之后,经过两个项目的开发,和大个、阿黄、建坤可以明显的感觉到前端开发在整个项目中耗时最多,但是究竟占多大的比例,我们却没有仔细的去思考。每次项目安排人员,前后端人员比大致为1:1,这明显是不合适的,所以在项目后期,后端人员要么闲下来了,要么

韩顺平Linux网课笔记(25到28)_garrulousabyss的博客-程序员宝宝

二十五 .Linux实操篇_实用指令 mkdir rmdir  二十六 .Linux实操篇_实用指令 touch cp  二十七 .Linux实操篇_实用指令 rm mv  二十八 .Linux实操篇_实用指令 cat more less   ...

webservice 的权限验证_weixin_30242907的博客-程序员宝宝

1. http://blog.csdn.net/jaune161/article/details/256026552.http://wcp88888888.iteye.com/blog/13993013.http://stupidbirds.iteye.com/blog/14956954.http://blog.csdn.net/lzwjavaphp/article/detai...

Python Process 进程池_妹特斯邦威的博客-程序员宝宝

进程池基本概念在程序实际处理问题过程中,忙时会有成千上万的任务需要被执行,闲时可能只有零星任务。频繁创建和销毁进程会影响系统性能和程序效率。这时定义一个池子,在里面放上固定数量的进程,有任务来了,就拿一个池中的进程来处理任务,等到处理完毕,进程并不关闭,而是将进程再放回进程池中继续等待任务。如果有很多任务需要执行,池中的进程数量不够,就要等待之前的进程执行任务完毕归来拿到空闲进程才能继续执行。...

随便推点

各种数据库的JDBC驱动下载及连接字符串URL写法 _wo1017的博客-程序员宝宝

<br />各种数据库的JDBC驱动下载及连接字符串URL写法 <br />各种数据库的JDBC驱动下载及连接字符串URL写法 <br />sun官方网站上的JDBC驱动列表:http://java.sun.com/products/jdbc/reference/industrysupport/index.html<br /><br />数 据 库  说      明  <br />MySQL  http://www.mysql.com/products/connector/j/ Shipped. But

批量读取数据next_batch()简单实现_liuzh(少昊)的博客-程序员宝宝

def next_batch(train_data, train_target, batch_size): index = [ i for i in range(0,len(train_target)) ] np.random.shuffle(index); batch_data = []; batch_target = []; for i...

Java内部类以及使用场景_时间漏斗的博客-程序员宝宝_java内部类使用场景

所谓内部类,即定义在另一个类中的类。那么,为什么会有内部类这个概念,他的使用场景又是什么呢?首先,来看一下内部类的特点:1. 它体现了一种代码的隐藏机制和访问控制机制,内部类与所在外部类有一定的关系,往往只有该外部类调用此内部类,所以没有必要专门用一个Java文件存放这个类。 public class Outer {  private int num;   private class Inner {    private int num;  }}一般的类是不允许用private修饰符

如何从IDEA提交任务到Spark,并查看任务执行结果_权GG的博客-程序员宝宝

1.创建程序打开IDEA——选择Maven项目——在下面找到scala222.IDEA程序如下

Centos7 修改文件夹权限和用户名用户组_张志翔 ̮的博客-程序员宝宝_centos7文件夹权限修改

Linux系统下经常遇到文件或者文件夹的权限问题,或者是因为文件夹所属的用户问题而没有访问的权限。根据我自己遇到的情况,对这类问题做一个小结。在命令行使用命令“ll”或者“ls -a”,可以查看文件或者文件的权限: -rw-r--r--. 1 root root 6 Nov 9 16:42 a.txt其中“-rw-r--r--”表示权限,一共有十个字符。第一个字符,如果是...

selenium总结_北山啦的博客-程序员宝宝

selenium提取数据总结附思维导图1. driver对象的常用属性和方法在使用selenium过程中,实例化driver对象后,driver对象有一些常用的属性和方法driver.page_source 当前标签页浏览器渲染之后的网页源代码driver.current_url 当前标签页的urldriver.close() 关闭当前标签页,如果只有一个标签页则关闭整个浏览器driver.quit() 关闭浏览器driver.forward() 页面前进driver.back()

推荐文章

热门文章

相关标签