计算机软件基础（MOOC版）课件 第3章 线性表及其存储结构

第三章

线性表BasicsofComputer

Software12345线性表的基本概念线性表的顺序存储线性表的链式存储堆队栈列线

性

表

的

基

本

概

念

与

运

算PART 01abcdea,b,c,d,e是数据元素，表长为5线性表的概念线性表的运算线性表的定义abcde线性表的概念线性表的运算线性表的特点常见线性表有：队列、堆栈、字符串、数组线性表的运算线性表的概念

线性表的运算线性表的运算置空表取前驱求表长取后继插入结点删除结点按值查找提取元素排序运算回忆：数据的物理结构线性表的概念

线性表的运算回顾链接存储表示增加一个或多个指针，用于存放和该数据元素

有关的另一个数据元素的地址，可以不占用连续地址空间。散列存储表示是一种在数据元素的关键码与存储位置之间建立确定对应关系的查找

技术。顺序存储表示将逻辑上相邻的数据元素存放在内存中的相邻位置中索引存储表示指除建立存储结点信息外，还建立附加的索引表来标识结点的地址线

性

表

的

顺

序

存

储

及

其

运

算PART 02定 义：将线性表中的元素相继存放在一个

连续的存储空间中存储结构：顺序存储（如：动态数组）特 点：逻辑上相邻的元素，物理次序也相邻存取方式：随机存取顺序表的概念顺序表的运算顺序表的应用顺序表的定义012345678910371354645652175888092LOC(a1)=LOC(a1)LOC(a2)=

LOC(a1)+(2-1)*l：LOC(ai)=

LOC(a1)+(i-1)*la1a2…a

i………ana a+l … a+(i-1)*l

…… …a+(n-1)*lidle顺序表的概念顺序表的运算顺序表的应用1 2 …顺序表的存储方式i … … … na1a2…a

i………ana a+l … a+(i-1)*l…

… … a+(n-1)*l idle例如：设顺序表的首地址为1000，数据类型是整型数，则每个元素的长度是2个字节，则有：LOC(a5)=LOC(a1)+(5-1)*

2=1000+4*2=1008顺序表的概念顺序表的运算顺序表的应用1 2 …顺序表的存储方式i … … … nabcd……4datalength#defineListSize

100

//最大允许长度typedefchar

ListData;typedefstruct

{

ListData

data[listsize];

//存储空间基址

int

length; //当前元素个数

}

SeqList; 顺序表的类型名

SeqList

L；L是变量名顺序表的概念顺序表的运算 顺序表的应用顺序表的类型定义012345678910371354645652175data8length设有定义：SeqList

L；L表的最大长度为11表的当前长度为8L.data[6]

//访问第7个，即6号元素

21L.length

//表长L.data[L.length]

//顺序表的下一个空位置，即8号位置顺序表的概念顺序表的运算顺序表的应用顺序表的引用初始化

voidInitList(SeqList

L){

L.length=

0;

}8012345678910371354645652175datalengthL0顺序表的概念

顺序表的运算顺序表的应用顺序表的初始化顺序表的概念

顺序表的运算顺序表的应用顺序表的查找

intFind(SeqListL,ListDatax

)

{int

i=0;

while(i<L.length&&

L.data[i]!=x)

i++;

if(i<L.length)return

i;

elsereturn

-1;

}i

1-1

0顺序表的概念

顺序表的运算顺序表的应用按值查找算法顺序表基本运算——求表的长度

intLength(SeqListL

)

{

return

L.length;

}顺序表的概念

顺序表的运算顺序表的应用求表长算法012345678910371354645652175data8lengthL在顺序表L中提取第i个元素的值

ListDataGetData(SeqList&L,inti

)

{if

(i>=1&&i<=L.length)

return

L.data[i-1];

else

{

printf

(“参数

i不合理！\n”);

returnnull}

}

顺序表的概念

