中北大学 算法与数据结构实验报告(5)

{//插入元素e为队列Q的新的队列为元素 QNode *p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)

{ cout<

p->data=e; //将值e放入新结点的数据域 p->next=NULL; //令新结点的指针域为空 if(Q.front==NULL) { Q.front=Q.rear=p; return (OK); }

Q.rear->next=p; //将新结点插入到队列Q的尾 Q.rear=p; //修改队列Q的队尾指针 return (OK); } //EnQueue() end

void main() //main() function { int i,e=1;

LinkQueue Q; QNode *q;

InitQueue(Q); //call InitQueue() cout<

cout<

{ cout<<\请输入队列当中的数据 (如58到0或exit):\ cin>>e; if(e)

EnQueue(Q,e); //开始插入元素 }

cout<

for(q=Q.front->next;q!=NULL;q=q->next) cout<data<<\ \

cout<

20

7、在链式队列头删除旧元素算法

# include # include # include

# define OK 1 # define ERROR 0

typedef int QElemType;

typedef struct QNode //define structure QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr;

typedef struct LinkQueue //define structure LinkQueue { QueuePtr front; QueuePtr rear; }LinkQueue;

int InitQueue(LinkQueue &Q) {//构造一个队列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)

{ cout<

Q.front->next=NULL; return (OK); } //InitQueue() end

int EnQueue(LinkQueue &Q,QElemType e) { QNode *p;

p=(QueuePtr)malloc(sizeof(QNode));

21

if(!p)

{ cout<

p->data=e;

p->next=NULL; if(Q.front==NULL) { Q.front=p; Q.rear=p; return (OK); }

Q.rear->next=p; Q.rear=p; return (OK); } //EnQueue() end

int DeQueue(LinkQueue &Q,QElemType &e) {//如果队列空，返回ERROR；如果队列不空，

//删除Q的队列头元素，用e返回其值，并返回OK if(Q.front==Q.rear)

{ cout<

QNode *p;

p=Q.front->next; //令p指向队列Q的头 e=p->data; //将队头结点的值取出并放入e Q.front->next=p->next; //修改队头指针 free(p); //释放队头元素所占空间 return (OK); } //DeQueue() end

void main() //main() function { int i,e=1;

LinkQueue Q; QNode *q; InitQueue(Q);

cout<

cout<

{ cout<<\请输入队列中的元素(如58到0或exit):\ cin>>e; if(e) EnQueue(Q,e); //构造队列 }

22

cout<<\原来的队列为:\

for(q=Q.front->next;q!=NULL;q=q->next) cout<data<<\ \ if(DeQueue(Q,e)) //开始删除 { cout<

for(q=Q.front->next;q!=NULL;q=q->next) cout<data<<\ \ }

cout<

8、创建运算符栈

# include # include # include

# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType;

typedef struct //define structure SqStack() { SElemType *base; SElemType *top; int stacksize; }SqStack;

int InitStack(SqStack &S) //InitStack() sub-function

{ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)

{ cout<

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

23

return (OK); } //InitStack() end

void main() //main() function { SqStack S;

cout<

9、创建运算符数栈

#include #include #include #include

#define MAXSIZE 10

#define DUSTACKSIZE MAXSIZE typedef int SElemType ; typedef struct DuSqStack

{ SElemType data[MAXSIZE-1]; //array[0..MAXSIZE-1] for the DuSqStack int top1; //top1 is the pointer of DuSqStack S1 int top2; //top2 is the pointer of DuSqStack S2 int flag; //if flag variable=1 then operate S1 }DuSqStack; //else if flag=2 then operate S2

void InitDuSqStack(DuSqStack &S) //InitDuSqStack() function { S.top1=1; S.top2=MAXSIZE-2; //Initialize the Pointers of DuSqStack }//end of InitDuSqStack() function

int DuSqStackPush(DuSqStack &S,SElemType x) //DuSqStackPush() function { //S is a shared stack this function will push x into stack S cout<<\ cin>>x; if(S.top1+1==S.top2) //if the two stack are full, then return error

24