数据结构——线性表杂记

什么是线性表

线性表是一种常用的数据结构，表示元素之间一对一的相邻关系。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。

线性表是具有相同数据类型的n (n>=0)个数据元素的有限序列。其中n为表长，当n=0 时该线性表是一个空表。若用L命名线性表，则其一般表示如下： L=(a1, a2, …, ai, ai+1, …, an)

其中，a1是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

由此，我们得出线性表的特点如下：

表中元素的个数有限。
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序。
表中元素都是数据元素，每一个表元素都是单个元素。
表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。
表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究竟表示什么内容。

三种特殊线性表

栈
队列
串

从数据结构角度看，栈和队列是操作受限的线性表，它们的逻辑结构相同

串是重要的非数值处理对象，它是以字符作为数据元素的线性表

//这里我们主要讨论下栈与队列概念/区别

栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。

如：在建筑工地上，使用的砖块从底层一层一层向上放，使用时从最上面一层一层的拿。所以为后进先出。

队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

如：在生活中排队上车，排队的规则是不允许插队，后来的人需要站在队尾，每次总是对头先上车。所以为先进先出。

栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下：

线性表

Insert(L,i,x) 
(1≤i≤n+1) 
Delete(L,i) 
(1≤i≤n)

1

2

3

4

5

Insert(L,i,x)

(1≤i≤n+1)

Delete(L,i)

(1≤i≤n)

如线性表允许在表内任一位置进行插入和删除

栈

Insert(L,n+1,x) 
Delete(L,n)

1

2

3

Insert(L,n+1,x)

Delete(L,n)

而栈只允许在表尾一端进行插入和删除

队列

Insert(L,n+1,x) 
Delete(L,1)

1

2

3

Insert(L,n+1,x)

Delete(L,1)

队列只允许在表尾一端进行插入，在表头一端进行删除

END

学习哇

参考：百度/谷歌 (ง •̀_•́)ง

0x00 前言/概述

什么是结构体？为了便于引用数据，有时需要用不同的数据组合成一个有机的整体，而这样的整体中则是互相影响，相互联系。比如一个人的基本资料：编号，姓名，性别，地址（如下）。c语言中把这样自己指定的组合项称为结构体（structure）。

num	name	sex	addr
1	Ruilin	M	Shanxi

阅读剩余部分 –

【NOIP2014】生活大爆炸版石头剪刀布

12月 5, 2015
0 条评论

题目描述 Description

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克：《星际迷航》主角之一。蜥蜴人：《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。

现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-„„”，而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”

已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。

输入描述 Input Description

输入文件名为rps.in。

第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。

第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。数与数之间以一个空格分隔。

输出描述 Output Description

输出文件名为rps.out。

输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于100%的数据，0 < N ≤ 200，0 < NA ≤ 200， 0 < NB ≤ 200。

答案

#include<stdio.h>
#define MAXN 200
int r[5][5]={0,0,1,1,0,  
             1,0,0,1,0,  
             0,1,0,0,1,  
             0,0,1,0,1,  
             1,1,0,0,0,  
            }; 
