线性表L是由n个元素组成的有序序列。线性表L的长度用|L|表示；如果长度是0，那么L是一个空表<>。L[i]表示线性表L的第i个元素.

栈是一种只能在一端插入和删除项来修改的线性表；插入新项为进栈，删除项为出栈。栈为先进后出线性表。

队列是只能在队列的一端（前端）插入项以及在队列的另一项（后端）删除项来修改。队列称为先进先出线性表。

#线性表的操作

Access（L，i）：返回L[i]

Length(L），返回|L|

Concat（L1，L2）：返回连接L1和L2的结果；

MakeEmptyList（）：返回空表<>。

IsEmptyList（L）：如果|L|=0；，返回true；否则返回false。

2.1线性表的定义和特点
【类型定义：

*是n个元素的有限序列

*除了第一个元素没有直接前驱和最后一个没有直接后驱之外，其余的每个元素只有一个直接前驱和直接后驱；

（a1,a2…an）
【特征：

*有穷性：由有限个元素组成，元素个数表长度       n=0空表

（a1,a2…an），称下标i为线性表的位序
*有序性： 线性表元素之间存在严格次序关系（序偶关系）
*同一性：线性表属于同类数据元素组成，每一个元素都属于同一数据对象

eg：（A，12，b）不是线性表，不遵守同一性
2.1.2线性表抽象数据类型定义
ADT List{
//数据对象

D={ai|ai∈ElemSet,i=1,2…n, n>0}
//数据关系

R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}
//基本操作

1)InitList(&L)

将：初数化为空表

2）
…
}ADT  list
【引用在什么情况下使用】
所用到的元素，哪个元素变化（带入数据或者 ），就在此元素前加 &

【eg】

1)InitList(&L)

将：初数化为空表

//表L初始化带入值，发生变化，故早L前加&
2.1.5  示例 *有序集合的合并
有序表：LA和LB，求合并递减有序LC
基本思路：

{若ai<=bi,则ci=bi

{

{若bi<ai,则ci=ai

//谁小就先吧他赋给c
算法时间复杂度：O（ListLength(LA)）+O（ListLength(LB)）
2.2.1线性表的顺序表示和实现------顺序映像
【顺序存储】在【查找时】的时间复杂度为【O(1)】，因为它的地址是连续的，只要知道首元素的地址，根据下标可以很快找到指定位置的元素

【插入和删除】操作由于可能要在插入前或删除后对元素进行移动，所以顺序存储的时间复杂度为【O(n)】。
1）初始化操作

思想：构造一个空表

设置表起始位置、表长及可用空间
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef struct
{
ElemType *elem;   //定义个地址变量，使其后面能指向线性表占用的数组空间
int length;  // 线性表的长度
int listsize;  // 当前分配的存储容量
}SqList;

//初始化操作
Status InitList_Sq(SqList &L)  //初始化
{ //构造一个空表
L.elem=(ElemType)malloc(LIST_INIT_SIZE*size of(ElemType));
if(!L.elem)  exit(OVERFLOW);  //存储分配失败
L.length=0;   //空表长度为0
L.listsize=LIST_INIT_SIZE;  //初始存储容量
return OK;

}


2.2.3顺序表的插入
2）顺序插入操作
目的：在线性表L第i个元素前插入一个元素e
【基本思想

1）判断i是否在允许范围

2）存储空间是否已满

3）将第i个元素和后面的所有元素向后移动

4）新元素写在空出的第i个位置

5）线性表长度加1
【注意】

长度为n的顺序表第i个位置插入移动n-i+1个元素

Status ListInsert_Sq(SqList&L,int i,ElemType e){

if(i<1||i>1.lenth+1)
return ERROR;   //插入位置不合法

if(L.length>=L.listsize)
{
newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType)); 
    If(!newbase) exit（OVERFLOW）;// 当前存储空间已满
 L.elem=newbase;              //新基址
 L.listsize+=LISTINCREMENT;  // 增加存储容量 
}     //判断空间足够

q=&(L.elem[i-1]);   //q指向插入位置

for(p=&(L.elem[L.elem-1]);p>-q;--q)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}


2.2.4顺序表的删除和插入
【基本思路

1）判断i是否在允许范围

2）将线性表的第i个元素给e

3）将第i个元素和后面的所有元素向前移动一个位置

4）线性表长度减1

Status ListDelete_Sq(SqList&L,int i,ElemType e){

//删除第i个元素并用e返回值

if(i<1||i>1.lenth+1)
return ERROR;   //删除位置不合法

p=&(L.elem[i-1]);   //q指向插入位置
e=*p;
q=L.elem+L.length-1; //表尾元素位置
for(++p;p<=q;++p)
*(p-1)=*p;    //p-1指向p

--L.length;
return OK;
}


【图】：平均移动次数
【查找操作】11:42
int LocateElem_Sq(SqList,ElseType e)
{
//查询第一个 满足条件的元素，若存在，返回位序，否则返回0；
int i;
i=1;
while (i<=L.length&&L.elem[i-1]!=e)
++i;
if(i<=L.length)
return i;
else return 0;
}// locateElem_Sq


i<=L.length&&L.elem[i-1]!=e
i>L.length


【顺序结构优缺点14:15

【优点：

逻辑相邻，物理相邻

可随机存取一元素

存储空间使用紧凑

【缺点：

插入，删除需要移动大量元素

预先分配空间需按最大空间分配，利用不充分表难以扩充
【】线性表的合并问题

【图：例1】

基本思路：

1）初始化Lc为空表

2）分别从La和Lb取得当前元素ai和bi

3)若ai<bj，则将ai插入到Lc中，否则

