Processing math: 6%
NOIP学习小站
西安交通大学附属中学航天学校

线性表——栈

tangyj626阅读(515)

线性表是最简单、最基本的一种数据结构,线性表可以描述为若干具有相同数据类型的数据按照线性“串起来”的结构,线性表中的每个元素都有前一个元素(前驱)和后一个元素(后继)。线性表可以分为栈、队列、链表等。

一、栈的定义

先来看一个例子:小张是流水线上的检验工人,他的工作是将传送带送来堆叠在一起的薄片零件从上到下依次取出检验。在他检验的过程中,还有大量的零件源源不断的传送过来,新传送来的零件堆在最上面。在工作的前半段时间,传送带传送零件的速度会快于小张的检验速度。

仔细分析我们会发现,每次新来的零件放在最上面,每次拿走检验的也是最上面的零件,但是由于检验速度慢一些,所以会造成零件逐渐积压。在这个过程中,每次检验的都是最新传送来的零件。这个例子表现出来的数据结构就是栈。是一种后进先出(LIFO——last in first out)的线性表,其特点是只允许在线性表的一端(称为栈顶)插入元素(称为入栈)和删除元素(称为出栈)。

二、栈的实现

可以使用“数组+函数”来模拟栈和栈的一些操作:入栈、出栈、取栈顶元素、判断栈是否为空等:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int MAX = 10000;
int stack[MAX];
int top = -1; //栈顶“指针”,也就是栈顶对应数组的下标
void push(int n){ //入栈(没有考虑数组已经被存满时不能入栈的情况)
stack[++top] = n;
}
void pop(){ //出栈(没有考虑栈为空时不能出栈的情况)
top--;
}
int getop(){ //取栈顶元素(没有考虑栈为空时不能取栈顶元素的情况)
return stack[top];
}
bool empty(){ //判断栈是否为空
return top==-1;
}
void print(){ //依次输出从栈底到栈顶的元素(测试需要)
for(int i=0;i<=top;i++) cout<<stack[i]<<" ";
cout<<endl;
}
int main()
{
for(int i=1;i<=5;i++) push(i);
print();
cout<<getop()<<endl;
pop();
print();
push(6);push(7);
print();
while(!empty()){ //全部出栈
cout<<getop()<<endl;
pop();
}
return 0;
}
#include<iostream> using namespace std; const int MAX = 10000; int stack[MAX]; int top = -1; //栈顶“指针”,也就是栈顶对应数组的下标 void push(int n){ //入栈(没有考虑数组已经被存满时不能入栈的情况) stack[++top] = n; } void pop(){ //出栈(没有考虑栈为空时不能出栈的情况) top--; } int getop(){ //取栈顶元素(没有考虑栈为空时不能取栈顶元素的情况) return stack[top]; } bool empty(){ //判断栈是否为空 return top==-1; } void print(){ //依次输出从栈底到栈顶的元素(测试需要) for(int i=0;i<=top;i++) cout<<stack[i]<<" "; cout<<endl; } int main() { for(int i=1;i<=5;i++) push(i); print(); cout<<getop()<<endl; pop(); print(); push(6);push(7); print(); while(!empty()){ //全部出栈 cout<<getop()<<endl; pop(); } return 0; }
#include<iostream>
using namespace std;
const int MAX = 10000;
int stack[MAX];
int top = -1;        //栈顶“指针”,也就是栈顶对应数组的下标 
void push(int n){    //入栈(没有考虑数组已经被存满时不能入栈的情况) 
    stack[++top] = n;
}
void pop(){          //出栈(没有考虑栈为空时不能出栈的情况) 
    top--; 
}
int getop(){         //取栈顶元素(没有考虑栈为空时不能取栈顶元素的情况) 
    return stack[top];
}
bool empty(){        //判断栈是否为空 
    return top==-1;
}
void print(){        //依次输出从栈底到栈顶的元素(测试需要)
    for(int i=0;i<=top;i++) cout<<stack[i]<<" ";
    cout<<endl;
} 
int main()
{
    for(int i=1;i<=5;i++) push(i);
    print();

    cout<<getop()<<endl;    
    pop();
    print();
    
    push(6);push(7);
    print();
    
    while(!empty()){     //全部出栈
        cout<<getop()<<endl;
		pop();   
    }
    return 0;
}

三、经典例题

1.P1739 表达式括号匹配

分析:使用栈来处理,依次扫描表达式中的字符,碰到左括号入栈,碰到右括号出栈。如果发现栈为空时要出栈的情况,或者扫描结束后栈不为空,那么括号不匹配。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int MAX = 300;
int stack[MAX];
int top = -1; //栈顶“指针”,也就是栈顶对应数组的下标
void push(int n){ //入栈(没有考虑数组已经被存满时不能入栈的情况)
stack[++top] = n;
}
int pop(){ //出栈(不仅仅出栈还返回出栈元素,没有考虑栈为空时不能出栈的情况)
return stack[top--];
}
bool empty(){ //判断栈是否为空
return top==-1;
}
int main()
{
char ch;
while(cin>>ch){
if(ch=='(') push(1); //入栈(入栈的数据在本题意义不大)
else if(ch==')'){
if(empty()){ //该出栈却发现栈为空,肯定不匹配
cout<<"NO";
return 0;
}
pop(); //出栈
}
}
//扫描结束后,栈为空则匹配
if(empty()) cout<<"YES";
else cout<<"NO";
return 0;
}
#include<iostream> using namespace std; const int MAX = 300; int stack[MAX]; int top = -1; //栈顶“指针”,也就是栈顶对应数组的下标 void push(int n){ //入栈(没有考虑数组已经被存满时不能入栈的情况) stack[++top] = n; } int pop(){ //出栈(不仅仅出栈还返回出栈元素,没有考虑栈为空时不能出栈的情况) return stack[top--]; } bool empty(){ //判断栈是否为空 return top==-1; } int main() { char ch; while(cin>>ch){ if(ch=='(') push(1); //入栈(入栈的数据在本题意义不大) else if(ch==')'){ if(empty()){ //该出栈却发现栈为空,肯定不匹配 cout<<"NO"; return 0; } pop(); //出栈 } } //扫描结束后,栈为空则匹配 if(empty()) cout<<"YES"; else cout<<"NO"; return 0; }
#include<iostream>
using namespace std;
const int MAX = 300;
int stack[MAX];
int top = -1;        //栈顶“指针”,也就是栈顶对应数组的下标 
void push(int n){    //入栈(没有考虑数组已经被存满时不能入栈的情况) 
    stack[++top] = n;
}
int pop(){       //出栈(不仅仅出栈还返回出栈元素,没有考虑栈为空时不能出栈的情况) 
    return stack[top--];
}
bool empty(){        //判断栈是否为空 
    return top==-1;
}
int main()
{
    char ch;
    while(cin>>ch){
        if(ch=='(') push(1);    //入栈(入栈的数据在本题意义不大) 
        else if(ch==')'){
            if(empty()){        //该出栈却发现栈为空,肯定不匹配 
                cout<<"NO";
                return 0;
            }
            pop();              //出栈 
        }
    }
    //扫描结束后,栈为空则匹配 
    if(empty()) cout<<"YES";
    else cout<<"NO";
    return 0;
}

本问题较简单,不使用栈也能处理。可以记录扫描过程中遇到的左括号的数量,遇到左括号计数+1,遇到右括号计数-1:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int main()
{
char ch;
int cnt = 0;
while(cin>>ch){
if(ch=='(') cnt++;
else if(ch==')'){
if(cnt==0){
cout<<"NO";
return 0;
}
cnt--;
}
}
if(cnt==0) cout<<"YES";
else cout<<"NO";
return 0;
}
#include<iostream> using namespace std; int main() { char ch; int cnt = 0; while(cin>>ch){ if(ch=='(') cnt++; else if(ch==')'){ if(cnt==0){ cout<<"NO"; return 0; } cnt--; } } if(cnt==0) cout<<"YES"; else cout<<"NO"; return 0; }
#include<iostream>
using namespace std;
int main()
{
	char ch;
	int cnt = 0;
    while(cin>>ch){
        if(ch=='(') cnt++; 
        else if(ch==')'){
            if(cnt==0){
                cout<<"NO";
                return 0;
            }
            cnt--;
        }
    }
    if(cnt==0) cout<<"YES";
    else cout<<"NO";
    return 0;
}

2.P1241 括号序列

分析:仍然使用栈来找出所有“找不到与之配对的括号”。对于这些没有与之配对的括号,如果是左括号,紧跟着左括号添加对应右括号;如果是右括号,在前面添加上对应左括号即可(下面的代码没有用函数来实现栈的操作)。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
struct node{
char ch;
int pos;
node(){}
node(char ch,int pos){
this->ch = ch;
this->pos = pos;
}
};
const int MAX = 110;
node stack[MAX];//栈里元素是结构体,记录字符和序号
int top = -1; //栈顶“指针”
char b[MAX]; //原始字符
int c[MAX]; //标记每个字符的匹配情况:0匹配,1不匹配
int main()
{
int i = 0;
while(cin>>b[i]){
if(b[i]=='(' || b[i]=='['){ //左括号:入栈
stack[++top] = node(b[i],i);
} else{
//右括号匹配上左括号,出栈
if(top!=-1 && (stack[top].ch=='(' && b[i]==')' || stack[top].ch=='[' && b[i]==']'))
top--;
else //匹配不上,标记
c[i] = 1;
}
i++;
}
while(top!=-1){ //栈里的左括号都是找不到与之匹配的,全部出栈,标记不匹配
c[stack[top--].pos] = 1;
}
for(int j=0;j<i;j++){
if(b[j]=='(' || b[j]=='['){ //左括号
cout<<b[j];
if(c[j]){ //没有匹配的右括号,直接在后面补上右括号
if(b[j]=='[') cout<<"]";
else if(b[j]=='(') cout<<")";
}
}else{ //右括号
if(c[j]){ //没有匹配的左括号,直接在前面补上左括号
if(b[j]==']') cout<<"[";
else if(b[j]==')') cout<<"(";
}
cout<<b[j];
}
}
return 0;
}
#include<iostream> using namespace std; struct node{ char ch; int pos; node(){} node(char ch,int pos){ this->ch = ch; this->pos = pos; } }; const int MAX = 110; node stack[MAX];//栈里元素是结构体,记录字符和序号 int top = -1; //栈顶“指针” char b[MAX]; //原始字符 int c[MAX]; //标记每个字符的匹配情况:0匹配,1不匹配 int main() { int i = 0; while(cin>>b[i]){ if(b[i]=='(' || b[i]=='['){ //左括号:入栈 stack[++top] = node(b[i],i); } else{ //右括号匹配上左括号,出栈 if(top!=-1 && (stack[top].ch=='(' && b[i]==')' || stack[top].ch=='[' && b[i]==']')) top--; else //匹配不上,标记 c[i] = 1; } i++; } while(top!=-1){ //栈里的左括号都是找不到与之匹配的,全部出栈,标记不匹配 c[stack[top--].pos] = 1; } for(int j=0;j<i;j++){ if(b[j]=='(' || b[j]=='['){ //左括号 cout<<b[j]; if(c[j]){ //没有匹配的右括号,直接在后面补上右括号 if(b[j]=='[') cout<<"]"; else if(b[j]=='(') cout<<")"; } }else{ //右括号 if(c[j]){ //没有匹配的左括号,直接在前面补上左括号 if(b[j]==']') cout<<"["; else if(b[j]==')') cout<<"("; } cout<<b[j]; } } return 0; }
#include<iostream>
using namespace std;
struct node{
    char ch;
    int pos;
    node(){}
    node(char ch,int pos){
        this->ch = ch;
        this->pos = pos;
    }
};
const int MAX = 110;
node stack[MAX];//栈里元素是结构体,记录字符和序号
int top = -1;   //栈顶“指针”
char b[MAX];    //原始字符 
int c[MAX];     //标记每个字符的匹配情况:0匹配,1不匹配
int main()
{
    int i = 0;
    while(cin>>b[i]){
        if(b[i]=='(' || b[i]=='['){    //左括号:入栈 
            stack[++top] = node(b[i],i);
        } else{
            //右括号匹配上左括号,出栈 
            if(top!=-1 && (stack[top].ch=='(' && b[i]==')' || stack[top].ch=='[' && b[i]==']'))
                top--;
            else //匹配不上,标记 
                c[i] = 1;
        }
        i++;
    }
    while(top!=-1){    //栈里的左括号都是找不到与之匹配的,全部出栈,标记不匹配 
        c[stack[top--].pos] = 1;
    }
    for(int j=0;j<i;j++){
        if(b[j]=='(' || b[j]=='['){    //左括号 
            cout<<b[j];
            if(c[j]){    //没有匹配的右括号,直接在后面补上右括号 
                if(b[j]=='[') cout<<"]";
                else if(b[j]=='(') cout<<")";
            }
        }else{           //右括号 
            if(c[j]){    //没有匹配的左括号,直接在前面补上左括号 
                if(b[j]==']') cout<<"[";
                else if(b[j]==')') cout<<"(";
            }
            cout<<b[j];
        }
    }
    return 0;
}

