计算机软件基础

计算机软件基础学时安排授课34+上机22章内容学时章内容学时1绪论27树和二叉树82线性表68图23堆栈和队列49排序44串10查找45数组211文件6递归算法复习2数学软件硬件数据结构课程的地位是介于数学、计算机硬件和计算机软件三者之间的一门核心课程第一章绪论1.1

数据结构的基本概念1.2数据结构研究的内容和方法1.4*C语言相关内容复习1.3算法和算法分析1.1

数据结构的基本概念为什么学习数据结构数值计算数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算数据元素之间的相互关系一般无法用数学方程加以描述数据描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。

数据元素

表示一个事物的一组数据，是数据的基本单位，又称结点。在计算机程序中通常作为一个整体进行处理。一个数据元素由若干数据项构成。数据结构数据元素之间具有的关系，即数据的组织形式。数据对象具有相同性质的数据元素组成的集合。基本概念表结构学号姓名性别籍贯出生年月住址06048001赵玲女上海1987.10上海06048002杨扬男北京1987.3北京………………………………学籍登记表交通图乌鲁木齐兰州西安呼和浩特北京郑州成都18921145668676695511842图结构

非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构课程研究的是计算机所处理的数据元素间的结构关系及其操作实现的算法

1.

研究数据元素之间的客观联系。

2.

研究具有某种逻辑关系的数据在计算机存储器内的存储方式。

3.研究如何在数据的各种结构(逻辑的和物理的)

的基础上对数据实施一系列有效的基本操作。

逻辑结构存储结构1.2数据结构研究的内容算法数据结构：

计算机处理的数据元素的组织形式及其相互间的关系。由数据元素的有限集合及所有数据元素之间的关系组成。记为：

Data_Structure={D,R}

其中，D是数据元素的有限集，R是所有数据元素之间的关系的有限集合。

根据数据元素间关系的基本特性，有四种基本数据结构集合结构

数据元素间除“同属于一个集合”外，无其它关系线性结构

一个对一个，如线性表、栈、队列树形结构

一个对多个，如树图状结构

多个对多个，如图集合结构数据结构:

SET=（K,R）

K={01,02,03,04,05,06,07,08,09,10} R={}08010305020704060910集合结构示意图线性结构数据结构

LINEARITY=（K,R）

K={01,02,03,04,05,06,07,08,09,10}R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,09>,<09,10>}05010308020704060910线性结构示意图数据元素之间的联系：1:1树结构数据结构

TREE=（K,R）

K={01,02,03,04,05,06,07,08,09,10}R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>,<04,10>}01020304070809050610树结构示意图数据之间的联系：1：NGraph=(D,R)D={1,2,3,4,5,6,7,8,9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}图结构数据之间的联系：M：N存储结构（StorageStructure):数据在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。四种基本的存储方法：（1）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。数据的逻辑结构数据的存储结构数据的运算

线性结构

非线性结构

顺序存储

链式存储线性表堆栈队列树形结构图形结构数据结构的三个方面：

散列存储索引存储串及数组查找、排序、插入、删除、修改等1.3算法和算法分析1.算法的定义(1).

算法是用来解决某个特定问题的指令的集合。(2).

算法是由人们组织起来准备加以实施的一系列有限的基本步骤。2.算法的描述文字形式程序设计语言形式（如C语言等）伪码形式3.算法的性质

一个完整的算法应该满足下面五个基本标准：输入性

有0个或多个输入输出性有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束；整个指令序列在有限的时间内完成。可行性（有效性）算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。例如：被零除的计算动作是不能被有效执行的。4.算法设计目标正确性可读性健壮性高时间效率高空间效率当时间效率目标和空间效率目标发生矛盾时，应先考虑时间效率目标5.算法分析时间复杂度T（n）空间复杂度S（n）其它（如可读性、可移植性等）前提条件：算法必须正确

2.源程序编译的强弱以及所产生的机器代码质量的优劣。3.机器执行一条指令的时间长短。4.程序中语句的执行次数。1.问题的规模。