bj插入到Lc中
代码：

Viod MergeList(SqList La.SqList ,lb.SqList &Lc)
{
Pa=La.elem;
Pb=Lb.elem;
Lc.listsize=Lc.length=La.elem+Lb.elem;
Pc=Lc.elem=(ElemType*)malloc(Lc.listsize* sizeof(ElemType));
if(!Lc.elem)
exit(overflow);
Pa_last=La.elem+La.length-1;
Pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last)
{
if(*pa<= *pb)
*pc++= *pa++;
else
*pc++= *pb++;
}
while(pa<=pa_last)
*pc++= *pa++;
while (pb<=pb_last)
*pc++= *pb++;
}


2.3线性表的链式表现与实现
2.3.1.1单链表

【特点：

*用一组任意的存储单元存储线性表的数据元素

*利用指针实现用不同相邻的存储单元存放逻辑上相邻的元素

*每个元素ai，除存储本身信息外，还存储其直接后继的元素（后一个元素的地址）

*结点：数据元素ai的存储映像

{数据域：数据元素本身

指针域：指示直接后继的存储位置
【头指针、头结点、第一个元素结点

*头指针：以线性表的第一个数据元素a1的存数地址作为线性表的地址，称为线性表的头指针
*头结点：为了操作方便，在第一个结点前虚加一个“头结点”，指向头结点的指针为链表的头指针（相当于第一个呀元素的结点）
代码：
typedef struct LNode{
  ElemType data;
  struct LNode*next;
}LNode,*LinkList    //LNode是结构体的别名，LinkList为指针变量
//相当于：typedef LNode *LinkList

2.3.1.2 单链表存储结构实现
格式： data | next
【p指向数据域

(*p).data=10;

或：p->data=10;    //表示p指向结点的数据域
（*p）.next=10

或 p->next       //表示p指向结点的指针域
*生成一个LNode型新结点：

p=(LinkList)malloc(sizeof(LNode));
*系统回收p的结点

free（p）
*单链表特点：

1）是它是一种动态结构，整个存储空间为多个链表共用

2）不需预先分配空间

3）指针占用额外存储空间

4）不能随机存取，查找速度慢
【基本操作：

1）GetElem（L,i,&e）  //第i个元素用e带回结果

2）ListInsert(&L,i,e)    //插入

3）ListDelete(&L,i,e)  //删除

4）CreateList_L（&L,n） //创建线性表
2.3.1.3单链表的查找
【操作：

1）GetElem（L,i,&e）
【基本思想：

1）令p为指针变量，首先指向第一个结点，变量 j为计数器

2）依次向后查找，循环结束条件：p为空或j>=i；

3）找到用e返回第i个值
【代码：

Status GetElem_L(LinkList L,int i,ElemType&e)
{  //L是链表的头指针（对带头结点的链表），以e返回dii个值
p=L->next;
j=1;

while (p&&j<i)
{
  p=p->next;  ++j;
 if(!p||j>i)
  return ERROR;

e=p->data;  //取第i个值
return OK;
}



2.3.1.4单链表的插入操作
2）ListInsert(&L,i,e)

在线性表第i个元素之前插入一个元素e，元素e存在结点s中
【思路：在第i项的前加一个接结点，i-1项的地址域和e的数据域连接

int ListInsert_L(LinkList&L,int i,int e)
{
LNode*p,*s;int j;   //或：LinkList p,s;    等同
p=L;j=0; //计数器
while(p&&j<i-1)
{p=p->next;++j;}
if(!p||j>i-1)
return ERROR;
s=LinkList()malloc(sizeof(LNode)); //新结点
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}

2.3.1.5 单链表的删除
【思路：删除第i个元素，并保存到元素e中
【代码：
int ListDelete_L(LinkList&L,int i,ElemType&e)
{
LNode*p,*q;int j;
p=L;j=0;
while(p->next||j<i-1)       //？？？？我觉得应该是(!p||j>i-1)
{p=p->next;++j}
if(p->next==NULL||j>i-1)
return ERROR;    //删除位置不合理
q=p->next;  //q指向被删除结点
p->next=q->next;  //
e=q->data;   //取出第i个结点的数据域
free(q);    // 释放dii个结点的内存
return OK;
}   



2.3.1.6单链表的建立
【头插法建立有头结点的单链表

可理解为:每次插一个新的头

【图】

L=(Linklist)malloc(sizeof(LNode))  //sizeof后面跟数据类型（LNode）

L->next=NULL
【图】

p=(LinkList)malloc(sizeof(LNode))

scanf("%f",&(p->data));  //
【整个代码：
void CreateList_L(LinkList &L,int n)
{
LNode*p;int i;
L=(LinkList)malloc(sizeof(Lnode));
L->next=NULL;
for(i=n;i>0;--i)
{ p=(Listlink)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=L->next;
l->next=p     //这里的=都可以理解为“给了，到，指向”
}
}




2.3.1.7有序单链表的合并
例：线性表LA和LB中数据元素按照废帝剑有序排列，将LA和LB合并为一个新的LC，且LC中的数据元素仍按照递减有序排列


【代码：

void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)
{// 归并La和Lb得到Lc，Lc也按照降序排列
LinkList pa,pb,pc;
pa=La->next;pb=Lb->next;
Lc=pc=La;  //用La的头结点作为Lc的头结点
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa; pc=pa;pa=pa->next;
}
else
{
pc->next=pb;pc=pb;pb=pb->next;
}
pc->next=pa?pa:pb;  //若a不为空则指向pa，否则指向pb
free(Lb);
}


