数据结构课件(c语言)3.ppt

例2.1 大写英文字母表：（A,B,C,D……,Y,Z），其中每个字母为一个数据元素，A是字母序列的“首”数据元素，Z是字母序列的“末”数据元素，其它每个字母有且只有一个直接前驱和一个直接后继，这个序列是一个线性表。 例2.2 教师信息表，其中每位教师的有关信息为一个数据元素，所有教师的信息集合构成一个线性表。 * 例2.6：已知L1和L2分别为两个单循环链表的头指针。试遍写一算法将链表L2连接在链表L1的后面，连接后形成的单循环链表头指针为L1。 linklist *Combination(linklist *L1, linklist *L2) { linklist *p, *q; p=L1–next; q=L2–next; while(p–next!=L1) p=p–next; while(q–next!=L2) q=q–next; p=L2–next; q–next=L1; free(L2); return(L1); } * 2.3.4 静态链表 以上我们提到的线性表的各种链式存储结构，都是根据需要动态分配及释放其结点所占的内存空间，这种链表称为动态链表。还有一种链表叫作静态链表，与动态链表的区别在于静态链表需要预先分配一个较大的空间，以备以后需求。因此，静态链表可用一维数组来实现，其基本结构为: #define MAXSIZE maxlen typedef int elemtype; /*定义新类型，类型名为elemtype*/ typedef struct SeqLinkList { elemtype data; /*数据域*/ int next; /*下标指针域*/ }SLList[MAXSIZE]; * 例2.6线性表（A,B,C,D,E,F）的静态链表存储示意图如下，请在第4个数据元素之前插入一新的数据元素G。 * 2.4 线性表的存储方式小结 线性表的存储方式主要分两大类，一类是顺序存储，一类是链式存储，其中链式存储又包括单链表、双向链表、循环链表及静态链表等多种存储结构。不同的存储结构各有其优缺点。 顺序存储结构是处理线性表时较常用的一种存储方式，它利用数组来实现数据元素的存储，数据元素的物理存储顺序与数据元素之间的逻辑关系相对应，可以方便的实现对数据的随机存取，是一种随机存储结构，如对一个线性表的主要操作是查询，则可采用这种存储方式。 * 但正因为它是利用数组来实现存储，就限定了它需要预先设定好线性表中数据元素可能达到的最大个数，如果对线性表操作过程中，表长变化较大，则设定最大表长就比较困难，也可能造成部分内存空间的浪费。另外，为了保持顺序表中数据元素有序性，在插入或删除数据元素时，需要移动大量的数据，这样对需要频繁进行插入删除操作的线性表来说，效率太低。 链式存储结构恰与顺序存储结构互补。组成链表的每个结点所占空间是动态申请及释放的，存储空间的使用更灵活，当线性表表长不确定时，可采用动态链表作为存储结构。链式存储结构中数据元素之间的逻辑顺序是由结点的指针域来控制的，这样在插入或删除数据元素时，只要修改指针域的值即可，不需要移动大量数据。但当每个结点数据域所占空间不是很大时，指针域所占空间就会显得很大，因此，具体使用哪种存储结构，还视实际问题而定。 第2章 线性表 * 第2章 线性表 2.1 线性表的定义及其基本操作 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的存储方式小结 * 线性结构是一种简单的数据结构。这种结构具有以下特点：在数据元素的非空有限集合中，有且只有一个“首”数据元素；有且只有一个 “末”数据元素；除“首”数据元素外，其它数据元素有且只有一个直接前驱；除“末”数据元素外，其它数据元素有且只有一个直接后继。线性表属于线性结构的范畴，是最常用的数据结构。 2.1 线性表的定义及其基本操作 * 线性表（linear list）是具有相同数据类型的n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1,a2,…,ai-1,ai,ai+1,…,an），其中数据元素ai（1≤i≤n）是线性表中第i个数据元素，它是一个抽象的符号，其数据类型可以根据具体情况而定，i称为数据元素ai在线性表中的位序。 2.1.1 线性表的定义 * 2.1.2 线性表的基本操作 (1)InitList(*