exam10-8.cpp

很好的C程序设计教程

/*文件名:exam10_8.cpp*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char DataType;    	/*用typedef语句定义DataType为char类型*/
typedef struct node 		/*用typedef语句定义ListNode为node结构体类型*/
{
	DataType data;     		/*数据域*/
   	struct node *next;  	/*指针域*/
} ListNode;
ListNode *createlist() 			/*该函数最后返回单链表的头结点的指针*/
{   
	char ch;
	ListNode *head=(ListNode *)malloc(sizeof(ListNode));/*创建头结点*/
	ListNode *s,*r=head;       	/*r始终指向单链表的最后结点*/
	printf("输入结点值:");
   	ch=getchar();              	/*读第1个字符*/
	while (ch!='\n') 
	{
		s=(ListNode *)malloc(sizeof(ListNode));  /*创建一个新结点*/
		s->data=ch;            	/*将读入的数据放入新结点的数据域中*/
       	r->next=s;r=s;         	/*在*r之后插入*s,并将s赋给r*/
		ch=getchar();          	/*读入下一字符*/
	}
	r->next=NULL;
   	return head;               	/*返回头结点的指针*/
}
ListNode *getnode(ListNode *head,int i)
{
	int j=0;
	ListNode *p;
   	p=head;	                     	/*从头开始扫描*/
	while (p->next!=NULL && j<i)   	/*顺next指针方向移动指针变量p*/
	{
		p=p->next;
		j++;
	}
	if (p!=NULL)					/*若p不为空,表示查找成功*/
		return p;                   /*找到了第i个结点*/
   	else
     	return NULL;                /*当i<0或i>n时,找不到第i个结点*/
}
void displist(ListNode *head)  
{
	ListNode *p=head->next;			/*p指向第一个数据结点*/
	if (p==NULL)
		printf("空表\n");
	else 
	{
		while (p!=NULL) 			/*沿next顺序扫描每个结点,并输出其data域*/
		{
			printf("%c ",p->data);
			p=p->next;
		}
		printf("\n");
	}
} 
void insertnode(ListNode *head,DataType x,int i)
{
	ListNode *p,*s;
	s=(ListNode *)malloc(sizeof(ListNode));  /*创建新插的结点*/
	s->data=x;
	if (i==1)       					/* *s作为1号数据结点 */
	{
		s->next=head->next;
		head->next=s;
	}
	else 
	{
		p=getnode(head,i-1);  			/*查找指向第i-1个结点的指针*/
		if (p==NULL)         			/*i<1或i>n+1时插入位置i有错*/
		{
			printf("i取值有错\n");
			exit(0);
		}
		s->next=p->next;     			/*将*s插入在*p之后*/
		p->next=s;						/*将*p的指针域指向*s结点*/
	}
} 
void deletenode(ListNode *head,int i)
{
	ListNode *p,*r;
	p=getnode(head,i-1);           	/*找第i-1个结点*/
	if (p==NULL || p->next==NULL)  	/*i<1或i>n时删除位置有错*/
	{
		printf("i取值有错\n");
		exit(0);
	}
	r=p->next;                     	/*令r指向被删结点*/
	p->next=r->next;               	/*将*r从链上摘下*/
	free(r);   						/*释放结点*r,将所占用的空间归还给存储池*/
} 
void freelist(ListNode *head)
{
	ListNode *p=head,*q=p->next;
	while (q!=NULL) 
	{
		free(p);
		p=q;q=q->next;
	}
	free(q);
}
ListNode *subs(ListNode *heada,ListNode *headb)
{
	ListNode *p,*q,*r,*s;
	p=heada->next;          			/*p指向第一个数据结点*/
	r=heada;r->next=NULL;   		/*r指向生成的单链表的最后一个结点*/
	while (p!=NULL)        			/*扫描A*/
	{
		q=headb;
		while (q!=NULL && q->data!=p->data)  
			q=q->next; 
		if (q!=NULL)        			/*若p结点在B中,则要删除之*/
		{
			s=p->next;
			free(p);p=s;
		}
		else               			/*若p结点不在B中,则链接到新单链表中*/
		{
			r->next=p;s=p->next;
			r=p;r->next=NULL;
			p=s;
		}
	}
	return heada;
}
main()
{
	ListNode *ha,*hb,*hc;
	ha=createlist();        		/*调用单链表基本运算函数创建A集合*/
	hb=createlist();        		/*调用单链表基本运算函数创建B集合*/
	printf("A集合:");displist(ha);	/*调用单链表基本运算函数输出单链表ha*/
	printf("B集合:");displist(hb); 	/*调用单链表基本运算函数输出单链表hb*/
	hc=subs(ha,hb);
	printf("A-B:");displist(hc);	/*调用单链表基本运算函数输出单链表hc*/
}