a1 a2 ai-1 ai ai+1… an
for( j = i; j < table.length; table.length-1; j++){ j++){ table.data[ j ] = table.data[ j+1 ]; }
SCIE, University of Electronic Science and Technology of China
elemtype data[ MAXNUM ]; int length; }list_type; list_type list;
问题: 如何获得第i的数据元素？ list.data[i] 0≤i ≤ length
SCIE, University of Electronic Science and Technology of China
SCIE, University of Electronic Science and Technology of China
23
2.1.1顺序表
例：设线性表的元素个数为N，请计算插入一个节点 需要移动的节点的平均个数？ 观察：在表首插入一个节点，需要搬移的节点个数为 N 在a1后插入一个节点，需要搬移的节点个数为 N-1 在ai处插入一个节点，则需要搬移的节点个数为 N-i 在各处插入节点的概率为 1/N ∴ 平均搬移节点个数为 1 1 1 1 1 N＋ (N-1) … ＋ (N-2) ＋ ＋ (N-3) + 1 N N N N N 1 1 N(N+1) (N ＋ . = (N-1) ＋ (N-2) ＋…＋ 1 ) = ≈ N/2 N N 2
SCIE, University of Electronic Science and Technology of China
8
2.1.1顺序表
typedef struct list_type{ elemtype data[ MAXNUM ]; int length; }list_type; list_type table; 。。。 for( i = 0; i < table.length; i++ ){
18
2.1.1顺序表
算法
void delete(table, location){
1、从ai节点开始，向后逐个向前搬动节点， 挤掉第i个元素
2、数组长度因为减少了一个新元素而减一
}
SCIE, University of Electronic Science and Technology of China
第二章 线性结构
线性表 堆栈 队列 串 二维数组
SCIE, University of Electronic Science and Technology of China
1
2.1线性表
线性表的定义
线性表特点：
线性表是n个相同类型数据元素的有限线性 序列，通常记为（a1, a2,a3,……,an）。
SCIE, University of Electronic Science and Technology of China
22
2.1.1顺序表
数组顺序存储结构的特点 元素随机获取特性。 存取时间短，存取时间与位置无关 算法效率（时间复杂度）： O(1) 元素更动的搬移性 平均N/2次的搬移 算法效率 O(n)
2.1线性表
逻辑结构：元素及元素之间的关系为线性；
（1）有且仅有一个开始节点（该节点只有一个直接后继 节点，没有直接前趋节点）
（2）有且仅有一个结束节点（该节点只有一个直接前 趋节点，没有直接后继节点） （3）其余节点有且仅有一个直接前趋和一个直接后继
SCIE, University of Electronic Science and Technology of China
3
2.1线性表
线性表不同的实现方式：
2.1.1顺序表 顺序表定义 顺序表基本操作： 遍历、插入、删除 顺序表算法分析 2.1.2单链表 2.1.3双向链表 2.1.4循环链表 数组存储
链接存储
SCIE, University of Electronic Science and Technology of China
6
2.1.1顺序表
二、顺序表的基本操作
遍历（查询） 插入 删除 ……
SCIE, University of Electronic Science and Technology of China
7
2.1.1顺序表
遍历运算
问题描述
在第1个元素到第length个元素依次取值
a1 a 2 … a i … a n
SCIE, University of Electronic Science and Technology of China
15
2.1.1顺序表
删除运算
问题描述：删除第i个元素 算法实现分析
删除算法是否与插入 算法一样有个方向和 过程的问题？
a1 a2 ai－1 ai ai+1
…
an
a1 a2 ai－1 ai ai+1
SCIE, University of Electronic Science and Technology of China
21
2.1.1顺序表
编写算法的一般步骤： 1、分析问题描述 输入，输出及模块功能等 2、分析算法实现的总体框架，关键问题的突破方法 3、核心算法的实现 4、算法补充完善， 如：增加算法有效性的保护措施——越界判断等
各元素数据类型必须相同
数据ai可以是数字、字符和记录等 例1 (1,1,2,3,5,8,13); 例2 (Sun，Mon，The，wed，Thu，Fri，Sat） 学号 姓名 成绩 例3 学生成绩表
001 002 … 丁一 马二 … 87 80 …
2
SCIE, University of Electronic Science and Technology of China
19
2.1.1顺序表
void delete(table, location){ location ＝ location － 1; if(table->length < 1) error(3); else{ if(location < 0 || location > table->length) error(4); else{ for(j = location ; j < table->length-1; j++){ } } } table->data[ j ] = table->data[ j+1 ];
17
2.1.1顺序表
算法
void delete(table, location){ }
输入
table：线性表指针 location：需要删除的节点位置
输出
table：线性表指针
SCIE, University of Electronic Science and Technology of China
};
SCIE, University of Electronic Science and Technology of China
13
2.1.1顺序表
void insert(table, new_node, location){ location ＝ location －1; if(table->length >= MAXNUM) error(1); else{ if(location<0 || location >table->length) error(2); else{ for(j = table->length-1 ; j >= location; j--){ table->data[ j+1 ] = table->data[ j ]; } table->data[ location ] = new_node; } } table->length = table->length +1; }
SCIE, University of Electronic Science and Technology of China
14
2.1.1顺序表
void error(int number){ switch(number){ case 1: printf(“the table is full”); break; case 2: printf(“can’t insert at location”); break; default: printf(“unknown error”); } }
SCIE, University of Electronic Science and Technology of China
2.1.1顺序表
算法
void insert( table, new_node, location){
输入：
}; }；
table: 指向线性表的指针 new_node：需要插入的元素 location：插入的位置，在其之前插入
table->length = table->length -1;
SCIE, University of Electronic Science and Technology of China
}
20
2.1.1顺序表
void error(int number){ switch(number){ case 1: printf(“the table is full”); break; case 2: printf(“can’t insert at location”); break; case 3: printf(“the table is empty”); break; default: printf(“unknown error”); } }