数据结构习题集作业代码（第二章）

Description

设顺序表va中的数据为递增有序。写一个算法，将x插入到顺序表的适当位置，保证有序性。

Input
输入分为两行，第一行是va顺序表，每个元素按空格分隔，第二行是x的值。

顺序表中的元素最多为100个，所有元素的值均大于0，元素为整型。

Output
输出插入x后，va的结果

#include
#include
#include
typedef struct PolyNode{
   int sum;
  struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,int sum){
	if(head==NULL){
		return init(sum);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	pre=head;
	if(head->sum>sum){
		now->next=head;
		return now;
	}
	else{
		while(pre->next!=NULL&&pre->next->sumsum){
			pre=pre->next;
		}
		now->next=pre->next;
		pre->next=now;
		return head;
	}
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	do{
		printf("%d ",pre->sum);
		pre=pre->next;
	}while(pre!=NULL);
}
char c;
int x;
int main(){
	struct PolyNode * head=NULL;
	while((c=getchar())!='n'){
		int x=0;
		int f=1;
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-'0';
			c=getchar();
		}
		x*=f;
		int sum=x;
		head=ins(head,sum);
		if(c=='n'||c==EOF)break;
	}
    scanf("%d",&x);
    head=ins(head,x);
	Print(head);
    return 0;
}

Description

设 A = ( a 1 , . . . , a m ) A=(a_1,...,a_m) A=(a1​,...,am​)和 B = ( b 1 , . . . , b n ) B=(b_1,...,b_n) B=(b1​,...,bn​)均为顺序表，A ′ 和B’分别A和B中除去最大共同前缀后的子表分别A和B中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为

Input
输入为两行，分别代表A和B中的元素，以逗号分开。每个顺序表最多100个元素。
Output
输出A和B的比较结果，0代表A=B，1代表AB

#include
#include
char A[1000],B[1000];
int main(){
	scanf("%s%s",A,B);
	int cmp=strcmp(A,B);
	if(cmp<0)printf("1");
	if(cmp==0)printf("0");
	if(cmp>0)printf("2");
	return 0;
}

Description

已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元节点连在另一个表的最后一个节点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成链接运算。
Input
输入包括三行，第一行是两个链表的长度m和n，第二行和第三行分别为链表ha和hb中的元素，以空格分隔。

Output
输出合并后的链表hc，元素以空格分隔

#include
#include
#include
typedef struct PolyNode{
   int sum;
  struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,int sum){
	if(head==NULL){
		return init(sum);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	pre=head;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	now->next=pre->next;
	pre->next=now;
	return head;
}
struct PolyNode * Merge(struct PolyNode *ha,struct PolyNode *hb){
	struct PolyNode *a=ha, *b=hb;
	while(a->next!=NULL&&b->next!=NULL){
		a=a->next;
		b=b->next;
	}
	if(a->next==NULL){
		a->next=hb;
		return ha;
	}
	else{
		b->next=ha;
		return hb;
	}
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	if(head==NULL){
		printf("NULL");
		return;
	}
	do{
		printf("%d ",pre->sum);
		pre=pre->next;
	}while(pre!=NULL);
}
char c;
int n,m,x,i;
int main(){
	struct PolyNode * ha=NULL, * hb=NULL, *hc=NULL;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i){
		scanf("%d",&x);
		ha=ins(ha,x);
	}
	for(i=1;i<=m;++i){
		scanf("%d",&x);
		hb=ins(hb,x);
	}
	hc=Merge(ha,hb);
	Print(hc);
    return 0;
}

Description
试写一算法，在无头节点的动态单链表上实现线性表操作DELETE(L,i)。
Input
输入包含两行，第一行是链表中的元素，第二行表示需要删除的第i个元素，i从0开始计数
若删除后，链表不包含元素，则输出“NULL”。
Output
输出删除后的链表元素

#include
#include
#include
typedef struct PolyNode{
   int sum;
  struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,int sum){
	if(head==NULL){
		return init(sum);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	pre=head;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	now->next=pre->next;
	pre->next=now;
	return head;
}
struct PolyNode * del(struct PolyNode *head,int idx){
	struct PolyNode *ret, *pre, *suc;
	if(idx==0){
		ret=head->next;
		free(head);
		return ret;
	}
	pre=head;
	idx--;
	while(idx){
		pre=pre->next;
		idx--;
	}
	if(pre->next!=NULL)
		suc=pre->next->next;
	else suc=NULL;
	if(pre->next!=NULL)
		free(pre->next);
	pre->next=suc;
	return head;
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	if(head==NULL){
		printf("NULL");
		return;
	}
	do{
		printf("%d ",pre->sum);
		pre=pre->next;
	}while(pre!=NULL);
}
char c;
int x;
int main(){
	struct PolyNode * head=NULL;
	while((c=getchar())!='n'){
		int x=0;
		int f=1;
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-'0';
			c=getchar();
		}
		x*=f;
		int sum=x;
		head=ins(head,sum);
		if(c=='n'||c==EOF)break;
	}
    scanf("%d",&x);
    head=del(head,x);
	Print(head);
    return 0;
}

