《数据结构》(C语言版)第二章_线性表.ppt

1、1,2.4 一元多项式的表示及相加,第二章 线性表,2.1 线性表的类型定义,2.2 线性表的顺序表示和实现,2.3 线性表的链式表示和实现,2,线性结构的基本特征:,线性结构是一个数据元素的 有序（次序）集 。,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,2.1 线性表的类型定义,3,线性表：n个数据元素组成的有限序列。 表示为（a1，a2，ai，ai+1，an),例：英文字母表（A,B,C,.Z)是一个线性表,4,线性表的长度：表中元素的个数n(n=0)，n=0 空表。 位序

2、：元素ai在表中的位置数i 。,逻辑特征： 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项,5,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 ,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,6,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT List,7,InitList( ,2. 依值在线性表LA中进行查访;,3. 若不存在，则插入之。,GetElem(LB, i, / 取Lb中第i个数据元素赋给

3、e if ( ! LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之,void union(List ,for (i = 1; i = Lb_len; + i) , / union,O(ListLength(LA)ListLength(LB)；,23,例2-2,已知线性表LA和LB是非递减的，将两表合并成新的线性表LC，且LC也是非递减的。,24,算法思想：,将LA、LB两表中的元素逐一按序加入到一个新表LC中。 设 La = (a1, , ai, , an)， Lb = (b1,

4、, bj, , bm) ， Lc = (c1, , ck, , cm+n),1. 分别从La和Lb中取得当前元素ai和bj； 2. 若aibj，则将ai插入到Lc中，否则将bj插入到Lc中。,操作步骤：,25,void MergeList(List La, List Lb, List / 构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb);,O(ListLength(LA)ListLength(LB),26,while (i=La_len) ,27,while (i = La_len) /

5、当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素,while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素,28,线性表的顺序表示： 用一组地址连续的储存单元依次存放线性表的数据元素。,2.2 线性表的顺序表示和实现,29,30,顺序映像的 C 语言描述：,typedef struct SqList; / 俗称 顺序表,#define LIST_INIT_SIZE 80 / 线性表存储空间的初始

6、分配量,int *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),P294 typedef,31,32,Status InitList_Sq( SqList if (!L.elem) exit (OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE return OK;,结构初始化InitList( j=i-1; -j) L.elemj+1= L.elemj; L.elemj+1=e;,36,Status ListInse

7、rt_Sq(SqList if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ,if (i L.length+1) return ERROR; / 插入位置不合法,38,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,删除操作ListDelete( p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length;

8、 /表长减1 return OK;,算法时间复杂度为:,O( ListLength(L),p = /表尾元素的位置,if (i L.length) return ERROR; /删除位置不合法,41,编写一个程序，动态地创建一个顺序表。要求：顺序表初始长度为10， 向顺序表中输入15个整数，并打印出来；在删除顺序表中的第5个元素， 打印出删除后的结果。,42,#include stdio.h #include conio.h #define MaxSize 10 typedef int ElemType ; /*将int定义为ElemType*/ typedef struct int *ele

9、m; int length; int listsize; Sqlist; /* 初始化一个顺序表 */ /* 参数L：Sqlist类型的指针 */ void initSqlist(Sqlist *L) L-elem=(int *)malloc(MaxSize*sizeof(ElemType); if(!L-elem) exit(0); L-length=0; L-listsize= MaxSize; /* 向顺序表中插入元素 */ /* 参数L：Sqlist类型的指针 */ /* 参数i：插入元素的位置 */ /* 参数item：插入的元素 */ void InsertElem(Sqlist

10、*L,int i,ElemType item) /*向顺序表L中第i个位置上插入元素item*/ ElemType *base,* insertPtr,*p; if(iL-length+1) exit(0); if(L-length=L-listsize) base=(ElemType*)realloc(L-elem,(L-listsize+10)*sizeof(ElemType); L-elem=base; L-listsize=L-listsize+100; insertPtr= ,43,优点 逻辑相邻，物理也相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元

11、素 需事先分配一定大小的连续的存储空间,顺序存储线性表的优缺点：,44,2.3 线性表的链式存储结构,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、其它形式的链表,一、单链表,45,用一组任意的存储单元存储线性表的数据元素。,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象),一、单链表,46,例 线性表 (ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG),头指针,47,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为

12、了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时， 头结点的指针域为空,48,typedef struct LNode / 定义单链表结点 ElemType data; /数据域 struct LNode *next； / 指向后继的指针域 LNode, *LinkList,LNode *p;,(*p)表示p所指向的结点 (*p).datap-data表示p指向结点的数据域 (*p).nextp-next表示p指向结点的指针域,二、结点和单链表的 C 语言描述,LinkList L； / L 为单链表的头指针,49,三、单链表操作的实现

13、,GetElem(L, i, e) / 取第i个数据元素,ListInsert( j = 1; / p指向第一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK;,53,线性表的操作ListInsert( j = 0; while (p / i 大于表长或者小于1,56,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s

14、-next = p-next; p-next = s; / 插入 return OK;,s,p,57,线性表的操作ListDelete ( p-next = q-next; e = q-data; free(q);,p,q,59,Status ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next / 删除位置不合理,q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;,60,操作 ClearList(,算法时间复杂度：,O(ListLen

15、gth(L),61,如何从线性表得到单链表？,链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。,62,例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an， 建立结点并插入；,三、输入数据元素an-1， 建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,63,void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (

16、sizeof (LNode); scanf( / 插入 ,64,补充作业： 写出按正位序建立一个单链表的算法。,65,回顾 2.1 节中两个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？,66,void union(List /for / union,控制结构： 基本操作：,for 循环 GetElem, LocateElem 和 ListInsert,当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) ),当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)ListLen

17、gth(Lb) ),例2-1,67,void MergeList(List La, List Lb, List ,控制结构： 基本操作：,三个并列的while循环 GetElem, ListInsert,当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)+ListLength(Lb) ),当以链式映像实现抽象数据类型线性表时为: O( (ListLength (La)+ListLength (Lb)2 ),例2-2,68,Pa=null,while ( pa ,pc next = pa? pa : pb ; free(Lb);,O( listlength(La)+li

18、stlength(Lb) ),69,编写一个程序，要求：从终端输入一组整数（大于10个数），以0为结束标志，将这一组整数存放在一个链表中（结束标志0不包括在内），打印出该链表中的值。然后删除该链表中的第5个元素，打印出删除后的结果。最后在内存中释放掉该链表。,70,#include stdio.h typedef int ElemType; typedef struct node ElemType data; /*数据域*/ struct node *next; /*指针域*/ LNode,*LinkList; LinkList GreatLinkList(int n) LinkList p,

19、r,list=NULL; ElemType e; int i; for(i=1;idata=e; p-next=NULL; if(!list) list=p; else r-next=p; r=p; return list; void insertList(LinkList *list,LinkList q,ElemType e) LinkList p; p=( LinkList)malloc(sizeof(LNode); p-data=e; if(!*list) *list=p; p-next=NULL; else p-next=q-next; q-next=p; void delLink(

20、LinkList *list ,LinkList q) LinkList r; if(q=list) *list=q-next; free(q); else for(r=*list;r-next!=q;r=r-next); if(r-next!=NULL) r-next=q-next; free(q); void destroyLinkList(LinkList *list) LinkList p,q; p=*list; while(p) q=p-next; free(p); p=q; *list=NULL; ,71,main() int e,i; LinkList l,q; q=l=Grea

21、tLinkList(1); /*创建一个链表结点，q和l指向该结点*/ scanf(%d, ,72,优点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 插入、删除操作方便 缺点 指针占用额外存储空间 不能随机存取，查找速度慢,链式存储线性表的优缺点：,73,四、其他形式的链表,74,在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn),一元多项式,2.4 一元多项式的表示及相加,75,但是对于形如 S(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？,76,一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 +

22、p2xe2 + + pmxem 其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n,可以下列线性表表示： （p1, e1）, (p2, e2), , (pm,em) ）,77,P999(x) = 7x3 - 2x12 - 8x999,例如:,可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示,78,ADT Polynomial 数据对象： 数据关系：,抽象数据类型一元多项式的定义：,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 ,R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 ,79,CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ),基本操作：,操作结