四、*利用结构体实现栈

选择阅读】也可以将栈封装成一个结构体,在结构体里使用成员函数实现栈的功能,通过调用结构体变量的成员函数实现入栈、出栈、判断栈是否为空:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//用结构体封装栈
const int N = 10000;
struct stack{
int pool[N];
int top;
stack(){ //构造函数
top = -1;
}
//判断栈是否为空
bool empty(){
return top==-1;
}
//入栈(如果存放栈元素的数组已满,返回false)
bool push(int n){
if(top>=N) return false;
pool[++top] = n;
return true;
}
//出栈(如果栈为空,返回false)
bool pop(){
if(empty()) return false;
top--;
return true;
}
//获取栈顶元素(如果栈为空,返回一个特殊值-1)
int getop(){
if(empty()) return -1;
return pool[top];
}
};
void print(stack s){ //依次输出从栈底到栈顶的元素(测试需要)
for(int i=0;i<=s.top;i++) cout<<s.pool[i]<<" ";
cout<<endl;
}
int main()
{
stack s;
for(int i=1;i<=5;i++) s.push(i);
print(s);
if(!s.empty()) cout<<s.getop()<<endl;
s.pop();
print(s);
s.push(6);s.push(7);
print(s);
while(!s.empty()){ //全部出栈
cout<<s.getop()<<endl;
s.pop();
}
return 0;
}
#include<iostream> using namespace std; //用结构体封装栈 const int N = 10000; struct stack{ int pool[N]; int top; stack(){ //构造函数 top = -1; } //判断栈是否为空 bool empty(){ return top==-1; } //入栈(如果存放栈元素的数组已满,返回false) bool push(int n){ if(top>=N) return false; pool[++top] = n; return true; } //出栈(如果栈为空,返回false) bool pop(){ if(empty()) return false; top--; return true; } //获取栈顶元素(如果栈为空,返回一个特殊值-1) int getop(){ if(empty()) return -1; return pool[top]; } }; void print(stack s){ //依次输出从栈底到栈顶的元素(测试需要) for(int i=0;i<=s.top;i++) cout<<s.pool[i]<<" "; cout<<endl; } int main() { stack s; for(int i=1;i<=5;i++) s.push(i); print(s); if(!s.empty()) cout<<s.getop()<<endl; s.pop(); print(s); s.push(6);s.push(7); print(s); while(!s.empty()){ //全部出栈 cout<<s.getop()<<endl; s.pop(); } return 0; }
#include<iostream>
using namespace std;

//用结构体封装栈 
const int N = 10000;
struct stack{
	int pool[N];
	int top;
		
	stack(){	//构造函数 
		top = -1;
	}
	
	//判断栈是否为空 
	bool empty(){
		return top==-1;
	}
	
	//入栈(如果存放栈元素的数组已满,返回false) 
	bool push(int n){
		if(top>=N) return false;
		pool[++top] = n;
		return true;
	}
	
	//出栈(如果栈为空,返回false) 
	bool pop(){
		if(empty()) return false;
		top--;
		return true;
	}
	
	//获取栈顶元素(如果栈为空,返回一个特殊值-1) 
	int getop(){
		if(empty()) return -1;
		return pool[top];
	}
};

void print(stack s){	//依次输出从栈底到栈顶的元素(测试需要)
	for(int i=0;i<=s.top;i++) cout<<s.pool[i]<<" ";
	cout<<endl;
}

int main()
{
	stack s;
	for(int i=1;i<=5;i++) s.push(i);
    print(s);
    if(!s.empty()) cout<<s.getop()<<endl;    
    s.pop();
    print(s);
    
    s.push(6);s.push(7);
    print(s);
    
    while(!s.empty()){     //全部出栈
        cout<<s.getop()<<endl;    
    	s.pop();    
    }
	return 0;
}

线性表——队列

tangyj626阅读(363)

中午在食堂打饭,真是一个令人头疼的事情,去食堂的路上也总是步伐匆匆,迟一点去,就会深刻领悟什么叫做人山人海了。相比较学生来说,打饭阿姨毕竟是少数,在每个窗口都有人的时候,我们就得排队等待,队列最前面的一个学生打完饭离开,后面排队的人才可以继续向前走,直到轮到自己。虽然费时,但是秩序和规则却是我们每个人都应该遵守的,也只能抱怨自己来的迟了。这里描述的就是现实生活中普遍存在的排队的情形。

一、队列的定义

用电脑的时候,有时候机器会处于疑似死机的状态,鼠标点什么似乎都没有用,双击任何快捷方式都不动,就当你快失去耐心,打算reset的时候,突然它就像酒醒了一样,把你刚才点击的所有操作全部按照顺序执行了一遍,这其实是因为操作系统中的多个程序需要通过一个通道输出,而按照先后次序排队等待造成的。

前面的例子体现出来的数据结构就是队列(queue)。队列是一种只允许在一端进行删除操作,在另一端进行插入操作的线性表。允许插入的一端称作队尾 (rear),允许删除的的一端称为队头 (front,或者称为队首) 。队列的数据元素又叫做队列元素。在队尾插入一个队列元素称为入队,从队头删除一个队列元素称为出队 。可知队列是一种典型的先进先出 (FIFO——first in first out) 结构。

二、队列的实现

1.普通队列

同样可以使用数组来模拟队列。需要用一个“指针”来指示队头front,用另外一个“指针”来指示队尾rear。队列的操作包括入队、出队、取队首元素和判断队列是否为空等:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int MAX = 1000;
int queue[MAX];
int front = 0; //队首“指针”,也就是队首对应数组的下标
int rear = 0; //队尾“指针”,其实是下一个入队元素存放位置(真实队尾应该是rear-1)
void push(int n){ //入队(没有考虑数组已被存满无法再入队的情况)
queue[rear++] = n;
}
int pop(){ //出队(没有考虑队列为空的情况)
return queue[front++];
}
int getfront(){ //取队首元素(没有考虑队列为空的情况)
return queue[front];
}
bool empty(){ //判断队列是否为空
return front==rear;
}
void print(){ //依次输出从队首到队尾的元素(测试需要)
for(int i=front;i<rear;i++) cout<<queue[i]<<" ";
cout<<endl;
}
int main()
{
for(int i=1;i<=5;i++) push(i);
print();
cout<<getfront()<<endl;
cout<<pop()<<endl;
print();
push(6);push(7);
print();
while(!empty()){ //全部出队
cout<<pop()<<endl;
}
return 0;
}
#include<iostream> using namespace std; const int MAX = 1000; int queue[MAX]; int front = 0; //队首“指针”,也就是队首对应数组的下标 int rear = 0; //队尾“指针”,其实是下一个入队元素存放位置(真实队尾应该是rear-1) void push(int n){ //入队(没有考虑数组已被存满无法再入队的情况) queue[rear++] = n; } int pop(){ //出队(没有考虑队列为空的情况) return queue[front++]; } int getfront(){ //取队首元素(没有考虑队列为空的情况) return queue[front]; } bool empty(){ //判断队列是否为空 return front==rear; } void print(){ //依次输出从队首到队尾的元素(测试需要) for(int i=front;i<rear;i++) cout<<queue[i]<<" "; cout<<endl; } int main() { for(int i=1;i<=5;i++) push(i); print(); cout<<getfront()<<endl; cout<<pop()<<endl; print(); push(6);push(7); print(); while(!empty()){ //全部出队 cout<<pop()<<endl; } return 0; }
#include<iostream>
using namespace std;
const int MAX = 1000;

int queue[MAX];
int front = 0;	//队首“指针”,也就是队首对应数组的下标 
int rear = 0;	 //队尾“指针”,其实是下一个入队元素存放位置(真实队尾应该是rear-1)

void push(int n){	//入队(没有考虑数组已被存满无法再入队的情况) 
	queue[rear++] = n;
}
int pop(){		   //出队(没有考虑队列为空的情况) 
	return queue[front++];
}
int getfront(){	  //取队首元素(没有考虑队列为空的情况) 
	return queue[front];
}
bool empty(){	    //判断队列是否为空
	return front==rear;
} 
void print(){        //依次输出从队首到队尾的元素(测试需要)
    for(int i=front;i<rear;i++) cout<<queue[i]<<" ";
    cout<<endl;
} 
int main()
{
    for(int i=1;i<=5;i++) push(i);
	print();
	
    cout<<getfront()<<endl;    
    cout<<pop()<<endl;
    print();
    
    push(6);push(7);
    print();
    
    while(!empty()){     //全部出队
        cout<<pop()<<endl;    
    } 
    return 0;
}

2.循环队列