Description
已知线性表中的元素以递增有序排列，并以单链表为存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删节点的空间。
注意：mink和maxk是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同。
Input
输入包含两行，第一行是链表中的元素，以空格分隔。
第二行分别为mink和maxk两个元素，以空格分隔。
Output
输出最后的链表中的元素

#include
#include
#include
char c;
int x,L,R;
typedef struct PolyNode{
   int sum;
  struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,int sum){
	if(head==NULL){
		return init(sum);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	pre=head;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	now->next=pre->next;
	pre->next=now;
	return head;
}
struct PolyNode * del(struct PolyNode *head){
	struct PolyNode *now=head,*ha=head,*pre;
	while(now!=NULL){
		if(now->sum>L&&now->sum
			if(now==ha){
				ha=now->next;
				free(now);
				now=ha;
			}
			else{
				pre=ha;
				while(pre->next!=now){
					pre=pre->next;
				}
				pre->next=now->next;
				free(now);
				now=pre;
			}
		}
		else
			now=now->next;
	}
	return ha;
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	if(head==NULL){
		printf("NULL");
		return;
	}
	do{
		printf("%d ",pre->sum);
		pre=pre->next;
	}while(pre!=NULL);
}
int main(){
	struct PolyNode * head=NULL;
	while((c=getchar())!='n'){
		int x=0;
		int f=1;
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-'0';
			c=getchar();
		}
		x*=f;
		int sum=x;
		head=ins(head,sum);
		if(c=='n'||c==EOF)break;
	}
	scanf("%d %d",&L,&R);
	head=del(head);
	Print(head);
    return 0;
}

Description
试写一算法，实现单链表的就地逆置
Input
输入为给定链表的所有元素，以逗号分隔
Output
输出为链表逆置后的结果，以逗号分隔

