《《数据结构》(C语言版)第二章 线性表》由会员分享，可在线阅读，更多相关《《数据结构》(C语言版)第二章 线性表（119页珍藏版）》请在金锄头文库上搜索。
1、2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加第二章第二章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现学习提要：1.了解线性表的逻辑结构和存储结构。2.掌握两种存储结构的描述方法以及在 每种存储结构上的基本操作的实现。3.理解两种存储结构的特点及其使用场 合。重难点内容：顺序表、链表及其操作实现线性结构的基本特征:线性结构是一个数据元素的有序（次序）集 。1集合中必存在唯一的一个“第一元素”；2集合中必存在唯一的一个 “最后元素” ；3除最后元
2、素在外，均有 唯一的后继；4除第一元素之外，均有 唯一的前驱。 2.1 2.1 线性表的类型定义线性表的类型定义l线性表：n个数据元素组成的有限序列。 表示为（a1，a2，ai，ai+1， an)例：英文字母表（A,B,C,.Z)是一个线性表例： 数据元素 线性表的长度：表中元素的个数 n(n=0)，n=0 空表。 位序：元素ai在表中的位置数i 。 逻辑特征： v1|ai-1 ,aiD, i=2,.,n 基本操作：结构初始化操作结构销毁操作引用型操作加工型操作 ADT ListInitList( 2. 依值在线性表LA中进行查访; 3. 若不存在，则插入之。GetElem(LB, i, /
3、取Lb中第i个数据元素赋给eif ( ! LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e);/ La中不存在和 e 相同的数据元素，则插入之void union(List / 求线性表的长度Lb_len = ListLength(Lb); for (i = 1; i 即：LOC(ai) = LOC(ai-1) + L一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置，即LOC(ai) = LOC(a1) + (i-1)L基地址a1 a2aibb+Lb+(i-1)L12i内存状态 储存地址位序b+(maxle
4、n-1)Lb+(n-1)Lanb+nLn空闲顺序映像的 C 语言描述：typedef struct SqList; / 俗称 顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)线性表的基本操作在顺序表中的实现：InitList( if (!L.elem) exit (OVERFLOW); L.
5、length = 0; L.listsize = LIST_INIT_SIZE return OK;结构初始化InitList( / i 的初值为第 1 元素的位序p = L.elem; / p 的初值为第 1 元素的存储位置while (i , 表的长度增加插入操作ListInsert_Sq( / q 指示插入位置for (p = p = q; -p) *(p+1) = *p;for( j=n-1; j=i-1; -j)L.elemj+1= L.elemj; L.elemj+1=e;Status ListInsert_Sq(SqList / q 指示插入位置 for (p = p = q;
6、-p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK;算法时间复杂度为: O( ListLength(L) )if (L.length = L.listsize) / 当前存储空间已满，增加分配newbase = (ElemType *) realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存储分配失败L.elem = newbase; / 新基址L.listsize
7、 += LISTINCREMENT; / 增加存储容量 if (i L.length+1) return ERROR; / 插入位置不合法考虑移动元素的平均情况:假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：(a1, , ai-1, ai, ai+1, , an) 改变为(a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 删除操作ListDelete( e=*p; q
8、= L.elem+L.length-1; for (+p; p L.length) return ERROR; /删除位置不合法考虑移动元素的平均情况:假设删除第 i 个元素的概率为 , 则在长 度为n 的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除 的概率都是相等的，则移动元素的期望值为 ：l优点逻辑相邻，物理也相邻可随机存取任一元素存储空间使用紧凑l缺点插入、删除操作需要移动大量的元素需事先分配一定大小的连续的存储空间顺序存储线性表的优缺点：顺序表实现合并算法2.2void MergeList(SqList La,SqList Lb,SqList
9、pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem) / 存储分配失败exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(padata表示p指向结点的数据域 (*p).nextp-next表示p指向结点的指针域二、结点和单链表的 C 语言描述aiai+1pp-nextLin
10、kList L； / L 为单链表的头指针三、单链表操作的实现GetElem(L, i, e) / 取第i个数据元素ListInsert( j = 1; / p指向第一个结点，j为计数器 while (p +j; / 顺指针向后查找，直到 p 指向第 i 个元素/ 或 p 为空if ( !p | ji )return ERROR; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK;ai-1 线性表的操作ListInsert( j = 0; while (p +j; / 寻找第 i-1 个结点 if (!p | j i-1)return ERROR;
11、/ i 大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK;eai-1aiai-1sp 线性表的操作ListDelete ( p-next = q-next; e = q-data; free(q);pqStatus ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next +j; / 寻找第 i 个结点，并令 p 指向其前趋 if (!(p-next)
12、| j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK; 操作 ClearList( L-next=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。操作步骤： 一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三
13、、输入数据元素an-1，建立结点并插入；anan an-1四、依次类推，直至输入a1为止。void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode);scanf( / 输入元素值p-next = L-next; L-next = p; / 插入 补充作业：写出按正位序建立一个单链表的 算法。回顾 2.1 节中两个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？void union(
14、List Lb_len =ListLength(Lb); for (i = 1; i next;pb=Lb-next,pc;Lc=pc=La; / 用La的头结点作为Lc的头结点while(pa pc=pa; pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; / 插入剩余段free(Lb); / 释放Lb的头结点 算法时间复杂度 l优点它是一种动态结构，整个存储空间为多个 链表共用不需预先分配空间插入、删除操作方便l缺点指针占用额外存储空间不能随机存取，查找速度慢链式存储线性表的优缺点：用上述定义的单链表实现线性表的操作时， 存在的问题：改进链表的设置：1单链表的表长是一个隐含的值；1增加“表长”、“表尾指针” 和 “当前位置的 指针” 三个数据域；2在单链表的最后一个元素之后插入元素时，需遍历整个链表； 3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2将基本操作中的“位序 i ”改变为“指针 p ”。四、一个带头结点的线性链表类型typedef struct LNode / 结点类型ElemType data;struct LNode *next; *Link, *Position;Status MakeNode( Link / 分配由