使用上面的方法,在入队出队的过程中,队首、队尾“指针”front和rear都在不断增大,那么很容易出现数组下标溢出的情况。并且我们还发现数组的前部(下标0~front-1)的区间被闲置了。解决问题的方法是当front和rear达到数组长度MAX的时候都重置成0,这个时候就成了循环队列

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
void push(int n){ //入队
queue[rear] = n;
rear = (rear+1)%MAX;
}
int pop(){ //出队
int t = queue[front];
front = (front+1)%MAX;
return t;
}
void push(int n){ //入队 queue[rear] = n; rear = (rear+1)%MAX; } int pop(){ //出队 int t = queue[front]; front = (front+1)%MAX; return t; }
void push(int n){	 //入队 
	queue[rear] = n;
	rear = (rear+1)%MAX;
}
int pop(){			//出队
	int t = queue[front];
	front = (front+1)%MAX;
	return t;
}

在入队和出队的过程,rear和front互相追赶,如果rear追到front说明队列满了,如果front追到rear说明队列为空。但是现在会出现一个新问题,那就是:空队特征是front == rear, 队满时也会有front == rear,可知判断条件将出现二义性。那么如何解决这个问题呢?可以设置一个标记变量flag,例如在入队时设置flag=1,出队时设置flag=0,那么结合标记变量的值就能区分开空队列和满队列的情况了:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int MAX = 6; //设置了一个较小的循环队列容量,正好测试后面的数据
int queue[MAX];
int front = 0; //队首“指针”,也就是队首对应数组的下标
int rear = 0; //队尾“指针”,其实是下一个入队元素存放位置
int flag = 0; //标记最近的操作是入队还是出队
bool empty(){ //判断空队列
return flag==0 && front==rear;
}
bool full(){ //判断满队列
return flag==1 && front==rear;
}
void push(int n){ //入队
if(full()) return; //队列满,不能再入队
flag = 1;
queue[rear] = n;
rear = (rear+1)%MAX;
}
int pop(){ //出队
if(empty()) return -1; //队列空,不能出队(返回一个特殊值-1)
flag = 0;
int t = queue[front];
front = (front+1)%MAX;
return t;
}
int getfront(){ //取队首元素
if(empty()) return -1; //队列空,不能取队首元素(返回一个特殊值-1)
return queue[front];
}
void print(){ //依次输出从队首到队尾的元素(测试需要)
if(empty()) return; //空队列不处理
int last = rear;
if(last<=front) last += MAX; //rear小于front,特殊处理
for(int i=front;i<last;i++) cout<<queue[i%MAX]<<" ";
cout<<endl;
}
int main()
{
for(int i=1;i<=5;i++) push(i);
print();
cout<<getfront()<<endl;
cout<<pop()<<endl;
print();
push(6);push(7);
print();
while(!empty()){ //全部出队
cout<<pop()<<endl;
}
return 0;
}
#include<iostream> using namespace std; const int MAX = 6; //设置了一个较小的循环队列容量,正好测试后面的数据 int queue[MAX]; int front = 0; //队首“指针”,也就是队首对应数组的下标 int rear = 0; //队尾“指针”,其实是下一个入队元素存放位置 int flag = 0; //标记最近的操作是入队还是出队 bool empty(){ //判断空队列 return flag==0 && front==rear; } bool full(){ //判断满队列 return flag==1 && front==rear; } void push(int n){ //入队 if(full()) return; //队列满,不能再入队 flag = 1; queue[rear] = n; rear = (rear+1)%MAX; } int pop(){ //出队 if(empty()) return -1; //队列空,不能出队(返回一个特殊值-1) flag = 0; int t = queue[front]; front = (front+1)%MAX; return t; } int getfront(){ //取队首元素 if(empty()) return -1; //队列空,不能取队首元素(返回一个特殊值-1) return queue[front]; } void print(){ //依次输出从队首到队尾的元素(测试需要) if(empty()) return; //空队列不处理 int last = rear; if(last<=front) last += MAX; //rear小于front,特殊处理 for(int i=front;i<last;i++) cout<<queue[i%MAX]<<" "; cout<<endl; } int main() { for(int i=1;i<=5;i++) push(i); print(); cout<<getfront()<<endl; cout<<pop()<<endl; print(); push(6);push(7); print(); while(!empty()){ //全部出队 cout<<pop()<<endl; } return 0; }
#include<iostream>
using namespace std;
const int MAX = 6;   //设置了一个较小的循环队列容量,正好测试后面的数据

int queue[MAX];
int front = 0;	   //队首“指针”,也就是队首对应数组的下标 
int rear = 0;		//队尾“指针”,其实是下一个入队元素存放位置 
int flag = 0;	    //标记最近的操作是入队还是出队 
bool empty(){		//判断空队列 
	return flag==0 && front==rear;
}
bool full(){		 //判断满队列 
	return flag==1 && front==rear;
}
void push(int n){	//入队
	if(full()) return;	//队列满,不能再入队 
	flag = 1; 
	queue[rear] = n;
	rear = (rear+1)%MAX;
}
int pop(){			//出队
	if(empty()) return -1;	//队列空,不能出队(返回一个特殊值-1) 
	flag = 0;
	int t = queue[front];
	front = (front+1)%MAX;
	return t;
}
int getfront(){	   //取队首元素
	if(empty()) return -1;	//队列空,不能取队首元素(返回一个特殊值-1)  
	return queue[front];
}
void print(){         //依次输出从队首到队尾的元素(测试需要)
	if(empty()) return;		//空队列不处理 
	int last = rear;
	if(last<=front) last += MAX;	//rear小于front,特殊处理 
    for(int i=front;i<last;i++) cout<<queue[i%MAX]<<" ";
    cout<<endl;
}
int main()
{
    for(int i=1;i<=5;i++) push(i);
	print();
	
    cout<<getfront()<<endl;    
    cout<<pop()<<endl;
    print();
    
    push(6);push(7);
    print();
    
    while(!empty()){     //全部出队
        cout<<pop()<<endl;    
    } 
    return 0;
}

三、经典例题:使用队列解决约瑟夫问题

再来看前面介绍的约瑟夫问题,其实也可以用循环队列解决问题。开始时编号1~n依次入队;每次数到m的人出圈,其实可以认为队列里前1~m-1个人依次出队并入队,第m个人出队;如此重复操作,直到队列为空为止:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int MAX = 110;
int queue[MAX];
int front = 0; //队首“指针”,也就是队首对应数组的下标
int rear = 0; //队尾“指针”,其实是下一个入队元素存放位置
int flag = 0; //标记最近的操作是入队还是出队
bool empty(){ //判断空队列
return flag==0 && front==rear;
}
void push(int n){ //入队
flag = 1;
queue[rear] = n;
rear = (rear+1)%MAX;
}
int pop(){ //出队(返回了出队元素)
flag = 0;
int t = queue[front];
front = (front+1)%MAX;
return t;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) push(i);
while(!empty()){
//队列里前m-1人依次出队并再次入队
for(int i=1;i<m;i++) push(pop());
//第m个人出队
cout<<pop()<<" ";
}
return 0;
}
#include<iostream> using namespace std; const int MAX = 110; int queue[MAX]; int front = 0; //队首“指针”,也就是队首对应数组的下标 int rear = 0; //队尾“指针”,其实是下一个入队元素存放位置 int flag = 0; //标记最近的操作是入队还是出队 bool empty(){ //判断空队列 return flag==0 && front==rear; } void push(int n){ //入队 flag = 1; queue[rear] = n; rear = (rear+1)%MAX; } int pop(){ //出队(返回了出队元素) flag = 0; int t = queue[front]; front = (front+1)%MAX; return t; } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) push(i); while(!empty()){ //队列里前m-1人依次出队并再次入队 for(int i=1;i<m;i++) push(pop()); //第m个人出队 cout<<pop()<<" "; } return 0; }
#include<iostream>
using namespace std;
const int MAX = 110;

int queue[MAX];
int front = 0;       //队首“指针”,也就是队首对应数组的下标 
int rear = 0;        //队尾“指针”,其实是下一个入队元素存放位置 
int flag = 0;        //标记最近的操作是入队还是出队 
bool empty(){        //判断空队列 
    return flag==0 && front==rear;
}
void push(int n){    //入队
    flag = 1; 
    queue[rear] = n;
    rear = (rear+1)%MAX;
}
int pop(){           //出队(返回了出队元素)
    flag = 0;
    int t = queue[front];
    front = (front+1)%MAX;
    return t;
}
int main()
{
    int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) push(i);
	while(!empty()){
		//队列里前m-1人依次出队并再次入队 
		for(int i=1;i<m;i++) push(pop());
		//第m个人出队 
		cout<<pop()<<" ";
	}
    return 0;
}

四、利用结构体实现循环队列

选择阅读】也可以将队列封装成一个结构体,在结构体里使用成员函数实现队列的功能,通过调用结构体变量的成员函数实现入队、出队、判断队列是否为空:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//使用结构体封装循环队列
const int N = 10000;
struct queue{
int pool[N];
int front,rear,flag;
queue(){ //构造函数
front = rear = flag = 0;
}
//判断队列是否为空
bool empty(){
return flag==0 && front==rear;
}
//判断队列是否为满(存放队列元素的数组没有剩余空间)
bool full(){
return flag==1 && front==rear;
}
//入队(如果队列已满,返回false)
bool push(int n){
if(full()) return false;
flag = 1;
pool[rear] = n;
rear = (rear+1)%N;
return true;
}
//出队(如果队列为空,返回false)
bool pop(){
if(empty()) return false;
flag = 0;
front = (front+1)%N;
return true;
}
//取队首元素(如果队列为空,返回一个特殊值-1)
int getfront(){
if(empty()) return -1;
return pool[front];
}
};
void print(queue q){ //依次输出从队首到队尾的元素(测试需要)
if(q.empty()) return; //空队列不处理
int last = q.rear;
if(last<=q.front) last += N; //rear小于front,特殊处理
for(int i=q.front;i<last;i++) cout<<q.pool[i%N]<<" ";
cout<<endl;
}
int main()
{
queue q;
for(int i=1;i<=5;i++) q.push(i);
print(q);
if(!q.empty()) cout<<q.getfront()<<endl;
q.pop();
print(q);
q.push(6);q.push(7);
print(q);
while(!q.empty()){ //全部出队
cout<<q.getfront()<<endl;
q.pop();
}
return 0;
}
#include<iostream> using namespace std; //使用结构体封装循环队列 const int N = 10000; struct queue{ int pool[N]; int front,rear,flag; queue(){ //构造函数 front = rear = flag = 0; } //判断队列是否为空 bool empty(){ return flag==0 && front==rear; } //判断队列是否为满(存放队列元素的数组没有剩余空间) bool full(){ return flag==1 && front==rear; } //入队(如果队列已满,返回false) bool push(int n){ if(full()) return false; flag = 1; pool[rear] = n; rear = (rear+1)%N; return true; } //出队(如果队列为空,返回false) bool pop(){ if(empty()) return false; flag = 0; front = (front+1)%N; return true; } //取队首元素(如果队列为空,返回一个特殊值-1) int getfront(){ if(empty()) return -1; return pool[front]; } }; void print(queue q){ //依次输出从队首到队尾的元素(测试需要) if(q.empty()) return; //空队列不处理 int last = q.rear; if(last<=q.front) last += N; //rear小于front,特殊处理 for(int i=q.front;i<last;i++) cout<<q.pool[i%N]<<" "; cout<<endl; } int main() { queue q; for(int i=1;i<=5;i++) q.push(i); print(q); if(!q.empty()) cout<<q.getfront()<<endl; q.pop(); print(q); q.push(6);q.push(7); print(q); while(!q.empty()){ //全部出队 cout<<q.getfront()<<endl; q.pop(); } return 0; }
#include<iostream>
using namespace std;