顺序表的运算顺序表的应用取元素算法（提取函数）012345678910371354645652175data8lengthL顺序表的概念

顺序表的运算顺序表的应用取元素的前驱操作listdataNext(SeqList&L,ListData

x)

{inti=

Find(L,x);

if(i>=0&&i<L.length-1

)

returnL.data[i+1];else

return

null;

}顺序表的概念

顺序表的运算顺序表的应用取元素的后继操作插入操作(i号位置插入x)for

( j=L.length;j>i;j--

)L.data[j]=L.data[j-1];L.data[i]=x;L.length++;return

1;}else {§intInsert(SeqList&L,ListDatax,inti

)if(i<0||i>L.length||L.length==

ListSize)return0; //插入失败//移动数据//插入成功顺序表的概念

顺序表的运算顺序表的应用插入操作插入时，数据平均移动次数AMN在各表项插入概率相等时，有：Pi是在i号位置上插入元素的概率,我们假设是等概率情况Ci是在i号位置上插入元素时所需要的移动次数插入操作(i号位置插入x)顺序表的概念

顺序表的运算顺序表的应用插入操作的算法分析int Delete(SeqList&L,ListDatax

){inti=Find(L,

x);if(i>=0

)//在表中查找

x//在表中找到

x{for(intj=i;j<L.length;j++)L.data[j]=L.data[j+1];L.length--

;//成功删除return1;}return

0;

//表中没有

x}顺序表的概念

顺序表的运算删除指定元素x顺序表的应用删除算法删除时，平均移动次数AMN在各位置删除概率相等时，有：Pi是在删除i号位置上的元素的概率,我们假设是等概率情况Ci是在删除i号位置上的元素时所需要的移动次数顺序表的概念

顺序表的运算顺序表的应用删除算法算法分析顺序存储结构的优缺点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑优点 缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充设：

集合A={1，3，4，5，7，10}集合B={2，4，7，9}则：A=A∪B={1，2，3，4，5，7，9，10}={1，3，4，5，7，10，2，9}={2，4，7，9，1，3，5，10}看：A=A∪B={1，3，4，5，7，10，2，9}=A+(B-A)结论：A和B的并集中，A中的所有元素属于他们的并集B中除去属于A的剩余元素同样属于他们的并集因此：只要以A为基础，从B中依次取出所有元素，在A中查询，如果没找到就将该元素插入到A中顺序表的概念顺序表的运算

顺序表的应用集合的“并”运算//在B中取一元素//在A中查找它//未找到，则插入到A尾部{intx=GetData(B,i

);intk=Find(A,

x);if(k==-1

)Insert(A,x,

A.length)}}算法思路：以A为基础，从B中依次取出所有元素，在A中查询，如果没找到就将该元素插入到A中voidUnion(SeqList&A,SeqList&B

){ for(inti=0;i<B.lenggth;i++

)顺序表的概念顺序表的运算

顺序表的应用

集合的“并”运算设：

集合A={1，3，4，5，7，10}集合B={2，4，7，9}则：A=A∩B={4，7}因此：只要以A为基础，从A中依次取出所有元素，在B中查询，如果没找到就将该元素从A中删除顺序表的概念顺序表的运算

顺序表的应用集合的“交”运算voidIntersection(SeqList&A,SeqList&B

){inti=

0;while(i<A.length

){//在A中取一元素//在B中查找它//未找到在A中删除它intx=GetData(A,i

);intk=Find(B,x

);if(k==-1

)Delete(A,

x);elsei++;}}顺序表的概念顺序表的运算

顺序表的应用集合的“交”运算（一）voidIntersection(SeqList&A,SeqList&B

){inti=A.length-1;while(i>=0A.length

){//在A中取一元素//在B中查找它//未找到在A中删除它intx=GetData(A,i

);intk=Find(B,x

);if(k==-1

)Delete(A,

x);i++;}}大家可以分析一下交集的方法1和方法2有什么不同？为什么不用for循环？顺序表的概念顺序表的运算

