functions.c

这是有关数据结构的例程序

#include<malloc.h>
#include<stdio.h>
#include"definition.h"

LinkList FormList()//正向形成链表
{
	ElemType temp;
	LinkList h, head, end;

	if( !( h=head=(LinkList)malloc(sizeof(Node)) ) ){
		printf("Not Enough Memory!\n");
		return 0;
	}
	head->next=0;
	while( (temp=getchar())!='\n' ){
		if( !( end=(LinkList)malloc(sizeof(Node)) ) ){
			printf("Not Enough Memory!\n");
			return 0;
		}
		head->next=end;
		head=end;
		head->data=temp;
		head->next=0;
	}

	return h;
}

LinkList FormList2()//逆向形成链表
{
	LinkList head, end;
	ElemType temp;

	if( !( head=(LinkList)malloc(sizeof(Node)) ) ){
		printf("Not Enough Memory!\n");
		return 0;
	}
	head->next=0;
	while( (temp=getchar())!='\n' ){
		if( !( end=(LinkList)malloc(sizeof(Node)) ) ){
			printf("Not Enough Memory!\n");
			return 0;
		}
		end->data=temp;
		end->next=head->next;
		head->next=end;
	}

	return head;
}
 
void Insert(LinkList L, unsigned i)//插入数据
{//若单链表没有头结点，需对在第一个结点之前进行插入的情况单独进行处理。很麻烦
	unsigned j;
	LinkList T;
	ElemType temp;
	
	getchar();
	for(j=1, L->next; L&&j<i; L=L->next, j++)
		;
	if(!L||j>i){
		printf("Error!\n");
		return;
	}
	printf("请输入您要插入的数据：");
	while( (temp=getchar())!='\n' ){
		if( !( T=(LinkList)malloc(sizeof(Node)) ) ){
			printf("Not Enough Memory!\n");
			return;
		}
		T->data=temp;
		T->next=L->next;
		L->next=T;
		L=T;
	}
}

void Delete(LinkList L, unsigned i, unsigned j)//删除数据
{
	LinkList T;

	getchar();
	for(i--; i&&L; L=L->next, i--)
		;
	if(!L){
		printf("Error!\n");
		return;
	}
	for(T=L->next; j&&T; j--){
		L->next=T->next;
		free(T);
		T=L->next;
	}
}

void Disp(LinkList L)//显示数据
{
	for(L=L->next; L; L=L->next)
		printf("%c", L->data);
	printf("\n");
}

void Destroy(LinkList L)//释放内存
{
	LinkList T=L;

	for(L=L->next; L; T=L, L=L->next)
		free(T);
	free(T);
}

void Bubble(LinkList L)//冒泡排序
{
	ElemType temp;
	LinkList T, H;
	unsigned i, j, flag=1;

	i=CountLen(L);//计算链表长度
	H=L->next;
	while(flag){
		L=H;
		T=H->next;
		flag=0;
		j=1;
		while(j<i){
			if(L->data > T->data){
				temp=T->data;
				T->data=L->data;
				L->data=temp;
				flag=1;
			}
			L=L->next;
			T=T->next;
			j++;
		}
		i--;
	}
}

void Merge(LinkList A, LinkList B)//合并有序链表
{
	LinkList C=A, D=B;

	A=A->next;
	B=B->next;
	while(A&&B){
		if(A->data<=B->data){
			C->next=A;
			C=A;
			A=A->next;
		}
		else{
			C->next=B;
			C=B;
			B=B->next;
		}
	}
	C->next=A?A:B;

	free(D);
}

unsigned CountLen(LinkList L)//计算链表长度
{
	unsigned i=0;

	for(L=L->next; L; L=L->next, i++)
		;
	return i;
}

void Exchange(LinkList L, unsigned i)//前 m 个结点和后 n 个结点的互换
{
	LinkList A, B;

	A=B=L->next;
	for(i--; i&&A; A=A->next, i--)
		;
	if(!A){
		printf("Error!\n");
		return;
	}
	L->next=A->next;
	A->next=0;
	A=L->next;
	while(A->next)
		A=A->next;
	A->next=B;
}

void Purge(LinkList L)//删除单链表中重复的数据元素
{
	LinkList A, B, C, D;

	B=C=L->next;
	L->next=0;
	while(B){
		A=L->next;
		D=L;
		while(A){
			if(A->data==B->data){
				B=B->next;
				free(C);
				C=B;
				break;
			}
			else{
				A=A->next;
				D=D->next;
			}
		}
		if(!A){
			D->next=B;
			B=B->next;
			C->next=0;
			C=B;
		}
	}
}