一个程序在计算机中运行时间的多少与诸多因素有关，其中主要有：4.时间复杂度称为时间频度，记为T（n）

定义：若有一辅助函数f(n)，当n趋于无穷大时，T(n)/f(n)为一不等于零的实常数，则f(n)为T(n)的同数量级函数，记为

T(n)=O(f(n))

称O(f(n))为时间复杂度。

例：3n+2=O(n)/*3n+24nforn2*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n) /*6*2n+n27*2nforn4*/常用的计算规则：1.加法规则

T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))

=O(max(f1(n),f2(n)))

2.乘法规则

T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))

时间复杂度T(n)按数量级递增顺序为：

注

空间复杂度S(n)按数量级递增顺序也与上表类同。复杂度高复杂度低时间复杂度的计算：例1：{++x;s=0;}2O(1)for(i=1;i<=n;++i){++x;s+=x;}n+2nO(n)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}2n+2n2O(n2)例2：例3：频度时间复杂度程序例4：频度时间复杂度程序x=n;//n>1while(x>=(y+1)*(y+1))y++;n1/2-1O(n1/2)例5：x=91;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;常数O(1)例6：频度时间复杂度程序O(n3)int

i,j,k,x=0;for(i=1;i<=n;i++)

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

for(k=1;k<=j;k++)x=x+2;按增长率由小至大的顺序排列下列各函数：

2100,(3/2)n,(2/3)n,nn,n0.5,n!,2n,lgn,nlgn,n3/2

思路：先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n3/2

指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn(2/3)n<2100<lgn<n0.5<n3/2<nlgn<(3/2)n<2n<n!<nn

1、数据结构是指计算机处理的①的组织形式以及它们相互之间的②。①A.数据元素B.计算方法

C.逻辑存储D.数据映像②A.结构B.关系

C.运算D.算法课堂练习3、衡量算法好坏的两个主要指标有算法的

和

。时间复杂度空间复杂度2、数据结构研究数据的

、

和操作实现算法。

A.结构关系、组织形式

B.逻辑结构、物理结构

C.数据元素、数据对象

D.数据复杂性、程序复杂性4、下面程序段的时间复杂度是

。

i=s=0;while(s<n){i++;s+=i;}O(n)5、算法的时间复杂度仅与问题的规模有关。

（）×*还与输入的元素取值有关6、下面程序段A[i][j]=0执行次数为

,

时间复杂度为

。

for(i=1;i<=n;i++)for(j=1;j<=i;j++)A[i][j]=0;n(n+1)/2O(n2)

理解：数据，数据元素，数据项，数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。

掌握：算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，对一般算法要能分析出时间复杂度。作业：P251-1，1-2，1－3，

1－7，1-11小结END复习：C语言的数据类型1、基本数据类型intshort;long;unsignedfloatfloat;double;longdouble2、指针类型10003i_pointeri地址（i的指针）指针变量1000*i_pointeri1000

15i=3;

3inti;指针变量的定义

inti;

int*i_pointer;i_pointer=&i;i=3;*i_pointer=3;5main(){intx=5;

printf(“\n%d”,x);Function1(x);

printf(“\n%d”,x)}voidFunction1(intx){x++;

printf(“\n%d”,x);}main(){intx=5;

printf(“\n%d”,x);Function1(&x);

printf(“\n%d”,x)}voidFunction1(int*px){(*px)++;

printf(“\n%d”,*px);}值传送地址传送x5x6x51000px1000*px63.数组类型数组名就是数组的起始地址数组作为函数参数时，为地址传递inta[100];a&a[0],a+1&a[1]……*aa[0],*(a+1)a[1]……4、字符串

字符串定义成字符数组‘\0’为字符串结束标志chara[40]=“Iamastudent”;strlen(a)为14不包括‘\0’5.结构体类型结构体由若干个结构体成员组成。定义结构体类型变量：1.定义结构体类型；2.定义结构体类型变量。structstudent{charname[10];

intage;floatscore;};structstudentstudent1;structstudentstu2[100];structstudent*p;6.

