数据结构第二章线性表

第二章线性表(Linearlist)逻辑结构与基本运算1顺序表2单链表与双向链表3线性表应用4madebyXiong’enLiuSchoolofComputer&InformationScience,FAFU1逻辑结构与基本运算L=(a1,a2,…,ai,…,an)

线性表逻辑结构非空表中有且仅有一个第一个元素非空表中有且仅有一个最后一个元素除第一个元素之外，每个元素均有且仅有一个前趋除最后一个元素外，每个元素均有且仅有一个后继#基本运算的操作体现逻辑结构特点线性表基本运算初始化initiate(L)，建立一个空表求表长length(L)，返回元素个数取第i个元素get(L,i)，其中1≤i≤length(L)元素定位locate(L,e)，返回元素的存储位置插入元素insertion(L,i,e)，其中1≤i≤length(L)+1删除元素deletion(L,i)，其中1≤i≤length(L)判表空empty(L)置表空clear(L)，清空表求前趋prior(L,e)求后继next(L,e)问题1：在线性表L中的元素a之前插入元素b。问题2：删除线性表L中的元素a。

线性表的应用问题---通过基本运算实现insertion(L,a,b)变换成insertion(L,locate(L,a),b)deletion(L,a)变换成

deletion(L,locate(L,a))2顺序表(sequentiallist)

一组地址连续的存储单元依次存储线性表的元素

顺序表数据类型#defineM?//?maybe1024forexampletypedef struct { …… //accordingtotheproblem }element;typedef struct { elementdata[M]; intlen;

}sqList;

voidinitiate(sqList&L) //初始化顺序表

{ L.len=0; }//-------------------------------------------------// intlength(constsqList&L) //求表长

{ returnL.len; }//-------------------------------------------------// voidclear(sqList&L) //置表空

{ L.len=0; }//-------------------------------------------------// boolempty(constsqList&L) //判表空

{ if(L.len==0)returntrue; returnfalse; }

elementget(constsqList&L,inti)//

取第i个元素

{ if(i<1||i>L.len)returnNULL; returnL.data[i-1]; } intlocate(constsqList&L,elemente) //

元素定位

{ intp=0; while(p<L.len&&L.data[p]!=e) p++; if(p<L.len)returnp; return-1; }以上算法的时间复杂度T(n)=O(1)顺序表其它涉及遍历的算法时间复杂度T(n)=O(n)...顺序表第i个元素之前插入新元素e1e2e3...eiei+1...enenen-1ei+1eie012i-1inn-1nlenn+1data

boolinsertion(sqList&L,inti,elementa) //插入元素

{ if(i<1||i>L.len+1)returnfalse; for(intj=L.len;j>=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=a; L.len++; returntrue; }//------------------------------------------------------------// booldeletion(sqList&L,inti) //元素删除

{ if(i<1||i>L.len)returnfalse; for(intj=i;j<L.len;j++) L.data[j-1]=L.data[j]; L.len--; returnture; }顺序表元素插入算法时间复杂度重复的基本操作---元素的移动T(n)=O(n)元素删除算法的时间复杂度T(n)=O(n)问题3：顺序表元素插入或删除算法的时间效率高吗？问题4：实现insert(L,a,b)及deletion(L,a)【例2.1】运用基本运算算法实现清除顺序表中的重复元素。

voidpurge(sqList&L) { inti=0,j; while(i<L.len-1) { j=i+1; while(j<L.len) if(L.data[i]==L.data[j])

deletion(L,j+1); elsej++; i++; } }T(n)=O(n3)3单链表与双向链表(linkedlist)3.1单链表(singlylinkedlist)

每个结点附设1个指向后继结点的指针仅为现有元素分配结点空间，元素删除时释放结点元素插入或删除时，不改变其它结点存储位置单链表结点数据类型

typedef structnode { elementdata; structnode*next; }linknode;

linknode*initiate() //初始化单链表

{ linknode*p; p=newlinknode; p->next=NULL; returnp; } boolempty(linknode*hp) //判空表

{ if(hp->next==NULL)returntrue; returnfalse; }

单链表遍历,T(n)=O(n)//-------------------------------------------------// intlength(linknode*hp) //求表长

{ intn=0; hp=hp->next; while(hp) //while(hp!=NULL) { n++; hp=hp->next; } returnn; } elementget(linknode*hp,inti) //取第i个元素

{ intj=1; hp=hp->next; while(hp&&j<i) { hp=hp->next; j++; } if(hp==NULL||j!=i)returnNULL; returnhp->data; }//-------------------------------------------------// linknode*locate(linknode*hp,elemente)//定位

{ hp=hp->next; while(hp&&hp->data!=e) hp=hp->next; returnhp; }单链表元素结点插入

boolinsertion(linknode*hp,inti,elemente) //单链表元素插入

{ intj=0; linknode*p=hp,*q; while(p!=NULL&&j<i-1)//定位前趋

{ p=p->next; j++; } if(p==NULL||j!=i-1)returnfalse; q=newlinknode; q->data=e; q->next=p->next;

p->next=q; returntrue; }问题5：单链表与顺序表元素插入T(n)=O(n),哪个实际效率更高？问题6：如何实现单链表建立过程？单链表元素结点删除

booldeletion(linknode*hp,inti)//删除元素

{ intj=0; linknode*p=hp,*q; while(p->next!=NULL&&j<i-1)//定位前趋

{ p=p->next; j++; } if(p->next==NULL||j!=i-1)returnfalse; q=p->next;

p->next=q->next;//p->next=p->next->next; deleteq; returntrue; }问题7：实现算法（指定元素的插入或删除） ①boolinsertion(linknode*hp,elementa,elementb); ②booldeletion(linknode*hp,elementa);【例3.1】将两个递增有序的单链表合并成一个递增有序的表。

linknode*merge(linknode*ha,linknode*hb) { linknode*q=ha,*pa=ha->next,*pb=hb->next; while(pa!=NULL&&pb!=NULL) if(pa->data<=pb->data) { q->next=pa; q=pa; pa=pa->next; } else { q->next=pb; q=pb; pb=pb->next; } if(pa!=NULL)q->next=pa; elseq->next=pb; deletehb; returnha; }linknode*merge(linknode*ha,linknode*hb) //改进版{ linknode*q=ha,*pa=ha->next,*pb=hb->next; while(pa&&pb) { while(pa&&pa->data<=pb->data) { q=pa; pa=pa->next; } q->next=pb; while(pb&&pb->data<pa->data) { q=pb; pb=pb->next; } q->next=pa; } if(pa)q->next=pa; elseq->next=pb; deletehb; returnha;}3.2双向链表(doublelinkedlist)问题8：单链表求前趋运算及其T(n)双向链表结点数据类型

typedef structnode { elementdata; structnode*prior,*next; }dlinknode;

dlinknode*initiate() //初始化双向循环链表

{ dlinknode*p; p=newdlinknode; p->prior=p->next=p; returnp; } boolempty(dlinknode*hp) //双向循环链表判空表

{ if(hp->next==hp)returntrue; //if(hp->prior==hp)returntrue; returnfalse; }//-------------------------------------------------// dlinknode*locate(dlinknode*hp,elemente) //双向循环链表元素定位

{ dlinknode*p=hp->next; //p=hp->prior; while(p!=hp&&p->data!=e) p=p->next; //p=p->prior; if(p!=hp)returnp; returnNULL; }双向链表元素结点插入

boolinsertion(dlinknode*hp,inti,elemente) //双向循环链表元素插入

{ intj=0; dlinknode*p=hp,*q; while(p!=hp&&j<i-1)//定位前趋

{ p=p->next; j+