数据结构算法设计C++实现 数据结构,算法与应用 ---C++语言描述(代码与习题答案)
\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u8bbe\u8ba1\u7f16\u7a0b\u9898\uff08\u7528C++\u63cf\u8ff0\uff09\uff0c\u6025\uff0c\u6c42\u5927\u795e\u89e3\u7b54~~~\u4ee5\u5f85\u6392\u5e8f\u5e8f\u5217 { 2\uff0c 5\uff0c 3\uff0c 4\uff0c 1} \u4e3a\u4f8b\uff0c\u6309\u975e\u9012\u51cf\u6709\u5e8f\u6392\u5217\u3002
\u7b2c\u4e00\u8d9f\u8d77\u6ce1\u6392\u5e8f\u8fc7\u7a0b\u5982\u4e0b\uff1a
\u521d\u59cb\uff1a 2 5 3 4 1\u7b2c1\u6b21\uff1a 2 5 3 4 1\u7b2c2\u6b21\uff1a 2 3 5 4 1 3\u6bd4\u6700\u7ec8\u4f4d\u7f6e\u524d\u79fb\u4e86\u4e00\u4e2a\u4f4d\u7f6e\u7b2c3\u6b21\uff1a 2 3 4 5 1 4\u6bd4\u6700\u7ec8\u4f4d\u7f6e\u524d\u79fb\u4e86\u4e00\u4e2a\u4f4d\u7f6e\u7b2c4\u6b21\uff1a 2 3 4 1 5\u901a\u8fc7\u7b2c\u4e00\u8d9f\u7684\u6392\u5e8f\u8fc7\u7a0b\u53d1\u73b0\uff0c3\u30014\u539f\u6765\u5728\u7d22\u5f15\u4e3a2\u30013\u7684\u4f4d\u7f6e\uff0c\u4f46\u7ecf\u8fc7\u7b2c\u4e00\u8d9f\u6392\u5e8f\u8fc7\u7a0b\u540e\uff0c3\u30014\u6682\u65f6\u79fb\u52a8\u5230\u4e86\u7d22\u5f15\u4e3a1\u30012\u7684\u4f4d\u7f6e\u3002
C++\u7a0b\u5e8f\u5982\u4e0b\uff1a
#include "iostream"#include "iomanip"using namespace std;//\u8f93\u51fa\u6570\u7ec4\u4e2d\u7684\u6240\u6709\u5143\u7d20void display(int arr[], int n){int i;for(i=0; i arr[j+1]){temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}cout<<"\u7b2c"<<i+1<<"\u8d9f\uff1a"<<endl;display(arr, n);}} int main(){ int arr[] = {2, 5, 3, 4, 1};int n = 5;cout<<"\u521d\u59cb\u72b6\u6001\uff1a"<<endl;display(arr, n);bubbleSort(arr, n); return 0;}
\u8fd0\u884c\u6d4b\u8bd5\uff1a
\u521d\u59cb\u72b6\u6001\uff1a 2 5 3 4 1\u7b2c1\u8d9f\uff1a 2 3 4 1 5\u7b2c2\u8d9f\uff1a 2 3 1 4 5\u7b2c3\u8d9f\uff1a 2 1 3 4 5\u7b2c4\u8d9f\uff1a 1 2 3 4 5
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int status;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
int *elem;
int length;
int listsize;
}sqlist;
int flag=0;
status initlist(sqlist *l)
{
l->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!l->elem)exit(OVERFLOW);
l->length=0;
l->listsize=LIST_INIT_SIZE;
return OK;
}
status listinsert(sqlist *l,int i,int e)
{
int *newbase,*q,*p;
if(il->length+1)return ERROR;
if(l->length>=l->listsize)
{
newbase=(int*)realloc(l->elem,(l->listsize+LISTINCREMENT)*sizeof(int));
if(newbase)exit(OVERFLOW);
l->elem=newbase;
l->listsize+=LISTINCREMENT;
}
q=&(l->elem[i-1]);
for(p=&(l->elem[l->length-1]);p>=q;--p)
{
*(p+1)=*p;
}
*q=e;
++l->length;
return OK;
}
void listprint(sqlist *l)
{
int i;
for(i=0;ilength;i++)
{
printf("%-5d",l->elem[i]);
}
}
status listdelete(sqlist *l,int i,int *e)
{
int *p,*q;
if((il->length))return ERROR;
p=&(l->elem[i-1]);
e=*p;
q=l->elem+l->length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--l->length;
return OK;
}
status getelem(sqlist *l,int i,int *e)
{
if((il->length))return ERROR;
*e=l->elem[i-1];
return OK;
}
int meun()
{
int a;
printf("*************************\n");
printf("* 1 InitList *\n");
printf("* 2 ListInsert *\n");
printf("* 3 ListPrint *\n");
printf("* 4 Delete *\n");
printf("* 5 Getelem *\n");
printf("* 6 Exit *\n");
printf("*************************\n");
fflush(stdin);
do
{
printf("qing xuan ze:\n");
scanf("%d",&a);
}while(!(a>=1&&a<=6));
return a;
}
void main()
{
sqlist l,*p;
int x,i,e,result;
p=&l;
do
{ clrscr();
x=meun();
switch(x)
{
case 1: initlist(p);
flag=1;
printf("initlist succes!press enter contiue");
getch();
break;
case 2: if(flag==0)
{
printf("you must initlist first!please select!");
getch();
break;
}
fflush(stdin);
printf("\n please input i and e:");
scanf("%d%d",&i,&e);
result=listinsert(p,i,e);
if(result==ERROR)
printf("error:i out of rang!press enter continue");
else
printf("insert completed!please enter continue");
getch();
break;
case 3: printf("sqlist:\n");
listprint(p);
getch();
break;
case 4: printf("\n please input i:");
scanf("%d",&i);
result=listdelete(p,i,&e);
if(result==ERROR)
printf("error:i out of rang!press enter continue");
else
printf("delete completed!please enter continue");
getch();
break;
case 5: printf("\n please input i:\n");
scanf("%d,&i");
result=getelem(p,i,&e);
if(result==ERROR)
printf("error:i out of rang!press enter continue");
else
printf("completed:%d",e);
getch();
break;
case 6: printf("bye\n");
getch();
exit(0);
}
}while(1);
}
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。 这里，我们简单介绍几种排序方法，直接插入排序、希儿排序、冒泡排序、快速排序、直接选择排序，文中所提及的代码在IE6下测试通过。 直接插入排序基本思想
假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。 算法描述
function InsertSort(arr) { //插入排序->直接插入法排序
var st = new Date();
var temp, j;
for(var i=1; i<arr.length; i++) {
if((arr[i]) < (arr[i-1])) {
temp = arr[i];
j = i-1;
do {
arr[j+1] = arr[j];
j--;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+1] = temp;
}//endif
}
status = (new Date() - st) + ' ms';
return arr;
} 希尔排序基本思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。 算法描述
function ShellSort(arr) { //插入排序->希儿排序
var st = new Date();
var increment = arr.length;
do {
increment = (increment/3|0) + 1;
arr = ShellPass(arr, increment);
}
while (increment > 1) status = (new Date() - st) + ' ms';
return arr;
}
function ShellPass(arr, d) { //希儿排序分段执行函数
var temp, j;
for(var i=d; i<arr.length; i++) {
if((arr[i]) < (arr[i-d])) {
temp = arr[i]; j = i-d;
do {
arr[j+d] = arr[j];
j = j-d;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+d] = temp;
}//endif
}
return arr;
} 再举个例子:#include "iostream.h"
void shellSort(int *arr, int len, int *p, int len1);
int main()
{
int num[15]={100,12,20,31,1,5,44,66,61,200,30,80,150,4,8};
int i;
cout<<"待排数据d=(5,3,1): ";
for(i=0;i<15;i++)
{
cout<<num[i]<<" ";
}
int s[3]={5,3,1};
shellSort(num,15, s,3);
cout<<"\n";
return 0;
} void shellSort(int *arr, int len, int *p, int len1)
{
for (int i = 0; i < len1; i++)
{
int d = p[i];
for (int n = 0; n < d; n ++)
{
for (int j = n + d; j < len; j = j + d)
{
if (arr[j] < arr[j - d])
{
int tmp = arr[j];
for (int k = j - d; k >= 0 && arr[k] > tmp; k = k - d)
{
arr[k + d] = arr[k];
}
arr[k + d] = tmp;
}
}
}
cout<<"第"<<i+1<<"趟排序结果：";
for(int m=0;m<15;m++)
cout<<arr[m]<<" ";
cout<<"\n";
}
}
冒泡排序基本思想
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
算法描述
function BubbleSort(arr) { //交换排序->冒泡排序
var st = new Date();
var temp;
var exchange;
for(var i=0; i<arr.length; i++) {
exchange = false;
for(var j=arr.length-2; j>=i; j--) {
if((arr[j+1]) < (arr[j])) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
exchange = true;
}
}
if(!exchange) break;
}
status = (new Date() - st) + ' ms';
return arr;
} 快速排序基本思想
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。 算法描述
function QuickSort(arr) { //交换排序->快速排序
if (arguments.length>1) {
var low = arguments[1];
var high = arguments[2];
} else {
var low = 0;
var high = arr.length-1;
}
if(low < high){
// function Partition
var i = low;
var j = high;
var pivot = arr[i];
while(i<j) {
while(i<j && arr[j]>=pivot)
j--;
if(i<j)
arr[i++] = arr[j];
while(i<j && arr[i]<=pivot)
i++;
if(i<j)
arr[j--] = arr[i];
}//endwhile
arr[i] = pivot;
// end function
var pivotpos = i; //Partition(arr，low，high);
QuickSort(arr, low, pivotpos-1);
QuickSort(arr, pivotpos+1, high);
} else
return;
return arr;
} 直接选择排序基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 算法描述
function SelectSort(arr) { //选择排序->直接选择排序
var st = new Date();
var temp;
for(var i=0; i<arr.length; i++) {
var k = i;
for(var j=i+1; j<arr.length; j++) {
if((arr[j]) < (arr[k]))
k = j;
}
if (k != i){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
status = (new Date() - st) + ' ms';
return arr;
}
从运行速度上来看，快速排序是最快的。 另外把二分查找算法也放这里算了:template<class Type> int BinarySearch(Type a[],const Type& x,int n) { int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; } return -1; }
直接插入排序template<class T,class E>
void DataSortList<T,E>::InsertSort(int left,int right)
{
//把从第二个开始到最后一个元素
//插入到前面排好的序列中去
for(int i=left+1;i<=right;i++)
{
//i是要插入的元素,放入temp中
Element<T,E> temp=Vector[i];
//待插入序列的最后一个元素
int j=i-1;
//寻找插入的位置
while(temp<Vector[j] && j>=left)
{
//后移
Vector[j+1]=Vector[j];
j--;
};
//插入的过程
Vector[j+1]=temp;
};
};
////////////////////////////////InsertSort()函数结束 --------------------------------------------------------------------------------------------------冒泡排序template<class T,class E>
void DataSortList<T,E>::BubbleSort()
{
for(int i=1;i<=currentSize-1;i++) //一共n-1趟排序
for(int j=currentSize-1;j>=i;j--) //每趟从最后一个向前排到i
if(Vector[j]<Vector[j-1]) //如果是逆序
Swap(Vector[j],Vector[j-1]);
}; Bubble()公有函数结束 -------------------------------------------------------------------------------------希尔排序 template<class T,class E>
void DataSortList<T,E>::ShellSort(int left,int right)
{
//初始的间隔大小
int gap=right-left+1;
//临时元素变量
Element<T,E> temp;
int i,j;
//把gap从最大到1的情况全部一遍
do
{
gap=int(gap/3)+1;
//以gap为间隙,对子序列进行直接插入排序
for(i=left+gap;i<=right;i++)
{
j=i-gap;
temp=Vector[i];
while(temp<Vector[j] && j>=left)
{
Vector[j+gap]=Vector[j];
j=j-gap;
};
Vector[j+gap]=temp;
};
}
while(gap>1);
};
////////////////////////////////ShellShell()函数结束 --------------------------------------------------------------------------------------快速排序 void QuickSort(int *pData, int left, int right){ int i, j; int middle, iTemp; i = left; j = right; middle = pData[(left + right) / 2]; //求中间值 do { while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数 i++; while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数 j--; if (i <= j) //找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } } while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left<j)，递归左半边 if(left<j) QuickSort (pData,left,j); //当右边部分有值(right>i)，递归右半边 if(right>i) QuickSort (pData,i,right);} ----------------------------------------------------------------------------------- 选择排序 void selectionSort(Type* arr,long len){ long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n"); for(i=len-1;i>=1;i--) { maxPos=i; for(j=0;j<i;j++) if(arr[maxPos]<arr[j])maxPos=j; if(maxPos!=i)swapArrData(arr,maxPos,i); }}
绛旓細浣犲ソ锛佽閲囩撼int CountX(LNode * head,ElemType x){ LNode *p=head; int count=0; while(p) { if(p->data==x) count++; p=p->next; } return count;}
绛旓細濂, 鎴戞敼绠鍗曠偣, main鍑芥暟閲屽啓浜嗙敤娉. 杩樻湁浠涔堜笉鎳傚啀闂 include "stdafx.h"define MAX_NUM_BIT_LEN (100)/*灏卞湴閫嗙疆 iArray鏁扮粍鎸囬拡, iLength鏁扮粍闀垮害*/ void reverselist(int iArray[], int iLength){ int iStart = 0;int iEnd = iLength - 1;while (iStart < iEnd){ int ch...
绛旓細浣犵殑杩炶〃绗竴涓粨鐐规病鍒濆鍖栵紝鎵浠ラ摼琛ㄧ涓涓暟閮芥槸涓偅涓湴鍧鍐呯殑鍊间笅闈㈠浘涓彲浠ョ湅鍑轰綘鐨勯摼琛–棣栧湴鍧鏄0x00382798 閲岄潰鐨勫兼槸-858993460 鎵浠ヨ緭鍑洪摼琛ㄤ腑灏变細涓鐩存湁杩欎釜鍊 浣犲啀鐪嬬湅锛屾妸閾捐〃鍒濆鍖栦竴涓
绛旓細//涓鑸殑娴嬭瘯锛屽彲浠ュ簲浠
绛旓細锛屼竴涓负鐩爣琛紝灏嗘簮琛ㄤ腑鐨勫厓绱犵帇鐩爣琛ㄤ腑绉伙紙鏈変笌涔嬬浉鍚岀殑鍒欏垹闄わ紝娌℃湁鍒欎繚瀛橈級鏁版嵁缁撴瀯鏄绠楁満瀛樺偍銆佺粍缁囨暟鎹殑鏂瑰紡銆傛暟鎹粨鏋勬槸鎸囩浉浜掍箣闂村瓨鍦ㄤ竴绉嶆垨澶氱鐗瑰畾鍏崇郴鐨勬暟鎹厓绱犵殑闆嗗悎銆傞氬父鎯呭喌涓嬶紝绮惧績閫夋嫨鐨勬暟鎹粨鏋勫彲浠ュ甫鏉ユ洿楂樼殑杩愯鎴栬呭瓨鍌ㄦ晥鐜囥傛暟鎹粨鏋勫線寰鍚岄珮鏁堢殑妫绱绠楁硶鍜岀储寮曟妧鏈湁鍏炽
绛旓細1銆佺敤鐨勬渶澶氫篃鏄渶绠鍗曠殑鏁版嵁缁撴瀯鏄嚎鎬ц〃銆2銆佹湁鍓嶉旂殑鍙堥毦鏁版嵁缁撴瀯鏄浘 銆3銆佸父鐢ㄧ殑80锛绠楁硶鏄帓搴忓拰鏌ユ壘銆傛帓搴忓父鐢ㄧ殑绠楁硶鏈夛細鎻掑叆绠楁硶锛堢洿鎺ユ彃鍏ョ畻娉曘佹姌鍗婃彃鍏ョ畻娉曘佸笇灏旂畻娉曪級銆侀夋嫨绠楁硶锛堢畝鍗曢夋嫨绠楁硶銆佸爢鎺掑簭绠楁硶锛夈佸揩閫熺畻娉(鍐掓场鎺掑簭銆佸揩閫熸帓搴忕畻娉)浠ヤ笅绋嬪簭缁欏嚭浜嗗悇绉嶇畻娉曠殑瀹炵幇锛屽叾鎺ュ彛涓簐oid...
绛旓細include <stdio.h> include <stdlib.h> include typedef struct Node { int data;struct Node * next;}Node, * LinkList;void ListReverse(LinkList L){ Node *p,*q;p=L->next;L->next=NULL;while(p){ q=p->next;p->next=L->next;//澶存彃娉 L->next=p;p=q;} }/*閫嗙疆鍑芥暟*/...
绛旓細鍙﹀涓句竴涓緥瀛愶紝鍓嶅簭abecfg鍜屼腑搴廱eafcg銆傚墠搴忓厛閬嶅巻鏍癸紝鏁卆涓烘牴锛屾墍浠ヤ腑搴忕殑be鍜宖cg鍒嗗埆涓哄乏瀛愭爲鍜屽彸瀛愭爲锛屽墠搴忓搴旀槸be鍜宑fg锛岀劧鍚庡宸﹀彸瀛愭爲鐢ㄩ掑綊锛屽緢绠鍗曠殑锛歴truct Btree *tree(char *front,char *middle, int length)//middle涓轰腑搴忛亶鍘嗙殑瀛楃涓诧紝front涓哄墠搴忛亶鍘嗙殑瀛楃涓层//length涓...
绛旓細甯垜鍋氫竴涓绋璁捐 鏁版嵁缁撴瀯涓庣畻娉曠殑! 璇剧▼璁捐涓夎糠瀹棶棰樼殑闈為掑綊绠楁硶瀹炵幇浜屻佸埄鐢ㄩ『搴忔爤瀹炵幇杩峰闂鐨勯潪閫掑綊绠楁硶銆傝姹傛彁渚涚敤鎴疯緭鍏ヨ糠瀹佽嚜鍔ㄧ敓鎴愯糠瀹拰榛樿杩峰涓夌鏂瑰紡,鑳藉浠ュ浘褰㈠寲鐨勬柟寮忓皢鎵鎼滃鐨勮糠瀹矾寰勬樉绀哄嚭... 璇剧▼璁捐涓 杩峰闂鐨勯潪閫掑綊绠楁硶瀹炵幇浜屻佸埄鐢ㄩ『搴忔爤瀹炵幇杩峰闂鐨勯潪閫掑綊绠楁硶銆傝姹傛彁渚涚敤鎴...
绛旓細54321锛1~5杩5涓暟杩炵画杩涙爤鍚庡啀5涓暟杩炵画鍑烘爤锛岀敤2涓惊鐜氨鍙互浜 32145锛1~3杩3涓暟杩炵画杩涙爤鍚庡啀3涓暟杩炵画鍑烘爤锛屼篃鍙互鐢2涓惊鐜紝鐒跺悗鏄4杩4鍑猴紝5杩5鍑
