(C语言详细版)第二章线性表

1、重点重点：顺序表顺序表和链表链表上各种基本算法的实现及相关的时间性能分析难点难点：线性表应用的算法设计算法设计第二章 线性表第二章 线性表n从第2章至第4章将讨论线性结构。n线性结构的特点是：n在数据元素的非空有限集中，n(1)存在唯一的一个被称做“第一个”的数据元素；n(2)存在唯一的一个被称做“最后一个”的数据元素；n(3)除第一个之外，集合中的每个数据元素均只有一个前驱；n(4)除最后一个之外，集合中每个数据元素均只有一个后继。2022-5-24卓月明2第二章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循

2、环链表 2.3.3 双向链表2.4 一元多项式的表示及相加(基于线性表的应用)作业2022-5-24卓月明32.1 线性表的类型定义n定义nn(0)个数据元素的有限序列,记作(a1, ai-1, ai, ai+1, an)其中，ai 是表中数据元素，n 是表长度(n=0时称为空表)，i为ai在线性表中的位序。n由此，我们也可以将线性表看成是由 (i,ai ) 构成的集合。n线性表中的数据元素可以是各种各样的，只要是属于同一个集合即可。例如，26个小写英文字母是一个线性表(a,b,z)同一花色的13张扑克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A)可以构成一个线性表。2022-5-

3、24卓月明42.1 线性表的类型定义n在稍复杂的线性表中，一个数据元素可以由若干个数据项数据项(Item)组成。在这种情况下，常把数据元素称为记录记录(Record)，含有大量记录的线性表又称文件文件(File)。例如，一个学校的学生健康情况登记表如图所示，表中每个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等六个数据项组成。n约定n同一线性表中的元素必定具有相同的特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。 姓 名 学 号 性 别 年 龄 班 级健康状况王小林790631 男 18 计98 健康陈 红790631 女 20 计98 一般刘键平790633 男

4、21 计98 健康张立立790634 男 17 计98神经衰弱 2022-5-24卓月明52.1 线性表的类型定义n逻辑特征n0时n有且仅有一个“第一个”数据元素n有且仅有一个“最后一个”数据元素n除第一个数据元素外，其它元素有且仅有一个直接前驱n除最后一个数据元素外，其它元素有且仅有一个直接后继n序偶 表示ai是ai+1的直接前驱，反之， ai+1是 ai的直接后继。2022-5-24卓月明62.1 线性表的类型定义nADT List定义n基于ADT List的算法设计n结论n不同的算法策略所得不同算法的时间复杂度不同n输入线性表的特征会影响算法的策略（是否有序？）n输出线性表的特征会影响算

5、法的策略（是否有序？）2022-5-24卓月明72.2 线性表的顺序表示和实现n若要在实际的程序设计中真正引用线性表的基本操作，首先必须实现线性表类型。即在计算机中确定它的存储结构并在此存储结构上实现类型中定义的所有基本操作。本节将讨论它的顺序存储结构以及在顺序存储结构中基本操作的实现。 n何谓顺序存储表示？ n顺序存储表示指的是，以数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。你还记得吗？2022-5-24卓月明82.2 线性表的顺序表示和实现n定义n用一组地址连续的存储单元依次存储线性表中的数据元素n特点n逻辑上相邻，物理上也相邻。随机存取68 89 70 67 40 78 逻

6、辑序号逻辑序号(位序位序) 1 2 3 4 5 6C数组下标数组下标 0 1 2 3 4 5陈述问题时用2022-5-24卓月明92.2线性表的顺序表示和实现 -顺序表的存储LOC(a i+1) = LOC( a i )+lLOC(a i) = LOC(a1)+(i-1)*l a1 a2 a i an 1 2 i n a a+l a+(i-1)*l a+(n-1)*l idle2022-5-24卓月明102.2线性表的顺序表示和实现 -类型定义与基本操作实现n顺序表定义n方案一#define LIST_SIZE 100typedef struct ElemType elemLIST_SIZE;

7、/* 存储空间 */ int length; /* 当前长度 */SqList_static;1) LIST_SIZE过小，则会导致顺序表上溢；2) LIST_SIZE过大，则会导致空间的利用率不高。 2022-5-24卓月明112.2线性表的顺序表示和实现 -类型定义与基本操作实现n方案二#define LIST_INIT_SIZE 100 /* 存储空间的初始分配量 */#define LISTINCREMENT 10 /* 存储空间的分配增量 */typedef struct ElemType *elem; /* 存储空间的基址*/ int length; /* 当前长度*/ int l

