dlist.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: dlist.c */
/* 双向链表的插入与删除*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
void init_f(void);     /* 初始化表，建立一个空节点为HEAD */
void read_f(void);     /* 读函数 */
void write_f(void);    /* 存储函数 */
void insert_f(void);   /* 插入函数*/
void sort_f(void);     /* 排序函数 */
void delete_f(void);   /* 删除函数*/
void display_f(void);  /* 输出函数 */
void modify_f(void);   /*修改函数*/
void anykey_f(void);
struct student {
	char name[20];          /*姓名*/
	int score;              /*分数*/
	struct student *prev;  /* 节点左链接*/
	struct student *next;   /* 节点右链接 */
};
struct student *ptr, *head, *tail, *current;

void main(void)
{
	char option1;
	system("cls");
	init_f();
	read_f();
	while(1)
	{
		system("cls");
		printf(" ****************************************\n");
		printf("              1.insert\n");
		printf("              2.delete\n");
		printf("              3.display\n");
		printf("              4.modify\n");
		printf("              5.quit\n");
		printf(" ****************************************\n");
		printf("   Please enter your choice (1-5)...");
		option1 = getche();
		switch(option1)
		{
			case '1':
				insert_f();
				break;
			case '2':
				delete_f();
				break;
			case '3':
				display_f();
				break;
			case '4':
				modify_f();
				break;
			case '5':
				write_f();
				exit(0);
		}
	}
}

void init_f(void)   /* 设一HEAD，将左右链接都指向本身 */
{
	ptr = (struct student *) malloc(sizeof(struct student));
	strcpy(ptr->name, "0");
	ptr->prev = ptr;
	ptr->next = ptr;
	head = ptr;
	tail = ptr;
}

void read_f(void)
{
	FILE *fptr;
	if((fptr = fopen("dlist.dat","r")) == NULL)  /* 找不到表，则要求输入第一笔数据*/
	{
		printf(" Data file not exist\n");
		printf(" Press any key to edit first record...\n");
		getch();
		insert_f();
	}
	else
	{
		ptr = (struct student *) malloc(sizeof(struct student));
		while(fscanf(fptr, "%s %d", ptr->name, &ptr->score) != EOF)
		{
			if(strcmp(ptr->name, "") != 0)
			{
				sort_f();
				ptr = (struct student *) malloc(sizeof(struct student));
			}
			else
				free(ptr);
		}
		fclose(fptr);
	}
}

void write_f(void)
{
	FILE *fptr;
	fptr = fopen("dlist.dat","w");
	current = head->next;
	while(current != head)
	{
		fprintf(fptr, "%s %d\n", current->name, current->score);
		current = current->next;
	}
	fclose(fptr);
}

void insert_f(void)
{
	char s_temp[4];
	system("cls");
	ptr = (struct student *) malloc(sizeof(struct student));
	printf(" Student name : ");
	gets(ptr->name);
	printf(" Student score: ");
	gets(s_temp);
	ptr->score = atoi(s_temp);
	sort_f();
}

/* 以姓名开头的字母有A-Z排列 */
void sort_f(void)
{
	current = head->next;
	while(current != head)
	{
		if(strcmp(ptr->name, current->name) < 0)   /*插入位置为中间*/
		{
			ptr->next = current;
			ptr->prev = current->prev;
			current->prev->next = ptr;
			current->prev = ptr;
			break;
		}
		current = current->next;
	}
	/* 插入位置为尾端*/
	if(head->next == head || current == head)
	{
		ptr->next = head;
		ptr->prev = head->prev;
		head->prev->next = ptr;
		head->prev = ptr;
		tail = ptr;
	}
}

void delete_f(void)
{
	char del_name[20];
	int count = 0;
	struct student *clear;
	system("cls");
	if(head->next == head) printf(" No student record\n");
	else
	{
		printf(" Delete student name: ");
		gets(del_name);
		current = head->next;
		while(current->next != head)
		{
			/*从中间删除数据*/
			while((strcmp(del_name,current->name) == 0) && (current->next != head))
			{
				count++;
				clear = current;
				current->prev->next = current->next;
				current->next->prev = current->prev;
				current = current->next;
				free(clear);
			}
			current = current->next;
		}
		if(strcmp(del_name,current->name) == 0)  /*从尾端删除数据 */
		{
			count++;
			clear = current;
			current->prev->next = head;
			head->prev = current->prev;
			tail = current->prev;
			free(clear);
		}
		if(count > 0)
			printf(" %d student record(s) deleted\n",count);
		else  /* 找不到数据则显示错误*/
			printf(" Student %s not found\n",del_name);
	}
	anykey_f();
}

void modify_f(void)
{
	int count = 0;
	char n_temp[20],s_temp[4];
	system("cls");
	if(head->next == head) printf(" No student recond\n");  /* 无数据显示错误*/
	else
	{
		printf(" Modify student name: ");
		gets(n_temp);
		current = head->next;
		while(current != head)
		{	/*若找不到修改的数据，则打印出原内容，并要求修改*/
			if(stricmp(n_temp,current->name) == 0)
			{
				printf(" **************************\n");
				printf("  Student name : %s\n",current->name);
				printf("  Student score: %d\n",current->score);
				printf(" **************************\n");
				printf(" Please enter new score: ");
				gets(s_temp);
				current->score = atoi(s_temp);
				count++;
			}
			current = current->next;
		}
		if(count > 0)
			printf(" %d student record(s) modified\n",count);
		else
			printf(" Student %s not found\n",n_temp);
	}
	anykey_f();
}

void display_f(void)
{
	int count = 0;
	system("cls");
	if(head->next == head) printf(" No student record\n");
	else
	{
		printf("  NAME                SCORE\n");
		printf(" ---------------------------\n");
		current = head->next;
		while(current != head)
		{
			printf("  %-20s %3d\n", current->name, current->score);
			count++;
			current = current->next;
			if(count % 20 == 0) getch();  /*每次打印出20笔数据 */
		}
		printf(" ---------------------------\n");
		printf(" Total %d record(s) found\n", count);
	}
	anykey_f();
}

void anykey_f(void)
{
	printf(" Press any key to continue...");
	getch();
}