数据结构教学课件作者C语言PPT 第2章.ppt

《数据结构教学课件作者C语言PPT 第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表的逻辑结构及其基本操作线性表的顺序存储结构线性表的链式存储结构静态链表应用实例第二章线性表2.1.线性表的逻辑结构及其基本操作线性表是n(n>=0)个相同类型数据元素a0,a1,…，an-1构成的有限序列。形式化定义：Linearlist=(D,R)其中：D0为某个数据对象的集合N为线性表长度线性表的主要操作初始化求长度取元素定位插入删除例：利用线性表的基本运算实现清除L中多余的重复节点。PURGE(Linear_list*L){inti=1,j,x,y;while(i

2、LENGTH(L)){y=GET(L,j);if(x==y)DELETE(L,j);elsej++;}i++;}}2.2线性表的顺序存储结构--顺序表设线性表的基地址为：LOC(a1),ai的存储地址为：LOC(ai)=LOC(a0)＋i*k1<=i<=na0a1aian-1……a0a1aian-1……01n-1Loc(a0)Loc(a0)+kiLoc(a0)+i*kLoc(a0)+(n-1)*k线性表的定义为：typedefintdatatype;//假定线性表元素的类型为整型#definemaxsize1024//假定线性表的最大长度为1024t

3、ypedefstruct{datatypedata[maxsize];intlast;//指向最后结点的位置}sequenlist;1、先定义结构类型，再定义变量名structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}；Structstudentstudent1,student2;C语言中定义结构的方法2、在声明类型的同时定义结构变量structstudent{intnum;charname[20];charsex;intage;floatscore;cha

4、raddr[30];}student1,student2;3、直接定义结构变量struct{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}student1,student2;例：#defineMAXSIZE<最大元素个数>typedefstruct{charName[20];charSex;intAge;floatfareAmount;}datatype;线性表元素的插入intINSERT(sequenlist*L,datatypex,inti){intj;if(((*L).l

5、ast)>=maxsize－1){printf(“overflow”);returnNULL;}\溢出elseif((i<1)

6、

7、(i>((*L).last)＋1){printf(“error”);returnNULL;}\非法位置else{for(j=(*L).last;j>=i-1;j--)(*L).data[j+1]＝(*L).data[j];(*L).data[i-1]＝x;(*L).last＝(*L).last+1;}return(1);}线性表元素的删除intDELETE(sequenlist*L,inti){intj;if(

8、(i<1)

9、

10、(i>(*L).last+1)){printf(“error”);returnNULL;}\非法位置else{for(j=i;j<=(*L).last;j++)(*L).data[j-1]＝(*L).data[j];(*L).last--;\表长减1}return(1);}1、插入n/22、删除(n-1)/23、按序号检索O(1)4、按内容检索n/2算法复杂性分析顺序表的优点：无须为表示节点间的逻辑关系而增加额外的存储空间可以方便的随机存取表中的任一节点顺序表的缺点插入和删除运算不方便由于要求占用连续的存储空间，存储分配只能预先

11、进行2.3线性表的链式存储hh不带头节点的链表带头节点的链表单链表结点的定义：typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;节点的申请p＝malloc(sizeof(linkist));节点的释放free(p);头插法建立单链表①②③④head①建立新节点②向新节点中添入内容③使新节点指向链首④改变头指针s头插法建立单链表linklist*CREATELIST(){charch;linklist*head,*s;head＝NULL;ch＝getc

12、har();while(ch!=‘$’){s＝malloc(sizeof(linklist));s->dat