?? algo10-2.c
字號:
/* algo10-2.c 靜態鏈表 */
#include"c1.h"
typedef int InfoType; /* 定義其它數據項的類型 */
#include"c10-2.h"
void TableInsert(SLinkListType *SL,RedType D[],int n)
{ /* 由數組D建立n個元素的表插入排序的靜態鏈表SL */
int i,p,q;
(*SL).r[0].rc.key=INT_MAX; /* 表頭結點記錄的關鍵字取最大整數(非降序鏈表的表尾) */
(*SL).r[0].next=0; /* next域為0表示表尾(現為空表,初始化) */
for(i=0;i<n;i++)
{
(*SL).r[i+1].rc=D[i]; /* 將數組D的值賦給靜態鏈表SL */
q=0;
p=(*SL).r[0].next;
while((*SL).r[p].rc.key<=(*SL).r[i+1].rc.key)
{ /* 靜態鏈表向后移 */
q=p;
p=(*SL).r[p].next;
}
(*SL).r[i+1].next=p; /* 將當前記錄插入靜態鏈表 */
(*SL).r[q].next=i+1;
}
(*SL).length=n;
}
void Arrange(SLinkListType *SL)
{ /* 根據靜態鏈表SL中各結點的指針值調整記錄位置,使得SL中記錄按關鍵字 */
/* 非遞減有序順序排列 算法10.3 */
int i,p,q;
SLNode t;
p=(*SL).r[0].next; /* p指示第一個記錄的當前位置 */
for(i=1;i<(*SL).length;++i)
{ /* (*SL).r[1..i-1]中記錄已按關鍵字有序排列,第i個記錄在SL中的當前位置應不小于i */
while(p<i)
p=(*SL).r[p].next; /* 找到第i個記錄,并用p指示其在SL中當前位置 */
q=(*SL).r[p].next; /* q指示尚未調整的表尾 */
if(p!=i)
{
t=(*SL).r[p]; /* 交換記錄,使第i個記錄到位 */
(*SL).r[p]=(*SL).r[i];
(*SL).r[i]=t;
(*SL).r[i].next=p; /* 指向被移走的記錄,使得以后可由while循環找回 */
}
p=q; /* p指示尚未調整的表尾,為找第i+1個記錄作準備 */
}
}
void Sort(SLinkListType L,int adr[])
{ /* 求得adr[1..L.length],adr[i]為靜態鏈表L的第i個最小記錄的序號 */
int i=1,p=L.r[0].next;
while(p)
{
adr[i++]=p;
p=L.r[p].next;
}
}
void Rearrange(SLinkListType *L,int adr[])
{ /* adr給出靜態鏈表L的有序次序,即L.r[adr[i]]是第i小的記錄。 */
/* 本算法按adr重排L.r,使其有序。算法10.18(L的類型有變) */
int i,j,k;
for(i=1;i<(*L).length;++i)
if(adr[i]!=i)
{
j=i;
(*L).r[0]=(*L).r[i]; /* 暫存記錄(*L).r[i] */
while(adr[j]!=i)
{ /* 調整(*L).r[adr[j]]的記錄到位直到adr[j]=i為止 */
k=adr[j];
(*L).r[j]=(*L).r[k];
adr[j]=j;
j=k; /* 記錄按序到位 */
}
(*L).r[j]=(*L).r[0];
adr[j]=j;
}
}
void print(SLinkListType L)
{
int i;
for(i=1;i<=L.length;i++)
printf("key=%d ord=%d next=%d\n",L.r[i].rc.key,L.r[i].rc.otherinfo,L.r[i].next);
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SLinkListType l1,l2;
int *adr,i;
TableInsert(&l1,d,N);
l2=l1; /* 復制靜態鏈表l2與l1相同 */
printf("排序前:\n");
print(l1);
Arrange(&l1);
printf("l1排序后:\n");
print(l1);
adr=(int*)malloc((l2.length+1)*sizeof(int));
Sort(l2,adr);
for(i=1;i<=l2.length;i++)
printf("adr[%d]=%d ",i,adr[i]);
printf("\n");
Rearrange(&l2,adr);
printf("l2排序后:\n");
print(l2);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -