链表
一.我们至少有两种方法来储存数据
数组
优点：
存取速度快
缺点：
需要一个连续的很大的内存
插入和删除元素的效率很低
链表
链表中每一个元素分成两部分：内容和指针
链表中每一个元素是相互独立的
链表各元素通过指针联系在一起
优点：
内存调用方便，不需要很大的连续内存
插入和删除元素很方便
缺点：
链表中取出某一项必须进行逐项查找（效率低）
参考术语：
头结点
头结点的数据类型和首结点的类型是一模一样的
头结点是首节点前面的那个结点
头结点并不存放有效数据
设置头结点的目的是为了方便对链表的操作
头指针
存放头节结点地址的指针变量，只需要头指针就可以确定整个链表
首结点
存放第一个有效数据的结点
尾结点
存放最后一个有效数据的结点
确定一个链表只需要一个变量
头指针
举例：该程序难度大，不需要完全掌握
#includestdio.h
#includemalloc.h
#includestdlib.h
//定义了一个链表结点的数据类型
structNode
{
intdata;//定义数据域
structNode*pNext;//定义指针域
};
//函数声明
structNode*CreateList(void);
voidTraverseList(structNode*);
//主函数
intmain(void)
{
structNode*pHead=NULL;//pHead用来存放链表头结点的地址
pHead=CreateList();//CreateList()的功能：创建一个非循环单链表
TraverseList(pHead);//TraverseList()的功能：输出一个链表
return0;
}
//定义CreateList()函数
structNode*CreateList(void)
{
intlen;//用来存放有效结点的个数
inti;
intval;//用来临时存放用户输入的结点的值
//分配了一个不存放有效数据的头结点
structNode*pHead=(structNode*)malloc(sizeof(structNode));
if(NULL==pHead)
{
printf("分配失败，程序终止\n");
exit(-1);
}
structNode*pTail=pHead;
pTail-pNext=NULL;
printf("请输入你要生成的链表的结点个数：len=");
scanf("%d",len);
for(i=0;ilen;++i)
{
printf("请输入第%d个结点的值：",i+1);
scanf("%d",val);
structNode*pNew=(structNode*)malloc(sizeof(structNode));
if(NULL==pHead)
{
printf("分配失败，程序终止\n");
exit(-1);
}
pNew-data=val;
pTail-pNext=pNew;
pNew-pNext=NULL;
pTail=pNew;
}
returnpHead;
}
voidTraverseList(structNode*pHead)
{
structNode*p=pHead-pNext;
while(NULL!=p)
{
printf("%d",p-data);
p=p-pNext;
}
printf("\n");
return0;
}
赞赏