计算机软件技术基础徐士良第2章1

第2章基本数据结构及其运算2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表及其运算2.4数组2.5树与二叉树2.6图1第2章基本数据结构及其运算2.1数据结构的基本概念2.1.1两个例子2.1.2什么是数据结构2.1.3数据结构的图形表示2.1.4线性数据结构与非线性数据结构2第2章基本数据结构及其运算数据结构三个方面的问题：(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算目的：提高数据处理的效率提高数据处理的速度尽量节省计算机存储空间

3第2章基本数据结构及其运算2.1.1两个例子例无序表的顺序查找35167885432933215446有序表的对分查找16212933354346547885数据元素在表中的排列顺序对查找效率是有很大影响。4第2章基本数据结构及其运算例学生情况登记表以学号为顺序排列5第2章基本数据结构及其运算6第2章基本数据结构及其运算7第2章基本数据结构及其运算8第2章基本数据结构及其运算结论：在对数据进行处理时，可以根据所做的运算不同，将数据组织成不同的形式，以便于做该种运算，从而提高数据处理的效率。9第2章基本数据结构及其运算2.1.2什么是数据结构

数据结构是指相互有关联的数据元素集合。

现实世界中客观存在的一切个体都可以是数据元素。10第2章基本数据结构及其运算描述一年四季的季节名春，夏，秋，冬可以作为季节的数据元素；表示数值的各个数

18，11，35，23，16，…

可以作为数值的数据元素；表示家庭成员的各成员名父亲，儿子，女儿可以作为家庭成员的数据元素。11第2章基本数据结构及其运算

前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。12第2章基本数据结构及其运算1.数据的逻辑结构

是指反映数据元素之间逻辑关系的数据结构。（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。13第2章基本数据结构及其运算

数据的逻辑结构有两个要素：数据元素的集合D；反映D中各数据元素之间的前后件关系R。

数据结构可以表示成

B＝（D，R）其中B表示数据结构。14第2章基本数据结构及其运算为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。例如

B＝（D，R）

D＝{春，夏，秋，冬}

R＝{(春，夏)，(夏，秋)，(秋，冬)}15第2章基本数据结构及其运算家庭成员数据结构

B＝（D，R）

D＝{父亲，儿子，女儿}R＝{(父亲，儿子），(父亲，女儿）}n维向量

X＝（x1，x2，…，xn）也是一种数据结构。即

X＝（D，R）

D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}16第2章基本数据结构及其运算m×n的矩阵是一个数据结构。即

A＝（D，R）

D＝{A1，A2，…，Am}R＝{(A1，A2)，(A2，A3)，…，(Ai，Ai＋1)，…，(Am－1，Am)}其中Ai=（ai1，ai2，…，ain），i＝1，2，…，m

Ai＝（Di，Ri）

Di＝{ai1，ai2，…，ain}

Ri＝{(ai1，ai2)，(ai2，ai3)，…，(aij，ai，j＋1)，…，(ai，n－1，ain)}17第2章基本数据结构及其运算2.数据的存储结构（数据的物理结构）

数据的逻辑结构在计算机存储空间中的存放形式。常用的存储结构有：顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。18第2章基本数据结构及其运算2.1.3数据结构的图形表示数据集合D中的每一个数据元素用中间标有元素值的方框表示（数据结点，结点）用一条有向线段从前件结点指向后件结点。19第2章基本数据结构及其运算

一年四季数据结构的图形表示20第2章基本数据结构及其运算

家庭成员间辈份关系数据结的图形表示21第2章基本数据结构及其运算

用图形表示数据结构B＝（D，R）D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}22第2章基本数据结构及其运算2.1.4线性数据结构与非线性数据结构线性结构：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。线性结构又称线性表。23第2章基本数据结构及其运算不是线性结构的数据结构特例

24第2章基本数据结构及其运算

如果一个数据结构不是线性结构，则称之为非线性结构25第2章基本数据结构及其运算2.2线性表及其顺序存储结构2.2.1线性表及其运算2.2.2栈及其应用2.2.3队列及其应用26第2章基本数据结构及其运算2.2.1线性表及其运算1.什么是线性表(LinearList)n维向量(x1，x2，…，xn)是一个长度为n的线性表英文小写字母表(a，b，c，…，z)是一个长度为26的线性表一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表矩阵是一个比较复杂的线性表27第2章基本数据结构及其运算学生情况登记表是一个复杂的线性表由若干数据项组成的数据元素称为记录(record)

由多个记录构成的线性表又称为文件(file)28第2章基本数据结构及其运算

线性表是由n(n≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为

(a1，a2，…，ai，…，an)

其中ai(i＝1，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。29第2章基本数据结构及其运算

非空线性表结构特征：

(1)有且只有一个根结点a1，它无前件；

(2)有且只有一个终端结点an，它无后件；

(3)除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。30第2章基本数据结构及其运算2.线性表的顺序存储结构线性表的顺序存储结构基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表中第i个元素ai在计算机存储空间中的存储地址为

ADR(ai)＝ADR(a1)＋(i－1)k31第2章基本数据结构及其运算长度为n的线性表(a1，a2，…，ai，…，an)顺序存储结构32第2章基本数据结构及其运算整型一维数组存放长度为8的线性表(29,18,56,63,35,24,31,47)33第2章基本数据结构及其运算建立空线性表的顺序存储空间（即初始化线性表的顺序存储空间）

#include"stdlib.h"voidinitsl(v，m，n)ET*v；

intm，*n；

{v＝malloc(m*sizeof(ET))；*n＝0；

return；

}释放线性表的顺序存储空间

free(v)；34第2章基本数据结构及其运算

线性表顺序存储结构下的主要运算：(1)在线性表的指定位置处加入一个新的元素（即线性表的插入）；(2)在线性表中删除指定的元素（即线性表的删除）；(3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）；(4)对线性表中的元素进行整序（即线性表的排序）；(5)按要求将一个线性表分解成多个线性表（即线性表的分解）；(6)按要求将多个线性表合并成一个线性表（即线性表的合并）；(7)复制一个线性表（即线性表的复制）；(8)逆转一个线性表（即线性表的逆转）等。35第2章基本数据结构及其运算3.线性表在顺序存储下的插入运算36第2章基本数据结构及其运算37第2章基本数据结构及其运算线性表在顺序存储下的插入算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。输出：插入后的线性表存储空间V(1：m)及线性表的长度n。

PROCEDUREINSL(V，m，n，i，b)1.IF(n＝m)THEN{OVERFLOW；RETURN}2.IF(i＞n)THENi＝n＋13.IF(i＜1)THENi＝14.FORj＝nTOiBY－1DOV(j＋1)＝V(j)5.V(i)＝b6.n＝n＋17.RETURN38第2章基本数据结构及其运算

voidinsl(v，m，n，i，b)ETv[]，b；

intm，*n，i；

{if(*n＝＝m){printf("overflow\n")；return；}if(i＞*n－1)i＝*n＋1；

if(i＜1)i＝1；

for(j＝*n；j＜＝i；j――)v[j]＝v[j－1]；

v[i－1]＝b；*n＝*n＋1；

return；

}39第2章基本数据结构及其运算4.线性表在顺序存储下的删除运算40第2章基本数据结构及其运算41第2章基本数据结构及其运算线性表在顺序存储下的删除算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；删除的位置i（表示删除第i个元素）。输出：删除后的线性表存储空间V(1：m)及线性表的长度n。

PROCEDUREDESL(V，m，n，i)1.IF(n＝0)THEN{UNDERFLOW；RETURN}2.IF(i＜1)or(i＞n)THEN{“Notthiselementinthelist”；RETURN}3.FORj＝iTOn－1DOV(j)＝V(j＋1)4.n＝n－15.RETURN42第2章基本数据结构及其运算

voiddesl(v，m，n，i)ETv[]；

intm，*n，i；

{if(*n＝＝0){printf("underflow\n")；return；}if((i＜1)||(i＞*n))

{printf("Notthiselementinthelist\n")；

return；

}for(j＝i；j＜＝*n－1；j＋＋)v[j－1]＝v[j]；*n＝*n－1；

return；

}43第2章基本数据结构及其运算2.2.2栈及其应用1.什么是栈主程序与子程序之间的调用关系

MAIN

SUB1

SUB2

SUB3SUB4……

……

……

…………CALLSUB1

CALLSUB2

CALLSUB3

CALLSUB4……A：……

B：……

C：……

D：……

……

……

……

……

…………END

RETURN

RETURN

RETURNRETURN44第2章基本数据结构及其运算栈(stack)是限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈是按照“先进后出”(FILO—FirstInLastOut)或“后进先出”(LIFO—LastInFirstOut)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。栈具有记忆作用。用指针top来指示栈顶的位置，用指针bottom指向栈底。往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。45第2章基本数据结构及其运算46第2章基本数据结构及其运算2.栈的顺序存储及其运算47第2章基本数据结构及其运算top＝0表示栈空；top＝m表示栈满。建立空栈的顺序存储空间（即初始化栈的顺序存储空间）

#include"stdlib.h"voidinit_stack(s，m，top)ET*s；

intm，*top；

{s＝malloc(m*sizeof(ET))；*top＝0；

return；

}释放栈的顺序存储空间时

free(s)；48第2章基本数据结构及其运算

(1)入栈运算

PROCEDUREPUSH(S，m，top，x)1.IF(top＝m)THEN{Stack－OVERFLOW；RETURN}2.top＝top＋13.S(top)＝x4.RETURNvoidpush(s，m，top，x)ETs[]，x；

intm，*top；

{if(*top＝＝m){printf("Stack－overflow\n")；return；}*top＝*top＋1；s[*top－1]＝x；

return；

}49第2章基本数据结构及其运算(2)退栈运算PROCEDUREPOP(S，m，top，y)1.IF(top＝0)THEN{Stack－UNDERFLOW；RETURN}2.y＝S(top)3.top＝top－14.RETURNvoidpop(s，m，top，y)ETs[]，*y；

intm，*top；{if(*top＝＝0){printf("Stack－underflow\n")；return；}*y＝s[*top－1]；*top＝*top－1；

return；}50第2章基本数据结构及其运算(3)读栈顶元素PROCEDURETOP(S，m，top，y)1.IF(top＝0)THEN{“Stackempty”；RETURN}2.y＝S(top)3.RETURNvoidtop(s，m，top，y)ETs[]，*y；

intm，*top；{if(*top＝＝0){printf("Stackempty\n")；return；}*y＝s[*top－1]；

return；}51第2章基本数据结构及其运算3.表达式的计算运算符栈，用于在表达式处理过程中存放运算符。在开始时，运算符栈中先压入一个表达式结束符“；”。操作数栈，用于在表达式处理过程中存放操作数。52第2章基本数据结构及其运算从左到右依次读出表达式中的各个符号：若是操作数，则压入操作数栈，依次读下一个符号。若是运算符，则作进一步判断：

①若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。②若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。③若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作数栈。53第2章基本数据结构及其运算A＋B*C－D/E；54第2章基本数据结构及其运算A＋B*C－D/E；55第2章基本数据结构及其运算A＋B*C－D/E；56第2章基本数据结构及其运算A＋B*C－D/E；57第2章基本数据结构及其运算4.递归依次打印输出自然数1到n的非递归算法

PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN依次打印输出自然数1到n的递归算法

PROCEDUREWRT(n)IF(n≠0)THEN{WRT(n)；OUTPUTn}RETURN58第2章基本数据结构及其运算

#include"stdio.h"wrt(intn){if(n!＝0)

{wrt(n－1)；

printf("%d\n"，n)；}return；

}59第2章基本数据结构及其运算2.2.3队列及其应用1.什么是队列队列(equeue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，用尾指针(rear)指向队尾元素。允许删除的一端称为排头(也称队头)，用排头指针(front)指向排头元素的前一个位置。队列又称为“先进先出”(FIFO—FirstInFirstOut)或“后进后出”(LILO—LastInLastOut)的线性表，体现了“先来先服务”的原则。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。60第2章基本数据结构及其运算61第2章基本数据结构及其运算2.循环队列及其运算62第2章基本数据结构及其运算63第2章基本数据结构及其运算队列空的条件为s＝0队列满的条件为(s＝1)且front＝rear64第2章基本数据结构及其运算建立循环队列顺序存储空间（即初始化循环队列顺序存储空间）#include"stdlib.h"voidinit_queue(q，m，front，rear，s)ET*q；

intm，*front，*rear，*s；{q＝malloc(m*sizeof(ET))；*front＝m；*rear＝m；*s＝0；

return；}释放循环队列的顺序存储空间free(q)；65第2章基本数据结构及其运算(1)入队运算PROCEDUREADDCQ(Q，m，rear，front，s，x)1.IF(s＝1)and(rear＝front)THEN{Queue－OVERFLOW；RETURN}2.rear＝rear＋13.IF(rear＝m＋1)THENrear＝14.Q(rear)＝x5.s＝16.RETURN66第2章基本数据结构及其运算voidaddcq(q，m，rear，front，s，x)ETq[]，x；

intm，*rear，*front，*s；{if((*s＝＝1)&&(*rear＝＝*front)){printf("Queue－OVERFLOW\n")；

return；

}*rear＝*rear＋1；

if(*rear＝＝m＋1)*rear＝1；

q[*rear－1]＝x；*s＝1；return；}67第2章基本数据结构及其运算(2)退队运算PROCEDUREDELCQ(Q，m，rear，front，s，y)1.IF(s＝0)THEN{Queue－UNDERFLOW；RETURN}2.front＝front＋13.IF(front＝m＋1)THENfront＝14.y＝Q(front)5.IF(front＝rear)THENs＝06.RETURN68第2章基本数据结构及其运算voiddelcq(q，m，rear，front，s，y)ETq[]，*y；

intm，*rear，*front，*s；{if(*s＝＝0){printf("Queue－UNDERFLOW\n")；return；}*front＝*front＋1；

if(*front＝＝m＋1)*front＝1；*y＝q[*front－1]；

if(*front＝＝*rear)*s＝0；

return；}69第2章基本数据结构及其运算3.队列的应用

(1)给工人分配工作的模拟开辟一个队列结构的线性表。设置一个排头指针和一个队尾指针。初始时队列为空。每当有一个工人到调度员处报到时（包括新来的与完成任务后返回的），都将他加入到队尾；当需要一名工人去做某项工作时，就派排头的工人去做该项工作。70第2章基本数据结构及其运算(2)输入输出缓冲区的结构71第2章基本数据结构及其运算(3)汽车加油站的工作模拟

汽车加油站有两台油泵，每台油泵为一辆汽车加油的时间为d分钟。该加油站的到车率为1辆/g分钟。用一个容量为m的循环队列来组织等待加油的汽车，并对到达加油站的汽车按先后顺序用自然数给予编号。假设循环队列的存储空间用一维数组cq(1：m)模拟，初始状态为rear＝front＝m，并假定该循环队列不会发生队列满的情况。其次，假设模拟的时间长度为time分钟，并用时间步长法进行模拟，取采样时间间隔为dt，即每隔dt分钟对汽车加油站的工作情况测试一次，同时输出汽车排队的情况及每台油泵的工作情况。72第2章基本数据结构及其运算模拟汽车排队（SIMUAUTO）一分钟来一辆车的概率为1/g。在采样时间间隔dt分钟内来一辆车的概率为dt/g。要求采样的时间间隔dt＜g。在实际模拟时，每隔dt分钟（即每次采样测试时）产生一个0到1之间均匀分布的随机数rnd。若rnd≤dt/g，则认为有一辆车到达，并将它编号，加入到循环队列中。PROCEDURESIMUAUTO(CQ，m，rear，num，dt，g，rnd)IF(rnd＜＝dt/g)THEN{num＝num＋1rear＝rear＋1IF(rear＝m＋1)THENrear＝1CQ(rear)＝num}RETURN73第2章基本数据结构及其运算模拟油泵工作用标志flag(i)表示第i(i＝1，2)台油泵的工作进程，aut(i)表示第i台油泵服务的对象（即汽车的编号）。当第i台油泵开始为一辆车加油服务时，置工作进程标志为flag(i)＝d－dt；以后每经过dt分钟，令flag(i)＝flah(i)－dt。当flag(i)＜0时，说明第i台油泵刚完成对一辆汽车的加油服务，有可以从循环队列的排头取出一辆汽车进行服务。若此时队列为空，则置油泵为空闲状态，即置flag(i)＝074第2章基本数据结构及其运算PROCEDURESIMUPUMP(CQ，m，front，rear，dt，d，flag，aut，i)IF(flag(i)＜＝0)THEN{IF(front＝rear)THENflag(i)＝0ELSE{front＝front＋1IF(front＝m＋1)THENfront＝1aut(i)＝cq(front)flag(i)＝d－dt

}}ELSEflag(i)＝flag(i)－dtRETURN75第2章基本数据结构及其运算采样测试结果输出每隔dt分钟将汽车队列的情况以及每台油泵的工作情况的模拟结果打印输出。PROCEDUREOUT(CQ，m，front，rear，flag，aut)k＝frontWHILE(k≠rear)DO{k＝k＋1IF(k＝m＋1)THENk＝1OUTPUTCQ(k)}OUTPUTflag(1)，aut(1)OUTPUTflag(2)，aut(2)RETURN76第2章基本数据结构及其运算在输出结果中，分以下两种情况：当aut(i)＞0时：若flag(i)＞0，

则aut(i)值为油泵i正在服务的对象；

若flag(i)＜0，

则aut(i)值为油泵i刚服务完的对象；若flag(i)＝0，

则aut(i)值为油泵i已服务完的对象。当aut(i)＝－1时，表示油泵i还未服务过。77第2章基本数据结构及其运算主模块①分配循环队列空间CQ(1：m)，并置循环队列为空。即置front＝rear＝m。②置每台油泵为空闲。即置flag(1)＝flag(2)＝0。③置每台油泵还无服务对象。即置aut(1)＝aut(2)＝－1。78第2章基本数据结构及其运算/*主模块*/#include"stdlib.h"#include"math.h"#include"stdio.h"main(){int*cq，m，front，rear，aut[2]，flag[2]，num；

doubletime，dt，t，g，d，rnd，r＝1.0，s；

m＝10；/*循环队列空间的容量*/

cq＝malloc(m*sizeof(int))；/*分配循环队列的顺序存储空间*/

rear＝m；front＝m；/*初始化循环队列*/

aut[0]＝－1；

aut[1]＝－1；/*置每台油泵还未服务过*/

flag[0]＝0；flag[1]＝0；/*置每台油泵为空闲*/num＝0；t＝0；79第2章基本数据结构及其运算

printf("inputg：")；

scanf("%lf"，&g)；/*输入来一辆车的平均时间*/

printf("inputd：")；

scanf("%lf"，&d)；/*输入油泵为一辆车加油所需要的时间*/

printf("inputtime：")；

scanf("%lf"，&time)；/*输入总的模拟时间长度*/

printf("inputdt：")；

scanf("%lf"，&dt)；/*输入采样时间间隔*/

printf("－－－－－－－－－－－－－－－－－－－－－－－－－－－\n")；80第2章基本数据结构及其运算

while(t＜time)/*模拟时间未结束*/

{r＝2053.0*r＋13849.0；

s＝(int)(r/65536.0)；

r＝r－s*65536.0；

rnd＝r/65536.0；/*产生一个0到1之间的随机数*/

simuauto(cq,m,&rear,&num,dt,g,rnd)；/*模拟汽车排队*/

simupump(cq，m，&front，rear，dt，d，flag，aut，1)；

/*模拟油泵1工作*/

simupump(cq，m，&front，rear，dt，d，flag，aut，2)；

/*模拟油泵2工作*/

out(cq，m，front，rear，flag，aut)；/*模拟结果输出*/

t＝t＋dt；

}free(cq)；/*释放循环队列空间*/}81第2章基本数据结构及其运算/*模拟汽车排队*/simuauto(cq，m，rear，num，dt，g，rnd)intcq[]，m，*rear，*num；doubledt，g，rnd；{if(rnd＜＝dt/g){*num＝*num＋1；*rear＝*rear＋1；

if(*rear＝＝m＋1)*rear＝1；

cq[*rear－1]＝*num；

}}82第2章基本数据结构及其运算/*模拟油泵工作*/simupump(cq，m，front，rear，dt，d，flag，aut，i)intcq[]，m，*rear，*front，flag[]，aut[]，i；doubledt，d；{if(flag[i－1]＜＝0){if(*front＝＝rear)flag[i－1]＝0；

else{*front＝*front＋1；

if(*front＝＝m＋1)*front＝1；

aut[i－1]＝cq[*front－1]；

flag[i－1]＝d－dt；

}}elseflag[i－1]＝flag[i－1]－dt；}83第2章基本数据结构及其运算/*模拟结果输出*/out(cq，m，front，rear，flag，aut)intcq[]，m，front，rear，flag[]，aut[]；{intk；

k＝front；

while(k!＝rear){k＝k＋1；

if(k＝＝m＋1)k＝1；

printf("cq(%d)＝%d\n"，k，cq[k－1])；

}

printf("flag(1)＝%d，aut(1)＝%d\n"，flag[0]，aut[0])；

printf("flag(2)＝%d，aut(2)＝%d\n"，flag[1]，aut[1])；

printf("－－－－－－－－－－－－－－－－－－－－－－－－－－－\n")；}84第2章基本数据结构及其运算2.3线性链表及其运算2.3.1线性链表的基本概念2.3.2线性链表的基本运算2.3.3循环链表85第2章基本数据结构及其运算2.3.1线性链表的基本概念1.线性链表线性表的链式存储结构称为线性链表。86第2章基本数据结构及其运算87第2章基本数据结构及其运算88第2章基本数据结构及其运算89第2章基本数据结构及其运算90第2章基本数据结构及其运算依次输出线性链表中的各结点值输入：线性链表的存储空间V(1：m)、NEXT(1：m)；

线性链表的头指针HEAD。输出：依次输出线性链表中各结点的值。

PROCEDUREPRTLL(HEAD)j＝HEADWHILE(j≠0)DO{OUTPUTV(j)；j＝NEXT(j)}RETURN91第2章基本数据结构及其运算

struct结构体名

{数据成员表；

struct结构体名*指针变量名；

}例如

structnode{charname[10]；/*数据域*/

charsex；/*数据域*/

structnode*next；/*指针域*/}92第2章基本数据结构及其运算#include"stdlib.h"/*malloc函数需要包含头文件stdlib.h*/structnode/*定义结点类型*/{intd；/*数据域*/

structnode*next；/*指针域*/}main(){structnode*p；/*定义该类型的指针变量p*/…p=(structnode*)malloc(sizeof(structnode))；

/*申请分配结点存储空间*/…

free(p)；/*释放结点存储空间*/}93第2章基本数据结构及其运算#include"stdlib.h"#include"stdio.h"structnode/*定义结点类型*/{intd；

structnode*next；

}main(){intx；

structnode*head，*p，*q；

head＝NULL；/*置链表空*/

q＝NULL；

scanf(“%d”，&x)；/*输入一个正整数*/94第2章基本数据结构及其运算

while(x＞0)/*若输入值大于0*/

{p＝(structnode*)malloc(sizeof(structnode))；/*申请一个结点*/

p－>d＝x；p－>next＝NULL；/*置当前结点的数据域和指针域*/

if(head＝＝NULL)head＝p；/*若链表空，则将头指针指向当前结点p*/elseq－>next＝p；/*将当前结点链接在最后*/

q＝p；/*置当前结点为链表最后一个结点*/

scanf("%d"，&x)；

}p＝head；

while(p!＝NULL)/*从链表第一个结点开始打印各结点元素值，并删除*/{printf("%5d"，p－>d)；/*打印当前结点中的数据*/

q＝p；p＝p－>next；free(q)；/*删除当前结点并释放该结点空间*/}

printf("\n")；}95第2章基本数据结构及其运算双向链表96第2章基本数据结构及其运算2.带链的栈97第2章基本数据结构及其运算可利用栈及其运算98第2章基本数据结构及其运算将结点送回可利用栈输入：可利用栈栈顶指针TOP（默认）；送回可利用栈的结点序号p。输出：结点p入栈后的可利用栈栈顶指针TOP（默认）。

PROCEDUREDISPOSE(p)NEXT(p)＝TOP；TOP＝pRETURN从可利用栈取得一个结点输入：可利用栈的栈顶指针TOP（默认）。输出：退栈后的可利用栈栈顶指针TOP（默认）；存放取得结点序号的变量p。

PROCEDURENEW(p)p＝TOP；TOP＝NEXT(TOP)RETURN99第2章基本数据结构及其运算带链栈的入栈运算输入：带链栈的栈顶指针top；入栈的元素值x。输出：元素x入栈后的带链栈栈顶指针top。

PROCEDUREPUSHLL(top，x)NEW(p)[从可利用栈取得一个新结点]

V(p)＝x[置新结点数据域]

NEXT(p)＝top[置新结点指针域]

top＝p[改变栈顶指针]

RETURN100第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/

structnode*next；

}；pushll(top，x)ETx；

