gc_8_1_linklist.c

gc:高级程序员考试用书的c程序源文件

/*本程序精简,恨适合学习,包括了链表的各种算法*/
/*以后改进,增加插入任何位置的函数*/
/*以后改进,把所有关于链表的算法全部放置在其中*/



# include <stdio.h>
# include <stdlib.h>
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);
	}
}