学步园

// pointer.cpp : 定義主控台應用程式的進入點。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

typedef int elemType ;

/************************************************************************/
/*             以下是关于线性表链接存储（单链表）操作的16种算法        */
/************************************************************************/
struct sNode{    /* 定义单链表结点类型 */
    elemType data;
    struct sNode *next;
};

/* 1.初始化线性表，即置单链表的表头指针为空 */
void initList(struct sNode* *hl)
{
    *hl = NULL;
    return;
}

/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
void clearList(struct sNode* *hl)
{

}

/* 3.返回单链表的长度 */
int sizeList(struct sNode *hl)
{
	int len=0;
	while(hl!=NULL)
	{
		len++;
		hl=hl->next;
	}
	return len;
}

/* 4.检查单链表是否为空，若为空则返回１，否则返回０ */
int emptyList(struct sNode *hl)
{
	if(hl!=NULL)
		return 0;
	else
		return 1;
}

/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
elemType getElem(struct sNode *hl, int pos)
{
	int cnt=0;
	if(pos<1)
	{
		printf("Error----> Out range!");
	}
	while(hl!=NULL)
	{
		cnt++;
		if(cnt==pos)
			return hl->data;
		hl=hl->next;
	}
	printf("Error----> Out range!");
	return 0;
}

/* 6.遍历一个单链表 */
void traverseList(struct sNode *hl)
{
	int len=0;
	while(hl!=NULL)
	{
		printf("%d  ",hl->data);
		hl=hl->next;
		len++;
	}
	printf("\n");
	printf("len=%d\n",len);
}

/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
elemType* findList(struct sNode *hl, elemType x)
{
	while(hl!=NULL)
	{
		if(hl->data==x)
			return &(hl->data);
		hl=hl->next;
	}
	return NULL;
}

/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
int updatePosList(struct sNode *hl, int pos, elemType x)
{
	int offset=0;
	while(hl!=NULL)
	{
		offset++;
		if(offset==pos)
		{
			hl->data=x;
			return 1;
		}
		hl=hl->next;
	}
	printf("Error----> Out range!\n");
	return 0;
}

/* 9.向单链表的表头插入一个元素 */
void insertFirstList(struct sNode* *hl, elemType x)
{
	struct sNode *head;
	head=(struct sNode *)malloc(sizeof(struct sNode));
	if(head==NULL)
	{
		printf("Error----> Mallco Fail!\n");
		return;
	}
	head->data=x;
	head->next=*hl;
	*hl=head;
}

/* 10.向单链表的末尾添加一个元素 */
void insertLastList(struct sNode* *hl, elemType x)
{
	struct sNode *temp,*tail;
	tail=(struct sNode *)malloc(sizeof(struct sNode));
	if(tail==NULL)
	{
		printf("Error----> Mallco Fail!\n");
		return;
	}
	tail->data=x;
	tail->next=NULL;

	temp=*hl;
	if(temp==NULL)
	{
		*hl=tail;
		return;
	}
	while(temp!=NULL)
	{
		temp=temp->next;
	}
	temp->next=tail;
}

/* 11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
int insetPosList(struct sNode* *hl, int pos, elemType x)
{
	int len=0;
	struct sNode *list,*new_node;
	new_node=(struct sNode *)malloc(sizeof(struct sNode));
	// 对pos值小于等于０的情况进行处理 
    if(pos<=0){
        printf("Error----> Pos error!\n");
        return 0;
    }
	if(new_node==NULL)
	{
		printf("Error----> Mallco Fail!\n");
		return 0;
	}
	list=*hl;
	new_node->data=x;
	if(pos==1)
	{
		new_node->next=list;
		*hl=new_node;
		return 1;
	}
	else
	{
		while(list!=NULL)
		{
			len++;
			if(len==pos)
			{
				new_node->next=list->next;
				list->next=new_node;
				return 1;
			}
			list=list->next;
		}
		return 0;
	}
}

/* 12.向有序单链表中插入元素x结点，使得插入后仍然有序 假定升序*/
void insertOrderList(struct sNode* *hl, elemType x)
{
	struct sNode *list,*new_node,*pre;
	list=*hl;
	if(list==NULL)
	{
		printf("Error----> Empty list!\n");
		return;
	}
	new_node=(struct sNode *)malloc(sizeof(struct sNode));
	if(new_node==NULL)
	{
		printf("Error----> Mallco Fail!\n");
		return;
	}
	new_node->data=x;
	pre=list;
	if(list==NULL||x<=list->data)    //头结点
	{
		new_node->next=list;
		*hl=new_node;
		return;
	}
	else
	{
		while(list!=NULL)
		{
			if(x<=list->data)
			{
				pre->next=new_node;
				new_node->next=list;
				return;
			}
			pre=list;
			list=list->next;
		}
	}
}


/* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
elemType deleteFirstList(struct sNode* *hl)
{
	elemType temp;
	struct sNode* list;
	list=*hl;
	if(list==NULL)
	{
		printf("Error----> Empty list!\n");
		return 0;
	}
	temp=list->data;
	*hl=(*hl)->next;
	free(list);
	return temp;
}

/* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
elemType deleteLastList(struct sNode* *hl)
{
	elemType temp;
	struct sNode *list,*last;
	list=*hl;
	if(list==NULL)
	{
		printf("Error----> Empty list!\n");
		return 0;
	}
	last=list;
	if(list->next==NULL)
	{
		temp=list->data;
		*hl=NULL;
		return temp;
	}
	else
	{
		while(list->next!=NULL)
		{
			last=list;
			list=list->next;
		}
		temp=list->data;
		last->next=NULL;
		free(list);
		return temp;
	}
}

/* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
elemType deletePosList(struct sNode* *hl, int pos)
{
	int len=0;
	elemType temp;
	struct sNode *list,*last;
	list=*hl;
	if(list==NULL)
	{
		printf("Error----> Empty list!\n");
		return 0;
	}
	if(pos==1)
	{
		temp=list->data;
		(*hl)=(*hl)->next;
		free(list);
		return temp;
	}
	else
	{
		last=list;
		while(list!=NULL)
		{
			len++;
			if(len==pos)
			{
				temp=list->data;
				last->next=list->next;
				return temp;
			}
			last=list;
			list=list->next;
		}
		return 0;
	}
}

/* 16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
int deleteValueList(struct sNode* *hl, elemType x)
{
	struct sNode *list,*last;
	list=*hl;
	if(list==NULL)
	{
		printf("Error----> Empty list!\n");
		return 0;
	}

	if(list->data==x)  //头结点
	{
		*hl=(*hl)->next;
		free(list);
		return 1;
	}
	last=list;
	while(list!=NULL)
	{
		if(list->data==x)
		{
			last->next=list->next;
			free(list);
			return 1;
		}
		last=list;
		list=list->next;
	}
	return 0;
}


int main(int argc, char* argv[])
{
	int i;
	int a[10] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
	struct sNode List,*p;  
	p=&List;
	initList(&p);
	for(i = 9; i >=0; i--){  
        insertFirstList(&p, a[i]);
    }  
	traverseList(p);
	printf("单链表长度：%5d \n", sizeList(p));
	printf("id=：%5d \n", *findList(p,4));
	printf("id=：%5d \n", updatePosList(p,4,9));
	traverseList(p);
	insertFirstList(&p,1);
	traverseList(p);
	insetPosList(&p,6,9);
	deleteFirstList(&p);
	deleteLastList(&p);
	traverseList(p);
	deletePosList(&p,2);
	traverseList(p);
	printf("id=：%5d \n", deleteValueList(&p,2));
	traverseList(p);
	while(1);
}