09级使用数据结构第2章

1、返回主目录 本 章 说 明2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式存储结构2.4 循环链表和双向链2.5 一元多项式的表示及相加 本 章 小 结本章说明学习目标了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。结合线性表类型的定义增强对抽象数据类型的理解。本章说明重点和难

2、点链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。知识点线性表、顺序表、链表、有序表线性结构的特点：在数据元素的非空有限集中存在唯一的一个被称做“第一个”的数据元素存在唯一的一个被称做“最后一个”的数据元素除第一个之外，每个元素都只有一个前驱除最后一个之外，每个元素都只有一个后继1.线性表定义：一个线性表是n个数据元素的有限序列。2.1 线性表的类型定义例如：英文字母（A，B，C，Z）是一个线性表。表中元素是一个字母。例如：星期（星

3、期日，星期一，星期二，星期六）是一个线性表。表中的数据元素是星期中一天的名称。例如：在稍复杂的线性表中，一个数据元素可以是由若干个数据项组成的记录，含有大量记录线性表称为文件。如，一个学校的学生健康情况登记表。姓 名学 号性别年龄班级健康状况王小林790631男18计91健康陈 红790632女20计91一般刘建平790633男21计91健康张立立790634男17计91神经衰弱数据元素2.线性表的结构特性综上三个例子，我们可以如下描述线性表： 线性表是n0个数据元素a1，a2，ai-1，ai，ai+1，an的有限序列。线性表的长度定义为线性表中数据元素的个数n。当n=0时，为空表。n0时记为

4、（a1，a2，an） ai-1是ai的直接前驱，a1无直接前趋 ai+1是ai的直接后继，an无直接后继数据元素同构，相邻数据元素之间存在着序偶关系。所以可将线性表记为 （a1, , ai-1, ai, ai+1, an）数据元素在线性表中的位置只取决于它们自己的序号。数据元素之间的相对位置是线性的2.1 线性表的类型定义3.线性表的基本运算表的初始化求表长取（或修改）表中的结点查找结点插入结点删除结点。 不是全部操作，不同的问题需要的操作不同。2.1 线性表的类型定义4.抽象数据类型线性表的定义P19 ADT List 数据对象：D=ai|aiElemSet, i=1,2,n,n=0 数据关

5、系：R1=|ai-1, aiD, i=1,2,n 基本操作： InitList(&L) /创建一个空的线性表L DestroyList(&L) /撤消L2.1 线性表的类型定义 ClearList(&L) /将L重置为空表 ListEmpty(L) /判L是否为空? 空为T ListLength(L) /返回表长度(元素个数) GetElemList(L,I,&e) /用e返回L中第i个数据元素的个数2.1 线性表的类型定义4.抽象数据类型线性表的定义P19 LocateElem(L, e, compare() ) /查找并返回第1个与e满足关系compare()的元素的位序,若没找到则返回0

