数据结构——单链表的简单实现

//单链表的实现
#include <stdio.h>
#include <stdlib.h> 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//判空函数
bool Empty(LinkList &L){
	if(L->next==NULL)
		return true;
	return false;	
} 

//单链表输出函数
bool LinkList_Output(LinkList &L){
	LinkList head = L->next;
	if(Empty(head)){
		printf("链表为空！\n");
		return false;
	}
	while(head){
		printf("%3d",head->data);
		head = head->next;
	}
	printf("\n");
	return true;
} 

//头插法建立单链表
LinkList List_HeadInsert(LinkList &L){
//从表尾到表头逆向建立单链表,每次都在头结点之后插入元素
	LNode *s;int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	printf("头插法：Please input a serious of numbers:");
	scanf("%d",&x);
	while(x!=9999){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d",&x);		
	}
	return L;
} 

//尾插法建立单链表
LinkList List_List_TailInsert(LinkList &L){
//从表头到表尾正向建立单链表
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	LNode *s,*r = L;
	printf("尾插法：Please input a serious of numbers:");
	scanf("%d",&x);
	while(x!=9999){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d",&x);
	} 
	r->next = NULL;
	return L;
} 

//按照序号查找结点值
LNode *GetElem(LinkList L,int i){
//本算法取出单链表L（带头结点）中第i个位置的结点指针
	 int j = 1;
	 LNode *p = L->next;
	 if(i == 0)
	 	return L;
	if(i < 1)
	return NULL;
	while(p&&j<i){
		p=p->next;
		j++;
	} 
	return p;
}

//按照值查找表结点
LNode *LocateElem(LinkList L,int e){
	LNode *p = L->next;
	while(p!=NULL&&p->data != e)
		p = p->next;
	return p;
}

//插入结点函数
bool LinkList_Insert(LinkList L,int i,int e){
	LNode* p = L->next;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	p = GetElem(L,i - 1);
	s->data = e;
	s->next = p->next;
	p->next = s;
}

//删除结点函数
bool LinkList_Delete(LinkList L,int i){
	LinkList p = GetElem(L,i - 1);
	LinkList s = p->next;
	p->next = s->next;
	free(s);
} 

//求表长函数
int LinkList_GetLength(LinkList L){
	int length = 0;
	while(!Empty(L)){
		length++;
		L=L->next;
	}
	return length;
}

int main(){
	LinkList list;
	int i,result,e;
	LinkList node;
	LNode *s;
	printf("输入9999代表结束输入...\n");
	List_HeadInsert(list);
	printf("头插法输出结果：\n");
	LinkList_Output(list);
	List_List_TailInsert(list);
	printf("尾插法输出结果：\n");
	LinkList_Output(list);
	printf("按序号查找结点的值：\n");
	scanf("%d",&i);
	node = GetElem(list,i);
	printf("结果是%d\n",node->data); 
	printf("按值查找结点：\n");
	scanf("%d",&i);
	node = LocateElem(list,i);
	printf("结果是%d\n",node->data); 
	printf("请输入要插入的新结点和位置：\n");
	scanf("%d",&e);
	scanf("%d",&i);
	LinkList_Insert(list,i,e);
	LinkList_Output(list);
	printf("请输出要删除结点的位置：\n");
	scanf("%d",&i);
	LinkList_Delete(list,i);
	printf("结果是：\n");
	LinkList_Output(list);
	printf("表长是：%d",LinkList_GetLength(list));
	return 0;
}