《冯毅数据结构ch》

实例线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构下一章第二章线性表线性表的应用举例顺序表与链表比较书目自动检索系统书目文件1、各条书目信息之间存在一个对一个的线性关系2、如何在计算机中存储书目信息3、数据操作：查找，插入，删除，修改等线性表实例约瑟夫环(JosephCircle)问题描述：

编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。 请编写程序求出圈的顺序。45961573182132245例：m：密码k：计数出队序列：start526743k=1311、各元素之间存在一个对一个的线性关系2、如何在计算机中存储3、数据操作：查找，删除等约瑟夫环(JosephCircle)在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继线性结构特点定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素特征：有限、序列、同构元素个数n—表长度，n=0空表1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项运算：存取插入删除查找合并分解排序求长度线性表的逻辑结构ADT

List{数据对象：D={ai|aiElemSet,i=1,2,…,n,n≥0},n—表长,n=0,空表

数据关系：R={<ai-1，ai>|ai-1，aiD,i=2，…，n},i为ai在线性表中位序

基本操作：结构初始化操作结构销毁操作

引用型操作(只读操作)

加工型操作(修改操作)}ADT

List线性表的抽象数据类型定义初始化操作：

InitList(&L)

操作结果：构造一个空线性表L结构销毁操作：

DestroyList(&L)

初始条件：线性表L已存在操作结果：销毁线性表L引用型操作：

ListEmpty(L)//线性表判空

初始条件：线性表L已存在操作结果：若L为空表，返回TRUE;否则返回FALSE

ListLength(L)//求线性表的表长

初始条件：线性表L已存在操作结果：返回L中数据元素个数

GetElem(L,i,&e)//求线性表的第i个元素

初始条件：线性表L已存在，且1≤i≤ListLength(L)操作结果：用e返回L中第i个数据元素的值线性表的抽象数据类型定义引用型操作：

LocateElem(L,e,compare())//定位函数

初始条件：线性表L已存在，compare()是元素判定函数操作结果：返回L中第1个与e满足关系compare()的元素的位序。

PriorElem(L,cur_e,&pre_e)//求数据元素的前驱

初始条件：线性表L已存在操作结果：若cur_e是L中元素，且不是第一个，则用pre_e 返回其前驱；否则操作失败，pre_e无定义

NextElem(L,cur_e,&next_e)//求数据元素的后继

初始条件：线性表L已存在操作结果：若cur_e是L中元素,且不是最后一个,则用next_e 返回其后继;否则操作失败，next_e无定义

ListTraverse(L,visit())//线性表遍历

初始条件：线性表L已存在,visit()为某个访问函数操作结果：依次对L中每个元素调用函数visit()。一旦visit()失败，则操 作失败线性表的抽象数据类型定义加工型操作：

ClearList(&L)//线性表置空

初始条件：线性表L已存在操作结果：将L重置为空表

ListInsert(&L,i,e)//插入数据元素

初始条件：线性表L已存在，且1≤i≤ListLength(L)+1操作结果：在L中第第i个位置之前插入元素e,L的长度加1

ListDelete(&L,i,&e)//删除数据元素

初始条件：线性表L已存在且非空，1≤i≤ListLength(L)操作结果：删除L的第i个元素,并用e返回其值,L的长度减1

线性表的抽象数据类型定义

线性表的顺序存储结构an……..ai……..a2a1LLOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现顺序表定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：length表长listsize表容量elem存储区首地址a1a2an01length-1listsize-1elem顺序表实现/*定义动态顺序表*/typedefint

ElemType;#defineLIST_INIT_SIZE100

//线性表存储空间的初始分配量#defineLISTINCREMENT10

//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前表长intlistsize;//当前分配的存储容量//以sizeof(ElemType)为单位}SqList;线性表的基本操作在顺序表中的实现Status