//使用结构体封装循环队列 
const int N = 10000;
struct queue{
	int pool[N];
	int front,rear,flag;
	
	queue(){	//构造函数 
		front = rear = flag = 0;
	}
	
	//判断队列是否为空 
	bool empty(){
		return flag==0 && front==rear;
	}
	
	//判断队列是否为满(存放队列元素的数组没有剩余空间) 
	bool full(){
		return flag==1 && front==rear;
	}
	
	//入队(如果队列已满,返回false)
	bool push(int n){
	    if(full()) return false; 
	    flag = 1; 
	    pool[rear] = n;
	    rear = (rear+1)%N;
	    return true;
	}
	
	//出队(如果队列为空,返回false) 
	bool pop(){
	    if(empty()) return false;
	    flag = 0;
	    front = (front+1)%N;
	    return true;
	}
	
	//取队首元素(如果队列为空,返回一个特殊值-1)
	int getfront(){
	    if(empty()) return -1;
	    return pool[front];
	}
};

void print(queue q){         //依次输出从队首到队尾的元素(测试需要)
	if(q.empty()) return;	 //空队列不处理 
	int last = q.rear;
	if(last<=q.front) last += N;	//rear小于front,特殊处理 
    for(int i=q.front;i<last;i++) cout<<q.pool[i%N]<<" ";
    cout<<endl;
}
int main()
{
	queue q;
    for(int i=1;i<=5;i++) q.push(i);
	print(q);
	
    if(!q.empty()) cout<<q.getfront()<<endl;    
    q.pop();
    print(q);
    
    q.push(6);q.push(7);
    print(q);
    
    while(!q.empty()){     //全部出队
        cout<<q.getfront()<<endl;    
    	q.pop(); 
    } 
    return 0;
}

线性表——链表

tangyj626阅读(575)

班级所有同学去参观自然博物馆,在博物馆前列队完毕后解散进入馆内自由参观。活动结束后,领队老师想恢复参观前队列的次序,但是在解散前老师并没有记录下来所有人的次序,幸运的是每个人都知道在队列里自己的下一个人是谁,领队老师也知道队列里第一个人是谁。根据这些信息其实可以还原参观前的队列。

一、链表的定义

假设n位同学的编号依次为1~n,用一个int数组Next记录下最初队列里每个人的下一个人的编号(也就是编号为i的同学的下一个人的编号保存在数组元素Next[i]中),假设队列第一个人的编号是head,那么可知第二个人的编号是Next[head],第三个人的编号是Next[Next[head]]…如果将最后一个人的下一个人编号设置为特殊值0(表示后面没人了),很显然可以通过循环结构依次找到最初队列的每个人来恢复队列:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int N = 5;
int Next[N+1] = {0,4,1,5,0,2};
int head = 3;
int main()
{
for(int i=head;i!=0;i=Next[i]){
cout<<i<<" ";
}
return 0;
}
#include<iostream> using namespace std; const int N = 5; int Next[N+1] = {0,4,1,5,0,2}; int head = 3; int main() { for(int i=head;i!=0;i=Next[i]){ cout<<i<<" "; } return 0; }
#include<iostream>
using namespace std;
const int N = 5;
int Next[N+1] = {0,4,1,5,0,2};
int head = 3;
int main()
{
    for(int i=head;i!=0;i=Next[i]){
    	cout<<i<<" ";
	}
    return 0;
}

根据上面的例子可知:如果知道每个元素的后一个元素(或者前一个元素),那么可以恢复整个排列顺序。利用上面的方式存储元素排列顺序的线性表,称为链表(list)。

二、普通链表

有同学可能会想到,直接使用原始数组也能解决问题呀,那么为什么要使用链表呢?我们来看新的问题:如果n位同学排好了队,现在有一位编号为y同学要插到编号为x的同学后面。直接使用数组需要将数组末尾最后一个元素反向到第x+1个元素全部后移一位,然后将编号y插入到数组下标x+1处。同样地,队列里某个同学要从队列里出来,要删除数组中的元素,又会导致数组内部大量元素前移。可知不管是插入还是删除元素,直接用原始数组操作会出现大量元素移动操作,导致效率低下。

1.链表的使用

如果使用链表呢?还是上面图例中的情况,假设在编号1的同学后要插入一个编号为6的同学,那么操作前后图示如下:

将编号为y=6的元素插入到链表编号为x=1的元素的后面,由图可知,只需要执行:Next[y] = Next[x];Next[x] = y;

如果要删除编号x=5的元素的下一个元素,那么操作前后图示如下:

由图可知,由于Next[x]是编号为x的元素的下一个元素的编号,Next[Next[x]]是编号为x的元素的下下个元素的编号(其实就是删除x的下一个元素后,x的下一个元素的编号),那么删除编号为x的元素的下一个元素只需要执行Next[x] = Next[Next[x]]即可。

通过上面的分析可知,使用链表结构,可以轻松避免使用原始数组插入、删除元素时出现大量元素移位的情况,时间复杂度为O(1)。但是如果要查找链表第x个元素,那么需要从链首开始依次向后“顺蔓摸瓜”一样查找,时间复杂度为O(n),而可以随机存取的数组直接使用x下标即可。

2.使用链表解决约瑟夫问题

再来看约瑟夫问题,可以用链表来解决,用数组存储每个人的下一个人的编号,第 i 个人的下一个人的编号是 i+1,最后一个人的的下一个人的编号设置为 1,这样可以构成一个循环链表。数到 m 的人从链表里删除,也就是将数 m-1 的人的下一个人从链表里删除:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int Next[1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
Next[i] = i+1;
}
Next[n] = 1;
int p = n;
for(int i=n;i>=1;i--){
//数(m-1)次
for(int j=1;j<m;j++){
p = Next[p];
}
//那么Next[p]数m
cout<<Next[p]<<" ";
//从链表删除Next[p]
Next[p] = Next[Next[p]];
}
return 0;
}
#include<iostream> using namespace std; int Next[1010]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { Next[i] = i+1; } Next[n] = 1; int p = n; for(int i=n;i>=1;i--){ //数(m-1)次 for(int j=1;j<m;j++){ p = Next[p]; } //那么Next[p]数m cout<<Next[p]<<" "; //从链表删除Next[p] Next[p] = Next[Next[p]]; } return 0; }
#include<iostream>
using namespace std;
int Next[1010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		Next[i] = i+1;
	}
	Next[n] = 1;
	int p = n;
	for(int i=n;i>=1;i--){
		//数(m-1)次
		for(int j=1;j<m;j++){
			p = Next[p];
		}
		//那么Next[p]数m
		cout<<Next[p]<<" ";
		//从链表删除Next[p]
		Next[p] = Next[Next[p]];
	}
    return 0;
}

将约瑟夫问题变形:除了输入n和m,还要输入n个人的姓名,输出时除了输出编号,还要输出姓名。这个时候可以使用结构体数组来存储链表,结构体中使用成员变量name来记录姓名,使用成员变量next来记录下一个人的编号。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//不使用结构体
#include<iostream>
using namespace std;
int Next[1010];
string name[1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>name[i];
Next[i] = i+1;
}
Next[n] = 1;
int p = n;
for(int i=n;i>=1;i--){
//数(m-1)次
for(int j=1;j<m;j++){
p = Next[p];
}
int q = Next[p];
cout<<q<<" "<<name[q]<<endl;
//从链表删除q
Next[p] = Next[q];
}
return 0;
}
//不使用结构体 #include<iostream> using namespace std; int Next[1010]; string name[1010]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>name[i]; Next[i] = i+1; } Next[n] = 1; int p = n; for(int i=n;i>=1;i--){ //数(m-1)次 for(int j=1;j<m;j++){ p = Next[p]; } int q = Next[p]; cout<<q<<" "<<name[q]<<endl; //从链表删除q Next[p] = Next[q]; } return 0; }
//不使用结构体
#include<iostream>
using namespace std;
int Next[1010];
string name[1010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>name[i];
		Next[i] = i+1;
	}
	Next[n] = 1;
	int p = n;
	for(int i=n;i>=1;i--){
		//数(m-1)次
		for(int j=1;j<m;j++){
			p = Next[p];
		}
		int q = Next[p];
		cout<<q<<" "<<name[q]<<endl;
		//从链表删除q
		Next[p] = Next[q];
	}
    return 0;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
struct Person{
string name;
int next;
};
Person list[1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>list[i].name;
list[i].next = i+1;
}
list[n].next = 1;
int p = n;
for(int i=n;i>=1;i--){
//数(m-1)次
for(int j=1;j<m;j++){
p = list[p].next;
}
int q = list[p].next;
cout<<q<<" "<<list[q].name<<endl;
//从链表删除q
list[p].next = list[q].next;
}
return 0;
}
#include<iostream> using namespace std; struct Person{ string name; int next; }; Person list[1010]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>list[i].name; list[i].next = i+1; } list[n].next = 1; int p = n; for(int i=n;i>=1;i--){ //数(m-1)次 for(int j=1;j<m;j++){ p = list[p].next; } int q = list[p].next; cout<<q<<" "<<list[q].name<<endl; //从链表删除q list[p].next = list[q].next; } return 0; }
#include<iostream>
using namespace std;
struct Person{
	string name;
	int next;
};
Person list[1010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>list[i].name;
		list[i].next = i+1;
	}
	list[n].next = 1;
	int p = n;
	for(int i=n;i>=1;i--){
		//数(m-1)次
		for(int j=1;j<m;j++){
			p = list[p].next;
		}
		int q = list[p].next;
		cout<<q<<" "<<list[q].name<<endl;
		//从链表删除q
		list[p].next = list[q].next;
	}
    return 0;
}

三、双向链表