structnode**top；{structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝*top；/*置新结点的数据域与指针域*/*top＝p；/*改变栈顶指针*/

return；}101第2章基本数据结构及其运算带链栈的退栈运算输入：带链栈的栈顶指针top。输出：退栈后的带链栈栈顶指针top；存放退出结点元素值的变量y。

PROCEDUREPOPLL(top，y)y＝V(top)[取出栈顶元素值]

p＝toptop=NEXT(p)[改变栈顶指针]

DISPOSE(p)[被删除结点送回可利用栈]

RETURN102第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/

structnode*next；

}；popll(top，y)ETy；

structnode**top；{structnode*p；

y＝*top－>d；/*取出栈顶元素值*/

p＝*top；*top＝p－>next；/*改变栈顶指针*/

free(p)；return；/*释放被删除结点后返回*/}103第2章基本数据结构及其运算3.带链的队列104第2章基本数据结构及其运算带链队列的入队运算输入：带链队列的队尾指针rear；入队的新元素x。输出：元素x入队后的带链队列队尾指针rear。

PROCEDUREADDLL(rear，x)NEW(p)[从可利用栈取得一个新结点p]V(p)＝x[置新结点的数据域]

NEXT(p)＝0[置新结点的指针为空]

NEXT(rear)＝p[最后一个结点的指针指向新结点]

