//删除某个位置的元素
void delpos(int n){
Node *p = head,*t;
//如果要删除头节点 if(n == 1){
if(head != NULL){
head = head->next; delete p;
}else{
cout<<"链表空"<<endl; }
}else{
int i;
//移动到要删除位置之前的节点
for(i = 1;i <= n - 2;i++){
p = p->next;
if(p == NULL) break;
}
if(p == NULL || p->next == NULL){
cout<<"n的值有误!"<<endl; }else{
t = p->next;
p->next = t->next;
delete t;
} }
}
//输出链表
void display(){
Node *p = head;
while(p != NULL){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl; }
int main(){
int order,x,p; cout<<"输入指令:"; while(1 == 1){
cout<<"1:追加,2:插入,3:删除值,4:删除位置,5:显示!"<<endl;
cin>>order;
if(order == 1){
cin>>x;
add(x);
display();
}else if(order == 2){
cin>>p>>x; insert(p,x); display();
}else if(order == 3){
cin>>x;
deldata(x);
display();
}else if(order == 4){
cin>>x;
delpos(x);
display();
}else if(order == 5){
display();
} }
}
注意：双向链表的基本操作；
插入的实现：
e->prev = p;
e->next = p->next;
p->next->prev=e;
p->next = e;
删除的实现：
p2->next = p2->next->next;
p3->next->prev=p2;
delete p3;
3、链式栈
Stack *p
Stack *top
入栈的实现：
p->next = top;
top = p;//修改栈顶位置
出栈的实现：
p = top;
p = p->next;
delete top;
top = p;
（1）栈的基本操作
push(int x)：入栈
pop()：出栈
display()：显示栈
（2）实现代码
#include <bits/stdc++.h>
using namespace std;
//栈元素 struct Stack{
int data;
struct Stack *next;
};
Stack *top = NULL;//栈顶指针
//入栈
void push(int x){
Stack *p = new Stack;
p->data = x;
p->next = top;
top = p;//修改栈顶位置 }
//出栈
void pop(){
Stack *p = top;
if(p != NULL){
cout<<p->data<<"出栈"<<endl; p = p->next; delete top;
top = p;//修改指针位置 }else{
cout<<"栈空"<<endl; }
}
//获得栈长度 int getlen(){
int len = 0;
Stack *p = top;
while(p != NULL){
len++;
p = p->next;
}
return len;
}
//显示栈元素 void display(){
Stack *p = top;
while(p != NULL){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
int main(){
int order,x;
cout<<"输入指令:"<<endl; while(1 == 1){
cout<<"1:入栈,2:出栈,3:显示,4:求栈长!"<<endl; cin>>order; if(order == 1){
cin>>x; push(x); display();
}else if(order == 2){
pop();
display();
}else if(order == 3){
display();
}else if(order == 4){
cout<<getlen()<<endl;
}
}
return 0; }
4、链式队列
入队的实现：
rear->next = e;
rear = e;//修改尾指针位置
出队的实现：
t = front;
front=front->next;
if(front == NULL) rear = NULL;
delete t;
（1）队列的基本操作
add(int x)：入队
del()：出队
display()：显示队
（2）实现代码
#include <bits/stdc++.h>
using namespace std;
//队列节点 struct Queue{
int data;
struct Queue *next;
};
Queue *front = NULL;//队头
Queue *rear = NULL;//队尾
//入队
void add(int value){
Queue *e = new Queue;
e->data = value;
e->next = NULL;
//队列第一个元素
if(front == NULL){
front = e;
}else{
rear->next = e;
}
rear = e; }
//出队
void del(){
Queue *t;
//如果对列有元素 if(front != NULL){
cout<<front->data<<"出队"<<endl; t = front;
front = front->next;
if(front == NULL) rear = NULL; delete t;
}else{
cout<<"队列空"<<endl;
}
}
//显示队
void display(){
Queue *p = front;
while(p != NULL){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
int main(){
int order,x;
cout<<"输入指令:"<<endl; while(1 == 1){
cout<<"1:入队,2:出队,3:显示队!"<<endl; cin>>order; if(order == 1){
cin>>x; add(x); display();
}else if(order == 2){
del(); display();
}else if(order == 3){
display(); }
}
return 0;
}
5、链表练习题
【noip2019 普及组】 6.链表不具有的特点是( )
A.插入删除不需要移动元素 B.不必事先估计存储空间
C.所需空间与线性表长度成正比 D.可随机访问任一元素
答案：D
解析：链表是通过记录每个元素的后继位置来实现数据存储,所需空间与元素个数成正比,优
点是不必事先估计存储空间、插入或删除指定位置元素的时间复杂度为 0(1)；但缺点是由
于其元素的内存地址不连续,无法进行 0(1)的随机访问。
【noip2017 普及组】13.向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，
应执行（ ）。
A.hs->next = s;
B.s->next = hs; hs = s;
C.s->next = hs->next; hs->next = s;
D.s->next = hs; hs = hs->next;
答案：B
【noip2015 普及组】 14. 线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）
A.必须连续 B.部分地址必须连续 C. 一定不连续 D.连续不连续均可
答案：D
【noip2015 提高组】13．双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，
设 p 指向链表中的一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为
（ ）。
A． p->llink = q; q->rlink = p;
p->llink->rlink = q; q->llink = p->llink;
B． q->llink = p->llink; p->llink->rlink = q;
q->rlink = p; p->llink = q->rlink;
C． q->rlink = p; p->rlink = q;
p->llink->rlink = q; q->rlink = p;
D． p->llink->rlink = q; q->rlink = p
q->llink = p->llink; p->llink = q;
答案：D