데이터 구조 c 언어 가 실현 하 는 단일 체인 표 의 응용

9751 단어
//c    ,            ,          《           》
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc() 
#include<limits.h> // INT_MAX 
#include<stdio.h> // EOF(=^Z F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define NAMELEN 8 //       
#define CLASSLEN 4 //        

typedef int Status; // Status      ,           , OK 

struct stud //      
{
	char name[NAMELEN+1]; //   '\0'
	long num;
	char sex;
	int age;
	char Class[CLASSLEN+1]; //   '\0'
	int health;
};
typedef stud ElemType; //             
char sta[3][9]={"    ","    ","    "}; //     (3 )
FILE *fp; //     

struct LNode
{
	ElemType data;
	LNode *next;
};
typedef LNode *LinkList; //      LinkList   

// bo2-8.cpp          (     c2-2.h  )       (9 )
#define DestroyList ClearList // DestroyList() ClearList()       
void InitList(LinkList &L)
{ //     :         L
	L=NULL; //     
}

void ClearList(LinkList &L)
{ //     :   L   。    : L     
	LinkList p;
	while(L) // L  
	{
		p=L; // p      
		L=L->next; // L   2   (     )
		free(p); //       
	}
}

Status ListEmpty(LinkList L)
{ //     :   L   。    : L   ,   TRUE,    FALSE
	if(L)
		return FALSE;
	else
		return TRUE;
}

int ListLength(LinkList L)
{ //     :   L   。    :  L       
	int i=0;
	LinkList p=L;
	while(p) // p    (    )
	{
		p=p->next; // p       
		i++;
	}
	return i;
}

Status GetElem(LinkList L,int i,ElemType &e)
{ // L              。  i      ,    e   OK,    ERROR
	int j=1;
	LinkList p=L;
	if(i<1) // i    
		return ERROR;
	while(j<i&&p) //    i   ,     
	{
		j++;
		p=p->next;
	}
	if(j==i) //    i   
	{
		e=p->data;
		return OK;
	}
	else
		return ERROR;
}

int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ //     :   L   ,compare()         (   1,   0)
	//     :  L  1  e    compare()        。
	//                      ,     0
	int i=0;
	LinkList p=L;
	while(p)
	{
		i++;
		if(compare(p->data,e)) //          
			return i;
		p=p->next;
	}
	return 0;
}

Status ListInsert(LinkList &L,int i,ElemType e)
{ //             L  i         e
	int j=1;
	LinkList p=L,s;
	if(i<1) // i    
		return ERROR;
	s=(LinkList)malloc(sizeof(LNode)); //      
	s->data=e; //  s data   
	if(i==1) //     
	{
		s->next=L;
		L=s; //   L
	}
	else
	{ //        
		while(p&&j<i-1) //    i-1   
		{
			p=p->next;
			j++;
		}
		if(!p) // i    +1
			return ERROR;
		s->next=p->next;
		p->next=s;
	}
	return OK;
}

