数据结构----单链表升级版

以下内容只是学习记录：

一、单链表管理模式：

 对于单链表增加修改数据只需要管理first last size，即定义两个结构体，一个结构体是Node节点，另一个结构体是管理Node节点的List链表

二、单链表结构体定义：

#define ElemType int
typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node, *PNode;
typedef struct List
{
	PNode first;
	PNode last;
	size_t size;
}List;

二、单链表功能代码实现：　

　　1、单链表初始化：

void InitList(List *list)
{
	list->first = list->last = (Node *)malloc(sizeof(Node));
	assert(list->first!=NULL);
	list->size = 0;
}

　　2、功能代码实现：

测试Main文件：

#include "SList.h"

void main()
{
	List mylist;
	InitList(&mylist);
	ElemType Item;
	Node *p = NULL;
	int select = 1;
	while (select)
	{
		printf("***************************************************\n");
		printf("*	[1] push_back				[2] push_front		*\n");
		printf("*	[3] show_list				[4] pop_back		*\n");
		printf("*	[5] pop_front				[6] insert_val		*\n");
		printf("*	[7] find    				[8] length		*\n");
		printf("*	[9] delete_val				[10] sort		*\n");
		printf("*	[11] reverse				[12] clear		*\n");
		printf("*	[13] destroy				[0] quit_system		*\n");
		printf("***************************************************\n");
		printf("请选择：>");
		scanf("%d",&select);
		if (select == 0)
			break;
		switch (select)
		{
			case 1:
				printf("请输入要插入的数据（-1结束）：");
				while (scanf("%d", &Item), Item != -1)
				{
					push_back(&mylist, Item);
				}
				
				break;
			case 2:
				printf("请输入要插入的数据（-1结束）：");
				while (scanf("%d", &Item), Item != -1)
				{
					push_front(&mylist, Item);
				}
				break;
			case 3:
				show_list(&mylist);
				break;
			case 4:
				pop_back(&mylist);
				break;
			case 5:
				pop_front(&mylist);
				break;
			case 6:
				printf("请输入要插入的数据：");
				scanf("%d",&Item);
				insert_val(&mylist, Item);
				break;
			case 7:
				printf("请输入要查找的数据：");
				scanf("%d",&Item);
				p = find(&mylist, Item);
				if (p == NULL)
				{
					printf("要查找的数据在链表中不存在\n");
				}
				else
				{
					printf("要查找的数据为：%d", p->data);
				}
				break;
			case 8:
				printf("链表的长度为：%d\n", length(&mylist));
				break;
			case 9:
				printf("请输入要删除的值：");
				scanf("%d", &Item);
				delete_val(&mylist, Item);
				break;
			case 10:
				sort(&mylist);
				break;
			case 11:
				reverse(&mylist);
				break;
			case 12:
				clear(&mylist);
				break;
			case 13:
				//destroy(&mylist);
				break;
			case 14:
				break;
			default:
				printf("输入的命令错误，请重新输入.\n");
				break;
		}
	}
	destroy(&mylist);
}

h文件：

#pragma once
#ifndef __SLIST_H_
#define __SLIST_H_
#include "stdio.h"
#include "malloc.h"
#include "assert.h"

#define ElemType int
typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node, *PNode;
typedef struct List
{
	PNode first;
	PNode last;
	size_t size;
}List;
void InitList(List *list);
void push_back(List *list, ElemType x);
void push_front(List *list, ElemType x);
void show_list(List *list);
void pop_back(List *list);
void pop_front(List *list);
void insert_val(List *list, ElemType x);//前提是数据有序
Node *find(List *list, ElemType key);
int length(List *list);
void delete_val(List *list, ElemType key);
void sort(List *list);
void reverse(List *list);
void clear(List *list);
void destroy(List *list);


////////////////////////////////////////
typedef Node* It;
Node* _buynode(ElemType x);
It begin(List *list);
It end(List *list);
void insert(List *list, It pos, ElemType x);

#endif

　c文件：

#include "SList.h"

void InitList(List *list)
{
	list->first = list->last = (Node *)malloc(sizeof(Node));
	assert(list->first!=NULL);
	list->first->next = NULL;
	list->last->next = NULL;
	list->size = 0;
}

void push_back(List *list, ElemType x)
{
	insert(list,end(list),x);
}

