数据结构习题集与实验指导

.

tmp1->next=tmp2; tmp1=tmp1->next; }

return pointer; }

link concatenate(link pointer1,link pointer2) { link tmp; tmp=pointer1; while(tmp->next) tmp=tmp->next; tmp->next=pointer2; return pointer1; }

void main(void)

{ int arr1[]={3,12,8,9,11}; link ptr;

ptr=create_list(arr1,5); selection_sort(ptr,5); }

实验二 栈和队列的应用

[实验目的]：掌握栈和队列的结构定义和特性；

掌握栈和队列的基本操作以及栈和队列在程序设计中的应用。 [实验题目]：

1、栈实现数制转换

#include #include #include

typedef int SElemType; #include \

Status visit(SElemType * e) {

printf(\ \}

void conversion() {

pSqStack S; SElemType e; int n;

InitStack(&S);

printf(\ scanf(\ if(n<0)

.

.

{

printf(\ return; }

if(!n) Push(S,0); while(n){

Push(S,n%8); n=n/8; }

printf(\ \ while(!StackEmpty(*S)){ Pop(S,&e); printf(\ } }

main() {

printf(\ conversion(); getch();

printf(\}

2、栈实现单行编辑 #include #include #include #include

#define EOFILE '`'

typedef char SElemType; #include \

Status visit(SElemType * e) {

printf(\}

char OP[10]={'+','-','*','/','(',')','#'}; int precede[7][7]={ 1,1,2,2,2,1,1, 1,1,2,2,2,1,1, 1,1,1,1,2,1,1, 1,1,1,1,2,1,1, 2,2,2,2,2,3,0, 1,1,1,1,0,1,1, 2,2,2,2,2,0,3}; int In(char c,char *op) {

int i=0;

.

.

while(I<7) if(c==op[i++]) return 1; return 0; }

char Precede(char op,char c) {

int pos_op; int pos_c; int i;

for(i=0;i<7; i++) {

if(op==OP[i]) pos_op=i; if(c==OP[i]) pos_c=i; }

switch(precede[pos_op][pos_c]) {

case 1: return '>'; case 2: return '<'; case 3: return '='; } }

char Operate(int a,char theta,int b) {

switch(theta) {

case '+':return a+b-'0'; case '-':return a-b+'0';

case '*':return (a-'0')*(b-'0')+'0'; case '/':return (a-'0')/(b-'0')+'0'; } }

char EvaluateExpression() {

SqStack *OPND,*OPTR; char c,x,theta; char a,b;

InitStack(&OPTR); Push(OPTR,'#'); InitStack(&OPND); c=getchar();

while(c!='#'||GetTop(*OPTR)!='#') {

if(!In(c,OP)) {Push(OPND,c);c=getchar();} else switch(Precede(GetTop(*OPTR),c))

.

.

{ case '<': Push(OPTR,c); c=getchar(); break; case '=': Pop(OPTR,&x); c=getchar(); break; case '>': Pop(OPTR,θ); Pop(OPND,&b); Pop(OPND,&a); Push(OPND,Operate(a,theta,b)); break; } }

c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; }

main() {

char i;

printf(\ i=EvaluateExpression();

printf(\ \ printf(\

printf(\}

实现栈的头文件： #include \#define OVERFLOW -1

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int Status; struct STACK {

SElemType *base; SElemType *top; int stacksize; };

typedef struct STACK SqStack; typedef struct STACK *pSqStack;

.