文档介绍：该【2.2何时选用顺序表、何时选用链表作为线性表的存储结构公开课获奖课件赛课一等奖课件 】是由【非学无以广才】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【2.2何时选用顺序表、何时选用链表作为线性表的存储结构公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据构造
C语言版
内 容
线性表的定义
基于抽象数据类型线性表的操作
线性表的存储构造
基于次序存储构造的线性表操作算法
基于链式存储的线性表操作算法
循环链表的操作算法
双向链表的操作算法
次序存储线性表与链式存储线性表的比较
一元多项式的表达及相加
第2章 线性表
线性表的定义
1、名词术语
·线性表--n个数据元素的有限序列.
记为(a1,a2,……,ai-1,ai,ai+1,……，an)。 例如：26英文字母表(A,B,C,……,X,Y,Z)、一种班级的学生成绩报表等 ·表长--线性表中元素的个数 ·直接前驱元素--线性表中ai-1领先于ai，则ai-1是ai的直接前驱元素 ·直接后继元素--线性表中ai领先于ai+1，则ai+1是ai的直接后继元素
2、线性表的抽象数据类型定义
ADT List{   数据对象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}   数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}   基本操作：     InitList(&L)       操作成果：构造一种空的线性表L。    …… }ADT List
基于抽象数据类型线性表的操作
1、建立一种空的线性表   2、求线性表中元素个数
  3、判断线性表L与否为空   4、取线性表L中第i个元素
  5、在线性表中插入某元素   6、在线性表中删除某元素
  7、求线性表中某元素的前驱元素
  8、求线性表中某元素的后继元素
  9、在线性表中查找某元素   10、两个线性表进行合并
线性表的存储构造
1、两种存储构造：
次序存储--数组
链式存储--链表
2、线性表的次序存储构造
示意图：
存储地址
内存状态
数据元素在线性表中的位序
b
1
b+l
2
…
…
b+(i-1)l
i
…
…
b+(n-1)l
n
b+nl
空闲
…
b+(maxlen-1)l
类型定义：
//---线性表的动态分派次序存储构造---   #define LIST_INIT_SIZE 100     //线性表存储空间的初始分派量   #define LISTINCREMENT 10     //线性表存储空间的分派增量   typedef struct{       ElemType *elem; //存储空间基址       int length; //目前长度       int listsize; //目前分派的存储容量            （以sizeof(ElemType)为单位）   }SqList;
3、线性表的链式存储构造L=(a1,a2,……,an)
示意图：
       
注：(a)为非空表，(b)为空表。
类型定义：
//---线性表的单链表存储构造---
  typedef struct LNode{
  ElemType data;        struct LNode *next;   }LNode,*LinkList;