数据结构(C语言版)课件

数据结构(C语言版)课件

第二章 线性表19:09

数据结构(C语言版)课件

第2章 第3章 第4章 第5章

线性表 栈和队列 串 数组和广义表

线性结构(逻辑、存储 和运算)

线性结构的定义：若结构是非空有限集，则有且仅有一个开始结 点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。 可表示为：(a1 ,

a2

, ……,

a n)

数据结构(C语言版)课件

线性结构表达式：(a1 ,

a2

, ……,

a n)

线性结构的特点：① 只有一个首结点和尾结点； ② 除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。简言之，线性结构反映结点间的逻辑关系是 一对一 的

线性结构包括线性表、堆栈、队列、字符串、数 组等等，其中，最典型、最常用的是

线性表19:09

数据结构(C语言版)课件

第2章

线性表

教学目标1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种 存储结构的不同特点及其适用场合

19:09

数据结构(C语言版)课件

教学内容2.1 线性表的类型定义 2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现2.4 线性表的应用

19:09

数据结构(C语言版)课件

2.1

线性表的类型定义(a1, a2, … ai-1,ai, ai+1 ,…, an)数据元素

线性表的定义：用数据元素的有限序列表示

线性起点

ai的直接前趋 ai的直接后继n=0时称为 空表

线性终点

下标，是元素的 序号，表示元素 在表中的位臵

n为元素总个数，即表长

19:09

数据结构(C语言版)课件

例1 分析26 个英文字母组成的字母表 ( A, B, C, D, …… , Z) 数据元素都是字母; 元素间关系是线性 例2 分析学生情况登记表学 号 99070101 99070102 99070103 99070104......

姓 名 李 军 王颜霞 孙 涛 单晓宏......

学生基本情况 性 别 出生年月 男 80.12 女 81.2 男 80.9 男 81.3...... ......

...... ...... ....... ...... ...... ......

数据元素都是记录;

元素间关系是线性

同一线性表中的元素必定具有相同特性19:09

数据结构(C语言版)课件

抽象数据类型线性表的定义为： ADT List {

数据对象： D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。}数据关系： R1={ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } {设线性表为 (a1,a2, . . . ,ai,. . . ,an), 称 i 为 ai 在线性表中的位序。}19:09

数据结构(C语言版)课件

线性表的基本操作1. 2. 3. 4. 5. 6. 7. 8. 9. 初始化线性表L InitList(L) 销毁线性表L DestoryList(L) 清空线性表L ClearList(L) 求线性表L的长度 ListLength(L) 判断线性表L是否为空 IsEmpty(L) 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 检索值为e的数据元素 LocateELem(L,e) 在线性表L中插入一个数据元素 ListInsert(L,i,e) 删除线性表L中第i个数据元素 ListDelete(L,i,e)

} ADT List

19:09

数据结构(C语言版)课件

2.2

线性表的顺序表示和实现

线性表的顺序表

示又称为顺序存储结构或顺序映像。 顺序存储定义：把逻辑上相邻的数据元素存储在物理 上相邻的存储单元中的存储结构。

简言之，逻辑上相邻，物理上也相邻顺序存储方法：用一组地址连续的存储单元依次存储 线性表的元素，可通过数组V[n]来实现。

19:09

数据结构(C语言版)课件

存储地址 存储内容 Lo Lo+m 元素1

元素2……..

顺序存储Lo+(i-1)*m

元素i ……..

Lo+(n-1)*m

元素n

Loc(元素i)=Lo+(i-1)*m

随机存取的存储结构

19:09

数据结构(C语言版)课件

顺序表的类型定义#define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct {ElemType *elem; // 存储空间基址 int length; // 当前长度 listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) } SqList; // 俗称 顺序表 int

数据结构基本运算操作有： 查找、插入、删除19:09

数据结构(C语言版)课件

补充：C语言的动态分配函数( <stdlib.h> )

malloc(m):开辟m字节长度的地址空间， 并返回这段空间的首地址 sizeof(x):计算变量x的字节长度

free(p):释放指针p所指变量的存储空间 ，即彻底删除一个变量

19:09

数据结构(C语言版)课件

补充：C++中的参数传递

函数调用时传送给形参表的实参必须与形参在类 型、个数、顺序上保持一致 参数传递有两种方式 传值方式(参数为整型、实型、字符型等) 传地址 参数为指针变量 参数为引用类型 参数为数组名19:09

数据结构(C语言版)课件

传值方式把实参的值传送给函数的形参中，函数使用 这个形参执行必要的功能。函数修改的是形 参的值，实参的值不变 #include <iostream.h> void swap(float m,float n) {float temp; temp=m; m=n; n=temp; }19:09

void main() {float a,b;

cin>>a>>b;swap(a,b);

cout<<a<<endl<<b<<endl;}

数据结构(C语言版)课件

传地址方式--指针变量作参数形参变化影响实参 #include <iostream.h> void main() {float a,b,*p1,*p2; cin>>a>>b;p1=&a; p2=&b; swap(p1, p2);

void swap(float *m,float *n){float t; t=*m; *m=*n; *n=t; }

cout<<a<<endl<<b<<endl;}19:09

数据结构(C语言版)课件

传地址方式--指针变量作参数形参变化不影响实参？? #include <iostream.h> void main() {float a,b,*p1,*p2; cin>>a>>b;p1=&a; p2=&b; swap(p1, p2);

void swap(float *m,float *n){float *t; t=m; m=n; n=t; }

cout<<a<<endl<<b<<endl;}19:09

数据结构(C语言版)课件

传地址方式--引用类型作参数什么是引用？??

引用：它用来给一个对象提供一个替代的名字。#include<iostream.h> void main(){ int i=5; int &j=i; i=7; cout<<"i="<<i<<" j="<<j; }

j是一个引用类型, 代表i的一个替代名 i值改变时,j值也跟 着改变，所以会输出

i=7 j=7

19:09

数据结构(C语言版)课件

传地址方式--引用类型作参数#include <iostream.h> void swap(float& m,float& n) {float temp; temp=m;

void main() {float a,b; cin>>a>>b; swap(a,b);

m=n;n=temp; }

cout<<a<<endl<<b<<endl;}

19:09

本文来源：https://www.bwwdw.com/article/k6hq.html