计算机软件基础（MOOC版）课件汇 第1-7章 预备知识-排序

计算机软件基础BasicsofComputerSoftware课程内容预备知识1数据结构概述2线性表及其存储结构3树和二叉树45图的基本概念和应用6查找算法7排序算法8其他第一章预备知识BasicsofComputerSoftware目录C语言复习1常用算法2算法的基本概念3C语言复习PART1if-else语句的一般形式为：if(表达式)

语句1;

else

语句2;其中：语句1和语句2可以是空语句,一般语句2为空，就是不带else的语句例：将a和b按从小到大排列#include<stdio.h>intmain(){inta,b,t;printf("请输入2个数字：");scanf("%d%d",&a,&b);if(a>b){t=a;a=b;b=t;}printf("%5d%5d\n",a,b);}不带else的语句例：将a、b、c按从小到大排列（只写完成该功能的程序段）if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}if(b>c){t=b;b=c;c=t;}例：判断一个数字是奇数还是偶数。#include<stdio.h>intmain(){intx;printf("请输入一个数字：");scanf("%d",&x);if(x%2==0)printf("%d是偶数！\n",x);elseprintf("%d是奇数！\n",x);return0;}带else的语句多分支结构和else-if语句一般形式为：

if(表达式1)

语句1;

elseif(表达式2)

语句2；

…

elseif(表达式n-1)

语句n-1;

else

语句n；sign(x)符号函数其功能是取某个数的符号：当x>0，sign(x)=1;当x=0，sign(x)=0;当x<0，sign(x)=-1；sign(x)符号函数方法一：if(x>0)sign=1；if(x==0)sign=0；if(x<0)

sign=-1；方法二：if(x>0)sign=1elseif(x==0)sign=0elsesign=-1三种循环结构for循环：一般用在循环次数固定或已知的情况while循环：又称当型循环，用的较多do-while循环：又称直到型循环，尽量用while实现一般的循环程序都涉及循环变量，循环变量尽量和问题对应我们通过例子来复习猴子吃桃问题猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就又吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第10天在想吃的时候就剩一个桃子了,求第一天共摘下来多少个桃子？猴子吃桃问题设D1为前一天的桃子数，D2为后一天的桃子数，则根据吃桃过程有公式：

D2=D1—(D1/2＋1)=D1/2—1这是根据前一天算后一天，但我们现在是要根据后一天算前一天，∴有D1=(D2＋1)×2我们用C语言的赋值语句来替换上面的等式，有：D=(D＋1)×2等号右边的D代表后一天的个数，左边的D代表前一天的个数猴子吃桃问题int

main(){

int

i;

int

D=1;

for(i=9;i>=1;i--)

D=2*(D+1);

printf("%d\n",D);}循环变量i

和第几天对应小球落地问题h=100;s=h;for(i=2;i<=10;i++){s=s+h;h=h/2;}小球落地问题h=100;s=h;for(i=2;i<=10;i++){h=h/2;s=s+2*h;}水仙花数问题所谓水仙花就是指一个三位数，其各个位上的数字的立方之和正好等于该数字本身。例如：153=13+53+33,那么153就是水仙花数。我们可以用一个单循环来实现，也可以用一个三重循环来实现设这个三位数是：abc水仙花数问题（单循环）main(){inti=0,a,b,c;for(i=100;i<1000;i++){a=i/100;b=i/10%10;c=i%10;if((a*a*a+b*b*b+c*c*c)==i)

//满足水仙花条件printf("%d",i);}}水仙花数问题（多重循环）main(){inti=0,a,b,c;for(a=1;a<=9;a++)for(b=0;b<=9;b++)for(c=0;c<=9;c++){i=100*a+10*b+c;if((a*a*a+b*b*b+c*c*c)==i)

//满足水仙花条件printf("%d",i);}}编写一个求1到100和的程序段，结果放在sum变量中main(){intsum;sum=(1+100)*100/2；printf(“sum=%d”,sum);}用循环语句的方式，编写一个求1到100和的程序main(){inti,sum;sum=0;for(i=1;i<=100;i++)

sum=sum+i;printf(“sum=%d”,sum);}编写一个程序，实现输入100个数据求和main(){inti,sum,x;sum=0;for(i=1;i<=100;i++)

{scanf("%d",&x);

sum=sum+x;}printf(“sum=%d”,sum);}main(){inti,sum,x;sum=0;i=1while(i<=100){scanf("%d",&x);

sum=sum+x;i=i+1;}printf(“sum=%d”,sum);}编写一个程序，实现输入以0作为结束的任意个数据求和main(){inti,sum,x;sum=0;i=1while(i<=100){scanf("%d",&x);

sum=sum+x;i=i+1;}printf(“sum=%d”,sum);}这是上一个程序main(){intsum,x;sum=0;scanf("%d",&x);

while(x<>0){sum=sum+x;scanf("%d",&x);}printf(“sum=%d”,sum);}这个程序结构用的是最多的编写一个程序，实现输入一个班（设40人）的成绩，打印出高于平均分的成绩和人数main(){inti,sum,a[40],count=0;float:ave;sum=0;for(i=0;i<40;i++)

{scanf("%d",&a[i]);

sum=sum+a[i];}ave=sum/40;for(i=0;i<40;i++)

If(a[i]>ave){printf(“%d”,a[i]);

count++;}printf(“count=%d”,count);}输出如下图形**********printf(“*\n**\n***\n****”);scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=i;j++)

