当前位置:首页 >> 数学 >>

数据结构第2章线性表-PPT课件_图文

第2章 线性表
2.1 线性表的基本概念 2.2 线性表的顺序存储结构及其运算

2.3 线性表的链式存储结构及其运算
2.4 顺序表和链表的比较 2.5 线性表的应用

本章学习目标
? ? ? ? 掌握线性表的基本概念 重点 掌握顺序表的各种基本操作及实现 掌握单链表、双向链表的的各种基本操作 会用线性表解决实际问题

? 关键:各种基本操作的程序实现 ? 难点:用线性表解决实际问题

2.1 线性表的基本概念
2.1.1 线性表的定义 ? 线性表(List):数据类型相同的n(n≥0)个数据元素组成 的有限序列, L=(a1,a2, …,ai-1,ai,ai+1, …,an) ? 表中数据元素类型相同,可为一个数、字符、结构体 ? 线性表的长度:表中数据元素的个数n; ? 空表:n=0,L=( ); ? 下标i:表示数据元素的位序; ? n>0时a1:表头元素; an:表尾元素; ? ai-1为ai(i>=2)的直接前驱; ai+1为ai(i<=n-1)为的直接 后继

职工工资表 职工 号 001 姓名 性别 年龄 工资

160.5 0 002 32 150.0 蔡三 男 0 003 28 130.0 张四 女 0 每一行数据为一个数据元素(结点)。 …… …… …… …… ……

王二



35

? 线性表的逻辑结构是线性结构
? 元素间是1对1关系 ? 有且仅有一个开始(头)结点 ? 有且仅有一个终端(尾)结点 ? 除开始结点和终端结点外的结点都最多只有一

个直接前驱和一个直接后继 ? 当表中只有一个元素时,它既没前驱也没后继

? 线性表是一种最简单、最常用的(线性)数 据结构

2.1.2 线性表及其基本操作 ? 1.初始化线性表 InitList(L)
? ?

初始条件 线性表L不存在。 运算结果 构造一个空的线性表,n=0。

? 2.求线性表的长度LenList(L)
? 初始条件 表L存在。
? 运算结果 返回线性表中所含数据元素的个数n。

3.读取线性表中的第i个数据元素GetfromList(L,i) ? 初始条件 表L存在。 ? 运算结果 返回线性表L中第i个元素的值或地址 1≤i≤n 。如果线性表为空,或者i超过 了线性表的长度,则报错。 4.按值查找SearchList(L,x) ? 初始条件 线性表L存在,x是给定的一个数据元素。 ? 运算结果 在表L中查找值为x的数据元素,返回x在L 中的位置或地址,若有多个则返回在L中首 次的位序或地址(查找成功);否则,在L中 未找到值为x的数据元素,返回一特殊值表 示查找失败。

5.插入操作InsertList(L,i,x)
? 初始条件 线性表L存在,i表示新元素将要插入的位置 (1≤i≤n+1,n为插入前的表长)。 ? 运算结果 在线性表L的第i个位置上插入一个值为x的新元素,该 元素成为新的第i个数据元素。 原位序为i,i+1,…,n 的数据元素的位序变为i+1,i+2,…,n+l。如果插入位 置i=n+1,则直接在线性表的最后一个数据元素后增加 x,插入后,表长=原表长+1。

6.删除操作:DeleteList(L,i)
? 初始条件 线性表L存在,i表示需要删除的数据元素的位序。 ? 运算结果 如果L为空表或位序i大于线性表长度,则报错。在线性 表L中删除位序为i的数据元素,删除后使位序为i+1,i+2,…,n 的元素变成位序为i,i+1,…,,n-1,新表长=原表长-1。

? 7. PriorElement(L,i) ? 8. NextElement(L,i) ? 9. ClearList(L) ? 10. ListEmpty(L) ? 11. PrintList(L) 根据以上基本操作,可以 实现一些复杂的操作。

假设利用线性表LA和LB分别表 示两个集合A和B,现要求构成一个 新的集合A=AUB。要求对线性表作如 下操作:扩大线性表LA,将存在于 LB中而不存在线性表LA中的数据元 素插入到线性表LA中去。

Step1 LB中依次取出每个元素。 Step2 依次在LA中进行查找。 Step3 若不存在,则插入之。

2.2 线性表的顺序存储结构及其运算 2.2.1 顺序表
?顺序存储结构
? 顺序存储结构:用一组地址连续(存储空间

紧邻)的存储单元依次存储数据元素的方法

?顺序表:采用顺序存储结构的线性表 ?顺序表的特点
? 数据元素的逻辑顺序与物理顺序是一致的。

