null第2单元 线性数据结构（一）第2单元 线性数据结构（一）教学目标：
了解数据结构的有关概念
什么是线性DS、线性表
了解线性DS的特点
了解线性DS的逻辑结构、物理结构以及操作null通过本单元的学习，了解并掌握：
有关数据结构（DS）的基本概念
数据元素、DS、逻辑结构、物理结构、DS的分类及特点、算法、时间复杂度等
线性DS的常用存储结构
顺序、链表、索引、散列存储结构
单向、双向、循环链表等
线性DS的有关算法
增、删、改
学习要求涉及的章节涉及的章节第2章的
2.1 数据结构概述
(P22~P24)
2.2 线性表
(P25~P34)数据结构问题的由来数据结构问题的由来计算机求解问题过程步骤：
实际 问题 求解
问题 模型 算法分析抽象模型求解命令
编程调试程序
编制
程序运行
程序求解
结果结果输出用户
需求数据类型、格式、
逻辑结构数据
逻辑
运算数据的物理
操作问题模型问题模型结构分析—— 线性方程组
人口预报—— 微分方程
优化问题—— 线性规划、非线性规划
振动问题—— 矩阵分析；特征值、特征向量
信息管理—— 二维数据表
下棋 —— 人工智能(树型结构)
交通管理——最佳道路选择(图型结构)一、基本概念 P22一、基本概念 P22数据（Data）
是信息的载体，它可以用计算机表示并加工，如数、字符、符号等的集合。
数据元素（ Data Element）
是数据的基本单位、数据集合中的个体。
数据对象（ Data Object）
具有相同性质的数据元素的集合。
数据结构（Data Structure）
是指同一数据对象中各数据元素间存在的关系。它有三个要素：
DS=数据的逻辑结构+存储结构+数据的运算
数据结构是以数据为加工对象，研究数据组织方式和相关操作方法的学问。也可以说：怎样去组织一批特定的数据。数据结构分类数据结构分类
线性表
栈
队列
串
数组树
二叉树
图线性结构
非线性结构数据结构
DS
1. 数据的逻辑结构1. 数据的逻辑结构 它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述：
DS=（D，R）
其中：
D：是数据元素的有限集合；
R：是数据元素之间关系的集合。举例举例课题组由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。
定义DS如下：
Group=（D，R）
其中：
D={T，G1，…,Gn,S11,…Snm} 1 n 3 , 1 m 2
R={R1,R2}
R1={
|1 i n , 1 n 3}
R2={|1in ,1 j m , 1 n 3 , 1 m 2 }2. 数据的存储结构2. 数据的存储结构又称物理结构
是指数据结构在计算机中的表示(又称映象)，即数据在计算机中的存放。
逻辑结构和物理结构的关系逻辑结构和物理结构的关系 数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进 行 研究、推理、运算等各种操作。
数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无 法进行 任 何 操作。
任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。数据存储结构分类数据存储结构分类
顺序存储结构
链式存储结构
索引存储结构
散列存储结构 顺序存储结构顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构:
特点:
连续存放；逻辑上相邻，物理上也相邻。
结构简单，易实现。
插入、删除操作不便（需大量移动元素）。 d1 d2 …… dn数据域链式存储结构链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构:
特点:
非连续存放,借助指针来表示元素间的关系;
插入、删除操作简单，只要修改指针即可；
结构较复杂，需要额外存储空间。 d1... d2dn ^数据域 指针域散列存储结构散列存储结构在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。
哈希查找中的哈希表就是这样一种存储结构。
特点： 数据元素间无内在联系； 存储形式不定。
索引存储
除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。如果每个节点在索引表中都有一个索引项，则该索引表就被称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表就成为稀疏索引。索引项的一般形式一般是关键字、地址。 3. 数据运算3. 数据运算
数据运算是指对存放在物理结构上的数据，按定义的逻辑结构进行的各种操作。
常见操作有：
输入、插入、删除、查找、修改、排序等。
4、算法与算法分析4、算法与算法分析 算法（Algorithm）
是对特定问题求解步骤的一种描述；
是一组指令的有限集合。
算法和数据结构的关系 P23下
为了充分地利用系统资源；既要效率高、速度快，又要存储空间少。显然，这是矛盾的。
研究算法追求的目标是：
时间和空间的适当和谐算法的特性算法的特性有穷性 一个算法必须总是在执行 有穷步后结束，且每一步都可在有穷时间内完成；
确定性 算法中的每一个指令必须有明确的含义，不能有二义性；
可行性 算法中描述的操作都是可通过已经实现的基本运算、执行 有限次实现的；
输入 一个算法应有0个或多个输入；
输出 一个算法应有1个或多个输出。算法的设计要求算法的设计要求正确性（Correctness）
可读性（Readability）
健壮性（Robustness）
高效率与低存储量null
(1) 算法中对数据的运算和操作
①算术运算：加减乘除
②逻辑运算：与或非
③关系运算：大于、小于、等于、不等于
④数据传输：赋值、输入、输出等
(2) 算法的控制结构算法的基本要素null1.符号与表达式
loop：i＝i＋1
“设x是A中的最大项”（其中A是一个数组）
“将x插入到L之中”（其中L是某个表）
算法描述语言中，关系运算符用＝、≠、＜、＞、≤、≥
逻辑运算符用and(与)、or(或)、not(非)算法描述语言null2.赋值语句
a＝e a←→b a＝b＝e null3.控制转移语句 无条件转移语句 GOTO 标号
条件转移语句 IF C THEN S 或 IF C THEN S1 ELSE S2 null4.循环语句 WHILE语句 WHILE C DO S
功能等价于如下的IF语句： loop：IF C THEN { S GOTO loop } null FOR i＝init TO limit BY step DO S FOR i＝init TO limit DO S
当step＞0时，功能等价于如下的IF语句： i＝init loop：IF i≤limit THEN { S i＝i＋step GOTO loop } FOR语句null当step＜0时，功能等价于如下的IF语句： i＝init loop：IF i≥limit THEN { S i＝i＋step GOTO loop } null5.其他语句
EXIT
RETURN
READ（或INPUT）
WRITE（或PRINT，或OUTPUT）null（1）算法中的注释用【】括起来；
（2）几个短的语句可以写在同一行上，但彼此之间要用分号隔开；
（3）复合语句总是用一对花括号{}括起来作为语句组。
（4）有时为了叙述方便，对算法中的每一行可加上行号。注：需要说明的几点null1. 列举法
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。算法设计基本方法null例
设每只母鸡值3元，每只公鸡值2元，两只小鸡值1
元。现要用100元钱买100只鸡，设计买鸡
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。
假设买母鸡I只，公鸡J只，小鸡K只。nullFOR I＝0 TO 100 DO
FOR J＝0 TO 100 DO
FOR K＝0 TO 100 DO
{ M＝I＋J＋K
N＝3I＋2J＋0.5K
IF ((M＝100)and(N＝100)) THEN
OUTPUT I，J，K
}
RETURN
总循环次数为1013算法1：null FOR I＝0 TO 33 DO
FOR J＝0 TO 50－1.5I DO
{ K＝100－I－J
IF (3I＋2J＋0.5K＝100) THEN
OUTPUT I，J，K
}
RETURN
总循环次数为算法2：null首先，考虑到母鸡为3元一只，因此，最多只能买33只母鸡，即算法1中的外循环只需要从0到33就可以了，没有必要从0到100。 其次，考虑到公鸡为2元一只，因此，最多只能买50只公鸡。又考虑到对公鸡的列举是在算法的第二层循环中，且买一只母鸡的价钱相当于买1.5只公鸡。因此在第一层循环中已确定买I只母鸡的情况下，公鸡最多只能买50-1.5I只，即第二层中对J的循环只要从0到50-1.5I就可以了。 最后，考虑到总共买100只鸡，因此，在第一层循环中已确定买I只母鸡，且第二层已确定买J只鸡的情况下，买小鸡的数量只能是K=100-I-J，即第三层的循环已没有必要了。并且，在这种情况下，条件I+J+K=100自然已经满足。 null #include "stdio.h"
main()
{ int i，j，k；
for (i＝0； i＜＝33； i＋＋)
for (j＝0； j＜＝50－1.5*i； j＋＋)
{ k＝100－i－j；
if (3*i＋2*j＋0.5*k＝＝100.0)
printf("%5d%5d%5d\n"，i，j，k)；
}
}null 运行结果如下：
2 30 68
5 25 70
8 20 72
11 15 74
14 10 76
17 5 78
20 0 80null
2. 归纳法
通过列举少量的特殊情况，经过分析，最后找出一般的关系。
3. 递推
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。算法设计基本方法null例nullnullnullnull4. 递归
将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。
注意：这种逐层分解实际上并没有对问题进行求解，而只是当解决了最简单的问题后，再沿着原来逆分解的过程逐步进行综合，这就是递归的基本思想。算法设计基本方法null编写一个过程，对于输入的参数n，依次打印输出自然数1到n。
PROCEDURE WRT(n)
FOR k＝1 TO n DO OUTPUT k
RETURN
#include "stdio.h"
wrt(int n)
{ int k；
for (k＝1；k＜＝n；k＋＋) printf("%d\n"，k)；
return；
}例:null PROCEDURE WRT1(n)
IF (n≠0) THEN
{ WRT1(n－1)
OUTPUT n
}
RETURN
#include "stdio.h"
wrt1(int n)
{ if (n!＝0)
{ wrt1(n－1)； printf("%d\n"，n)；}
return；
}输出自然数1到n的递归算法。null5. 减半递推技术
所谓“减半”，是指将问题的规模减半，而问题的性质不变。
所谓“递推”，是指重复“减半”的过程。算法设计基本方法nullnullnullnullnull二分法求方程实根的减半递推过程：
首先取给定区间的中点c＝(a＋b)/2。
然后判断f(c)是否为0。
若f(c)＝0,则说明c即为所求的根，求解过程结束；
如果f(c)≠0,则根据以下原则将原区间减半：
若f(a)f(c)＜0，则取原区间的前半部分；
若f(b)f(c)＜0，则取原区间的后半部分。
最后判断减半后的区间长度是否已经很小：
若|a－b|＜ε，则过程结束，取(a＋b)/2为根的近似值；
若|a－b|≥ε，则重复上述的减半过程。例:设方程f(c)＝0在区间【a，b】上有实根，且f(a)
与f(b)异号，利用二分法求该方程的实根。null FUNCTION ROOT(a，b，eps，f)
f0＝f(a)
WHILE (|a－b|≥ε) DO
{ c＝(a＋b)/2； f1＝f(c)
IF (f1＝0) THEN
{ ROOT＝c ；RETURN }
IF (f0*f1＞0) THEN a＝c
ELSE b＝c
}
c＝(a＋b)/2；ROOT＝c
RETURNnull#include "stdio.h”
#include "math.h”
double root(a，b，eps，f)
double a，b，eps，(*f)()；
{ double f0，f1，c；
f0＝(*f)(a)；
while (fabs(a－b)＞＝eps)
{ c＝(a＋b)/2； f1＝(*f)(c)；
if (f1＝＝0) return(c)；
if (f0*f1＞0) a＝c；
else b＝c；
}
c＝(a＋b)/2； return(c)；
}null6. 回溯法
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。算法设计基本方法null
由n2个方块排成n行n列的正方形称为“n元棋盘”。如果两个皇后位于棋盘上的同一行或同一列或同一对角线上，则称它们为互相攻击。
现要求找使n元棋盘上的n个皇后互不攻击的所有布局。例:求解皇后问题。null八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 null方法一：每个皇后在一行。做个8重循环，把每个皇后安排在每行的每个位置都试一遍。 1、棋盘是8*8数组，定义9个空棋盘。 2、第一个皇后从1行1列到1行8列循环。 复制一个空棋盘到棋盘1，在皇后能控制的点上做上标记。 3、第二个皇后从2行1列到2行8列循环。 若本点是前面标注了的被控制点，则此点不能放棋子。 若有地方安排，将棋盘1复制到棋盘2，在棋盘2上将本皇后能控制的点上做上标记。 4、第三个皇后从3行1列到3行8列循环。 若本点是前面标注了的被控制点，则此点不能放棋子。 若有地方安排，将棋盘2复制到棋盘3，在棋盘3上将本皇后能控制的点上做上标记。 ..... 到第8重循环，若8个皇后都有地方安排，则这是八后问题的一个解。 8重循环结束，得八后问题的所有解 null方法二、循环实现 * 用一个 8 位的 8 进制数表示棋盘上皇后的位置： * 比如：45615353 表示： * 第0列皇后在第4个位置 * 第1列皇后在第5个位置 * 第2列皇后在第6个位置 * 。。。 * 第7列皇后在第3个位置 * 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了皇后所有的情况 * 程序中用八进制数用一个一维数组 data[] 表示 null方法三.递归循环，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题： 1、冲突。包括行、列、两条对角线： （1）列：规定每一列放一个皇后，不会造成列上的冲突； （2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； （3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
如果有一个Q 为 chess[i]=j; //则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置 null2、数据结构。 （1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8 （2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8 （3）对角线冲突标记数组C、D。 C[I-J]=0表示第（I-J）条对角线空闲；
C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7 D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16 null3 算法
１、数据初始化。 ２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）: 如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来)，接着进行递归； 如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。 ３、当n>8时，便一一打印出结果。 null方法四.回溯法
假设棋盘上的每一行放置一个皇后，分别用自然数进行编号为1，2，…，n。
首先定义一个长度为n的一维数组q，其中每一个元素q[i]（i＝1，2，…，n）随时记录第i行上的皇后所在的列号。
初始时，先将各皇后放在各行的第1列。即数组q的初值为
q[i]＝1，i＝1，2，…，n
第i行与第j行上的皇后在某一对角线上的条件为
|q[i]－q[j]|＝|i－j|
而它们在同一列上的条件为
q[i]＝q[j]null回溯法的步骤如下：
从第一行（即i＝1）开始进行以下过程：
设前i－1行上的皇后已经布局好，即它们均互不攻击。
现在考虑安排第i行上的皇后的位置，使之与前i－1行上的皇后也都互不攻击。
为了实现这一目的，可以从第i行皇后的当前位置q[i]开始按如下规则向右进行搜索：null①若q[i]＝n＋1，将第i个皇后放在第1列（即置q[i]＝1），且回退一行，考虑重新安排第i－1行上的皇后与前i－2行上的皇后均互不攻击的下一个位置。此时如果已退到第0行（实际没有这一行），则过程结束。
②若q[i]≤n，则需检查第i行上的皇后与前i－1行的皇后是否互不攻击。若有攻击，则将第i行上的皇后右移一个位置（即置q[i]＝q[i]＋1），重新进行这个过程；若无攻击，则考虑安排下一行上的皇后位置，即置i＝i＋1。
③若当前安排好的皇后是在最后一行（即第n行），则说明已经找到了n个皇后互不攻击的一个布局，将这个布局输出（即输出q[i]，i＝1，2，…，n）。然后将第n行上的皇后右移一个位置（即置q[n]＝q[n]＋1），重新进行这个过程，以便寻找下一个布局。nullPROCEDURE QUEEN(n)
定义长度为n的数组存储空间q。
FOR i＝1 TO n DO q[i]＝1
i＝1
loop:
IF (q[i]≤n) THEN
{ k＝1
WHILE ((k＜i)and((q[k]－q[i])*(|q[k]－q[i]|
－|k－i|))≠0)
DO k＝k＋1
IF (k＜i) THEN q[i]＝q[i]＋1回溯法求解皇后问题。null ELSE
{ i＝i＋1
IF (i＞n) THEN
{ OUTPUT q[i](i＝1，2，…，n)
q[n]＝q[n]＋1
i＝n
}
}
}nullELSE
{ q[i]＝1
i＝i－1
IF (i＜1) THEN RETURN
q[i]＝q[i]＋1
}
GOTO loop
RETURNnull#include "stdio.h"
#include "math.h"
#include "stdlib.h"
void queen(int n)
{ int i，j，k，jt，*q；
q＝malloc(n*sizeof(int))；
for (i＝0； i＜n； i＋＋) q[i]＝0；
i＝0； jt＝1；
printf("\n")；
printf("%d queen problem\n"，n)；null while(jt＝＝1)
{ if (q[i]＜n)
{ k＝0；
while ((k＜i)&&((q[k]－q[i])*
(fabs(q[k]－q[i])－fabs(k－i)))!＝0) k＝k＋1；
if (k＜i) q[i]＝q[i]＋1；
else
{ i＝i＋1；
if (i＞n－1)
{ for(j＝0；j＜n；j＋＋)
printf("%5d"，q[j]＋1)；null printf("\n")；
q[n－1]＝q[n－1]＋1；
i＝n－1；
}
}
}
else
{ q[i]＝0； i＝i－1；
if (i＜0) { printf("\n")； free(q)； return； }
q[i]＝q[i]＋1；
}
}
}nullnullnullnullnull算法的描述算法的描述 算法的描述方式（常用的）：
自然语言
流程图 特定的表示算法的图形符号
算法描述 伪语言 包括程序设计语言的三大基本结构（顺序,
选择,循环 ）及自然语言的一种语言（软
件工程）
类语言 类似高级语言的语言，例如，类
PASCAL、类C语言。本书采用一种接近高级语言的算法描述语言。算法的
评价
LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载
算法的评价算法评价的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
：时间复杂度和空间复杂度。
时间复杂度
指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有：
O（1） O（logn） O（n ） O（ n2 ）
常量型 对数型 线性型 平方型
空间复杂度
指算法在计算机上运行所占用的存储空间。度量同时间复杂度。P25 时间复杂度举例时间复杂度举例（a） X =X+1 ； O（1）
（b） FOR I =1 TO n DO
X = X+1； O（n）
（c） FOR I = 1 TO n DO
FOR J = 1 TO n DO O（ n2 ）
X：= X+1；二、线性表二、线性表 是指数据元素之间的关系为一一对应的线性关系的数据结构。例如，一星期七天的英文缩写表示：
（Sun，Mon，The，wed，Thu，Fri，Sat）是一个线性表，其中的元素是字符串，表的长度为7。
线性表虽然简单，但是应用范围非常广泛。（一）线性表的逻辑结构（一）线性表的逻辑结构定义： 线性表是n（n0）个元素a1,a2,…,an 的有限序列；表中每个数据元素，除了第1个和最后1个外，有且仅有一个前趋元素和后继元素。
形式定义：
含有n个数据元素的线性表是一种数据结构，表示为：
Linear_list=( D , R )
其中: D={a1,a2,…,an }
R={|ai-1,ai D ,i=2,…,n}
D是数据元素的有限集合，R是D上逻辑关系的有限集合。相互关系描述相互关系描述1）L 的长度为n（n 0），当n为0时，
表示是空表；
2）每个元素（除了第1个和最后一个元素
外），有唯一的前趋和后继；
3）线性表中各元素间存在着线性关系；
4）均匀性：各元素数据类型必须相同；
5）有序性：各元素是有序的，不可交换次序。
线性表的基本操作线性表的基本操作Setnull（L） 置空表
Length（L） 求表长度；求表中元素个数
Get（L，i） 取表中第i个元素（1i n）
Prior（L，i） 取i的前趋元素
Next（L，i） 取i的后继元素
Locate（L，x） 返回指定元素在表中的位置
Insert（L，i，x）插入元素
Delete（L，x） 删除元素
Empty（L） 判别表是否为空（二）线性表的顺序存储结构（二）线性表的顺序存储结构将线性表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。
采用顺序存储结构的线性表简称为“顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
得到：
adr（ai）=adr（a1）+（i-1）*L
1i n
其中，L 是每个元素占用存储单元的长度。线性表元素存储示意图线性表元素存储示意图 a1a2….ai….元素序号 内存状态 存储地址12…. i….adr(a1)adr(a1)+1 ….adr(a1)+(i-1)….算法1-1 插入算法算法1-1 插入算法算法步骤（将x插入表中第i个位置）:
step1 将第n至第i个元素后移一个存储位置;
step2 将x插入到ai-1之后;
step3 表的长度+1。
线性表采用一维数组存放。C 语言描述为：
#define MAXLENGTH 100
int list [MAXLENGTH]；
int last ；/* last 指示表中最后一个元素的序号*/
后续
课件
超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载
中涉及到C语言描述和具体C语言程序部分仅供参考！！nullx算法1-1 插入算法算法1-1 插入算法insert（int i，int x）
{ int k；
if（last==MAXLENGTH）
{ printf（“线性表已满！\n”); exit(-1); }
if (i<1||i>last+1) /* 插入位置-元素序号 */
{ printf(“插入位置错误!\n” ); exit(-2); }
else
{ for (k=last-1;K>=i-1;k--)
list[k+1]=list[k]; /* 数组下标0-(n-1) */
list [i-1] =x;
++last;
}
}算法1-1 插入算法主程序 参考算法1-1 插入算法主程序 参考#define MAXLENGTH 100 /* 例1-1主程序 */
int list[MAXLENGTH]={5,3,1,10,7,8,-1,4};
int last=8;
main（）
{ int x,j,loc;
printf(“Enter x、loc\n”);
scanf(“%d,%d”,&x,&loc);
for (j=0;j last )
{ printf(“表中不存在位置为i的元素 \n”);
exit(-1);
}
for(k= i-1;k<=last-1;k++)
list[k]=last[k+1];
last--;
} null算法1-2 ——线性表删除算法主程序算法1-2 ——线性表删除算法主程序#define MAXLENGTH 100 /* 例1-2主程序 */
int list[MAXLENGTH]={5,3,1,10,7,8,-1,4};
int last=8;
main（）
{ int j,loc;
printf(“Enter loc\n”);
scanf(“%d”,&loc);
for (j=0;jnext; ; next(head)
head所指向结点的next域表示形式不统一表示形式不统一若没有头结点, 空表和非空表的表示形式将不统一。
空表形式: head = NULL
非空表形式: head . next = addressheadheada1链表举例链表举例由食品组成的单链表（biscuit,butter,cheese,eggs,grapes,jam)
不带头结点。biscuitbuttercheesejamgrapeseggs^head 头指针单链表在存储区的物理状态单链表在存储区的物理状态 Grapes 60biscuit 61cheese 13eggs 1jam NULLbutter 12存储地址 数据域（data） 指针域（next）1
11
12
13
60
6111头指针
head逻辑上相邻，
物理上不相邻2、单链表的操作2、单链表的操作指针的基本操作
单链表的查找get
单链表的插入insert
单链表的删除delete
指针的基本操作指针的基本操作设指针变量p、q的定义为： NODE *p，*q；
对链表的操作实际上是对指针的操作。例如，要删除结点ai，首先要使指针p指向ai，即：
a1......headaian^p指针的基本操作列表指针的基本操作列表p=（NODE*）malloc（sizeof（NODE））
申请一个NODE型结点空间，并将该结点的地址送入p中。
free（p） 释放p指针所指结点的空间
p=q 指针p指向指针q所指的结点
p=q->next 指针p指向指针q所指结点的后继
p=p->next 指针p向后移动一个结点
p->next=q 将指针q所指结点改接为指针p所指结点的后继
p->next=NULL 将指针p所指结点与后继结点断开指针操作的举例指针操作的举例p=q->next p指向q所指结点的后继
aiai-1ai+1aiai-1ai+1qqpp操作前状态操作后状态单链表的查找算法单链表的查找算法单链表查找ai算法操作步骤:
step1 初始化，指针p指向头指针,
计数器置0
step2 p非空且计数器小于i循环
step3 每循环一次，p后移一个位置,
计数器加1
step4 循环结束,返回指向ai 的指针p。
单链表查找算法程序单链表查找算法程序 get（NODE *head,intｉ）/* 查找i 子函*/
｛ NODE *p; /* 结构指针*/
int counter = 0;
p=head->next;
while((p!=NULL)&&(counternext; counter++; }
if((p!=NULL)&&(counter == i))
return p;
else
return NULL;
}单链表插入算法1-3单链表插入算法1-3单链表插入算法操作步骤（将s插到ai-1和ai间）:
step1 找到ai-1的位置,使指针p指向ai-1
step2 申请并生成新结点s
step3 使s插入到ai-1和ai之间
s->next=p->next
p->next=s
s->data=x
(或写为：next(s)← next(p)
next(p) ←s
data(s)=x)ai-1aipxs单链表的插入算法程序单链表的插入算法程序 insert（NODE *head, int i, int x）
{ NODE *p,*s;
if(i==1) p=head;
else
p=get(head,i-1);
if(p==NULL)
{ printf(“插入位置错\n”); exit(0); }
else
{ s=(NODE*)malloc(sizeof(NODE));
s->data=x; s->next=p->next;
p->next=s;
}
} /* 令p指向a i-1 *//* 若i=1，p指向头指针 *//* p为空，说明找不到i位置 *//* p定位成功 */单链表删除算法1-4单链表删除算法1-4算法1-4操作步骤（删除结点ai ）:
step1 找到ai-1的位置,使指针p指向ai-1
step2 使指针t指向p所指结点的后继
step3 使t所指结点ai 脱链
step4 释放t
t=p->next
p->next=t->next
free(t)
亦可写为： p->next =p->next ->next pta i-1aia i+1单链表的删除算法程序单链表的删除算法程序 delete(NODE *head, int i)
{ NODE *p,*t;
if(i==1) p=head;
else p=get(head,i-1);
if(p==NULL)
{ printf(“i<1或 i >表长+1, 无此结点\n”); exit(0); }
if(p->next==NULL)
{ printf(“i=表长+1,无此结点\n”); exit(0); }
else
{ t = p-> next; p->next = t->next;
free(t) ;
}
} /* P定位a i-1操作*//* P定位成功 */3、循环单链表和双向链表3、循环单链表和双向链表链表检索只能从头指针开始，且只能顺链表方向移动。
在单链表中，从表的任一结点ai找其前趋结点，时间复杂度是O（n）。
如果让链表首尾相接，构成环形，这就是单循环链表。
链表可以从两个方向检索，效果更佳；这就是双向循环链表。单循环链表单循环链表单循环链表表示形式：
单循环链表为空的条件: head ↑.next=head
表示形式为:
head...heada1a2an单循环链表特点单循环链表特点从表中任一结点出发，均可以找到表中其它结点。
找其前趋结点的时间复杂度是O（n）。双向循环链表双向循环链表在单向循环链表中，也存在检索前趋结点费时的问题（所需时间是O（n））。
双向循环链表，其存储结构：
struct dnode{
int data；
struct dnode *prior，*next；
}；
typedef struct dnode DNODE；双向循环链表结点结构双向循环链表结点结构 prior data next指向后继结点
指针域数据域指向前趋结点
指针域双向循环链表表示形式双向循环链表表示形式双向循环链表表示形式：
双循环链表为空的条件:
head .prior = head .next = head
表示形式为: headhead......^^ana2a1双向循环链表特点双向循环链表特点 适合于两个方向的移动。
找其前趋结点的时间复杂度是O（1）。
十字链表十字链表
prior data next updown上指针下指针后继结
点指针前趋结
点指针特点：
四个方向可
以自由移动 4、链表结点及标识符4、链表结点及标识符约定： 设指针p指向结点ai ，
ai作为一个变量，其标识符为p
由于p是记录类型，它的分量分别表示为：
数据域标识符为 p .data
后继结点指针域为 p.next
p pp.datap.nextaiai链表结点及各分量标识符（双链表）链表结点及各分量标识符（双链表）约定： 设指针p指向结点ai ，
ai作为一个变量，其标识符为p
p的分量分别表示为： 数据域标识符为 p .
浙公网安备 33021202002483