第二章 数据结构线性表2

例：在顺序表{12，15，33，45，67，89， 57，78}的第三个元素处插入元素44。
12 15 33 45 67 89 57 78 01234567
44
整理ppt
15
程序实现
Templet <class type> int Seqlist<type> ::Insert(type &x, int i){ If(i<0||i>last+1||last==MaxSize-1) return 0; //procondition校验 Else{ last++; for(int j=last;j>i;j--)data[j]=data[j-1]; data[i]=x; //插入 return 1;
整理ppt
10
顺序表上实现的基本运算
1.查找 例：在顺序表{12，15，33，45，67，89，
57，78}查找57（找到），查找66（找 不到）。
12 15 33 45 67 89 57 78
01234567
整理ppt
11
程序实现
Templet <class type> int Seqlist<type>
➢ 在非空的线性表，有且仅有一个开始结
点a1，它没有直接前趋，而仅有一个直 接后继a2；
➢ 有且仅有一个终端结点an，它没有直接 后继，而仅有一个直接前趋a n-1；
➢ 其余的内部结点ai(2≦i≦n-1)都有且仅有 一个直接前趋a i-1和一个直接后继a i+1
整理ppt
5
线性表的特点
线性表 的逻辑结构：线性结构 数据的运算是定义在逻辑结构上的。 运算的具体实现则是在（物理）存储

1
第二章 线性表 2.1 线性表的逻辑结构
1. 线性表的语言定义： n个数据元素的有限序列。
例1 英文字母表（A,B,C,…..Z)是一个线性表
线性表中的数据元素可以由若干个数据项组成。
例2 包含大量记录的登记表 学号 姓名 001 张三 002 李四 …… ……
年龄 18 19 ……
数据元素
2
第二章 线性表
q = & ( L.elem[i-1]) ；
for ( p = & L.elem[L.length-1] ；p >= q ；- - p ) * (p+1) = * p ； // 后移元素 * q = e ； // 插入新元素 ++L.length ；
return OK ；
}
26
第二章 线性表
// 越界处理
31
第二章 线性表
Status ListDelete_Sq ( Sqlist &L ，int i ，ElemType &e ) { if ( i < 1 || i > L.length ) return ERROR ；
p = & ( L.elem[i-1]) ；
e = * p ； // 取第 i 个元素的值 q =& L.elem[ L.length–1] ； for ( ++p；p <= q；++p ) * (p - 1) = * p ； // 前移
O(ListLength(La) ＋ ListLength(Lb))
14
第二章 线性表 算法时间复杂度
前提: GetElem() 和 ListInsert() 的执行时间与表长无关

利用上述定义的线性表,可以实现其它更复杂的操作
例 2-1 假设:有两个集合 A 和 B 分别用两个线性
表 LA 和 LB 表示，即：线性表中的数据元素
即为集合中的成员。现要求一个新的集合A＝
A∪B。
上述问题可演绎为要求对线性表作如
下操作： 扩大线性表 LA，将存在于线性
表LB 中而不存在于线性表 LA 中的 数据元素插入到线性表 LA 中去。
操作步骤：
1．从线性表LB中依次取得每个数据元素;
GetElem(LB, i,e) 2．依值在线性表LA中进行查访;
LocateElem(LA, e, equal（）)
3．若不存在（上述函数返回0），则插入之。
ListInsert(LA, ++LA_len, e)
void union(List &La, List Lb) { La_len = ListLength(La); Lb_len = ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); //取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之
} } // union
时间复杂度 O(ListLength(LA)*ListLength(LB))
例 2-2 已知线性表LA和LB中的数据元素按值非
递减有序排列，现要求将LA和LB归并为一个新
的线性表LC，且LC中的数据元素仍按值非递减