顺序表的应用集合的“交”运算（二）线

性

表

的

链

式

存

储

及

其

运

算PART 03单链表双向链表循环链表静态链表链表：线性表的链式存储表示1定义：用一组地址任意的存储单元存放线性表中的数据元素。链表：线性表的链式存储表示1每个元素由结点(Node)构成，它包括两个域:数据域（Data）和

指针域（next）存储结构：链式存储结构特 点：存储单元可以不连续。存取方式：按顺序存取。Nodedata

next线性链表的结点结构1typedefintListData;

//定义数据类型typedefstructnode

//链表结点

{

ListData

data; //结点数据域

structnode*next;

//结点链域}

ListNode;Typedef

ListNode

*

LinkList;

//链表头指针LinkListhead，p,q;

//链表头指针Nodedata nextListNode是类型名线性链表的类型定义1为使运算简单，可以在单链表的第一个结点之前另加一个结点，称之为头结点。后面的链表操作均是带头结点的单链表….

FBAhead头结点 第一结点设置表头结点的目的是统一空链表与非空链表的操作，简化链表操作的实现。带头结点的单链表1

952headPp->data;p->next;p->next->data;q->next=nil;p=p->next;q//得到元素值2//2和5之间的指针//得到元素值5p->next->next->data; //得到元素9//最后一个结点的指针分量置空//指针后移一个节点单链表的引用1情况1headabc ^单链表的插入操作情况1：在第一个结点前插入情况2：中间插入情况3：插入到链表尾部情况3情况2newnodea bc ^Newnode->next=p->next;p->next=newnode;Phead第一种情况：在第一个结点前插入单链表的插入操作第二种情况：在链表中间插入单链表的插入操作第三种情况：在链表尾部插入单链表的插入操作1.移动指针P向后移动，指向下一个结点：

p=p->next;2.用指针动态申请一个结构体空间：malloc函数的格式：(类型

*)

malloc(size）；q=(ListNode*)malloc(sizeof(ListNode));q->data=x;3.在移动指针P之后，插入新结点的操作：q->next=p->next;p->next=q;准备知识(在head链表第

i

个结点处插入新元素

x)intInsert(LinkList*head,inti,int

x)

{

p=head;

k=0;

while(p!=nil&&

k<i-1)

{

p=p->next;

k++;

}

//找第

i-1个结点

if(p==nil)

//终止插入

{

printf(“无效的插入位置!\n”);

return0;

}

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//创建新结点

q->next=p->next;

//完成插入

p->next=q;

Return1;}

单链表插入算法一//完成插入

q->next=p->next;

p->next=q;

}

插入算法2(在有序链表head中插入元素x)Insertsort(LinkList*head,int

x)

{

p=head;

while

(p

-

>

n

e

x

t

！

=

n

i

l

&

&

p

-

>

n

e

x

t

-

>

d

a

t

a

<

=

x

)

p=p->next;

//为x结点定位

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//创建新结点单链表插入算法二单链表的删除操作（删除P之后的结点）单链表的删除操作intDelete(head,x){p=head;

while(p->next!=nil&&

p->next->data!=x)

p=p->next;

if(p->next==nil

)

{printf(“链表中没有要删除的元素”)；

return0；}

q=p->next;

p->next=q->next;

free(q);

Return

1}删除元素值为x的结点单链表的删除算法前插法建立单链表建立空链表从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端直到读入结束符为止。设输入顺序为：8、5、2LinkListcreateListF

()

{

head=(LinkList)

malloc(sizeof(ListNode));

head->next=nil;

//建立空链表

scanf(“%d”,&x);

while

(x!=0)

{

q=(listNode*)malloc

(sizeof(ListNode));

q->data=x;

//建立新结点

q->next=head->next;

//插入到头节点之后

head->next=q;

scanf(“%d”,&x);

}

returnhead;}前插法建立单链表算法每次将新结点加在链表的表尾；尾指针rear

,总是指向表中最后一个结点，新结点插在它的后面；后插法建立单链表LinkListcreateListR

(){head=(LinkList)

malloc(sizeof(ListNode));

head->next=nil;

//建立空链表

rear=head;

scanf(“%d”,&x);

while

(x!=0)

{

q=(listNode*)malloc

(sizeof(ListNode));

q->data=x;

//建立新结点//插入到头节点之后

rear->next=q;

rear=q;

scanf(“%d”,&x);

}

rear->next=

nil;

returnhead;}后插法建立单链表算法单链表的输出output(head);//让移动指针指向第一个结点{p=head->next；while

(p!=nil){printf(“%5d”,p->data);p=p->next; //指针后移}}intLength(LinkList

head)

{

p=head->next;count=0;

while(p!=NULL

)

{

count++;

p=p->next;

}

return

count;}计算单链表长度单链表的清空删去除结点外的所有结点voidmakeEmpty(LinkListhead

)

{

ListNode

*q;

while

(head->next!=nil)

{

q=head->next;

head->next=q->next;

free(q);

//释放

}

}ListNode*Find(LinkListhead,ListDatavalue

)

{

//在链表中从头搜索其数据值为value的结点p=head->next; //指针

p

指示第一个结点while(p!=nil&&

p->data!=value)

p=p->next;

return

p;

}问题：如果在有序链表中进行查找，该如何修改，以提高效率？单链表的按值查找ListNode*Locate(LinkListhead,int

i){//返回表中第i个元素的地址

if(i<0)return

nil;

p=head;

k=0;

while(p!=nil&&k<i

)

{p=p->link;

k++;

} //找第

i

个结点

if

(k==i)

return

p;

//返回第

i

个结点地址

elsereturn

nil;

}单链表的按序号查找循环链表特点:最后一个结点的

next指针不为nil，而是指向头结点。只要已知表中某一结点的地址，就可搜寻所有结点的地址存储结构:链式存储结构an-1heada1a0head(空表)(非空表)带表头结点的循环链表循环链表的插入、删除、查询等操作和相应的单链表的操作基本相同。区别：在判断尾结点时的条件不同。单

链

表：p->next==nil循环链表：p->next==head循环链表q->next=p->next;p->next=q;q=p->next;p->next=q->next;free(q);循环链表的插入循环链表的删除双向链表结点结构：指向直接前驱指向直接后继非空表空表headhead双向循环链表typedefintListData;typedefstruct

dnode

{

ListNode

data;

structdnode*prior,

*next;

}

DblNode;typedefDblNode*

DblList;

双向循环链表的定义voidCreateDblList(DblList

head)

{

head=(DblNode*)malloc(sizeof(

DblNode));

head->prior=head;

head->next=head;

//表头结点的链指针指向自己}head建立空的双向循环链表intLength(DblList

head)

{

DblNode*p=

head->next;

intcount=

0;

while(p!=

head)

{p=p->next;count++;

}

return

count;}

head31 482515计算双向循环链表长度q->prior=

p;q->next=

p->next;p->next=

q;q->next->prior=

q;在结点

*p

后插入q结点head314815pheadp31482515q25q双向循环链表的插入（非空表）在结点

*p

后插入q结点q->prior=

p;q->next =

p->next;p->next =

q;q->next->prior=

q;qfirst25firstp p同样的4条指令对空表来说同样适用双向循环链表的插入（空表）Insertsort(DblListhead,int

x)

{

p=head;

while(p->next=nil&&

p->next->data<=x)

p=p->next;

//为x结点定位

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//创建新结点

q->prior=

p;

q->next=p->next;

p->next=q;

p->next->prior

=

q;

//完成插入}双向循环链表的插入算法head314815p例如：删除48：p->next->prior=p->prior;p->prior->next=p->next;free(p);双向循环链表的删除操作first31p例如：删除31p->next->prior=p->prior;p->prior->next=

p->next;双向循环链表的删除操作删除最后一个结点（1）存储分配的方式u

顺序表的存储空间是静态分配的u

链表的存储空间是动态分配的（2）存储密度u

顺序表的存储密度

=

1u

链表的存储密度

<

1注：存储密度=

结点数据本身所占的存储量/结点结构所占的存储总量顺序表与链表的比较基于空间的比较n 存取方式u

顺序表可以随机存取，也可以顺序存取u

链表是顺序存取的n 插入/删除时移动元素个数u

顺序表平均需要移动近一半元素u

链表不需要移动元素，只需要修改指针顺序表与链表的比较基于时间的比较有序链表的归并有序链表的归并LinkList

meger(ha,hb)

//将ha、hb两个有序链表归并为hc有序链表{LinkList

*pa,*pb,*pc;

pa=ha->next;

pb=hb->next;

pc=ha;

while

(pa!=nil&&pb!=nil)

if

(pa->data<pb->data)

{pc->next=pa;pc=pa;

pa=pa->next;}

else

{pc->next=pb;pc=pb;

pb=pb->next;}

if(pb！=nil)

pc->next=pb;

else

pc->next=pa;

free(hb);

return

ha;

}在多项式的链表表示中每个结点的数据域有2个，分别是coef（系数）和exp（指数）。Coef exp nexttypedefstruct

pnode{

int

coef，exp;

structpnode*

next;

}PolyNode;typedefPolyNode

*Polylist多项式的相加1 0-10

62 8714

^418

^15

14418

^AH=

1-10x6+2x8+7x14BH=

-x4+10x6-3x10+8x14+4x18AHBHCH-1

4 10

6 -3

10 8

14（a）两个相加的多项式1 0 -1

4 2 8 -310（b）两个多项式相加的结果多项式的相加polylistPolynomialAdd(Polylist

ah,bh){

Term*pa,*pb,*pc,

*p;

pa=ah->next;

pb=bh->next;

pc=ah;

deletebh;多项式的相加多项式的相加while(pa!=nil&&pb!=nil

)

if(pa→exp==pb→exp)

//幂相同

{tcoef=pa→coef+pb→coef;

if

(tcoef==0

//系数相加为0

{p=pa;pa=pa->next;

free(p);

p=pb;pb=pb->next;

free(p);

}

else

//系数相加不为0

{pa→coef=tcoef;

pc→next=pa;

pc=pa;

pa=pa→next;

p=pb;pb=pb→next;

free(p);

}

}多项式的相加

elseif

(pa→exp<pb→exp)

{

pc→next=pa;

pc=pa;

pa=pa→next;

}

elseif

(pa→exp>pb→exp)

{

pc→next=pb;

pc=pb;

pb=pb→next;

}if(pb==nil)

pc→next=pa;

else

pc→next=pb;

}

堆栈PART 04定义:是限定仅在表尾进行插入或删除操作的线性表。栈顶(top):允许插入和删除的一端，则另一端称为栈底(bottom)特点：后进先出

(LIFO)堆栈及其应用实现程序调用，子程序嵌套调用和递归调用对于“中断”技术，堆栈更是不可缺少的，保存“断点”和“现场”堆栈在计算机中的作用020304050601堆栈的主要操作StackEmpty(S)判栈空StackFull(S)

判栈满POP（S）

出栈GetTop（S）取栈顶元素顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素指针top指向栈顶元素在顺序栈中的下一个位置base为栈底指针，指向栈底的位置。链栈：栈的链式存储结构，利用链表来存储堆栈的数据元素。堆栈的表示和实现空栈topbottom

aa

进栈top

bottomb

进栈

b

abottomtopa

b

c e

d bottomtope

d

c

b

af

进栈溢出bottomtopbottomtop

d

c

b

ae

出栈c,d,e分别进栈栈满栈满顺序栈的常见操作}

SeqStack；……datatoplength改为top#defineSTACK_SIZE100；typedef

struct

//顺序栈定义{int

data[STACK_SIZE];

inttop;

//栈顶指针length改为top顺序栈的类型表示§堆栈的初始化voidInitStack(SeqStack

*S)