上面的问题都涉及到将元素插入到指定元素的后面,删除指定元素后面的元素,如果要插入到指定元素的前面,或者删除指定元素呢?这个时候可以使用双向链表:链表的每个元素可以设置成一个结构体,链表所有元素存储在结构体数组中;结构体里有基本数据成员(例如上面例子中的编号)、用来记录链表元素的下一个元素在数组中存储下标的next成员,此外再添加一个用来记录链表元素的上一个元素在数组中存储下标的prev成员;实际操作时,可以将链首元素存储在数组的首部:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int N = 1000;
struct node{
int key;
int prev,next; //链表中:本元素的上一个元素、下一个元素在数组list中的下标
node(){}
node(int key,int prev,int next){
this->key = key;
this->prev = prev;
this->next = next;
}
};
node list[N+10]; //链表的所有元素存储在数组中
int tot = 0; //记录list数组实际存储数量
int head = 1; //链首“指针”(链表第一个元素在数组list中的存储下标)
void printall(){ //“顺蔓摸瓜”从链首遍历链表所有元素
int now = head;
while(now){
cout<<list[now].key<<" ";
now = list[now].next;
}
cout<<endl;
}
int main()
{
//生成上面图例的双向链表
list[++tot] = node(3,0,2);
list[++tot] = node(5,1,3);
list[++tot] = node(2,2,4);
list[++tot] = node(1,3,5);
list[++tot] = node(4,4,0);
printall();
return 0;
}
#include<iostream> using namespace std; const int N = 1000; struct node{ int key; int prev,next; //链表中:本元素的上一个元素、下一个元素在数组list中的下标 node(){} node(int key,int prev,int next){ this->key = key; this->prev = prev; this->next = next; } }; node list[N+10]; //链表的所有元素存储在数组中 int tot = 0; //记录list数组实际存储数量 int head = 1; //链首“指针”(链表第一个元素在数组list中的存储下标) void printall(){ //“顺蔓摸瓜”从链首遍历链表所有元素 int now = head; while(now){ cout<<list[now].key<<" "; now = list[now].next; } cout<<endl; } int main() { //生成上面图例的双向链表 list[++tot] = node(3,0,2); list[++tot] = node(5,1,3); list[++tot] = node(2,2,4); list[++tot] = node(1,3,5); list[++tot] = node(4,4,0); printall(); return 0; }
#include<iostream>
using namespace std;
const int N = 1000;
struct node{
	int key;
	int prev,next;  //链表中:本元素的上一个元素、下一个元素在数组list中的下标
	node(){}
	node(int key,int prev,int next){
		this->key = key;
		this->prev = prev;
		this->next = next;
	}
};
node list[N+10];  //链表的所有元素存储在数组中
int tot = 0;	  //记录list数组实际存储数量
int head = 1;     //链首“指针”(链表第一个元素在数组list中的存储下标)
void printall(){  //“顺蔓摸瓜”从链首遍历链表所有元素 
	int now = head;
	while(now){
		cout<<list[now].key<<" ";
		now = list[now].next;
	}
	cout<<endl;
}
int main()
{
    //生成上面图例的双向链表 
    list[++tot] = node(3,0,2);
    list[++tot] = node(5,1,3);
    list[++tot] = node(2,2,4);
    list[++tot] = node(1,3,5);   
    list[++tot] = node(4,4,0);
	printall();
    return 0;
}

1.查找元素

查找链表结点key为x的元素在数组list中的存储下标(没找到会返回0):

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
int find(int x){
int now = head;
while(now && list[now].key!=x)
now = list[now].next;
return now;
}
int find(int x){ int now = head; while(now && list[now].key!=x) now = list[now].next; return now; }
int find(int x){
	int now = head;
	while(now && list[now].key!=x)
		now = list[now].next;
	return now;
} 

如果用一个tail来记录链尾,还可以实现从链尾反向查找:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
int rfind(int x){
int now = tail;
while(now && list[now].key!=x)
now = list[now].prev;
return now;
}
int rfind(int x){ int now = tail; while(now && list[now].key!=x) now = list[now].prev; return now; }
int rfind(int x){
	int now = tail;
	while(now && list[now].key!=x)
		now = list[now].prev;
	return now;
} 

2.插入元素

在key为x的元素后插入key为y的元素:

