1.设线性表存放在向量 Alarrsize的前num个分量中,且递增有序。试写一算法,将ⅹ插入到线性表 的适当位置上,以保持线性表的有序性。并且分析算法的时间复杂度。 int insert(int Alarrsize], int num, int x) if (num==arrsize) return (-1); iEnum-I while(1>=0&&A[]>x) Al+IFAL A[+ll num++ return( 1); 2已己知一顺序表A,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素 typedef struct( datatype datalmaxsize int last iseqlist void delete(seeqlist *A) 1=0 while(ilast) while(klast&&A->data[i]==A->data[]) k++ n=k--1; for g=k;jlast;j ++ A->data[j-n]=A->dataL A->last=A->last-n 1++ 3写一个算法,从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素,要求以较高的效率来 实现
⒈设线性表存放在向量 A[arrsize]的前 num 个分量中，且递增有序。试写一算法，将 x 插入到线性表 的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 int insert(int A[arrsize],int num,int x) { if (num==arrsize) return(-1); i=num-1; while(i>=0&&A[i]>x) { A[i+1]=A[i]; i--; } A[i+1]=x; num++; return(1); } ⒉已知一顺序表 A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。 typedef struct{ datatype data[maxsize]; int last; }seqlist; void delete(seeqlist *A) { i=0; while (ilast) { k=i+1; while (klast&&A->data[i]==A->data[k]) k++; n=k-i-1; for (j=k;jlast;j++) A->data[j-n]=A->data[j]; A->last=A->last-n; i++; } } ⒊写一个算法，从一给定的顺序表 A 中删除值在 x~y(x<=y)之间的所有元素，要求以较高的效率来 实现
typedef struct( datatype data[maxsize]; int last. 3seqlist void delete(seeqlist *A, int x, int y) for(i=0; Klast; 1++) if(A->data[i]>x&&A->data[i]y Ai-J=] A->last=A->last-j 4线性表中有n个元素,每个元素是一个字符,现存于向量R[n]中,试写一算法,使R中的字符按 字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小 int fch(char c) if(c>='a'&&c='A'&&c=0&&c<=9) return(1) else return(0) void process(char r[n]) low=0; high=n-1 while(low<high)
typedef struct{ datatype data[maxsize]; int last; }seqlist; void delete(seeqlist *A,int x,int y) { j=0; for (i=0;ilast;i++) if (A->data[i]>x&&A->data[i]last= A->last-j; j=0; } } ⒋线性表中有 n 个元素，每个元素是一个字符，现存于向量 R[n]中，试写一算法，使 R 中的字符按 字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。 int fch(char c) { if (c>='a'&&c='A'&&c='0'&&c<='9') return (1); else return (0); } void process(char R[n]) { low=0;high=n-1; while (low<high)
while (lowdata[0I
{ while (lowdata[0];
for(k-l; klast; k++) L->data[k-1=L->data[k] ->data[L->last=x; else for(i=l; Kdata L->last]; for(k=L->last-1; k>=0; k--) L->data[k+1=L->data(k] ->data[0=x 6.已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x的结点插入到 表L中,使得L仍然有序。并且分析算法的时间复杂度 typedef struct node int data iNode, *linklist; linklist insert(linklist L, int x) while(p->next&&x>p->next->data) p=p->next; snew Inode s->data=x S->next=p->next lext=s return (L) 7假设有两个已排序的单链表A和B,编写一个算法将它们合并成一个链表C而不改变其排序性 typedef struct node dataty pe data struct node * next iNode, linklist
for (k=1;klast;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } else for(i=1;idata[L->last]; for (k=L->last-1;k>=0;k--) L->data[k+1]=L->data[k]; L->data[0]=x; } } ⒍已知带头结点的单链表 L 中的结点是按整数值递增排列的，试写一算法，将值为 x 的结点插入到 表 L 中，使得 L 仍然有序。并且分析算法的时间复杂度。 typedef struct node{ int data; struct node *next; }lnode,*linklist; linklist insert(linklist L,int x) { p=L; while (p->next&&x>p->next->data) p=p->next; s=new lnode; s->data=x; s->next=p->next; p->next=s; return(L); } ⒎假设有两个已排序的单链表 A 和 B，编写一个算法将它们合并成一个链表 C 而不改变其排序性。 typedef struct node{ datatype data; struct node *next; }lnode,linklist;
linklist combine(linklist A, linklist B) C=A: rc=C pa=A-next, t delete B while(pa&&pb) if(pa->datadata) rc->next-pa rc-pa, pa=>next eIse rc->next=pb p if rc-nextpa else rc->next=pb return(C) 8假设长度大于1的循环单链表中,既无头结点也无头指针,p为指向该链表中某一结点的指针,编 写一个算法删除该结点的前驱结点。 linklist delete(linklist p) qp while(q->next->next!=p) q q->next rq->next q->nextp delete r return(p);
linklist combine(linklist A,linklist B) { C=A;rc=C; pa=A->next; pb=B->next; delete B; while (pa&&pb) if (pa->datadata) { rc->next=pa; rc=pa; pa=pa->next; } else { rc->next=pb; rc=pb; pb=pb->next; } if (pa) rc->next=pa; else rc->next=pb; return(C); } ⒏假设长度大于 1 的循环单链表中，既无头结点也无头指针，p 为指向该链表中某一结点的指针，编 写一个算法删除该结点的前驱结点。 linklist delete(linklist p) { q=p; while (q->next->next!=p) q=q->next; r=q->next; q->next=p; delete r; return(p);
9.已知两个单链表A和B分别表示两个集合,其元素递增排列,编写一个算法求出A和B的交集C, 要求c同样以元素递增的单链表形式存储 linklist process (linklist A, linklist B) pa=A->next pb=B->next pc=C=new Inode while(pa&&pb) if(pa->datadata pa=pa->next; eIse if(pa->data>pb->data pb=pb->next Snew Inode, S->data=pa->data pc->next=s pap pb=pb->next return(c) 1设有一个双向链表,每个结点中除有 prior、data和next域外,还有一个访问频度freq域, 在链表被起用之前,该域其值初始化为零。每当在链表进行一次 Locat a(L,x)运算后,令值为x的结点 中的￡req域增1,并调整表中结点的次序,使其按访问频度的递减序列排列,以便使频繁访问的结点总 是靠近表头。试写一个算法满足上述要求的 Locate(L,x)算法。 typedef struct anode datatype data; int freq struct dnode prior, "next inode, dlinklist
} ⒐已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，编写一个算法求出 A 和 B 的交集 C， 要求 C 同样以元素递增的单链表形式存储。 linklist process(linklist A,linklist B) { pa=A->next; pb=B->next; pc=C=new lnode; while (pa&&pb) { if (pa->datadata) pa=pa->next; else if (pa->data>pb->data) pb=pb->next; else { s=new lnode; s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pb=pb->next; } } pc->next=NULL; return(c); } ⒑设有一个双向链表，每个结点中除有 prior、data 和 next 域外，还有一个访问频度 freq 域， 在链表被起用之前，该域其值初始化为零。每当在链表进行一次 Locata(L,x)运算后，令值为 x 的结点 中的 freq 域增 1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总 是靠近表头。试写一个算法满足上述要求的 Locata(L,x)算法。 typedef struct dnode{ datatype data; int freq; struct dnode *prior,*next; }dnode,dlinklist;
dlinklist locate(dilnklist L, datatype x) p=L->next while(p&&p->data!=x p=p->next if(p) return(NULL) p->freq++ while(p->prior!=L&&p->prior->freqp->freq) k=p-→ prior->data; p->prior->data=p->data p->data=k k=p->prior->freq p->prior->freqp->freq p->freq=k; p=p->prior; return(p)
dlinklist locate(dilnklist L,datatype x) { p=L->next; while (p&&p->data!=x) p=p->next; if (!p) return(NULL); p->freq++; while (p->prior!=L&&p->prior->freqfreq) { k=p->prior->data; p->prior->data=p->data; p->data=k; k=p->prior->freq; p->prior->freq=p->freq; p->freq=k; p=p->prior; } return(p); }