带表头的单链表应用——多项式

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define Notpresent 4
#define Duplicate 5

typedef int ElemType;
typedef int Status;

typedef struct PNode
{
	ElemType ceof;
	ElemType exp;
	struct PNode *link;
}PNode;

typedef struct 
{
	struct PNode *head;
}polynominal;

Status Init(polynominal *p){
	p->head = (PNode *)malloc(sizeof(PNode));
	p->head->exp = -1;
	p->head->link = NULL;
	return OK;
}

Status Create(polynominal *p){
	PNode *pn = NULL,*q=NULL,*pre=NULL;
    Init(p);
	//p->head = (PNode *)malloc(sizeof(PNode));
	//p->head->exp = -1;
	//p->head->link = NULL;
	for (;;)   // <==>while(1)
	{
		pn = (PNode *)malloc(sizeof(PNode));
		printf("ceof:\n");
		scanf("%d",&pn->ceof);
		printf("exp:\n");
		scanf("%d",&pn->exp);
		if (pn->exp < 0) {printf("End the input\n"); break;}
		pre = p->head;						//pre从链表头开始
		q=p->head->link;
		while(q && q->exp > pn->exp){		//pn为当前结点,q为链表中结点
			pre = q;						//
			q = q->link;
		}
		pn->link = q;						// 在pre和q之间插入pn,(q为null时,相当于末尾插入pn)
		pre->link = pn;						// pre => pn => q
	}
	return OK;
}

Status Sort(polynominal *L){		//从大到小
	PNode *p=L->head,*pre=NULL;
	PNode *r=p->link;
	p->link = NULL;
	p=r;				//r保存原来的结点顺序
	while(p != NULL){	
		r = p->link;	//r继续取下一个结点
		pre = L->head;	//pre重新构造L,从头开始循环
		while(pre->link != NULL && pre->link->exp < p->exp)  
            // 如果链表非空 且 新链表与当前结点数值比较
			pre = pre->link;	
        //如果当前要插入的结点值大于循环中当前已排序结点,则取已排序链表下一个结点继续比较
		p->link = pre->link;   
        //找到p要插入的位置后,插入:若3<pre=5<bigger=7<8,p=6,则 p=>bigger
		pre->link = p;			// pre=>p,插入即可
		p=r;					// p继续取下个结点依次按原来顺序循环遍历原来链表
	}
	return 	OK;
}


Status Add(polynominal *px,polynominal *qx){	//目的:将q改成p+q
	PNode *q1=qx->head, *p=px->head->link;		//q1指向qx表头结点
	PNode *q=q1->link;							//p指向多项式px第一个结点,q指向qx第一个
	PNode *temp = NULL;							//q1是q前驱
	while( q && p){
		while( p->exp < q->exp ){				//找到qx中 大于等于q指数项的项,q不断右移
			q1 = q;
			q = q->link;
		}
		if (p->exp == q->exp ){
			q->ceof = q->ceof + p->ceof;
			if (q->ceof == 0){
				q1->link = q->link;				//释放当前q的内存
				free(q);
				q = q1->link;
				p = p->link;
			}else{								//p\q都右移
				q1 = q;							//q1
				q = q->link;
				p = p->link;
			}
		}else{		//p->exp > q->exp 
			temp = (PNode * )malloc(sizeof(PNode));
			temp->ceof = p->ceof;
			temp->exp = p->exp;
			temp->link = q1->link;
			q1->link = temp;
			p = p->link;
		}
	}
	return OK;
}

void Output(polynominal *p){
	PNode *q = p->head->link;
	int last = 0;
	while( q!=NULL ){
		if(q->link == NULL) last =1;
		printf("%dx^%d", q->ceof,q->exp);
		if(!last) printf("+");		//此处注意个+的小细节
		q = q->link;
	}
	printf("\n");
}

void Destory(polynominal *p){
	PNode *q = NULL;
	while(p->head){			//不断删除head所指向的内存,直到head被释放
		q = p->head->link;	
		free(p->head);
		p->head = q;
	}
}