开始状态
STEP1:创建新元素(借助构造函数设置元素prev和next)
STEP2:设置now的下一个元素的prev指向新元素
STEP3:设置now的next指向新元素
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
bool insert_back(int x,int y){
if(tot+1>N) return false;
int now = find(x);
if(now==0) return false; //未找到key为x的元素,插入失败
//查找结束后,list[now]是key为x的元素
//新元素存放到数组中
list[++tot] = node(y,now,list[now].next);
//更新list[now]下一个元素list[list[now].next]的prev
//list[now].next是list[now]的下一个元素在list数组的存储下标
//list[list[now].next]就是list[now]的下一个元素
list[list[now].next].prev = tot;
//更新list[now]的next
list[now].next = tot;
return true;
}
bool insert_back(int x,int y){ if(tot+1>N) return false; int now = find(x); if(now==0) return false; //未找到key为x的元素,插入失败 //查找结束后,list[now]是key为x的元素 //新元素存放到数组中 list[++tot] = node(y,now,list[now].next); //更新list[now]下一个元素list[list[now].next]的prev //list[now].next是list[now]的下一个元素在list数组的存储下标 //list[list[now].next]就是list[now]的下一个元素 list[list[now].next].prev = tot; //更新list[now]的next list[now].next = tot; return true; }
bool insert_back(int x,int y){
	if(tot+1>N) return false;
	int now = find(x);
	if(now==0) return false;	//未找到key为x的元素,插入失败
	//查找结束后,list[now]是key为x的元素
	 
	//新元素存放到数组中 
	list[++tot] = node(y,now,list[now].next);
	
	//更新list[now]下一个元素list[list[now].next]的prev
	//list[now].next是list[now]的下一个元素在list数组的存储下标
	//list[list[now].next]就是list[now]的下一个元素 
	list[list[now].next].prev = tot;
	
	//更新list[now]的next 
	list[now].next = tot;
	
	return true;
}

在key为x的元素前插入key为y的元素(图例分析略):

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
bool insert_front(int x,int y){
if(tot+1>N) return false;
int now = find(x);
if(now==0) return false; //未找到key为x的元素,插入失败
//查找结束后,list[now]是key为x的元素
//新元素存放到数组中
list[++tot] = node(y,list[now].prev,now);
//更新list[now]上一个元素list[list[now].prev]的next
//list[now].prev是list[now]的上一个元素在list数组的存储下标
//list[list[now].prev]就是list[now]的上一个元素
list[list[now].prev].next = tot;
//更新list[now]的prev
list[now].prev = tot;
if(head==now) head = tot;
return true;
}
bool insert_front(int x,int y){ if(tot+1>N) return false; int now = find(x); if(now==0) return false; //未找到key为x的元素,插入失败 //查找结束后,list[now]是key为x的元素 //新元素存放到数组中 list[++tot] = node(y,list[now].prev,now); //更新list[now]上一个元素list[list[now].prev]的next //list[now].prev是list[now]的上一个元素在list数组的存储下标 //list[list[now].prev]就是list[now]的上一个元素 list[list[now].prev].next = tot; //更新list[now]的prev list[now].prev = tot; if(head==now) head = tot; return true; }
bool insert_front(int x,int y){
	if(tot+1>N) return false;
	int now = find(x);
	if(now==0) return false;	//未找到key为x的元素,插入失败
	//查找结束后,list[now]是key为x的元素
	
	//新元素存放到数组中 
	list[++tot] = node(y,list[now].prev,now);
	
	//更新list[now]上一个元素list[list[now].prev]的next
	//list[now].prev是list[now]的上一个元素在list数组的存储下标
	//list[list[now].prev]就是list[now]的上一个元素
	list[list[now].prev].next = tot;
	
	//更新list[now]的prev
	list[now].prev = tot;

	if(head==now) head = tot;

	return true;
}

3.删除元素

删除key为x的元素:

开始状态
STEP1:设置now下一个元素的prev为now的上一个元素
STEP2:设置now的上一个元素的next为now的下一个元素
STEP3:将now的prev和next设置为0(表示指向空元素)
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
bool del(int x){
int now = find(x);
if(now==0) return false; //未找到key为x的元素,删除失败
//查找结束后,list[now]是key为x的元素
list[list[now].next].prev = list[now].prev;
list[list[now].prev].next = list[now].next;
if(head==now) head = list[head].next;
return true;
}
bool del(int x){ int now = find(x); if(now==0) return false; //未找到key为x的元素,删除失败 //查找结束后,list[now]是key为x的元素 list[list[now].next].prev = list[now].prev; list[list[now].prev].next = list[now].next; if(head==now) head = list[head].next; return true; }
bool del(int x){
	int now = find(x);
	if(now==0) return false;	//未找到key为x的元素,删除失败	
	//查找结束后,list[now]是key为x的元素
	
	list[list[now].next].prev = list[now].prev;
	list[list[now].prev].next = list[now].next;

	if(head==now) head = list[head].next;
	
	return true;
}

4.完整测试程序

完整双链表测试程序如下:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int N = 1000;
struct node{
int key;
int prev,next; //链表中:本元素的上一个元素、下一个元素在数组list中的下标
node(){}
node(int key,int prev,int next){
this->key = key;
this->prev = prev;
this->next = next;
}
};
node list[N+10]; //链表的所有元素存储在数组中
int tot = 0; //记录list数组实际存储数量
int head = 1; //链首“指针”(链表第一个元素在数组list中的存储下标)
//“顺蔓摸瓜”从链首遍历链表所有元素
void printall(){
int now = head;
while(now){
cout<<list[now].key<<" ";
now = list[now].next;
}
cout<<endl;
}
//查找链表结点key为x的元素在数组list中的存储下标
int find(int x){
int now = head;
while(now && list[now].key!=x) now = list[now].next;
return now;
}
//在key为x的元素后插入key为y的元素
bool insert_back(int x,int y){
if(tot+1>N) return false;
int now = find(x);
if(now==0) return false; //未找到key为x的元素,插入失败
//查找结束后,list[now]是key为x的元素
//新元素存放到数组中
list[++tot] = node(y,now,list[now].next);
//更新list[now]下一个元素list[list[now].next]的prev
//list[now].next是list[now]的下一个元素在list数组的存储下标
//list[list[now].next]就是list[now]的下一个元素
list[list[now].next].prev = tot;
//更新list[now]的next
list[now].next = tot;
return true;
}
//在key为x的元素前插入key为y的元素
bool insert_front(int x,int y){
if(tot+1>N) return false;
int now = find(x);
if(now==0) return false; //未找到key为x的元素,插入失败
//查找结束后,list[now]是key为x的元素
//新元素存放到数组中
list[++tot] = node(y,list[now].prev,now);
//更新list[now]上一个元素list[list[now].prev]的next
//list[now].prev是list[now]的上一个元素在list数组的存储下标
//list[list[now].prev]就是list[now]的上一个元素
list[list[now].prev].next = tot;
//更新list[now]的prev
list[now].prev = tot;
if(head==now) head = tot;
return true;
}
//删除key为x的元素
bool del(int x){
int now = find(x);
if(now==0) return false; //未找到key为x的元素,删除失败
//查找结束后,list[now]是key为x的元素
list[list[now].next].prev = list[now].prev;
list[list[now].prev].next = list[now].next;
if(head==now) head = list[head].next;
return true;
}
int main()
{
//生成上面图例的双向链表
list[++tot] = node(3,0,2);
list[++tot] = node(5,1,3);
list[++tot] = node(2,2,4);
list[++tot] = node(1,3,5);
list[++tot] = node(4,4,0);
printall();
insert_back(1,6);
//insert_front(3,6);
printall();
del(2);
printall();
return 0;
}
#include<iostream> using namespace std; const int N = 1000; struct node{ int key; int prev,next; //链表中:本元素的上一个元素、下一个元素在数组list中的下标 node(){} node(int key,int prev,int next){ this->key = key; this->prev = prev; this->next = next; } }; node list[N+10]; //链表的所有元素存储在数组中 int tot = 0; //记录list数组实际存储数量 int head = 1; //链首“指针”(链表第一个元素在数组list中的存储下标) //“顺蔓摸瓜”从链首遍历链表所有元素 void printall(){ int now = head; while(now){ cout<<list[now].key<<" "; now = list[now].next; } cout<<endl; } //查找链表结点key为x的元素在数组list中的存储下标 int find(int x){ int now = head; while(now && list[now].key!=x) now = list[now].next; return now; } //在key为x的元素后插入key为y的元素 bool insert_back(int x,int y){ if(tot+1>N) return false; int now = find(x); if(now==0) return false; //未找到key为x的元素,插入失败 //查找结束后,list[now]是key为x的元素 //新元素存放到数组中 list[++tot] = node(y,now,list[now].next); //更新list[now]下一个元素list[list[now].next]的prev //list[now].next是list[now]的下一个元素在list数组的存储下标 //list[list[now].next]就是list[now]的下一个元素 list[list[now].next].prev = tot; //更新list[now]的next list[now].next = tot; return true; } //在key为x的元素前插入key为y的元素 bool insert_front(int x,int y){ if(tot+1>N) return false; int now = find(x); if(now==0) return false; //未找到key为x的元素,插入失败 //查找结束后,list[now]是key为x的元素 //新元素存放到数组中 list[++tot] = node(y,list[now].prev,now); //更新list[now]上一个元素list[list[now].prev]的next //list[now].prev是list[now]的上一个元素在list数组的存储下标 //list[list[now].prev]就是list[now]的上一个元素 list[list[now].prev].next = tot; //更新list[now]的prev list[now].prev = tot; if(head==now) head = tot; return true; } //删除key为x的元素 bool del(int x){ int now = find(x); if(now==0) return false; //未找到key为x的元素,删除失败 //查找结束后,list[now]是key为x的元素 list[list[now].next].prev = list[now].prev; list[list[now].prev].next = list[now].next; if(head==now) head = list[head].next; return true; } int main() { //生成上面图例的双向链表 list[++tot] = node(3,0,2); list[++tot] = node(5,1,3); list[++tot] = node(2,2,4); list[++tot] = node(1,3,5); list[++tot] = node(4,4,0); printall(); insert_back(1,6); //insert_front(3,6); printall(); del(2); printall(); return 0; }
#include<iostream>
using namespace std;
const int N = 1000;
struct node{
	int key;
	int prev,next;  //链表中:本元素的上一个元素、下一个元素在数组list中的下标
	node(){}
	node(int key,int prev,int next){
		this->key = key;
		this->prev = prev;
		this->next = next;
	}
};
node list[N+10];  //链表的所有元素存储在数组中
int tot = 0;	  //记录list数组实际存储数量
int head = 1;     //链首“指针”(链表第一个元素在数组list中的存储下标)

//“顺蔓摸瓜”从链首遍历链表所有元素
void printall(){ 
	int now = head;
	while(now){
		cout<<list[now].key<<" ";
		now = list[now].next;
	}
	cout<<endl;
}

//查找链表结点key为x的元素在数组list中的存储下标
int find(int x){
	int now = head;
	while(now && list[now].key!=x) now = list[now].next;
	return now;
} 

//在key为x的元素后插入key为y的元素
bool insert_back(int x,int y){
	if(tot+1>N) return false;
	int now = find(x);
	if(now==0) return false;	//未找到key为x的元素,插入失败
	//查找结束后,list[now]是key为x的元素
	 
	//新元素存放到数组中 
	list[++tot] = node(y,now,list[now].next);
	
	//更新list[now]下一个元素list[list[now].next]的prev
	//list[now].next是list[now]的下一个元素在list数组的存储下标
	//list[list[now].next]就是list[now]的下一个元素 
	list[list[now].next].prev = tot;
	
	//更新list[now]的next 
	list[now].next = tot;
	
	return true;
}

//在key为x的元素前插入key为y的元素
bool insert_front(int x,int y){
	if(tot+1>N) return false;
	int now = find(x);
	if(now==0) return false;	//未找到key为x的元素,插入失败
	//查找结束后,list[now]是key为x的元素
	
	//新元素存放到数组中 
	list[++tot] = node(y,list[now].prev,now);
	
	//更新list[now]上一个元素list[list[now].prev]的next
	//list[now].prev是list[now]的上一个元素在list数组的存储下标
	//list[list[now].prev]就是list[now]的上一个元素
	list[list[now].prev].next = tot;
	
	//更新list[now]的prev
	list[now].prev = tot;
	
	if(head==now) head = tot;
	
	return true;
}

//删除key为x的元素
bool del(int x){
	int now = find(x);
	if(now==0) return false;	//未找到key为x的元素,删除失败	
	//查找结束后,list[now]是key为x的元素
	
	list[list[now].next].prev = list[now].prev;
	list[list[now].prev].next = list[now].next;
	
	if(head==now) head = list[head].next;
	
	return true;
}

int main()
{
    //生成上面图例的双向链表
    list[++tot] = node(3,0,2);
    list[++tot] = node(5,1,3);
    list[++tot] = node(2,2,4);
    list[++tot] = node(1,3,5);   
    list[++tot] = node(4,4,0);
	printall();
	
	insert_back(1,6);
	//insert_front(3,6);
	printall();
	
	del(2);
	printall();	
    return 0;
}

5.双向链表解决约瑟夫问题

约瑟夫问题同样可以用循环双链表来解决:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int N = 100;
//本例中记录第i个人的前一个人、后一个人的编号的结构体肯定存储在数组元素list[i]中
//所以结构体中不需要存储人的编号
struct node{
int prev,next;
node(){}
node(int prev,int next){
this->prev = prev;
this->next = next;
}
};
node list[N+10];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
list[i] = node(i-1,i+1);
}
//构成循环双链表
list[1].prev = n;
list[n].next = 1;
int i = n; //i记录数数的人的编号,初始值设置为n,进入循环正好第1个人数数
while(list[i].next != i){
//m个人依次数数
for(int j=1;j<=m;j++) i = list[i].next;
cout<<i<<" ";
//删除编号为i的元素
list[list[i].prev].next = list[i].next;
list[list[i].next].prev = list[i].prev;
}
return 0;
}
#include<iostream> using namespace std; const int N = 100; //本例中记录第i个人的前一个人、后一个人的编号的结构体肯定存储在数组元素list[i]中 //所以结构体中不需要存储人的编号 struct node{ int prev,next; node(){} node(int prev,int next){ this->prev = prev; this->next = next; } }; node list[N+10]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ list[i] = node(i-1,i+1); } //构成循环双链表 list[1].prev = n; list[n].next = 1; int i = n; //i记录数数的人的编号,初始值设置为n,进入循环正好第1个人数数 while(list[i].next != i){ //m个人依次数数 for(int j=1;j<=m;j++) i = list[i].next; cout<<i<<" "; //删除编号为i的元素 list[list[i].prev].next = list[i].next; list[list[i].next].prev = list[i].prev; } return 0; }
#include<iostream>
using namespace std;
const int N = 100;
//本例中记录第i个人的前一个人、后一个人的编号的结构体肯定存储在数组元素list[i]中
//所以结构体中不需要存储人的编号
struct node{
	int prev,next;
	node(){}
	node(int prev,int next){
		this->prev = prev;
		this->next = next;
	}
};
node list[N+10];
int main()
{
	int n,m;
	cin>>n>>m;

	for(int i=1;i<=n;i++){
		list[i] = node(i-1,i+1);
	}	
	//构成循环双链表 
	list[1].prev = n;
	list[n].next = 1;
	
	int i = n;		//i记录数数的人的编号,初始值设置为n,进入循环正好第1个人数数 
	while(list[i].next != i){
		//m个人依次数数 
		for(int j=1;j<=m;j++) i = list[i].next;
		cout<<i<<" ";
		//删除编号为i的元素
		list[list[i].prev].next = list[i].next;
		list[list[i].next].prev = list[i].prev;
	}
    return 0;
}

*链表(用指针实现)

tangyj626阅读(302)

前面小节我们学习了用结构体数组来存储链表,结构体中的prev和next“指针”其实是整数,指向的是上一个元素和下一个元素在数组中的存储下标。其实我们还可以在结构体中使用真正的指向上一个元素和下一个元素的指针来实现链表。

一、普通链表

1.使用结构体定义结点

可以在结构体内部设置一个指向该结构体的指针成员来指向链表的下一个结点(或者上一个结点),具体做法如下:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//借助结构体定义链表的结点
struct node{
int key;
node *next; //结点的next指针,指向下一个node接点
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->next = NULL; //NULL是空指针
}
};
node *head; //链表的head指针,指向链表的首结点
//借助结构体定义链表的结点 struct node{ int key; node *next; //结点的next指针,指向下一个node接点 node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->next = NULL; //NULL是空指针 } }; node *head; //链表的head指针,指向链表的首结点
//借助结构体定义链表的结点 
struct node{
	int key;
	node *next;		//结点的next指针,指向下一个node接点 
	node(){}		   //无参构造函数 
	node(int key){	 //有参构造函数 
		this->key = key;
		this->next = NULL;	//NULL是空指针 
	}
};
node *head;			//链表的head指针,指向链表的首结点

可知结构体node内部有一个node类型(与结构体名称相同)的指针next,用来指向链表中该结点的下一个结点。构造函数中将next设置成了一个特殊的空指针NULL。

2.生成链表

仍然是上节课引例中的链表,用这样的方式生成的链表结构如下:

