链表
计算机的存储结构有两种
- 顺序存储(以数组方式实现)
- 链式存储(以链表方式实现)
1.顺序存储
2.链式存储
3.链表中结点的关系
4.与单向链表有关操作
- 第一步:定义结构存储结点信息
struct node{
int data;
node *next;
};
- 第二步:创建头结点(head)和尾节点(tail),头结点起带头作用,尾结点用于新节点的增加。
node *head,*tail;
head=new node;
head->next=NULL;
tail=head;
- 第三步:创建多个新节点,并依次链接到链表的尾结点之后
node *p;//当前结点
for(int i=1;i<=n;i++){
p=new node;
cin>>p->data;
p->next=NULL;//指针域初始为空
tail->next=p;//将新结点p链接到链表的尾结点之后
tail=p;//更新链表的尾结点
}
- 第五步:(1)打印
p=head->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
或
p=head;
while(p->next!=NULL){
cout<<p->next->data;
p=p->next;
}
(2)查找
p=p->next;
while(p->data!=3&&p->next!=NULL){
p=p->next;
}
(3)删除
p->next=p->next->next;
(4)插入
s->next=p->next;
p->next=s;
5.循环链表
6.双向链表
7.双向链表的操作
(1)建立
struct node{
int data;
node *pre,*next;
};
(2)删除
p->pre->next=p->next;
p->next->pre=p->pre;
(3)第一种插入
(4)第二种插入
8.练习
A. 数组-删除某个数
时间：0.2 空间：32M
题目描述：
在给定的数组中删除一个数
输入格式：
多组测试，每组测试包含三行：第一行是一个整数表示数组的大小n，第二行是n个整数，第三行是要求删除的数字m。
输出格式：
删除在第二行n个整数中第一次出现数字m并删除，然后按照顺序输出剩下的数
样例输入1：
4
1 2 3 4
3
样例输出1：
1 2 4
样例输入2：
5
6 5 2 1 7
9
7
2 5 5 2 4 7 6
2
样例输出2：
6 5 2 1 7
5 5 2 4 7 6
提示：
1≤n≤100
m有可能在原数组中找不到，找不到则输出原数组
我的代码(可能不是很简洁):
#include<bits/stdc++.h>
using namespace std;
int n,x,m;
struct node{
int data;
node *next;
};
int main(){
while(cin>>n){
node *tail,*head;
head=new node;
head->next=NULL;
tail=head;
node *p;
for(int i=1;i<=n;i++){
p=new node;
cin>>p->data;
p->next=NULL;
tail->next=p;
tail=p;
}
cin>>m;
p=head;
while(p->next!=NULL){
if(p->next->data==m){
p->next=p->next->next;
break;
}
p=p->next;
}
p=head->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
return 0;
}
再来一道题
B. 双链表
时间：1s 空间：256M
题目描述：
实现一个双链表，双链表初始为空，支持5种操作：
1.在最左侧插入一个数；
2.在最右侧插入一个数；
3.将第k个插入的数删除；
4.在第k个插入的数左侧插入一个数；
5.在第k个插入的数右侧插入一个数；
现在要对该链表进行M次操作，进行完所有操作后，从左到右输出整个链表。
注意：题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，
则按照插入的时间顺序，这n个数依次为：第一个插入的数，第二个插入的数，…第n个插入的数。
输入格式：
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
1.L x，表示在链表的最左端插入数x。
2.R x，表示在链表的最右端插入数x。
3.D k，表示将第k个插入的数删除。
4.IL k x，表示在第k个插入的数左侧插入一个数。
5.IR k x，表示在第k个插入的数右侧插入一个数。
输出格式：
共一行，将整个链表从左到右输出。
数据范围：
1 ≤ M ≤ 100000
所有操作保证合法。
样例输入：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
样例输出：
8 7 7 3 2 9
我的代码(可能不是特别好):
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int l[N],r[N],e[N],idx;
void init(){
r[0]=1;
l[1]=0;
idx=2;
}
void add(int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
void del(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main(){
init();
int m,i=0;
cin>>m;
while(m--){
string op;
cin>>op;
int k,x;
if(op=="L"){
cin>>x;
add(0,x);
}else if(op=="R"){
cin>>x;
add(l[1],x);
}else if(op=="D"){
cin>>k;
del(k+1);
}else if(op=="IL"){
cin>>k>>x;
add(l[k+1],x);
}else if(op=="IR"){
cin>>k>>x;
add(k+1,x);
}
}
while(r[r[i]]!=0){
i=r[i];
cout<<e[i]<<" ";
}
return 0;
}
(我发的第一个话题，求赞)