chap002线性表.ppt

第二章 线性表;;;2.1 线性表的类型定义（线性表的逻辑结构）;;;;线性表上的基本操作;;;;;;;;;;;;;例 2-1;;;;例 2-2;;;;;;2.2 线性表的顺序表示和实现;;a1;;线性表的基本操作在顺序表中的实现;线性表的基本操作在顺序表中的实现;例如：顺序表; int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { // 在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回 0 } // LocateElem_Sq;线性表的基本操作在顺序表中的实现;内存;status ListInsert_Sq(sqlist L,int i,ElemType e){ If (i1||iL.length+1) return ERROR; If (L.length=L.listsize){ Newbase =(elemtype*)realloc(L.elem, (L.listsize+listincrement)*sizeof(ElemType)); if (!newbase) exit (overflow); l.elem =newbase; l.listsize+=listincrement; } q=(L.elem[i-1]); // q 指示插入位置 for (p=(L.elem[L.length-1]);p=q;--p) *(p+1)=*p; // 插入位置及之后的元素右移 *q=e; // 插入e ++L.length; // 表长增1 return OK; };算法时间复杂度T(n);;内存;;算法评价;;2.3线性表的链式表示和实现;ZHAO;线性链表;data; 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。;; 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。 ; Status GetElem_L(LinkList L, int i, ElemType e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L;单链表的操作; 因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。; Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L;单链表的操作; 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。; Status ListDelete_L(LinkList L, int i, ElemType e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete_L;动态建立单链表算法：;void CreateList_L(LinkList L, int n) { // 逆序输入 n 个数据元素，建立带头结点的单链表 } // CreateList_L;单链表特点;重新定义带头结点的单链表类型;循环链表(circular linked list);;双向链表;双向循环链表;双向链表的操作;ai-1;;ai-1;ai-1;;ai-1;2.4 线性表的应用——一元多项式的表示及相加;;;;设p,q分别指向A,B中某一结点，p,q初值是第一结点;q;void add_poly(linklist *pa,linklist *pb) //一元多项式的表示及相加 linklist *p,*q,*u,*pre; int x; p=pa-next; q=pb-next; pre=pa; //pre总是指向待进入链表的节点的前驱 while((p!=NULL) ((q!=NULL)) //结束条件 if(p-expq-exp){ //p指数小于q指数 pre=p; p=p-next; } else if(p-exp==q-exp){//相等 x=p-coef+q-coef; //系数相加 if(x