自定义类型typedefcharelemtype;typedef

structstudent{charname[10];

intage;floatscore;}stu;elemtypea;stustudent1;

数据项具有独立含义的最小标识单位,是数据的最小单位数据元素数据项学号姓名性别籍贯出生年月住址06048001赵玲女上海1987.10上海06048002杨扬男北京1987.3北京………………………………逻辑结构a1a2a3

a30…d1d2d3d4

…d30a2a1a3a4a30存储结构1.顺序存储结构线性结构（线性表）刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………

姓名性别民族年龄其他

例2.链式存储结构…d1d2d3d4

a1a2a3a30∧list…a2a1a4a3d4d1d5d3百钱买百鸡问题:100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？

for(i=0;i<=100;i++)for(j=0;j<=100;j++) for(k=0;k<=100;k++) {if(k%3==0&&(i+j+k)==100&&(5*i+3*j+k/3)==100)

printf(“%d,%d,%d\n”,i,j,k);}求解：设母鸡、公鸡、小鸡各为i,j,k只，则有：

i+j+k=100 5i+3j+k/3=100

只需要解出本方程就可以得到答案。方法1：用三重循环方法2、3：用两重循环因总共买100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。

for(i=0;i<100;i++)for(j=0;j<100;j++){

k=100-i-j;if(k%3==0&&(5*i+3*j+k/3)==100)

printf(“%d,%d,%d\n”,i,j,k);}for(i=0;i<=20;i++)for(j=0;j<33;j++){

k=100-i-j;if(k%3==0&&(5*i+3*j+k/3)==100)

printf(“%d,%d,%d\n”,i,j,k);}

方法4：用一重循环由i+j+k=100和5*i+3*j+k/3=100合并为一个方程： 14*i+8*j=200,

简化:7*i+4*j=100

得:i不超过14，i必为4的倍数？!

for(i=0;i<=14;i+=4){

j=(100-7*i)/4;k=100-i-j;

printf(“%d,%d,%d\n”,i,j,k);}上面四个方法中， 第一个方法的循环次数为：100*100*100,一百万次；第二个方法的循环次数为：100*100，1万次；第三个方法为：20*34，680次;

第四个方法为：4次.由此可见，算法的设计至关重要。BACK第二章线性表Chapter2LinearList数据结构课程——涉及数学、计算机硬件和计算机软件数据结构定义——指互相有关联的数据元素的集合，用D_S=(D,R)或S=(D,R)表示。数据结构内容——数据的逻辑结构、存储结构和运算

算法效率指标——时间效率和空间效率要点回顾

数据的逻辑结构

数据的存储结构

数据的运算

线性结构

非线性结构

顺序存储

链式存储线性表、栈、队列、串、数组树形结构图形结构

散列存储索引存储插入、删除、修改、查找、排序等逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构（单链表）应用实例本章内容

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a0,a1,……,an-1）

线性结构的定义：线性结构的特点：①只有一个首结点和一个尾结点；②

除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型最常用的是------（a0,a1…ai-1，ai,ai＋1

，…,an-1）2.1线性表的逻辑结构

1.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点（首结点）ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置空表线性终点（尾结点）n为元素总个数，即表长例1分析26个英文字母组成的英文表

（A,B,C,D,……,Z）学号姓名性别年龄班级06048001于春梅女18微电06106048002何仕鹏男18微电06106048003王爽女18微电06106048004王亚武男18微电061：：：：：例2分析学生情况登记表每个数据元素由5个数据项组成;元素之间的关系是线性的数据元素都是字母;元素之间的关系是线性的同一线性表中的元素必定具有相同特性2.线性表的基本操作Initiate(L)

初始化操作。建立一个空线性表L。Length(L)

求表长。求给定线性表L中数据元素的个数。Get(L,i)

读取元素。读取线性表L中第i个数据元素。Insert(L,i,x)前插。在线性表L中第i个数据元素

ai之前插入一个新的数据元素x。Delete(L,i)删除。删除线性表L中第i个的数据元素ai。Locate(L,x)

