学步园

链表操作，测试下 通过 指向结点的指针以及 指向结点指针的指针 完成 链表操作。

//链表的实现
#include <stdio.h>
#include <malloc.h>

#define ElemType int
#define LIST_INIT_SIZE 20
#define OK 1
#define ERROR 0

typedef struct Node{
	int data;
	struct Node *next;
}Node, *LinkList;

int CreateList(LinkList *list, int n);
int InsertList(LinkList list, int pos, int n);
int DelList(LinkList *list, int pos, int *n);
int MergeList(LinkList *des_list, LinkList *src_list);//将src_list合并至des_list中，两列表有序 从小到大排列
int ListTraverse(LinkList list); //可传指针，减少复制
int ListLength(LinkList list);
int DestroyList(LinkList *list);//摧毁链表，表头+结点
int ClearList(LinkList *list);//置为空表
int InsertList_p(LinkList *list, int pos, int n); 

int LocatePos(LinkList list, int i, LinkList *des);//用des指向list中第i个结点
int MakeNode(LinkList *node, ElemType e);//
int InsFirst(LinkList *list, LinkList p);
int DelFirst(LinkList list, LinkList p);

#define _POINT_

int main()
{
	LinkList list_q = NULL;
	LinkList list_p = NULL;
	LinkList des = NULL;
	int n, m;

	CreateList(&list_q, 3);
	printf("create list,length:%d \n", ListLength(list_q));
	ListTraverse(list_q);

	MakeNode(&des, 5);
	LocatePos(list_q, 2, &des);

	InsFirst(&list_q, des);
	printf("first insert,length:%d \n", ListLength(list_q));
	ListTraverse(list_q);

	DelFirst(list_q, des);
	printf("first del,length:%d \n", ListLength(list_q));
	ListTraverse(list_q);

	CreateList(&list_p, 3);
	printf("create list,length:%d \n", ListLength(list_q));
	ListTraverse(list_p);


	MergeList(&list_p, &list_q);
	printf("after merge,length:%d \n", ListLength(list_p));
	ListTraverse(list_p);


	ClearList(&list_p);
	printf("after clear,length:%d \n", ListLength(list_p));
	ListTraverse(list_p);

	//CreateList(&list_q, 3);//list_q在Mergelist中被释放，需重建
#ifndef _POINT_
	if (InsertList(list_p, 1, 3))
	{
		ListTraverse(list_p);
		printf(" 1 insert length:%d \n", ListLength(list_p));
	}
	if (InsertList(list_p, 3, 6))
	{
		ListTraverse(list_p);
		printf(" 2 insert length:%d \n", ListLength(list_p));
	}
	if (InsertList(list_p, ListLength(list_p) + 1, 5))
	{
		ListTraverse(list_p);
		printf(" 3 insert length:%d \n", ListLength(list_p));
	}

	if (InsertList(list_p, ListLength(list_p) + 2, 5))
	{
		ListTraverse(list_p);
		printf(" 4 insert length:%d \n", ListLength(list_p));
	}
	if (InsertList(list_p, ListLength(list_p) + 12, 5))
	{
		ListTraverse(list_p);
		printf(" 4 insert length:%d \n", ListLength(list_p));
	}
#else
	if (InsertList_p(&list_p, 1, 3))//边界测试
	{
		printf("1st insert length:%d \n", ListLength(list_p));
		ListTraverse(list_p);
	}
	if (InsertList_p(&list_p, 3, 6))
	{
		printf("2nd insert length:%d \n", ListLength(list_p));
		ListTraverse(list_p);
	}
	if (InsertList_p(&list_p, ListLength(list_p) + 1, 5))//边界测试
	{
		printf("3th insert length:%d \n", ListLength(list_p));
		ListTraverse(list_p);
	}
	if (DelList(&list_p, 1, &n))//边界测试
	{
		printf("del 1st num:%d\n", n);
		ListTraverse(list_p);
	}
	if (DelList(&list_p, ListLength(list_p), &m))//边界测试
	{
		printf("del last num:%d\n", m);
		ListTraverse(list_p);
	}
 	if (InsertList_p(&list_p, ListLength(list_p) + 2, 5)) //边界测试
	{
		printf("insert len+2 length:%d \n", ListLength(list_p));
		ListTraverse(list_p);
	}
#endif

	return 0;
}

int CreateList(LinkList *list, int n) //创建带表头的链表  从尾到头
{
	int i = 0;
	LinkList p;

	*list = (LinkList)malloc(sizeof(Node));//创建头结点
	if(!(*list))
		return ERROR;
	(*list)->next = NULL;

	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		if (!p)
			return ERROR;
		
		printf("input data:");
		scanf_s("%d",&p->data);
		p->next = (*list)->next;
		(*list)->next = p;
	}
	return OK;
}

int ListTraverse(LinkList list)
{
	LinkList p = list->next;//指向第一个节点
	while(p)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");

	return OK;
}