? 由于线性表的各个数据元素的类型相同,所以 线性表便于顺序存储。 ? 对顺序表,根据表的第一个数据元素的地址可 以计算出其他数据元素的地址。 ? 假设每个数据元素占据的存储块包括c个存储 地址,则第一个存储地址通常称为该数据元素 的地址。 ? ai的地址用Loc(ai)表示,则第i+1个数据元素的 地址为 Loc(ai+1)=Loc(ai)+c l≤i≤n-1 ? 线性表的基地址:数据元素a1的地址 ?则 Loc(ai)=Loc(a1)+(i-1)c l≤i≤n

顺序存储结构示意图(顺序表):

首地址 起始地址 基地址

存储地址 内存状态 元素a1 b b+m
元素a2 ……..

b+(i-1)*m

元素ai

…….. b+(maxlen-1)*m
元素an 每个元素所占用 的存储单元个数

Loc(元素i)=b +(i-1)*m
线性表的顺序存储示意图

?在C语言中,一维数组在内存中占用的存 储空间是一组连续的存储区域,因此顺序 表可用一维数组表示。 #define MAXSIZE 100 TypeDef struct { DataType elem[MAXSIZE]; /*存放顺序表的容量*/ int Length; /*顺序表的实际长度*/ } SeqList; 静态数组-----存储空间的申请和释放有系统 自动完成

? 由于线性表所需最大存储空间不容易确定,通常 可以使用动态分配的一维数组(动态数组)来存储 线性表。 ? 动态数组存储空间的申请和释放由用户调用系统 函数实现 ? 定义如下结构来描述顺序表。 typedef struct { DataType *elem; /*线性表的基地址*/ int length; /*线性表当前的长度*/ int listsize; /*线性表当前分配的存储容量*/ }SeqList;
问:如何表示第i个结点呢?

2.2.2 顺序表基本运算的实现 1.初始化
顺序表的初始化,即构造一个空表,用 LIST_INIT_SIZE表示最初分配给线性表的顺序存储 空间。
Status InitSeqList(SeqList *L) { /*操作结果:构造一个空的顺序线性表*/
L->elem=(DataType*)malloc(LIST_INIT_SIZE*sizeof(DataType));

if(!L->elem) exit(OVERFLOW); /* 存储分配失败*/ L->length=0; /* 空表长度为0*/ L->listsize=LIST_INIT_SIZE; /*初始存储容量*/ return OK;
}

2.插入运算 ?线性表的插入是指在表的序号为i的元 素前面插入一个值为e的新元素,成为 新的第i个元素,原来的第i个元素成为 第i+1个元素。 ?插入后使原表长为n的表 (a1, a2, …, ai-1, ai, ai+1, …, an) 成为表长为n+1的表 (a1, a2, …, ai-1,e, ai, ai+1, …, an) ?i的合法取值范围1≤i≤n+1。

Status InsertSeqList(SeqList *L,int i,DataType e) { /*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)+1*/ /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/ DataType *q,*p; if(i<1||i>L->length+1) /* i值不合法*/ return ERROR; else if(L->length>=L->listsize) /*当前存储空间已满,增加分配*/ { printf("顺序表已满"); return ERROR;} else { q=L->elem+i-1; /* q为插入位置*/ for(p=L->elem+L->length-1; p>=q; --p) /* 插入位置及之后的元素右移*/ *(p+1)=*p; *q=e; /*插入e*/ ++L->length; /*表长增1*/ return OK; } } 时间复杂度为O(n)

3.删除运算
? 线性表的删除运算是指将表中第i个元素从线 性表中去掉 ? 删除后使原表长为n的线性表 (a1, a2, …, ai-1, ai, ai+1, …, an) ? 成为表长为 n-l的线性表 (a1, a2, …, ai-1, ai+1, …, an) ? i的取值范围1≤i≤n。

int DeleteSeqList(SeqList *L,int i) { /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ int j; if(i<1||i>L->length) /* i值不合法*/ { printf("不存在第i个元素!\n"); return 0; } else { for(j=i; j<L->length; j++) *( L->elem+j-1)=*(L->elem+j); /* 向上顺序移动元素*/ L->length--; /* 表长减1*/ return 1; } }

时间复杂度为O(n)

4.按值查找

?线性表中的按值查找:指在线性表中 查找与给定值x相等的数据元素。 ?在顺序表中实现该运算的最简单方法: 从第一个元素a1起依次与x比较,直到 找到一个与x相等的数据元素,则返回 它在顺序表中的位序,或者查遍整个 表都没有找到与x相等的元素,返回-1。

