计算机软件基础：11第四章数据结构-线性表

《计算机软件基础》多媒体教程

第十一讲

第四章数据结构

4.1基本概念XT

4.1.0数据结构的研究内容

※数据(对象)的性质万丽I信息学院*信息学院

什么样的数据/集合

时间微电子学系

※数据联系「性别I|变量

相互之间是什么关系

信息、姓名

※数据表示微电子学系亚

如何在计算机中存储Q属性

学生必修课宿舍

※数据处理

如何对数据进行操作选修课宿舍

设置

abc

地点软件基础

必修课撷机原理

学号intnumber;

选修课

而一►charname[3]；软件开发

short"room;修改.llxxxx

4.1.1数据结构的定义

※数据结构的定义

设B是一个二元组，记为B=(K,R)。K是数据的有限集合，R是K中各数据的有限关系

集合，则称B是数据结构。

其中，K的成员ki,k2,…，又称为数据元素(或数据结点，结点)，记为K={k>k2.........kn}o

R的成员小⑵…，称为关系，记为R={ri/2,…，rm|ri=(ks,kt),ks,kyK},表示在结点

ks,kt之间存在关系口。

【例5-1.1］数据结构示例。

0~9可组成集合K,在集合K={0~9}上可存在GT(大于)和LT(小于网种关系。

定义:B=(K,R),K={0,1.......9},R={GT,LT},

其中，GT={(1,0),(2,0),(2,1),...},LT={(0,1),(0,2),(1,2),...),

则称B=(K,R)是一种数据结构。

4.1.2结点定义

设B=(K,R)是一种数据结构，可有以下定义：

※结点的存储单元

结点k的存储单元由结点地址ak,数据场Bk和指针场pk组成，记为：

k={ak,8k,pk}

※结点的数据场

若结点k的数据场3k有m个分量，即每个结点都有m个不同的数据，则记为:

8k={8ik|i=1,m}={§ik,82k,8mk}

※结点的指针场

若结点k的指针场pk有h个分量，每个指针场分量都对应于R的一个关系00=1，…，h),

则记为：

pk={pjk|j=1,h}={pik,p2k.......phk}

结点k的存储单元结点k的数据场结点k的指针场

假定对应于一种关系门的指针场pjk,需要指向t(j)个结点，即：

Pjk={pjkk|k=1，…,t（j）}={pjik，.…pjt（j）k）,

则pk又可以进一步记为

pk={puk,...,pit（i）k,p2ik,...,p2t（2）k.......Phik,...,Pht（h）k}

从而

k={ak,81k,82k,...,8mk,pnk,...,pit（i）k,paik,...,p2t（2）k......Phik,...,Pht（h）k}

RkRk

或

（PNULL

。空置的指针场

用q＞或NULL表示空置的指针场pik,记为pik=q＞或pik=NULL。

※结点性质

O前件和后件密汨隆园

设r=(k,k'),其中reR,(k,k'GK),则称k是k'关于出U文詈文不可省略

关系r的前件，k，是k关于关系r的后件。图中用箭头从k多个关系®关系标记

指向k'。

当R中只有一种关系r时，可以省略关系的名称，并个亲三G

直接称k是k'的前件，k'是k的后件。।大东尘厂飞人关系标记

。孤立结点

若在K中对于关系r而言，既无前件又无后件的k称为孤立结点。

对于非孤立的结点，定义：

。始结点

o始结点

若在K中不存在任何k',使得成立(k',k)en

则称k为r的始结点。o终结点

。终结点

Q内结点

若在K中不存在任何k',使得成立(k,k')en

则称k为r的终结点。o孤立结点

。内结点

既非始结点又非终结点的称为r的内结点。

【例4-1.2】结点性质示例

定义B1=(K,R),其中

K={1,2,3,4,5,6,7},

R={N,T},

N={(1,2),(1,4),(2,3),(2,6),

(3,7),(6,3),(7,3)},

T={(2,6),(4,5),(5,2),(6,7)}。

结关系N关系T

点前件后件前件后件

12,4

213,656

32,6,77

415

542

62327

7336

关系N关系T

始结点14

终结点47

内结点2,3,6,72,5,6

孤立结点51,3

4.1.3数据结构的存储方式

假定r是B=(K,R)中的一种关系，实现r的存储方式有以下两种：

※顺序存储

