第二章 线性表 2.1 线性表的逻辑结构 一. 线性表定义如下：

Presentation on theme: "第二章 线性表 2.1 线性表的逻辑结构 一. 线性表定义如下："— Presentation transcript:

1 第二章 线性表 2.1 线性表的逻辑结构 一. 线性表定义如下：
第二章 线性表 2.1 线性表的逻辑结构 一. 线性表定义如下： 线性表(Linear_list )是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：(a1，a2，… ai-1，ai，ai+1，…an) ，其中 n 为表长， n＝0 时称为空表。 有且仅有一个开始结点和一个终端结点,每一结点最多只有一个直接前趋和一个直接后继。

2 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。 void union(List &La，List Lb) { La_len=listlength(La); Lb_len=listlength(Lb); for(i=1;i<=lb_len;i++) getelem(Lb，i，e); if(!locateelem(La，e，equal)) listinsert(La，++La_len，e); }

3 算法2.2 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法如下： void MergeList(List La，List Lb，List &Lc) { InitList(Lc); i=j=1;k=0; La_len=ListLength(La); Lb_len=ListLength(Lb);

4 while((i<=La_len)&&(j<=Lb_len))
{ //La和Lb均非空 GetElem(La，i，ai); GetElem(Lb，j，bj); if(ai<=bj) { ListInsert(Lc，++k，ai); ++i; } else { ListInsert(Lc，++k，bj); ++j; } } while(i<=La_len) //如果线性表La中还有省余的元素 { getelem((La，i++，ai);ListInsert(Lc，++k，ai); while(j<=lb_len) { getelem((lb，j++，bj);listinsert(lc，++k，bi);

5 分析上面两个算法: 算法2.2的时间复杂度为O(ListLength(La)+ListLength(Lb)) 算法2.1的时间复杂度为O(ListLength(La)*ListLength(Lb)) 原因?

6 2.2 线性表的顺序表示和实现 一.线性表的顺序存储
在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。 如图 2.2 所示。设 a１的存储地址为Loc(a１)，每个数据元素占c个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a１)+(i-1)*c <=i<=n

7 在C语言中用一维数组表示的顺序表： #define LIST_INIT_SIZE //存储空间的初始分配量 #define LISTINCREMENT //存储空间的分配增量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度,实际用量 int listsize; //当前分配存储空间容量 } SqList;

8 顺序表上的基本运算: 算法2.3顺序表的初始化 即构造一个空表，这是一个加工型的运算，首先动态分配存储空间，将表中 length设置为0，表示表中没有数据元素。算法如下： Status InitList_Sq(SqList &L ) { L.elem=( ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType)) ; if(!L.elem) exit(OVERFLOW) ; L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//InitList_Sq

9 表长为 length，数据元素分别存放在data[0]到L.elem[length -1]中。
线性表的顺序存储示意图 1 … i-1 i n-1 ….. listsize-1 elem a1 a2 ai-1 ai ai+1 an length 表长为 length，数据元素分别存放在data[0]到L.elem[length -1]中。

10 顺序表插入运算ListInsert_Sq( )
线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表: (a1 , a2 ,... , ai-1 , ai , ai+1, ... ,an ) 成为表长为 n+1 表: (a1，a2，...，ai-1，x，ai，ai+1，...，an　) i 的取值范围为1<=i<=n+1 。 P23图2.3 顺序表上完成这一运算则通过以下步骤进行： (1) 将ai～an 顺序向后移动，为新元素让出位置； (2) 将 x 置入空出的第i个位置； (3) 修改表长length的值。

11 算法2.4 顺序表插入运算 Status ListInsert_Sq(Sqlist L，int i，ElemType e) { if (i<1 || i>L.length+1) return ERROR; if (L.length>=L.listsize) newbase=(ElemType *) realloc(L.elem, (L.listsize +LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW);//分配不成功 L.elem= newbase; L.listsize += LISTINCREMENT; } q=&(L.elem[i-1]); //q所指向的是第 i 个元素 for(p=&(L.elem[L.length-1]);p>=q;--p) //从最后一个元素开始移动 *(p+1)=*p; *q=e; ++L.length; return OK; }//ListInsert_Sq

12 插入算法的时间性能分析： 顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 n－i＋1个元素，而 i 的取值范围为 ： 1<= i<= n+1，即有 n＋1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数： 设：Pi=1/ (n+1) ，即为等概率情况，则： 这说明在顺序表上做插入操作需移动表中一半的数据元素, 显然时间复杂度为Ｏ(n)。

13 删除运算 ListDelete_Sq( ) 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表:(a1，a2，... ，ai-1，ai，ai+1，...，an) 成为表长为 n－1 的线性表: (a1，a2，... ，ai-1， ai+1，... ，an) ; i 的取值范围为：1<=i<=n 。 顺序表上完成这一运算的步骤如下： 1) 将ai+1～an 顺序向前移动。 2) 修改length仍使 length-1 为最后一个元素的下标。

14 算法2.5顺序表删除算法 Status ListDelete_Sq(Sqlist &L，int i ,ElemType &e)
{ //在顺序表L中删除第i个元素,并用e返回其值 //i的合法值为1 <= i <= ListLength_Sq(L) if((i<1) || (i>L.length)) return ERROR; p=&(L.elem[i-1]); e=*p; q=&(L.elem [ L.length-1]); for(++ p;p<= q;++p) *(p-1)=*p; - - L.length; return OK; }//ListDelete_Sq

15 删除算法的时间性能分析： 与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1～an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。

16 按值查找 在顺序表中完成该运算最简单的方法是：从第一个元素 a1 起依次和 e比较，直到找到一个与e相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 e 相等的元素，返回 0。 算法如： int LocateElem_Sq(SeqList L, ElemType e, Status(*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; /*返回的是存储位置*/ }//LocateElem_Sq

17 当查找成功时： 当 a1= =e 时，比较一次成功。当 an==e时比较 n 次成功。平均比较次数为（n+1）/2，时间性能为O(n)。

18 顺序表的合并 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
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;　//指向顺序表La的最后一个元素 pb_last=Lb.elem+Lb.length -1;　//指向顺序表Lb的最后一个元素 while( pa<=pa_last && pb<=pb_last ) if (*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa<=pa_list) *pc++=*pa++; while(pb<=pb_list) *pc++=*pb++; }//MergeList_Sq

19 两个有序顺序表合并的时间复杂度为： O(n+n)即为　　O(n) 作业2 实现两个顺序表的合并 建立两个顺序表（通过随机过程生成，并排序）； 输出合并前的结果 对这两个顺序表进行合并； 输出合并结果

20 2.3 线性表的链式存储结构 顺序表的优缺点 优点：可随机存取; 无需增加额外的存储空间
2.3 线性表的链式存储结构 顺序表的优缺点 优点：可随机存取; 无需增加额外的存储空间 缺点: 插入、删除要移动大量的节点，时间开销大 ; 要有连续的存储空间，有时会浪费或难以满足分配。 链式存储可以利用任意的存储单元 链表 用一组地址任意的存储单元存放线性表中的数据元素, 以元素(数据元素的映象) + (指示后继元素存储位置的)指针 = 结点(表示数据元素)。 线性表结点的序列称作链表

21 ^ 2.3.1 单链表：只有一个指示后继元素指针域 结点的结构包括: 数据域和指针域 data next
typedef struct Lnode { ElemType data; struct Lnode *next; } LNode , *LinkList; 单链表结点结构 data next 单链表的表示: 用头指针命名.如 La, Head a1 H … an ^ a2

22 带头结点的单链表 在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量head中存放该结点的地址，使得“空表”和“非空表”的处理成为一致。 头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。

23 申请一个结点 如 LinkList s；//注意：此时的s是指针变量 则语句：
s=(linklist ) malloc(sizeof(LNode))； free(s)则表示释放 s所指的结点 该结点的 数据域为 (*s).data 或 s->data 指针域为 (*s).next 或 s->next s s->data s->next

24 单链表上的基本操作 按序号查找 算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第ｉ个结点时返回空。 Status GetElem_L(LinkList L,int i ,ElemType &e) { //L为带头结点的单链表的头指针 p=L->next; j=1; while( p && j<i) { p=p->next; ++j; } if (!p|| j>i) return ERROR; //只有一开始时j就大于i e = p->data; return OK; }//GetElem_L //算法 时间复杂度为O(n)

25 单链表的插入 插入分前插入和后插入两种 （1）后插入结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。 主要操作如下： ①s->next=p->next; ②p->next=s; 注意：这两步（指针）操作顺序不能交换。

26 算法 2.9 Status ListInsert_L(LinkList &L, int i, ElemTyp e ) { //在带头结点的单链表L中第i个位置之前插入元素e p=L;j=0; while (p && j<i-1) //当循环结束时p可能指向第i-1个元素 { p=p->next; ++j; } if(!p || j>i-1) return ERROR; s=(LinkList ) malloc(sizeof(LNode)); // ?写出其他的写法 s->data=e; s->next=p->next; p->next=s; return OK; }//ListInsert_L

27 前插结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将. s插入到. p的前面，插入示意图如下图，与后插不同的是：首先要找到
前插结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如下图，与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s。

28 单链表的删除操作 设r指向单链表中某结点，删除*r。操作示意图如下图所示。通过示意图可见，要实现对结点*r的删除，首先要找到*r的前驱结点*p。 p->next = p->next->next; free(r);

29 Status ListDelete_L(Linklist &L, int i, ElemTyp &e )
/*在带头结点单链表 L 上删除第i个结点,并由e返回其值*/ { p=L;j=0; while (p->next && j<i-1 ) p=p->next;++j; } if(!p->next || j>i-1 ) return ERROR; q=p->next; p->next=q->next; e=q->data; free(q); return OK; }//ListDelete_L 算法2.10

30 通过上面的基本操作得知： (1)在单链表上插入、删除一个结点，必须知道其前驱结点。 (2)单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行,所以其时间复杂度为O(n)。

31 建立单链表 （头插法和尾插法） 头插法： 链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部。 ^ 在头部插入建立单链表 d c b a head p 2 1 3 \\

32 算法 用头插法建立单链表 void CreateList_L(LinkList &L, int n) { LinkList p; int i; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; // 先建立一个带头结点的单链表 for ( i=n; i>0; --i ) p = (LinkList)malloc(sizeof(LNode)); // 生成新结点 p->data = random(200); // 随机生成的数字(200以内) p->next = L->next; L->next = p; // 插入到表头 } } // CreateList_L

33 尾插法 头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针 r 用来始终指向链表中的尾结点。 算法思路： 初始状态：头指针Head=NULL，尾指针 r=NULL; 按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到 r 所指结点的后面，然后 r 指向新结点（第一个结点有所不同）。

34

35 合并两个非递减有序的单链表 思路: ?

36 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{ // 已知单链线性表La和Lb的元素按值非递减排列。 LinkList pa, pb, pc; pa = La->next; pb = Lb->next; Lc = pc = La; // 用La的头结点作为Lc的头结点 while (pa && pb) { if (pa->data <= pb->data) pc->next = pa; pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } pc->next = pa ? pa : pb; // 插入剩余段 free(Lb); // 释放Lb的头结点 } // MergeList_L // 算法2.12

37 静态链表 静态链表用一维数组表示，表中的结点是数组的一个分量，用游标代替指针来指示结点在数组中的相对位置，数组的第零个分量作为头结点，这种结构仍需预先分配一个较大的空间，但插入和删除不需移动结点，仅需修改游标。 #define MAXSIZE 1000 typedef struct { ElemType data; int cur; } component , SLinkList[ MAXSIZE]； 画在a2后插入a7的示意图中

38 算法 静态链表中的按值定位运算 int LocateElem_SL( SLinkList S, ElemType e) { // 在静态单链线性表L中查找第1个值为e的元素。 // 若找到，则返回它在L中的位序，否则返回0。 int i; i = S[0].cur; // i指示表中第一个结点 while (i && S[i].data != e) i = S[i].cur; // 在表中顺链查找 return i; } // LocateElem_SL

39 开始先将整个数组初始化为一个备用链表。 // 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针， "0"表示空指针 // 算法2.14 void InitSpace_SL(SLinkList &space) { for (int i=0; i<MAXSIZE-1; ++i) space[i].cur = i+1; space[MAXSIZE-1].cur = 0; } // InitSpace_SL

40 静态链表结点的申请和释放 静态链表不使用malloc()和free()。 静态链表将所有未使用的分量用游标链成一个备用的链表，插入时可从备用链表上取得第一个结点作为待插入的新结点；删除时将被删除的结点链接到备用链表上。

41 静态链表结点的申请 若备用空间链表非空，则返回分配的结点下标，否则返回0 int Malloc_SL(SLinkList &space) { int i = space[0].cur; if (space[0].cur) space[0].cur = space[space[0].cur].cur; return i; } // Malloc_SL 算法2.15 space[0]看成是备用链表的头结点

42 静态链表结点的释放 void Free_SL(SLinkList &space, int k) {// 将下标为k的空闲结点回收到备用链表 space[k].cur = space[0].cur; space[0].cur = k; } // Free_SL 算法2.16 采用的是头插入法的思路

43 例2-3 假设由终端输入集合元素,先建立集合A的静态链表S,而后在输入集合B的元素的同时查找S表,若存在和B相同的元素,则从S表中删除之,否则将此元素插入S表
算法 ALGO0217.CPP

44 2.3.2循环链表 循环链表： 最后一个结点的指针域指向头结点，形成一个环。 一般用尾指针rear来表示单循环链表。

45 对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表;
有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针rear来标识，可以使得操作效率得以提高。 遍历(Traversal)： 根据已给的表头指针，按由前向后的次序访问单链表的各个结点。 判断不是最后一个结点的条件是: p->next !=head 单链表如何判断是否是最后一个结点，或链表结束？

46 对两个单循环链表(a1,a2,…,an)和（b1，b2,…bn)链接成一个线线表（a1,a2,…an,b1,b2,…bn)，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针ra、rb来标识，则时间性能为O(1)。

47 p= ra –>next; /*保存R1 的头结点指针*/
ra->next=rb->next->next; /*头尾连接*/ free(rb->next); /*释放第二个表的头结点*/ rb->next=p; /*组成循环链表*/

48 2.3.4 双向链表 双向链表：每一结点有两个指针域，一个指向直接后继，另一个指向直接前趋。 typedef struct DuLNode
双向链表 双向链表：每一结点有两个指针域，一个指向直接后继，另一个指向直接前趋。 typedef struct DuLNode { ElemType data; struct DuLNode *prior ; struct DuLNode *next; }DuLNode, * DuLinkList; dlinklist *head; 和单链表类似，双链表一般也是由头指针head唯一确定。

49 p->prior->next表示的是
p->prior->next表示的是*p结点之前驱结点的后继结点的指针，即与p相等；类似，p->next->prior表示的是*p结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式： p->prior->next = p = p->next->prior

50 双向链表中结点的删除： 设p指向双向链表中某结点，删除*p。 操作如下： ①p->prior->next=p->next; ②p->next->prior=p->prior; free(p); 双向链表中删除结点

51 //算法2.19 删除带头结点的双链循环线性表L的第i个元素
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) { // i的合法值为1≤i≤表长 if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; // p=NULL, 即第i个元素不存在 e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; } // ListDelete_DuL

52 返回一个指定结点的指针 DuLinkList GetElemP_DuL(DuLinkList va, int i) { 　DuLinkList 　p; p = va->next; int j = 1; // 初始化，p指向第一个结点，j为计数器 while (p!=va 　&&　 j<i) { //顺指针向后查找，直到p指向第i个元素或p为空 p = p->next; ++j; } if (p==va || j<i) 　return 　NULL; // 第i个元素不存在 else return p; } // GetElem_L

53 双向链表中结点的插入： 设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如下图所示。 ①     s->prior=p->prior; ②     p->prior->next=s; ③     s->next=p; ④     p->prior=s;

54 //算法2.18 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{// 在带头结点的双链循环线性表L的第i个元素之前插入元素e， // i的合法值为1≤i≤表长+1。 DuLinkList p,s; if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; // p=NULL, 即第i个元素不存在 if (!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data = e; s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; return OK; } // ListInsert_DuL

55 2.4 顺序表和链表的比较 顺序存储的三个优点： (1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。 两个缺点： (1)   在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 (2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

56 链表的优缺点 １．基于存储的考虑 : 链表不用事先估计存储规模，但链表的存储密度较低。 ２．基于运算的考虑 ： 链表中按序号访问的时间性能O(n) ３．基于环境的考虑 ： 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的 通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。

57 其存储结构可以用顺序存储结构，也可以用单链表
2.4 一元多项式的表示及相加 一元多项式的表示： 可用线性表P表示 但对S(x)这样的多项式浪费空间 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构，也可以用单链表

58 单链表的结点定义 typedef struct { float coef; //系数 int exp; //指数
} term , ElemType; coef exp next typedef struct Lnode { ElemType data; struct Lnode *next; } LNode , *LinkList;

59 一元多项式相加 -1 A ^ -1 B 22 7 ^ -1 C 22 7 ^

60 若p==NULL，将B中剩余部分连到A上即可
运算规则 设p,q分别指向A,B中某一结点，p,q初值是第一结点 比较 p->exp与q->exp p->exp < q->exp: p结点是和多项式中的一项 　　　　　　 p后移,q不动 p->exp > q->exp: q结点是和多项式中的一项 　　　　　　 将q插在p之前,q后移,p不动 p->exp = q->exp: 系数相加 0：从A表中删去p, 释放p,q，p,q后移 0：修改p系数域, 释放q，p,q后移 直到p或q为NULL 若q==NULL，结束 若p==NULL，将B中剩余部分连到A上即可