8、istsize; /* 当前分配的存储容量*/SqList;n这种方法可以解决方案一中的“上溢”问题和“空间利用率不高”问题。但是这一方案是有时间和空间代价的：当因插入元素而空间不足时，需要重新分配比原先的顺序表多存储LISTINCREMENT个数据元素的连续空间，并且需要将原空间的数据元素复制到新分配的空间中。 2022-5-24卓月明122.2线性表的顺序表示和实现 -类型定义与基本操作实现n注意n1) 必须记载当前线性表的实际分配的空间大小；n2) 当线性表不再使用时，应释放其所占的空间；n3) 这种方法要求实现级的语言能提供空间的动态分配与释放管理。nvoid *malloc(unsi

9、gned int size)生成一大小为size的结点空间，将该空间的起始地址赋给p；nfree(void *p)回收p所指向的结点空间;nvoid *realloc(void *p, unsigned int size)将p所指向的已分配内存区的大小改为size，size可以比原分配的空间大或小。n若需使用上面三个函数，需include 2022-5-24卓月明132.2线性表的顺序表示和实现 -类型定义与基本操作实现n基本操作的实现n初始化 Status InitList_Sq( SqList &L) / 构造一个空的线性表LL.elem = (ElemType *) malloc

10、(LIST_INIT_SIZE*sizeof(ElemType);if ( L.elem = NULL ) exit(OVERFLOW); / 存储分配失败L.length = 0; / 空表长度为0L.listsize = LIST_INIT_SIZE;/ 初始存储容量return OK; / InitList_Sq2022-5-24卓月明142.2线性表的顺序表示和实现 -类型定义与基本操作实现n求表长 L.lengthn取第i个元素 L.elemi-1 (0iL.length+1)n按值查找 nint LocateElem_Sq(SqList L, ElemType e, Status

11、(*compare)(ElemType, ElemType)i=1;p=L.elem;while(i=L.length & !(*compare)(*p+,e) +i; if (i=L.length) return i;else return 0; for(i=0; iL.length & !(*compare)(L.elemi,e);i+);if (i= i; j-) L.elemj = L.elemj-1; / 后移L.elemi -1 = e; /第i个元素存放在L.elemi-1中，数组下标的起始为0L.length = L.length+1;n合法的位置：i:1.L.

12、length+1n上溢及处理：n上溢发生的条件：L.lengthL.listsizen此时要先申请一个有一定增量的空间，申请成功则原空间的元素复制到新空间，修改L.listsize，再进行插入工作；否则报错退出。2022-5-24卓月明172.2 插入操作的实现n2、算法Status ListInsert_Sq( SqList &L, int i, ElemType e) / 位置合法性的判断if ( iL.length +1 )return ERROR;/ 上溢时增加空间的分配if( L.length = L.listsize)newbase = (ElemType *) reall

13、oc(L.elem,(L.listsize+ LISTINCREMENT)*sizeof(ElemType);if ( newbase = NULL ) exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;/ 插入元素for ( j = L.length; j = i; j-)L.elemj = L.elemj-1;L.elemi-1 = e;L.length+;return OK;2022-5-24卓月明182.2 插入操作的实现n算法分析时间n频次最高的操作：移动元素。另外，上溢时的空间的再分配与复制(realloc操作)

14、的时间复杂度与realloc的算法以及当前的表长相关，至少为O(n)；但它仅在插入元素会引起上溢时才执行。n若线性表的长度为n，则：n最好情况：插入位置i为n+1，此时无须移动元素，时间复杂度为O(1);n最坏情况：插入位置i为1，此时须移动n个元素，时间复杂度为O(n);2022-5-24卓月明192.2 插入操作的实现n平均情况：假设pi为在第i个元素之前插入一个元素的概率，则：插入时移动次数的期望值：11) 1(niiisinpE等概率时等概率时，即，即， ， T(n) = O(n)11npi2) 1(1111ninnEniis2022-5-24卓月明202.2 删除操作的实现n基本操作

15、的实现n删除操作 演示Status ListDelete_Sq(SqList &L, int i, ElemType &e)15 23 46 16 57 10 64 1 2 3 4 5 6 7 816删除 e0 1 2 3 4 5 6 7i15 23 46 57 10 64 1 2 3 4 5 6 72022-5-24卓月明212.2 算法设计n基于顺序表的算法设计例2-1和例2-2n基本操作在顺序表中的实现nListLength(La) La.length nGetElem(Lb, i, e) e = Lb.elemi-1;nLocateElem(La, e, equal)

16、nListInsert(La, +La_len, e) La.elemLa_len+ = e;n基于顺序表实现例2-1和例2-2基本操作的简单替换，针对例2-2得到P26算法2.72022-5-24卓月明22n单链表n静态链表n循环链表n双向链表n其他 2.3 线性表的链式表示和实现2022-5-24卓月明23n单链表 n顺序映像的弱点n空间利用率空间利用率不高（预先按最大空间分配） n表的容量不可扩充容量不可扩充（针对顺序表的方案一） n即使表的容量可以扩充容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销开销，也不允许它频繁地使用n插入或删除时需移动移动大量元素n链表定义n特

17、点逻辑上相邻的元素，物理上未必相邻；非随机存取2.3.1 线性链表单链表2022-5-24卓月明24n链表定义n结点-数据元素的存储映像，包括数据域和指针域（其信息称为指针或链）n头指针-链表存取的开始 ；空(NULL)-最后一个结点的指针 2.3.1 线性链表单链表数据域数据域指针域指针域LI43QIAN13SUN1WANGNULLWU37ZHAO7ZHENG19ZHOU25存储地址存储地址1713192531374331头指针头指针2022-5-24卓月明252.3.1 线性链表单链表n链表定义n每个结点中只包含一个指针域，则称为线性链表线性链表或单链表；单链表；n相对地，称含两个或两个以

18、上指针域的结点构成的链表称为多重链表多重链表。n用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映象，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，这种存储结构为非顺序映象非顺序映象或链式映象链式映象。2022-5-24卓月明26n链表定义typedef struct LNode ElemType data;/数据域 struct LNode *next;/后向指针域LNode, *LinkList;2.3.1 线性链表单链表2022-5-24卓月明272.3.1 线性链表单链表n链表定义n1、无头结点的单链表、无头结点的单

19、链表头指针为L，则空表时，L = NULL由于第一个结点无前驱结点，所以只能通过某指针变量来指向，如L；其余结点均有前驱结点，故可通过其直接前驱结点的next域来指向，即-next；表示方法的不同，会造成对结点的操作处理的不同。n2、有头结点的单链表、有头结点的单链表空表时，L指向一结点(称为头结点)，该结点的数据域可以不存储信息，也可存储如表长等的附加信息，结点的指针域存放NULL，即 L-next = NULL。第一个结点和其余结点均可统一表示为其直接前驱结点的next域所指向的结点，即-next。a1a2Lana1anL2022-5-24卓月明282.3.1 线性链表单链表n基本操作的实

20、现 演示n取第i个元素GetElem_L(LinkList L, int i, ElemType &e) n插入操作ListInsert_L(LinkList &L, int i, ElemType e)2022-5-24卓月明29n基本操作的实现 演示n删除操作ListDelete_L(LinkList &L, int i, ElemType &e) n创建单链表CreateList_L(LinkList &L) n头插法n尾插法2.3.1 线性链表单链表2022-5-24卓月明30n基于单链表的算法设计不能简单地用基本操作的实现来替换要结合问题的处理

21、特征和存储结构的特征进行适当的整合整合！2.3.1 线性链表单链表2022-5-24卓月明31n静态链表 n问题：若语言不支持指针类型，能有链式存储吗？可以借用一维数组来表示链表-静态链表 数组元素(数据元素的值、指示器指示器)-结点n类型定义#define MAXSIZE1000typedef struct ElemTypedata; intcur;/替代动态链表结点中的指针域component, SLinkListMAXSIZE;2.3.1 线性链表静态链表2022-5-24卓月明32n循环链表 n问题1如何从一个结点出发，访问到链表中的全部结点？循环链表n问题2如何在O(1)时间内由链表指针访问到第一个结点和最后一个结点？头指针表示/尾指针表示尾指针表示n与单链表在基本操作的实现上的差异如链表的创建循环