数据结构 教学课件 作者 晋良颖 2.ppt

《数据结构 教学课件 作者 晋良颖 2.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二章线性表B=（A，R）A={a1，a2，……an}R={

2、i=2,3,…..,n}2.1线性表的基本概念2.2顺序存储的线性表2.3链式存储的线性表退出对于一个线性表，经常遇到的一些操作是：1、访问表中任意一个数据元素；2、删除表中任意一个数据元素；3、在表中第i（1<=i<=n-1）个数据元素之前或之后插入一个新数据元素；4、根据某种性质或特征，查找满足要求的数据元素；5、对表中数据元素进行重新排列；6、一些更复杂的操作，例如表的合并，拆分等。1.2顺序存储的线性表顺序存储的线性表的定义如下：#defineMAXSIZE100/*用宏定义一个线性表的最大长度*/typ

3、edefstruct{elemtypeelem[MAXSIZE];/*定义一个存放数据元素的一维数组，元素类型elemtype根据实际需要确定*/intlen;/*线性表的当前长度*/}SQLIST;1、建立一个顺序存储的线性表voidcreatsqlist(SQLIST*L){inti;printf(“请输入线性表元素个数”);scanf("%d",&(*L).len);printf(“请输入%d个元素”,(*L).len);for(i=0;i<(*L).len;i++)scanf("%d",&(*L).elem[i].key);/*这里略去了对数据元素中其他数据项的输入，仅输入其

4、主关键字。*/2、访问表中第i个元素(0<=i<(*L).len))3、求第i个元素的前驱和后继前驱为：L.elem[i-1]，后继为：L.elem[i+1]。若i=0则没有前驱，若i=(*L).len-1，则没有后继。4、查找表中的一个数据元素算法2.1如书第14页所示5、从线性表中删除第i个元素算法2．2如书第14页所示6、在线性表的第i个元素之后插入一个新元素算法2．3如书第15页所示[例1]线性表中的元素以第一个元素的key为界划分成两部分。算法2．4如书第15页所示例1、两个有序表的归并算法2．5如书第16页所示2.3链式存储的线性表2．3．1单链表图2-1单链表的存储结构，可用C

5、语言的结构指针来定义：typedefstructnode{elemtypedata;/*数据元素的类型，可以替换为任何实际所需类型*/structnode*next;/*指示后继结点地址的指针*/}NODE，*NODEPTR;/*定义结点类型和指向结点的指针类型*/#defineLENsizeof(NODE)图2-2、算法2．6如书第18页所示遍历链表的算法：voidtravlist(NODEPTRL)/*L为头结点*/{NODEPTRp;p=L->next;while(p){printf(“%3d”,p->data.key);/*这里仅以输出结点的主关键字代表访问结点*/p=p->next

6、;}printf(“”);}1、查找链表中第i个元素算法2．7如书第19页所示2、第i个元素的前驱和后继及已知地址为p的结点的前驱和后继已知某个结点的地址为p，它的后继结点的地址应为：q=p->next；结点值为：q->data。找它的前驱的算法为：算法2．8如书第20页所示图2-33、查找表中的一个数据元素算法2．9如书第21页所示4、从线性表中删除第i个结点或关键字为某个特定值的结点图2-4(1)、删除链表中第i个结点的算法算法2．10如书第22页所示(2)、删除关键字为aidkey的结点的算法算法2．11如书第22页所示5、在单链的第i个元素之后（或之前）插入一个新元素图2-5算法

7、2．12如书第23页所示例1、链表的表头元素为界把单链表划分成两部分图2-6算法2．13如书第25页所示[例4]两个有序链表的归并算法2．14如书第25页所示静态链表可以如下定义：typedefstructnode{elemtypedata;/*数元素类型可根据需要替换*/intnext;/*指示后继结点的静态指针*/}SLKNODE,SLKLIST[MAXSIZE];图2-7先设计下面这三个函数:（1）、初始化算法(算法2．15)如书第28页所示（2）、分配算法(算法2．16)如书第28页所示（3）、回收算法(算法2．17)如书第28页所示图2-8[例5]利用插入法建立一个图2-7所示的静

8、态链表算法2-18如书第29页所示[例6]建立两个静态链表A和B表示两个集合，算法要求通过改链得到一条新的链表表示集合（A-B）∪（B-A）。算法2.19如书第31页所示算法2.20如书第31页所示2．3．2循环链表图2-92．3．3双向链表双向链表的结点可以如下定义：typedefstructdbnode{elemtypedata;structdbnode*prior;structdbnode*next;}