#include
#include
#include
char c;
typedef struct PolyNode{
   char sum;
  struct PolyNode *next;
}PolyNode;
struct PolyNode * init(char sum){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,char sum){
	if(head==NULL){
		return init(sum);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	pre=head;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	now->next=pre->next;
	pre->next=now;
	return head;
}
struct PolyNode * Reverse(struct PolyNode *head){
	struct PolyNode *now=head->next,*pre=head,*tmp;
	while(now!=NULL){
		tmp=now->next;
		now->next=pre;
		pre=now;
		now=tmp;
	}
	head->next=NULL;
	return pre;
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	if(head==NULL){
		printf("NULL");
		return;
	}
	printf("%c",pre->sum);
	pre=pre->next;
	do{
		printf(",%c",pre->sum);
		pre=pre->next;
	}while(pre!=NULL);
}
int main(){
	struct PolyNode * head=NULL;
	while((c=getchar())!='n'&&c!=EOF){
		if(c==',')continue;
		else head=ins(head,c);
	}
	head=Reverse(head);
	Print(head);
    return 0;
}

Description

已知A，B和C为三个递增有序的线性表，现要求对A表做如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法。

Input
输入包含三行，分别为ABC三个线性表中的元素，以逗号分隔

Output
输出操作之后的A表中的元素

#include
#include
#include
char c;
int i;
typedef struct PolyNode{
   char sum;
  struct PolyNode *next;
}PolyNode;
struct PolyNode * init(char sum){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,char sum){
	if(head==NULL){
		return init(sum);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	pre=head;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	now->next=pre->next;
	pre->next=now;
	return head;
}
struct PolyNode * del(struct PolyNode *head,char idx){
	struct PolyNode *ret, *pre, *suc;
	if(idx==head->sum){
		ret=head->next;
		free(head);
		return ret;
	}
	pre=head;
	while(pre->next!=NULL&&pre->next->sum!=idx){
		pre=pre->next;
	}
	if(pre->next!=NULL)
		suc=pre->next->next;
	else suc=NULL;
	if(pre->next!=NULL)
		free(pre->next);
	pre->next=suc;
	return head;
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	if(head==NULL){
		printf("NULL");
		return;
	}
	printf("%c",pre->sum);
	pre=pre->next;
	if(pre==NULL)return;
	do{
		printf(",%c",pre->sum);
		pre=pre->next;
	}while(pre!=NULL);
}
struct PolyNode * operate(struct PolyNode *ha,struct PolyNode *hb,struct PolyNode *hc){
	struct PolyNode *a=ha,*b=hb,*c=hc,*now,*ret=ha;
	while(a!=NULL){
		while(b!=NULL&&b->sumsum){
			b=b->next;
		}
		while(c!=NULL&&c->sumsum){
			c=c->next;
		}
		if(b!=NULL&&c!=NULL){
			if(a->sum==b->sum&&a->sum==c->sum){
				now=a->next;
				ret=del(ret,a->sum);
				a=now;				
			}
			else{
				a=a->next;
			}
		}
		else a=a->next;
	}
	return ret;
}
char s[1000+10];
int main(){
	struct PolyNode * ha=NULL,* hb=NULL,* hc=NULL;
	scanf("%s",s);
	for(i=0;i
		if(s[i]!=',')ha=ins(ha,s[i]);
	}
	scanf("%s",s);
	for(i=0;i
		if(s[i]!=',')hb=ins(hb,s[i]);
	}
	scanf("%s",s);
	for(i=0;i
		if(s[i]!=',')hc=ins(hc,s[i]);
	}
	ha=operate(ha,hb,hc); 
	Print(ha);
    return 0;
}

Description
设有一双向循环链表，每个节点中除有prior,data和next三个域外，还增设了一个访问频度域freq。在链表被启用之前，频度域freq的值均初始化为0，而每当对链表进行一次LOCATE(L,x)的操作后，被访问的节点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中节点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的节点总是靠近表头结点。编写符合上述要求的LOCATE操作的算法。
Input
输入包含三行，第一行是链表中的元素个数，第二行是链表中的元素，第三行包含所有被访问的元素
Output
顺序输出从表头节点开始的链表中的元素。
注意：如果有多个元素的访问次数相同，需要按照访问次序，将先访问到的元素放在前面

#include
#include
#include
int i,n;
typedef struct PolyNode{
   int sum,freq,Tim;
  struct PolyNode *next, *pre;
}PolyNode;
struct PolyNode * init(int sum,int freq){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->freq=freq;
	now->Tim=0;
	now->next=NULL;
	now->pre=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,int sum,int freq){
	if(head==NULL){
		return init(sum,freq);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->sum=sum;
	now->freq=freq;
	now->Tim=0;
	pre=head;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	now->next=pre->next;
	pre->next=now;
	now->pre=pre;
	return head;
}
struct PolyNode * Convert(struct PolyNode *head){
	struct PolyNode *now=head;
	while(now->next!=NULL){
		now=now->next;
	}
	now->next=head;
	head->pre=now;
	return head;
} 
struct PolyNode * Modify(struct PolyNode *head,int sum,int Tim){
	struct PolyNode * now=head,*pre;
//	printf("%dn",sum);
	do{
//		printf("%d ",now->sum);
		if(now->sum==sum){
			if(now->Tim==0)now->Tim=Tim;
			now->freq++;
			now->pre->next=now->next;
			now->next->pre=now->pre;
			if(now==head)head=now->next;
			pre=head;
			while((pre->freq>now->freq||(pre->freq==now->freq&&pre->TimTim))&&pre->next!=head)
				pre=pre->next;
			if(pre->next==head&&(pre->freq>now->freq||(pre->freq==now->freq&&pre->TimTim))){
				pre=pre->next;	
				now->pre=pre->pre;
				now->pre->next=now;	
				now->next=pre;
				pre->pre=now;
				return head;
			}
//			printf("sum=%d freq=%dn",pre->sum,pre->freq);
			now->pre=pre->pre;
			now->pre->next=now;	
			now->next=pre;
			pre->pre=now;
//			printf("%p %pn",head,pre);
			if(pre==head)return now;
			else return head;	
			break;
		}
		now=now->next;
//		printf("%p %pn",head,now);
	}while(now!=head);
	return head;
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	if(head==NULL){
		printf("NULL");
		return;
	}
	do{
		printf("%d ",pre->sum);
		pre=pre->next;
	}while(pre!=head);
}
struct PolyNode * operate(struct PolyNode *head){
	return ;
}
int main(){
	struct PolyNode * head=NULL;	
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		head=ins(head,x,0);
		if(n==1){
			printf("%d",x);
			return 0;	
		}
	}
	head=Convert(head);
	int Tim=0;
	char c;
	c=getchar();
	while((c=getchar())!='n'){
		int x=0;
		int f=1;
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-'0';
			c=getchar();
		}
		x*=f;
		int sum=x;
		head=Modify(head,sum,++Tim);
		if(c=='n'||c==EOF)break;
//		Print(head);
	}
	Print(head);
    return 0;
}

2.41-稀疏多项式求导
Description

试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的节点空间存放其导函数（多项式），同时释放所有无用（被删）节点。

稀疏多项式中采用的循环链表存储结构LinkedPoly定义为

typedef struct PolyNode{
  PolyTerm data;
  Struct PolyNode *next;
} PolyNode, *PolyLink;

typedef PolyLink LinkedPoly;

Input
输入为给定的多项式

Output
输出为求导之后的结果，按照多项式中每一项的幂次由高到低排列

如果导数为0，则输出0

#include
#include
#include
typedef struct PolyTerm{
	int sum,power;
}PolyTerm;
typedef struct PolyNode{
   struct PolyTerm data;
  struct PolyNode *next;
}PolyNode, *PolyLink;
struct PolyNode * init(int sum,int power){
	struct PolyNode *now=malloc(sizeof(struct PolyNode));
	memset(now,0,sizeof(struct PolyNode));
	now->data.sum=sum;
	now->data.power=power;
	now->next=NULL;
	return now;	
}
struct PolyNode * ins(struct PolyNode *head,int sum,int power){
//	printf("%d %dn",sum,power);
	if(head==NULL){
		return init(sum,power);
	}
	struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
	memset(now,0,sizeof(struct PolyNode));
	now->data.sum=sum;
	now->data.power=power;
	pre=head;
	if(head->data.powerdata.power){
		now->next=head;
		return now;
	}
	else{
		if(head->data.power==power){
			head->data.sum+=sum;
			return head;
		}
		while(pre->next!=NULL&&pre->next->data.power>now->data.power){
			pre=pre->next;
		}
		if(pre->next!=NULL&&pre->next->data.power==now->data.power){
			pre->next->data.sum+=sum;
			return head;
		}
		now->next=pre->next;
		pre->next=now;
		return head;
	}
}
struct PolyNode * del(struct PolyNode *now){
	struct PolyNode * pre=now;
//	printf("%pn%pn",now,now->next);
	if(now->next==now){
		free(now);
		return NULL;	
	}
	while(pre->next!=now){
		pre=pre->next;
	}
	pre->next=now->next;
	free(now);
	return pre;
}
void convert(struct PolyNode *head){
	struct PolyNode * pre=head;
	if(head==NULL)return;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	pre->next=head;
}
struct PolyNode * derivation(struct PolyNode * head){
	if(head==NULL)return NULL;
	struct PolyNode * now=head;
	do{
		now->data.sum*=now->data.power;
		now->data.power-=(now->data.power!=0);
		now=now->next;
	}while(now!=head);
	do{
		if(now->data.sum==0){
			now=del(now);
		}
		if(now==NULL)break;
		now=now->next;
	}while(now!=head&&now!=NULL);
	if(now==NULL)return NULL;
	else return head;
}
void Print(struct PolyNode * head){
	struct PolyNode * pre=head;
	do{
		struct PolyTerm now=pre->data;
		if(now.sum<0){
			printf("- ");
			now.sum=-now.sum;
		}
		else{
			if(pre!=head)
				printf("+ ");
		}
		printf("%d",now.sum);
		if(now.power!=0){
			printf("x");
			if(now.power>1){
				printf("^");
				printf("%d",now.power);
			}
		}
		if(pre->next!=head)
			printf(" ");
		pre=pre->next;
	}while(pre!=head);
}
char c;
int stack[10000];
int main(){
	struct PolyNode * head=NULL;
	int current=1;
	while((c=getchar())!=EOF&&c!='n'){
		int x=0;
		int f=1;
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-'0';
			c=getchar();
		}
		x*=f;
		stack[++stack[0]]=x;
		if(current==2){
			int power=stack[stack[0]--];
			int sum=stack[stack[0]--];
			head=ins(head,sum,power);
			current=1;
		}
		else{
			if(c=='x'){
				c=getchar();
				if(c=='^'){
					current=2;
				}
				else{
					int sum=stack[stack[0]--];
					head=ins(head,sum,1);
				}
				if(c=='n'||c==EOF)break;
			}
			else{
				int sum=stack[stack[0]--];
				head=ins(head,sum,0);				
			}			
		}
//		printf("%cn",c);
		if(c=='n'||c==EOF)break;
//		puts("in");
	}
	convert(head);
	head=derivation(head);
	if(head==NULL){
		printf("0");
	}
	else{
		Print(head);
	}
	return 0;
}