[数学]数据结构-02线性表.pptVIP

第2章 线性表 教学要求： 理解线性表的概念 掌握线性表的抽象数据类型和应具有的基本操作 掌握线性表的顺序存储结构的实现方法 掌握线性表的链表存储结构的实现方法 掌握线性表的简单应用 （ A, B, C, D, …… , Z） 综上例： 线性表中的数据元素可以不同 但同一个表中的元素必须具有相同的属性 相邻数据元素之间存在序偶关系 线性表中每一个元素都有确定的位置，如a1是第1个数据元素，ai是第i个数据元素 问题： １、在顺序表中，第ｉ个元素前面插入一个元素，要移动多少个元素？ ２、在顺序表中，要删除第ｉ个元素，要移动多少个元素？ 算法：顺序表的合并 已知顺序表La和Lb按值非递减排列，归并两表，得到新表Lc也按值非递减排列。 分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要将La或Lb中的元素逐个插入到Lc中即可。 设两个指针pa和pb分别指向La和Lb中的某个元素，若设pa当前所指的元素为a，pb当前所指的元素为b，则当前应插入到Lc中的元素c为 c=ａ(ａ≤ｂ)； c=ｂ(ａ＞ｂ) 很显然，指针pa和pb的初值均为1，在所指元素插入Lc后，pa，pb在La或Lb中顺序后移。 void MergeList(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)); pa.last=La.elem+La.length-1; pb.last=Lb.elem+Lb.length-1; While (pa=pa.last pb=pb.last) { if(*pa=*pb) *pc++=*pa++; else *pc++=*pb++; } while (pa=pa.last ) *pc++=*pa++; while (pb=pb.last) *pc++=*pb++; } 作业: 用C语言编写代码,实现顺序表里面所有的操作。并写出main（）函数调用这些操作。 在单链表中设置头结点的好处 1、使空表和非空表统一。 2、在设计算法的时候，使首元结点和其他结点的处理一致。 将两个有序链表合并为一个有序链表 已知单链表La和Lb按值非递减排列，归并两表，得到新表Lc也按值非递减排列。 分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要将La或Lb中的元素逐个插入到Lc中即可。 设两个指针pa和pb分别指向La和Lb中的某个元素，若设pa当前所指的元素为a，pb当前所指的元素为b，则当前应插入到Lc中的元素c为： c=ａ(ａ≤ｂ)； c=ｂ(ａ＞ｂ) 很显然，指针pa和pb的初值均为1，在所指元素插入Lc后，pa，pb在La或Lb中顺序后移。 void MergeList(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)); pa.last=La.elem+La.length-1; pb.last=Lb.elem+Lb.length-1; While (pa=pa.last pb=pb.last) { if(*pa=*pb) *pc++=*pa++; else *pc++=*pb++; } while (pa=pa.last ) *pc++=*pa++; while (pb=pb.last) *pc++=*pb++; } void MergeList(LinkList La,LinkList Lb, LinkList Lc) { pa=La-next; pb=Lb-next; Lc=pc=La; 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); } 链表的优点 1、合理利用空间。 2、插入和删