链表！！！

链表课件

链表，是一种线性数据结构。它的优势我们可以通过与数组的对比来看一下。

数组，优势在于可以随机访问，调用非常方便。但是劣势也非常明显：

• 删除和插入会涉及到大量数据移动。
• 定义的空间必须是连续的，这就导致当需要一个较大的数组时，系统将面临无法分配出如此之大的连续空间的问题。

链表，是一种物理上分散，但逻辑上连续的数据结构。它可以将各个数据存入到内存中任意的空余空间，哪怕这些空间是分散的。但在空间与空间之间建立一道隧道，即通过指针将空间串联起来，使得我们可以有序访问。逻辑上，它是连续的。当我们需要插入和修改，只需改其指针的值即可。

单链表

输出单链表：

void print_list(){
	p=head;
	while(p!=NULL){	
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}

操作：

• 向系统申请空间：

p= new node;

• 释放空间

delete p;

• 节点赋值

p->data=x;

构建单链表

void creat_list(){
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        p=new node;//申请空间
        p->data=x;
        p->next=head;
        head=p;
  }
}

输出单链表

void print_list(){
    p=head;
    while(p!=NULL){//注意结束条件
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

双向链表

静态链表‌

在日常使用中，静态链表更为常用。对比链表每次使用都适用new去申请一个节点的空间，静态链表是通过数组预先申请一块数据域，每次使用将数据填入每个单元，然后去构建链即可。

在预先生成的数据空间，每个但愿（应为“单元”）都有两个参数，一个是数据data，一个是用数组下标来表示地址next。定义代码如下：

1 struct node{ 
2 int data; 
3 int next; 
4 }a[1000];//预先生成1000个元素点 
5 int head=-1;

list

1 #include<iostream> 
2 #include<list> 
3 using namespace std; 
4 list<int> 1st; 
5 list<int>::iterator it;//定义迭代器it 
6 int n,x; 
7 int main(){ 
8 cin>>n; 
9 for(int i=1;i<=n;i++){ 
10 1st.push_back(x); 
11 } 
12 for(it=lst.begin();it!=lst.end();it++){ 
13 //需要注意的是循环条件it!=lst.end(),不能用大于小于来判断，必须用不等于 
14 cout<<*it<<"";/注意it为指针 
15 
16 }

list功能

操作	说明	时间复杂度
Size()	返回表的元素数	O(1)
Begin()	返回指向表开头的迭代器
End()	返回指向表末尾的迭代器
Push_front(x)	在表的开头添加元素x
Push_back(x)	在表的末尾添加元素x
Pop_front()	删除表头元素
Pop_back()	删除表尾元素
Insert(p,x)	在位置p插入元素x
Erase(p)	删除位置p的元素
Clear()	删除表中所有元素