//链表的最大长度
typedef struct {
ElemType data;
int cur;
}componet, SLinkList[MAXSIZE];
第1个元素的下标： SLinkList[0].cur
带头结点的单链表上的基本运算
1 建立单链表 2 单链表查找 3 单链表插入 4 单链表删除第i个结点
} if（i= =j）return p； // 找到了第i个结点 else return NULL； // 找不到,i≤0或i>n }
算法时间复杂度为:
O(Length(*L))
2) 按值查找
算法描述：按值查找是指在单链表中 查找是否有结点值等于e的结点，若有的话， 则返回首次找到的其值为e的结点的存储位 置，否则返回NULL。查找过程从单链表的头 指针指向的头结点出发，顺着链逐个将结点 的值和给定值e作比较。算法实现，算法演 示。
L=(Linklist)malloc(sizeof(Node));//分配头结点
L->next=NULL;
while(flag)
//输入“$”时, flag置0, 建表结
束
{ c=getchar();
if(c!=’$’)
//为新结点分配存储空间
{ s=(Node*)malloc(sizeof(Node)); s->data=c;
链表； • 首尾相接的链表称为循环链表。
循环链表示意图：
head
a1
a2
……
an head
4）头指针、头结点和首元结点的区别 示意图如下：
hea
info
d
a1
a2
…
an ^
头指针 头结点 首元结点

线性结构的定义：
若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 →可表示为：（a1 , a2 , ……, an） 特点① 只有一个首结点和尾结点； 特点② 除首尾结点外，其他结点只有一个直接前驱和一个
直接后继。
简言之，线性结构反映结点间的逻辑关系是 一对一 (1:1) 的。
班级
012002009524 刘禹圻 男
18
2002级计科0201班
012002009613 武 锐 男
18
2002级计科0202班
012002009710 彭 隽 男 012002009801 郭 芳 女
17
2002级计科0203班
18
2002级计科0204班
012002009904 张珍珍 女
18
n--;
// 表长减1
整理ppt
11
删除顺序表中某个指定的元素的示意图如下：
1 12 2 13 3 21 4 24 5 25 6 28 7 30 8 42 9 77
1 12 2 13 3 21 4 24 5 28 6 30 7 42 8 77
整理ppt
12
2.2.3 顺序表的运算效率分析
时间效率分析:
顺序存储方法：用一组地址连续的存储单元依次 存储线性表的元素。
可以利用数组V[n]来实现。
注意：在C语言中数组的下标是从0开始，即： V[n]的有效范围是从 V[0]～V[n-1]
整理ppt
4
线性表顺序存储特点： 1. 逻辑上相邻的数据元素，其物理上也相邻；
2. 若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出（利用数组V[n]的下标）。

2020/4/7
14
2.3.1单链表
2020/4/7
15
2.3.1单链表
单链表的基本操作算法
查找运算
按序号查找 按值查找
插入运算
结点插入到链表的第一个结点前 结点插入到两个结点之间 结点插入到链表的最后一个结点后
删除运算
2020/4/7
16
2.3.1单链表
按序号查找 算法描述：设带头结点的单链表的头指针为L,要查
3
2.1 线性表的基本概念
线性表基本运算 初始化运算InitList(L) 求表长运算ListLength(L) 元素定位运算 LocateElem(L,x) 取元素运算GetElem(L,i,e) 插入运算ListInsert(L,i,x) 删除运算ListDelete(L,i,e) 遍历运算ListTraverse(L）
第2章 线性表
本章的基本内容是：
线性表的逻辑结构 线性表的顺序存储 线性表的链式存储 顺序表和链表的比较
2020/4/7
1
2.1 线性表的基本概念
线性表（Linear List): 是由n(n≥0)个类型相同的数据元素组成的 有限序列，记为（a1，a2，a3，…，an）。
a1
a2
a3
a4
next
2020/4/7
13
2.3.1单链表
上图所示为线性表（Sun，Mon，Tue，Wed，Thu， Fri，Sat）的线性链式存储结构。这种链表有一个头 指针（H），如果线性表非空，H指向链表中第一个结 点，否则它为空指针（即不指向任何结点的指针，通 常用NULL或∧表示）。由于最后一个结点设有直接后 继，所以它的指针域为空。
d
Loc(a1)

线性表的抽象数据类型
Clear_List(&L) //清空线性表 输入：线性表L。 返回结果：将线性表L重置为空表。 List_Empty(&L) //判断线性表是否为空 输入：线性表L。 返回结果：若线性表L为空表，则返回TRUE，否则返回 FALSE。 List_Length(&L) //求线性表的长度 输入：线性表L。 返回结果：线性表L中的数据元素个数。
Next_Elem(& L，cur_e，&next_e) //返回当前元素的后一个元素值 输入：线性表L。 返回结果：若cur_e是线性表L中的数据元素，且不是最后一个，则 用next_e返回它的直接后继元素；否则操作失败，next_e无定义。 List_Insert(&L，i，e) //在线性表的第i个位置之前插入数据元素e 输入：线性表L，1≤ i ≤ List_Length(L)+1。 返回结果：在线性表L中的第i个位置之前插入新的数据元素e，线 性表L的长度加1。
• 例2–2 设一维数组A的下标的取值范围是0 - - 99，每个数组 元素用相邻的5个字节存储。存储器按字节编址，设存储数组 元素A[0]的第一个字节的地址是100，则A[5]的第一个字节的 地址是 。 • 解：第i个元素的存储地址的计算公式为Loc(ai) = Loc(a1) + (i– 1) × d，1 ≤ i ≤ n。因此，Loc(A[5])=100+ (5–0)×5=125。数 组A的第1个元素的下标是0，即A[0]。
• 时间复杂度为： • O(List_Length(LA)*List_Length(LB))
2.2 线性表的顺序存储结构
• 2.2.1 顺序表 • 线性表的顺序存储：是指用一组地址连续的存储单元依次 存储线性表中的数据元素。设a1的存储地址为Loc(a1)，每个 数据元素占用d个字节，则第i个数据元素的地址为 Loc(ai)=Loc(ai)+(i–1)×d，1≤i≤n，如图2.1所示。

●线性表的逻辑结构特征： （1）有且仅有一个开始结点a1,没有前驱，
只有一个直接后继a2 （2）有且只有一个终端结点an,没有后继，
只有一个直接前驱 （3）其余内部结点ai（1<i<n)有且仅有一个
前驱ai-1和一个后继ai+1
一、线性表的概念
● 线性表的基本运算：创建、删除线性表；增、 删、查、改结点；辅助管理操作：求表长等。
三、链表
（1）单链表——建表算法
● 头插法：
head 123
P->next = head->next Head->next = p
12
1
● 尾插法： head 11
last->next = p p->next = NULL
22
3
三、链表
（1）单链表——结点的删除算法
pre dele
head
3
2
1
Link <T> * head; //定义头指针 int len; //存储链表的长度 public: linkList( ){
head= new Link <T>( ); len=0; } ~linkList( ) { Link<T> *p; while(head!=NULL) {
p=head; head=head->next; date <class T>
Class CarrList：public CList<T>{
●顺pr序Tiva*表taeL:：ist;按//T顺类型序的方指式针，存存储储的线性线表性实表例，采用定长 的一维int数ma组xS存ize储; 结//实构例。的最大长度

单链表的删除图例
单链表的删除算法
Status ListDelete(LinkList L,int i,ElemType &e) //算法2.10 { //在带头结点的单链表L中，删除第I个元素，并由e返回其值。 p=L；j=0; while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋 { p=p->next; ++ j; } if(!p->next||j>i-1) return ERROR; // 删除位置不合理 q=p->next; // 删除并释放结点 p->next=q->next; e=q->data; free(q); return OK; }
顺序表的运算
• 插入运算 • 删除运算 • 总结
–由此可见，在顺序表中插入或删除一个数 据元素时，平均约移动表中的一半数据元 素。所以当n很大时，算法的效率是很低的。 若表长为n，则上述算法的时间复杂度为 O(n)。
顺序表的插入图例
顺序表的插入运算
Status ListInsert(SqList &L,int i,ElemType e) // 算法2.4
ai
逆置单链表
逆置单链表的算法如下：
void nz（NODE *h） {// 逆置头指针为h的带表头结点的单链表 NODE *s,*p； p=h->link；// p先指向原表中第一个结点 h->link=NULL；// 逆表的初态为空表 while (p!=NULL) {s=p； // s指向当前逆转的结点 p=p->link； s->link=h->link； h->link=s； // 把s结点插入逆表 } }

t个单元
a1 a2 ai-1 ai ai+1 an
2.2 线性表的顺序存储和实现
线性表的顺序存储结构——顺序表 一 线性表的顺序存储结构 顺序表
顺序表的定义： 一维数组＋表长
例1： 写出线性表（6，17，28，50，92，188）的顺序 存储结构表示。 # define ListSize 100 typedef int ElemType; ElemType List[ListSize]; int length;
思考：采用其它的定义如何初始化空表？
2.2 线性表的顺序存储和实现
三 顺序表应用举例
1. 设有两个按元素值递增有序排列的顺序表A和B，请编写算法将A 和B归并成一个按元素值递增有序排列的线性表C。 void merge(SeqList A,SeqList B,SeqList &C) {i=0;j=0;k=0; while ( i<A.length && j<B.length ) if (A.data[i]<B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[j++]; while (i<A.length ) C.data[k++]= A.data[i++]; while (j<B.length ) C.data[k++]=B.data[j++]; C.length=k; }
调用示例： main() {SeqList L; ElemType e; ．．． delete_ListSq(L,2,e); ．．． }

大长度*/
};
当初始化此类型的一个线性表时，要使list指针指向大小为MaxSize的动 态数组空间。
2.2.2 顺序存储下的线性表的操作实现
1. 初始化线性表L，即进行动态存储空间分配并置L为一个空表 void InitList(struct List *L,int ms) { /*检查ms是否有效，若无效则退出运行*/ if(ms<=0) {printf("ms值非法!\n"); exit(1);} /*置线性表空间大小为ms*/ L->MaxSize=ms; /*动态存储空间分配，若分配失败则退出运行*/ L->list=malloc(ms*sizeof(ElemType)); if(!L->list) { printf("动态存储分配失败!\n"); exit(1); /*执行此函数则中止程序运行，此函数在stdlib.h中有定义*/ } /*初始置线性表为空*/ L->size=0; }
5. 向有序线性表L中插入元素x，使得插入后仍然有序 有序线性表是指按元素值从小到大顺序排列的线性表，如（23,36,45,49,56,73,80） 就是一个有序线性表。向有序线性表中插入一个新元素后要保证仍然是有序的，需要进 行的插入过程为： (1) 检查表空间是否用完，若是则分配更大的存储空间； (2) 采用顺序查找的方法查找出x的插入位置； (3) 从表尾到插入位置止，把所有位置上的元素均后移一个位置； (4) 把新元素写入到空出的位置上； (5) 线性表的长度增1。 算法描述为： void InsertOrderList(struct List *L, ElemType x) { int i,j; /*若数组空间用完则重新分配更大的存储空间*/ if(L->size==L->MaxSize) againMalloc(L); /*顺序查找出x的插入位置*/ for(i=0; i<L->size; i++) if(x<L->list[i]) break; /*从表尾到下标i元素依次后移一个位置，把i位置空出*/

线性表的顺序存储结构可用数组来实现。
线性表的顺序存储结构可用数组来实现。 数组元素的类型就是线性表中数据元素 的类型，数组的大小，最好大于线性表 的长度。因此，顺序存储结构是把线性 表中每个元素a1, a2, a3, …, an依次存放到数 组下标为0, 1, 2,…, n1的位置上。
假设用数组data［MAXSIZE］存储线性 表 A =（a1, a2, a3, …, an） 其顺序存储结构如图2.1所示。
➢2.2.1 线性表的顺序存储结构 ➢2.2.2 顺序表的基本运算 ➢2.2.3 插入和删除运算的时间分析 ➢2.2.4 顺序表的优点和缺点
2.2.1 线性表的顺序存储结构
线性表的顺序存储方法是：将线性表的所有元素 按其逻辑顺序依次存放在内存中一组连续的存储 单元中，也就是将线性表的所有元素连续地存放 到计算机中相邻的内存单元中，以保证线性表元 素逻辑上的有序性。 顺序表的特点是：其逻辑关系相邻的两个结点在 物理位置上也相邻，结点的逻辑次序和物理次序 一致。
图2.1 顺序存储结构示意图
由于线性表中所有结点的数据类型是相同 的，因此每个结点占用的存储空间也是
相同的。假设每个结点占用d个存储单元，
若 线 性 表 中 第 一 个 结 点 a1 的 存 储 地 址 为 LOC(a1) ， 那 么 结 点 ai 的 存 储 地 址 LOC(ai) 可以通过下面的公式计算得到：
【例2.3】学生成绩统计表也是一个线性表， 见表2.1。在线性表中每个学生的成绩是
一个数据元素，它由学号、姓名、数学、 外语、物理、总分这6个数据项组成。该 线性表的长度为5。
学号 1 2 3 4 5
姓名 李华 王放 张利 田勇 成惠
表 2.1 某班学生成绩统计表

2.2 线性表的顺序存储和实现
顺序表-顺序表定义

由上可知，数据的存储逻辑位置由数组的下标决定。 所以相邻的元素之间地址的计算公式为（假设每个数 据元素占有d个存储单元）： LOC（ai）=LOC（ai-1）+d 对线性表的所有数据元素，假设已知第一个数据元 素a0的地址为LOC（a0） ，每个结点占有d个存储 单元， 则第i个数据元素ai的地址为： LOC（ai）=LOC（a0）+i*d 线性表的第一个数据元素的位置通常称做起始位置 或基地址。 在使用一维数组时，数组的下标起始位置根据给定 的问题确定，或者根据实际的高级语言的规定确定。
2.1 线性表抽象数据类型
线性表的分类
顺序存储结构 （元素连续存储、 随机存取结构） 线性表 ADT 链式存储结构 （元素分散存储） 继承 顺序表类 排序顺序表类 继承 单链表类 循环单链表 双链表 继承 排序循环双链表类 排序单链表类

单链表
双链表

循环双链表类
线性表的存储结构
2.2 线性表的顺序存储和实现
线性表的基本操作 求长度：求线性表的数据元素个数。 访问：对线性表中指定位置的数据元素进行存取、替 换等操作。 插入：在线性表指定位置上，插入一个新的数据元素， 插入后仍为一个线性表。 删除：删除线性表指定位置的数据元素，同时保证更 改后的线性表仍然具有线性表的连续性。 复制：重新复制一个线性表。 合并：将两个或两个以上的线性表合并起来，形成一 个新的线性表。 查找：在线性表中查找满足某种条件的数据元素。 排序：对线性表中的数据元素按关键字值，以递增或 递减的次序进行排列。 遍历：按次序访问线性表中的所有数据元素，并且每 个数据元素恰好访问一次。