1.cpp

数据结构中的另一实验:双向链表.学好计算机课程,从基础开始.

#include <stdio.h>
#include<stdarg.h>
#include<stdlib.h>


typedef char ElemType;

typedef struct Node { /* 定义单链表 */
	ElemType data;
	struct Node *next;
	struct Node *prior;
} Node, *LinkList;

void Delete( LinkList, unsigned, unsigned ); /* 删除数据 */
void Destroy( LinkList ); /* 删除链表 */
void Disp( LinkList ); /* 显示数据 */
LinkList FormList( void ); /* 正向形成链表除数据 */
int Insert( LinkList, unsigned ); /* 插入数据 */
int Find(LinkList,unsigned );


void error( char *, ... ); /* 输出错误信息，退出程序 */
void flush_stdin( void );  /* 清空“输入缓冲区” */

/* begin of error 05-8-15 18:40 */
void error( char *fmt, ... )
{ /* 输出错误信息，退出程序 */
	va_list args;

	va_start( args, fmt );/* <stdarg.h> 开始使用可变参数，该函数和va_end，va_arg配合使用  */
       /*函数原型：void va_start(va_list argptr, Npara) 输入参数：argptr void类型指针，     *
        *类型va_list是一个void类型的指针，Npara 可变参数的个数) */
	fprintf( stderr, "error: " ); /*int fprintf(FILE *fp, char *format,…) 将格式化数据写入流式文件中 */
	vfprintf( stderr, fmt, args );/*int vfprintf(FILE *fp,const char *format, va_list arglist)*/
                             /*fp 文件指针，format 参数格式说明，具体参见printf函数，arglist 参数列表指针 */
	fprintf( stderr, "\n" );
	va_end( args ); /* 停止使用可变参数，该函数和va_start,va_arg配合使用 */

	exit( -1 );
}  /* end of error */

/* begin of flush_stdin 05-8-31 19:30 */
void flush_stdin( void )  /* 清空“输入缓冲区” */
{
	int c;
       /* 检测文件位置指示器是否已到结尾 int feof(FILE *stream) stream是文件指针*/
	if ( !feof(stdin) ) {
		while( ( c=getchar() ) != '\n' && c != EOF )
			;
	}
} /* end of flush_stdin */


int main( void )
{
	unsigned i =0, j = 0,a;
	LinkList A;

	printf( "请输入数据：" );
	if ( !( A = FormList() ) ) {
		error( "%s\n", "fail to create double link list..." );
	}
	printf( "表 A 中的数据为：" );
	Disp( A );

	/* 插入数据 */
	printf( "请问您要在表 A 的哪个位置插入数据：" );
	scanf( "%u", &i );
	flush_stdin();  /* 清空“输入缓冲区” */
	if ( !Insert( A, i ) ) {
		error( "%s\n", "fail to insert data into double link list..." );
	}
	printf( "表A中的数据为：" );
	Disp( A );

	/* 删除数据 */
	i = j = 0;
	printf( "请问您要从表A的哪个位置开始删除数据：" );
	scanf( "%u", &i );
	flush_stdin();
	
	printf( "请问您要删除几个元素：" );
	scanf( "%u", &j );
	flush_stdin();
	
	Delete( A, i, j );
	 
	printf("请问您要访问第几个元素:");
	scanf("%u",&a);
    flush_stdin();
	if ( !(Find(A,a) ) ) {
		error( "%s\n", "fail to visit double link list..." );
	}

	printf( "表A中的数据为：" );
	Disp( A );

	Destroy( A );
	puts( "请按任意键退出..." );
	getchar();
	return 0;
}



void Delete(LinkList L, unsigned i, unsigned j) /* 删除数据 */
{
	LinkList T, A, B = L;//此处定义了三个指针

	if ( !L || !i ) {
		return;
	}
	while ( --i ) {
		L = L->next;
		if ( !( L - B) ) {
			break;
		}
	}
	if ( i && !( L - B) ) {
		return;
	}
	for ( T = L->next; j && ( T - B ); --j ) {
		L->next = T->next;
		A = T->next;
		A->prior = L;
		free( T );
		T = L->next;
	}
} /* end of Delete */

/* begin of Destroy 05-8-17 00:15 */
void Destroy( LinkList L )
{
	LinkList p = L, n = L->next;

	if ( !L ) {
		return;
	}
	while ( L != n ) {
		free( p );
		p = n;
		n = n->next;
	}
	free( p );	
} /* end of Destroy */

/* begin of Disp 05-8-17 00:20 */
void Disp(LinkList L) /* 显示数据 */
{
	LinkList T = L;

	for ( L = L->next; L - T; L = L->next ) {
		printf( "%c", L->data );
	}
	printf( "\n" );
} /* end of Disp */

/* begin of FormList 05-8-16 00:15 */
LinkList FormList( void ) /* 正向形成链表 */
{
	LinkList h, head, end; //定义了三个指针
	int temp;

	if ( !( h = head = (Node*)malloc(sizeof *head) ) ) {
		return NULL;
	}
	h->next = h->prior = head;
	while ( ( temp=getchar() ) != '\n' && temp != EOF ) {
		if ( !( end = (Node*)malloc(sizeof *head) ) ) {
			Destroy( head );
			return NULL;
		}//end 每次作为新插入的结点
		end->data = temp;
		end->next = head;  //表尾指向新插入的元素
		end->prior = h;    /*把h放在end的前一个位置*/
		h->next = end;
		h = end;
		head->prior = end;
	}
	return head;
} /* end of FormList */

/* begin of Insert 05-8-17 00:50 */
int Insert(LinkList L, unsigned i) /* 插入数据 */
{ /* 若单链表没有头结点，需对在第一个结点之前进行插入的情况单独进行处理。很麻烦 */
	LinkList T, A = L;
	int temp;

	if ( !L || !i ) {
		return 0;
	}
	
	while ( --i ) {
		L = L->next;
		if( !( L - A ) ) {
			break;
		}
	}
	if ( i && !( L - A ) ) {
		return 0;
	}

	printf( "请输入您要插入的数据：" );
	while ( ( temp = getchar() ) != '\n' && temp != EOF ) {
		if ( !( T = (Node*)malloc( sizeof *T ) ) ) {
			Destroy( L );
			return 0;
		}
		T->data = temp;
		T->next = L->next;
		A = L->next;
		A->prior = T;
		T->prior = L;
		L->next = T;
		L = T;
	}

	return 1;
} /* end of Insert */
/*begin of Find*/
int Find(LinkList L, unsigned i) 
{
	LinkList  B = L;//此处定义了三个指针

	if ( !L || !i ) {
		return 0;
	}
	while ( --i ) {
		L = L->next;
		if ( !( L - B) ) {
			break;
		}
	}
	if ( i && !( L - B) ) {
		return 0;
	}
	
        printf("The ith Element is:");
        printf("%c",L->data);
        printf("the prior Element and next Element are:");
        printf("%c  %c",L->prior->data,L->next->data);
		return 1;
} /* end of Find */