printf(“*”);printf(“\n”);}输入行数n，输出如下图形输入行数n，输出如下图形**********scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=?;j++)

printf(“*”);printf(“\n”);}ij14233241满足：i+j=5=n+1∴有：j=n+1-i；n+1-i输入行数n，输出如下图形**********scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=?;j++)

printf(“”);

for(j=1;j<=?;j++)

printf(“*”);printf(“\n”);}打印空格关系ij10213243每一行先打印空格，再打“*”打印“*”关系ij14233241i-1n+1-ij=i-1j=n+1-i输入行数n，输出如下图形**********scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=?;j++)

printf(“”);

for(j=1;j<=?;j++)

printf(“*”);printf(“\n”);}打印空格关系ij13223140每一行先打印空格，再打“*”打印“*”关系ij11223344n-iij=n-ij=i函数（过程和函数）max（a，b）main(){

intx,y,z;x=3;y=5;

z=max(x,y)}intmax(inta,b){if(a>b)returna;elsereturnb;}形参实参35mainmax35函数举例main(){

intx,y;x=3;y=5;

exchg(x,y);printf(“%5d%5d”,x,y);}exchg(inta,b){intt;t=a;a=b;b=t;}35mainexchg35运行结果：?a.35b.53√指针的概念指针就是地址对单元内容的访问有两种：1.直接访问：直接通过变量名访问x=20,y=1,z=155;2.间接访问：通过另一个变量访问把该变量的地址放到另一个变量中我们把存放地址的变量称为指针变量，例如变量p定义如下：Int

x,y,z;Int*p;直接访问：x=20,y=1,z=155;xyzp20115510001000100210042000P=&x；//指针变量赋值不能直接给指针变量赋常量间接访问：p=1000或p=20？*P=50；//通过针变量访问简单变量501155P=&x；&在这是取地址运算符，把x变量的地址赋给指针变量p&在双目运算中是位运算的按位与运算*P=50；*在这是p指针指向的变量（内存单元）的内容，在前面已经将p指向了变量x，最后实现的是将变量x（内存

1000单元）的内容设成50。设有定义：int

