数据结构实验1——线性表及多项式的运算

链表操作

#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 Status;
typedef int ElemType;
typedef struct Node{
	ElemType elem;
	struct Node *link;
}Node;

typedef struct {
	struct Node* first;
	int n;

}SingleList;

SingleList list;		//声明全局的



Status Init(SingleList *L){
	L->first = NULL;
	L->n = 0;
	return OK;
}

Status Find(SingleList L,int i,ElemType *x){
	Node *p;
	int j;
	if (i<0 || i> L.n-1) return ERROR;
	p = L.first;
	for (j = 0; j < i; ++i) p=p->link;
		*x = p->elem;
	return OK;
}

Status Insert(SingleList *L,int j,ElemType x){
	Node *p,*q;
	int i;
	if(j<-1 || j> L->n) return ERROR;
	p = L->first;
	for(i=0;i<j;i++) p=p->link;		//p==>a(i-1)
	
	q = (Node *)malloc(sizeof(Node));
	q->elem = x;
	if (j>-1)
	{
		q->link = p->link;		// a(i-1)==>???  ===>  a(i)->???
		p->link = q ;			//	a(i-1)->a(i)
	}else
	{
		q->link = L->first;
		L->first = q;
	}
	L->n++;
	return OK;
}

Status Delete(SingleList *L,int j){
	int i;
	Node *p,*q;
	if(!L->n) return ERROR;
	if ( j<0 || j>L->n) return ERROR;
	q = L->first;
	p = L->first;
	for(i=0;i<j-1;i++) q = q->link;			//q指向 a(i-1)
		if (i==0)
			L->first = L->first->link;
		else{
			p = q->link;					//此时p指向a(i)
			q->link = p->link;				//将q指向a(a+1)
		}
		free(p);
		L->n -- ;
		return OK;
}

Status Output(SingleList L){
	Node *p;
	if(!L.n) return ERROR;
	p = L.first;
	while(p){
		printf("%d ",p->elem );
		p = p->link;
	}
	return OK;
}

void Destory(SingleList *L){
	Node *p;
	while(L->first){
		p = L->first->link;  //保存后继节点地址,防止断链
		free(L->first);		//释放first节点所指节点的存储空间   从前往后释放
		L->first = p;
	}			
}


int main(){
	int i,x;

	Init(&list);
	for (i = 0; i < 9; ++i)
		Insert(&list,i-1,i);
	printf("the linked list is :");
	Output(list);

	Delete(&list,1);
	printf("\nafter deleting the list is:");
	Output(list);
	

	Find(list,0,&x);
	printf("\nthe value is %d\n",x );

	Destory(&list);

	system("pause");
	return 0;
}

带表头节点的单链表

#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 Node{
	ElemType elem;
	struct Node *link;
}Node;

typedef struct {
	struct Node* head;
	int n;
}Headlist;

Status Init(Headlist *L){
	L->head = (Node*)malloc(sizeof(Node));
	if(!L->head) return ERROR;
	L->head->link = NULL;
    //注意到这边没有对L->head->element作设置,因为不会用到
	L->n = 0;
	return OK;
}

Status Sort(Headlist *L){
	Node *p=L->head,*pre=NULL;
	Node *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->elem < p->elem)  
        // 如果链表非空 且 新链表与当前结点数值比较
			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 deleleab(Headlist *L, int a,int b){ 
     Node *q = L->head,*p=L->head->link;  // q为上一个,p为当前的
     while( p )
     	if(p->elem >= a && p->elem <= b)
     {
     	q->link = p->link;		// 1 - 2 - 3  1==>3,1的指针域指向3
     	free(p);				//释放2
     	p = q->link;			// 当前的指针变成3
     }else{
        p = p->link;
        q = p->link;
     }     
     return OK; 
}

