C语言程序设计之链表篇2

程序设计之链表2

• 链表
• 问题2_1
• • 代码2_1
  • 结果2_1
• 问题2_2
• • 代码2_2
  • 结果2_2
• 问题2_3
• • 代码2_3
  • 结果2_3
• 问题2_4
• • 代码2_4
  • 结果2_4

链表

        考查链表的数据结构，需利用指针变量才能实现，一个结点中应包含一个指针变量，用来存放下一个结点的地址。
        建立单向链表的一般步骤是：建立头指针 -> 建立第一个结点 -> 头指针指向第一个结点 -> 建立第二个结点 -> 头指针指向第二个结点
-> ··· -> 最后一个结点的指针指向 $NULL$。

问题2_1

        函数 $fun$ 的功能是：将不带头结点的单向链表逆置，即若原链表中从头自尾结点数据域依次为 $2、4、6、8、10$ ，逆置后，依次为 $10、8、6、4、2$ 。

代码2_1

#include<stdio.h> #include<stdlib.h>  #define N 5   typedef struct node{ 	int data; 	struct node *next; }NODE;  NODE *fun(NODE *h){ 	NODE *p, *q, *r; 	p = h; 	if(p==NULL) 		return NULL; 	q = p->next; 	p->next = NULL; 	while(q){ 		r = q->next; 		q->next = p; 		p = q; 		q = r; 	} 	return p; }   NODE *creatlist(int a[]){ 	NODE *h, *p, *q; 	int i; 	h = NULL; 	for(i=0; i<N; i++){ 		q = (NODE*)malloc(sizeof(NODE)); 		q->data = a[i]; 		q->next = NULL; 		if(h==NULL) 			h = p = q; 		else{ 			p->next = q; 			p = q; 		} 	} 	return h; }  void outlist(NODE *h){ 	NODE *p; 	p = h; 	if(p==NULL) 		printf("The list is NULL!\n"); 	else{ 		printf("\nHead"); 		do{ 			printf("->%d", p->data); 			p = p->next; 		}while(p!=NULL); 		printf("->End\n"); 	} }  void main(void){ 	NODE *head; 	int a[N] = {2, 4, 6, 8, 10}; 	head = creatlist(a); 	printf("\nThe original list:\n"); 	outlist(head); 	head = fun(head); 	printf("\nThe list after inverting:\n"); 	outlist(head); } 

结果2_1

问题2_2

        函数 $fun$ 的功能是：将不带头结点的单向链表结点数据中的数据从小到大排序。即若原链表中从头自尾结点数据域依次为 $10、4、2、8、6$ ，逆置后，依次为 $2、4、6、8、10$ 。

代码2_2

#include<stdio.h> #include<stdlib.h>  #define N 6 typedef struct node{ 	int data; 	struct node *next; }NODE;  void fun(NODE *h){ 	NODE *p, *q; 	int t; 	p = h; 	while(p){ 		q = p->next; 		while(q){ 			if(p->data>q->data){ 				t = p->data; 				p->data = q->data; 				q->data = t; 			} 			q = q->next; 		} 		p = p->next; 	} }   NODE *creatlist(int a[]){ 	NODE *h, *p, *q; 	int i; 	h = NULL; 	for(i=0; i<N; i++){ 		q = (NODE*)malloc(sizeof(NODE)); 		q->data = a[i]; 		q->next = NULL; 		if(h==NULL)  			h = p = q; 		else{ 			p->next = q; 			p = q; 		} 	} 	return h; }  void outlist(NODE *h){ 	NODE *p; 	p = h; 	if(p==NULL) 		printf("The list is NULL!\n"); 	else{ 		printf("\nHead"); 		do{ 			printf("->%d", p->data); 			p = p->next; 		} 		while(p!=NULL); 		printf("->End\n"); 	} }  void main(void){ 	NODE *head; 	int a[N] = {0, 10, 4, 2, 8, 6}; 	head = creatlist(a); 	printf("\nThe original list:\n"); 	outlist(head); 	fun(head); 	printf("\nThe list after inverting :\n"); 	outlist(head); } 

结果2_2

问题2_3

        在带头结点的单向链表中，查找数据域中值为 $ch$ 的结点。找到后通过函数值返回该结点在链表中所处的顺序号；若不存在值为 $ch$ 的结点，函数返回 0 值。

代码2_3

#include<stdio.h> #include<stdlib.h>  #define N 8  typedef struct list{ 	int data; 	struct list *next; }SLIST;  SLIST *creatlist(char *); void ooutlist(SLIST *);  int fun(SLIST *h, char ch){ 	SLIST *p; 	int n=0; 	p = h->next; 	while(p!=NULL){ 		n++; 		if(p->data==ch) 			return n; 		else 			p = p->next; 	} 	return 0; }  void main(void){ 	SLIST *head; 	int k; 	char ch; 	char a[N] = {'z', 'y', 's', 'd', 'a', 'o'}; 	head = creatlist(a); 	outlist(head); 	printf("Enter a letter: "); 	scanf("%c", &ch); 	k = fun(head, ch); 	if(k==0) 		printf("\nNot found!\n"); 	else 		printf("The sequence number is : %d\n", k); }  SLIST *creatlist(char *a){ 	SLIST *h, *p, *q; 	int i; 	h = p = (SLIST*)malloc(sizeof(SLIST)); 	for(i=0; i<N; i++){ 		q = (SLIST*)malloc(sizeof(SLIST)); 		q->data = a[i]; 		p->next = q; 		p = q; 	} 	p->next = 0; 	return h; }  void outlist(SLIST *h){ 	SLIST *p; 	p = h->next; 	if(p==NULL) 		printf("\nThe list is NULL!\n"); 	else{ 		printf("\nHead"); 		do{ 			printf("->%c", p->data); 			p = p->next; 		}while(p!=NULL); 	} 	printf("->End\n"); } 

结果2_3

问题2_4

         函数 $fun$ 的功能是 ：统计带头结点的单向链表中结点的个数，并存放在形参 $n$ 所指的存储单元中。

代码2_4

#include<stdio.h> #include<stdlib.h>  #define N 8  typedef struct list{ 	int data; 	struct list *next; }SLIST;  SLIST *creatlist(int *); void ooutlist(SLIST *);  int fun(SLIST *h, int *n){ 	SLIST *p; 	p = h->next; 	while(p!=NULL){ 		(*n)++; 		p = p->next; 	} 	return 0; }  void main(void){ 	SLIST *head; 	int a[N] = {12, 87, 45, 32, 91, 16, 20, 48}, num; 	head = creatlist(a); 	outlist(head); 	fun(head, &num); 	printf("\nNumber = %d\n", num); }  SLIST *creatlist(int *a){ 	SLIST *h, *p, *q; 	int i; 	h = p = (SLIST*)malloc(sizeof(SLIST)); 	for(i=0; i<N; i++){ 		q = (SLIST*)malloc(sizeof(SLIST)); 		q->data = a[i]; 		p->next = q; 		p = q; 	} 	p->next = 0; 	return h; }  void outlist(SLIST *h){ 	SLIST *p; 	p = h->next; 	if(p==NULL) 		printf("\nThe list is NULL!\n"); 	else{ 		printf("\nHead"); 		do{ 			printf("->%d", p->data); 			p = p->next; 		}while(p!=NULL); 	} 	printf("->End\n"); } 

结果2_4