rear＝p[改变队尾指针]

RETURN105第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/

structnode*next；

}；addll(rear，x)ETx；

structnode**rear；{structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝NULL；/*置新结点的数据域与指针域*/*rear－>next＝p；/*置最后一个结点的指针指向新结点*/

*rear＝p；/*改变队尾指针*/return；}106第2章基本数据结构及其运算带链队列的退队运算输入：带链队列的排头指针front。输出：退队后的带链队列排头指针front；存放退出结点值的变量y。

PROCEDUREDELLL(front，y)y=V(front)[取出排头元素值]

p＝frontfront＝NEXT(front)[改变排头指针]

DISPOSE(p)[释放删除的结点]

RETURN107第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/

structnode*next；

}；delll(front，y)ETy；

structnode**front；{structnode*p；

y＝*front－>d；/*取出排头元素值*/

p＝*front；*front＝p－>next；/*改变排头指针*/

free(p)；/*释放被删除结点*/

return；}108第2章基本数据结构及其运算2.3.2线性链表的基本运算(1)在线性链表中包含指定元素的结点之前插入一个新元素。(2)在线性链表中删除包含指定元素的结点。(3)将两个线性链表按要求合并成一个线性链表。(4)将一个线性链表按要求进行分解。(5)逆转线性链表。(6)复制线性链表。(7)线性链表的排序。(8)线性链表的查找。109第2章基本数据结构及其运算1.在线性链表中查找指定元素在非空线性链表中寻找包含元素x的前一个结点p输入：非空线性链表头指针HEAD；被寻找元素x。输出：非空线性链表中包含元素x的前一个结点p。PROCEDURELOOKST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠0)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN110第2章基本数据结构及其运算structnode/*定义结点类型*/{ETd；/*数据元素类型*/

structnode*next；

}；structnode*lookst(head，x)ETx；

