链表与列表
dream_contry · · 个人记录
链表
1.概念
(1)劣势
访问麻烦
(2)优势
插入与删除简单
链接两个链表简单
不固定长度
占内存小
2.定义
struct Node{
int x,y;
Node* next;
};
Node* p=(Node*)malloc(sizeof(Node));
(*p).next=NULL;
p->next=NULL;//p是指向一个结构体的指针
p->x=0;
p->y=0;3.函数
malloc()
malloc(4)//申请一段4字节的空间
//返回申请到的空间的指针
sizeof(类型)//计算某个结构占多少字节
free(指针)//释放指针所指的内存4.操作
(1)遍历
for(Node* p=head;p!=NULL;p=p->next){
cout<<p->x<<‘ ’<<p->y<<endl;
}(2)插入节点
void insert_node(Node* p,int x;int y){
q->next=new_node(x,y);
q->next=p->next;
p->next=q;
}(3)删除
void insert_node(Node* p,int x;int y){
Node* q=p->next;
p->next=p->next->next;
free(q);
}(4)反转链表
Node* reverse(Node* head){
Node* prev=NULL;
Node* next;
for(Node p=head;p=NULL;p=next){
next=p->next;
p>next=prev;
q->Prev=p;
}
return prev;
}列表
list
(1)定义
list<类型> 名字;
迭代器
interator 指针
(2)特点
双向链表
(3)函数
```cpp
a.begin()//返回列表a最前端的迭代器
a.end()//返回列表a的最后的迭代器的后面
a.rbegin()//返回一个反向的最前端的迭代器
a.rend()//返回反向末端迭代器
a.push_back(x)//往链表最后新增元素
a.push_front(x)//往链表最前端新增元素
a.pop_back(x)//往链表最后删除元素
a.pop_front(x)//往链表最前端删除元素
a.size()//返回a的大小
a.empty()//判断 a是否为空
a.insert(迭代器,要插入的元素)//把要插入的元素插入到迭代器所指的地方
a.erase(迭代器)//删除迭代器所指的元素(4)操作
1.遍历
for(list<int>::interator it=a.begin();it!=a.end();it++){
cout<<*it<<endl;
}