/*在第pos位置之前添加，1<=n<= length +1*/
int InsertList(LinkList list, int pos, int n) 
{
	int i = 0;
	LinkList p = list; //指向头
	LinkList temp;

	if(pos < 1)
		return ERROR;
	for (i = 0; i< pos-1 && p;i++) //使指针 指向 pos - 1 的位置, !p保证 pos-1 <=length+1
	{
		p = p->next;
	}//退出3中可能 (1)i == pos -1  正确 (2)p == null (3)兼有  (2)(3)为超过length+1
	if(!p || i != pos-1) 
	{
		printf("beyond the limit\n");
		return ERROR; //确认指针 指向 pos - 1 的位置
	}
	temp = (LinkList)malloc(sizeof(Node));
	if (!temp)
	{
		return ERROR;
	}
	temp->data = n;
	temp->next = p->next;
	p->next = temp;

	return OK;
}

int DelList(LinkList *list, int pos, int *n)
{
	int i;
	LinkList p = *list;//p指向标头
	LinkList q;
	
	if (pos < 1)
		return ERROR;
	for(i = 0; (i < pos-1)&&(p->next); i++) //指向pos-1
	{
		p = p->next;
		//边界检测
	}	
	if ((i != pos-1)||(!(p->next)))
		return ERROR;
	
	q = p->next;
	*n = q->data;
	p->next = q->next;
	free(q);

	return OK;
}

int ListLength(LinkList list)
{
	int length = 0;
	LinkList p = list;

	if (!list)//边界检测
		return ERROR;

	while (p->next)
	{
		length++;
		p = p->next; 
	}
	return length;
}

int InsertList_p(LinkList *list, int pos, int n) 
{
	int i = 0;
	LinkList *p = list; //指向头
	LinkList temp;

    LinkList q = *list;
	if (pos < 1)
	{
		return ERROR;
	}
	for (i = 0; i < pos-1 && q ;i++) //指向 pos - 1 的位置
	{
		q = q->next;	
	}
	if ( !q || i != pos-1 )
	{
		printf("beyond limit\n");
		return ERROR;
	}
	temp = (LinkList)malloc(sizeof(Node));
	temp->data = n;
	temp->next = q->next;
	q->next = temp;

	return OK;
}

int MergeList(LinkList *des_list, LinkList *src_list)//两列表有序 从小到大排列
{	
	LinkList des = *des_list;//指向头结点
	LinkList p_des = (*des_list)->next;//指向第一个结点
	LinkList p_src = (*src_list)->next;

	while(p_des && p_src)
	{
		if (p_des->data <= p_src->data)
		{
			des->next = p_des;
			des = des->next;
			p_des = p_des->next;
		}
		else
		{
			des->next = p_src;
			des = des->next;
			p_src = p_src->next;
		}	
	}
	des->next = p_des ? p_des : p_src;//
	free(*src_list);//释放源链表的头结点

	return OK;
}

int DestroyList(LinkList *list)//从表头开始释放
{
	LinkList *t_list = list;//*t_list为 标头
	LinkList p;

	while (*t_list)
	{
		p = (*t_list)->next;
		free(*t_list);
		*t_list = p;
	}
	*list = NULL;  //收尾，是list指向空

	return OK;
}

int ClearList(LinkList *list)//从第一个结点开始释放
{
	LinkList p = (*list)->next;//指向第一个节点
	LinkList q;

	while(p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*list)->next = NULL;

	return OK;
}

int LocatePos(LinkList list, int pos, LinkList *des)//用des指向list中第pos个结点
{
	LinkList p = list;//p指向头结点
	int i = 0;

	if (pos < 1)
		return ERROR;
	while(p && i<pos)//p指向 pos位置，pos次
	{
		p = p->next;
		i++;
	}
	if(!p || i != pos)
		return ERROR;

	(*des)->next = p->next;
	(*des)->data = p->data;

	return OK;
}

int MakeNode(LinkList *node, ElemType e)
{
	*node = (LinkList)malloc(sizeof(Node));
	if (!*node)
		return ERROR;

	(*node)->next = NULL;
	(*node)->data = e;
	return OK;
}

int InsFirst(LinkList *list, LinkList p)//将p指向的结点添加至list第一个位置
{
	LinkList t_list = (*list)->next;//指向第一个节点
	(*list)->next = p;
	p->next = t_list;//p指向结点为第一结点

	return OK;
}

int DelFirst(LinkList list, LinkList p)//p删除第一个结点，并用p指向该结点
{
 	LinkList head = list;
	LinkList q = head->next;//p指向第一个节点
	if (!q)
		return ERROR;
	head->next = q->next;

	return OK;
}

测试结果：

小结：

 对比  int InsertList(LinkList list, int pos, int n);  与   int InsertList_p(LinkList *list, int pos, int n);

上例中对 链表进行插入操作时，既可以 传递 LinkList p_node变量--指向结点的指针，也可传递 LinkList *list指向 链表的指针。

理解不同传递参数的意义：

传递 LinkList p_node时，理解为 传递头结点的地址。  (LinkList == Node*)

传递 LinkList *list 时，理解为传递的为链表的地址。 （链表为指向头结点的指针/地址）

传递不同参数的目的：

获取参数拷贝，还是获取地址 修改该参数的内容。