{ S.top=0;

}

n 顺序表的初始化

voidInitList(SeqList

L)

{L.length=0;

}顺序栈的基本运算判栈空intStackEmpty(SeqStack

*S)

{

if(S.top==0

)

return

1

//判栈空,空则返回1

else

return

0;

//否则返回0}判顺序表空intListEmpty(SeqList

L)

{

if(L.length==0

)

return

1

else

return

0;

}顺序栈基本运算——判栈空intStackFull(SeqStack

*S)

{if(S.Top==STACK_SIZE

)

return

1

//判栈满,满则返回1else

return

0;

//否则返回0}顺序栈基本运算——判栈满intPush(SeqStackS,StackData

x)

{if(StackFull(S)

)return0;//失败else：a4a3a2a1a0top{

(S.data[S.top])=x;

(S.top)++;Return

1}}Insert(SeqListS,ListDatax,int

S.length)

顺序栈的入栈算法intpop(SeqStackS

){if

(StackEmpty(S))

returnerror;else

{(S.top)--;

return(S.data[s.top]);

}}：a5a4a3a2a1a0topBase顺序栈的出栈intGettop(SeqStack

S)

{if(StackEmpty(S)

)

returnerror;else

return

(S.data[s.top-1]);}GetData

(

SeqList

S,

int

S.length-1

);//顺序表的取最后一个元素取栈顶元素定义：栈的链式存储结构，利用链表来存储堆栈的数据元素。a3a2a1

