节线性数据结构-基本概念-去掉声音效果了

1、第二章第二章 线性数据结构线性数据结构描述客观事物的数字、字符以及一切描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计能够输入到计算机中，并且能够被计算机程序处理的算机程序处理的符号的集合符号的集合。 表示一个事物的一组数据，是数据的基表示一个事物的一组数据，是数据的基本单位，又称结点。在计算机程序中通本单位，又称结点。在计算机程序中通常作为一个整体进行处理。一个数据元常作为一个整体进行处理。一个数据元素由若干素由若干数据项数据项构成。构成。数据元素之间具有的关系，即数据的组数据元素之间具有的关系，即数据的组织形式。织形式。2.1.1 数据和数据结构 具有独立含义的最小标识单位

2、具有独立含义的最小标识单位, ,是是数据的数据的最小单位最小单位学号学号姓名姓名性别性别籍贯籍贯出生年月出生年月住址住址06048001赵玲女上海1987.10上海06048002杨扬男北京1987.3北京 描述客观事物的数字、字符以及一切描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计能够输入到计算机中，并且能够被计算机程序处理的算机程序处理的符号的集合符号的集合。 表示一个事物的一组数据，是数据的基表示一个事物的一组数据，是数据的基本单位，又称结点。在计算机程序中通本单位，又称结点。在计算机程序中通常作为一个整体进行处理。一个数据元常作为一个整体进行处理。一个数据元素由若干

3、素由若干数据项数据项构成。构成。数据元素之间具有的关系，即数据的组数据元素之间具有的关系，即数据的组织形式。织形式。2.1.1 数据和数据结构表结构表结构学号学号姓名姓名 性别性别籍贯籍贯出生年月出生年月住址住址06048001 赵玲女上海1987.10上海06048002 杨扬男北京1987.3北京 学籍登记表学籍登记表交通图交通图乌鲁木齐兰州西安呼和浩特北京郑州成都18921145668676695511842图结构图结构 1. 研究数据元素之间的客观联系研究数据元素之间的客观联系。 2. 研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的

4、存储方式。 3. 研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的) 的基础上对数据实施一系列有效的基本操作。的基础上对数据实施一系列有效的基本操作。 逻辑结构逻辑结构存储结构存储结构1.2 数据结构研究的内容数据结构研究的内容算法算法逻辑结构逻辑结构： 计算机处理的数据元素的组织形式及其相互间的关系。 由数据元素的有限集合及所有数据元素之间的关系组成。记为： Data_Structure = (D, R) 其中，D是数据元素的有限集，R是所有数据元素之间的关系的有限集合。 数据结构: SET =（D,R）08010305020704060910集合结构示意图D

5、= 01,02,03,04,05,06,07,08,09,10 R = 数据结构 LINEARITY =（D,R）05010308020704060910线性结构示意图数据元素之间的联系：数据元素之间的联系：1:1D = 01,02,03,04,05,06,07,08,09,10 R = , , , 数据结构 01020304070809050610树结构示意图数据之间的联系：数据之间的联系：1：NGraph = ( D, R )数据之间的联系：数据之间的联系：M：ND = 1,2,3,4,5,6,7,8,9 R = , , ,d1 d2 d3 d4 d301. 顺序存储结构顺序存储结构线性结

6、构线性结构（线性表）（线性表）2. 链式存储结构链式存储结构a1a2a3a30list 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算数据的运算 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表堆栈堆栈队列队列树形结构树形结构图形结构图形结构数据结构的三个方面： 散列存储散列存储索引存储索引存储串及数组串及数组查找、排序、插入、删除、修改等查找、排序、插入、删除、修改等1. .算法的定义算法的定义(1). 算法算法是用来解决某个特定问题的指令的集合。是用来解决某个特定问题的指令的集合。(2). 算法算法是由人们组织起来准备加以实施

7、的一系是由人们组织起来准备加以实施的一系 列有限的基本步骤。列有限的基本步骤。2. .算法的描述算法的描述文字形式文字形式程序设计语言形式（如程序设计语言形式（如C语言等）语言等）伪码形式伪码形式3. .算法的性质算法的性质 4. .算法分析算法分析时间复杂度时间复杂度 T T（n n）空间复杂度空间复杂度 S S（n n）其它（如可读性、可移植性等）其它（如可读性、可移植性等）前提条件：算法必须正确4.时间复杂度时间复杂度称为时间频度，记为T（n） 例：例：3n+2=O(n) /* 3n+2 4n for n 2 */10n2+4n+2=O(n2) /* 10n2+4n+2 11n2 for

8、 n 5 */6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n 4 */注注 空间复杂度空间复杂度S(n)按数量级递增顺序也与上表类按数量级递增顺序也与上表类同。同。常用的计算规则：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) 3.空间复杂空间复杂度度时间复杂度和空间复杂度的关系时间复杂度和空间复杂度的关系复习：链表numnamesexageaddr10001Zhan

