《数据结构第2章线性表》由会员分享，可在线阅读，更多相关《数据结构第2章线性表（122页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储2.3 线性表的链式存储2.4 线性表的应用 2.5 有序表 本章小结2.1 线性表的基本概念 1 线性表的定义2 线性表的运算1 定义线性表是具有相同特性的数据元素的一个有 限序列。线性表的长度：线性表中所含元素的个数。用n表示，n0。当n=0时，表示线性表是一个空表，即表中 不包含任何元素。设序列中第i（i表示位序）个元素为ai(1in) ，则线性表的一般表示为：(a1，a2，ai，ai+1，an)例如，在线性表(1，4，3，2，8，10)中，1 为表头元素，10为表尾元素。2 线性表的运算(1)初始化线性表 InitLis
2、t(ElemType e;InitList(LC);for(i=1；ilength=0；本算法的时间复杂度为O(1)。2 顺序表基本运算的实现(2)销毁线性表 DestroyList(L)释放线性表L占用的内存空间。void DestroyList (SqList * 本算法的时间复杂度为O(1)。 (3)判定是否为空表 ListEmpty(L)若L为空表，则返回1，否则返回0。int ListEmpty (SqList *L)return(L-length=0);本算法的时间复杂度为O(1)。(4)求线性表的长度 ListLength(L)只需返回length成员的值即可。int ListL
3、ength(SqList *L)return(L-length);本算法的时间复杂度为O(1)。(5)输出线性表 DispList(L)该运算当线性表L不为空时，顺序显示L中各元素 的值。void DispList(SqList *L)int i;if (ListEmpty(L) return;for (i=0; ilength; i+)printf(“%c“, L-elemi);printf(“n“); 时间复杂度为：O(L-length)或O(n)(6)求某个数据元素值 GetElem(L，i，e)该运算返回L中第 i(1iListLength(L)个元素的 值，存放在e中。int Get
4、Elem(SqList *L, int i, ElemType e=L-elemi-1;return 1;本算法的时间复杂度为O(1)。 (7)按元素值查找 LocateElem(L, e)该运算顺序查找第1个值域与e相等的元素的位序。 若这样的元素不存在，则返回值为0。int LocateElem (SqList *L, ElemType e)int i=0;while (ilength if (i=L-length) return 0;else return i+1;时间复杂度为: O(L-length)或O(n)(8)插入数据元素 ListInsert(L，i，e)该运算在顺序表L的第i
5、个位置 (1iListLength(L)+1)上插入新的元素e。步骤：如果i值不正确，则显示相应错误信息；否则：将顺序表原来第i个元素及以后元素均后移一 个位置；腾出一个空位置插入新元素，顺序表长度增1 。演示线性表操作ListInsert(if (iL-length+1) return 0;i-;/*将顺序表位序转化为elem下标*/for (j=L-length;ji;j-) L-elemj=L-elemj-1;/*将elemi及后面元素后移一个位置*/L-elemi=e;L-length+; /*顺序表长度增1*/return 1;演示假设pi(= )是在第i个位置上插入一个元素的 概率
6、，则在长度为n的线性表中插入一个元素时所需 移动元素的平均次数为: 元素移动的次数与两个因素有关：表长Llength（n）；插入位置i（有n+1个可能的插入位置）。因此，插入算法的平均时间复杂度为O(n)。如：ListInsert_Sq(L, 5, 66) i-; /*将顺序表位序转化为elem下标*/for (j=L-length;ji;j-) L-elemj=L-elemj-1;/*将elemi及后面元素后移一个位置*/L-elemi=e;L.length-10jjjij2118307542568766算法(9)删除数据元素 ListDelete(L, i, e)如果i值不正确，则显示相应
7、错误信息； 否则:将线性表第i个元素以后元素均向前移动一个 位置，这样覆盖原来的第i个元素，达到删除该元 素的目的，最后顺序表长度减1。线性表操作ListDelete(if (iL-length)return 0;i-; /*将顺序表位序转化为elem下标*/e=L-elemi;for(j=i;jlength-1;j+) L-elemj=L-elemj+1;/*将elemi之后的元素前移一个位置*/L-length-;/*顺序表长度减1*/return 1;演示元素移动的次数也与表长n和删除元素的位 置i有关；当i=n时，移动次数为0；当i=n-1时，移动次数为1；当i=1时，移动次数为n-1
8、。 在线性表sq中共有n个元素可以被删除。假设 pi(pi= )是删除 第i个位置上元素的概率，则在长 度为n的线性表中删除一个元素时所需移动元素的平 均次数为: 因此，删除算法的平均时间复杂度为O(n)。i-; /*将顺序表位序转化为elem下标*/e=L-elemi;for(j=i;jlength-1;j+) L-elemj=L-elemj+1;如：ListDelete_Sq(L, 5, e) L.length-10jji21183075425687算法例 已知长度为n的线性表A采用顺序存储结构 ，编写一个时间复杂度为O(n)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为ite
9、m 的数据元素。解:用k记录顺序表A中等于item的元素个数，边 扫描A边统计k，并将不为item的元素前移k个位 置，最后修改A的长度。对应的算法如下:2 4 10 13 22 4 10 2 20item=2k=i0 1 2 3 49iiiii4 10 134 10 209用K来统计 item的个数void delnode (SqList /*k记录值等于item的元素个数*/while (ii /*从右向左扫描，找一个小元素*/if(inext=NULL;for (i=0;idata=ai; s-next=L-next;/*将*s插在原开始结点之前,头结点之后*/L-next=s; /*
10、L-next始终指向链表的当前最新插入结点*/ adcbi采用头插法建立单链表的过程a dcheadheadbiiiss(2)尾插法建表：队列建表法头插法建立链表虽然算法简单，但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致，可采用尾插法建立。该方法是将新结点插到当前链表的表尾上，为此 必须增加一个尾指针r，使其始终指向当前链表的尾结点。void CreateListR(LinkList * int i;L=(LinkList *) malloc (sizeof(LinkList); /*创建头结点*/L-next=NULL;r=L; /*r始终指向尾结点，开始时指向了头结点
11、*/for (i=0;idata=ai; r-next=s; /*将*s插入*r之后*/r=s;r-next=NULL;/*尾结点next域置为NULL*/adcbi=0 i=1 i=2 i=3head头结点ad cb 采用尾插法建立单链表的过程rsrs2. 插入结点运算插入运算是将值为x的新结点插入到单链表的 第i个结点的位置上。先在单链表中找到第i-1个结 点，再在其后插入新结点。s-next=p-next;p-next=s;headheadSSpp在带表头结点的链表中插入结点比 不带表头节点的链表中的处理简单3. 删除结点运算删除运算是将单链表的第i个结点删去。先在 单链表中找到第i-1
12、个结点，再删除其后的结点。a2 a1 an headai ai-1 ai+1 head qqppp=q-next; q=p-next; free(p);在带表头结点的链表中删除结点比不带表头结点的 链表中的处理简单4. 线性表基本运算实现(1)初始化线性表 InitList(L)建立一个空的单链表，即创建一个头结点。void InitList (LinkList * /*创建头结点*/L-next=NULL;(2)销毁线性表 DestroyList(L)释放单链表L占用的内存空间。即逐一释放全部 结点的空间。void DestroyList (LinkList *while (q!=NULL)
13、free(p);p=q; q=p-next;free(p);(3)判线性表是否为空表 ListEmpty(L)若链表L没有结点，则返回真，否则返回假。int ListEmpty(LinkList *L)return(L-next=NULL);(4)求线性表的长度 ListLength(L)返回单链表L中数据结点的个数。int ListLength (LinkList *L)LinkList *p=L; int i=0;while (p-next != NULL)i+;p=p-next;return(i); (5)输出线性表 DispList(L)逐一扫描单链表L的每个数据结点，并显示各 结点的
14、data域值。void DispList (LinkList *L)LinkList *p=L-next;while (p != NULL)printf(“%c“, p-data);p=p-next;printf(“n“);(6)求线性表L中指定位置的某个数据元素 GetElem(L，i， LinkList *p=L;while (jnext; if (p = NULL) return 0; /*不存在第i个数据结点*/ else /*存在第i个数据结点*/ e=p-data;return 1; L线性表的操作 GetElem(L, i, int n=1;while (p!=NULL n+;i
15、f (p=NULL) return(0);else return(n);(8)插入数据元素ListInsert(LinkList *p=L, *s;while (jnext;if (p=NULL) return 0; /*未找到位序为i-1的结点*/else/*找到位序为i-1的结点*p*/ s= (LinkList *) malloc (sizeof(LinkList);/*创建新结点*s*/s-data=e;s-next=p-next; /*将*s插入到*p之后*/p-next=s;return 1;s = new LNode; / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK;eai-1aiai-1sp(9)删除数据元素 ListDelete (LinkList *p=L,*q;while (jnext;/*查找第i-1个结点*/if (p=NULL)