int SearchSeqList(SeqList *L, DataType x) { int j=l; while(j<=L->length&&*(L->elem+j-1)!=x) j++; if(j>L->length) return(-1); else return j; /*返回x所在位置的位序*/ }

时间复杂度为O(n)

顺序表主要具有以下优点: (1)顺序表随机存取表中元素。 (2)顺序表使用的方法简单,容易编程。 (3)无须增加额外的指针域空间。

顺序表有两个缺点: (1)插入、删除操作的效率非常低。 (2)需要预先分配足够大的存储空间,其 存储空间长度通常要被预设为线性表使用 过程中表长的最大值。

2.3 线性表的链式存储结构及其运算
?链式存储结构:
?采用链表实现存储,即表中数据元素是用一组任

意的存储单元存储, ?通过指针反映元素之间的关系,不要求逻辑上相 邻的元素在物理位置上也相邻。

?链式存储结构可以克服顺序表的缺点,但是 随机存取性能的消失。 ?链表:链式存储的线性表 ?单链表、循环链表和双向链表都是线性表的 链式存储结构。

2.3.1 单链表存储结构
?链表是用一组任意的存储单元来依次存储线性表中的各 个数据元素,这些存储单元可以是连续的,也可以是不连 续的。 ?数据元素之间的逻辑关系用指向直接后继的指针来表示。 ?用链式存储结构表示线性表的一个元素时至少要有两部 分信息:一是这个数据元素的值,二是这个数据元素的直 接后继的存储地址。这两部分信息一起组成了链表的一个 结点。
数据域,存放数据信息

data

next

指针域,指向下一个数据单元

? 链表通过每个结点的指针域将线性表的n个 结点按其逻辑次序链接成为一个整体。
? 单链表:每个结点只有一个指针域链的表 ? 用C语言描述单链表的结点结构: typedef struct node { /*单链表结点结构*/ DataType data ;/* DataType 可以是任何 相应的数据类型如int,char等*/ struct node *next; }LinkList;

头指针和头结点
头指针
头结点
线性表为空表时, 头指针 头结点的指针域为空

空指针

?

a1

a2

… ...

an ^

线性表的头指针:以线性表中第一个数据元素a1的存 储地址作为线性表的地址 为了使链表上的操作实现起来简单、清晰,通常在链 表的第一个结点之前增设一个类型相同的附加结点, 称之为头结点,以指向头结点的指针为链表的头指针。

在单链表上实现线性表的基本运算方法如下: 1. 建立单链表。
建表的方法通常有两种: ? 头插入法,也就是每输入一个不为零整数就建立 结点,把结点插入到当前链表的表头之前; ? 尾插入法,它是把新生成的结点插入到当前链表 的表尾结点之后。 两种方法的区别是生成链表的结点的次序和输 入的顺序不一样。

(1)头插入法建表 LinkList *AddHead1( ) { /*用头插法建立带头结点的单链表*/ int x; LinkList *head,*p; head=( LinkList*)malloc(sizeof(LinkList)); head->next=NULL; /*初始化一个空链表,head为头指针*/ scanf(“%d”,&x); /*x是和链表结点的数据域值具有相同类 型的变量*/ while(x!=flag) /*flag为结束输入的标志*/ { p=(LinkList *)malloc(sizeof(LinkList)); /*生成新的结点*/ p->data=x; /*输入元素值*/ p->next= head ->next; head ->next=p; /*插入到表头*/ scanf(“%d”,&x); /*读入下一个元素的值*/ } return head; }

(2)尾插入法建表