InitList_Sq(SqList&L){L.elem=(ElemType*)malloc(

LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=LIST_INIT_SIZE;return(OK);}顺序表结构初始化：length=0表长listsize=LIST_INIT_SIZE表容量elem存储区基址a1a2an01length-1listsize-1elem算法时间复杂度：O(1)线性表的基本操作在顺序表中的实现int

LocateElem_Sq(SqListL,ElemTypee){}顺序表查找：算法时间复杂度：O(n

)找64ppppppp

513192137566475查找成功L.elemL.lengthL.listsizei=

1;

//i初值为第1元素的位序p=L.elem;

//p指向第一个元素while(i<=L.length&&*p++!=e)i++;if(i<=L.length)returni;elsereturn0;inti;ElemType*p;i=1234567顺序表删除定义：线性表的删除是指将第i（1iL.length）个元素删除，使长度为L.length的线性表

变成长度为L.length-1的线性表需将第i+1至第L.length共（L.length-i)个元素前移线性表的基本操作在顺序表中的实现a1a2aiai+1an12ii+1L.lengtha1a2ai+1ai+2an12ii+1L.length-1L.lengthai+1ai+2an顺序表删除线性表的基本操作在顺序表中的实现Status

ListDelete_Sq(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;

p=&(L.elem[i-1]);//p指向被删除元素

e=*p;//被删除元素赋给e

q=L.elem+L.length-1;//q指向表尾元素for(++p;p<=q;p++)*(p-1)=*p;--L.length;//表长减1return(OK);}顺序表删除算法：ElemType*p,*q;a1a2...ai-1an...aiai+1L.elempqpai+1an...pp线性表的基本操作在顺序表中的实现判断i值合法性元素依次前移算法时间复杂度：O(n

)设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低顺序表删除算法评价：线性表的基本操作在顺序表中的实现顺序表插入定义：线性表的插入是指在第i（1iL.length+1）个元素之前插入一个新的元素x，使长度为L.length的线性表变成长度为L.length+1的线性表需将第i至第n共（L.length-i+1)个元素后移线性表的基本操作在顺序表中的实现a1a2aiai+1an12ii+1L.lengthL.length+1anai+1aix顺序表插入线性表的基本操作在顺序表中的实现Status

ListInsert_Sq(SqList&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;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指向插入位置,p指向表尾元素for(

;p>=q;p--)*(p+1)=*p;

*q=e;++L.length;//线性表长度加1return(OK);}顺序表插入算法：ElemType*q,*p,*newbase;线性表的基本操作在顺序表中的实现判断i值合法性判断是否溢出元素后移插入算法时间复杂度：O(n

)p=&(L.elem[L.length-1])设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：顺序表插入算法评价：线性表的基本操作在顺序表中的实现优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序表特点a1a2...aian...链式存储结构……a1a2aian逻辑结构a1a3...an顺序存储结构a2ai...线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置线性表的链式存储结构数据域指针域结点^ZHAOQIANSUNLIZHOUWUZHENGWANGH例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针线性表的链式存储结构数据域指针域实现typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;LNode*h,*p;datanextp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).nextp->next表示p指向结点的指针域生成一个LNode型新结点：p=(LNode*)malloc(sizeof(LNode));系统回收p结点：free(p)定义：结点中只含一个指针域的链表叫~，也叫线性链表单链表头结点：在单链表第一个结点前附设一个结点叫～头结点指针域为空表示线性表为空La1a2头结点an

^…...L空表^头指针La1a2a3an……^头指针LinkList

L;单链表GetElem(L,i,&e)

：取第i个数据元素。若存在，其值赋给e并返回OK；否则返回ERROR算法思路ppp头指针La1a2a3an……^Status