structnode*head；{structnode*p；

p＝head；

while((p－>next!＝NULL)&&(((p－>next)－>d)!＝x))

p＝p－>next；

return(p)；}111第2章基本数据结构及其运算2.线性链表的插入在链式存储结构下的线性表中插入一个新元素。112第2章基本数据结构及其运算可利用栈与线性链表113第2章基本数据结构及其运算(1)从可利用栈取得一个结点，设该结点号为p。

并置结点p的数据域为插入的元素值b，即V(p)＝b。(2)在线性链表中寻找包含元素x的前一个结点q。114第2章基本数据结构及其运算(3)将结点p插入到结点q之后：①使结点p指向包含元素x的结点，即

NEXT(p)＝NEXT(q)②使结点q的指针域内容改为指向结点p，即

NEXT(q)＝p115第2章基本数据结构及其运算线性链表的插入输入：线性链表的头指针HEAD；插入位置处的前一个结点值x；插入的新元素b。输出：插入后的线性链表。PROCEDUREINSLST(HEAD，x，b)1.NEW(p)2.V(p)＝b3.IF(HEAD＝0)THEN{HEAD＝p；NEXT(p)＝0；RETURN}4.IF(V(HEAD)＝x)THEN{NEXT(p)＝HEAD；HEAD＝p；RETURN}5.LOOKST(HEAD，x，q)6.NEXT(p)＝NEXT(q)；NEXT(q)＝p7.RETURN116第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；inslst(head，x，b)ETx，b；structnode**head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置结点的数据域*/

