住宅开盘营销策略.ppt

、多重链表的结构二、、广义表的概念二、广义表的存储表示三、广义表的运算一、线性链表的概念线性链表——线性表的链式存储。①存储空间不能满足线性表要求;线性表长n>连续的存储空间大小。②事先不能确定线性表所需要的存储空间的大小如,多项式的表示与运算:A(x)=a0+a1x+a2x+…+anxB(x)=b0+b1x+…+bmx运算前后有哪些项?③线性表长经常发生变化如,空闲单元管理——应用程序经常要取用和释放所占用的存储空间。:①用一组任意的存储单元存储线性表中的元素②存储数据元素之间的关系好处:灵活利用存储空间,提高插入、删除运算效率数据元素的存储映像——结点结点结点的图形表示:???)(指针—存关系—指针域—放元素—,线性表(a1,a2,……ai,……,an),结点链接:pdatapnext空指针二、线性链表及其结构定义结点类型的定义:typedefstructLNode{ElemTypedata;//结点值域structLNode*next;//结点指针}LNode;表结构类型:structLinkList{LNode*head;//定义单链表头指针};a1a2an∧头指针H结点P……、(LinkList*HL){=NULL;//置线性链表的头指针为空}(LinkList*HL){LNode*p=;intlen=0;//len存链表长度while(p){p=p->next;len++;}returnlen;//返回链表长度},在元素b的结点之前插入一个新元素a,如:b∧e…adfb∧eac…headdfchead插入后::?分配一个空闲结点p,令P→data=a;?寻找元素b的前一个结点s;?将结点p插入到s与s→next之间;主要问题:如何寻找元素b的前一个结点s?注意特殊情况:?HL为空表;?b处于第1个结点;?b不在HL中;∧eak…head找不到b?head=NULL链表空dfc∧eab…:voidInsertList(LinkList*HL,ElemTypeb,ElemTypea)//在线性链表HL中的元素b之前插入元素a{LNode*newp,*p,*q;newp=(LNode*)malloc(sizeof(LNode));//分配一个新结点if(!newp){printf(〃内存动态空间分配失败!\n″);exit(1);}newp->data=a;//置a到新结点的值域if(HL->head==NULL‖HL->head->data=b)//处理空表或元{newp->next=HL->head;//素b处于第一个结点的情况HL->head=newp;return;}=HL->head;p=q->next;//从第2个结点开始查找元素bwhile(p!=NULL&&p->data!=b){q=p;p=p->next;}newp->next=q->next;//若找到元素b,把元素a插入到b之前q->next=newp;//若b不在表中,则把元素a插入到链尾。}主要操作——查找元素b所在结点平均时间复杂度为:O(n)若不要查找插入位置(指定插入位置),则时间复杂度为O(1)