^栈底top栈顶…...ai…topaia3a2a1 ^栈的链式存储——链栈typedefint

StackData;typedefstruct

Snode{ListData data;struct

Snode *

next;}

StackNode;Typedef

StackNode *LinkStack;

//链表头指针LinkStack top，p,q; //链表头指针Snodedatanext//定义数据类型//链表结点//结点数据域//结点链域StackNode是类型名…topaia3a2a3 ^链栈的类型表示voidInitStack(LinkStack

S)

{

top=nil

;

}

链栈的初始化intStackEmpty(SeqStack

top){if(top==nil

)return

1

//判栈空,空则返回1elsereturn

0;

//否则返回0}判栈满—只要内存最够大，就不需要链栈判栈空int

push(LinkStack top,int

e){q=(Lstack)malloc(sizeof(lnode));q->data=e;q->next=top;top=q;return1；}qtopbcd ^ae链栈的入栈intpop(LinkStack

top){if(top==nil)return

null;else{x=top->data;q=top;top=top->next;free(q);return

x；}}tope^cdq链栈的出栈设入栈顺序为1，2，3，4问：将4个元素全部出栈的情况下，可以得到哪些出栈顺序？即：从1到4的共24种排列组合中，哪些组合是可以得到的？提示：并不要求4个元素全部入栈之后才能出栈趣味练习队 列PART 05定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。§在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为队头(front)。§特点：先进先出

(FIFO)出队队尾a1 , a2 , a3 , a4 , …………an-1

, an队 列 示意

图队头先进

先出FIFO入队队列队列的主要运算队列的存储结构顺序存储顺序队列循环队列链式存储结构和栈一样，用顺序结构表示队列是一种简单的方法，通常用一维数组实现。用MaxSize表示队列允许的最大容量，在队的两端设置两个整型变量作指针，front为头指针，rear为尾指针。data……frontrear顺序队列的存储结构#defineMaxSize 100；typedefintQueueDatatypedef

struct{ QueueDatadata[MaxSize];int front,rear;}Queue；data……frontrear顺序队列的类型表示rearfront6543210e7e6e5e4e3e2e1空队列：队空的条件是front=rear=-1e1、e2、e3、e4分别入队e1、e2出队e5、e