．[題目分析] 知道雙向循環鏈表中的一個結點與前驅交換涉及到四個結點(p結點前驅結點前驅的前驅結點後繼結點)六條鏈
void Exchange(LinkedList p)∥p是雙向循環鏈表中的一個結點本算法將p所指結點與其前驅結點交換
{q=p>llink;
q>llink>rlink=p;∥p的前驅的前驅之後繼為p
p>llink=q>llink;∥p的前驅指向其前驅的前驅
q>rlink=p>rlink;∥p的前驅的後繼為p的後繼
q>llink=p;∥p與其前驅交換
p>rlink>llink=q;∥p的後繼的前驅指向原p的前驅
p>rlink=q;∥p的後繼指向其原來的前驅
}∥算法exchange結束
．[題目分析] 順序存儲的線性表遞增有序可以順序查找也可折半查找題目要求用最少的時間在表中查找數值為x的元素這裡應使用折半查找方法
void SearchExchangeInsert(ElemType a[];ElemType x)∥a是具有n個元素的遞增有序線性表順序存儲本算法在表中查找數值為x的元素如查到則與其後繼交換位置;如查不到則插入表中且使表仍遞增有序
{ low=;high=n;∥low和high指向線性表下界和上界的下標
while(low<=high)
{mid=(low+high)/;∥找中間位置
if(a[mid]==x) break;∥找到x退出while循環
else if (a[mid] <x) low=mid+;∥到中點mid的右半去查
else high=mid;∥到中點mid的左部去查
}
if(a[mid]==x && mid!=n)∥若最後一個元素與x相等則不存在與其後繼交換的操作
{t=a[mid];a[mid]=a[mid+];a[mid+]=t;}∥數值x與其後繼元素位置交換
if(low>high)∥查找失敗插入數據元素x
{for(i=n;i>high;i) a[i+]=a[i];∥後移元素
a[i+]=x;∥插入x
}∥結束插入
}∥結束本算法
[算法討論] 首先是線性表的描述算法中使用一維數組a表示線性表未使用包含數據元素的一維數組和指示線性表長度的結構體若使用結構體對元素的引用應使用aelem[i]另外元素類型就假定是ElemType未指明具體類型其次C中一維數組下標從開始若說有n個元素的一維數組其最後一個元素的下標應是n第三本算法可以寫成三個函數查找函數交換後繼函數與插入函數寫成三個函數顯得邏輯清晰易讀
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23335.html