2.3.1.8静态链表
定义：用数组描述的链表叫静态链表
目的：为在不设指针类型的高级程序语言中使用链表结构
存储结构：
#define MAXSIZE 100 //静态链表最大长度
typedef struct{
ElemType data;
int cur;  //游标，代替指针的结点，表示数组中的位置
}component,SLinkList[MAXSIZE]


2.3.2循环链表
循环链表是单链表的变形
循环链表最后一个结点link指针部位NULL，而是指向表的前端
为简化操作，在循环链表往往插入头结点
特点：

只要知道表中一结点的地址，就可以搜索到所有其他结点的地址
操作的时间复杂度：

表尾插入，时间复杂度：O(1)

表尾删除：O(n)

表头插入，同表尾

表头删除：O(1)
2.3.3双向链表  插入、删除
指在前驱和后驱方向都能游历（遍历）的线性链表
双向链表的每个结点有两个指针域

【结构】：prior  data  next
双链表通常采用带头结点的循环链表形式


可理解为首位相接的数据“圈”，每个结点都可以向前或向后走
【结点指向】


【插入操作】：
1.分配空间

2.断开与连接


【操作算法

status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{if(!p=GetElem_Dul(L,i))  
return ERROR;  //相当于嵌套第i个结点的指针

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))
return ERROR   //空间分配失败
s-data=e;      //将数据放入新结点的数据图
s-prior=p-prior;  //将p的前驱结点指针放入新结点的前向指针域
s-next=p;      //将p放入新结点的反向指针域
p-prior-next=s;   //修改p的前驱结点的反向指针
p-prior=s;    // 修改p的前驱指针
return OK;
}   ListInsert_DuL