p->data=x; if(head==NULL) head=p; 带头结点的尾插入算法的 /*第一个结点的处理*/ 执行过程如图所示,其算 else 法如下: q->next=p;/*其他结点的处理*/ LinkList *AddHead( ) q=p; /*q指向新的尾结点*/ scanf(“%d”,&x); {/*尾插入法建立一个不带头结点的单 } 链表,返回表头指针*/ LinkList *head=NULL,*q=head,*p; if(q!=NULL) q->next=NULL; int x ; /*对于非空表,最后结点的指针域 scanf(“%d”,&x); 放空指针*/ while(x!=flag) return head; { p=(LinkList } *)malloc(sizeof(LinkList)); q
head

a1

a2

a3
p

图2.2 尾插入法建立单链表的插入过程

a4 ∧

2. 初始化单链表

算法如下:
void InitList(LinkList *&head) {/*初始化带头结点的链表头指针*/ head=(LinkList*)malloc(sizeof(LinkList)); if (!head) exit(OVERFLOW); /* 存储分配失败*/ head->next=NULL; }

3. 单链表中插入元素
已知p指向单链表中某结点,在p 所指结点的后面插入一个值为x的 新结点。操作可以分解为四步: ① s=( LinkList *)malloc(sizeof (LinkList)); /*申请一个新结点,用 s保存结点的地址*/ ② s->data=x; /*把值x写入s 所指的结点的数据域*/ ③ s->next=p->next; /*令s->next 指向p所指结点的下一个结点(或 NULL)*/ ④ p->next=s; /*令p->next指 向s所指结点*/ 该操作的时间复杂度为O(1)。

p p

a
a

b b

x
s

4. 单链表中删除元素

在单链表中删除第 i 个结点的基本操作为:找到线
性表中第i-1个结点,修改其指向后继的指针。

q = p->next; p->next = q->next;

e = q->data;

free(q);

p ai-1

q ai ai+1

5. 单链表按序号查找

? 顺序存取:单链表采用顺序存取,因此如果要 访问表中第i个结点必须从头结点出发开始搜索, 直到第i个结点为止。 ? 设单链表的长度为n,从头结点开始,顺着链 搜索; ? 指针p指向当前扫描到的结点,j为计数器; ? p的初值指向头结点,j的初值为0,当p扫描下 一个结点时,计数器j相应地加l; ? 当j==i时,p所指的结点就是要找的第i个结点。

5. 单链表按序号查找
LinkList *GetNode(LinkList *head,int i) { /*在带头结点的单链表中查找第i个结点, 找到返回该结点指针,否则返回NULL*/ LinkList *p=head; int j=0; while(p->next&&j<i) { j++; p=p->next; /*p右移一个结点*/ } if(j==i) return p; else return NULL; }

6. 单链表按值查找
?查找过程从头结点开始,依次将每个结点的值与x作比较 ?若查找第一个和给定值x相等的结点,则返回指向该结点的 指针,否则返回NULL。 LinkList *LocateNode(LinkList *head,int x) { /*在带头结点的单链表中查找值为x的结点,找到返回结点指 针,否则返回NULL*/ LinkList *p=head->next; while(p&&p->data!=x) p=p->next; return p; }

7. 求单链表长度
?依次访问链表中的每个结点,每访问一个结点,表长变量len 自加1,直到访问完所有结点。 int ListLen(LinkList *head) { /*在带头结点的单链表求表的长度*/ int len=0; LinkList *p=head ; while(p->next!=NULL) { len++; p=p->next; } return len; } 算法时间复杂度为O(n)。

2.3.2 循环单链表存储结构
? 单链表的尾结点的指针域是NULL ? 循环单链表(circular singly linked list):将链表的头指针 放置在尾部结点的指针域,则使得链表首尾相连

a1

a2

… ...

an

? 判别循环链表中最后一个结点的条件:后继是否为头结点; ?判断单链表中最后一个结点的条件:后继是否为空。 空循环单链表:将链表头指针放 在头结点的指针域

2.3.2 循环单链表存储结构
? 在单链表中,从某一个结点出发只能访问该结点之后的各个 结点 ? 在循环单链表中,从任意结点出发可以访问链表中的任意节 点 ? 思考题: 1) 设两个(不)带头结点的单循环链表,头指针分别为head1 和head2,编写算法将循环单链表head2链接到head1之后, 要求链接后仍是循环单链表,头指针为head1. 2) 设两个(不)带头结点的单循环链表,尾指针分别为rear1和 rear2,编写算法将循环单链表rear2链接到rear1之后,要求 链接后仍是循环单链表,尾指针为rear2.

2.3.3 双向链表存储结构 2.3.3.1 双向链表
?双向链表(doubly linked list):每个结点都有指 向后继和前驱的两个指针域的链表 ?优点:找后继和前驱结点的时间复杂度均是O(1) ?在单链表中,找某结点的后继结点算法时间复杂度 是O(1),找其前驱结点的算法时间复杂度是O(n)

head head

双向链表存储结构用C语言数据类型描述: typedef struct node { ListDT data; struct node *prior,*next; }DNode,*DLink;

2.3.3.2 线性表基本运算在双向链表上的实现
1. 双向链表的后插入元素操作

ptr

ai-1

ai

d
q->next = ptr->next; ptr->next = q; q->next->prior = q; q->prior = ptr; 次序不唯一

q

2. 双向链表的删除元素操作

ai-1
ptr

ai

ai+1

ptr->next = ptr->next->next; ptr->next->prior = ptr;

2.3.3.3 循环双向链表