定位函数。返回线性表L中元素值等于x的数据元素ai的序号i。2.2线性表的顺序存储结构—顺序表

一、顺序表

用一组地址连续的存储单元存储线性表的各个数据元素，称作线性表的顺序存储结构，简称顺序表。

顺序表的特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.

若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标，参见存储结构示意图）。逻辑地址数据元素存储地址数据元素0a0Loc(a0)a01a1Loc(a0)+Ka1…………iaiLoc(a0)+i*Kai……n-1an-1Loc(a0)+(n-1)*Kan-1线性表的顺序存储结构示意图首地址每个元素占K字节一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是

113例1：因此：LOC(M[3])=98+5×3=113解：地址计算通式为：LOC(ai)=LOC(a0)+L*i用c语言定义顺序表#defineMaxlen100typedef

struct{charname[10];charsex;

intage;}elemtype;elemtype

List[Maxlen];intnum=-1;/*定义数据类型*//*定义顺序表*//*当前数据元素下标*//*顺序表最大长度*/姓名性别年龄张三M18李四F19………………typedef

struct{elemtype

List[Maxlen];

intnum;}SeqList;ss->nums->List[0]s->List[1]s->List[2]…s->List[Maxlen-1]SeqLista;SeqList*s;a.num，a.List[0]……numList[0]List[1]…用c语言定义顺序表二、顺序表的基本操作1.初始化ListInitiate(L)voidListInitiate(SeqList*L){L->num=-1;}/*num指示线性表最后一个元素的下标*/2.求表长ListLength(L)int

ListLength(SeqListL){returnL.num+1;}3.取数据元素ListGet(L，i，x)int

ListGet(SeqList

L,int

i,elemtype*x){if(i<0||i>L.num){printf(“ERROR!\n”);return0;}else{*x=L.List[i];return1;}}…Maxlen-1a0a1…ai-1aiai+1an-1…01…i-1ii+1n-1…a0a1…ai-101…i-1iMaxlen-1…ai+1an-1…aii+1…i+2na0a1…ai-1aiai+1an-1…Maxlen-101…i-1ii+1…i+2…nx4.插入（在第i个（0<=i<=n）数据元素之前插入一个新的数据元素x）i位置非法？开始表满？n-1至i位置的元素依次后移将元素x存放在i位置表长加1结束i非法表满NYNY前插算法流程图是否满足0≤i≤num+1num≤

Maxlen-1是否成立for(j=num;j>=i;j--)a[j+1]=a[j];

a[i]=x;

num++;注意：n表示数据元素的个数,num是线性表最后一个元素的下标增强健壮性int

ListInsert(SeqList*L,inti,elemtypex){intj;

if(i<0||i>L->num+1){printf(“error\n”);return0;}if(L->num)>=Maxlen-1){printf(“overflow\n”);return0;}for(j=L->num;j>=i;j--)L->list[j+1]＝L->List[j];L->List[i]＝x;L->num＝L->num+1;return1;}判断i是否合法判断表是否已满若i合法，元素后移将元素x存放在i位置当前数据元素下标加1用c语言描述插入算法该算法的时间复杂度：Eis:

插入一个元素所需平均移动次数:

则

因此,该算法的时间复杂度为O(n)。a0a1…ai-101…i-1iai5.删除（删除第i个（0<=i<=n-1）数据元素）…Maxlen-1a0a1…ai-1aiai+1an-1…01…i-1ii+1n-1…Maxlen-1…ai+1ai+2an-1…i+1n-2…iaix删除算法流程图位置非法？开始i+1至n-1位置的元素依次前移表长减1结束i非法NY表空？表空Yfor(j=i+1;j<=num;j++)a[j-1]=a[j];num--;判断num<0是否成立是否满足0≤i≤

numN用c语言描述删除算法int

