www.pudn.com > gc.rar > GC_8_1_LINKLIST.C

/*本程序精简,恨适合学习,包括了链表的各种算法*/ 
/*以后改进,增加插入任何位置的函数*/ 
/*以后改进,把所有关于链表的算法全部放置在其中*/ 
 
 
 
# include  
# include  
struct intNode { 
	int value; 
	struct intNode *next; 
}; 
struct intNode *head; 
 
/*能实现遍历链表功能的函数*/ 
void travelLink(struct intNode *h) 
{ 
	struct intNode *p = h; 
	while (p!=NULL) { 
		printf("%4d",p->value);                 /*输出表元的值*/ 
		p=p->next; 
	} 
	printf("\n"); 
} 
 
 
/*无序链表上的动态查找*/ 
struct intNode *searchDSLink(struct intNode *h,int key,struct intNode **pp) 
{ 
	struct intNode *v = h, *u = NULL; 
	while((v!=NULL) && (v->value !=key)) { 
		u = v;                          /*准备考察下一个表元,当前表元成为后继表元的前驱表元*/ 
		v = v->next;                   /*考察下一个表元,后继表元成为当前表元*/ 
	} 
	*pp = u;                  /*   *pp是NULL时,找到的是首节点   ,当找到结点时,它是前驱结点*/ 
	return v;                /*返回NULL时,代表找不到,如果返回有值,那么*pp是它的前驱*/ 
} 
 
/*创建链表的函数*/ 
struct intNode *createList() 
{ 
	struct intNode *h,                 /*链表的头指针*/ 
	*tail,                             /*链表的尾指针*/ 
	*p; 
	int n; 
	char c; 
 
	h = tail = NULL; 
	printf("Input data.   \n"); 
	while (scanf("%d",&n)>0) {              /*有整数输入*/ 
		p = (struct intNode *)malloc(sizeof(struct intNode)); 
		p->value = n; 
		p->next = NULL; 
		if (h == NULL) 
			h = tail = p; 
		else 
			tail = tail->next = p; 
	} 
	do { 
		scanf("%c",&c); 
	}while (c!='\n');                  /*掠过整数序列之后,回车之前的字符*/ 
	return h; 
} 
 
 
/*颠倒链表的函数*/ 
struct intNode * reverse(struct intNode *h) 
{ 
	struct intNode *p,*v1,*v2; 
	v2 = h;                                  /*v2指向链表的首表元*/ 
	v1 = NULL;                               /*开始颠倒时,已颠倒部分为空*/ 
	while (v2 != NULL) {                       /*还未颠倒完,循环*/ 
		p = v2->next;                /*保存后一个表元*/ 
		v2->next = v1; 
		v1 = v2; 
		v2 = p; 
	} 
	return v1; 
} 
 
 
 
 
/*插入函数--------插入在首结点之前*/ 
struct intNode *inNode(void) 
{ 
	int d; 
	struct intNode *p; 
	printf("输入插入表元的值[将插入在首结点之前]  "); 
	scanf("%d",&d); 
	p = (struct intNode *)malloc(sizeof(struct intNode)); 
	p -> value = d; 
	p -> next = head; 
	return p; 
} 
 
 
/*删除结点,如果找不到这个值,那么就不做什么*/ 
struct intNode * delNode(void) 
{ 
	int d; 
	struct intNode *p,*q; 
	printf("输入删除表元的值  "); 
	scanf("%d",&d); 
	p = searchDSLink(head,d,&q); 
	if (p == NULL) printf("没有指定值%d的表元.\n",d); 
	else { 
		if (q == NULL) head = p -> next;           /*删除的是第一个结点,首结点*/ 
		else 
			q->next = p->next; 
		p->next = NULL; 
		free(p); 
	} 
	return head; 
} 
 
 
 
/*反转链表---前面已经有一个函数了,怎么还来这样的形式,为什么*/ 
struct intNode * revNode() 
{ 
	return reverse(head); 
} 
 
 
 
char * menuName [] = 
 { "创建一个整数链表,输入非整数结束输入","向链表插入 一个新结点","从链表删除一个结点","将链表颠倒",""}; 
 
struct intNode * (*fpt[])(void) = { createList,inNode,delNode,revNode,NULL }; 
/*指向函数的指针数组,所指向的这些函数的返回值是指向struct intNode的指针 */ 
 
struct intNode * (*menu(void))(void)          /*函数返回函数的指针*/ 
{ 
	int ans,k; 
	printf("请选择以下的菜单命令.  \n"); 
	for (k = 0;menuName[k][0] != '\0'; k++) 
		printf("\t%d:%s\n",k+1,menuName[k]); 
	printf("\t其他选择结束程序运行.   \n"); 
	scanf("%d",&ans); 
	if (ans <1 || ans > k) return NULL; 
	return fpt[ans -1];                   //返回函数的指针 
} 
 
void main() 
{ 
	struct intNode *(*fp)(void);            //必须先定义// 
	head = NULL; 
	while (1) { 
		if ((fp=menu()) == NULL) break; 
		head = (*fp)(); 
		travelLink(head); 
	} 
}