算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)

Presentation on theme: "算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)"— Presentation transcript:

1 算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)
L.elem=new ElemType[msize]; L.listsize=msize; //顺序表的最大容量 L.length=0; // 顺序表初始时的元素数是0 }// end InitList_sq

2 算法3.4 void DestroyList_sq(SqList &L) {//销毁顺序表L
delete [] L.elem; // 释放数组空间 L.length=0; L.listsize=0; }// end DestroyList_sq

3 算法3.5 /3.6/ 3.7 bool ListEmpty_sq(SqList L) { return (L.lenth==0); }
bool ListFull_sq(SqList L) return (L.lenth==L.listsize); int ListLength_sq(SqList L) return L.lenth;

4 算法3.8 int LocateItem_sq(SqList L,Elemtype e)
for(i=1;i<=L.length;i++) //依次查找每个元素 if(L.elem[i-1]==e)return i; //找到位序为i的元素 return 0; //没有找到值为e的元素 }// end LocateItem_sq

5 算法3.9 void GetItem_sq(SqList L,int i,Elemtype &e)
{//将顺序表L中位序为i的元素值赋予e. e=L.elem[i-1]; }// end GetItem_sq

6 算法3.10 void ListInsert_sq(SqList &L，int i，Elemtype e)
{//在顺序表L中位序为i的元素前插入一个新的元素e //同时需要考虑i的合法性和满状态 if(i<1||i>L.length+1){ErrorMsg(“i值非法！”);return;} if(L.length==L.listsize)Increment(L); //当前L已满 for(j=L.length-1;j>=i-1;j--) //由后往前逐个后移元素 L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; //在L.elem[i-1]放入e ++L.length; }// end ListInsert_sq

7 算法3.11 #define LIST_INC_SIZE 20
void Increment(SqList &L，int inc_size=LIST_INC_SIZE) { //增加顺序表L的容量为listsize+inc_size ElemType *a; a=new ElemType[L.listsize+inc_size]; // 给a指针分配内存 if(!a){ErrorMsg(“分配内存错误！”);return;} for(i=0;i<L.length;i++)a[i]=L.elem[i]; // 将原数组的元素复制到新数组 delete [] L.elem; // 释放原数组空间 L.elem=a; // 将新的数组赋予顺序表的指针 L.listsize+=inc_size; // 顺序表的容量增加inc_size }// end ListInsert_sq

8 算法3.12 void ListDelete_sq(SqList &L，int i，Elemtype &e)
{//从顺序表L中删除位序为i的元素并把值赋予e if(i<1||i>L.length){ErrorMsg(“i值非法！”);return;} e=L.elem[i-1]; //保存L.elem[i-1]到e for(j=i;j<=L.length-1;j++) //由前往后逐个前移 L.elem[j-1]=L.elem[j]; L.length--; }// end ListDelete_sq

9 算法3.13 void Union_sq(SqList &La，SqList &Lb)
{//实现顺序表A和B所表示的集合的并，结果放在A，销毁B for(i=0;i<Lb.length;i++){ //逐个处理Lb的元素 e=Lb.elem[i]; //取Lb中第i个元素 j=0; while(j<La.length&&La.elem[j]!=e)++j; //在La中查找e if(j==La.length){ //La中没有找到e La.elem[La.length]=e; //e插入到La的最后 La.length++; //La长度增加1 }//if }//for delete [] Lb.elem; //释放Lb内存 Lb.length=0;Lb.listsize=0; }// end Union_sq

10 算法3.25 void exchange(SqList &L,int m,int n) {//实现L中前m个元素和后n个元素的交换。
for(k=1;k<=n;k++){ //对b1,b2,...,bn逐个处理 w=L.elem[m+k-1]; //移出bk for(j=m+k-1;j>=k;j--) //a1,a2,...am均后移 L.elem[j]=L.elem[j-1]; L.elem[k-1]=w; //bk放到a1前 }//for }// end exchange

11 算法3.26 void invert(ElemType &R[],int s,int t) {//实现数组R中从下标s到t的逆置
for(k=s;k<=(s+t)/2;k++){ w=R[k]; //交换R[k]和R[t-k+s] R[k]=R[t-k+s]; R[t-k+s]=w; }//for }// end invert

12 算法3.27 void exchange2(SqList &L,int m,int n)
{//利用invert实现L中前m个元素和后n个元素的交换 invert(L.elem,0,m+n-1); invert(L.elem,0,n-1); invert(L.elem,n,m+n-1); }// end exchange2

13 算法3.14 void InitList_L(LinkList &L) {//初始化链表L L=NULL;
}// end InitList_L

14 算法3.15 Int ListLength_L(LinkList L) {//求链表L的长度 p=L;k=0; while(p){
k++;p=p->next; }//while return k; }// end ListLength_L

15 算法3.16 {//在链表L中查找元素e p=L; while(p&&p->data!=e)p=p->next;
LNode * LocateItem_L(LinkList L,ElemType e) {//在链表L中查找元素e p=L; while(p&&p->data!=e)p=p->next; return p; }// end LocateItem_L

16 算法3.17 void ListInsert_L(LinkList &L,LNode *p，LNode *s)
{//在链表L中，在p所指结点前插入s所指的结点 if(p==L){ //p是第一个结点 s->next=L; L=s; }//if else { //p不是第一个结点 q=L; while(q&&q->next!=p)q=q->next;//找后继是p的结点 if(q){q->next=s;s->next=p;} //在p前插入s else ErrorMsg(“p不是L中的结点”); }//else }// end ListInsert_L

17 算法3.18 void ListDelete_L(LinkList &L,LNode *p，ElemType &e)
{//在链表L中，删除p所指结点 if(p==L)L=p->next; //p是第一个结点 else { //p不是第一个结点 q=L; while(q&&q->next!=p)q=q->next;//找后继是p的结点 if(q)q->next=p->next; //使p的原前驱直接指向p的后继 else ErrorMsg(“p不是L中的结点”); // p不在L中 }//else e=p->data;delete p; //保存被删除的元素值，释放空间 }// end ListDelete_L

18 算法3.24 void Purge(SqList &L) {//把顺序有序表L中相同的元素删除。 i=-1;j=0;
while(j<L.length){ if(j==0||L.elem[j]!=L.elem[i]) L.elem[++i]=L.elem[j]; j++; }//while L.length=i+1; }// end Purge

19 算法3.28 void union_ord(LinkList &La,linkList &Lb)
{//有序循环链表La、Lb表示的集合A、B，求表示集合A∪B的链表Lc，结果存储在La pa=La->next->next; pb=Lb->next->next; rc=La->next; ha=La->next; hb=Lb->next; //保留头结点指针 while(pa!=ha && pb!=hb){ if(pa->data < pb->data){ //pa所指结点值小 rc->next=pa;rc=pa;pa=pa->next; //pa链入Lc } else if(pa->data > pb->data){ //pb所指结点值小 rc->next=pb;rc=pb;pb=pb->next; //pb链入Lc else{ rc->next=pa;rc=pa;pa=pa->next; //pa链入Lc qb=pb;pb=pb->next;delete qb; //删除pb所指结点 }//while if(pb==hb)rc->next=pa; //Lb结束直接链入La剩余部分 rc->next=pb; //直接链入Lb剩余部分 Lb->next=ha;La=Lb; }//else delete hb; //释放Lb头结点,结果在La中 }// end union_ord