ListDelete(SeqList*L,inti,elemtype*x){intj;if(L->num<0){printf(“\nThelistisempty!”);return0;}elseif(i<0||i>L->num){printf(“\nthepositionisinvalid”);return0;}else{*x=L->list[i];for(j=i+1;j<=L->num;j++)L->list[j-1]=L->list[j];L->num--;return1;}}/*删除顺序表L中的第i个元素,并将其保存在x中*//*判断表是否为空*//*若i合法，元素依次前移*//*当前数据元素下标减1*//*判断i值是否合法*/该算法的时间复杂度：Edl：删除一个元素所需平均移动次数

因此,该算法的时间复杂度为O(n)。算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O

(移动元素次数)移动元素的个数取决于插入或删除元素的位置.顺序表时间效率分析:顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）顺序表空间效率分析:三、顺序存储结构的特点顺序表的优点：无需为表示节点间的逻辑关系而增加额外的存储空间可以方便地随机存取表中的任一节点顺序表的缺点：插入和删除运算不方便,需要移动大量的数据元素。由于要求占用连续的存储空间，存储分配只能预先进行作业：P552-82-14(顺序表)如何克服顺序表的这些缺点呢？第二章线性表线性结构的特点：仅有一个首、尾结点，其余元素仅有一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或1:1存储结构：顺序存储、链式存储3.顺序表特征：逻辑上相邻，物理上一定相邻优点：随机查找快缺点：插入、删除慢；

需要预先知道线性表的长度

单链表基本概念单链表基本操作

线性表的链式存储结构—链表循环单链表双向链表单链表初始化插入删除求元素个数取元素单链表的基本概念线性表链式存储结构的一种。用一组不一定连续的存储单元来存放数据元素。

数据域指针域结点头指针空指针130Aheada01475130Aa110CB1475a2^10CB

数据元素的逻辑顺序是通过链表中的指针连接次序来实现的。

结点datanext数据域指针域typedef

structNode{DataTypedata;

structNode*next;}SLNode；单链表结点的定义：

2.3.1单链表的存储结构Loc(a1)Loc(a2)…Loc(an-1)Loc(a0)第2个学生信息第3个学生信息…最后一个学生信息第1个学生信息逻辑示意图第2个学生信息Loc(a2)第3个学生信息Loc(a3)……第n个学生信息结束标志第1个学生信息Loc(a1)物理示意图第n个学生信息NULL第1个学生信息Loc(a2)第2个学生信息Loc(a3)head

链表结构示意图……带头结点的单链表12EFhead130A12EFa01475130Aa110CB1475a2^10CB带头结点的空单链表

^headhead->next==NULL不带头结点的单链表130Aheada01475130Aa110CB1475a2^10CB不带头结点的空单链表^headhead==NULL头指针头结点首元结点何谓头指针、头结点和首元结点？头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a0的结点。

头指针头结点首元结点a0一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②HZHAOQIANLISUNZHOUWUZHENG/\WANG区别：①

无头结点②

有头结点

相关知识动态内存分配设计人员根据具体问题的具体需要，在程序运行时再具体确定数组的个数或占用内存单元的大小，从而在程序运行时具体确定所需要的内存单元空间。malloc()函数free()函数头文件malloc.h#include<malloc.h>malloc()函数free()函数函数原型：

void*malloc(unsignedsize)函数功能：用于向系统动态申请size个字节的内存单元空间，函数返回值为所申请的内存空间首地址。函数原型：

voidfree(void*p)函数功能：用于释放动态分配的内存空间。sizeof

运算符：sizeof(已定义的数据类型)功能：返回括号中给出的已定义数据类型占用的字节个数。MemoryAllocation如：sizeof(int)例如：定义结构体类型

typedef

struct

nodetype{intdata;

struct

nodetype*next;}SLNode;p=(SLNode*)malloc(sizeof(SLNode));SLNode*p;p=malloc(sizeof(SLNode));强制类型转换（1）指针后移操作

p=p->next130Apa11475130Aa216001475…1475（2）指向指针的指针

SLNode**h;130A*ha11475130A**h1000h1000一级指针二级指针int

ListInitiate(SLNode**head){if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}（1）初始化2.3.2单链表的操作实现12EFhead*headNULLmain(){SLNode*h;ListInitiate(&h);}头结点12EF(2)求当前数据元素个数int

