（1）双向链表
【1】头插法
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
ElemType data;
Node *prev,*next;
};
Node* initList(){
Node* head=new Node;
head->data=0;
head->next=NULL;
return head;
}
int insertHead(Node *L,ElemType e){
Node *p=new Node;
p->data=e;
p->prev=L;
p->next=L->next;
if(L->next!=NULL){
L->next->pre*** }
L->next=p;
return true;
}
void listNode(Node* L)
{
Node *p=L->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
Node* list=initList();
insertHead(list,10);
insertHead(list,20);
insertHead(list,30);//头插法
listNode(list);
}
【2】尾插法
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
ElemType data;
Node *prev,*next;
};
Node* initList(){
Node* head=new Node;
head->data=0;
head->next=NULL;
return head;
}
int insertHead(Node *L,ElemType e){
Node *p=new Node;
p->data=e;
p->prev=L;
p->next=L->next;
if(L->next!=NULL){
L->next->pre*** }
L->next=p;
return true;
}
Node* get_tail(Node*L){
Node *p=L;
while(p->next!=NULL){
p=p->next;
}
return p;
}
Node* insertTail(Node *tail,ElemType e)
{
Node *p=new Node;
p->data=e;
p->prev=tail;
tail->next=p;
p->next=NULL;
return p;
}
void listNode(Node* L)
{
Node *p=L->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
Node* list=initList();
Node* tail=get_tail(list);//头插法
tail=insertTail(tail,40);
tail=insertTail(tail,30);//尾插法
tail=insertTail(tail,20);
tail=insertTail(tail,10);
listNode(list);
}
【3】在指定位置插入数据
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
ElemType data;
Node *prev,*next;
};
Node* initList(){
Node* head=new Node;
head->data=0;
head->next=NULL;
return head;
}
int insertHead(Node *L,ElemType e){
Node *p=new Node;
p->data=e;
p->prev=L;
p->next=L->next;
if(L->next!=NULL){
L->next->pre*** }
L->next=p;
return true;
}
Node* get_tail(Node*L){
Node *p=L;
while(p->next!=NULL){
p=p->next;
}
return p;
}
Node* insertTail(Node *tail,ElemType e)
{
Node *p=new Node;
p->data=e;
p->prev=tail;
tail->next=p;
p->next=NULL;
return p;
}
void listNode(Node* L)
{
Node *p=L->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int insertNode(Node *L,int pos,ElemType e)
{
Node *p=L;
int i=0;
while(i<pos-1){
p=p->next;
i++;
if(p==NULL){
return 0;
}
}
Node *q=new Node;
q->data=e;
q->pre*** q->next=p->next;
p->next=q;
p->next->prev=q;
return true;
}
int main()
{
Node* list=initList();
Node* tail=get_tail(list);//头插法
tail=insertTail(tail,40);
tail=insertTail(tail,30);//尾插法
tail=insertTail(tail,20);
tail=insertTail(tail,10);
insertNode(list,2,55);//在指定位置插入数据
listNode(list);
}
【4】删除节点
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node
{
ElemType data;
Node *prev,*next;
};
Node* initList(){
Node* head=new Node;
head->data=0;
head->next=NULL;
return head;
}
int insertHead(Node *L,ElemType e){
Node *p=new Node;
p->data=e;
p->prev=L;
p->next=L->next;
if(L->next!=NULL){
L->next->pre*** }
L->next=p;
return true;
}
Node* get_tail(Node*L){
Node *p=L;
while(p->next!=NULL){
p=p->next;
}
return p;
}
Node* insertTail(Node *tail,ElemType e)
{
Node *p=new Node;
p->data=e;
p->prev=tail;
tail->next=p;
p->next=NULL;
return p;
}
void listNode(Node* L)
{
Node *p=L->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int insertNode(Node *L,int pos,ElemType e)
{
Node *p=L;
int i=0;
while(i<pos-1){
p=p->next;
i++;
if(p==NULL){
return 0;
}
}
Node *q=new Node;
q->data=e;
q->pre*** q->next=p->next;
p->next=q;
p->next->prev=q;
return true;
}
void freeList(Node *L)
{
Node *p=L->next;
Node *q;
while(p!=NULL){
q=p->next;
delete p;
p=q;
}
L->next=NULL;
}
int deleteNode(Node* L,int pos)
{
Node *p=L;
int i=0;
while(i<pos-1){
p=p->next;
i++;
if(p==NULL){
return 0;
}
}
if(p->next==NULL){
cout<<"删除错误"<<endl;
return 0;
}
Node *q=p->next;
p->next=q->next;
q->next->pre*** delete q;
return true;
}
int main()
{
Node* list=initList();
Node* tail=get_tail(list);//头插法
tail=insertTail(tail,40);
tail=insertTail(tail,30);//尾插法
tail=insertTail(tail,20);
tail=insertTail(tail,10);
insertNode(list,2,55);//在指定位置插入数据
deleteNode(list,3);//删除指定位置的节点
listNode(list);
}
【5】其他的都和单项链表一样
【6】栈的顺序结构实现
#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Stack{
ElemType data[MAXSIZE];
int top;
};
void initStack(Stack *s){
s->top=-1;
}
int isEmpty(Stack *s)
{
if(s->top==-1){
cout<<"空的"<<endl;
return true;
}
else
{
return false;
}
}
int push(Stack *s,ElemType e)
{
if(s->top>=MAXSIZE-1){
cout<<"满了"<<endl;
return false;
}
s->top++;
s->data[s->top]=e;
return true;
}
ElemType pop(Stack *s,ElemType *e)
{
if(s->top==-1)
{
cout<<"空的"<<endl;
return false;
}
*e=s->data[s->top];
s->top--;
return true;
}
int getTop(Stack *s,ElemType *e)
{
if(s->top==-1){
cout<<"空的"<<endl;
return 0;
}
*e=s->data[s->top];
return 0;
}
int main()
{
Stack s;
initStack(&s);//初始化
push(&s,90);
push(&s,80);
push(&s,70);//压栈
ElemType e;
pop(&s,&e);//出栈
cout<<e<<endl;
getTop(&s,&e);//获得栈顶元素
cout<<e<<endl;
}
【7】栈的顺序结构-动态内存分配
只有初始化和结构体改变了
#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Stack{
ElemType *data;
int top;
};
Stack* initStack(){
Stack *s=new Stack;
s->data=new ElemType[MAXSIZE];
s->top=-1;
return s;
}
int isEmpty(Stack *s)
{
if(s->top==-1){
cout<<"空的"<<endl;
return true;
}
else
{
return false;
}
}
int push(Stack *s,ElemType e)
{
if(s->top>=MAXSIZE-1){
cout<<"满了"<<endl;
return false;
}
s->top++;
s->data[s->top]=e;
return true;
}
ElemType pop(Stack *s,ElemType *e)
{
if(s->top==-1)
{
cout<<"空的"<<endl;
return false;
}
*e=s->data[s->top];
s->top--;
return true;
}
int getTop(Stack *s,ElemType *e)
{
if(s->top==-1){
cout<<"空的"<<endl;
return 0;
}
*e=s->data[s->top];
return 0;
}
int main()
{
Stack *s=initStack();//初始化
push(s,90);
push(s,80);
push(s,70);//压栈
ElemType e;
pop(s,&e);//出栈
cout<<e<<endl;
getTop(s,&e);//获得栈顶元素
cout<<e<<endl;
}
【8】栈的链式结构
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Stack{
ElemType data;
Stack *next;
};
Stack* initStack()
{
Stack *s=new Stack;
s->data=0;
s->next=NULL;
return s;
}
int isEmpty(Stack *s)
{
if(s->next==NULL)
{
cout<<"空的"<<endl;
return 1;
}
else
{
return 0;
}
}
int push(Stack *s,ElemType e)
{
Stack *p=new Stack;
p->data=e;
p->next=s->next;
s->next=p;
return true;
}
int pop(Stack *s,ElemType *e)
{
if(s->next==NULL)
{
cout<<"空的"<<endl;
return 0;
}
*e=s->next->data;
Stack *q=s->next;
s->next=q->next;
delete q;
return true;
}
int getTop(Stack *s,ElemType *e)
{
if(s->next==NULL)
{
cout<<"空的"<<endl;
return 0;
}
*e=s->next->data;
return 1;
}
int main()
{
Stack *s=initStack();
push(s,10);
push(s,20);
push(s,30);
ElemType e;
pop(s,&e);
cout<<e<<endl;
getTop(s,&e);
cout<<e<<endl;
}
【9】队列顺序结构
（1）栈内存中的形式
#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Queue{
ElemType data[MAXSIZE];
int front;
int rear;
};
void initQueue(Queue *Q){
Q->front=0;
Q->rear=0;
}
int isEmpty(Queue *Q){
if(Q->front==Q->rear){
cout<<"空的"<<endl;;
return true;
}
else
{
return false;
}
}
ElemType dequeue(Queue *Q)
{
if(Q->front==Q->rear)
{
cout<<"空的"<<endl;
return 0;
}
ElemType e=Q->data[Q->front];
Q->front++;
return e;
}
int queueFull(Queue *Q)
{
if(Q->front>0)
{
int step=Q->front;
for(int i=Q->front;i<=Q->rear;i++)
{
Q->data[i-step]=Q->data[i];
}
Q->front=0;
Q->rear=Q->rear-step;
return true;
}
else
{
cout<<"真的满了"<<endl;
return false;
}
}
int equeue(Queue *Q,ElemType e)
{
if(Q->rear>=MAXSIZE)
{
if(!queueFull(Q))
{
return 0;
}
}
Q->data[Q->rear]=e;
Q->rear++;
return 1;
}
int getHead(Queue *Q,ElemType *e)
{
if(Q->front==Q->rear)
{
cout<<"空的"<<endl;
return 0;
}
*e=Q->data[Q->front];
return 1;
}
int main()
{
Queue q;
initQueue(&q);
equeue(&q,10);
equeue(&q,20);
equeue(&q,30);
equeue(&q,40);//队列入队
cout<<dequeue(&q)<<endl;
cout<<dequeue(&q)<<endl;//出队
ElemType e;
getHead(&q,&e);//获取队头元素
cout<<e<<endl;
}
（2）堆内存的形式
#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Queue{
ElemType *data;
int front;
int rear;
};
Queue * initQueue(){
Queue *q=new Queue;
q->data=new ElemType[MAXSIZE];
q->front=0;
q->rear=0;
return q;
}
int isEmpty(Queue *Q){
if(Q->front==Q->rear){
cout<<"空的"<<endl;;
return true;
}
else
{
return false;
}
}
ElemType dequeue(Queue *Q)
{
if(Q->front==Q->rear)
{
cout<<"空的"<<endl;
return 0;
}
ElemType e=Q->data[Q->front];
Q->front++;
return e;
}
int queueFull(Queue *Q)
{
if(Q->front>0)
{
int step=Q->front;
for(int i=Q->front;i<=Q->rear;i++)
{
Q->data[i-step]=Q->data[i];
}
Q->front=0;
Q->rear=Q->rear-step;
return true;
}
else
{
cout<<"真的满了"<<endl;
return false;
}
}
int equeue(Queue *Q,ElemType e)
{
if(Q->rear>=MAXSIZE)
{
if(!queueFull(Q))
{
return 0;
}
}
Q->data[Q->rear]=e;
Q->rear++;
return 1;
}
int getHead(Queue *Q,ElemType *e)
{
if(Q->front==Q->rear)
{
cout<<"空的"<<endl;
return 0;
}
*e=Q->data[Q->front];
return 1;
}
int main()
{
Queue *q=initQueue();
equeue(q,10);
equeue(q,20);
equeue(q,30);
equeue(q,40);//队列入队
cout<<dequeue(q)<<endl;
cout<<dequeue(q)<<endl;//出队
ElemType e;
getHead(q,&e);//获取对头元素
cout<<e<<endl;
}
【10】循环队列（普通队列的效率太慢了，才引入循环队列）
（1）代码是存在bug的无论如何都会空出一个格，如图
#define MAXSIZE 100
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Queue{
ElemType *data;
int front;
int rear;
};
Queue * initQueue(){
Queue *q=new Queue;
q->data=new ElemType[MAXSIZE];
q->front=0;
q->rear=0;
return q;
}
int isEmpty(Queue *Q){
if(Q->front==Q->rear){
cout<<"空的"<<endl;;
return true;
}
else
{
return false;
}
}
ElemType dequeue(Queue *Q)
{
if(Q->front==Q->rear)
{
cout<<"空的"<<endl;
return 0;
}
ElemType e=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return e;
}
int equeue(Queue *Q,ElemType e)
{
if((Q->rear+1)%MAXSIZE==Q->front)
{
cout<<"满了"<<endl;
return 0;
}
Q->data[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXSIZE;
return 1;
}
int getHead(Queue *Q,ElemType *e)
{
if(Q->front==Q->rear)
{
cout<<"空的"<<endl;
return 0;
}
*e=Q->data[Q->front];
return 1;
}
int main()
{
Queue *q=initQueue();
equeue(q,10);
equeue(q,20);
equeue(q,30);
equeue(q,40);//队列入队
cout<<dequeue(q)<<endl;
cout<<dequeue(q)<<endl;//出队
ElemType e;
getHead(q,&e);//获取对头元素
cout<<e<<endl;
}
【11】队列的链式结构
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct QueueNode
{
ElemType data;
QueueNode *next;
};
struct Queue{
QueueNode *front;
QueueNode *rear;
};
Queue* initQueue(){
Queue *q=new Queue;
QueueNode *node=new QueueNode;
node->data=0;
node->next=NULL;
q->front=node;
q->rear=node;
return q;
}
int isEmpty(Queue *q)
{
if(q->front==q->rear)
{
return true;
}
else
{
return false;
}
}
void equeue(Queue *q,ElemType e){
QueueNode *node=new QueueNode;
node->data=e;
node->next=NULL;
q->rear->next=node;
q->rear=node;
}
int dequeue(Queue *q,ElemType *e)
{
QueueNode *node=q->front->next;
*e=node->data;
q->front->next=node->next;
if(q->rear==node)
{
q->rear=q->front;
}
delete node;
return true;
}
ElemType getFront(Queue *q)
{
if(isEmpty(q))
{
cout<<"空的"<<endl;
return 0;
}
return q->front->next->data;
}
int main()
{
Queue *q=initQueue();
equeue(q,10);
equeue(q,20);
equeue(q,30);
equeue(q,40);
equeue(q,50);//入队
ElemType e;
dequeue(q,&e);//出队
cout<<e<<endl;
cout<<getFront(q)<<endl;//获取队头元素
}
京公网安备 11010502036488号