Ⅰ c語言排序
//總共給你整理了7種排序演算法：希爾排序，鏈式基數排序，歸並排序
//起泡排序，簡單選擇排序，樹形選擇排序，堆排序,先自己看看吧，
//看不懂可以再問身邊的人或者查資料,既然可以上網，我相信你所在的地方信息流通方式應該還行,所有的程序全部在VC++6.0下編譯通過
//希爾排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void ShellInsert(SqList &L,int dk)
{ // 對順序表L作一趟希爾插入排序。本演算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前後記錄位置的增量是dk,而不是1;
// 2.r[0]只是暫存單元,不是哨兵。當j<=0時,插入位置已找到。演算法10.4
int i,j;
for(i=dk+1;i<=L.length;++i)
if LT(L.r[i].key,L.r[i-dk].key)
{ // 需將L.r[i]插入有序增量子表
L.r[0]=L.r[i]; // 暫存在L.r[0]
for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; // 記錄後移，查找插入位置
L.r[j+dk]=L.r[0]; // 插入
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}
void print1(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
void ShellSort(SqList &L,int dlta[],int t)
{ // 按增量序列dlta[0..t-1]對順序表L作希爾排序。演算法10.5
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量為dlta[k]的插入排序
printf("第%d趟排序結果: ",k+1);
print(L);
}
}
#define N 10
#define T 3
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列數組
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序後: ");
print1(l);
}
/*****************************************************************/
//鏈式基數排序
typedef int InfoType; // 定義其它數據項的類型
typedef int KeyType; // 定義RedType類型的關鍵字為整型
struct RedType // 記錄類型(同c10-1.h)
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項
};
typedef char KeysType; // 定義關鍵字類型為字元型
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 關鍵字項數的最大值
#define RADIX 10 // 關鍵字基數，此時是十進制整數的基數
#define MAX_SPACE 1000
struct SLCell // 靜態鏈表的結點類型
{
KeysType keys[MAX_NUM_OF_KEY]; // 關鍵字
InfoType otheritems; // 其它數據項
int next;
};
struct SLList // 靜態鏈表類型
{
SLCell r[MAX_SPACE]; // 靜態鏈表的可利用空間，r[0]為頭結點
int keynum; // 記錄的當前關鍵字個數
int recnum; // 靜態鏈表的當前長度
};
typedef int ArrType[RADIX];
void InitList(SLList &L,RedType D[],int n)
{ // 初始化靜態鏈表L（把數組D中的數據存於L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max為關鍵字的最大值
for(i=1;i<n;i++)
if(max<D[i].key)
max=D[i].key;
L.keynum=int(ceil(log10(max)));
L.recnum=n;
for(i=1;i<=n;i++)
{
L.r[i].otheritems=D[i-1].otherinfo;
itoa(D[i-1].key,c,10); // 將10進制整型轉化為字元型,存入c
for(j=strlen(c);j<L.keynum;j++) // 若c的長度<max的位數,在c前補'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;j<L.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}
int ord(char c)
{ // 返回k的映射(個位整數)
return c-'0';
}
void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 演算法10.15
{ // 靜態鍵表L的r域中記錄已按(keys[0],…,keys[i-1])有序。本演算法按
// 第i個關鍵字keys[i]建立RADIX個子表,使同一子表中記錄的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個和最後一個記錄
int j,p;
for(j=0;j<RADIX;++j)
f[j]=0; // 各子表初始化為空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord將記錄中第i個關鍵字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 將p所指的結點插入第j個子表中
}
}
int succ(int i)
{ // 求後繼函數
return ++i;
}
void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本演算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成
// 一個鏈表，e[0..RADIX-1]為各子表的尾指針。演算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一個非空子表，succ為求後繼函數
r[0].next=f[j];
t=e[j]; // r[0].next指向第一個非空子表中第一個結點
while(j<RADIX-1)
{
for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一個非空子表
if(f[j])
{ // 鏈接兩個非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最後一個非空子表中的最後一個結點
}
void printl(SLList L)
{ // 按鏈表輸出靜態鏈表
int i=L.r[0].next,j;
while(i)
{
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
i=L.r[i].next;
}
}
void RadixSort(SLList &L)
{ // L是採用靜態鏈表表示的順序表。對L作基數排序，使得L成為按關鍵字
// 自小到大的有序靜態鏈表，L.r[0]為頭結點。演算法10.17
int i;
ArrType f,e;
for(i=0;i<L.recnum;++i)
L.r[i].next=i+1;
L.r[L.recnum].next=0; // 將L改造為靜態鏈表
for(i=0;i<L.keynum;++i)
{ // 按最低位優先依次對各關鍵字進行分配和收集
Distribute(L.r,i,f,e); // 第i趟分配
Collect(L.r,f,e); // 第i趟收集
printf("第%d趟收集後:\n",i+1);
printl(L);
printf("\n");
}
}
void print(SLList L)
{ // 按數組序號輸出靜態鏈表
int i,j;
printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
for(i=1;i<=L.recnum;i++)
{
printf("keys=");
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
}
}
void Sort(SLList 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(SLList &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.recnum;++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;
}
}
#define N 10
void main()
{
RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域還沒賦值):\n");
print(l);
RadixSort(l);
printf("排序後(靜態鏈表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序後(重排記錄):\n");
print(l);
}
/*******************************************/
//歸並排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ // 將有序的SR[i..m]和SR[m+1..n]歸並為有序的TR[i..n] 演算法10.12
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) // 將SR中記錄由小到大地並入TR
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; // 將剩餘的SR[i..m]復制到TR
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; // 將剩餘的SR[j..n]復制到TR
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ // 將SR[s..t]歸並排序為TR1[s..t]。演算法10.13
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; // 將SR[s..t]平分為SR[s..m]和SR[m+1..t]
MSort(SR,TR2,s,m); // 遞歸地將SR[s..m]歸並為有序的TR2[s..m]
MSort(SR,TR2,m+1,t); // 遞歸地將SR[m+1..t]歸並為有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // 將TR2[s..m]和TR2[m+1..t]歸並到TR1[s..t]
}
}
void MergeSort(SqList &L)
{ // 對順序表L作歸並排序。演算法10.14
MSort(L.r,L.r,1,L.length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 7
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(l);
printf("排序後:\n");
print(l);
}
/**********************************************/
//起泡排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define N 8
void bubble_sort(int a[],int n)
{ // 將a中整數序列重新排列成自小至大有序的整數序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
{
change=FALSE;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}
void main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序後:\n");
print(d,N);
}
/****************************************************/
//簡單選擇排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
int SelectMinKey(SqList L,int i)
{ // 返回在L.r[i..L.length]中key最小的記錄的序號
KeyType min;
int j,k;
k=i; // 設第i個為最小
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) // 找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList &L)
{ // 對順序表L作簡單選擇排序。演算法10.9
int i,j;
RedType t;
for(i=1;i<L.length;++i)
{ // 選擇第i小的記錄，並交換到位
j=SelectMinKey(L,i); // 在L.r[i..L.length]中選擇key最小的記錄
if(i!=j)
{ // 與第i個記錄交換
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序後:\n");
print(l);
}
/************************************************/
//樹形選擇排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
typedef int InfoType; // 定義其它數據項的類型
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void TreeSort(SqList &L)
{ // 樹形選擇排序
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; // 完全二叉樹的層數
k=(int)pow(2,l)-1; // l層完全二叉樹的結點總數
k1=(int)pow(2,l-1)-1; // l-1層完全二叉樹的結點總數
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉樹採用順序存儲結構
for(i=1;i<=n;i++) // 將L.r賦給葉子結點
t[k1+i-1]=L.r[i];
for(i=k1+n;i<k;i++) // 給多餘的葉子的關鍵字賦無窮大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 給非葉子結點賦值
for(i=j1;i<j;i+=2)
t[i].key<t[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
j=j1;
j1=(j1-1)/2;
}
for(i=0;i<n;i++)
{
L.r[i+1]=t[0]; // 將當前最小值賦給L.r[i]
j1=0;
for(j=1;j<l;j++) // 沿樹根找結點t[0]在葉子中的序號j1
t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; // 序號為j1的結點的雙親結點序號
t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}
free(t);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
TreeSort(l);
printf("排序後:\n");
print(l);
}
/****************************/
//堆排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
typedef SqList HeapType; // 堆採用順序表存儲表示
void HeapAdjust(HeapType &H,int s,int m) // 演算法10.10
{ // 已知H.r[s..m]中記錄的關鍵字除H.r[s].key之外均滿足堆的定義，本函數
// 調整H.r[s]的關鍵字,使H.r[s..m]成為一個大頂堆(對其中記錄的關鍵字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{ // 沿key較大的孩子結點向下篩選
if(j<m&<(H.r[j].key,H.r[j+1].key))
++j; // j為key較大的記錄的下標
if(!LT(rc.key,H.r[j].key))
break; // rc應插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}
void HeapSort(HeapType &H)
{ // 對順序表H進行堆排序。演算法10.11
RedType t;
int i;
for(i=H.length/2;i>0;--i) // 把H.r[1..H.length]建成大頂堆
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{ // 將堆頂記錄和當前未經排序子序列H.r[1..i]中最後一個記錄相互交換
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 將H.r[1..i-1]重新調整為大頂堆
}
}
void print(HeapType H)
{
int i;
for(i=1;i<=H.length;i++)
printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
HeapType h;
int i;
for(i=0;i<N;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序後:\n");
print(h);
}
Ⅱ 關於數據結構的問題，用C語言描述
數據結構復習重點歸納筆記[清華嚴蔚敏版]
數據結構復習重點歸納[適於清華嚴版教材]
一、數據結構的章節結構及重點構成
數據結構學科的章節劃分基本上為：概論，線性表，棧和隊列，串，多維數組和廣義表，樹和二叉樹，圖，查找，內排，外排，文件，動態存儲分配。
對於絕大多數的學校而言，「外排，文件，動態存儲分配」三章基本上是不考的，在大多數高校的計算機本科教學過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對於報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那麼這部分朋友就要留意這三章了。
按照以上我們給出的章節以及對後三章的介紹，數據結構的章節比重大致為：
概論：內容很少，概念簡單，分數大多隻有幾分，有的學校甚至不考。
線性表：基礎章節，必考內容之一。考題多數為基本概念題，名校考題中，鮮有大型演算法設計題。如果有，也是與其它章節內容相結合。
棧和隊列：基礎章節，容易出基本概念題，必考內容之一。而棧常與其它章節配合考查，也常與遞歸等概念相聯系進行考查。
串 ：基礎章節，概念較為簡單。專門針對於此章的大型演算法設計題很少，較常見的是根據KMP進行演算法分析。
多維數組及廣義表
：基礎章節，基於數組的演算法題也是常見的，分數比例波動較大，是出題的「可選單元」或「侯補單元」。一般如果要出題，多數不會作為大題出。數組常與「查找，排序」等章節結合來作為大題考查。
樹和二叉樹
：重點難點章節，各校必考章節。各校在此章出題的不同之處在於，是否在本章中出一到兩道大的演算法設計題。通過對多所學校的試卷分析，絕大多數學校在本章都曾有過出大型演算法設計題的歷史。
圖 ：重點難點章節，名校尤愛考。如果作為重點來考，則多出現於分析與設計題型當中，可與樹一章共同構成演算法設計大題的題型設計。
查找
：重點難點章節，概念較多，聯系較為緊密，容易混淆。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。演算法設計型題中可以數組結合來考查，也可以與樹一章結合來考查。
排序
：與查找一章類似，本章同屬於重點難點章節，且概念更多，聯系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序演算法的優劣比較此類的題。演算法設計大題中，如果作為出題，那麼常與數組結合來考查。
二、數據結構各章節重點勾劃：
第0章 概述
本章主要起到總領作用，為讀者進行數據結構的學習進行了一些先期鋪墊。大家主要注意以下幾點：數據結構的基本概念，時間和空間復雜度的概念及度量方法，演算法設計時的注意事項。本章考點不多，只要稍加註意理解即可。
第一章 線性表
作為線性結構的開篇章節，線性表一章在線性結構的學習乃至整個數據結構學科的學習中，其作用都是不可低估的。在這一章，第一次系統性地引入鏈式存儲的概念，鏈式存儲概念將是整個數據結構學科的重中之重，無論哪一章都涉及到了這個概念。
總體來說，線性表一章可供考查的重要考點有以下幾個方面：
1.線性表的相關基本概念，如：前驅、後繼、表長、空表、首元結點，頭結點，頭指針等概念。
2.線性表的結構特點，主要是指：除第一及最後一個元素外，每個結點都只有一個前趨和只有一個後繼。
3.線性表的順序存儲方式及其在具體語言環境下的兩種不同實現：表空間的靜態分配和動態分配。靜態鏈表與順序表的相似及不同之處。
4.線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算：單鏈表、循環鏈表，雙向鏈表，雙向循環鏈表。其中，單鏈表的歸並演算法、循環鏈表的歸並演算法、雙向鏈表及雙向循環鏈表的插入和刪除演算法等都是較為常見的考查方式。此外，近年來在不少學校中還多次出現要求用遞歸演算法實現單鏈表輸出（可能是順序也可能是倒序）的問題。
在鏈表的小題型中，經常考到一些諸如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。
5.線性表的順序存儲及鏈式存儲情況下，其不同的優缺點比較，即其各自適用的場合。單鏈表中設置頭指針、循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。
第二章 棧與隊列
棧與隊列，是很多學習DS的同學遇到第一隻攔路虎，很多人從這一章開始坐暈車，一直暈到現在。所以，理解棧與隊列，是走向DS高手的一條必由之路，。
學習此章前，你可以問一下自己是不是已經知道了以下幾點：
1.棧、隊列的定義及其相關數據結構的概念，包括：順序棧，鏈棧，共享棧，循環隊列，鏈隊等。棧與隊列存取數據（請注意包括：存和取兩部分）的特點。
2.遞歸演算法。棧與遞歸的關系，以及藉助棧將遞歸轉向於非遞歸的經典演算法：n!階乘問題，fib數列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節中進行考查。
3.棧的應用：數值表達式的求解，括弧的配對等的原理，只作原理性了解，具體要求考查此為題目的演算法設計題不多。
4.循環隊列中判隊空、隊滿條件，循環隊列中入隊與出隊演算法。
如果你已經對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，並不是可以不作題哦。
第三章 串
經歷了棧一章的痛苦煎熬後，終於迎來了串一章的柳暗花明。
串，在概念上是比較少的一個章節，也是最容易自學的章節之一，但正如每個過來人所了解的，KMP演算法是這一章的重要關隘，突破此關隘後，走過去又是一馬平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡壘有：
1.串的基本概念，串與線性表的關系（串是其元素均為字元型數據的特殊線性表），空串與空格串的區別，串相等的條件
2.串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的演算法是很多學校在基本操作上的考查重點。
3.順序串與鏈串及塊鏈串的區別和聯系，實現方式。
4.KMP演算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配演算法的不足，明確next數組需要改進之外。其中，理解演算法是核心，會求數組是得分點。不用我多說，這一節內容是本章的重中之重。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP演算法進行匹配的匹配過程。
第四章 數組與廣義表
學過程序語言的朋友，數組的概念我們已經不是第一次見到了，應該已經「一回生，二回熟」了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學里的程序語言所關注的不太一樣，下面會作介紹。
廣義表的概念，是數據結構里第一次出現的。它是線性表或表元素的有限序列，構成該結構的每個子表或元素也是線性結構的，所以，這一章也歸入線性結構中。
本章的考查重點有：
1.多維數組中某數組元素的position求解。一般是給出數組元素的首元素地址和每個元素佔用的地址空間並組給出多維數組的維數，然後要求你求出該數組中的某個元素所在的位置。
2.明確按行存儲和按列存儲的區別和聯系，並能夠按照這兩種不同的存儲方式求解1中類型的題。
3.將特殊矩陣中的元素按相應的換算方式存入數組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的演算法。
4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點，是理解整個廣義表一節演算法的基礎。近來，在一些學校中，出現了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作後的串值，要求求出原廣義表L。大家要留意。
5.與廣義表有關的遞歸演算法。由於廣義表的定義就是遞歸的，所以，與廣義表有關的演算法也常是遞歸形式的。比如：求表深度，復制廣義表等。這種題目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。
第五章 樹與二叉樹
從對線性結構的研究過度到對樹形結構的研究，是數據結構課程學習的一次躍變，此次躍變完成的好壞，將直接關繫到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業課總分。所以，樹這一章的重要性，已經不說自明了。
總體來說，樹一章的知識點包括：
二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種演算法（遞歸與非遞歸），在三種基本遍歷演算法的基礎上實現二叉樹的其它演算法，線索二叉樹的概念和線索化演算法以及線索化後的查找演算法，最優二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷演算法及其與二叉樹遍歷演算法的聯系，樹與森林和二叉樹的轉換。
下面我們來看考試中對以上知識的主要考查方法：
1.二叉樹的概念、性質和存儲結構
考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區別；考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質：第i層的最多結點數，深度為k的二叉樹的最多結點數，n0=n2+1的性質，n個結點的完全二叉樹的深度，順序存儲二叉樹時孩子結點與父結點之間的換算關系（左為：2*i，右為：2*i+1）。
二叉樹的順序存儲和二叉鏈表存儲的各自優缺點及適用場合，二叉樹的三叉鏈表表示方法。
2.二叉樹的三種遍歷演算法
這一知識點掌握的好壞，將直接關繫到樹一章的演算法能否理解，進而關繫到樹一章的演算法設計題能否順利完成。二叉樹的遍歷演算法有三種：先序，中序和後序。其劃分的依據是視其每個演算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸演算法，理解其執行的實際步驟，並且應該熟練掌握三種遍歷的非遞歸演算法。由於二叉樹一章的很多演算法，可以直接根據三種遞歸演算法改造而來（比如：求葉子個數），所以，掌握了三種遍歷的非遞歸演算法後，對付諸如：「利用非遞歸演算法求二叉樹葉子個數」這樣的題目就下筆如有神了。我會在另一篇系列文章（）里給出三種遍歷的遞歸和非遞歸演算法的背記版，到時請大家一定熟記。
3.可在三種遍歷演算法的基礎上改造完成的其它二叉樹演算法：
求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷演算法，那麼解決以上問題就是小菜一碟了。
4.線索二叉樹：
線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現了。對於線索二叉樹，應該掌握：線索化的實質，三種線索化的演算法，線索化後二叉樹的遍歷演算法，基本線索二叉樹的其它演算法問題（如：查找某一類線索二叉樹中指定結點的前驅或後繼結點就是一類常考題）。
5.最優二叉樹（哈夫曼樹）：
最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。最優二叉樹一節，直接考查演算法源碼的很少，一般是給你一組數據，要求你建立基於這組數據的最優二叉樹，並求出其最小權值之和，此類題目不難，屬送分題。
6.樹與森林：
二叉樹是一種特殊的樹，這種特殊不僅僅在於其分支最多為2以及其它特徵，一個最重要的特殊之處是在於：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之後的二叉樹與原二叉樹我們認為是不相同的兩棵二叉樹。但是，對於普通的雙分支樹而言，不具有這種性質。
樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷演算法：先根與後根（對於森林而言稱作：先序與後序遍歷）。在難度比較大的考試中，也有基於此二種演算法的基礎上再進行擴展要求你利用這兩種演算法設計其它演算法的，但一般院校很少有這種考法，最多隻是要求你根據先根或後根寫出他們的遍歷序列。此二者的先根與後根遍歷與二叉樹中的遍歷演算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而後根遍歷對應二叉樹的中序遍歷。這一點成為很多學校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然後回答這個問題。二叉樹、樹與森林之所以能有以上的對應關系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。
樹一章，處處是重點，道道是考題，大家務必個個過關。
第六章 圖
如果說，從線性結構向樹形結構研究的轉變，是數據結構學科對數據組織形式研究的一次升華，那麼從樹形結構的研究轉到圖形結構的研究，則進一步讓我們看到了數據結構對於解決實際問題的重大推動作用。
圖這一章的特點是：概念繁多，與離散數學中圖的概念聯系緊密，演算法復雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。
下面我們看一下圖這一章的主要考點以及這些考點的考查方式：
1.考查有關圖的基本概念問題：
這些概念是進行圖一章學習的基礎，這一章的概念包括：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，迴路，（強）連通圖，（強）連通分量等概念。與這些概念相聯系的相關計算題也應該掌握。
2.考查圖的幾種存儲形式：
圖的存儲形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用演算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。
3.考查圖的兩種遍歷演算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷演算法，這兩個演算法對圖一章的重要性等同於「先序、中序、後序遍歷」對於二叉樹一章的重要性。在考查時，圖一章的演算法設計題常常是基於這兩種基本的遍歷演算法而設計的，比如：「求最長的最短路徑問題」和「判斷兩頂點間是否存在長為K的簡單路徑問題」，就分別用到了廣度遍歷和深度遍歷演算法。
4.生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM演算法和KRUSKAL演算法。
考查時，一般不要求寫出演算法源碼，而是要求根據這兩種最小生成樹的演算法思想寫出其構造過程及最終生成的最小生成樹。
5.拓撲排序問題：
拓撲排序有兩種方法，一是無前趨的頂點優先演算法，二是無後繼的頂點優先演算法。換句話說，一種是「從前向後」的排序，一種是「從後向前」排。當然，後一種排序出來的結果是「逆拓撲有序」的。
6.關鍵路徑問題：
這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑，二是最早時間是什麼意思、如何求，三是最晚時間是什麼意思、如何求。簡單地說，最早時間是通過「從前向後」的方法求的，而最晚時間是通過「從後向前」的方法求解的，並且，要想求最晚時間必須是在所有的最早時間都已經求出來之後才能進行。這個問題拿來直接考演算法源碼的不多，一般是要求按照書上的演算法描述求解的過程和步驟。
在實際設計關鍵路徑的演算法時，還應該注意以下這一點：採用鄰接表的存儲結構，求最早時間和最晚時間要採用不同的處理方法，即：在演算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。
7.最短路徑問題：
與關鍵路徑問題並稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是演算法的理解。最短路徑問題分為兩種：一是求從某一點出發到其餘各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅遊景點及旅遊路線的選擇問題。解決第一個問題用DIJSKTRA演算法，解決第二個問題用FLOYD演算法。注意區分。
第七章 查找
在不少數據結構的教材中，是把查找與排序放入高級數據結構中的。應該說，查找和排序兩章是前面我們所學的知識的綜合運用，用到了樹、也用到了鏈表等知識，對這些數據結構某一方面的運用就構成了查找和排序。
現實生活中，search幾乎無處不在，特別是現在的網路時代，萬事離不開search，小到文檔內文字的搜索，大到INTERNET上的搜索，search占據了我們上網的大部分時間。
在復習這一章的知識時，你需要先弄清楚以下幾個概念：
關鍵字、主關鍵字、次關鍵字的含義；靜態查找與動態查找的含義及區別；平均查找長度ASL的概念及在各種查找演算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。
在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹表上的查找；3rd，在哈希表上的查找。下面詳細介紹其考查知識點及考查方式：
1.線性表上的查找：
主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。考生需要注意這三種表下的ASL值以及三種演算法的實現。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。
2.樹表上的查找：
這是本章的重點和難點。由於這一節介紹的內容是使用樹表進行的查找，所以很容易與樹一間的某些概念相混淆。本節內容與樹一章的內容有聯系，但也有很多不同，應注意規納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密，二叉樹一章學好了，這里也就不難了。
二叉排序樹，簡言之，就是「左小右大」，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大於1。對於二叉排序樹，「判斷某棵二叉樹是否二叉排序樹」這一演算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整演算法，所以應該掌握平衡二叉樹的四種調整演算法，調整的一個參照是：調整前後的中序遍歷結果相同。
B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找演算法外，應該特別注意一下B樹的插入和刪除演算法。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。B樹是報考名校的同學應該關注的焦點之一。
鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。
3.基本哈希表的查找演算法：
哈希一詞，是外來詞，譯自「hash」一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。基於哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。
第八章 內部排序
內排是DS課程中最後一個重要的章節，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型演算法題。但是，歸結到一點，就是考查你對書本上的各種排序演算法及其思想以及其優缺點和性能指標（時間復雜度）能否了如指掌。
這一章，我們對重點的規納將跟以上各章不同。我們將從以下幾個側面來對排序一章進行不同的規納，以期能更全面的理解排序一章的總體結構及各種演算法。
從排序演算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸並、計數等五種排序方法。
其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序演算法的最根本的不同點，說到底就是根據什麼規則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數的總范圍「由小到大」的增量來實現排序效率提高的目的。
交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序。快速排序的思想，一語以敝之：用中間數將待排數據組一分為二。快速排序，在處理的「問題規模」這個概念上，與希爾有點相反，快速排序，是先處理一個較大規模，然後逐漸把處理的規模降低，最終達到排序的目的。
選擇排序，相對於前面幾種排序演算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據什麼規則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數；樹選擇，是通過「錦標賽」類似的思想，讓兩數相比，不斷淘汰較大（小）者，最終選出最小（大）數；而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。樹選擇排序，也曾經在一些學校中的大型演算法題中出現，請大家注意。
歸並排序，故名思義，是通過「歸並」這種操作完成排序的目的，既然是歸並就必須是兩者以上的數據集合才可能實現歸並。所以，在歸並排序中，關注最多的就是2路歸並。演算法思想比較簡單，有一點，要銘記在心：歸並排序是穩定排序。
基數排序，是一種很特別的排序方法，也正是由於它的特殊，所以，基數排序就比較適合於一些特別的場合，比如撲克牌排序問題等。基數排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數排序）。基數排序的核心思想也是利用「基數空間」這個概念將問題規模規范、變小，並且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。
本章各種排序演算法的思想以及偽代碼實現，及其時間復雜度都是必須掌握的，學習時要多注意規納、總結、對比。此外，對於教材中的10.7節，要求必須熟記，在理解的基礎上記憶，這一節幾乎成為很多學校每年的必考點。
至此，數據結構所有章節的章節重點問題，我們已經規納完畢，使用清華嚴版教材的同學，在復習的同時，可以參照本貼給出的重點進行復習。但是，由於作者本人水平有限，可能有很多考點沒有規納出來，也可能有些考點規納有誤，在此，作者本人誠懇希望諸位朋友直面提出，我會不斷完善和發布新的關於數據結構復習的總結以及筆記
嚴蔚敏數據結構為主的筆記二
第二章：線性表(包括習題與答案及要點)
--------------------------------------------------------------------------------
本章的重點是掌握順序表和單鏈表上實現的各種基本演算法及相關的時間性能分析，難點是使用本章所學的基本知識設計有效演算法解決與線性表相關的應用問題。
要求達到<識記>層次的內容有:線性表的邏輯結構特徵；線性表上定義的基本運算，並利用基本運算構造出較復雜的運算。
要求達到<綜合應用>層次的內容有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應用問題。
鏈表如何表示線性表中元素之間的邏輯關系；單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。循環鏈表上尾指針取代頭指針的作用，以及單循環鏈表上的演算法與單鏈表上相應演算法的異同點。雙鏈表的定義和相關演算法。利用鏈表設計演算法解決簡單應用問題。
要求達到<領會>層次的內容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優的時空性能。
--------------------------------------------------------------------------------
線性表的邏輯結構特徵是很容易理解的，如其名，它的邏輯結構特徵就好象是一條線，上面打了一個個結，很形象的，如果這條線上面有結，那麼它就是非空表，只能有一個開始結點，有且只能有一個終端結點，其它的結前後所相鄰的也只能是一個結點(直接前趨和直接後繼)。
關於線性表上定義的基本運算，主要有構造空表、求表長、取結點、查找、插入、刪除等。
--------------------------------------------------------------------------------
線性表的邏輯結構和存儲結構之間的關系。在計算機中，如何把線性表的結點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。
在順序表中實現的基本運算主要討論了插入和刪除兩種運算。相關的演算法我們通過練習掌握。對於順序表的插入和刪除運算，其平均時間復雜度均為O(n)。
--------------------------------------------------------------------------------
線性表的鏈式存儲結構。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結點，這組存儲單元可以分布在內存中任何位置上。因此，鏈表中結點的邏輯次序和物理次序不一定相同。所以為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其後繼結點的地址信息(即
Ⅲ C語言排序有哪些方法 詳細點
排序方法嗎應該和語言沒有太緊密的關系，關鍵看數據類型和結構，一般常用的排序方法有：
1 插入排序——細分的話還可有（1）直接插入排序（2）折半插入排序（3）希爾排序（4）2-路插入排序（5）表插入排序 等
2 比較排序——如冒泡排序，快速排序 等
3 選擇排序——如簡單選擇排序，樹形選擇排序，堆排序 等
4 歸並排序——簡單的如 2-路歸並排序 等
5 基數排序
等等
一般情況下，如果數據不大，只是簡單的自己練習或簡單的幾個十幾個或幾十個數據的話，效率分不出多少來，常用冒泡，直接插入，簡單選擇這幾種簡單的時間復雜度為O（n2）的排序方法就可以。這里舉一個簡單的小例子——比較排序中的——冒泡排序 如下：
//其中a[]是用於排序的數組變數的首地址，也即數組名,a[0]不放數據，
//用於交換時的輔助存儲空間，數據從a[1]開始存放，n表示存放的數據個數
void bubble_sort(int a[], int n){
int i = 0, j = 0, change = 0;//change用於記錄當前次比較是否進行了交換
for(i = n - 1, change = 1; i >= 1 && change; i--){//如果change是0，即已經排好序不用再進行比較了
change = 0;//將當前次的change賦值為0，記錄不交換即下次不用比較了
for(j = 1; j <= i; j++){//內循環依次將相鄰的兩個記錄進行比較
if(a[j] > a[j+1]){//小的前移，最大的移動到本次的最後一項去
a[0] = a[j+1];
a[j+1] = a[j];
a[j] = a[0];
change = 1;//進行了交換的標記
}
}
}
}
Ⅳ C語言數組排序方法
選擇排序的原理是，每次從待排序數字中挑選出最大（最小）數字，放在有序序列的末尾。實際操作中，只需要在這個數組中將挑出來的數字與前面的數字交換即可。例如：4
1 5
2 3找到最小的1，1和4交換1
4 5
2
3找到最小的2，2和4交換1
2
5
4
3找到最小的3，3和5交換1
2
3
4
5找到最小的4，4和4交換（不交換也可）可見，選擇排序需要一個雙重循環來完成，因此它的復雜度是O(n^2)在數據量比較大時，不建議使用這種排序方法。 其他排序方法有很多，你甚至可以自己根據不同數據規模設計不同的排序方法。比較常見的有冒泡排序，插入排序（這兩種和選擇排序一樣，都是O(n^2)），二分法插入排序（降低了一些復雜度，但是涉及到大規模數據移動，效率依然不高），快速排序（平均復雜度O(nlogn)，但是不穩定，最壞情況O(n^2)），隨機化快速排序（很大程度上避免了最壞情況的出現），堆排序（O(nlogn)，編程復雜度高），基數排序（理論復雜度O(n)，實際要比這個慢。甚至能應付字元串排序，但是編程復雜度高，牽扯到其他數據結構），桶排序（O(n)，編程簡單，效率高，但是應付的數據范圍不能太大，受到內存大小的限制）。 平時比較常用的就是快速排序，程序簡單，效率也可以接受。 這是我了解的一些東西，希望對你有幫助。
Ⅳ 求基數排序的演算法代碼C語言
void Sort(int *arr, int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
vector<int> *bucket = new vector<int>[max / 10 + 1];
for (int i = 0; i < n; i++)
{
int change = arr[i] / 10; //元素arr[i]所在的桶編號
bucket[change].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
{
if (bucket[i].size() > 0)
{
sort(bucket[i].begin(), bucket[i].end()); //桶內排序
}
}
int index = 0;
for (int i = 0; i < n; i++) //桶遍歷
{
for (int j = 0; j < bucket[i].size(); j++) //遍歷桶內元素
{
arr[index++] = bucket[i][j];
}
}
}
Ⅵ 求c語言基數排序與桶排序的源代碼
基數排序：
#include<math.h>
testBS()
{
inta[]={2,343,342,1,123,43,4343,433,687,654,3};
int*a_p=a;
//計算數組長度
intsize=sizeof(a)/sizeof(int);
//基數排序
bucketSort3(a_p,size);
//列印排序後結果
inti;
for(i=0;i<size;i++)
{
printf("%d ",a[i]);
}
intt;
scanf("%d",t);
}
//基數排序
voidbucketSort3(int*p,intn)
{
//獲取數組中的最大數
intmaxNum=findMaxNum(p,n);
//獲取最大數的位數，次數也是再分配的次數。
intloopTimes=getLoopTimes(maxNum);
inti;
//對每一位進行桶分配
for(i=1;i<=loopTimes;i++)
{
sort2(p,n,i);
}
}
//獲取數字的位數
intgetLoopTimes(intnum)
{
intcount=1;
inttemp=num/10;
while(temp!=0)
{
count++;
temp=temp/10;
}
returncount;
}
//查詢數組中的最大數
intfindMaxNum(int*p,intn)
{
inti;
intmax=0;
for(i=0;i<n;i++)
{
if(*(p+i)>max)
{
max=*(p+i);
}
}
returnmax;
}
//將數字分配到各自的桶中，然後按照桶的順序輸出排序結果
voidsort2(int*p,intn,intloop)
{
//建立一組桶此處的20是預設的根據實際數情況修改
intbuckets[10][20]={};
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum為上式中的1、10、100
inttempNum=(int)pow(10,loop-1);
inti,j;
for(i=0;i<n;i++)
{
introw_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++)
{
if(buckets[row_index][j]==NULL)
{
buckets[row_index][j]=*(p+i);
break;
}
}
}
//將桶中的數，倒回到原有數組中
intk=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if(buckets[i][j]!=NULL)
{
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}
桶排序
#include<stdio.h>
#defineMAXNUM100
voidbucksort(intarr[],intN,intM)
{
intcount[MAXNUM];
for(inti=0;i<=M;i++)
{
count[i]=0;
}
for(inti=0;i<N;i++)
{
++count[arr[i]];
}
for(inti=0;i<=M;i++)
{
for(intj=1;j<=count[i];j++)
{
printf("%d",i);
}
}
}
intmain()
{
inta[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6};
bucksort(a,sizeof(a)/sizeof(a[0]),12);
return0;
}
Ⅶ c語言，基數排序
如圖
//#pragmaGCCdiagnosticerror"-std=c11"
#include<stdlib.h>//有隨機數庫
#include<malloc.h>
#include<time.h>//用於產生隨機數種子
#include<string.h>
#include<stdio.h>
#defineLEN30//要多長這里改就行
intA[LEN];
intascend(constvoid*a,constvoid*b){
return*((int*)a)-*((int*)b);
}
voidprintArr(intA[],intlen){
inti;
for(i=0;i<len;++i){
printf("%d",A[i]);
if((i+1)%10==0)putchar('
');//10個數換一行
}
}
intmain(){
inti;
srand(time(0));//置隨機數種子
printf("生成隨機數：↓
");
for(i=0;i<LEN;++i){
A[i]=rand();
}
printArr(A,LEN);
printf("
排序後：↓
");
qsort(A,LEN,sizeof(int),ascend);
printArr(A,LEN);
return0;
}
Ⅷ 什麼是基數排序啊
基數排序，是」數據結構「課程中，排序演算法的一種。基數排序是一種藉助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。
如果你感興趣。想進一步了解的話。可以參閱《數據結構（C語言版）》---嚴蔚敏著。清華大學出版社出版。
Ⅸ c語言中排序方法
1、冒泡排序（最常用）
冒泡排序是最簡單的排序方法：原理是：從左到右，相鄰元素進行比較。每次比較一輪，就會找到序列中最大的一個或最小的一個。這個數就會從序列的最右邊冒出來。（注意每一輪都是從a[0]開始比較的）
以從小到大排序為例，第一輪比較後，所有數中最大的那個數就會浮到最右邊；第二輪比較後，所有數中第二大的那個數就會浮到倒數第二個位置……就這樣一輪一輪地比較，最後實現從小到大排序。
2、雞尾酒排序
雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時排序, 是冒泡排序的一種變形。該演算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。
原理：數組中的數字本是無規律的排放，先找到最小的數字，把他放到第一位，然後找到最大的數字放到最後一位。然後再找到第二小的數字放到第二位，再找到第二大的數字放到倒數第二位。以此類推，直到完成排序。
3、選擇排序
思路是設有10個元素a[1]-a[10]，將a[1]與a[2]-a[10]比較，若a[1]比a[2]-a[10]都小，則不進行交換。若a[2]-a[10]中有一個以上比a[1]小，則將其中最大的一個與a[1]交換，此時a[1]就存放了10個數中最小的一個。同理，第二輪拿a[2]與a[3]-a[10]比較，a[2]存放a[2]-a[10]中最小的數，以此類推。
4、插入排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素*
一般來說，插入排序都採用in-place在數組上實現。
具體演算法描述如下：
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從後向前掃描
⒊ 如果該元素（已排序）大於新元素，將該元素移到下一位置
⒋ 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復步驟2~5
Ⅹ C語言（簡單的）編寫程序輸入一維整形數組a[10],將其按由小到大排序後輸出
這個應該用起泡法排序演算法。
#include<stdio.h>
intmain(){
inta[10];inti,j,k;
printf("input10numbers: ");
for(i=0;i<10;i++）{//輸入十個數，一次循環輸入10次
scanf("%d",&a[i]);
printf(" ");//換行
for(j=0;j<9;j++)//從小到大換行經典方法四行
for(i=0;i<9;i++)
if(a[i]>a[i+1])
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
printf(」thesortednumbers: 」）；
for（i=0;i<10;i++）
printf("%d",a[i]);
printf(" ");
}
}
結果演示：