int a[MAXN],b[MAXN];
int main()
{
	freopen("rps.in","r",stdin);
	freopen("rps.out","w",stdout);
	int n,na,nb;
	int suma=0,sumb=0;
	scanf("%d%d%d",&n,&na,&nb);
	for(int i=0;i<na;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<nb;i++)
        scanf("%d",&b[i]);
    for(int i=0;i<n;i++)
    {
        int c=a[i%na],d=b[i%nb];
		suma+=r[c][d];
		sumb+=r[d][c];
    }

    printf("%d %d",suma,sumb);   
    return 0;    
        
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

#include<stdio.h>

#define MAXN 200

int r[5][5]={0,0,1,1,0,

1,0,0,1,0,

0,1,0,0,1,

0,0,1,0,1,

1,1,0,0,0,

};

int a[MAXN],b[MAXN];

int main()

{

freopen("rps.in","r",stdin);

freopen("rps.out","w",stdout);

int n,na,nb;

int suma=0,sumb=0;

scanf("%d%d%d",&n,&na,&nb);

for(int i=0;i<na;i++)

scanf("%d",&a[i]);

for(int i=0;i<nb;i++)

scanf("%d",&b[i]);

for(int i=0;i<n;i++)

{

int c=a[i%na],d=b[i%nb];

suma+=r[c][d];

sumb+=r[d][c];

}

printf("%d %d",suma,sumb);

return 0;

}

阅读剩余部分 –

算法入门之开灯问题

12月 4, 2015
0 条评论

开灯问题属于C语言中一维数组中较为基础典型的一道练习

问题：

有n盏灯，编号为1~n。第一个人把所有灯都打开，第二个人按下所有编号为2的倍数的开关（这些灯将被关掉），第三个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），以此类推。一共有k个人，问最后有哪些灯开着？输入n和k,输出开着的灯的编号

样例输入：

7 3

样例输出：

1 5 6 7

【分析】

用a[1],a[2]…..a[n]来表示编号为1，2….n的灯
第二个人按下2的倍数，第三个人按下3的倍数可以通过第几盏灯除以第几个人取余数看是否为0
通过真假判断灯的亮灭

【代码】

#include<stdio.h>
#include<string.h>
#define maxn 1010
int a[maxn];
int main()
{
	int n,k,first=1;
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	   for(int j=1;j<=n;j++)
	     if(j%i==0) a[j]=!a[j];
    for(int i=1;i<=n;i++)
       if(a[i])
       {
       	if(first)
       	  first=0;
 	else
 	  printf(" ");
 	  printf("%d",i);
       }
     printf("\n");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

#include<stdio.h>

#include<string.h>

#define maxn 1010

int a[maxn];

int main()

{

int n,k,first=1;

memset(a,0,sizeof(a));

scanf("%d%d",&n,&k);

for(int i=1;i<=k;i++)

for(int j=1;j<=n;j++)

if(j%i==0) a[j]=!a[j];

for(int i=1;i<=n;i++)

if(a[i])

{

if(first)

first=0;

else

printf(" ");

printf("%d",i);

}

printf("\n");

return 0;

}

部分解释：

memset(a,0,sizeof(a)); 用来表示把数组a清零，他在#include<string.h> 中定义

接下来

for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
if(j%i==0) a[j]=!a[j];

依次用第几盏灯数除以当前第几个人取余数看是否为0，如果是则取反即1->0 ,0->1来表示灯的亮灭

接下来程序为了避免输出多余的空格，设置了一个标志变量first 开始时定义first=1即为真if(first) first=0;来管理当前输出变量是否为第一个，如果是则first为0即为假，后续每一个值前加一个空格

阅读剩余部分 –

计算线段长度

11月 6, 2015
0 条评论

总时间限制:: 1000ms
内存限制:: 65536kB

描述: 已知线段的两个端点的坐标A（Xa,Ya），B（Xb，Yb），求线段AB的长度。
输入: 共两行。
第一行是两个实数Xa，Ya，即A的坐标。
第二行是两个实数Xb，Yb，即B的坐标。
输入中所有实数的绝对值均不超过10000。
输出: 一个实数，即线段AB的长度，保留到小数点后3位。
样例输入
1 1 2 2 1 2 1 1 2 2
样例输出
1.414 1 1.414

答案：

#include<stdio.h>
#include<math.h>
int main()
{
float Xa,Ya,Xb,Yb;
scanf("%f%f%f%f",&Xa,&Ya,&Xb,&Yb);
float s=(Xa-Xb)* (Xa-Xb)+(Ya-Yb)*(Ya-Yb);
float t=sqrt(s);
printf("%.3f",t);
return 0;
}

1

2

3

4

5

6

7

8

9

10

11

#include<stdio.h>

#include<math.h>

int main()

{

float Xa,Ya,Xb,Yb;

scanf("%f%f%f%f",&Xa,&Ya,&Xb,&Yb);

float s=(Xa-Xb)* (Xa-Xb)+(Ya-Yb)*(Ya-Yb);

float t=sqrt(s);

printf("%.3f",t);

return 0;

}

空格分隔输出

10月 31, 2015
0 条评论

好久没看C了，从简单开始做做看.毕竟我是个渣渣…

空格分隔输出

总时间限制:: 1000ms
内存限制:: 65536kB

描述

读入一个字符，一个整数，一个单精度浮点数，一个双精度浮点数，然后按顺序输出它们，并且要求在他们之间用一个空格分隔。输出浮点数时保留6位小数。

输入

共有四行：
第一行是一个字符；
第二行是一个整数；
第三行是一个单精度浮点数；
第四行是一个双精度浮点数。

输出

输出字符、整数、单精度浮点数和双精度浮点数，之间用空格分隔。

样例输入

a
12
2.3
3.2

1

2

3

4

a

12

2.3

3.2

样例输出

a 12 2.300000 3.200000

1	a 12 2.300000 3.200000

阅读剩余部分 –

分类 C语言下的文章