《数据结构课程教程第二章》由会员分享，可在线阅读，更多相关《数据结构课程教程第二章（108页珍藏版）》请在金锄头文库上搜索。
1、线性表是一种最简单的线性结构线性结构的基本特征:1集合中必存在唯一的一个“第一元素”；2集合中必存在唯一的一个 “最后元素”3除最后元素在外，均有 唯一的后继；4除第一元素之外，均有 唯一的前驱。线性结构 是一个数据元素的有序（ 次序）集。2.1 线性表的类型定义2.3 线性表类型的实现 链式映象2.4 一元多项式的表示2.2 线性表类型的实现 顺序映象抽象数据类型线性表的定义如下： ADT List 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。 数据关系： R1 |ai-1 ,aiD, i=2,.,n
2、设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。基本操作：结构初始化操作 结构销毁操作引用型操作加工型操作 ADT ListInitList( 2依值在线性表 LA 中进行查访; 3若不存在，则插入之。GetElem(LB, i)eLocateElem(LA, e, equal( )ListInsert(LA, n+1, e)( n 表示线性表 LA 当前长度)操作步骤：GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal( ) ) ListInsert(La,
3、 +La_len, e);/ La中不存在和 e 相同的数据元素，则插入之La_len = ListLength(La); / 求线性表的长度Lb_len = ListLength(Lb); for (i = 1; i 用一组地址连续的存储单元依次存放线性表中的数据元素a1 a2 ai-1 ai an线性表的起始地址， 称作线性表的基地址LOC(ai)以“存储位置相邻”表示有序对即：LOC(ai) = LOC(ai-1) + C一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai) = LOC(a1) + (i-1)C基地址顺序映像的 C 语言描述typed
4、ef struct SqList; / 俗称 顺序表！=有序表ElemType *elem; / 存储空间基址 int length; / 线性表当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)注意动态分配的数组和静态分配的数据的区别！线性表的基本操作在顺序表中的实现InitList( if (!L.elem) exit(OVERFLOW);L.length = 0; L.listsize = LIST_INIT_SIZE; return OK;例如：顺序表定位操作23 75 41 38 54 62 17L.elemL.length
5、= 7L.listsizee =38pppppi 1 2 3 4 1 850p可见，基本操作是， 将顺序表中的元素 逐个和给定值 e 相比较。int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，/ 若存在，则返回它的位序，否则返回 0 / LocateElem_SqO( ListLength(L) )if (i , 表的长度增加(a1, , ai-1, e, ai, , an)Status ListInsert_Sq(SqList / q 指示插
6、入位置 for (p = p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK;/realloc()!元素右移考虑移动元素的平均情况:假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：if (L.length = L.listsize) return OVERFLOW;/ 当前存储空间已满 if (i L.length+1) return ERROR; /
7、 插入位置不合法21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = / q 指示插入位置for (p = p = q; -p) *(p+1) = *p;p线性表操作ListDelete( p L.length) return ERROR; / 删除位置不合法元素左移考虑移动元素的平均情况:假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除 的概率都是相等的，则移动元素的期望值为 ：21 18
8、 30 75 42 56 8721 18 30 75L.length-10pppq8756p = q = L.elem+L.length-1; for (+p; p next; 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
9、i-1)return ERROR; / i 大于表长或者小于1 s = (LinkList)malloc(sizeof(Lnode); if ( ！s) return (OVERFLOW) ; 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; / 寻
10、找第 i 个结点，并令 p 指向其前趋q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;if (!(p-next) | j i-1) return ERROR; / 删除位置不合理操作 ClearList( L-next=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程 是一个结点“逐个插入” 的过程。例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。操作步骤：
11、 一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素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; / 插入 最后一个结点的指针域的指针又指回第一个结点的链表(适合合并操作）a1 a2 . an 1. 循环链表和单链表的差别仅在于
12、，判别链表中 最后一个结点的条件不再是“后继是否为 空”，而是“后继是否为头结点”。五、其它形式的链表2. 双向链表typedef struct DuLNode ElemType data; / 数据域struct DuLNode *prior; / 指向前驱的指针域struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;datanextprior双向循环链表空表非空表a1 a2 . an双向链表的操作特点：“查询” 和单链表相同“插入” 和“删除”时需要同时修改两个方向上的指针。ai-1aies-next = p-next; p-next
13、= s;s-next-prior = s; s-prior = p;psai-1ai插入ai-1删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1用前面定义的单链表实现线性表的操作时， 存在的问题：改进链表的设置：1单链表的表长是一个隐含的值；1增加“表长”、“表尾指针” 两个个数据域；2在单链表的最后一个元素之后插入元素时，需遍历整个链表； 3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2将基本操作中的“位序 i ”改变为“指针 p ”。 如：求前趋、后继的基本操作，改为： Postion PriorPos(LinkList
14、L,Link p); Postion NextPos(LinkList L,Link p);四、一个带头结点的线性链表类型typedef struct LNode / 结点类型ElemType data;struct LNode *next; *Link, *Position;Status MakeNode( Link / 分配由 p 指向的值为e的结点，并返回OK；/ 若分配失败，则返回 ERRORvoid FreeNode( Link / 释放 p 所指结点typedef struct / 链表类型Link head, tail; / 分别指向头结点和/ 最后一个结点的指针int len; / 指示链表长度Link current; / 指向当前被访问的结点/的指针，初始位置指向头结点int curpos; / 指示当前指针位置,初值为0 LinkList;链表的基本操作:结构初始化和销毁结构Status InitList( LinkList / 构造一个空的线性链表 L，其头指针、/ 尾指针和当前指针均指向头结点，/ 当前位置和表长为零。Status DestroyList( LinkList / 销毁线性链表 L，L不再存在。O(1)O(n)引用型操作Status ListEmpty (