【删除操作】
1.p指向目标结点

2.将目标结点的前一个结点与后一个连接（跳过中间那个）

3释放内存


【操作算法】

status ListDelete_Dul(DuLinkList &L,int i,ElemType &e)

{ 删除头结点的双向循环链表L中第i个元素返回，1=i=表长

if（!p=GetElem_Dul(L,i)）

return ERROR;   查找第i个指针

e=p-data;      将p指向结点数据域中的值取出

p-prior-next=p-next;    p前一个结点的后驱指向p的后一个结点

p-next-prior=p-prior;   后指向前

free§;    释放p

return OK;
}  ListDelete_DuL
【  算法评价：T(n)=O(n)  】
！注意：如何选择合适的存储结构

链表只能顺序存取，在单链表的最后一个元素后插入元素，需遍历整个链表

频繁插入删除用链式存储

偶尔              用顺序存储
2.4一元多项式的表示及相加

n阶多项式的表示：

n阶多项式有n+1项

指数按升幂排序

【 优点：

多项式的项数可以动态增长，不存在存储溢出的问题
插入，删除方便，不移动元素

【表示：

有两个数据域，一个地址域


【一元多项式的建立算法：

void polycreate(Polylist &head)
{
polylist rear,s;  int c,e;
head=(Polynode *)malloc(sizeof(POlynode));
rear=head;      //尾插法
scanf("%d,%d",&c,&e);
while(c!=0)
  { s=(Polynode *)malloc(sizeof(Polynode));
    s->coef=c; s->exp=e;
    rear->next=s;  rear=s;
    scanf("%d,%d",&c,&e);
    rear->next=NULL;
  }
}



【一元多项式相加：


扫描两个多项式