9、g xinM19Shanghai10002Wang liF18Xian10003Li fangM18Beijing学生学籍信息学生学籍信息struct Student int num; char name20; char sex; int age; char addr30; ;记录记录关键字关键字结构体名结构体名numnamesexageaddr10001Zhang xinM19Shanghai10002Wang liF18Xian10003Li fangM18Beijing学生学籍信息学生学籍信息struct Student int num; char name20; char sex; i

10、nt age; char addr30; ;记录记录结构体类型结构体类型结构体成员结构体成员struct Student int num; char name20; char sex; int age; char addr30; ;struct Student s1;s1.numstruct Student *s2;(*s2).num等价于等价于s2-num 链表是一种常见的重要的数据结构 它是动态地进行存储分配的一种结构head12491249A135613561475B1475C10211021DNULL头指针头指针各结点地址不连续各结点地址不连续各结点含有两个部分各结点含有两个部分表尾表

11、尾struct Student int num; float score; struct Student *next; a,b,c;1010189.510103901010785a结点结点b结点结点c结点结点a.next=&b;b.next=&c;numscorenext程序运行过程中，程序运行过程中，如何动态申请内存如何动态申请内存空间？空间？q 动态内存分配 设计人员根据具体问题的具体需要，在程序运行时再具体确定数组的个数或占用内存单元的大小，从而在程序运行时具体确定所需要的内存单元空间。malloc()函数free()函数头文件malloc.h# include mall

12、oc()函数free()函数函数原型： void * malloc ( unsigned size)函数功能： 用于向系统动态申请size个字节的内存单元空间，函数返回值为所申请的内存空间首地址。函数原型： void free ( void * p)函数功能：用于释放动态分配的内存空间。sizeof 运算符：运算符：sizeof(已定义的数据类型)功能：返回括号中给出的已定义数据类型占用的字节个数。Memory Allocation如：如：sizeof(int)p=( SLNode * ) malloc(sizeof(SLNode) );SLNode *p;p=malloc(sizeof(SL

13、Node);强制类型转换 所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。 例9.9 写一函数建立一个有3名学生数据的单向动态链表。 解题思路： 定义3个指针变量：head,p1和p2，它们都是用来指向struct Student类型数据struct Student *head,*p1,*p2;unsigned LEN=sizeof(struct Student); 解题思路： 用malloc函数开辟第一个结点，并使p1和p2指向它p1p1=p2=(struct Student*)malloc(LEN);p2 解题思路

14、： 读入一个学生的数据给p1所指的第一个结点p1scanf(%ld,%f,&p1-num,&p1-score);p21010189.5 解题思路： 读入一个学生的数据给p1所指的第一个结点 使head也指向新开辟的结点headp1p2scanf(%ld,%f,&p1-num,&p1-score);1010189.5 解题思路： 再开辟另一个结点并使p1指向它，接着输入该结点的数据headp1p21010189.5 解题思路： 再开辟另一个结点并使p1指向它，接着输入该结点的数据headp1p21010189.5p1=(struct Student*)malloc

15、(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010390 解题思路： 使第一个结点的next成员指向第二个结点，即连接第一个结点与第二个结点 使p2指向刚才建立的结点headp1p21010189.5p2-next=p1;1010390 解题思路： 使第一个结点的next成员指向第二个结点，即连接第一个结点与第二个结点 使p2指向刚才建立的结点headp1p21010189.5p2-next=p1;1010390p2=p1; 解题思路： 再开辟另一个结点并使p1指向它，接着输入该结点的数据headp1p21010189.51010390 解题思

16、路： 再开辟另一个结点并使p1指向它，接着输入该结点的数据headp1p21010189.51010390p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010785 解题思路： 使第二个结点的next成员指向第三个结点，即连接第二个结点与第三个结点 使p2指向刚才建立的结点headp1p21010189.510103901010785p2-next=p1; 解题思路： 使第二个结点的next成员指向第三个结点，即连接第二个结点与第三个结点 使p2指向刚才建立的结点headp1p21010189.

17、510103901010785p2-next=p1;p2=p1; 解题思路： 再开辟另一个结点并使p1指向它，接着输入该结点的数据headp1p21010189.5101039010107850 解题思路： 再开辟另一个结点并使p1指向它，接着输入该结点的数据headp1p21010189.5101039010107850p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score); 解题思路： 输入的学号为0，表示建立链表的过程完成，该结点不应连接到链表中headp1p21010189.510103901010

18、7850NULLp2-next=NULL;#include #include #define LEN sizeof(struct Student)struct Student long num; float score; struct Student *next;int n;struct Student类型数据的长度类型数据的长度struct Student *creat(void) struct Student *head,*p1,*p2; n=0; p1=p2=( struct Student*) malloc(LEN); scanf(“%ld,%f”,&p1-num,&p1-score); head=NULL; while(p1-num!=0) n