可以使用node *p = new node(n);这样“new +结构体构造函数”的方式生成一个指向结构体的指针,那么生成上述链表的代码如下:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//借助结构体定义链表的结点
struct node{
int key;
node *next; //结点的next指针,指向下一个node接点
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->next = NULL; //NULL是空指针
}
};
node *head; //链表的head指针,指向链表的首结点
int main()
{
node *p,*q;
head = p = new node(3);
q = p;
p = new node(5);
q->next = p;
q = p;
p = new node(2);
q->next = p;
q = p;
p = new node(1);
q->next = p;
q = p;
p = new node(4);
q->next = p;
q = p;
//遍历链表的所有结点
p = head;
while(p!=NULL){ //条件p!=NULL可以简写成p(p不为NULL则条件成立)
cout<<p->key<<" ";
p = p->next;
}
return 0;
}
#include<iostream> using namespace std; //借助结构体定义链表的结点 struct node{ int key; node *next; //结点的next指针,指向下一个node接点 node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->next = NULL; //NULL是空指针 } }; node *head; //链表的head指针,指向链表的首结点 int main() { node *p,*q; head = p = new node(3); q = p; p = new node(5); q->next = p; q = p; p = new node(2); q->next = p; q = p; p = new node(1); q->next = p; q = p; p = new node(4); q->next = p; q = p; //遍历链表的所有结点 p = head; while(p!=NULL){ //条件p!=NULL可以简写成p(p不为NULL则条件成立) cout<<p->key<<" "; p = p->next; } return 0; }
#include<iostream>
using namespace std;
//借助结构体定义链表的结点 
struct node{
	int key;
	node *next;		//结点的next指针,指向下一个node接点 
	node(){}		   //无参构造函数 
	node(int key){	 //有参构造函数 
		this->key = key;
		this->next = NULL;	//NULL是空指针 
	}
};
node *head;			//链表的head指针,指向链表的首结点 
int main()
{
	node *p,*q;
	head = p = new node(3);
	q = p;
	
	p = new node(5);
	q->next = p;
	q = p;
	
	p = new node(2);
	q->next = p;
	q = p;
	
	p = new node(1);
	q->next = p;
	q = p;
	
	p = new node(4);
	q->next = p;
	q = p;
	
	//遍历链表的所有结点 
	p = head;
	while(p!=NULL){    //条件p!=NULL可以简写成p(p不为NULL则条件成立)
		cout<<p->key<<" ";
		p = p->next;
	} 
    return 0;
}

当然可以将结点的key存储在数组中,使用循环生成链表:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//正向建立链表
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;
head = q = new node(a[0]);
for(int i=1;i<N;i++){
p = new node(a[i]);
q->next = p;
q = p;
}
//正向建立链表 const int N = 5; int a[N] = {3,5,2,1,4}; node *p,*q; head = q = new node(a[0]); for(int i=1;i<N;i++){ p = new node(a[i]); q->next = p; q = p; }
//正向建立链表
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;

head = q = new node(a[0]);
for(int i=1;i<N;i++){
	p = new node(a[i]);
	q->next = p;
	q = p;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//反向建立链表
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;
q = new node(a[N-1]);
for(int i=N-2;i>=0;i--){
p = new node(a[i]);
p->next = q;
q = p;
}
head = p; //head = q;亦可
//反向建立链表 const int N = 5; int a[N] = {3,5,2,1,4}; node *p,*q; q = new node(a[N-1]); for(int i=N-2;i>=0;i--){ p = new node(a[i]); p->next = q; q = p; } head = p; //head = q;亦可
//反向建立链表
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;
q = new node(a[N-1]);
for(int i=N-2;i>=0;i--){
	p = new node(a[i]);
	p->next = q;
	q = p;
}
head = p;  //head = q;亦可

3.查找结点

查找key为x的结点,返回指向结点的指针,找不到返回NULL(注意此时函数的返回值是指针):

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
node* find(int x){ //返回key为x的结点的指针(找不到返回NULL)
node *p = head;
while(p && p->key!=x) p = p->next;
return p;
}
node* find(int x){ //返回key为x的结点的指针(找不到返回NULL) node *p = head; while(p && p->key!=x) p = p->next; return p; }
node* find(int x){      //返回key为x的结点的指针(找不到返回NULL)
	node *p = head;
	while(p && p->key!=x) p = p->next;
	return p;
}

4.插入结点

在结点指针p后面插入一个key为y的结点,只需要执行下图所示①②③三步操作:

①:node *q = new node(y);
②:q->next = p->next;
③:p->next = q;
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
node *q = new node(y);
q->next = p->next;
p->next = q;
node *q = new node(y); q->next = p->next; p->next = q;
node *q = new node(y);
q->next = p->next;
p->next = q;

5.删除结点

删除结点指针p后面的结点,只需要执行下图所示①②③三步操作:

node *q = p->next;
②:p->next = q->next;
③:delete q;释放q指向的node结点内存
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
node *q = p->next;
if(q) {
p->next = q->next;
//delete q;
}
node *q = p->next; if(q) { p->next = q->next; //delete q; }
node *q = p->next;
if(q) {			
	p->next = q->next;
	//delete q;
}

6.完整测试程序

完整的测试代码如下:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//借助结构体定义链表的结点
struct node{
int key;
node *next; //结点的next指针,指向下一个node接点
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->next = NULL; //NULL是空指针
}
};
node *head; //链表的head指针,指向链表的首结点
//遍历链表的所有结点
void printall(){
node *p = head;
while(p){
cout<<p->key<<" ";
p = p->next;
}
cout<<endl;
}
//查找key为x的结点,返回指向结点的指针
node* find(int x){
node *p = head;
while(p && p->key!=x) p = p->next;
return p;
}
int main()
{
//正向建立链表
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;
head = q = new node(a[0]);
for(int i=1;i<N;i++){
p = new node(a[i]);
q->next = p;
q = p;
}
printall();
p = find(1);
if(p){
//在p后插入新结点
node *q = new node(6);
q->next = p->next;
p->next = q;
}
printall();
p = find(5);
if(p){
//删除p的下一个结点
node *q = p->next;
if(q) {
p->next = q->next;
//delete q;
}
}
printall();
return 0;
}
#include<iostream> using namespace std; //借助结构体定义链表的结点 struct node{ int key; node *next; //结点的next指针,指向下一个node接点 node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->next = NULL; //NULL是空指针 } }; node *head; //链表的head指针,指向链表的首结点 //遍历链表的所有结点 void printall(){ node *p = head; while(p){ cout<<p->key<<" "; p = p->next; } cout<<endl; } //查找key为x的结点,返回指向结点的指针 node* find(int x){ node *p = head; while(p && p->key!=x) p = p->next; return p; } int main() { //正向建立链表 const int N = 5; int a[N] = {3,5,2,1,4}; node *p,*q; head = q = new node(a[0]); for(int i=1;i<N;i++){ p = new node(a[i]); q->next = p; q = p; } printall(); p = find(1); if(p){ //在p后插入新结点 node *q = new node(6); q->next = p->next; p->next = q; } printall(); p = find(5); if(p){ //删除p的下一个结点 node *q = p->next; if(q) { p->next = q->next; //delete q; } } printall(); return 0; }
#include<iostream>
using namespace std;
//借助结构体定义链表的结点 
struct node{
	int key;
	node *next;        //结点的next指针,指向下一个node接点 
	node(){}		   //无参构造函数 
	node(int key){	 //有参构造函数 
		this->key = key;
		this->next = NULL;	//NULL是空指针 
	}
};
node *head;			//链表的head指针,指向链表的首结点

//遍历链表的所有结点 
void printall(){
	node *p = head;
	while(p){ 
		cout<<p->key<<" ";
		p = p->next;
	}
	cout<<endl;
}

//查找key为x的结点,返回指向结点的指针
node* find(int x){
	node *p = head;
	while(p && p->key!=x) p = p->next;
	return p;
}
int main()
{
	//正向建立链表
	const int N = 5;
	int a[N] = {3,5,2,1,4};
	node *p,*q;
	head = q = new node(a[0]);
	for(int i=1;i<N;i++){
		p = new node(a[i]);
		q->next = p;
		q = p;
	}
	printall();
	
	p = find(1);
	if(p){
		//在p后插入新结点
		node *q = new node(6);
		q->next = p->next;
		p->next = q;
	}
	printall();
	
	p = find(5);
	if(p){
		//删除p的下一个结点
		node *q = p->next;
		if(q) {			
			p->next = q->next;
			//delete q;
		}
	}
	
	printall();
    return 0;
}

7.使用链表解决约瑟夫问题

和上一小节一样,用循环链表解决约瑟夫问题:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//借助结构体定义链表的结点
struct node{
int key;
node *next; //结点的next指针,指向下一个node接点
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->next = NULL; //NULL是空指针
}
};
int main()
{
int n,m;
cin>>n>>m;
node *head,*p,*q;
head = q = new node(1);
for(int i=2;i<=n;i++){
p = new node(i);
q->next = p;
q = p;
}
p->next = head; //构成循环链表
//循环开始前p、q均指向最后一个结点
for(int i=1;i<=n;i++){
//前m-1个人数数
for(int i=1;i<m;i++) p = p->next;
q = p->next; //第m个人数数
cout<<q->key<<" ";
p->next = q->next;
}
return 0;
}
#include<iostream> using namespace std; //借助结构体定义链表的结点 struct node{ int key; node *next; //结点的next指针,指向下一个node接点 node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->next = NULL; //NULL是空指针 } }; int main() { int n,m; cin>>n>>m; node *head,*p,*q; head = q = new node(1); for(int i=2;i<=n;i++){ p = new node(i); q->next = p; q = p; } p->next = head; //构成循环链表 //循环开始前p、q均指向最后一个结点 for(int i=1;i<=n;i++){ //前m-1个人数数 for(int i=1;i<m;i++) p = p->next; q = p->next; //第m个人数数 cout<<q->key<<" "; p->next = q->next; } return 0; }
#include<iostream>
using namespace std;
//借助结构体定义链表的结点 
struct node{
    int key;
    node *next;        //结点的next指针,指向下一个node接点 
    node(){}           //无参构造函数 
    node(int key){     //有参构造函数 
        this->key = key;
        this->next = NULL;    //NULL是空指针 
    }
};
int main()
{
    int n,m;
    cin>>n>>m;

    node *head,*p,*q;
    head = q = new node(1);
    for(int i=2;i<=n;i++){
        p = new node(i);
        q->next = p;
        q = p;
    }
    p->next = head;        //构成循环链表
    
    //循环开始前p、q均指向最后一个结点 
    for(int i=1;i<=n;i++){
        //前m-1个人数数 
        for(int i=1;i<m;i++) p = p->next;
        q = p->next;       //第m个人数数
        cout<<q->key<<" ";
        p->next = q->next;
    }
    return 0;
}

二、双向链表

单链表可以快速实现在某个结点后插入新结点或者删除某个结点后的结点,但是如果要在结点前插入新结点或者删除某个指定结点就有难度了,这个时候可以使用双链表:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//借助结构体定义链表的结点
struct node{
int key;
node *prev,*next;
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->prev = NULL; //NULL是空指针
this->next = NULL; //NULL是空指针
}
};
node *head,*tail; //链首指针和链尾指针
int main()
{
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;
head = q = new node(a[0]);
for(int i=1;i<N;i++){
p = new node(a[i]);
p->prev = q;
q->next = p;
q = p;
}
tail = p;
//遍历链表的所有结点
p = head;
while(p){
cout<<p->key<<" ";
p = p->next;
}
cout<<endl;
//从链尾反向遍历链表所有结点
p = tail;
while(p){
cout<<p->key<<" ";
p = p->prev;
}
return 0;
}
#include<iostream> using namespace std; //借助结构体定义链表的结点 struct node{ int key; node *prev,*next; node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->prev = NULL; //NULL是空指针 this->next = NULL; //NULL是空指针 } }; node *head,*tail; //链首指针和链尾指针 int main() { const int N = 5; int a[N] = {3,5,2,1,4}; node *p,*q; head = q = new node(a[0]); for(int i=1;i<N;i++){ p = new node(a[i]); p->prev = q; q->next = p; q = p; } tail = p; //遍历链表的所有结点 p = head; while(p){ cout<<p->key<<" "; p = p->next; } cout<<endl; //从链尾反向遍历链表所有结点 p = tail; while(p){ cout<<p->key<<" "; p = p->prev; } return 0; }
#include<iostream>
using namespace std;
//借助结构体定义链表的结点 
struct node{
	int key;
	node *prev,*next;
	node(){}		  //无参构造函数 
	node(int key){	//有参构造函数 
		this->key = key;
		this->prev = NULL;	//NULL是空指针
		this->next = NULL;	//NULL是空指针 
	}
};
node *head,*tail; 	//链首指针和链尾指针 
int main()
{
	const int N = 5;
	int a[N] = {3,5,2,1,4};
	node *p,*q;
	head = q = new node(a[0]);
	for(int i=1;i<N;i++){
	    p = new node(a[i]);
	    p->prev = q;
	    q->next = p;
	    q = p;
	}
	tail = p;
	
	//遍历链表的所有结点 
    p = head;
    while(p){ 
        cout<<p->key<<" ";
        p = p->next;
    }
    cout<<endl;
    
    //从链尾反向遍历链表所有结点
	p = tail;
    while(p){ 
        cout<<p->key<<" ";
        p = p->prev;
    }
    return 0;
}

