西南交大大数据结构实验资料报告材料

目录

实验一 一元稀疏多项式的计算 ................................................... 2 实验三 停车场管理 ............................................................. 11 实验四 算术表达式求值 ......................................................... 18 实验七 哈夫曼编/译码器实验指导书 ............................................. 25 实验八 最短路径实验指导书 .................................................... 36 实验十 部排序算法比较实验指导书 .............................................. 45

1

实验一 一元稀疏多项式的计算

#include #include #include typedef struct Item{ double coef; int expn; struct Item *next; }Item,*Polyn;

#define CreateItem(p) p=(Item *)malloc(sizeof(Item)); #define DeleteItem(p) free((void *)p);

/************************************************************/ /* 判断选择函数 */ /************************************************************/ int Select(char *str) { char ch;

printf(\ printf(\ do{ ch=getch();

}while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');

printf(\

if(ch=='Y'||ch=='y') return(1); else return(0); }

/************************************************************/ /* 插入位置定位函数 */ /**************************************************************/ int InsertLocate(Polyn h,int expn,Item **p) { Item *pre,*q; pre=h; q=h->next;

while(q&&q->expnnext;

}

if(!q)

{ *p=pre;

return(1); }

else if(q->expn==expn) { *p=q;

return(0); }

else { *p=pre;

return(-1);

} }

/************************************************************/ /* 插入结点函数 */ /************************************************************/ void insert(Item *pre,Item *p) { p->next=pre->next; pre->next=p; }

/************************************************************/ /* 输入多项式 */ /************************************************************/ Polyn Input(void) {double coef; int expn,flag;

Item *h,*p,*q,*pp; CreateItem(h);//产生头结点 h->next=NULL;

printf(\ while(1)

{ printf(\ scanf(\

printf(\

scanf(\输入多项式的系数和指数

if(expn==-1) break; //若指数为－1，表示输入结束 if(InsertLocate(h,expn,&pp))//返回值非0表示插入新结点 { CreateItem(p); p->coef=coef; p->expn=expn;

insert(pp,p); //按顺序在插入 }

else if(Select(\

pp->coef=coef; //指数相同，替换系数

} return h; }

/************************************************************/ /* 撤消多项式 */ /************************************************************/ void Destroy(Polyn h)