ListLength(SLNode*head){SLNode*p=head;

intsize=0;while(p->next!=NULL){p=p->next;size++;}returnsize;}12EFhead130A12EFa01475130Aan-110CB1800…12EFpsize=0130Apsize=11800psize=n(3)取元素（寻找到第i个结点ai并返回该结点的数据元素）12EFhead130A12EFa01475130Aai10CB1800an-1^1700…ai+1150010CB…1800p130Ap12EFp{p=p->next;j++;}while(p->next!=NULL&&j<i)*x=p->data;int

ListGet(SLNode*head,int

i,DataType*x){SLNode*p;

intj=0;p＝head;while((p->next!=NULL)&&(j<i)){p＝p->next;j++;}if(j!=i){printf(“取元素位置参数错！”);return0;}*x=p->data;return1;}/*找第i个结点*//*判断是否找到该结点*//*将数据元素值赋给*x*/

xP(1)步骤:（1）找插入位置，指针p指向ai的前一个结点

（2）插入：1、x结点指针域指向ai结点

2、ai-1结点的指针域指向x结点

(2)(2.1)(2.2)（4）插入运算（前插，即在ai之前插入一个数据元素x）sheada0ai-1ai…an-1

不可以！（2.1）和（2.2）可不可以交换？为什么？heada0ai-1ai…an-1

P(1)

xs

x？an-1^1700{p=p->next;j++;}while(p->next!=NULL&&j<i-1)1614x1614sp->next=s;12EFhead130A12EFa01475130Aai-110CB1800…ai150010CB…161410CBs->next=p->next;s->data=x;s=(SLNode*)malloc(sizeof(SLNode));12EFpj=-1130Apj=01800pj=i-1int

ListInsert(SLNode*head,inti,DataTypex){SLNode*p,*s;

intj;p=head;j=-1;

while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}用c语言实现的单链表插入算法定义变量并初始化搜索表，寻找ai-1结点if(j!=i-1){printf(“\n插入位置不合理！”);return0;}if((s=(SLNode*)

malloc(sizeof(SLNode)))==NULL)return0;s->data=x;s->next=p->next;p->next=s;return1;}插入位置不合理判断是否申请到新结点将该结点插入到ai结点之前（5）单链表的删除（删除第i(i>=0)个结点）130A12EFa01475130Aai-110CB1800ai150010CB1800pai+11600150010CBs12EFhead………1500s=p->next;p->next=s->next;free(s);{p=p->next;j++;}while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)ListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;

intj;p=head;j=0;while(p->next!=NULL&&p->next->next!=0&&j<i-1){p=p->next;j++;}

用c语言实现的单链表删除算法定义变量并初始化搜索表，寻找ai-1结点if(j!=i-1){printf(“\n

删除位置不合理!”);return0;}s=p->next;*x=s->data;p->next=p->next->next;free(s);return1;}删除位置不合理将ai结点删除释放s结点空间关于上机的相关说明1、实验报告不得有雷同，否则按不及格处理；2、函数自己编写，函数名、变量名等自己定义；#include<stdio.h>#defineMAXLEN100typedef

int

datatype;typedef

