数据结构课内实验
实验一：
1、实验名称：一元多项式表示与实现
要求：
（1） 一元多项式的ADT定义；
（2） 存储结构描述；
（3） 一元多项式的操作实现(最低实现)
——初始化；
——一元多项式的输入，输出；
——一元多项式加减法；
（4） 实验报告要提交实现的主要代码；
2、实验名称：表达式求值
要求：
（1） 实验中要求的栈的操作自主实现；
（2） 可以按照自定义格式输入表达式；
（3） 表达式求值可以采用：原表达式求值；
（4） 若采用前缀式或者后缀式求值，可以输入前缀式或者后缀式的字符串即可。
（5） 实验报告要提交实现的主要代码；
代码实现
#include <stdio.h>
#include "stdlib.h"
typedef struct{ // The respresentation of the term, the polynomial term as the linkList's data element
float coef; // coefficient
int expn; // exponent
}elemType; // linkList's object name
typedef struct lNode{ // the single linked list storage structure for linear tables.
elemType *data; // data object
struct lNode *next; // a pointer to the next item
}lNode, *linkList;
typedef struct{
int length; // the number of the term
struct lNode *next; // apointer to the polynomial's first name.
}polynomial;
void printPattern(elemType data);
void initList(polynomial *p) {
p->next = NULL;
p->length = 0;
}
int locateElem(polynomial *p, elemType *e){
linkList cur = p->next;
if(cur == NULL){
return 0;
}
while (cur->next){
if(cur->data->expn == e->expn){
return 1;
}
cur = cur->next;
}
return 0;
}
void insFirst(polynomial *p, elemType *e){
linkList node = (linkList)malloc(sizeof(lNode));
node->next = p->next;
node->data = e;
p->next = node;
p->length++;
}
void creatPolyn2(polynomial *p, int m, const float coeff[], const int expnn[]){
initList(p);
for (int i = 0; i < m; ++i) {
elemType *e;
e = (elemType *) malloc(sizeof(elemType));
// scanf_s("%f%d", &(e->coef), &(e->expn));
e->coef = coeff[i];
e->expn = expnn[i];
if(!locateElem(p, e)){
insFirst(p, e);
}else{
free(e);
}
}
}
void creatPolyn(polynomial *p, int m){
initList(p);
for (int i = 0; i < m; ++i) {
elemType *e;
e = (elemType *) malloc(sizeof(elemType));
scanf_s("%f%d", &(e->coef), &(e->expn));
if(!locateElem(p, e)){
insFirst(p, e);
}else{
free(e);
}
}
}
void printPolyn(polynomial p){
if(p.length == 0){
printf("sorry, the polynomial doesn't have any terms \n");
}else{
printf("y = ");
linkList cur = p.next;
for (int i = 0; i < p.length -1; ++i) {
if (cur->data->coef < 0) {
printf("(%f)x^%d + ", cur->data->coef, cur->data->expn);
} else {
printf("%fx^%d + ", cur->data->coef, cur->data->expn);
}
cur = cur->next;
}
if (cur->data->coef < 0) {
printf("(%f)x^%d\n", cur->data->coef, cur->data->expn);
} else {
printf("%fx^%d\n", cur->data->coef, cur->data->expn);
}
}
}
void printPattern(elemType data) {
}
void destroyPolyn(polynomial *p){
linkList cur = p->next;
while (cur) {
linkList temp = cur;
cur = cur->next;
if (sizeof(&(temp->data))) {
free(temp->data);
}
free(temp);
}
p->length = 0;
p->next = NULL;
}
int polynLength(polynomial p){
return p.length;
}
int cmp(elemType *a, elemType *b){
if(a->expn > b->expn){
return 1;
} else if(a->expn == b->expn){
return 0;
}
return -1;
}
void deltePolynode(polynomial *p, elemType pNode) {
linkList node = p->next;
linkList f = NULL;
while (node){
if(node->data->expn == pNode.expn){
if(f==NULL){
elemType *e = node->data;
free(e);
p->next = node->next;
free(node);
} else{
elemType *e = node->data;
free(e);
f->next = node->next;
free(node);
}
p->length--;
break;
}
f = node;
node = node->next;
}
}
void insTerm(polynomial *p, linkList pNode) {
linkList node = p->next;
linkList f = NULL;
linkList newNode = (linkList)malloc(sizeof(lNode));
newNode->next = NULL;
newNode->data = pNode->data;
while (node){
if(node->data->expn <pNode->data->expn){
if(f==NULL){
newNode->next = p->next;
p->next = newNode;
} else{
newNode->next = node;
f->next = newNode;
}
p->length++;
}
f = node;
node = node->next;
}
}
void addPolyn(polynomial *pa, polynomial *pb) {
linkList qa = pa->next; linkList qb = pb->next;
linkList ha = NULL; linkList hb = NULL;
while (qa && qb){
elemType *a = qa->data; elemType *b = qb->data;
switch (cmp(a, b)) {
case -1:
ha = qa; qa = qa->next;
break;
case 0:
float sum = a->coef + b->coef;
if(sum!=0){
a->coef = sum; ha = qa;
// pa->length++;
}else{
ha->next = qa->next; free(qa);
qa = ha->next;
pa->length--;
}
hb = qb; qb = qb->next;
free(hb);
pb->length--;
break;
case 1:
hb = qb; qb = qb->next;
hb->next = qa;
if(!ha){
pa->next = hb;
ha = hb;
}else{
ha->next = hb;
}
pb->length--;
pa->length++;
break;
}// switch
}//while
if(qb){
int i = 0;
ha->next = qb;
while (qb){
i++;
qb = qb->next;
}
pa->length += i;
}
}
void subPolyn(polynomial *pa, polynomial *pb) {
linkList cur = pb->next;
while (cur){
cur->data->coef = -cur->data->coef;
cur = cur->next;
}
addPolyn(pa, pb);
}
void multiplyPolyn(polynomial *pa, polynomial *pb){
int length = pb->length;
linkList cur = pb->next;
for (int i = 0; i < length; ++i) {
float coefB = cur->data->coef;
int expnB = cur->data->expn;
cur = cur->next;
linkList cura = pa->next;
for (int j = 0; j < pa->length; ++j) {
linkList tem = cur+j;
cura->data->expn += expnB;
cura->data->coef *= coefB;
cura = cura->next;
}
}
destroyPolyn(pb);
}
void testAdd(){
printf("testing addPolyn...\n");
polynomial p1; polynomial p2;
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {6};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {2};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {1};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {3};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {7};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1}; int exp2[]= {13,11,9,8};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1,1}; int exp2[]= {15,13,11,9,8};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1}; int exp2[]= {2,1};
float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1}; int exp2[]= {15, 13, 2,1};
creatPolyn2(&p1, 4, coef, exp); creatPolyn2(&p2, 4, coef2, exp2);
printPolyn(p1); printPolyn(p2);
addPolyn(&p1, &p2);
printPolyn(p1); destroyPolyn(&p1);
printf("---------------------------------------------\n");
}
void testSub(){
printf("testing subPolyn...\n");
polynomial p1; polynomial p2;
float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {6};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {2};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {1};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {3};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {7};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1}; int exp2[]= {13,11,9,8};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1,1}; int exp2[]= {15,13,11,9,8};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1}; int exp2[]= {2,1};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1}; int exp2[]= {15, 13, 2,1};
creatPolyn2(&p1, 4, coef, exp); creatPolyn2(&p2, 1, coef2, exp2);
printPolyn(p1); printPolyn(p2);
// addPolyn(&p1, &p2);
subPolyn(&p1, &p2);
printPolyn(p1); destroyPolyn(&p1);
printf("---------------------------------------------\n");
}
void testPrintPolyn(){
polynomial p1;
float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5};
creatPolyn2(&p1, 4, coef, exp);
printPolyn(p1);
}
void testMultyiPolyn(){
printf("testing multiplyPolyn...\n");
polynomial p1; polynomial p2;
float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {6};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {2};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {1};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {3};
// float coef[] = {5, 5, 4, 3}; int exp[]= {7,5,3,2}; float coef2[] = {5}; int exp2[]= {7};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1}; int exp2[]= {13,11,9,8};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1,1}; int exp2[]= {15,13,11,9,8};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1}; int exp2[]= {2,1};
// float coef[] = {5, 5, 4, 3}; int exp[]= {11,9,7,5}; float coef2[] = {1,1,1,1}; int exp2[]= {15, 13, 2,1};
creatPolyn2(&p1, 4, coef, exp); creatPolyn2(&p2, 1, coef2, exp2);
printPolyn(p1); printPolyn(p2);
// addPolyn(&p1, &p2);
multiplyPolyn(&p1, &p2);
printPolyn(p1); destroyPolyn(&p1);
printf("---------------------------------------------\n");
}
int main() {
testAdd();
testSub();
testMultyiPolyn();
printf("test successfully finish.");
return 0;
}