若对于任何一对结点(k,k')都成立ak'=ak+s(s为存储单元的大小，固定长度)，则称r

是用顺序方式存储的，简称顺序存储。

※链接存储

若对于任何一对结点(k,k片遮立ak七pk,则称r是用链接方式存储的，简称链接存储。

顺序存储aki=FFOO〔r荐w福ak[=FF60pki=FF10

s=2ak2=FF02

ak2=FF10pk2=FF00

ak3=FF04

ak3=FF00pk3=FF40

例如，在N中各结点的最多后件数大于1,则只能用链接存储。

在T中，各结点的最多后件数不超过1,则既可用顺序存储，也可用链接存储。

【例4-1.3］存储单元的图形表示。

在数据结构B1=(K,R)中，每个结点k的数据场只有一个分量3k。

由于所有结点关于关系N的后件最多有2个，关于关系T的后件均为1个，则k的存

储单元为：

k={ak,8k,(pNik,pN2k),PT}«

现以链接方式存储关系N,以顺序方式存储关系T,B1=(K,R)的存储单元如图所示(虚

设存储单位的地址)。

4.1.4数据结构的分类

(1)纯集合：结点间相互无关系，全部为孤立结点。

(2)线性：只有一个始结点和一个终结点，各结点的前件和后件数至多一个，无孤立结

点。

(3)树状：只有一个始结点，各结点的前件数至多一个，无孤立结点。

(4)网状：始结点和终结点的数目任意，各结点的前件和后件数任意，无孤立结点。

4.1.5基本操作

数据结构的基本操作包括查找，增添，删除和排序。

(1)查找：根据地址、序号或某个数据场的值来寻找某个结点。

例如，查找结点值为key=6的结点，即查找片==6,得i=5。

(2)增添：根据某种关系，在保持数据结构的特点不变情况下，增加结点或结点组。

例如，在已有的数据结构中增添两个结点：

(3)删除：在保持数据结构的特点不变情况下，删去某些结点或结点组。

例如，在已有的数据结构中删除两个结点：

(4)排序：按某种方式使各结点有序排列。

例如，使数据结构中的结点按照从小到大排序:

2排序

4.1.6数据结构的学习内容

※数据类型：

线性，树状，网状。

※存储方式：

顺序存储，链接存储。

※基本操作：

查找，增添，删除和排序。

※算法实现：

用C语言编程。

《计算机软件基础》多媒体教程

第四章数据结构

4.2线性表

线性表(list),又称并列表，线性并列表，或者有序表。

4.2.1基本问题

※线性表的定义

设B=(K,R),若K中有n个结点K={k°，…，kn-i},R中只有一种关系N,即

N={(ki,ki+1)|ki,ki+ieK,0<i<n-1},

则称B为线性表。

※推论

有且仅有一个始结点和一个终结点，其余为内结点

除终结点外，每个结点有且仅有一个后件。

除始结点外，每个结点有且仅有一个前件。

※课程约定

。如果没有特别说明，数据结构中的结点k只有一个数据场分量。

。假定可以调用一个已设计的出错函数error。，用于出错处理。

※线性表的顺序存储

采用数组实现线性表的顺序存储。数组

。存储单元

ki={aki,8kj)

可省略指针场，其中，

akj=i

Ski=a[i],

pkj=akj+i=aki+1=i+1

。数据定义和生成线性表

#defineM1000

shortn;/*M>=n7

shorta[M];/*在a[0卜a[n-1]中分别存放各结点的值3ko~Bknr*/

。生成线性表的程序

scanf("%hd",&n);

if(n>M||n<1)

error();/*结点数超界*1

for(j=0;j<n;j++)

scanf("%hd",&a[j]);

※线性表的链接存储

采用链表实现线性表的链接存储.

。存储单元

ki={aki,8ki,pki}

其中，

pki=akj+i

。数据定义

#defineNODEstructnode

NODE

(

shortnum;/*5ki*1

NODE*next；/*aki+i*/

)；

shortn;

。生成带哨兵的链表

指针Head指向一个空置的结点(哨兵)，首指针为Head->next,即Head->next为始

结点k0的地址ako，终结点kn-i的指针next指向空(NULL)。

NODE*Head;/*设置哨兵*/

/*生成哨兵*/

if((Head=(NODE*)(malloc(sizeof(NODE)))==NULL)

error();/*内存分配失败*/

Head->next=NULL;

/*生成链表*/

createList(Head);___

。链表生成函数

voidcreateList(NODE*head)

(

shortn,j,num;

NODE*node;

scanf("%hd",&n);

if(n<1)

error();I*结点数超界

for(j=0;j<n;j++)

if((node=(NODE*)(malloc(sizeof(NODE)))==NULL)

error();/*内存分配失败7插入后head2000

scanf("%hd",&num);

node->num=num;

node->next=head->next;

head->next=node;

)

4.2.2查找结点

※查找结点的操作

。按结点值查找

根据结点kj的值的查找结点，打印序号j,使得3kj==key。

查找条件酝词瓯=.京2==q/3==®1查找结果

卜《丫=6常写』：/彳sj=3

。按结点地址查找

根据结点kj的序号j(ak),查找结点kj,打印结点始值3L

查找条件j==3查找结果

j=38k3==6

®-<5)­<2>6

。按前件或后件查找

根据结点用的前件(或后件)k'的值3k',打印序号j和结点kj的值bkj,使得bk'==key。

查找条件4查找结果

前件的值5k2==5

8k'=2

※顺序存储的查找结点

。根据结点值查找结点的程序

#include<stdio.h>

#include<stdlib.h>

#defineM1000

voidsearchNode(short*a,shortn,shortkey)

main()

shortj;

for(j=0;j<n;j++)shortn,a[M],j,key;

if(a[j]==key)scanf(u%hdM,&n);

if(n>M||n<1)

printf("node(%hd)=',j);error();/*结点数超界*/

printf(H%hd\n",a[j]);for(j=0;j<n;j++)

return;scanf(H%hd",&a[j]);

)scanf(,,%hdM,&key);

error();/*查找结点失败*/searchNode(a,n,key);

))

。算法复杂度

查找次数与n成正比，最多为n次，称该算法的时间复杂度为0(n)。

。根据结点地址查找结点的程序main()

#include<stdio.h>

#include<stdlib.h>shortn,a[M],j;

#defineM1000scanf(u%hdn,&n);

voidprtNode(a,n,j)if(n>M||n<1)

shortn,a[],j;error();/*结点数超界*/

for(j=0;j<n;j++)

if(j<0||j>n-1)scanf("％hd”,&a[j]);

error();/*结点地址超界*/scanf("％hd”,&j);

printf(unode(%hd)=%hd\n”,j,a[j]);prtNode(a,n,j);

))

。算法复杂度

查找次数与n无关，是一个常数C,称该算法的时间复杂度为0(C)。

※链接存储的查找结点

main()

(生成哨兵

NODE*Head,*node;

shortkey;Head

/*生成哨兵*/一|___1

if((Head=(NODE*)(malloc(sizeof(NODE)))==NULL)|NULL|

error();/*内存分配失败*/

Head->next=NULL;

/*生成链表*/生成链表

createList(Head);createList。

/*读入key*/

scanf("%hd",&key);读入key

r查找结点*/scanf()

if(node=searchNode(Head,key))

printf("node=%hd\n",node->num);

else查找结点

error();/*查找结点失败*1searchNode。

}

◎查找结点函数

NODE*searchNode(NODE*head,shortkey)

(

NODE*node;

for(node=head->next;node;node=node->next)

if(node->num==key)

return(node);

return(NULL);/*查找结点失败*1

}

。算法复杂度

查找次数与n成正比，最多为n次。称该算法的时间复杂度为0(n)。

4.2.3添加结点

※顺序存储的添加结点

0添加结点的操作

已知结点kj的地址akj,在kj后添加新结点k',使得6k'=key。

添加前j=24添加后

今

8k=3

将a［n-1］到a［j+1］向数组尾部移动，腾出添加新结点key的位置，再将新结点key插入。

j—j——线性表----------------------►

粤口位置

kn-1

a[0]……aO]|a0+1]…………a[n-1]……a[M-1]

----------►向后移动

<-------------------------数组--------

。顺序存储添加结点的程序

#include<stdio.h>

#include<stdlib.h>

#defineM1000

voidaddNode(a,n,j,key)

shorta[],j,key;main()

short*n;/*添加结点后*n要加1*1(

(shorta[M],n,j,key;

shortk;scanf("％hd”，&n);

ifG<-1llj>(*n)-1)if(n>M-1||n<1)

error();/*结点地址超界*1error();/*结点数超界7

for(k=(*n)-1;k>j;k-)for(j=0;j<n;j++)

a[k+1]=a[k];/*向后移动*/scanf("％hd”,&a[j]);

aO+1]=key;scanf("%hd%hd”,&j,&key);

(*n)++;addNode(a,&n,j,key);

。添加结点的算法复杂度

移动次数最多为n次，算法复杂度为O(n)。

※链接存储的添加结点

。添加结点的操作

已知结点k的值3k,在k后添加新结点k',使得3k'=key。

添加前§k=5(T)添加后区)区)

Sk，=3⑦-代i芬小⑦-返＞■遂④

由key指向待添加结点k'。先查找结点k,由node指向结点k,再在node后面插入结点k'。

添加前node1100‘添加］key3000添加后node11003000

1100—►8kI3000f8k,1100­►5k5k,

#依「待加结点W1=>3000T#

。链接存储添加结点的函数

voidaddNode(NODE*node,shortkey)

(

NODE*key;

if(node==NULL)

error();/*非法结点*/

key=(NODE*)(malloc(sizeof(NODE)));

if(key==NULL)

error();/*内存分配失败7

key->num=key;

key->next=node->next;

node->next=key;

)

。链接存储添加结点的算法复杂度

添加结点的操作次数与n无关，是一个常数C,算法复杂度为0(C)。

。链接存储添加结点的程序

#include<stdio.h>

#include<stdlib.h>

#defineNODEstructnode

NODE

shortnum;

NODE*next;

)；

voidcreateList(NODE*head)

{……}/*略*/

NODE*searchNode(NODE*head,shortkey)

{……}/*B&7

main()

(

shortkey,nxtkey;

NODE*Head,node;

r生成哨兵*/

if{(Head=(NODE*)(malloc(sizeof(NODE)))==NULL)

error();/*内存分配失败*/

Head->next=NULL;

/*生成链表*/

createList(Head);

/*读入key,nxtkey*/

scanf("%hd%hd",&key,&nxtkey);

/*查找结点*/

if(!(node=searchNode(Head,key))

error();/*查找结点失败*/

/*添加结点*/

addNode(node,nxtkey);

)

4.2.4删除结点

※顺序存储的删除结点

◎删除结点的操作

已知结点kj的地址akj,删除kjo

。顺序存储删除结点的程序

include<stdio.h>

#include<stdlib.h>

#defineM1000

voiddeleteNode(a,n,j)main()

shorta[],j;(

short*n;/*删除结点后*n要减1*/shorta[M],n,j,key;

(scanf("％hd”，&n);

shortk;if(n>M-1||n<1)

if(j<0||j>(*n)-1)error();/*结点数超界*/

error();/*结点地址超界*/for(j=0;j<n;j++)

for(k=j+1;k<(*n);k++)scanf("％hd”,&a[j]);

a[k-1]=a[k];/*向前移动7scanf("％hd”,&j);

⑴)一；deleteNode(a,&n,j);

))

。删除结点的算法复杂度

移动次数最多为n・1次，算法复杂度为O(n)。

a[0]aO]aO+1].....……|a[n-1]............

陷删除鼠缸=亟］

a[0].........................a[n-1]..........

※链接存储的删除结点

。删除结点的操作

已知结点k的值6k,删除k的后件k'。

册U除前⑷区)1s删除后旧

8k=5叩⑦

先查找结点k,由node指向结点k,由node->next指向node的后件k'(待删结点key),再

删除结点k'。

1100

8k

#

。链接存储删除结点的函数

voiddeleteNode(NODE*node)

(

NODE*key;

if(node==NULL)

error();/*非法结点*/

key=node->next;

node->next=key->next;

free(key);/*释放删除结点的存储单元*/

}

◎链接存储删除结点的算法复杂度

删除结点的操作次数与n无关，是一个常数C,算法复杂度为0(C)。

。链接存储删除结点的程序

include<stdio.h>

#include<stdlib.h>

#defineNODEstructnode

NODE

shortnum;

NODE*next;

);

voidcreateList(NODE*head)

{……}/*略*/

NODE*searchNode(NODE*head,shortkey)

{……}/*略*/

main()

(

shortkey;

NODE*Head,node;

/*生成哨兵*/

Head=(NODE*)(malloc(sizeof(NODE)));

if(Head==NULL)

error();/*内存分配失败*/

Head->next=NULL;

/*生成链表*/

createList(Head);

r读入key*/

scanf("%hd",&key);

/*查找结点*1

if(!(node=searchNode(Head,key))

error();/*查找结点失败*/

I*删除结点后件*/

deleteNode(node);

)

4.2.5排序

※排序问题

以升序为例讨论排序问题。

。定义：

已知结点序列K={k0,ki,k2,....kn-i},经排序得到K'={k'o,k]k'2，…，—使得K和

K'中结点数值相同，而5ki'W3k'i+i(i=0,1,…，n-2),称新的结点序列K'为已排序的结点序歹

。需要掌握五种排序算法：

(1)插入排序法以下仅讨论插入排序算法

(2)选择排序法

(3)冒泡排序法

(4)快速排序法

(5)合并排序法

※插入排序算法

。插入排序算法描述

设已知结点序列为K={k0,k,k2，…，kn.i},

将已排序的结点序列记为S,未排序的结点序列记为U。

初始：令$=*。},U=K-{k0}={k1,k2，…，kn.i}

循环执行的插入步骤：

从i=1到n-1

令key=ki|k{U,U=U-{ki}

在S中插入k”使得S=SU{key}为已排序。

若U=q),插入排序结束。

0排序过程示例

已知结点序列为{6,5,9,4,8}。

初始：令$=伙0}={6},U={ki，…，k4}={5,9,4,8)o

循环插入的过程示例：

Step1:i=1,插入5,得$={5,6},U={9,4,8)；

Step2:i=2,插入9>得$={5,6,9),U={4,8};

Step3:i=3,插入4,得S={4,5,6,9),U={8}；

Step4:i=4,插入8,得S={4,5,6,8,9},U=(p,结束。

※顺序存储的插入排序函数

voidinsert(short*a,shortn)

(

shortkey,j,k;

for(j=1;j<n;j++)/*初始*1

{/*备存:key=a[j],定位:key<a[k]*/

for(key=a[j],k=j-1;key<a[k]&&k>=0;k-)

a[k+1]=a[k];/*移动*/

a[++k]=key;/*插入7

)

)

<-----------------------S:已排序------------——U:未排序

插入^-------

a[0]……a[k]……|a[j-1]|a[j]]……|a[n-1]

P®A:a[kl=keykey

。顺序存储的插入排序程序

include<stdio.h>

#include<stdlib.h>

#defineM1000

voidinsert(short*a,shortn)

{……}/*略*/

main()

(

shorta[M],n,j;

scanf("％hd"，&n);

if(n>M-1||n<1)

error();/*结点数超界*/

for(j=0;j<n;j++)

scanf("%hd",&a[j])；

/*排序*/

insert(a,n);■.Q.

■o

for(j=0;j<n;j++)/*打印*/

printf("％hd\n”,aQ])；

)

。顺序存储插入排序的算法复杂度

考虑n很大时，最多移动次数

=1+...+(n-2)+(n-1)=(n-1)*n/2=n2/2«=n2

所以，算法复杂度为0(产)。

※链接存储的插入排序

。链接存储的插入排序算法

1)初始设置

由head->next指向S={⑹，由指针unsort指向未排序的结点序列U=K-S=K-{k0}»

程序语句为：

unsort=head->next->next;

head->next->next=NULL;

,O''0r

已排序结点序列S={k}未排序结点序列

0U=K-S=K-{k0}

Head20001100unsort21002500

2100-►3kl取向

1200_n-_rNULL|

2)从U中逐个取出结点在S中排序的过程

while(unsort)

从U中取出一个结点，由指针key指向，即在U中删除结点:

key=ki|kiWU,U=U-{kJ

程序语句为：

key=unsort;

unsort=key->next;

未排序结点序列uU=U-{key}

unsort31002200unsort2200key3100

3100f|2200-►3100-►

2200##In

将结点key插入S：S=SU{key),并且保持S为已排序。

。链接存储的插入排序函数

voidinsert(head)

NODE*head;

NODE*unsort,*key,*node;

if(head->next==NULL||head->next->next==NULL)

return;/*空链表或者单结点链表*/

unsort=head->next->next;/*初始：S={ko},U=K-{ko}*/

head->n