if(*head＝＝NULL)/*链表为空*/{*head＝p；p－>next＝NULL；return；}if((*head－>d)＝＝x)/*在第一个结点前插入*/{p－>next＝*head；*head＝p；return；}q＝lookst(*head，x)；/*寻找包含元素x的前一个结点q*/p－>next＝q－>next；q－>next＝p；/*结点p插到结点q之后*/

return；}117第2章基本数据结构及其运算3.线性链表的删除在链式存储结构下的线性表中删除包含指定元素的结点。118第2章基本数据结构及其运算可利用栈与线性链表119第2章基本数据结构及其运算(1)寻找包含元素x的前一个结点q。则包含元素x的结点序号p＝NEXT(q)。(2)将结点q后的结点p删除，即

NEXT(q)＝NEXT(p)。120第2章基本数据结构及其运算(3)将包含元素x的结点p送回可利用栈。121第2章基本数据结构及其运算线性链表的删除输入：线性链表的头指针HEAD；需删除的元素x。输出：删除后的线性链表。PROCEDUREDELST(HEAD，x)1.IF(HEAD＝0)THEN{“Thisisaemptylist!”；RETURN}2.IF(V(HEAD)＝x)THEN{p＝NEXT(HEAD)；DISPOSE(HEAD)；HEAD＝p；RETURN}3.LOOKST(HEAD，x，q)4.IF(NEXT(q)＝0)THEN{“Nothisnodeinthelist!”；RETURN}5.p＝NEXT(q)；NEXT(q)＝NEXT(p)6.DISPOSE(p)7.RETURN122第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；delst(head，x)ETx；structnode**head；{structnode*p，*q；

if(*head＝＝NULL)/*链表为空*/{printf("Thisisaemptylist!\n")；return；}if((*head－>d)＝＝x)/*删除第一个结点*/{p＝*head－>next；free(*head)；*head＝p；return；}q＝lookst(*head，x)；/*寻找包含元素x的前一个结点q*/if(q－>next＝＝NULL)/*链表中没有包含元素x的结点*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*删除结点p*/free(p)；/*释放结点p*/return；}123第2章基本数据结构及其运算2.3.3循环链表(1)在循环链表中增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表第一个元素的结点。循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。124第2章基本数据结构及其运算(1)在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。(2)空表与非空表的运算统一。125第2章基本数据结构及其运算在头指针为HEAD的循环链表中寻找包含元素x的前一个结点输入：循环链表的头指针HEAD；被寻找的元素x。输出：循环链表中包含元素x的前一个结点p。PROCEDURELOOKCST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠HEAD)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN126第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；structnode*lookcst(head，x)ETx；