x,y;int*p;判断下列语句正确与否？X=y;p=&x;P=x;p=*x;X=5;x=*p;P=1000;x=&p√√√√××××例如：例如：voidmain(){inta,b,*p1,*p2,*p;a=3;b=6;p1=&a;p2=&b;63p1ap2bp运行结果：6，33，6p=p1;p1=p2;p2=p;printf(“%d,%d\n”,*p1,*p2);printf(“%d,%d\n”,a,b);}例如：voidmain(){inta,b,t，*p1,*p2;a=3;b=6;p1=&a;p2=&b;63p1ap2bt运行结果：6，36，363t=*p1;*p1=*p2;*p2=t;printf(“%d,%d\n”,*p1,*p2);printf(“%d,%d\n”,a,b);}例如：voidmain(){inta,b;a=3;b=6;exchg(a,b);printf(“%d,%d\n”,a,b);}exchg(intx,y){intt;t=x,x=y,y=t;}63ab运行结果：3，663mainexchg63txy例如：用指针实现交换voidmain(){inta,b;a=3;b=6;exchg(&a,&b);printf(“%d,%d\n”,a,b);}exchg(int*x,*y){intt;t=*x,*x=*y,*y=t;}63ab运行结果：6，363mainexchg&b&atxy指针和数组指向数组元素的指针（一维数组）inta[5],*p;p=a;或p=&a[0];//结果是一样的数组名本身就是数组的起始地址inta[5],*p=a;//和上面一样吗？指针和数组数组元素的引用inta[5]]={10,11,12,13,14},*p=a；下标法：通过a[i]来引用，如a[3]下列指令那些合法，什么含义p++；a++；p=a+2；a=a+2指针法：用*(a+i)、*(p+i)引用第i个元素1011121314指针和结构体结构体结构体是自定义类型，由多个类型不相同的分量组成，定义如下：structstud{longnum;charname[20];chargender;intage;floatscore;}s1;numnamegenderagescore类型名为stud的结构体18020101张三男9520numnamegenderagescore变量名为s1的结构体变量指针和结构体结构体structstud{longnum;charname[20];chargender;intage;floatscore;}s1;18020101张三男9520numnamegenderagescore变量名为s1的结构体变量s1.num=18020101strcpy(,“张三”);s1.gender=‘M’;s1.age=20;s1.score=95;s1指向结构体的指针structstud{longnum;charname[20];chargender;intage;floatscore;}s1，*p；18020101张三男9520numnamegenderagescore变量名为s1的结构体变量同理：strcpy(p->name,“张三”);p->gender=‘M’;p->age=20;p->score=95;s1p指针变量Pp=&s1;//这个必须要则(*p).num=18020201;可表示为:p->num=18020201;链表headacdefg^b存储地址数据域指针域1f137e113gnull19b3725d731a1937c25头指针31每个元素由结点(Node)构成，它包括两个域:数据域（Data）和指针域（next）存储结构：链式存储结构特点：存储单元可以不连续。Nodedatanext单链表的类型定义typedefintListData;//定义数据类型typedefstructnode//链表结点

