线性表就是由n（n>=0）个相同类型的数据元素组成的有限序列，他是最基本，最常用的一种线性结构。理解为一条线，有唯一的开始与结束。除了第一个元素每个元素都有唯一的直接前驱；除了最后一个元素，每个元素都有唯一的直接后继。
线性表有两种存储方式：顺序存储和链式存储。采用顺序存储的被称为顺序表。采用链式存储的被称为链表。
一：顺序表
顺序表就是说相邻的数据在计算机内部存储位置也是相邻的。顺序存储方式中元素存储是连续的，中间不允许有空，可以快速定位某个元素，所以插入删除时要移动大量元素。根据空间分配方法的不同，顺序表可分为静态存储和动态分配两种。
静态分配：
就是指定长数组需要预先分配一段固定大小的连续空间，但易造成的问题就是操作过程中超出预支空间，产生溢出。
#define Maxsize 100typedef struct{Elem_Type date[Maxsize];int length;}Sqlist;
动态分配
为解决可能产生的溢出问题，我们用动态分配方法，也就是用基地址（数组首地址）来记录，一旦溢出就开辟更大空间来替换掉原来的存储空间，从而达到扩容的目的。
#define Maxsize 100
typedef struct{
Elem_Type *elem;
int length;
}Sqlist;
1.插入
想要在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始，后移一位，直到空出i位置。
算法步骤：
（1）判断插入位置，位置必须大于1小于最后一位加一。
（2）：判断存储空间是否已满。
（3）：依次后移
（4）：插入新元素
（5）：表长加一，插入完成后返回TRUE。
bool ListInsert(sqlist &l,int i,int e)
{
if(i<1||i>L.length+1)
return false;
if(L.length == Maxsize)
return false;
for(int j = L.length-1;j>=i-1;j--)
{
L.elem[j+1]=L.elem[j];
}
L.elem[i-1]=e;
L.length++;
return true;
}
2.删除
在顺序表中删除第i个元素时，需将该变量暂存到变量e中，之后从i+1一个个前移，直至第n个元素。
算法步骤：
（1）：判断插入位置i是否合法（1<=i<=L.length）
（2）：将欲删除元素保存在e中。
（3）： 将i+1至n的元素依次前移1位
（4）：表长-1，删除完毕返回TRUE
bool ListDelete(sqlist &L,int i,int &e)
{
if(i<1||i>L.length-1)
return false;
e = L.elem[i-1];
for(int j=i;j<=L.length-1;j++)
{
L.elem[j-1]=L.elem[j];
}
L.length--;
return true;
}
二：单链表
小程序：
为了方便理解，此处以一个小程序示例，如出现乱码请将编码设置为GBK，以此来理解单链表中功能的实现。本次我们将以讲解单向链表为主，其他链表就是稍加修改的单向链表。
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct Lnode{
int data; //结点的数据域
struct Lnode *next; //结点的指针域
}Lnode,*LinkList; //LinkList为指向结构体LNode的指针类型
bool InitList_L(LinkList &L){//构造一个空的单链表L
L=new Lnode; //生成新结点作为头结点，用头指针L指向头结点
if(!L)
return false; //生成结点失败
L->next=NULL; //头结点的指针域置空
return true;
}
void CreateList_H(LinkList &L){//前插法创建单链表
//输入n个元素的值，建立到头结点的单链表L
int n;
LinkList s; //定义一个指针变量
L=new Lnode;
L->next=NULL; //先建立一个带头结点的空链表
cout<<"请输入元素个数n："<<endl;
cin>>n;
cout<<"请依次输入n个元素："<<endl;
cout<<"前插法创建单链表..."<<endl;
while(n--){
s=new Lnode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=L->next;
L->next=s; //将新结点s插入到头结点之后
}
}
void CreateList_R(LinkList &L){//尾插法创建单链表
//输入n个元素的值，建立带表头结点的单链表L
int n;
LinkList s, r;
L=new Lnode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
cout<<"请输入元素个数n："<<endl;
cin>>n;
cout<<"请依次输入n个元素："<<endl;
cout<<"尾插法创建单链表..."<<endl;
while(n--){
s=new Lnode;//生成新结点
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=NULL;
r->next=s;//将新结点s插入尾结点*r之后
r=s;//r指向新的尾结点s
}
}
bool GetElem_L(LinkList L, int i, int &e){//单链表的取值
//在带头结点的单链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int j;
LinkList p;
p=L->next;//p指向第一个结点，
j=1; //j为计数器
while(j<i&&p){ //顺链域向后扫描，直到p指向第i个元素或p为空
p=p->next; //p指向下一个结点
j++; //计数器j相应加1
}
if(!p||j>i)
return false; //i值不合法i＞n或i<=0
e=p->data; //取第i个结点的数据域
return true;
}
bool LocateElem_L(LinkList L,int e){ //按值查找
//在带头结点的单链表L中查找值为e的元素
LinkList p;
p=L->next;
while(p&&p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next; //p指向下一个结点
if(!p)
return false; //查找失败p为NULL
return true;
}
bool ListInsert_L(LinkList &L,int i,int e){//单链表的插入
//在带头结点的单链表L中第i个位置插入值为e的新结点
int j;
LinkList p,s;
p=L;
j=0;
while(p&&j<i-1){ //查找第i-1个结点，p指向该结点
p=p->next;
j++;
}
if(!p||j>i-1)//i＞n+1或者i＜1
return false;
s=new Lnode; //生成新结点
s->data=e; //将新结点的数据域置为e
s->next=p->next; //将新结点的指针域指向结点ai
p->next=s; //将结点p的指针域指向结点s
return true;
}
bool ListDelete_L(LinkList &L, int i){ //单链表的删除
//在带头结点的单链表L中，删除第i个位置
LinkList p, q;
int j;
p=L;
j=0;
while((p->next)&&(j<i-1)){ //查找第i-1个结点，p指向该结点
p=p->next;
j++;
}
if(!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
return false;
q=p->next; //临时保存被删结点的地址以备释放空间
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放被删除结点的空间
return true;
}
void Listprint_L(LinkList L){ //单链表的输出
LinkList p;
p=L->next;
while(p){
cout<<p->data<<"\t";
p=p->next;
}
cout<<endl;
}
int main(){
int i,x,e,choose;
LinkList L;
cout<<"1. 初始化\n";
cout<<"2. 创建单链表（前插法）\n";
cout<<"3. 创建单链表（尾插法）\n";
cout<<"4. 取值\n";
cout<<"5. 查找\n";
cout<<"6. 插入\n";
cout<<"7. 删除\n";
cout<<"8. 输出\n";
cout<<"0. 退出\n";
choose=-1;
while(choose!=0){
cout<<"请输入数字选择:";
cin>>choose;
switch(choose){
case 1: //初始化一个空的单链表
if(InitList_L(L))
cout<<"初始化一个空的单链表!\n";
break;
case 2: //创建单链表（前插法）
CreateList_H(L);
cout<<"前插法创建单链表输出结果:\n";
Listprint_L(L);
break;
case 3: //创建单链表（尾插法）
CreateList_R(L);
cout<<"尾插法创建单链表输出结果:\n";
Listprint_L(L);
break;
case 4: //单链表的按序号取值
cout<<"请输入一个位置i用来取值:";
cin>>i;
if (GetElem_L(L,i,e)){
cout<<"查找成功\n";
cout<<"第"<<i<<"个元素是："<<e<<endl;
}
else
cout<<"查找失败\n\n";
break;
case 5: //单链表的按值查找
cout<<"请输入所要查找元素x:";
cin>>x;
if(LocateElem_L(L,x))
cout<<"查找成功\n";
else
cout<<"查找失败! "<<endl;
break;
case 6: //单链表的插入
cout<<"请输入插入的位置和元素（用空格隔开）:";
cin>>i;
cin>>x;
if(ListInsert_L(L,i,x))
cout<<"插入成功.\n\n";
else
cout<<"插入失败!\n\n";
break;
case 7: //单链表的删除
cout<<"请输入所要删除的元素位置i:";
cin>>i;
if(ListDelete_L(L,i))
cout<<"删除成功!\n";
else
cout<<"删除失败!\n";
break;
case 8: //单链表的输出
cout<<"当前单链表的数据元素分别为:\n";
Listprint_L(L);
cout<<endl;
break;
}
}
system("pause");
return 0;
}
链表就是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻。为表示相邻关系，需要给每个元素都附加一个指针域，指向下一个元素的存储位置。
每个节点都包含两个域：数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。链表中的每个指针都指向下一个节点，也朝向同一方向，这样的链表被称为单向链表或者单链表。
typedef struct Lnode{
Elem Type data;
struct Lnode *next;
}Lnode,*Linklist;
定义了上面的节点结构体之后，就可以通过它将若干节点连接在一起，形成一个单链表了。
显然，不论这个链表多长，只要找到他的头，就可以拉起整个单链表。而有时为了方便操作，还会给单链表增加一个不存放数据的头结点（也可以用来存储下表长），给单链表加上头结点，可以理解成给一串钥匙加了个钥匙扣。
随机存取与顺序存取：
若想在顺序表中找第i个元素，则可以立即通过L.elem[i-1]找到，想找哪个就找那个，这种存取被称作随机存取。但放到链表中，是无法这样操作的，只能从头一个个读取，直至找到想要的元素。这种被称作顺序存取。
1.插入
在第i个节点之前插入元素e，就相当于在i-1节点后插入，则插入操作如视频图解。
2.删除
删除某个节点，实际上就是跳过去，图解如视频。
三：双向链表
在单链表中，每个元素附加一个指针域，而双向链表就是添加两个指针域，一个指向前驱节点，一个指向后继节点。其他同单向链表。
四：循环链表（环）
单向链表存在问题，也就是从当前节点开始，无法访问前面的节点。所谓循环链表就是最后一个节点后继指向头结点。
五：静态链表
链表的另一种表示方法就是，可以用一个数组存储数据，另一个数组记录当前数据后继的下标。
例如用一个静态链表来表示一个动态单向循环链表，就可以先把数据存储在一维数组data【】中，用后继数组right【】记录每个元素的后继下标。
练习：
uva101：http://web.kshs.kh.edu.tw/academy/luckycat/homework/q101.htm
#include<bits/stdc++.h>
using namespace std;
vector<int>block[30];
int n;
void init()
{
cin>>n;
for(int i=0;i<n;i++)
block[i].push_back(i);
}
void loc(int x,int &p,int &h)//找位置
{
for(int i=0;i<n;i++)
for(int j=0;j<block[i].size();j++)
{
if(block[i][j]==x)
{
p=i;
h=j;
}
}
}
void goback(int p,int h)//p堆>h的所有块归位
{
for(int i=h+1;i<block[p].size();i++)
{
int k=block[p][i];
block[k].push_back(k);
}
block[p].resize(h+1);//重置大小
}
void moveall(int p,int h,int q)//p堆>=h的所有块移动到q之上
{
for(int i=h;i<block[p].size();i++)
{
int k=block[p][i];
block[q].push_back(k);
}
block[p].resize(h);//重置大小
}
void solve()
{
int a,b;
string s1,s2;
while(cin>>s1)
{
if(s1=="quit")
break;
cin>>a>>s2>>b;
int ap=0,ah=0,bp=0,bh=0;
loc(a,ap,ah);
loc(b,bp,bh);
if(ap==bp)
continue;
if(s1=="move")//a归位
goback(ap,ah);
if(s2=="onto")//b归位
goback(bp,bh);
moveall(ap,ah,bp);
}
}
void print()
{
for(int i=0;i<n;i++)
{
cout<<i<<":";
for(int j=0;j<block[i].size();j++)
cout<<" "<<block[i][j];
cout<<endl;
}
}
int main()
{
init();
solve();
print();
return 0;
}
uva11988：http://web.kshs.kh.edu.tw/academy/luckycat/homework/q11988.htm
#include<bits/stdc++.h>
using namespace std;
void solve(string s)
{
int len=s.length();
list<char> text;
list<char>::iterator it=text.begin();
for(int i=0;i<len;i++)
{
if(s[i]=='[')
it=text.begin();
else if(s[i]==']')
it=text.end();
else
{
it=text.insert(it,s[i]);
it++;
}
}
for(it=text.begin();it!=text.end();it++)
cout<<*it;
s.clear();
cout<<endl;
}
int main()
{
string s;
while(cin>>s)
solve(s);
return 0;
}
uva12657：https://vjudge.net/problem/UVA-12657
#include<bits/stdc++.h>
using namespace std;
int r[100000+5],l[100000+5];
void init(int n)
{
for(int i=1;i<=n;i++)
{
l[i]=i-1;
r[i]=(i+1)%(n+1);
}
r[0]=1;
l[0]=n;
}
void link(int L,int R)
{
r[L]=R;
l[R]=L;
}
int main()
{
int n,m,a,x,y,k=0;
bool flag;
while(cin>>n>>m)
{
flag=false;
init(n);
for(int i=0;i<m;i++)
{
cin>>a;
if(a==4)
flag=!flag;//翻转
else
{
cin>>x>>y;
if(a==3&&r[y]==x) swap(x,y);
if(a!=3&&flag)
a=3-a;
if(a==1&&x==l[y])
continue;
if(a==2&&x==r[y])
continue;
int Lx=l[x],Rx=r[x],Ly=l[y],Ry=r[y];
if(a==1)
{
link(Lx,Rx);//删除x
link(Ly,x);
link(x,y);//x插入y左
}
else if(a==2)
{
link(Lx,Rx);//删除x
link(y,x);
link(x,Ry);//x插入y右
}
else if(a==3)
{
if(r[x]==y)
{
link(Lx,y);
link(y,x);
link(x,Ry);
}
else
{
link(Lx,y);//交换位置
link(y,Rx);
link(Ly,x);
link(x,Ry);
}
}
}
}
int t=0;
long long sum=0;
for(int i=1;i<=n;i++)
{
t=r[t];
if(i%2==1)
sum+=t;
}
if(flag&&n%2==0)
sum=(long long)n*(n+1)/2-sum;
cout<<"Case "<<++k<<": "<<sum<<endl;
}
return 0;
}
若有收获，就点个赞吧
0 人点赞