structnode*head；{structnode*p；

p＝head；

while((p－>next!＝head)&&(((p－>next)－>d)!＝x))p＝p－>next；

return(p)；}127第2章基本数据结构及其运算在头指针为HEAD的循环链表中包含元素x的结点前插入新元素b输入：循环链表的头指针HEAD；插入位置处的前一个结点值x；插入的新元素b。输出：插入后的循环链表。PROCEDUREINSCST(HEAD，x，b)NEW(p)[从可利用栈取得一个新结点p]V(p)＝b[置新结点p的数据域（插入的元素值b）]LOOKCST(HEAD，x，q)[寻找循环链表中包含元素x的前一个结点q]NEXT(p)＝NEXT(q)；NEXT(q)＝p

[将新结点p插入到结点q之后]RETURN128第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；inscst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置结点的数据域*/

q＝lookcst(head，x)；/*寻找包含元素x的前一个结点q*/p－>next＝q－>next；q－>next＝p；/*结点p插入到结点q后*/

return；}129第2章基本数据结构及其运算在头指针为HEAD的循环链表中删除包含元素x的结点输入：循环链表的头指针HEAD；需删除的元素x。输出：删除后的循环链表。PROCEDUREDELCST(HEAD，x)LOOKCST(HEAD，x，q)[寻找包含元素x的前一个结点q]IF(NEXT(q)＝HEAD)THEN[循环链表中没有该结点]

{“Nothisnodeinthelist!”；RETURN}p＝NEXT(q)；NEXT(q)＝NEXT(p)[删除结点q后的结点]DISPOSE(p)[将被删除的结点p送回可利用栈]RETURN130第2章基本数据结构及其运算#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；delcst(head，x)ETx；structnode*head；{structnode*p，*q；

q＝lookcst(head，x)；/*寻找包含元素x的前一个结点q*/if(q－>next＝＝NULL)/*链表中没有包含元素x的结点*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*删除结点p*/free(p)；/*释放结点p*/return；}131第2章基本数据结构及其运算2.4数组2.4.1数组的顺序存储结构2.4.2规则矩阵的压缩2.4.