循环链表的运算和单链表的运算相似，区别仅在 于当需要从头到尾扫描整个链表时判断是否到表尾 的条件不同。在单链表中以指针域是否为“空”作 为判断表尾结点的条件，而在循环链表中则以结点 的指针域是否等于头指针作为判断表尾结点的条件。
顺序结构线性表的运算(插入)
例如要在线性表的第4和第5个元素之间插入一个 值为b的数据元素，则需将第5个至第8个数据元素 依次往后移动一个位置。
顺序结构线性表的运算(插入)
当在第i(1≤i≤n)个元素之前插入一个元素，需将第n个 至第i个元素(n-i+1个)依次向后移动一个位置，算法 描述见P24算法2.4。 算法分析：本算法时间主要耗费在移动元素上，即 执行for循环语句，循环次数为n-i，每执行一次循环， 就移动一个数据元素。所以移动元素的个数取决于 插入的位置。当i=1，从第1个结点到第n个结点之间 的所有结点依次向后移动一位；当i=n+1，则就不需 要移动结点。如果在每个元素之前插入结点的概率 是相同的即1/(n+1)。插入一个结点需移动的个数为： [n+(n-1)+(n-2)+…+2+1]/(n+1)=n/2。算法的时间复 杂度为O(n)。
线性表的应用举例
{ /* LA和LB均非空*/ GetElem(LA，i，ai)； GetElem(LB，j，bj)； if(ai＜bj) { ListInsert(LC，++k，ai)；++i；}/*LA的元素插入到表LC中*/ else if (ai=bj) { ListInsert(LC，++k，bj)；++i；++j；} else { ListInsert(LC，++k，bj)；++j；} } while(i <＝LA_len){ /*如果LA完，则将表LA中的所剩元素插入到表LC中*/ GetElem(LA，i++，ai)； ListInsert(LC，++k，ai)；
定义：n（ 0）个数据元素的有限序列，记作（a1, a2, …, an） ai 是表中数据元素，n 是表长度。
线性表的特点
线性表(linear list)是一种最简单、常用的 数据结构，通常一个线性表是由n(n≥0)个性 质相同的数据元素组成的有限序列。线性表的 长度即为线性表中元素的个数n(n≥0)，当n＝ 0时，称为空表。 非空线性表结构特征：
单链表的基本运算
单链表是一种非随机存取的结构，在单链表中要寻 找某个元素必须从头指针开始进行遍历。 查找：见P29算法2.8 插入：在单链表中插入一个结点有三种情况。(1) 将新结点插入在链表的第一个结点前；(2) 将新结 点插入在两个结点之间；(3) 将新结点插入在链表 的最后一个结点后。参见P30算法2.9。 删除：参见P30算法2.10。 创建：参见P31算法2.11(往前插入)。 两个有序链表的合并：参见P31算法2.12。
线性表的顺序实现
各种高级语言中的一维数组也具有随机存取的特 性，因此常用一维数组来表示线性表。在C语言 中就是用数组来表示顺序存储结构的线性表。 建立一个一维数组V[0，1，…，n-1]，使数据元 素ai的下标与数组V的下标i相关联，把a1，a2， a3，…，ai，ai+1，…，an依次相继存入存储单元 V[0]，V[1]，V[2]，…，V[i-1]，V[i]，…，V[n-1] 中。数组V中的第i个分量V[i-1]就是线性表中第i 个数据元素在内存中的映像，只要给出一个下标 值i-1，就可以存取元素ai。
data：数据域，存放结点的值； next：指针域，存放直接后继结点的地址。 链表正是通过每个结点的指针域将线性表中n个结 点按其逻辑顺序链接在一起的。 如果链表中的每个结点只有一个指针域，该种链表 则称为单链表(或线性链表)。
每个链表须有一个头指针，指向(存放)表中 第一个结点(地址)。已知一单链表，就是已 知了链表的起地址，即头指针。因此单链 表可以用头指针的名字来命名。例如，头 指针的名字是head，则把链表称为表head。 用C语言描述单链表的结点结构如下： typedef struct LNode { ElemType data; struct Lnode *next; } LNode, *LinkList;
一元多项式的表示及相加
ห้องสมุดไป่ตู้小结
线性表的顺序表示
线性表的顺序表示就是： 把线性表的各个数 据元素依次存储在一组地址连续的存储单元 里。线性表的这种机内表示称为线性表的顺 序映像或线性表的顺序存储结构，用这种方 法存储的线性表简称为顺序表。 假设线性表的每个元素需占用L个存储单元， 并以所占的第一个单元的存储地址作为数据 元素的存储位置。则线性表中第i+1个数据 元素的存储位置LOC(ai+1)和第i个数据元素 的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)＝LOC(ai)+L
设L是LinkList型的变量，则L为单链表的头指针，它 指向表中第一个结点。若L为“空”(L＝NULL)，则 所表示的线性表为“空”表，其长度n为“零”。 在有些情况下，需要在单链表的第一个结点之前附 设一个结点，称之为头结点，头结点的数据域可以 不存储任何信息，也可存储如线性表的长度等附加 信息，头结点的指针域存储指向第一个结点的指针 (即第一个元素结点的存储位置)。此时单链表的头 指针指向头结点。若线性表为空表，则头结点的指 针域为“空”。
线性表的应用举例
x=get(LA，i)； k=i+1； while(k<=length(LA)) { y=get(LA，K)；/**/ if(x==y) Delete(LA，k)；/**/ else k++； } i++； } }/**/
内容提要
线性表的类型定义
线性表的顺序表示与实现 线性表的链式表示与实现
(1)有且只有一个首结点a1，它无前驱； (2)有且只有一个尾结点an，它无后继； (3)其它所有结点有且只有一个前驱，也有且只有一 个后继。
线性表中的数据元素可以是各种各样的，但同 一表中的元素必定具有相同特性。
抽象数据类型线性表的定义
线性表数据结构： List=(D，R) 数据对象： D={ ai| ai∈Elemtype，i=1， 2，…，n，i>=1} 数据关系： R={< ai-1，ai>| ai-1，ai，∈D， i=2，3，…，n} 。 抽象数据类型线性表的定义：见P19。
顺序结构线性表的运算(插入)
线性表的插入操作是指在线性表的第i-1个数 据元素和第i个数据元素之间插入一个新的数 据元素，就是要使长度为n的线性表： (a1，…，ai-1，ai，…，an) 变成长度为n+1的线性表： (a1，…，ai-1，b，ai，…，an+1) 如果在第i(1≤i≤n)个元素之前插入，就必须把 第n到第i个之间的所有结点依次向后移动一 个位置，再将新结点x插入到第i个位置；除 非i=n+1。
顺序结构线性表的运算(删除)
线性表的删除操作是使长度为n的线性表： (a1，…，ai-1 ，ai，，ai+1，…，an ) 变成长度为n-1的线性表： (a1，…，ai-1 ，ai+1，…，an ) 数据元素ai-1 ， ai，ai+1之间的逻辑关系发 生变化，为了在存储结构上反映这个变化， 需要移动表中的元素，把表中的第i+1个到第 n个结点的所有元素依次向前移动一个位置。
顺序结构线性表的特点
优点：


