数据结构CH2-2.ppt

//将x插入第i个位置 int AV； SNode sd[MAXSIZE]; int Insert_SList(int SL,datatype x,int i) {int p,t; p=Get_SList(SL,i-1); if(p==-1) {printf(插入的位置不正确);return -1;} if(AV==-1) {printf(存储池无空闲结点);return 0;} t=malloc_SList(); sd[t].data=x; sd[t].next=sd[p].next; sd[p].next=t; return 1; } 2.5.1 顺序表应用举例 [例1]将顺序表（a1，a2，…，an）重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大。 基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： if(aia1) 继续比较下一个; if(aia1) {将它上面的元素依次下移一个位置; ai放入最上面; } /*算法2-5*/ void part(Sequenlist *L) { int i,j; elemtype x,y; x=L-data[0]; for(i=1;i=L-len-1;i++) if(L-data[i]x) {y=L-data[i]; for(j=i-1;j=0;j--) L-data[j+1]=L-data[j]; L-data[0]=y; } } 内存 5 6 7 4 an 0 1 4 数组下标 n-1 5 n 8 3 2 3 内存 5 6 7 4 an 8 3 0 1 4 5 2 3 [例2]有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也按从小到大的升序排列。 基本思路： 依次扫描A和B的元素，比较当前元素ai和bj： if(aibj) {ai赋给Ck; i++;k++；} else {bj赋给Ck; j++;k++；} 将未完的那个顺序表中余下部分赋给C; /*算法2-6*/ void merge(Sequenlist A,Sequenlist B,Sequenlist *C) { int i,j,k; i=0;j=0;k=0; while(i=A.len-1j=B.len-1) if(A.data[i]B.data[j]) C-data[k++]=A.data[i++]; else C-data[k++]=B.data[j++]; while(i=A.len-1) C-data[k++]=A.data[i++]; while(j=B.len-1) C-data[k++]=B.data[j++]; C-len=k; } 2.5 .2单链表应用举例 [例3]已知单链表H,写一算法将其倒置。 基本思路： 设置新链表; 依次取原链表的每个结点; while(原链表还有结点) 将该结点插入到新链表的头部; /*算法2-15*/ void reverse(linklist *H) {linklist *p,*q; p=H-next; H-next=NULL; while(p) { q=p;p=p-next; q-next=H-next; H-next=q; } } [例4]删除单链表H中重复的结点。 基本思路： 将p指向第一个结点; while(p之后还有结点) 删除p之后与p值相同的结点; void pur_LinkList(linklist *H) {linklist *p,*q,*r; p=H-next; if(p==NULL)return ; while(p-next) {q=p; while(q-next) if(q-next-data==p-data) {r=q-next;q-next=r-next;free(r);} else q=q-next; } p=p-next; } } [例5]两个单链表A、B递增有序，归并A、B成递减有序的链表C。 基本思路： 将p、q分别指向