/*
void push_back(List *list, ElemType x)
{
	//Node *s = _buynode(x);
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s!=NULL);
	s->data = x;
	s->next = NULL;
	list->last->next = s;
	list->last = s;
	list->size++;
}
*/

void push_front(List *list, ElemType x)
{
	insert(list, begin(list), x);
}

/*
void push_front(List *list, ElemType x)
{
	//Node *s = _buynode(x);
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x; 
	s->next =list->first->next;
	list->first->next = s;
	list->last = s;
	if (list->size == 0)
	{
		list->last = s;
	}
	list->size++;
}
*/
void show_list(List *list)
{
	Node *p = list->first->next;
	while (p != NULL)
	{
		printf("%d-->", p->data);
		p = p->next;
	}
	printf("Null.\n");
}

void pop_back(List *list)
{
	if (list->size == 0)
		return;
	Node *p = list->first;
	while (p->next != list->last)
	{
		p = p->next;
	}
	free(list->last);
	list->last = p;
	list->last->next = NULL;
	list->size--;
}

void pop_front(List *list)
{
	if (list->size == 0)
		return;
	Node *p = list->first->next;
	list->first->next = p->next;
	free(p);
	list->size--;
	if (list->size == 0)
		list->last = list->first;
}

void insert_val(List *list, ElemType x)
{
	Node *s = _buynode(x);
	/*Node *s = (Node *)malloc(sizeof(Node));
	s->data = x;*/
	Node *p = list->first;
	while (p->next != NULL && p->next->data <= s->data)
	{
		p = p->next;
	}
	if (p->next == NULL)
	{
		list->last = s;
	}
	s->next = p->next;
	p->next = s;
}

Node *find(List *list, ElemType key)
{
	Node *p = list->first;
	while (p->next != NULL && p->next->data != key)//条件顺序不能颠倒
	{
		p = p->next;
	}
	return (p->next);
}

int length(List *list)
{
	return list->size;
}

void delete_val(List *list, ElemType key)
{
	if (list->size == 0)
		return;
	Node *p = find(list, key);
	if (p == NULL)
	{
		printf("要删除的数据不存在\n");
		return;
	}
	if (p == list->last)
	{
		pop_back(list);
	}
	else if (p->next->next == NULL)
	{
		Node *q = p->next;
		p->data = q->data;
		p->next = q->next;
		free(q);
		q = NULL;
		list->size--;
		list->last = p;
		printf("%p", list->last);
	}
	else
	{
		Node *q = p->next;
		p->data = q->data;
		p->next = q->next;
		free(q);
		q = NULL;
		list->size--;
		

	}

}

void sort(List *list)
{
	if (list->size == 0 || list->size == 1)
		return;
	Node *s = list->first->next;
	Node *q = s->next;
	list->last = s;
	list->last->next = NULL;
	while (q != NULL)
	{
		s = q;
		q = q->next;
		Node *p = list->first;
		while (p->next != NULL && p->next->data <= s->data)
			p = p->next;
		if (p->next == NULL)
		{
			list->last = s;
		}
			
		s->next = p->next;
		p->next = s;

	}
	
}

void reverse(List *list)
{
	if (list->size == 0 || list->size == 1)
		return;
	Node *p = list->first->next;
	Node *q = p->next;
	list->last = p;
	list->last->next = NULL;
	while (q != NULL)
	{
		p = q;
		q = q->next;
		p->next = list->first->next;
		list->first->next = p;
	}
}

void clear(List *list)
{
	if (list->size == 0)
		return;
	Node *p = list->first->next;
	while (p != NULL)
	{
		list->first->next = p->next;
		free(p);
		p = list->first->next;
	}
	list->last = list->first;
	list->size = 0;
}

void destroy(List *list)
{
	clear(list);
	free(list->first);
	list->first = list->last = NULL;
}

/////////////////////////////////////
Node* _buynode(ElemType x)
{
	Node *s = (Node*)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	return s;
}

It begin(List *list)
{
	return list->first->next;
}
It end(List *list)
{
	return list->last->next;//(单链表是NULL)
}

void insert(List *list, It pos, ElemType x)
{
	Node *p = list->first;
	while (p->next != pos)
	{
		p = p->next;
	}
	Node *s = _buynode(x);
	s->next = p->next;
	p->next = s;
	if (pos == NULL)
		list->last = s;
	list->size++;

}

先把代码粘贴上，有空再写关于代码的分析