1、数据结构与算法线性表赵颖 中南大学赵颖 中南大学目录n 线性表的定义n 线性表的顺序存储结构n 线性表的链式存储结构 单链表 循环链表 双向（循环）链表n 应用实例赵颖 中南大学目录n 教学重点： 理解线性表的定义及其运算； 理解顺序表和链表的定义、组织、结构特征； 掌握在这两种表上实现的插入、删除和查找的算法； 了解循环链表、双向 (循环 )链表的结构特点和在其上施加的插入、删除等操作。n 教学难点 线性表与线性结构的联系与区别； 顺序表的插入、删除和按值查找的算法 头结点在链表中的作用；删除、插入运算中的指针操作； 双向链表上删除、插入时指针的操作顺序。赵颖 中南大学顺序存储结构n
2、 顺序存储结构（顺序表）优缺点n 优点 逻辑相邻，物理相邻 可随机存取任一元素，可按数组序号访问 存储空间使用紧凑n 缺点 插入、删除操作需要移动大量的元素，平均移动元素为 n/2 必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构；即使是动态分配的方式，每次也需要固定增加一定容量的内存空间，仍然是一种变相的静态存储结构。赵颖 中南大学链式存储结构n 线性表链式存储结构 -简称链表 用一组任意的存储单元存储线性表中的元素；n 结点可以连续，可以不连续存储n 结点的逻辑顺序与物理顺序可以不一致 不但存储数据，还存储数据元素之间的关系。n 表可扩充，无需连续空
3、间，灵活利用存储空间链表是通过一组任意的存储单元来存储线性表中的数据元链表是通过一组任意的存储单元来存储线性表中的数据元素的，对每个数据元素素的，对每个数据元素 ai，除了存放数据元素的自身的信，除了存放数据元素的自身的信息息 ai 之外，还需要和之外，还需要和 ai一起存放其后继一起存放其后继 ai+1 所在的存贮所在的存贮单元的地址，这两部分信息组成一个单元的地址，这两部分信息组成一个 “结点结点 ”。存放数据元。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。素信息的称为数据域，存放其后继地址的称为指针域。a0 a1 a2 a3 a4 first赵颖 中南大学链式存储结构n
4、链表根据结构不同又可以分为： 单链表 循环链表 双向链表n 我们首先学习最简单的单链表赵颖 中南大学单链表n 单链表举例next data数据域 指针域a0 a1 a2 a3 a4 first赵颖 中南大学单链表n 单链表描述形式 单链表简化描述形式n head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值 NULL用（ ）表示。 带头结点的单链表n 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。赵颖 中南大学单链表n 简单的单链表
5、typedef struct node /链表类型，也是节点类型 datatype data; struct node *next; node, *linklist; 是链表类型同时也是节点类型n 带头节点的单链表 typedef strcut node /结点类型 datatype data; struct node *next; node; typedef struct /链表类型 NODE *head; /头节点的指针 linklist; 节点类型和链表类型分开实际上头节点只是为链表的第一个数据节点前面附加了一个节点 ,头节点使得链表定义更清晰实际中 2种都使用得很普遍赵颖 中南大学单链表n 初始化链表 L 带头节点的int InitList(LINK_LIST L) /实际上初始化是创建一个空链表 L-head=(*NODE)malloc(sizeof(Linklist); /为头结点分配存储单元 if (L-head) L-head-next=NULL; return OK; else return ERROR ;带头节点的链表，只有一个节点 头节点 ,并且头节点的指针为 NULL，长度为 0
