链表

一、数组与链表的比较

数组：

优点：存取速度快
缺点：需要一个连续的很大的内心

            插入和删除元素的效率很低

链表：

优点：插入删除元素效率高

   不需要一个连续的很大的内存

缺点：查找某个位置的元素效率低

二、链表的结构

首节点：存放第一个有效数据的节点

尾节点：存放最后一个有效数据的节点

头结点：头结点的数据类型和首节点的类型是一样的

                头结点并不存放有效数据

                头结点是首节点前面的那个节点

                设置头结点的目的是为了对链表的操作

头指针：存放头结点地址的指针变量

                 确定一个链表只需要一个参数：只需要头指针。

/*
	2016年9月11日17:10:57
	链表
*/

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>    //用exit函数需要此声明

struct Node
{
	int data;      //数据域
	struct Node * pNext;     //指针域
};

//函数声明
struct Node * creat_list();
void traverse_list(struct Node * pHead);
 
int main(void)
{
	struct Node * pHead = NULL;
	
	pHead = creat_list();     //创建新链表
	traverse_list(pHead);     //遍历整个链表并将数据域的内容输出
	
	return 0;
}

struct Node * creat_list()
{
	int len;   //有效字节的个数
	int val;   //用来临时存放用户输入字节的值
	int i;
	
	struct Node * pHead = NULL;
	pHead = (struct Node *) malloc(sizeof(struct Node));   //分配了一个不存放有效数据的头结点
	
	if(NULL == pHead)
	{
		printf("内存分配失败，程序终止！
");
		exit(-1);
	}
	
	//pHead->pNext = NULL;
	struct Node * pTail = pHead;
	pTail->pNext = NULL;
	
	printf("请输入要创建链表的个数：");
	printf("len = ");
	scanf("%d", &len);
	
	for(i = 0; i < len; ++i)
	{
		struct Node * pNew = NULL;
		pNew = (struct Node *) malloc(sizeof(struct Node));
		
		if(NULL == pNew)
		{
			printf("内存分配失败，程序终止！
");
			exit(-1);
		}
		
		printf("请输入第%d个链表的值：", i+1);
		scanf("%d", &val);
		
		pNew->data = val;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
		
	}
	
	return pHead;	
}

void traverse_list(struct Node * pHead)
{
	struct Node * p = pHead->pNext;
	while(NULL != p)
	{
		printf("%d
", p->data);
		p = p->pNext;
	}
	
	return;
}

在VC++6.0运行的结果为：