线性表 定义顺序存储结构基本操作两种特殊的线性表栈队列.ppt
线性表 定义顺序存储结构基本操作两种特殊的线性表栈队列 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望数据结构与算法设计数据结构与算法设计第5次2012.5顺序存储结构的优缺点顺序存储结构的优缺点l优点l逻辑相邻，物理相邻l可随机存取任一元素l存储空间使用紧凑l缺点l插入、删除操作需要移动大量的元素,平均移动n/2l预先分配空间需按最大空间分配，利用不充分l表容量难以扩充第三章链表第三章链表1:单向链表链表链表 内容提要内容提要l单向链表l循环链表l双向链表l稀疏矩阵的表示单向链表单向链表l每个元素(表项)由结点(Node)构成typedef struct LNodeDatatype data;struct LNode*next;l线性结构结点可以不连续存储,表可扩充单向链表的存贮映像单向链表的存贮映像指针操作指针操作lLNode*p,*q;lp-data;p-next;lq=new LNode;lq=p;lq=p-next;(q指向后继)lp=p-next;(指针移动)lp-next=q;(链指针改接)lp-next=q-next;(?)链表结点的基本运算链表结点的基本运算lVoid SetNode(LNode*front);/构造函数,结点的next置NULLlNode*NextNode(LNode*ptr);/返回后继指针lVoid InsertAfter(LNode*ptr,Datatype item);/在结点*ptr插入lVoid DeleteAfter(LNode*ptr);/删除结点后的一个结点.在结点后插入数据指针的变化在结点后插入数据指针的变化newnode-next=current-next;current-next=newnode；lVoid InsertAfter(LNode*ptr,Datatype item)LNode *q;q=new LNode;If(q=NULL)错误信息 printf()q-next=ptr-next;q-data=item;ptr-next=q;在结点后删除数据指针的变化在结点后删除数据指针的变化q=p-next;If(q!=NULL)p.next=q.next;Delete q;单链表的定义单链表的定义l多个类表达一个概念(单链表)链表结点(ListNode)链表(List)Typedef structLNode *front;int Size;/并非必要的成员 LList;lVoid SetLList(LList*L);lVoid FreeList(LList*L);lInt LListSize(LList*L);lInt LListEmpty(LList*L);lInt LListLocate(LList*L,DataType item);l。求线性表的长度求线性表的长度lint LListSize(LList*L)Lnode*p=L;int k=0;while(p)k+,p=p-next;return k;/时间复杂度O(n)关于插入的讨论关于插入的讨论l已知结点之后插入,时间复杂度O(1)l已知结点之前插入?需要查找前驱,时间复杂度为O(n),如果指向第一个结点,要修改头指针Void LListInsertB(LList*L,LNode*p,LNode*s)LNode*q;if(p=L)s-next=L;L=s;else q=L;while(q-next!=p)q=q-next;q-next=s;s-next=p;带表头结点的单链表带表头结点的单链表l表头结点位于表的最前端，本身不带数据，仅标志表头l设置表头结点的目的是统一空表与非空表的操作,简化链表操作的实现l头结点:表中的第一个结点，数据域为空l最后一个结点的指针为 NULLl开始结点：第一个数据元素的结点l头指针：指向头结点的指针带表头结点的单链表插入带表头结点的单链表插入l在带表头结点的单链表第一个结点前插入新结点Newnode-next=p-next ;p-next=newnode从带表头结点的单链表中删除第一个从带表头结点的单链表中删除第一个结点结点q=p-link;p-link=q-link;delete q;lVoid LListSetData(LList*L,Datatype item,int pos)int i;LNode*ptr;如果pos不合法，退出 否则 ptr=NextNode(L-front);for(i=0;idata=iteml循环链表循环链表l循环链表是单链表的变形。l循环链表最后一个结点的link指针不为NULL,而是指向了表的前端l为简化操作，在循环链表中往往加入表头结点。l循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。编程操作编程操作l建立工程l建立.h数据结构的定义，基本运算声明基本运算的函数实现l建立.c实例实例lNode.htypedef int DataTypetypedef struct node DataType data;struct node*next;Node;Void SetNode(Node*front);Void SetNode(Node*front)front-next=NULL;lTest1.cl#include“node.h”Void main()int i,j;Node front,*prevptr,*ptr;SetNode(&front);ptr=&front;for(i=1;ifront=new LNode;if(Q-front=NULL)err;SetNode(Q-front);Q-rear=Q-front;lvoid EnQueue(LQueue *Q,DataType item)InsertAfter(Q-rear,item);Q-rear=NextNode(Q-rear);lvoid OutQUEUE (LQueue *Q)if (EMPTY(Q)error;else temp=Q-front-next;Q-front-next=temp-next;delete temp;if (Q-front-next=NULL)Q-rear=Q-front;上机练习上机练习l用链表实现josephus问题，王p177 每次让指针移动m次，然后删除指向的节点project1：多项式类：多项式类l多项式的各种运算l加，减，乘，除l简单多项式的其他特殊运算l二次多项式的求根计算l其他project1：多项式：多项式ln 阶多项式Pn(x)有 n+1项lc0,c1,c2,cnl指数按升幂排多项式的存储表示多项式的存储表示l静态数组int degree;float coefmaxDegree+1;以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式不经济l动态数组typedef struct int degree;float*coef;Polynomial;构造函数:Void SetPoly(Polynomial*poly,int sz)Poly-degree=sz;Poly-coef=new float degree+1;多项式的链表表示多项式的链表表示l在多项式的链表表示中每个结点三个数据成员：l优点l多项式的项数可以动态地增长l不存在存储溢出问题l插入、删除方便，不移动元素。基本操作基本操作lPolynomial();/构造函数lint IfZeroPoly();/判是否零多项式lfloat Coef(int e);/返回某次数的系数lint MaxExp();/返回最大指数lPolynomial Add();/加法lPolynomial Minus();/减法lPolynomial Mult();/乘法lfloat Eval(float x);/求值要求要求l采用链式结构l写文档l测试说明l截止日期:待定
