线性表——链表（一）

单链表

主要操作

1. LinkList SetNullList() 创建一个空链表
2. int IsNull(LinkList head) 判断是否为空链表
3. void CreatList_Head(LinkList head) 头插法创建非空链表
4. void CreatList_Tail(LinkList head) 尾插法创建非空链表
5. void Delete_One_Node(LinkList head，DataType x) 删除结点
6. void Insert(LinkList head，DataType x) 插入结点
7. LinkList Find(LinkList head，DataType x) 查找结点

链表数据类型定义

typedef int DataType;
struct Node
{
	DataType data;
	struct Node*next;
};
typedef struct Node*PNode;
typedef struct Node*LinkList;

创建一个空链表

LinkList SetNullList()
{
	PNode head = (LinkList)malloc(sizeof(struct Node));
	if (PNode != NULL)
	{
		head->next = NULL;
		return NULL;
	}
	else
	{
		printf("Alloc failure!\n");
		return NULL;
	}
}

判断是否为空链表

int IsNull(LinkList head)
{
	if (head->next == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

头插法创建非空链表

void CreatList_Head(LinkList head)
{
	DataType data;
	PNode p;
	printf("请输入整型数据以-1结束\n");
	scanf("%d", &data);
	while (data != -1)
	{
		p = (PNode)malloc(sizeof(struct Node));
		p->data = data;
		p->next = head->next;
		head->next = p;
		scanf("%d", &data);
	}
}

尾插法创建非空链表

void CreatList_Tail(LinkList head)
{
	PNode p, q;
	DataType data;
	q = head;
	printf("请输入整形数据以-1结束\n");
	scanf("%d", &data);
	while (data != -1)
	{
		p = (PNode)malloc(sizeof(struct Node));
		p->data = data;
		p->next = NULL;
		q->next = p;
		q = p;
		scanf("%d", &data);
	}
}

删除结点

void Delete_One_Node(LinkList head，DataType x)
{
	PNode p, q;
	p = head;
	q = head->next;
	if (q != NULL)
	{
		if (q->data = x)
		{
			p->next = q->next;
			free(q);
			break;
		}
		q = p;
		q = q->next;
	}
	if (q == NULL)
	{
		printf("not exit!\n");
	}
	else
	{
		printf("delete success!\n");
	}
}

插入结点

void Insert(LinkList head，DataType x)
{
	PNode p, q;
	q = head;
	p = (PNode)malloc(sizeof(struct Node));
	p->data = x;
	if (IsNull)//如果为空链表则用头插法插入结点
	{
		p->next = head->next;
		head->next = p;
	}
	else
	{
		while (q != NULL)
		{
			if (q->next->data > x || q->next == NULL)
				break;
			else
				q = q->next;
		}
	}

	p->next = q->next;
	q->next = p;
}

查找结点

LinkList Find(LinkList head，DataType x)
{
	PNode p;
	p = head->next;
	while (p != NULL)
	{
		if (p->data == x)
			return p;
		else
			p = p->next;
	}
	printf("not find!\n");
	return NULL;
}