GetElem_L(LinkListL,inti,ElemType&e){

p=L->next;//p指向第一个元素

j=1;//j做计数器while()//顺链查找{}if()//若i不存在returnERROR;

e=p->data;//取得第i个元素return(OK);}LNode*p;

intj;p==NULL||j>ip!=NULL&&j<ip=p->next;j++;算法时间复杂度：O(n)单链表基本操作LocateElem_L(L,e)

：查找单链表中是否存在结点e，若有则返回指向e结点的指针；否则返回NULL算法描述LNode*LocateElem_L(LinkListL,ElemTypee){ LNode*p;

p=L->next; while()

p=p->next; return(p);}pppp&&p->data!=eLa1a2a3an……^单链表基本操作While循环中语句频度为若找到结点e，为结点e在表中的位序否则，为n算法评价单链表基本操作LocateElem_L(L,e)

：查找单链表中是否存在结点e，若有则返回指向e结点的指针；否则返回NULL算法描述LNode*LocateElem_L(LinkListL,ElemTypee){ LNode*p;

p=L->next; while()

p=p->next; return(p);}p&&p->data!=eListInsert(&L,i,e)

：在第i个元素前插入e。若i非法，返回ERROR；否则返回OK算法思路考虑：在线性表两个数据元素a和b间插入e，已知p指向apabess->next=p->next;p->next=s;s=(LinkList)malloc(sizeof(LNode));s->data=e;思考：指针修改顺序是否可交换？特别注意：修改指针的语句次序一定要小心处理，否则会出现意想不到的错误。单链表基本操作ListInsert(&L,i,e)

：在第i个元素前插入e。若i非法，返回ERROR；否则返回OK单链表基本操作……a1

ai

an^L

ai-1

ai+1

p①

e

s②③④(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)StatusListInsert_L

(LinkList&L,int

i,ElemTypee){LNode*s,*p;intj;

}p=L;j=0;while(p&&j<i-1){p=p->next;j++;}if(!p||j>i-1)returnERROR;returnOK

;

s->next=p->next;

p->next=s;

s=(LinkList)malloc(sizeof(LNode));s->data=e;ListDelete(&L,i,&e)

：删除第i个元素，用e返回。若i非法，返回ERROR；否则返回OK算法思路考虑：在单链表中删除b，已知p指向apabcqq=p->next;p->next=q->next;free(q);e=q->data;单链表基本操作ListDelete(&L,i,&e)

：删除第i个元素，用e返回。若i非法，返回ERROR；否则返回OK单链表基本操作a1

…ai

an^…L

ai-1

ai+1

p①q②③StatusListDelete_L

(LinkList&L,inti,ElemType&e){LNode*q,*p;intj;

}p=L;j=0;while(p->next&&j<i-1){p=p->next;j++;}if(p->next==NULL||j>i-1)returnERROR;q=p->next;returnOK

;

p->next=q->next;

e=q->data;

free(q);ClearList(&L)

：将单链表重置为一个空表算法思路单链表基本操作voidClearList_L

(LinkList&L){LNode*p;

}while(L->next){}p=L->next;

L->next=p->next;

free(p);L->next=p->next;p=L->next;free(p);p①③②a1

ai

an^…L

a2

ai+1

…CreatList(&L,n)

：创建有n个元素的单链表算法思路头插法（带头结点）a1

…an-1

an^p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);pp->next=L->next;L->next=p;voidCreateList_L

(LinkList&L,intn)//逆序输入n个元素的值，建立带头结点的单链表L{LNode*p;inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;for(i=n;i>0;i--){

p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);

p->next=L->next;

L->next=p;}}生成头结点循环插入单链表基本操作CreatList(&L,n)

：创建有n个元素的单链表算法思路尾插法（带头结点）p=(LinkList)malloc(sizeof(LNode));p->next=NULL;scanf("%d",&p->data);rear->next=p;rear=p;rearreara2^pan^

…voidCreateList_L_B

(LinkList&L,intn)//顺序输入n个元素的值，建立带头结点的单链表L{LNode*p,*rear;inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;

rear=L;for(i=n;i>0;i--){

p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=NULL;

rear->next=p;rear=p;}}生成头结点循环插入单链表基本操作它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除不需移动元素指针占用额外存储空间单链表的表长是一个隐含的值在链表中，元素的“位序”概念淡化，结点的“位置”概念加强不能随机存取，查找速度慢在单链表的最后一个元素之后插入元素时需遍历整个链表单链表特点静态链表(StaticLinkList)用一维数组来实现链式存储结构ZHAOQIANSUNWANGWUZHENGZHOUdatacur01234567891011123456780LI在元素LI后插入元素SHISHI95删除元素ZHENG8#defineMAXSIZE100typedefstruct{

ElemTypedata;intcur;}SLinkList[MAXSIZE];游标cursor预先分配较大空间插入、删除不需移动元素，仅修改指针循环链表(CircularLinkedList)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状L空表特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->next==NULL循环链表p或p->next==La1a2a3an……L双向链表（DoubleLinkedList）单链表具有单向性的缺点结点定义typedefstructDuLNode{ElemTypedata;structDuLNode*prior,*next;}DuLnode,*DuLinkList;priordatanextL空双向循环链表：非空双向循环链表：LABbcap双向循环链表删除p->prior->next=p->next;p->next->prior=p->prior;free(p);双向循环链表删除……L

a1

ai-1

