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(i<A->last) while(k<=A->last&&A->data[i]==A->data[]) k++ n=k--1; for g=k;j<=A->last;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 (i<A->last) { k=i+1; while (k<=A->last&&A->data[i]==A->data[k]) k++; n=k-i-1; for (j=k;j<=A->last;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; K<=A->last; 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<=zlc>='A'&&c<='Z) return(1) return(O) int fnum(char c) if(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;i<=A->last;i++) if (A->data[i]>x&&A->data[i]<y) j++; else { A[i-j]=A[i]; A->last= A->last-j; j=0; } } ⒋线性表中有 n 个元素，每个元素是一个字符，现存于向量 R[n]中，试写一算法，使 R 中的字符按 字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。 int fch(char c) { if (c>='a'&&c<='z'||c>='A'&&c<='Z') return (1); else return (0); } int fnum(char c) { if (c>='0'&&c<='9') return (1); else return (0); } void process(char R[n]) { low=0;high=n-1; while (low<high)
while (low<high&&fch(R[lowD low++ while(low<high&&! fch(R[high) high if (low<high) k=Rlow] Rlow]=R[high THigh]=k; low-low+1: high=n-1 while(low<high) while(low<high&&fnum(R[low) ow++ while(low<high&&l fnum(R[high) hi if (low<high) k=Rlow] Rlow]=R[high THigh]=k 5.线性表用顺序存储,设计一个算法,用尽可能少的辅助存储空间将顺序表中前n个元素和后n个元 素进行整体互换。即将线性表 (a,a2,…,an,b,b2,…,bn)改变为 (b,b2,….,bn,al,a2,….,am void process(seqlist *L, int m, int n) if(m<=n for(1=1;i<=m;i++) X=L->data[0I
{ while (low<high&&fch(R[low])) low++; while (low<high&&!fch(R[high])) high--; if (low<high) { k=R[low]; R[low]=R[high]; R[high]=k; } } low=low+1;high=n-1; while (low<high) { while (low<high&&fnum(R[low])) low++; while (low<high&&!fnum(R[high])) high--; if (low<high) { k=R[low]; R[low]=R[high]; R[high]=k; } } } ⒌线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前 m 个元素和后 n 个元 素进行整体互换。即将线性表 （a1, a2, … , am, b1, b2, … , bn） 改变为： （b1, b2, … , bn , a1, a2, … , am）。 void process(seqlist *L,int m,int n) { if (m<=n) for (i=1;i<=m;i++) { x=L->data[0];
for(k-l; k<=L->last; k++) L->data[k-1=L->data[k] ->data[L->last=x; else for(i=l; K<=n; 1++) x=L->data 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;k<=L->last;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } else for(i=1;i<=n;i++) { x=L->data[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->data<pb->data) 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->data<pb->data) { 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);