{

ListDatadata; //结点数据域

structnode*next;//结点链域}ListNode;TypedefListNode*LinkList;//链表头指针LinkListhead，p，q;//链表头指针ListNode*head，*p，*q;NodedatanextListNode是类型名

9

5

2

head

单链表的引用P

p->data;//得到2p->next;//2和5之间的指针p->next->data;//得到5p->next->next->data;//得到9q->next=nil;//最后一个指针分量置空p=p->next;//指针后移一个节点q

单链表的插入操作（三种情况）第一种情况：在第一个结点前插入newnodeheadabc^Newnode->next=p->next;p->next=newnode;P第二种情况：在链表中间插入newnodeheadabc^Newnode->next=p->next;p->next=newnode;P第三种情况：在链表尾部插入newnodeheadabcNewnode->next=p->next;p->next=newnode;^^PNewnode->next=p->next;p->next=newnode;注意，在这三种情况中，插入操作均是：单链表的删除操作

headabe^Pcdq（删除P结点之后的结点）q=p->next;p->next=q->next;free(q);编程：实现输出以head为头节点的单链表中所有结点的程序段output(head);{p=head->next；

//让移动指针指向第一个结点while(p!=nil){printf(“%5d”,p->data);p=p->next;//指针后移}}常用算法PART2算法设计基本方法—常用算法一.枚举法

枚举法是利用计算机运行速度快、精度高的特点，对要解决问题的所有可能情况，一个不落的进行检测，从中找出符合要求的答案。

枚举法通过牺牲时间来换取答案的全面性。算法设计基本方法—枚举法百钱买百鸡问题中国古代数学家张丘建在《算经》中提出：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？百元买百鸡——枚举法方法1：voidbqbj(){intCock,Hen,Chicken;for(Cock=0;Cock<20;Cock++)for(Hen=0;Hen<34;Hen++)for(Chicken=0;Chicken<100;Chicken++)if((Cock+Hen+Chicken==100)&&(Cock*5+Hen*3+Chicken/3==100)&&(Chicken%3==0))printf("Cock=%dHen=%dChicken=%d\n",Cock,Hen,Chicken);}循环次数68000次百元买百鸡——枚举法方法2：voidbqbj(){intCock,Hen,Chicken;for(Cock=0;Cock<20;Cock++)for(Hen=0;Hen<34;Hen++){Chicken=100-Cock-Hen;if((Cock*5+Hen*3+Chicken/3==100)&&(Chicken%3==0))printf("Cock=%dHen=%dChicken=%d\n",Cock,Hen,Chicken);}}循环次数680次百元买百鸡——枚举法方法3：voidbqbj(){intCock,Hen,Chicken;for(Cock=0;Cock<20;Cock++)for(Hen=0;Hen<(100-Cock*5)/3;Hen++){Chicken=100-Cock-Hen;if((Cock*5+Hen*3+Chicken/3==100)&&(Chicken%3==0))printf("Cock=%dHen=%dChicken=%d\n",Cock,Hen,Chicken);

}}循环次数少于680次二、归纳法找规律在复习C语言时举的例子基本都是找规律三、递推法

递推算法是通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。例1：阶乘函数n！=1*2*3*…*n即：n！=（n-1）！*n即：2！=1！*2，3！=2！*3,……例1：阶乘函数IntFact(n){intt=1,i;for(i=1;i<=n;i++)t=t*i;returnt;}三、递推法四、递归法myfunc(参数){：

：myfunc(参数);::}四、递归法例1：阶乘函数intfact(n){if(n==1)return1;elsereturnn*fact(n-1);}四、递归法例2：hano塔四、递归法例2：hano塔算法描述：如果n=1

直接将n号盘从a搬到c否则做如下操作

将a上的n-1张盘从a搬到b；直接将n号盘从a搬到c；将b上的n-1张盘从b搬到c；说明：一张盘时直接搬到目的地

多张盘时调用自己基本思路：首先将n张盘看成由2部分组成：第一部分是最大的盘n号盘，然后把剩余的n-1张盘看成另外一个整体，称n-1张盘，这样其移动过程就和2张盘的移动过程相同，如右上角。注意，这里的n-1张盘是多张盘组成的，n号盘只有1张盘。voidHanoi(intn,a,b,c){if(n==1)move(n,a,c);//一张盘片else{Hanoi(n-1,a,c,b);

//多张盘片move(n,a,c);//一张盘片

Hanoi(n-1,b,a,c);

//多张盘片}}voidmove(intn,a,c){printf(“将%d号盘从%d搬到%d\n”,n,a,c);}五、分治法例：折半查找——查字典例如:在有序表中查找key=21的查找过程六、迭代法例：求X2-X-1=0在x=1.5附近的一个根X=(x+1)0.5所以，X=(1.5+1)0.5=1.58113883

X=(1.58113883+1)0.5=1.606592304

X=(1.606592304+1)0.5=1.614494442

X=(1.614494442+1)0.5=1.616939839

X=(1.616939839+1)0.5=1.617695842

X=(1.617695842+1)0.5=1.617929492

X=(1.617929492+1)0.5=1.618001697

X=(1.618001697+1)0.5=1.61802401七、回溯法（高级算法）—八皇后问题

有八个皇后（可以当成八个棋子），如何在8*8的棋盘中放置八个皇后，使得任意两个皇后都不在同一条横线、纵线或者斜线上。七、回溯法（高级算法）—八皇后问题算法的解决思路是：1从棋盘的第一行开始，从第一个位置开始，依次判断当前位置是否能够放置皇后，判断的依据为：同该行之前的所有行中皇后的所在位置进行比较，如果在同一列，或者在同一条斜线上,都不符合要求，继续检验后序的位置。2如果该行所有位置都不符合要求,则回

溯到前一行,改变皇后的位置,继续试探。3.如果试探到最后一行，所有皇后摆放

完毕,则直接打印出8*8的棋盘。七、回溯法（高级算法）—八皇后问题1.1.6算法的复杂度分析一.算法的后期在算法中的某些部位插装时间函数time

(),

测定算法完成某一功能所花费时间

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf(“%d%d\n”,n,runTime);二.算法的事前估计1.空间复杂度度量（1）存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间（2）可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间2.时间复杂度度量运行时间=算法中每条语句执行时间之和。每条语句执行时间=该语句的执行次数（频度）*语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。算法的基本概念PART31.1.1算法的四个基本特征：1.有穷性：

一个算法必须在执行有穷步之后结束2.确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。3.可行性：

算法每一步都是能够实现的，即可操作的。4.有输出：算法执行完毕，必须有一个或若干个输出结果。1.1.2评价算法：正确性：对于一切合法输入都能产生满足规格要求的结果易读性：算法要便于阅读，有助于人们对算法的理解健壮性：当输入非法数据时，也能正常作出反应和处理效率和低存储量需求：对相同规模的问题，运行时间短、占用空间少

1.1算法的基本概念1.1算法的基本概念1.1.3算法的基本要素1、对数据的运算和操作 如：插入、删除2、算法的控制结构 如用流程图和N-S图表示1.1.4算法描述语言采用类C语言来描述一、符号与表达式二、赋值语句三、控制转移语句 如：go,if等语句四、循环五、其他语句：exit、ruturn、如:ab本次课程结束，谢谢大家的观看！常州工学院主讲人：黄文生BasicsofComputerSoftware第二章数据结构概述BasicsofComputerSoftware基本概念

逻辑结构物理结构数据操作目录数据结构的基本概念1数据的逻辑结构2数据的物理结构3数据操作41.无序表和有序表的查找有序表的查找无序表的查找基本概念

逻辑结构物理结构数据操作问题引入结论01数据的组织结构和算法是密切相关的2.学生成绩表成绩表我们可以采用链表，数组，树形结构，甚至可以用图型结构进行表示和存储，但相应的各种操作算法也不同基本概念

逻辑结构物理结构数据操作问题引入结论：数据结构和算法是相互依赖的关系：基本概念

逻辑结构物理结构数据操作问题引入02算法要作用在特定的数据结构之上算法要结合数据存储的特点，用最优的策略来分析并处理数据。01数据结构是为算法服务的数据结构要配合算法选择最优的存储结构来存储数据。队列可以用线性链表描述家谱可以用树描述交通网可以用图或者网络来描述基本概念

逻辑结构物理结构数据操作什么是数据结构基本概念

逻辑结构物理结构数据操作什么是数据结构描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构数据结构是一门研究数据组织、存储和运算的一般方法的学科因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现学习数据结构知识有助于编制高质量的计算机应用程序数据结构（DataStructure）形式定义：数学上的抽象的定义

某一数据对象的所有数据成员之间的关系。记为：

Data_Structure={D,S}其中，D是某一数据对象S是该对象中所有数据成员之间的关系的有限集合如：线性表（2，5，7，9）中可以写成：D={2，5，7，9}S={(2,5),(5,7),(7,9)}基本概念

逻辑结构物理结构数据操作什么是数据结构数据(Data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据基本概念

逻辑结构物理结构数据操作基本概念和术语数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。数据元素又称为元素、结点、记录一个数据元素往往可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素（DataElement）基本概念

逻辑结构物理结构数据操作基本概念和术语数据项(DataItem)

姓名部门名称出生日期入职时间职位业绩年月日基本概念

逻辑结构物理结构数据操作基本概念和术语数据对象(dataobject)具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象

C={‘A’,‘B’,‘C’,…‘F’}基本概念

逻辑结构物理结构数据操作基本概念和术语从逻辑关系上描述数据，与数据的存储方式无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关与数据元素的相对位置无关基本概念逻辑结构物理结构数据操作数据的逻辑结构四个基本结构树形结构（一对多）线性结构（一对一）集合（松散结构）图形结构（多对多）基本概念逻辑结构物理结构数据操作数据的逻辑结构基本概念逻辑结构物理结构数据操作数据的逻辑结构02非线性结构树和图（网络）01线性结构逻辑结构的分类bindevetclibuser线性结构基本概念逻辑结构物理结构数据操作数据的逻辑结构102114131211234678955一般的树987456231二叉树3158710119613二叉排序树堆结构123548711102916非线性结构：树型结构基本概念逻辑结构物理结构数据操作数据的逻辑结构125643125436113318146651921图结构网络结构ABECF非线性结构：图型结构基本概念逻辑结构物理结构数据操作数据的逻辑结构数据的存储结构：又称物理结构，指数据结构在计算机中的表示，依赖于计算机语言基本概念逻辑结构物理结构数据操作数据的物理结构增加一个或多个指针，用于存放和该数据元素有关的另一个数据元素的地址，可以不占用连续地址空间。链接存储表示是一种在数据元素的关键码与存储位置之间建立确定对应关系的查找技术。散列存储表示将逻辑上相邻的数据元素存放在内存中的相邻位置中顺序存储表示指除建立存储结点信息外，还建立附加的索引表来标识结点的地址索引存储表示基本概念逻辑结构物理结构数据操作数据的操作构造一个空结构初始化在数据结构中插入一个新元素插入在数据结构中删除满足指定要求的元素删除在数据结构中修改原有的数据元素修改在数据结构中查找指定要求的元素查找将数据按某一关键字排序排序数据操作数据结构的研究内容基本概念逻辑结构物理结构数据操作本章小结数据的逻辑结构数据的存储结构数据的运算1数据的逻辑结构按照某种逻辑关系将数据组织好，即逻辑结构2数据的存储结构将数据及数据之间的关系存储到存储区域中，即存储结构3数据的运算在这些数据上定义一个基本运算的集合反映数据元素之间的逻辑关系1.数据的逻辑结构2.数据的存储结构A.线性结构B.非线性结构A.顺序存储B.链式存储C.散列结构D.索引结构线性表栈队列树形结构图形结构数据结构的研究内容数据元素在计算机内部的组织方式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

h