在指针结点p后插入key为y的结点、在指针结点p前插入key为y的结点、删除指针结点p的参考代码如下,大家可以参照下图自行分析:

在p指向的结点插入新结点q
在p指向的结点插入新结点q
删除p指向的结点
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//借助结构体定义链表的结点
struct node{
int key;
node *prev,*next;
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->prev = NULL; //NULL是空指针
this->next = NULL; //NULL是空指针
}
};
node *head,*tail; //链首指针和链尾指针
//遍历链表的所有结点
void printall(){
node *p = head;
while(p){
cout<<p->key<<" ";
p = p->next;
}
cout<<endl;
}
//从链尾反向遍历链表的所有结点
void rprintall(){
node *p = tail;
while(p){
cout<<p->key<<" ";
p = p->prev;
}
cout<<endl;
}
//查找key为x的结点,返回结点指针
node* find(int x){
node *p = head;
while(p && p->key!=x) p = p->next;
return p;
}
//从链尾反向查找key为x的结点,返回结点指针
node* find(int x){
node *p = tail;
while(p && p->key!=x) p = p->prev;
return p;
}
//在指针结点p后插入key为y的结点
void insert_back(node *p,int y){
node *q = new node(y);
if(p->next) p->next->prev = q;
else tail = q;
q->next = p->next;
p->next = q;
q->prev = p;
}
//在指针结点p前插入key为y的结点
void insert_front(node *p,int y){
node *q = new node(y);
if(p->prev) p->prev->next = q;
else head = q;
q->prev = p->prev;
p->prev = q;
q->next = p;
}
//删除指针结点p
void _delete(node *p){
if(p==head) head = p->next;
if(p==tail) tail = p->prev;
if(p->prev) p->prev->next = p->next;
if(p->next) p->next->prev = p->prev;
//delete p;
}
int main()
{
const int N = 5;
int a[N] = {3,5,2,1,4};
node *p,*q;
head = q = new node(a[0]);
for(int i=1;i<N;i++){
p = new node(a[i]);
p->prev = q;
q->next = p;
q = p;
}
tail = p;
printall();
rprintall();
p = find(4);
if(p) insert_front(p,6);
printall();
rprintall();
p = find(2);
if(p) _delete(p);
printall();
rprintall();
return 0;
}
#include<iostream> using namespace std; //借助结构体定义链表的结点 struct node{ int key; node *prev,*next; node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->prev = NULL; //NULL是空指针 this->next = NULL; //NULL是空指针 } }; node *head,*tail; //链首指针和链尾指针 //遍历链表的所有结点 void printall(){ node *p = head; while(p){ cout<<p->key<<" "; p = p->next; } cout<<endl; } //从链尾反向遍历链表的所有结点 void rprintall(){ node *p = tail; while(p){ cout<<p->key<<" "; p = p->prev; } cout<<endl; } //查找key为x的结点,返回结点指针 node* find(int x){ node *p = head; while(p && p->key!=x) p = p->next; return p; } //从链尾反向查找key为x的结点,返回结点指针 node* find(int x){ node *p = tail; while(p && p->key!=x) p = p->prev; return p; } //在指针结点p后插入key为y的结点 void insert_back(node *p,int y){ node *q = new node(y); if(p->next) p->next->prev = q; else tail = q; q->next = p->next; p->next = q; q->prev = p; } //在指针结点p前插入key为y的结点 void insert_front(node *p,int y){ node *q = new node(y); if(p->prev) p->prev->next = q; else head = q; q->prev = p->prev; p->prev = q; q->next = p; } //删除指针结点p void _delete(node *p){ if(p==head) head = p->next; if(p==tail) tail = p->prev; if(p->prev) p->prev->next = p->next; if(p->next) p->next->prev = p->prev; //delete p; } int main() { const int N = 5; int a[N] = {3,5,2,1,4}; node *p,*q; head = q = new node(a[0]); for(int i=1;i<N;i++){ p = new node(a[i]); p->prev = q; q->next = p; q = p; } tail = p; printall(); rprintall(); p = find(4); if(p) insert_front(p,6); printall(); rprintall(); p = find(2); if(p) _delete(p); printall(); rprintall(); return 0; }
#include<iostream>
using namespace std;
//借助结构体定义链表的结点 
struct node{
	int key;
	node *prev,*next;
	node(){}		  //无参构造函数 
	node(int key){	//有参构造函数 
		this->key = key;
		this->prev = NULL;	//NULL是空指针
		this->next = NULL;	//NULL是空指针 
	}
};
node *head,*tail; 	//链首指针和链尾指针

//遍历链表的所有结点
void printall(){ 
    node *p = head;
    while(p){
        cout<<p->key<<" ";
        p = p->next;
    }
    cout<<endl;
}

//从链尾反向遍历链表的所有结点
void rprintall(){ 
    node *p = tail;
    while(p){ 
        cout<<p->key<<" ";
        p = p->prev;
    }
    cout<<endl;
}

//查找key为x的结点,返回结点指针 
node* find(int x){
    node *p = head;
    while(p && p->key!=x) p = p->next;
    return p;
}

//从链尾反向查找key为x的结点,返回结点指针 
node* find(int x){
    node *p = tail;
    while(p && p->key!=x) p = p->prev;
    return p;
}

//在指针结点p后插入key为y的结点 
void insert_back(node *p,int y){
	node *q = new node(y);
	
	if(p->next) p->next->prev = q;
	else tail = q;
	
	q->next = p->next;
	p->next = q;
	q->prev = p;
}

//在指针结点p前插入key为y的结点
void insert_front(node *p,int y){
	node *q = new node(y);
	
	if(p->prev) p->prev->next = q;		
	else head = q;
	
	q->prev = p->prev;
	p->prev = q;
	q->next = p;
}

//删除指针结点p 
void _delete(node *p){
	if(p==head) head = p->next;
	if(p==tail) tail = p->prev;
	
	if(p->prev) p->prev->next = p->next;
	if(p->next) p->next->prev = p->prev;
	//delete p;
}
int main()
{
	const int N = 5;
	int a[N] = {3,5,2,1,4};
	node *p,*q;
	head = q = new node(a[0]);
	for(int i=1;i<N;i++){
	    p = new node(a[i]);
	    p->prev = q;
	    q->next = p;
	    q = p;
	}
	tail = p;
	printall();
	rprintall();
	
	p = find(4);
	if(p) insert_front(p,6);
	printall();
	rprintall();
	
	p = find(2);
	if(p) _delete(p);
	printall();
	rprintall();
	
    return 0;
}

同样地,可以使用循环双链表解决约瑟夫问题:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
//借助结构体定义链表的结点
struct node{
int key;
node *prev,*next;
node(){} //无参构造函数
node(int key){ //有参构造函数
this->key = key;
this->prev = NULL; //NULL是空指针
this->next = NULL; //NULL是空指针
}
};
int main()
{
int n,m;
cin>>n>>m;
node *head,*p,*q;
head = q = new node(1);
for(int i=2;i<=n;i++){
p = new node(i);
p->prev = q;
q->next = p;
q = p;
}
//构成循环链表
p->next = head;
head->prev = p;
//循环开始前p指向最后一个结点
for(int i=1;i<=n;i++){
//m个人依次数数
for(int j=1;j<=m;j++) p = p->next;
cout<<p->key<<" ";
//删除结点p
p->prev->next = p->next;
p->next->prev = p->prev;
}
return 0;
}
#include<iostream> using namespace std; //借助结构体定义链表的结点 struct node{ int key; node *prev,*next; node(){} //无参构造函数 node(int key){ //有参构造函数 this->key = key; this->prev = NULL; //NULL是空指针 this->next = NULL; //NULL是空指针 } }; int main() { int n,m; cin>>n>>m; node *head,*p,*q; head = q = new node(1); for(int i=2;i<=n;i++){ p = new node(i); p->prev = q; q->next = p; q = p; } //构成循环链表 p->next = head; head->prev = p; //循环开始前p指向最后一个结点 for(int i=1;i<=n;i++){ //m个人依次数数 for(int j=1;j<=m;j++) p = p->next; cout<<p->key<<" "; //删除结点p p->prev->next = p->next; p->next->prev = p->prev; } return 0; }
#include<iostream>
using namespace std;
//借助结构体定义链表的结点 
struct node{
	int key;
	node *prev,*next;
	node(){}		  //无参构造函数 
	node(int key){	//有参构造函数 
		this->key = key;
		this->prev = NULL;	//NULL是空指针
		this->next = NULL;	//NULL是空指针 
	}
};

int main()
{
	int n,m;
	cin>>n>>m;
	
	node *head,*p,*q;
	head = q = new node(1);
	for(int i=2;i<=n;i++){
	    p = new node(i);
	    p->prev = q;
	    q->next = p;
	    q = p;
	}
	//构成循环链表 
	p->next = head;
	head->prev = p;

	//循环开始前p指向最后一个结点
	for(int i=1;i<=n;i++){
		//m个人依次数数
		for(int j=1;j<=m;j++) p = p->next;
		cout<<p->key<<" ";
		//删除结点p
		p->prev->next = p->next;
		p->next->prev = p->prev; 
	}	
    return 0;
}

登录

注册