ai

ai+1

an

时间复杂度：O(n)StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e)//删除带头结点的双向循环链表L中的第i个元素{DuLNode*p;if(!(p=GetElemP_DuL(L,i)))returnERROR;//i值非法

p->prior->next=p->next;

p->next->prior=p->prior;

e=p->data;free(p);returnOK;}p①eSbap双向循环链表插入s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

s=(DuLinkList)malloc(sizeof(DulNode));

s->data=e;StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee)//在带头结点的单链表L的第i个元素之前插入新元素e{DuLNode*p,*s;if(!(p=GetElemP_DuL(L,i)))returnERROR;//i值非法

if(!(s=(DuLinkList)malloc(sizeof(DulNode))))returnERROR;s->data=e;

s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}双向循环链表插入p……L

a1

ai-1

ai

ai+1

an

s

e

时间复杂度：O(n)s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;eSbap思考：

s->next=p;

p->prior->next=s;s->prior=p->prior;

p->prior=s;

p->prior=s;s->prior=p->prior;

p->prior->next=s;

s->next=p;s->prior=p;

p->next=s;

s->next=p->next;

p->next->prior=s;思考：eSabps->prior=p;

s->next=p->next;

p->next->prior=s;

p->next=s;线性表的应用举例一元多项式的表示及相加一元多项式的表示：可用线性表P表示顺序存储p0p1...p2pn...pi……Head

单链表方式存储p0

p1

pi

pn^但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示

Head一元稀疏多项式单链表方式存储p1

e1p2

e2…pi

ei…pm^em一元多项式的表示ADT

Polynomial{数据对象：D={ai|aiTermSet,i=1,2,…,m,m≥0,TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}

数据关系：R={<ai-1,ai>|ai-1，aiD,i=2，…，n,且ai-1中的指数值＜ai中的指数值

}

基本操作：……}ADT

Polynomial一元多项式的抽象数据类型定义如下：基本操作：CreatPolyn(&P,m)

操作结果：输入m项的系数和指数，建立一元多项式P初始条件：一元多项式P已存在操作结果：销毁一元多项式P初始条件：一元多项式P已存在操作结果：打印输出一元多项式PDestroyPolyn(&P)PrintPolyn(&P)AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在操作结果：多项式相加运算,即:Pa=Pa＋Pb，并销毁PbSubtractPolyn(&Pa,&Pb)

MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在操作结果：多项式相减运算,即:Pa=Pa－Pb，并销毁Pb初始条件：一元多项式Pa和Pb已存在操作结果：多项式相乘运算,即:Pa=Pa×Pb，并销毁Pb一元多项式ADT的实现typedefstruct{floatcoef;intexp;}term,ElemType;coefexpnexttypedefLinkListpolynomial;voidCreatPolyn(polynomial&P,intm);

voidDestroyPolyn(polynomial

&P);voidPrintPolyn(polynomial

P

);voidAddPolyn(polynomial

&Pa,polynomial

&Pb);voidSubtractPolyn(polynomial

&Pa,polynomial

&Pb);voidMultiplyPolyn(polynomial

&Pa,polynomial

&Pb);intPolynLength(polynomial

P

);一元多项式相加A(x)=7+3x+9x8+

5x17-8x100B(x)=8x+22x7-9x8C(x)=A(x)+B(x)=7+11x+22x7+5x17-8x100+headA703198517-8^100headB81227-9^8coefexp设qa,qb分别指向A,B中某一结点，其初值是第一结点比较qa->exp与qb->expqa->exp<qb->exp:qa->exp>qb->exp:qa->exp==qb->exp:0：0：直到qa或qb为NULL若qb==NULL,结束若qa==NULL,将B中剩余部分连到A上即可运算规则qa结点是和多项式中的一项qa后移,qb不动qb结点是和多项式中的一项将qb插在qa之前,qb后移,qa不动系数相加从A表中删去qa,释放qa,qb,qa,qb后移修改qa系数域,释放qb,qa,qb后移算法描述voidAddPoly(polynomial&Pa,polynomial&Pb){Linkqa,qb,ha,hb;ElemTypesum;

ha=Pa;qa=Pa->next;hb=Pb;qb=Pb->next;while(qa&&qb){if(qa->data.exp<qb->data.exp){}elseif(qa->data.exp>qb->data.exp){