Status ListDelete(LinkList &L,int i,ElemType &e)
{ //             L ,   i   ,  e    
	int j=1;
	LinkList p=L,q;
	if(i==1) //    1   
	{
		L=p->next; // L  2     
		e=p->data;
		free(p); //       1   
	}
	else
	{
		while(p->next&&j<i-1) //    i   ,  p     
		{
			p=p->next;
			j++;
		}
		if(!p->next||j>i-1) //        
			return ERROR;
		q=p->next; //        
		p->next=q->next;
		e=q->data;
		free(q);
	}
	return OK;
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ //     :   L   。    :   L           vi()
	LinkList p=L;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("
"); } // func2-1.cpp ( c2-2.h ) (3 ) // algo2-6.cpp bo7-2.cpp void InsertAscend(LinkList &L,ElemType e,int(*compare)(ElemType,ElemType)) { // e L。 compare() : 1 - 2 LinkList q=L; if(!L||compare(e,L->data)<=0) // e ListInsert(L,1,e); // e , bo2-8.cpp else { while(q->next&&compare(q->next->data,e)<0) // q q <e q=q->next; ListInsert(q,2,e); // q ( q ) } } LinkList Point(LinkList L,ElemType e,Status(*equal)(ElemType,ElemType),LinkList &p) { // L 。 , ,p ( // , p=NULL)。 L , NULL,p 。 // equal() , OK; ERROR int i,j; i=LocateElem(L,e,equal); if(i) // { if(i==1) // { p=NULL; return L; } p=L; for(j=2;j<i;j++) p=p->next; return p->next; } return NULL; // } Status DeleteElem(LinkList &L,ElemType &e,Status(*equal)(ElemType,ElemType)) { // L , TRUE; , FALSE。 // equal() , OK; ERROR LinkList p,q; q=Point(L,e,equal,p); if(q) // , q { if(p) // ,p ListDelete(p,2,e); // p , 2 else // ListDelete(L,1,e); return TRUE; } return FALSE; } void Print(stud e) { // e printf("%-8s %6ld",e.name,e.num); if(e.sex=='m') printf(" "); else printf(" "); printf("%5d %-4s",e.age,e.Class); printf("%9s
",sta[e.health]); } void ReadIn(stud &e) { // printf(" (<=%d ): ",NAMELEN); scanf("%s",e.name); printf(" : "); scanf("%ld",&e.num); printf(" (m: f: ): "); scanf("%*c%c",&e.sex); printf(" : "); scanf("%d",&e.age); printf(" (<=%d ): ",CLASSLEN); scanf("%s",e.Class); printf(" (0:%s 1:%s 2:%s):",sta[0],sta[1],sta[2]); scanf("%d",&e.health); } void WriteToFile(stud e) { // fp fwrite(&e,sizeof(stud),1,fp); } Status ReadFromFile(stud &e) { // fp e int i; i=fread(&e,sizeof(stud),1,fp); if(i==1) // return OK; else return ERROR; } int cmp(ElemType c1,ElemType c2) { return (int)(c1.num-c2.num); } void Modify(LinkList &L,ElemType e) { // , L char s[80]; Print(e); // printf(" , :
"); printf(" (<=%d ): ",NAMELEN); gets(s); if(strlen(s)) strcpy(e.name,s); printf(" : "); gets(s); if(strlen(s)) e.num=atol(s); printf(" (m: f: ): "); gets(s); if(strlen(s)) e.sex=s[0]; printf(" : "); gets(s); if(strlen(s)) e.age=atoi(s); printf(" (<=%d ): ",CLASSLEN); gets(s); if(strlen(s)) strcpy(e.Class,s); printf(" (0:%s 1:%s 2:%s):",sta[0],sta[1],sta[2]); gets(s); if(strlen(s)) e.health=atoi(s); // InsertAscend(L,e,cmp); // q L(func2-1.cpp) } #define N 4 // student Status EqualNum(ElemType c1,ElemType c2) { if(c1.num==c2.num) return OK; else return ERROR; } Status EqualName(ElemType c1,ElemType c2) { if(strcmp(c1.name,c2.name)) return ERROR; else return OK; } void main() { // stud student[N]={{" ",790631,'m',18," 91",0},{" ",790632,'f',20," 91",1}, {" ",790633,'m',21," 91",0},{" ",790634,'m',17," 91",2}}; int i,j,flag=1; char filename[13]; ElemType e; LinkList T,p,q; InitList(T); // while(flag) { printf("1: student
"); printf("2:
"); printf("3: ,
"); printf("4:
"); printf("5:
"); printf("6:
"); printf("7:
"); printf("8:
"); printf("9:
"); printf("10:
11:
12:
"); printf(" :
"); scanf("%d",&i); switch(i) { case 1: for(j=0;j<N;j++) InsertAscend(T,student[j],cmp); // func2-1.cpp break; case 2: printf(" :
"); scanf("%s",filename); if((fp=fopen(filename,"rb"))==NULL) printf(" !
"); else { while(ReadFromFile(e)) InsertAscend(T,e,cmp); // func2-1.cpp fclose(fp); } break; case 3: ReadIn(e); InsertAscend(T,e,cmp); // func2-1.cpp break; case 4: printf(" : "); scanf("%ld",&e.num); if(!DeleteElem(T,e,EqualNum)) // func2-1.cpp printf(" %ld
",e.num); break; case 5: printf(" :
"); scanf("%*c%s",e.name); // %*c if(!DeleteElem(T,e,EqualName)) // func2-1.cpp printf(" %s
",e.name); break; case 6: printf(" :
"); scanf("%ld%*c",&e.num); if(!DeleteElem(T,e,EqualNum)) // , e ( func2-1.cpp) printf(" %ld
",e.num); else Modify(T,e); // e T break; case 7: printf(" :
"); scanf("%*c%s%*c",e.name); // %*c if(!DeleteElem(T,e,EqualName)) // func2-1.cpp printf(" %s
",e.name); else Modify(T,e); break; case 8: printf(" :
"); scanf("%ld",&e.num); if(!(q=Point(T,e,EqualNum,p))) // func2-1.cpp printf(" %ld
",e.num); else Print(q->data); break; case 9: printf(" :
"); scanf("%*c%s",e.name); if(!(q=Point(T,e,EqualName,p))) // func2-1.cpp printf(" %s
",e.name); else Print(q->data); break; case 10:printf("
"); ListTraverse(T,Print); break; case 11:printf(" :
"); scanf("%s",filename); if((fp=fopen(filename,"wb"))==NULL) printf(" !
"); else ListTraverse(T,WriteToFile); fclose(fp); break; case 12: flag=0; } } }

좋은 웹페이지 즐겨찾기