6、 PriorElem(L, cur_e, &pre_e) /找cur_e并返回其前驱pre_e,否则操作失败,pre_e无定义 NextElem(L, cur_e, &next_e) /找cur_e并返回其后继next_e,否则操作失败,next_e无定义 ListInsert(&L, i, e) ListDelete(&L, i, &e) ListTraverse(L, visit() /依次对L的元素调用visit(),如visit()失败,则操作失败ADT List2.1 线性表的类型定义 例2-1 两个线性表LA、LB，将存在于线性表LB中而不在LA中的数据元素加入到线性表LA中。即L

7、A=LALB 算法思想：逐一取出LB中的元素，判断是否在LA中，若不在,则插入之。 仅已知LA、LB （1）先求出LA、LB长度 （2）取LB中一元素=e，若LB取空则转（4） （3）如e不在LA中，则插入到LA中，转（2） （4）结束2.1 线性表的类型定义void unin(List &La，List Lb) La_len=(ListLength(La); Lb_len=(ListLength(Lb); for (i=1; ia,LB中取一元素=b, 否则转（3） （2）若ac,否则b=c,转（1） （3）若LA不空，则LA剩余部分放到LC尾 （4）若LB不空，则LA剩余部分放到LC尾vo

8、id MergeList(List La, List Lb, List &Lc) InitList(Lc); /建一空表LC i=j=1; k=0; /i，j，k分别指向La，Lb，Lc 初始位置 算法2.22.1 线性表的类型定义 La_len=(ListLength(La); Lb_len=(ListLength(Lb); 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,

9、 +k, bj); +j; 算法2.22.1 线性表的类型定义 while (i=La_len) /La还有元素 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j=Lb_len) /Lb还有元素 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); /MergeList时间复杂度：O(ListLength(LA) +ListLength(LB)算法2.22.1 线性表的类型定义2.2 线性表的顺序表示和实现3.线性表的动态分配顺序存储结构4.顺序线性表的操作 2.顺序表的特点 1.线性表的顺序表示 5

10、.顺序表的优缺点 1.线性表的顺序表示 定义：用一组地址连续的存储单元存储一个线性表的数据元素，称为顺序表。元素地址计算方法： LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+(i-1)* L 其中： L一个元素占用的存储单元个数 LOC(ai)线性表第i个元素的地址实现：可用C语言的一维数组实现2.2 线性表的顺序表示和实现a1a2an01n-112n内存V数组下标元素序号M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例 typedef struct card int num; char name20; c

11、har author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE);free(pData); 2.顺序表的特点 特点： 实现逻辑上相邻物理地址相邻 实现随机存取2.2 线性表的顺序表示和实现3.线性表的动态分配顺序存储结构用一维数组定义一个线性表#define LIST_INIT_SIZE 100#define LISTINCREAMENT

12、10type struct ElemType *elem; /指向线性表起始地址的指针 int length; /线性表实际存放数据长度 int listsize; /线性表申请长度 SqList2.2 线性表的顺序表示和实现 4.顺序线性表的操作顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。(1)初始化操作算法思想：构造一个空表。设置表的起始位置表长可用空间2.2 线性表的顺序表示和实现线性表初始化算法2.3Status InitList_Sq(SqList &L)L.elem= (ElemType*) malloc(LIST_INIT_SIZE*sizeof(El

13、emType);If (!L.elem) exit(OVERFLOW);L.length=0; L.listsize= LIST_INIT_SIZE;Return OK;/InitList_Sq2.2 线性表的顺序表示和实现（2）插入定义：线性表的插入是指在第i（1i n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 变成长度为n+1的线性表 需将第n至第i,共（n-i+1)个元素后移算法Ch2_1.c内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x

14、X插入算法2.4 （在表L中的第i个元素之前插入e），见P24判i值的合法性，1i表长+1；判表的空间满否？若满则增加分配（动态分配）；从表元素n到i，依次后移一个位置；将e插入第i个位置，表长度增1。算法中定义的线性表是L，以结构形式出现2.2 线性表的顺序表示和实现Status ListInsert_Sq(SqList &L, int i, ElemType e )if (iL.length+1) return ERROR; /i不合法 if (L.length=L.listsize) /当前可用空间已满 /增加分配 newbase=(ElemType*)realloc(L.elem, (

15、L.listsize+ LISTINCREMENT)sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; /新基址 L.listsize+= LISTINCREMENT; 插入算法2.4实现2.2 线性表的顺序表示和实现 q=&(L.elemi-1); /取插入位置 for (p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; /将ni位置的元素后移 *q=e; /插入e +L.length; /表长度+1 return OK;插入算法2.4实现2.2 线性表的顺序表示和实现插入算法2.

16、4时间复杂度 可见插入元素的时间主要花费在移动元素上，而移动元素的个数主要取决于插入的位置。 设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时需移动元素的平均次数为若在任何位置上插入元素都是等概率2.2 线性表的顺序表示和实现（3）删除算法思想：删除第i个元素，将第（i+1）至第n个元素逐一向前移动一个位置，将长度为n/ListInsert_Sq(a1,a2ai-1,ai,ai+1an)变成长度为n=n-1的线性表(a1,a2ai-1, ai+1an) 需将第i+1至第n共（n-i)个元素前移算法Ch2_1.c内存a1a2aiai+1an01i-1V数组下标n-

17、1i12i元素序号i+1n内存a1a2ai+201i-1V数组下标n-1i12i元素序号i+1nanai+1删除在表L中删除第i个元素，放入e，见P24 判i值的合法性，1i表长n 取第i个元素，放入e 从i+1到表长n，依次前移 表长度减1删除算法2.5思想2.2 线性表的顺序表示和实现删除算法2.5实现Status ListDelete_Sq(SqList &L, int i, ElemType &e )if ( (iL.length) ) return ERROR; /i不合法 p=&(L.elemi-1); /取被删除元素位置 e=*p; /取插入位置 q=L.elem+L.Lengt

18、h-1; /取表尾元素的位置 for (+p; p=q; +p;) *(p-1)=*p; /将i+1n位置的元素前移 -L.length; /表长度+1 return OK;/ListInsert_Sq2.2 线性表的顺序表示和实现删除算法2.5时间复杂度 可见删除元素的时间主要花费在移动元素上，而移动元素的个数主要取决于删除的位置。 设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为若在任何位置上插入元素都是等概率2.2 线性表的顺序表示和实现查找算法2.6Int LocateElem_Sq(SqList L,ElemType e, Status(

19、*compare)(ElemType, ElemType) /在顺序线性表L中找第一个值与e满足compare()的元素的位序，找到返回位序，否则返回0 i=1; p=L.elem; while (i=L.length&!(*compare)(*p+,e) +i; if (i=L.length) return i; else return 0;/ LocateElem_Sq 时间复杂度：O(L.length)2.2 线性表的顺序表示和实现合并算法2.7实现Int MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知顺序线性表La和Lb的元素非递减

20、排列，归并得到线性表Lc，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);2.2 线性表的顺序表示和实现 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while (pa=pa_last & pb=pb_last) /归并 if (*pa=*

21、pb) *pc+=*pa+; else *pc+=*pb+; while (pa=pa_last) *pc+=*pa+; /插入La剩余部分 while (pbdata表示p指向结点的数据域p-next表示p指向结点的指针域生成一个LNode型新结点：p=(LNode *)malloc(sizeof(LNODE);系统回收p结点：free(p)带头结点非空表：空表：datanextp结点（*p）a1a2an/L/L2.3 线性表的链式存储结构4. 链式存储结构的优点 插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。5.单链表的操作（1）取第i个元素算法思想：单链表是非随

22、机存取结构。每个元素的位置信息都包含在前驱结点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。2.3 线性表的链式存储结构Status GetElem_L(LinkList L, int i, ElemType)/L为带头结点的单链表的头指针。/当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p=Lnext; j=1; /p指向第一个结点，j做计数器 while(p & ji) return ERROR; e=pdata; return OK;/GetElem_L取结点算法2.82.3 线性表的链式

23、存储结构（2）插入操作： 要在数据元素a和b 之间插入元素x。算法思想：决定a和b之间的相邻关系是由a的指针决定的。若要实现插入，生成x结点，然后让a的指针指向x 且x的指针指向b。实现三个元a、x和b的逻辑关系。设p为指向结点a 的指针，s为指向结点x的指针，则修改s、a的指针：插入结点算法2.92.3 线性表的链式存储结构XsBAps-next=p-nextp-next= sXsBApStatus ListInsert_L(ListLInk &L, int i, ElemType e) /在带头结点的单链表L中第i个位置之前插入元素ep=L; j=0;while(p & ji-1) ret

24、urn ERROR; /i小于1或大于表长s=(LinkList)malloc(sizeof(LNode);sdata=e; snext=p-next;pnext=s;return OK;/ListInsert_L插入结点算法2.9实现2.3 线性表的链式存储结构BCApCAp（3）删除操作p-next=p-next-next删除结点算法2.10实现Status ListDelete_L(LinkList &L,int i,ElemType &e) /在带头结点的单链表L中删除第i个元素，并由e返回 p=L; j=0; while (p-next & jnext; +j; /寻找第i个结点，并

25、令p指向其前驱 if (!(p-next) | ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK;/ListDelete_L 2.3 线性表的链式存储结构动态创建链表算法动态建立单链表算法：设线性表n个元素，逆位序输入数据元素建立一个单链表，h为头指针。h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0h头结点0动态创建链表算法2.11实现Void CreateList_L(LinkList &L, int n) /逆位序输入n个元素值，建立带头结点的

26、单链表L L=（LinkList)malloc(sizeof(LNode); L-next=NULL; for (i=n; i0; -i) p=(LinkList)malloc(sizeof(LNode); scanf(&p-data); p-next=L-next; L-next=p; /CreatList_L2.3 线性表的链式存储结构（4）单链表的合并例：将两个有序链表合并为一个有序链表。算法思想：设立三个指针pa、pb和pc分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到合并表Lc中,让合并表的当前指针指向该元素，然后，修改指针。在归并两个链表为

27、一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。合并有序链表算法2.122.3 线性表的链式存储结构3511/La8152620/8911LbLcpbpapcpc-next=pbpc-next=papbpcpapcpapcpbpcpapcpbpcpbpcpapc每次链接pa或pb的一个结点后，便做如下操作： pa=pa-next; pc=pc-next; pa和pc分别后移一个位置或pb=pb-next; pc=pc-next; pb和pc分别后移一个位置合并有序链表算法2.12实现Void MergeList_L(LinkList La, Lin

28、kList Lb, LinkList &Lc) pa=La-next; pb=Lb-next; Lc=pc=La; while (pa & pb) if (pa-data 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);/MergeList_L2.3 线性表的链式存储结构6.静态单链表 有些高级语言没有指针，我们可以用数组来表示单链表，在数组中以整型游标来代替指针。这种用数组描述的链表称为静态链表。存储结构： #define MAXSIZE 1

29、000 typedef struct ElemType data; int cur; component, SLinklistMAXSIZE;Si.cur 指示第i+1个结点的位置。静态链表的操作和动态链表相似，以整型游标代替动态指针。2.3 线性表的链式存储结构011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910SHI9S0.cur为头指针，可以遍历整个静态链表找到插入位置i011ZHAO22QIAN33SUN44LI95ZHOU66WU87ZHEN

30、G88WANG09SHI510删除ZHENG, s6.cur=s7.curSHI85int LocateElem_SL(SLinkList S, ElemType e) /在静态单链线性表L中查找第1个值为e的元素 / 找到返回位序，否则返回0 i=S0.cur; while (i & Si.data!=e) i=Si.cur; return i; /没找到则到链尾，i=0/LocateElem_SL 算法2.13静态链表查找 2.3 线性表的链式存储结构假设由终端输入A集合元素并建立静态链表S，然后输入集合B元素在S中查找，若存在和B相同的元素，则从S中删除之，否则插入到S中。算法思想：将整

31、个数组空间初始化成一个链表从备用空间取得一个结点将空闲结点链接到备用链表上例2-3 运算(A-B)U(B-A)2.3 线性表的链式存储结构01122334455667788991010003122c0344556677089910100Space0.cur是备用空闲链表的头指针，space1.cur是链表的头指针A=(c, b, e, g, f, d), B=(a, b, n, f)初始化后04122c33b0455667708991010005122c33b44e05667788991010006122c33b44e55g0677889910100Space0.cur是备用空闲链表的头指针，

32、space1.cur是链表的头指针A=(c, b, e, g, f, d), B=(a, b, n, f)07122c33b44e55g66f07889910100A=(c, b, e, g, f, d), B=(a, b, n, f) 取B中元素在A中查找，若有与其相同的，则将A中的同元素删除，若没有则在A中插入08122c33b44e55g66f77d089910100A输入结束取a，在A中找，没有插入09122c33b44e55g66f77d88a091010003122c43b94e55g66f77d88a0910100删b, space2.curA=(c, b, e, g, f, d

33、), B=(a, b, n, f) 取B中元素在A中查找，若有与其相同的，则将A中的同元素删除，若没有则在A中插入03122c43b94e55g66f77d88a091010009122c43n04e55g66f77d88a391010006122c43n04e55g76f97d88a3910100插入n删除f，space5.cur=space6.curvoid InitSpace_SL(SLinkList &space) /将一维数组space中各分量链成一个备用链表 / space0.cur为头指针，0表示空指针 for (i=0; iMAXSIZE-1; +i) spacei.cur=i

34、+1; spaceMAXSIZE-1.cur=0;/ InitSpace _SL int Malloc_SL(SLinkList &space) i=space0.cur; if (space0.cur) space0.cur=spacei.cur; return i;/Malloc_SL算法2.14 2.15静态链表初始化 2.3 线性表的链式存储结构 void Free_SL(SLinkList &space, int k) /将下标为k的空闲结点回收到备用链表 spacek.cur=space0.cur; space0.cur=k;/ Free _SL (2.16) void diffe

35、rece(SLinkList &space, int &S) /依次输入集合A和B，在space中建立静态链表，S为头指针 /设space的备用空间足够大，space0.cur为其头指针， InitSpace_SL(space); /初始化备用空间 S=Malloc_SL(space); /生成S头结点 r=S; scanf(m,n); /r指向表尾元素，输入A,B元素个数算法2.16 2.17静态链表初始化 2.3 线性表的链式存储结构 for (j=1; j=m; +j) /建立集合A的链表 i=Malloc_SL(space); /分配结点，i为结点下标 scanf(spacei.dat

36、a); spacer.cur=i; r=i; /插入到表尾，r指向新表尾 /for spacer.cur=0; /创建结束，表尾的指针为空 for (j=1; jnext=NULL循环链表p-next=H 非空表空表HH2.双向链表 在双向链表的结点中有两个指针域，分别指向前驱和后继。双向链表也可以有循环链表。双向链表的存储结构 typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinklist;priordatanext2.4 循环链表和双向链表 L空双

37、向循环链表：非空双向循环链表：Labbcapp-prior-next= p= p-next-proir;双向链表的操作双指针使得链表的双向查找更为方便、快捷NextElem和PriorElem的执行时间为O(1)仅需涉及一个方向的指针的操作和线性链表的操作相同插入和删除需同时修改两个方向的指针2.4 循环链表和双向链表 Hab插入算法：在表L中第i个位置之前插入元素e设P指针，p=GetElemP-DuL(L,i)，使其指向第i个结点p 若p=null，则i不存在；pnull，则为e申请结点, e赋值xs 插入 s-prior=p-prior p-prior-next=s s-next=p p

38、-prior=s算法实现删除算法：删除表L中第i个元素，赋于e。P37算法219 设P指针，p=GetElemP-DuL(L,i)，使其指向第i个结点 p p=null，则i不存在；若pnull，p指向第i个结点，将其赋给e 删除 p-prior-next=p-next p-next-prior=p-priorHbca算法实现算法评价：T(n)=O(1)3.带头结点的线性链表类型类型定义：typedef struct LNode ElemType data; struct LNode *next *Link, *Position;typedef struct /链表类型 Link head,t

39、ail; int len; LinkList2.4 循环链表和双向链表 操作 从实际应用出发，重新定义了线性表及其基本操作。基本操作定义见P37 利用这些基本操作，很容易实现插入和删除操作2.4 循环链表和双向链表 算法2.20Status ListInsert_L(LinkList &L, int I, ElemType e) /在带头结点的单链表L的第i个元素之前插入元素e if ( !LocatePos(L, i-1, &h) return ERROR; /找第i-1个结点,h指向i-1结点 if ( !MakeNode(s,e) return ERROR;/结点申请失败 InsFirs

40、t(h,s); /h指向头结点,将s插在第一个结点之前 return OK;/ListInsert_L2.4 循环链表和双向链表 Status MargeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int(*compare)(ElemType,ElemTYpe) ) if ( !InitList(Lc) return ERROR; ha=GetHead(La); hb= GetHead(Lb); pa=NextPos(La,ha); pb=NextPos(Lb,hb); while (pa&pb) a=GetCurElem(pa); b= GetCurElem(pb); if (*compare)(a,b)=0) /aexp与q-expp-exp 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，结束