{若当前被检测项指数相等，系数相加。  和不为0，则结果加到结果多项式
{若检查指数不等，将指数小的加到结果多项式，然后往后移


若一个多项式检测完，将另一个多项式剩余全部复制到结果多项式


【设计思想：


算法：
void polyadd(Polylist polya,Polylist polyb)
{
Polynode *pa,*pb,*pc,*r;
int sum;
pa=polya->next;
pb=polyb->next;
pc=polyb;   //pre指向和多项式的尾结点

while(pa!=NULL&&pb!=NULL)
{
if(pa->exp<pb->exp)
  {pa->next=pa; pc=pa;pa=pa->next;}    //【1.】 pa指数小于pb指数，把pa给了pc
else if(pa->exp==pb->exp)
 {
   sum=pa->coef+pb->cofe;
   if(sum!=0)                                            //【3.】指数相等，但系数sum不是0
   {
    pa->cofe=sum; pc->next=pa;
    pc=pa; pa=pa->next;
    r=pb; pb=pb->next ;  free(r);
   }
   else                                                    //【4.】指数相等，系数sum为0
    {r=pa; pa=pa->next;free(r);
     r=pb;pb=pb->next;free(r);
    }
 }
  else
  {pc->next=pb; pc=pb;pb=pb->next;}    // 【2.】pb指数小于pa指数，把pb给了pc
  

if(pa!=NULL)
  pc->next=pa;
else pc->next=pb;
}

} 

Description:

线性表是n个元素的有序集合（n≥0），n是线性表中元素的个数，称为线性表的长度。可以用一组地址连续的存储单元依次存储线性表中元素，采用这种存储方式的线性表称为顺序表。

请在顺序表上实现运算，实现顺序表的逆置，删除表中所有元素值等于x的元素。

Input:

三组数据，顺序表元素类型分别为整型、字符型和实型。

每一组第一行给出元素数目n（0<n≤1000），第二行给出元素数值，第三行给出待删除的元素。

Output:

三组数据，每一组第一行给出逆置后的顺序表元素，第二行是在此基础上删除指定元素后的顺序表元素，每一个输出元素后均有一个空格，如果元素全部被删除，那么输出一个空行。

Sample Input:

8
1 2 3 7 5 6 7 8 
7
3
a c m
h
4
1.2 3.4 5.6 7.8
1.2

Sample Output:

8 7 6 5 7 3 2 1 
8 6 5 3 2 1 
m c a 
m c a 
7.8 5.6 3.4 1.2 
7.8 5.6 3.4 



Note:

该题属于南京邮电大学《数据结构A》实验一中的内容，验证的是课本代码，请慎重解答。

2014.12.30 输出格式做了必要说明。

本题由旧版NOJ导入，来源：南京邮电大学《数据结构A》课程实验

 

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <stdio.h>
#include <iomanip>
#include <math.h>   
#include <list>
#include <stack>
#include <string.h>
using namespace std;

int main(void)
{
	int n;
	cin >> n;
	vector<int> nums1(n);
	for(int i = 0; i < nums1.size(); i++)
	{
		cin >> nums1[i];
	}
	int target;
	cin >> target;
	reverse(nums1.begin(), nums1.end());
	for(int i = 0; i < nums1.size(); i++)
	{
		cout << nums1[i] << " ";
	}

	cout << endl;
	for(int i = 0; i < nums1.size(); i++)
	{
		if(nums1[i] != target)
			cout << nums1[i] << " ";
	}
	cout << endl;

	cin >> n;
	vector<char> nums2(n);
	for(int i = 0; i < nums2.size(); i++)
	{
		cin >> nums2[i];
	}
	char target1;
	cin >> target1;
	reverse(nums2.begin(), nums2.end());
	for(int i = 0; i < nums2.size(); i++)
	{
		cout << nums2[i] << " ";
	}

	cout << endl;
	for(int i = 0; i < nums2.size(); i++)
	{
		if(nums2[i] != target1)
			cout << nums2[i] << " ";
	}
	cout << endl;
	//cout << " helo" <<endl;
	cin >> n;
	//cout << "n=" << n <<endl;
	vector<double> nums3(n);
	for(int i = 0; i < nums3.size(); i++)
	{
		cin >> nums3[i];
	}
	double target2;
	cin >> target2;
	reverse(nums3.begin(), nums3.end());
	for(int i = 0; i < nums3.size(); i++)
	{
		cout << nums3[i] << " ";
	}

	cout << endl;
	for(int i = 0; i < nums3.size(); i++)
	{
		if(nums3[i] != target2)
			cout << nums3[i] << " ";
	}
	cout << endl;
	return 0;

}

 

线性表是由n(n>)个相同数据类型数据结构(节点)a1，a2，an组成的有序序列。

n：数据元素的个数，也称表的长度。

空表:n=0,计为（）

线性表有两种储存方式，一种是顺序表的形式。一种是链表的形式。

顺序表最大的特点是按元素顺序存放，地址连续

线性表的特征：

在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个后继a2,
有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1，
其余的内部结点ai（2<i<n-1）都有且仅有一个直接前趋ai-1和一个直接后续ai+1，

线性表的基本运算：
求表长—求线性表中元素个数
遍历—从左到右（或从右到左）扫描（或读取）表中的各元素
按编号查找—找出表中第i个元素
按特征查找—按某个特定值查找线性表
插入—在第i个位置上（即原第i个元素前）插入一新元素
删除-删除原表中的第i个元素
排序—按元素某特征值的递增（或递减）排序，重排表中各元素

插入方法图：



顺序表的删除一定要备份，我们删除后的元素要挨个往前移一格，这样才能保证地址连续存放的特点


单链表的结构

单链表中构成链表的节点只有一个指向直接后续节点的指针域。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。

数据域：可以存放存储元素的数据数值

指针域：他指向的是直接后续的存放地址。

单链表跟顺序表不同的是他不需要地址连续的单元来存储我们的线性表

单链表的插入：单链表的插入就是在我们的单链表这个结构往里面插入一个节点，实际元素要++


单链表的删除：删除掉就不会有这个数据了，一定要备份，

删除掉的数据不会在链表中了，我们整个数据要减一


链表不是地址连续的空间，他的插入和删除不需要移动元素，它看到内存有空余地址就可以毫无顾忌地挤进去，所以我们叫它”调皮的链表“