?循环双向链表(circular doubly linked list):把头结点 当作尾结点的后继结点,把尾结点当作头结点的前驱结 点的链表; ?空循环双向链表:头结点的前驱指针和后继指针都是头 结点本身; ?循环双向链表兼具循环单链表和双向链表的优点: ?在循环双向链表中的ptr所指结点之后插入新结点时无 须判断原先链表中的ptr->next是否为空,因为ptr->next 至少也是头结点的指针; ?在循环双向链表中删除ptr所指结点之后的结点q时也无 须判断q->next是否为空(q指向ptr的后继结点,q不能 是头结点)。
head

head

2.4 顺序表和链表的比较
顺序表主要具有以下优点: (1)顺序表可以按序号随机访问表中元素。 (2)顺序表使用的方法比较简单,容易编程。 (3)无须为表示表中元素之间的逻辑关系而增加额外的 指针域空间。 但顺序表也有两个缺点: (1)在顺序表中做插入或删除元素的操作时,可能会发 生大量的数据移动,两个操作的效率非常低。 (2)需要预先分配足够大的存储空间,其存储空间长度 通常要被预设为线性表使用过程中表长的最大值。

链表的优缺点恰好与顺序表相反,主要优点是:
(1)在链表中做插入或删除结点的操作(对于结点中只 有后继指针的链表是指“后插入或删除”)时,不 会发生数据移动,操作效率比较高。 (2)链表的存储空间占用量是动态的,无须事先分配备 用空间。

主要缺点是:
(1)链表不具备随机访问表中元素的特性。 (2)链表的操作要频繁使用指针,编程难度较大。 (3)链表需要为表示表中元素之间的逻辑关系而增加额 外的指针域空间。

2.5 线性表的应用
?一元多项式按升幂 Pn(x)=P0+P1x+P2x2+…+Pnxn 由n+1个系数惟一确定。 ?用一个线性表P表示 P=(P0,P1,P2,…,Pn) 每一项的指数i隐含在其系数Pi的序号里。 ? 若多项式的次数很高且变化很大,浪费存储空间。 A(x)=1+2x100 +3x1000+4x10000 ?用系数和指数的组合表示多项式的一个项,则多项式 A(x)可表示成如下线性表的形式。 A=((1,0),(2,100),(3,1000),(4,10000))

?线性表的存储结构确定:要视其做何运算以及是 否有利于该运算的实现而定; ?只对多项式求值,由于不会改变多项式的系数和 指数,用顺序表; ?对多项式作求和运算,则插入、删除操作不可避 免,而且线性表的长度变化比较大,故宜用链表 结构。 ?多项式A(x)用带头结点的单链表表示:

head

1 0

2 100

3 1000

4 10000 ∧

多项式的链式存储结构描述: typedef struct pnode /*多项式结点结构*/ { float coef; /*表示多项式的系数*/ int exp; /*表示多项式的指数*/ stuct pnode *next; }Poly;

?对两个多项式A和B相加的实现:设指针p和q分别指向 多项式A和多项式B中当前进行比较的某个结点,比较两 个结点中的exp指数域,有下列三种情况: (1)p->exp<q->exp,*p应为多项式的一项; (2)p->exp==q->exp,则将两个结点中的系数相加, 若相加为零,则释放指针p和q所指结点,否则修改*p结 点的coef系数域,并释放指针q所指结点; (3)p->exp>q->exp,*q应为多项式的一项,把*q插 入到*p之前。 pa 1 0 2 100 3 1000 4 10000 ∧
pb 6 1 -2 100 3 300 5 10000 ∧

1

0

3 1000

9

10000 ∧

6

1

3

300

Poly PolyAdd(Poly *pa,Poly *pb) {/*求两多项式之和,多项式用带 头结点的单链表表示,pa, pb 为头指针*/ Poly *p,*q,*r,*s; int x; p=pa->next; r=pa; /*r为p的前驱指针*/ q=pb->next; free(pb); while(p!=NULL&&q!=NULL) if(p->exp<q->exp) {/*指针顺链向后移动*/ r=p; p=p->next; } else if(p->exp==q->exp) { x=p->coef+q->coef; if(x==0) {r->next=p->next;

free(p); /*释放p所指结点*/ } else { p->coef=x; r=p; } p=r->next; s=q->next; /*s为辅助指针, 指向q的后继结点*/ free(q); /*释放q所指结点*/ q=s; } else{/*q所指结点插入到r,p所 指结点之间*/ s=q->next; r->next=q; q->next=p; r=q; q=s; } if(q!=NULL) r->next=q; /*将pb表的剩余结点插人到 pa表尾*/ return(pa); /*返回新多项式 表头指针,与pa一致*/



束!