/***********合并同类项*****************/
/***********合并即free*****************/
Status unify(polynominal *t)
{
    PNode *p=NULL;
    PNode *q=NULL;
    PNode *last=NULL;
    PNode *tmp;
    //while(p->link != NULL){			
    for(p=t->head->link;p!=NULL;p=p->link){ //选择
        last = p;
        for(q=last->link; q!=NULL ; ){  //q指针向后推移指向下一结点
	        if(q->exp == p->exp){			//相等计算
	            p->ceof += q->ceof;		//q为 滑动项
	            tmp = q->link;
	            last->link = q->link;     //last保存上一个q   
	            free(q);				// 吧q的空间释放掉
	            q= tmp;
	        }else{
		        last= q;
		        q=q->link;}				//如果不相等就判断下一个
        }
    }
    return OK;
}



polynominal Multiply(polynominal *px,polynominal *qx){
	PNode *p = px->head;
	PNode *q = qx->head;
	PNode *x = NULL;
	PNode *tmp = NULL;
	polynominal newpoly;
	Init(&newpoly);
	x = newpoly.head;
	for (p=px->head->link; p!=NULL; p=p->link){
		for (q=qx->head->link; q!=NULL; q=q->link){
			tmp = (PNode*)malloc(sizeof(PNode));
			tmp->ceof = p->ceof * q->ceof;
			tmp->exp = p->exp + q->exp;
			tmp->link = x->link;	//新生成的结点指向上一个生成的结点的地址
			x->link = tmp;			//使链表记录当前tmp结点
			x = x->link;			//取下一个结点
		}
	}
	unify(&newpoly);
	Sort(&newpoly);
	return newpoly;
}

int main()
{
	polynominal p,q;
	polynominal mul;
	Create(&p);
	Output(&p);
    // printf("After unify:\n");	Unify
    // unify(&p);
    // Output(p);

	Create(&q);			
	Output(&q);

	// Add(&p,&q);					ADD
	// printf("q:");
	// Output(q);
	printf("After Multiplied:\n");
	mul = Multiply(&p,&q);
	Output(&mul);

	system("pause");
	return 0;
}
//其中Sort,unify,add,multiply,需要捉摸一下

(一)实验中遇到的主要问题及解决方法

1.题目二，带表头的单链表在插入时出现了点问题，书上给出的方法是错的，且是C++代码。于是在尝试理解他的想法及每步Debug中终于写出了正确的代码。（L->head->link = NULL,其中L->head->data 不填）

2.题目二中带表头节点的单链表中插入时for( j=0;j<=i; j++) 和之前j<i以及删除时for( j=0;j<=i-1; j++) 和之前j<i-1有很大不同,通过debug知道了是为了略过第一个表头节点。

3.逆置过程中,为了不动表头,略过第一个表头结点时出现了点麻烦.并且在第一个元素逆置后指向NULL,第二个结点指向第一个结点时没有想明白,后来才想到了先让P=NULL,然后记录上一个结点就能达到效果了.同时还有个问题是一直没有保存原来链表的顺序,再因为P=NULL导致会访问到非法内存而程序崩溃

4.合并同类项的过程中,使用了选择排序类似的思想,但是在里层for(q=last->link; q!=NULL ; )出了问题,一开始写成 for(q=last->link; q!=NULL ; q=q->link)但是如果指数相等,q就会被free掉,此时q=q->link就会出问题

（二）实验心得

1.题目一中，顺序表是malloc动态申请的空间，是连续的，可以直接通过下标访问。

2.题目二中,带表头单链表和不带表头单链表,在删除和插入时的循环条件不同要注意.及初始化时带表头的L->head->link = NULL; 与 无表头的 L->first = NULL;

3.Debug过程中F10和F11的区别,在malloc和free处按F11会进入malloc函数、free函数的汇编的运行过程

4.排序和逆置时都要有个指针记住原来链表的顺序,然后才能再依次按顺序进行.

5.理清要做的事,再下手写代码,画图有时很重要.