线性数据结构
什么是数据结构？
  数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。通常情况下，精⼼选择的数据结构可以带来更⾼的运⾏或者存储效率。数据结构往往同⾼效的检索算法和索引技术有关。
举3个例⼦：
⾷堂排队打饭，每个⼈与前后⼈之间的关系
计算机的⽬录结构
⼿机导航软件如何存储位置
⼀、线性数据结构
  线性数据结构的特点：
存在唯⼀的⼀个被称作“第⼀个”的数据元素
存在唯⼀的⼀个被称作“最后⼀个”的数据元素
除第⼀个以外，集合中的每个数据元素均只有⼀个前驱
除最后⼀个以外，集合中的每个数据元素均只有⼀个后继
  【思考】：　⼀元多项式f(x)=a0+a1x+···a n-1x n-1+a n x n在计算机中如何表⽰？
        计算机如何运算5-4*3+2
  1.线性表的存储结构
    线性表就像⽕车，按照储存结构分为：顺序表和链表
①顺序表：⽤数组存储，插⼊和删除数据元素的时间复杂度都为O(n)
②：
  包括两个域信息，数据域和指针域，可以⽤指针来实现也可以⽤数组来模拟。
  ⽤数组模拟链表需要注意：(1)元素数组Value[]  (2)后继数组Next[]  (3)头指针Head
  查询元素时间复杂度为O(n)，插⼊和删除数据元素的时间复杂度都为O(1)
1//⽤单链表实现线性表：获得存储位置、插⼊新元素、删除元素
2 #include<iostream>
3using namespace std;
4int n, Value[2001], Next[2001], Head=0;
5int GetPos(int pos)//求链表第i个元素的存储位置
6 {
7int hd=Head;
8for(int i=1; i<=pos; i++)hd=Next[hd];
9return hd;
10 }
11
12void InsertValue(int pos, int val)//在第pos个元素前插⼊新元素val
13 {
14int p=GetPos(pos-1);
15    Value[++n]=val;
16    Next[n]=Next[p];
17    Next[p]=n;
18 }
19
20void DeleteValue(int pos)//删除第pos个元素
21 {
22int p=GetPos(pos-1);
23    Next[p]=Next[Next[p]];
24 }
25
26int main()
27 {
28int m;
29    cin>>n;
30for(int i=1; i<=n; i++)
31    {
32        cin>>Value[i];
什么是编程举个例子
33        Next[i-1]=i;
34    }
35    cin>>m;
36for(int i=1; i<=m; i++)
37    {
38int type, pos, val;
39        cin>>type>>pos;
40if(type==1)cout<<Value[GetPos(pos)]<<endl;
41if(type==2){cin>>val; InsertValue(pos,val);}
42if(type==3)DeleteValue(pos);
43    }
44 }
View Code
③循环链表
④双向链表
2.队列
  由三个部分构成：(1)顺序表q[m](2)队⾸指针front(3)队尾指针rear
  队列的基本操作（⼿写）：
队列初始化：front=rear=0
判断队列是否为空 
判断队列是否已满
进队(插⼊元素X)
出队
队列中元素个数：rear-front
  循环队列的基本操作：
“队列的初始化”与“判断队列是否为空”与队列是⼀样的
判断队列是否已满：如果（rear+1）%m==front即rear下⼀位置是front，则队列已满。这种情况下，循环队列q[m]最多只能存储m-1个元素
进队（插⼊元素x）：如果队列未满，则执⾏q[rear]=x;rear=(rear+1)%m.
出队：如果队列不为空，则返回队⾸元素q[front]同时front=(front+1)%m
队列中元素的个数：(rear-front+m)%m
  队列的STL操作：
queue<int> q;//定义⼀个存放整形数据的队列
q.push(x);// x进队
q.pop();//出队
q.size();//队列⼤⼩
q.front();//返回队⾸元素
  3.栈
  【思考】计算机如何运算5-4*3+2？
      中缀算术表达式》》后缀算术表达式
  栈的基本操作：
初始化：top=0;stack[m]只能存储m-1个元素？??
进栈：如果栈不满，则stack[++top]=item  (s.push(item))
出栈：如果栈不为空，则item=stack[top--]；即执⾏出栈操作时要保证栈中有元素（s.pop()）
  4.线性表的处理技巧--哈希表
  处理数据集合（1，75，324，43，1353，90，46）（18，75，60，43，54，90，46）
  哈希表：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)⽽直接进⾏访问的数据结构。也就是说，它通过把关键码值映射到表中⼀个位置来访问记录，以加快查的速度。
  思考：给出n个不同的正整数a[1]~a[n]，它们的值在1~1000000之间。再给定⼀个整数x，编程计算这样的数（a[i],a[j]）,1<=i<j<=n并且
a[i]+a[j]=x.样例数据：
  【输⼊】
  9
  5 12 7 10 9 1 2 3 11  13
  【输出】3
//hash<rtx>
#include<cstdio>
#include<iostream>
using namespace std;
int a[10000010],n,x,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int b;
scanf("%d",&b);
a[b]++;
}
scanf("%d",&x);
for(int i=1;i<=x/2;i++)
{
if(x-i!=i)
{
if(a[x-i]&&a[i])
{
ans+=a[x-i]*a[i];            }
}
else ans+=a[i]*(a[i]-1)/2;    }
printf("%d",ans);
}
View Code

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。