/*****
思路为: 将顺序遍历的结点不断插入为L->head->link
******/
Status Converse(Headlist *L){
	Node *p = NULL,*cur= NULL; 
	Node *q = L->head->link;
    if(L->head && L->head->link){		//如果表不存在或是为空,则return ERROR
	while( q != NULL )			//q按照原来的顺序依次遍历各结点	
	{
		cur = q;				//cur为当前结点
		q = q->link;			//q保存下一个结点
		L->head->link = cur;	//为了不动头结点,所以头结点link始终指向当前要加的结点
		cur->link = p;			//当前的link指向上一个结点
		p = cur;				//保存上一个结点
	}
	}else return ERROR;
	return OK;
}

Status Insert(Headlist *L,int j,ElemType x){
	int i;
	Node *p=NULL,*q=NULL;
	if(j<-1 || j> L-> n-1) return ERROR;
	p = L->head;
	for(i=0;i<=j;i++) p=p->link;
    // 与普通链表不同,这边是 <= , 因为要多一个表头Node
	q = (Node *)malloc(sizeof(Node));
	q->elem = x;
	q->link = p->link;
	p->link = q;
	L->n++;
	return OK;
}

Status Output(Headlist L){
	Node *p = L.head->link;
	if(!L.n) return ERROR;
	while(p){
		printf("%d ",p->elem );
		p = p->link;
	}
	return OK;
}

Status Destory(Headlist *L){
	Node *p=NULL;
	while(L->head){
		p = L->head->link; 
		free(L->head);		
		L->head = p;
	}	
	return OK;		
}

Status Delete(Headlist *L,int j){		//下标j
	Node *p = L->head,*q = L->head;		// q = tmp
	int i;
	if(!L->n) return ERROR;
	if ( j<0 || j>L->n) return ERROR;
	for(i = 0 ;i<=j-1;i++) p = p->link;
		q = p;
		p = p->link;
		q->link = p->link;
		free(p);
	return OK;
}

Status Find(Headlist *L,int j,ElemType *x){
	Node *p= L->head;
	int i;
	if ( j<0 || j>L->n) return ERROR;
	for(i = 0 ;i<=j;i++) p = p->link;
		*x = p->elem;
	return OK;
}

int main(){
	int x;
	Headlist list;
	Init(&list);
	 	Insert(&list,-1,3);
		Insert(&list,0,2);
		Insert(&list,-1,5);
		Insert(&list,2,7);
		Insert(&list,-1,1);
	printf("the linked list is :"); 
	Output(list);
	printf("\nAfter sorted:");
	Sort(&list);
	Output(list);
	printf("\nAfter Conversed:");
	Converse(&list);
	Output(list);
	
	printf("\nAfter delete index of 0,the list is:");
	Delete(&list,0);
	Output(list);

	Find(&list,2,&x);
	printf("\nthe index of 2:%d\n",x);

	Destory(&list);
	system("pause");
	return 0;
}

带表头的链表和普通链表的区别在于:

• 带表头链表的头结点的数据域是不设置的,真正有用的结点是L->head->link指向的结点.而普通链表L->first指向的结点
• 这样的好处是不用特殊考虑是不是头结点.

代码实现细节:

1.插入的i,是$a_{i}$后面再添加一项,所以for条件为j=0;j<i 进行j次link

2.删除时,删除的是$a_{i}$,for(j=0;j < i - 1;j++),为什么是 i-1跟代码实现有关,先把q指向要删除的前一个结点,p=q->link,q->link = p->link从而将p即$a_{i}$孤立出来

▲带表头的话,将<变为<=,因为要多推个link,跳过head结点

设计上最大的区别在于

▲多了个表头以后,就不用再考虑,删除和插入的时候去动List->first指针，带表头后，修改的都是L->head->link之后的结点Node

单链表实现多项式加减、相乘

#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;
	p->head = (PNode *)malloc(sizeof(PNode));
	p->head->exp = -1;
	p->head->link = NULL;
	for (;;)
	{
		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){	
		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);

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

	Add(&p,&q);						//ADD
	printf("After added:");
	Output(&q);
	printf("\n");
	system("pause");
	return 0;
}