无须为表示结点间的逻辑关系而增加额外的存 储空间； 可以方便地随机存取表中的任一结点 为了保持顺序表中数据元素的顺序，在插入操 作和删除操作时需要移动大量数据。对于有些 需要频繁进行插入和删除操作的问题、以及每 个数据元素所占字节较大的问题来说，将导致 系统的运行速度难以提高。
线性表的应用举例
} while(j＜＝LB_len) { GetElem(LB，j++，bj)； ListInsert(LC，++k，bj)； } }/*MergeList*/
判断下面算法有何功能：
PURGE(LA)/**/ List *LA； { int i=1，k，x，y； while(i<length(LA)) /**/
第二章 线性表
内容提要
线性表的类型定义
线性表的顺序表示与实现 线性表的链式表示与实现
一元多项式的表示及相加
小结
什麽是线性表
英文小写字母表(a，b，c，…，z)是一个长度为26 的线性表。 一年中的四个季节(春，夏，秋，冬)是一个长度为 4的线性表。 学生情况登记表是一个复杂的线性表。 由若干数据项组成的数据元素称为记录(record)， 由多个记录构成的线性表又称为文件(file)。
顺序结构线性表的运算(删除)
通常情况下，删除第i(1≤i≤n)个元素时，需将从第i+1 至第n个元素依次向前移动一个位置，算法描述P24算 法2.5。 算法分析：类似于插入结点时间复杂度的分析，可以 得到删除一个结点的需要移动[(n-1)+(n-2)+(n3)+…+2+1]n=(n-1)/2。时间复杂度也为O(n)。 当在顺序存储结构的线性表中某个位置上插入或删除 一个数据元素时，其时间主要耗费在移动元素上，而 移动元素的个数取决于插入或删除元素的位置。在顺 序存储结构的线性表中插入或删除一个数据元素，平 均要移动表中的一半结点，当线性表中的结点很多时， 算法效率将较低，时间复杂度为O(n)。
缺点：

内容提要
线性表的类型定义
线性表的顺序表示与实现 线性表的链式表示与实现
一元多项式的表示及相加
小结
线性链表的基本概念