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

}//end of for

cout<>i; //输入要删除的位置 if(i<= LListNodeNum)

{ cout<<\数据\已经被删除\ for(j=1;jnext; cout<data<<\ \输出新的单链表 }//结束for

cout<

else cout<<\ getch();

}//end of main() function

【实验结果】

1、写出实验的总结与体会，要简洁、真实、深刻；忌空话、套话

10

2、单向链表和双向链表在实现时的区别

3、单向链表如何修改实现循环链表

11

实验二 链表的应用（二）栈的应用

【实验内容】

1、实现单向链栈的抽象数据类型

2、实现单向链栈的建立、销毁、取栈顶元素、压栈、弹栈的运算 3、给出包含括号和+、-、*、\\四则运算的运算符优先级表 4、创建运算符栈和运算数栈

5、实现有一定通用性的程序，实现一个四则运算表达式的求解 6、设计测试用的运算表达式，通过键盘输入进行测试 【实验方法与步骤】

1、构造空链式队列算法

# include # include # include

# define MAXQSIZE 100 # define OK 1 # define ERROR 0

typedef int QElemType;

typedef struct SqQueue//创建一个头结点 { QElemType *base; int front; int rear; }SqQueue;

int InitQueue(SqQueue &Q)

{ Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)//存储空间分配失败 { cout<

Q.front=Q.rear=0; return (OK); } //InitQueue() end

void main() //main function { SqQueue Q;

cout<

12

cout<

2、销毁链式队列算法

# include # include # include

# define MAXQSIZE 100 # 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 EnQueue(LinkQueue &Q,QElemType e) //构造队列 { QNode *p;

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

{ cout<

p->data=e;

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

Q.rear->next=p; Q.rear=p;

13

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

int DestroyQueue(LinkQueue &Q)//销毁队列Q { while(Q.front)

{ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }

return (OK);

} //DestroyQueue() end

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

LinkQueue Q; QNode *q;

Q.front=Q.rear=NULL;

cout<

cout<

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

cout<

for(q=Q.front;q!=NULL;q=q->next) cout<data<<\ \ DestroyQueue(Q); //开始销毁 cout<

3、将元素压入链式栈算法

# include

14