struct{

datatype

List[MAXLEN];

intnum;}Seqlist;函数声明voidmain(){变量定义

printf(“选择所要进行的操作：1:初始化\n2:插入\n3:删除\n4:输出\n5:退出\n“)；

scanf(%d”,&sel);

switch(sel){case1:调用初始化函数;break;case2:调用插入函数;break;case3:调用删除函数;break;case4:调用输出函数;break;case5:break;default:给出出错信息，并要求重新输入｝｝(6)单链表的创建

尾接法12EFhead12EFp130Ap*s130Asa0NULL*headNULL130A1475p*s1475sa1NULL1475for(j=0;j<=n-1;j++){if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;s->data=a[j];s->next=NULL;p->next=s;p=s;}开始初始化单链表尾结点指向新结点修改尾指针NY初始化尾指针链表创建结束?申请新结点结束尾接法创建单链表流程图intCreatL1(SLNode**h,DataType

a[],intn){SLNode*p,*s;

inti,j;

i=ListInitiate(h);if(i==0)return0;p=*h;

for(j=0;j<=n-1;j++){if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;s->data=a[j];s->next=NULL;p->next=s;p=s;}return1;}12EFh*s130Asa0NULL*hNULL130A*s1475sa1130A1475for(j=0;j<=n-1;j++){if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;s->data=a[j];s->next=(*h)->next;(*h)->next=s;}(6)单链表的创建头插法开始初始化单链表新结点指向第一个结点头结点指向新结点NY链表创建结束?申请新结点结束头接法创建单链表流程图intCreatL2(SLNode**h,DataType

a[],intn){SLNode*s;

inti,j;i=ListInitiate(h);if(i==0)return0;for(j=0;j<=n-1;j++){if((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)return0;s->data=a[j];s->next=(*h)->next;(*h)->next=s;}return1;}

2.3.5循环单链表head非空表空表headhead->next==head2.3.6双向循环链表typedef

structNode{DataTypedata;

structNode*prior,*next;}DLNode;priordatanext要点回顾线性表的链式存储——链表特征：逻辑上相邻，物理上不一定相邻；优点：不需预先确定数据元素的最大个数；插入、删除不需移动数据元素缺点：空间利用率低；算法较复杂单链表结点datanext数据域指针域单链表的初始化、插入、删除、头插法及尾插法创建单链表讨论线性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。问1：线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？答：

顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。顺序存储的优点是存储密度大(＝1)，存储空间利用率高。缺点是插入或删除元素时不方便。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小（<1），存储空间利用率低。答：问2：顺序存储和链式存储各有哪些优缺点？事实上，链表插入、删除运算的快捷是以空间代价来换取时间。问3：在什么情况下用顺序表比链表好？顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。答：具体要求顺序表链表基于空间适于线性表长度变化不大，易于事先确定其大小时采用。适于当线性表长度变化大，难以估计其存储规模时采用。基于时间由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。应用实例1

删除顺序表la中所有值为x的数据元素。设顺序表的数据结构定义为：#defineMAX100typedef

int

DataType;typedef

struct{

DataTypeList[MAX];

intnum;/*最后一个数据元素的下标*/}SeqList;

voidDeleteSeqList(SeqList*la,DataTypex){intj,k;for(j=0;j<=la->num;j++){if(la->List[j]==x){for(k=j;k<la->num;k++)la->List[k]=la->List[k+1];la->num--;

j--;}}}

应用实例2删除顺序表a中第i(i>=0)个元素起的k个元素。#defineMAX100typedef

int

DataType;typedef

struct{

DataTypeList[MAX];

intnum;/*最后一个数据元素的下标*/ }SeqList;int

DeleteK(SeqList*a,int

i,intk)

{intj;

if(a->num<0){printf(“顺序表已空！\n”);return0;}elseif(i<0||k<0||i+k-1>a->num)return0;else{for(j=i;j<=a->num-k;j++)

a->List[j]=a->List[j+k];a->num=a->num-k;

return1;}

}/*判断表是否为空*//*判断删除位置、个数是否合理*//*删除从第i个元素开始的k个元素*/应用实例3在有序顺序表中插入值为x的数据元素以保持顺序表的有序性。#defineMAX100typedef

int

DataType;typedef

struct{

DataTypeList[MAX];

intnum;/*最后一个数据元素的下标*/}SeqList;

int

Orderlnsert(SeqList*L,DataTypex){inti;if(L->num==Max-1){printf(“顺序表已满”);return0;}else{for(i=L->num;i>=0&&x<L->List[i];i--)L->List[i+1]=L->List[i];L->List[i+1]=x;L->num++;return1;}}应用实例4实现单链表的就地逆序。设其头结点的指针为head，编写一个算法将单链表逆置。单链表的逆转headpqqa1a2` a3a4a0headheada0headqa0a1a0a1a2a0a1a2a3a4a1a2a3a4a2a3a4a3a4ppheada0a1a2a3a4ppheadvoidreverse(SLNode*head){

SLNode*p,*q;p=head->next;head->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=head->next;head->next=q;}}应用实例5

已知线性表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素合并为一个新的线性表lc，lc中的数据元素仍按非递减有序排列，并要求不破坏la和lb表。La=(3,5,8,11)Lb=(2,6,8,9,11,15,20)合并结果:Lc=(2,3,5,6,8,8,9,11,11,15,20)typedef

struct{elemtype

List[maxlen];

intnum;}qltype;1.顺序表结构int

mergeql(qltype

la,qltypelb,qltype*lc){

inti,j,k;if(la.num+1+lb.num+1>maxlen){printf(“\n数组下界溢出！”);return0;}i=j=k=0;while(i<=la.num&&j<=lb.num){if(la.list[i]<=lb.list[j])

lc->list[k++]=la.list[i++];else

lc->list[k++]=lb.list[j++];}while(i<=la.num)lc->list[k++]=la.list[i++];while(j<=lb.num)lc->list[k++]=lb.list[j++];lc->num=k-1;return1;}typedef

struct

slnode{elemtypedata;

struct

slnode*next;}slnodetype;2.单链表结构La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新链表当前结点Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPaint

mergesl(slnodetype*la,slnodetype*lb,slnodetype**lc){slnodetype*pa,*pb,*pc;

if(*lc=(slnodetype*)malloc(sizeof(slnodetype)))==NULL){printf(“\n分配内存失败！”);return0;}pa=la->next;

pb=lb->next;pc=*lc;

while(pa&&pb){if(pc->next=(slnodetype*)malloc(sizeof(slnodetype)))==NULL){printf(“\n分配内存失败！”);return0;}pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;

pb=pb->next;}

while(pa){if

pc->next=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)

{printf(“\n分配内存失败！”);return0;}pc=pc->next;pc->data=pa->data;pa=pa->next;}while(pb){if

pc->next=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)

{printf(“\n分配内存失败！”);return0;}pc=pc->next;pc->data=pb->data;

pb=pb->next;}pc->next=NULL;return1;}

思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何编程？2、要求不能有重复的数据元素，如何编程？总结（1）了解线性表的定义和线性结构的特点；（2）理解线性表的顺序存储和链式存储，理解用数组与单链表表示线性表的优缺点；（3）掌握线性顺序表中数据元素的存储位置的计算，顺序表的插入、删除等有关操作；（4）会用单链表编写插入、删除等有关算法。作业：P562-14(单链表）

2-172-18int

ListInitiate(SLNode**head){if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}（1）初始化12EFhead*headNULL12EF第三章堆栈和队列Chapter3StackandQueue3.1堆栈（Stack）

3.2

队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式本章内容3.1堆栈一、堆栈的基本概念定义

堆栈是限定只能在表的一端进行插入和删除的线性表。在表中允许插入和删除的一端叫做栈顶(top)；表的另一端则叫做栈底(base)。出栈或退栈入栈或进栈a0a1…an-2an-1basetopLastInFirstOut一般线性表逻辑结构：一对一存储结构：顺序表、链表运算规则：随机存取堆栈逻辑结构：一对一存储结构：顺序栈、链栈运算规则：后进先出(LIFO)*堆栈与一般线性表的比较*例

一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，1出即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。*不可能产生的输出序列：3121、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空二、堆栈的操作三、栈的顺序表示和实现——顺序堆栈1.顺序栈的存储结构出栈或退栈入栈或进栈basetopa0a1a3a4a5maxlen-1543210顺序栈的定义typedef

int

DataType;#definemaxlen100/*顺序堆栈数组最大存储单元个数*/typedef

struct

/*顺序栈定义*/{DataType

stack[maxlen];/*顺序堆栈存放数据元素的数组*/

inttop;/*顺序堆栈数组的当前栈顶位置*/}seqstack;

/*结构类型名*/2.顺序堆栈的操作实现toptopa0a1a2toptopmaxlen个