list1.c

数据结构中单链表的基本操作

#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1
typedef struct elemtype{
	int number;
	char name[15];
	char sex;
}ELEMTYPE;
typedef struct node{
	ELEMTYPE data;
	struct node *next;
}NODE;
//主函数main
void main(){
	//各函数在主函数中声明
	NODE *creat_list(int n);
	int empty_list(NODE *head);
	int length_list(NODE *head);
	ELEMTYPE get_data(NODE *head,int i);
	ELEMTYPE get_succ(NODE *head,int i);
	ELEMTYPE get_pre(NODE *head,int i);
	int replace_data(NODE *head,int i,ELEMTYPE x);
	int insert_data(NODE *head,int i,ELEMTYPE X);
	int delet_data(NODE *head,int i);
	void print_list(NODE *head);
//全局变量的定义
	int n;
	int number;
	NODE *L;
	int L_length=0;
	ELEMTYPE e={0,"null",'f'};
	ELEMTYPE elm={0,"null",'f'};
//开始进入函数调用的代码段
	printf("输入所要创建的单链表的长度：");
	scanf("%d",&n);
	L=creat_list(n);
//输出刚刚建立的单链表
	printf("输出刚刚创建的单链表: \n");
	print_list(L);
//判断这个链表是否为空表
	printf("Is the list called L a empty list ?\n");
	empty_list(L);
	if(empty_list(L)==1) printf("TRUE !\n");
	else printf("FALSE !\n");
//计算这个链表的长度
	printf("Calculate the list length:\n");
	L_length=length_list(L);
	printf("The length of L is %d .\n",L_length);
//读取你想读取的第几个元素
	printf("Input the number of the data that you want :\n");
	scanf("%d",&number);
	e=get_data(L,number);
	printf("The data you want is :%d,%s,%c !\n",e.number ,e.name ,e.sex );
    fflush(stdin);
//读取你想读取的第几个元素的后继
	printf("Input the number of the data whose successor you want :\n");
	scanf("%d",&number);
	e=get_succ(L,number);
	printf("The successor you want is :%d,%s,%c !\n",e.number ,e.name ,e.sex );
    fflush(stdin);
//读取你想读取的第几个元素的前驱
	printf("Input the number whose successor you want :\n");
	scanf("%d",&number);
	e=get_pre(L,number);
	printf("The precursor you want is :%d,%s,%c !\n",e.number ,e.name ,e.sex );
    fflush(stdin);
//替换你想替换的第几个元素
	printf("Input your data and the number in the list where you want replace with your data:\n ");
	scanf("%d,%d,%s,%c",&number,&elm.number,elm.name,elm.sex);
	e=get_data(L,number);
	printf("Before replace number %d data is:%d,%s,%c\n",number,e.number ,e.name ,e.sex );
	replace_data(L,number,elm);
	e=get_data(L,number);
	printf("After replace number %d data is:%d,%s,%c !\n",number,e.number ,e.name ,e.sex );
    fflush(stdin);
//在你想要的位置插入你给定的元素
	printf("Input the position and the data you want to insert :\n");

	scanf("%d,%d,%s,%c",&number,&elm.number,&elm.name,&elm.sex );
	printf("Output the list before insert :\n");
	print_list(L);
	insert_data(L,number,elm);
	printf("Output the list after insert :\n");
	print_list(L);
    fflush(stdin);
//在你想要的位置删除元素
	printf("Input the position where you want to delete elem :\n");
	scanf("%d",&number);
	printf("Output the list before delete !\n");
	print_list(L);
	delet_data(L,number);
	printf("Output the list after delete !\n");
	print_list(L);
    fflush(stdin);
}
//各内部函数的定义部分
NODE *creat_list(int n){
	NODE *head,*newnode,*p;
	int i=0;
	head=(NODE *)malloc(sizeof(NODE));
	if(head==NULL){
		printf("无法创建带头结点的单链表!\n");
		return NULL;
	}
	else{
		head->next=NULL;
		p=head;
        printf("输入%d个元素:\n",n);
		for(i;i<n;i++){
			newnode=(NODE *)malloc(sizeof(NODE));
			if(newnode==NULL){
				printf("内存空闲空间不足，创建失败!\n");
				return NULL;
			}
			newnode->next=p->next;
			p->next=newnode;
			p=p->next;
			printf("请输入第%d个接点的数据域的number:",i+1);
			scanf("%d",&(p->data.number));
			printf("请输入第%d个接点的数据域的name：",i+1);
            fflush(stdin);//强制进行键盘缓冲区清空语句
			scanf("%s",&(p->data.name));
			printf("请输入第%d个接点的数据域的sex：",i+1);
			fflush(stdin);//强制进行键盘缓冲区清空语句 
			scanf("%c",&(p->data.sex));
			printf("\n");
		}
		printf("创建长为%d的单链表成功!\n",n);
		return head;
	}
}
int empty_list(NODE *head){
	if(head->next ==NULL) return TRUE;
	else return FALSE;
}
int length_list(NODE *head){
	int sum=0;
	NODE *p;
	p=head->next;
	while(p!=NULL){
		sum=sum+1;
		p=p->next ;
	}
	return sum;
}
ELEMTYPE get_data(NODE *head,int i){
	ELEMTYPE x={0,"false",'f'};
	NODE *p;
	int j=1;
	if((i<1)||(i>length_list(head))){
		printf("非法位置，无法读取!\n");
		return (x);
	}
	p=head->next ;
	while((p!=NULL)||(j<i)){
		j++;
		p=p->next ;
	}
	return (p->data);
}
ELEMTYPE get_succ(NODE *head,int i){
    ELEMTYPE x={0,"false",'f'};
	NODE *p;
	int j=1;
	if((i<1)||(i>length_list(head))){
		printf("非法位置，无法读取!\n");
		return (x);
	}
	p=head->next ;
	while((p!=NULL)||(j<i)){
		j++;
		p=p->next ;
	}
	if(p->next!=NULL){
		return (p->next->data);
	}
	else{
		printf("第%d个元素无后继，不能读取!\n");
		return (x);
	}
}
ELEMTYPE get_pre(NODE *head,int i){
	ELEMTYPE x={0,"false",'f'};
	NODE *p,*pre;
	int j=1;
	if((i<1)||(i>length_list(head))){
		printf("非法位置，无法读取!\n");
		return (x);
	}
	pre=head;
	p=head->next ;
	while((p!=NULL)||(j<i)){
		j++;
		pre=p;
		p=p->next ;
	}
	if(pre!=head){
		return (pre->data) ;
	}
	else{
		printf("第%d个元素无前驱，不能读取!\n");
		return (x);
	}
}
int replace_data(NODE *head,int i,ELEMTYPE x){
	NODE *p,*pre;
	int j=1;
	if((i<1)||(i>length_list(head))){
		printf("非法位置，无法更改!\n");
		return FALSE;
	}
	p=head->next ;
    while((p!=NULL)||(j<i)){
		j++;
		pre=p;
		p=p->next ;
	}
	p->data =x;
	return TRUE;
}
int insert_data(NODE *head,int i,ELEMTYPE x){
	NODE *p,*pre,*newnode;
	int j=1;
	if((i<0)||(i>(length_list(head)))){
		printf("插入位置非法，不能插入!\n");
		return FALSE;
	}
	newnode=(NODE *)malloc(sizeof(NODE));
	if(newnode==NULL){
		printf("内存无空闲空间，不能插入!\n");
		return FALSE;
	}
	newnode->data=x;
	newnode->next=NULL;
	pre=head;
	p=head->next;
	while((p!=NULL)&&(j<i)){
		pre=p;
		p=p->next;
		j++;
	}
	newnode->next=p;
	pre->next=newnode;
	return TRUE;
}
int delet_data(NODE *head,int i){
	NODE *p,*pre;
	int j=1;
	if(empty_list(head)){
		printf("表已空，不能删除!\n");
		return FALSE;
	}
	if((i<0)||(i>(length_list(head)))){
		printf("删除位置非法，不能删除!\n");
		return FALSE;
	}
	pre=head;
	p=head->next;
	while((p!=NULL)&&(j<i)){
		pre=p;
		p=p->next;
		j++;
	}
	pre->next=p->next;
	free(p);
	return TRUE;
}
void print_list(NODE *head){
	NODE *p;
	p=head;
	printf("链表中全体数据元素:");
	while(p){
		printf("%d,   %s,    %c\n",p->data.number,p->data.name,p->data.sex);
		p=p->next;
	}
	printf("\n");
}