前言
链表是数据结构中非常重要的一种线性结构,它在线性结构中是离散存储的。在讲链表之前,先谈下typedef(为数据类型取别名)的用法,因为typedef在定义结构体时经常用到,可以起到很好的简化数据类型书写的作用。
实例说明:
#include<stdio.h>
typedef struct Student
{
int sno;//学号
char name[20];//姓名
}*PST,ST;//PST代表了struct Student *,ST代表了struct Student,即分别为其数据类型取别名
int main()
{
ST s={1001,"张三"};
PST pst=&s;
printf("学号:%d\n姓名:%s\n",pst->sno,pst->name);
return 0;
}
链表
链表可理解为n个结点(由数据域和指针域两部分组成)离散分配,彼此通过指针相连,每个结点只有一个前驱结点(除首节点外),每个结点只有一个后继结点(除尾结点外),且每个结点的数据类型相同。
链表中常见的专业术语有:首节点(第一个有效结点,即存放了有效数据),尾结点(最后一个有效结点,指针域为NULL),头结点(是在首结点前附加的一个节点,它没有存放有效数据,也没有存放有效结点个数。在首结点前加一个实际含义的头结点,可以方便我们对链表进行操作),头指针(存放了头结点的地址,即指向了头结点),尾指针(指向结点的地址)。我们通常只需要头指针通过一个函数来对链表进行处理,通过头指针就可以推算出链表的其他信息。链表的分类有:单链表(每个结点指针只能指向后一个结点--尾结点除外),双链表(每个结点有两个指针域,前一个指针域指向前驱结点,后一个指针域指向后继结点),循环链表(能通过任何一个结点找到其它结点--尾结点可以指向头结点),还有非循环链表等;
结点的表示
typedef struct Node
{
int data;//数据域
struct Node *pNext;//指针域,指向本身和它一样的结构体(数据类型)
}NODE,*PNODE;//NODE等价于struct Node,PNODE等价于struct Node*
链表的创建和遍历
实例说明:
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
int data;//数据域
struct Node *pNext;//指针域
}NODE,*PNODE;
PNODE CreateList(void);//void表示无形参
void TraverseList(PNODE);//此处省略形参名
int main()
{
PNODE pHead=NULL;
pHead=CreateList();//创建链表,并将返回的头结点的地址赋给pHead
TraverseList(pHead);//遍历链表
return 0;
}
PNODE CreateList(void)
{
int len;//用来存放有效结点的个数
int i;
int val;//用来临时存放用户输入结点的值
PNODE pHead=(PNODE)malloc(sizeof(NODE));//动态分配一个块内存,该内存用来存放头结点
PNODE pNew;
PNODE pTail=pHead;
pTail->pNext=NULL;
if(NULL==pHead)
{
printf("分配失败,程序终止!\n");
exit(-1);//终止程序运行
}
printf("请输入您要创建链表的结点个数:len=");
scanf("%d",&len);
for(i=0;i<len;i++)
{
printf("请输入第%d个结点的值:",i+1);
scanf("%d",&val);
pNew=(PNODE)malloc(sizeof(NODE));//每循环一次,动态分配一个新临时结点
if(NULL==pNew)
{
printf("分配失败,程序终止!\n");
exit(-1);
}
pNew->data=val;//为新节点数据域赋值
pTail->pNext=pNew;//将新节点挂到尾结点后面
pNew->pNext=NULL;//将新节点的指针域设为空
pTail=pNew;//每次循环,让新节点成为尾节点
}
return pHead;
}
void TraverseList(PNODE pHead)
{
PNODE p=pHead->pNext;//此时p指向首节点
while(p!=NULL)
{
printf("%d ",p->data);
p=p->pNext;//将p的指针域指向下一个结点(指针域为空时,说明已经到了尾结点)
}
printf("\n");
}
注意
1. 第一个结点的指针域指向下一个结点(地址)的整体信息。
2.若p指针指向某个结点(头结点和尾结点除外),则p本身没有指针域,p指向的那个结构体变量(结点)才有指针域。
分享到:
相关推荐
简单实用的创建和遍历链表代码
链表的创建和遍历。这是一个最基本的操作,元素类型定义为int 本源程序包含了链表的创建和遍历操作
本文档讲解C语言 动态链表的创建和遍历;适合刚学习的入门读者
单向链表(一) 结构体、创建链表、遍历链表
线索链表是在二叉链表的基础上增加了结点的前驱和后继,若一结点的左指针为空,则指向其前驱,若右结点为空,则指向其后继结点。
含有链表的遍历 指定位置的查找 删除 链表的创建 面向对象的 C++课程设计
C语言
链表实现二叉树创建和遍历,三种遍历方式实现,二叉树
--- 链表创建与遍历的算法 可
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法。将一棵二叉树的所有左右子树进行交换的算法。
C++先序遍历的顺序建立二叉链表,
二叉树创建及遍历算法
1.先序创建 2.先序遍历递归算法 3.中序遍历递归算法 4.后序遍历递归算法 5.先序遍历非递归算法 6.后序遍历非递归算法 7.中序遍历非递归算法 8.二叉树求深度 9.左孩子右兄弟链表创建树并求深度
采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,根据输入的一棵二叉树的完整先序遍历序列(子树空用’#’表示),建立...
1.初始化 2....遍历链表(设为输出元素7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。。。。。 其中黑体部分必做
一、实验目的 1.掌握二叉树的二叉表存储结构。 2.掌握利用二叉树创建方法。...在计算机中创建如附图1-1所示的二叉树,分别对它进行中序,先序,后序遍历,并输出遍历结果。 注:采用二叉链表作为二叉树的存储结构。
绝对是对数据结构经典算法的程序实现,可以在提供大家C语言程序设计的同时,提高算法分析与设计能力,绝对是大家走出"代码民工"的必然选择...
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
树开始的推荐,以及数的一些用法,包括二叉树的链表结构,以及遍历
[一段可以运行的代码]二叉树的层序创建和后续遍历。 代码一共涉及涉及二叉树、队列、堆栈。二叉树和堆栈采用链表实现,队列采用数组实现。 二叉树本身用链表表示,链表每个节点有3个字段,其中2个是左右指针。 ...