c語言鏈表排序演算法

❶ c語言做鏈表的排序

＃include＂stdafx．h＂
＃include＜stdlib．h＞
／／創建一個節點，data為value，指向NULL
Node＊Create（intvalue）｛
Node＊head＝（Node＊）malloc（sizeof（Node））；
head－＞data＝value；
head－＞next＝NULL；
returnhead；
｝
／／銷毀鏈表
boolDestroy＿List（Node＊head）｛
Node＊temp；
while（head）｛
temp＝head－＞next；
free（head）；
head＝temp；
｝
head＝NULL；
returntrue；
｝
／／表後添加一個節點，Create（value）
boolAppend（Node＊head，intvalue）｛
Node＊n＝Create（value）；
Node＊temp＝head；
while（temp－＞next）｛
temp＝temp－＞next；
｝
temp－＞next＝n；
return0；
｝
／／列印鏈表
voidPrint＿List（Node＊head）｛
Node＊temp＝head－＞next；
while（temp）｛
printf（＂％d－＞＂，temp－＞data）；
temp＝temp－＞next；
｝
printf（＂＼n＂）；
｝
／／在鏈表的第locate個節點後（頭節點為0）插入創建的節點Create（value）
boolInsert＿List（Node＊head，intlocate，intvalue）｛
Node＊temp＝head；
Node＊p；
Node＊n＝Create（value）；
if（locate＜0）
returnfalse；
while（locate－－）｛
if（temp－＞next＝＝NULL）｛
temp－＞next＝Create（value）；
returntrue；
｝
temp＝temp－＞next；
｝
p＝temp－＞next；
temp－＞next＝n；
n－＞next＝p；
returntrue；
｝
／／刪除第locate個節點後（頭節點為0）的節點
boolDelete＿List（Node＊head，intlocate）｛
Node＊temp＝head；
Node＊p；
if（locate＜0）
returnfalse；
while（locate－－）｛
if（temp＝＝NULL）｛
returnfalse；
｝
temp＝temp－＞next；
｝
p＝temp－＞next－＞next；
free（temp－＞next）；
temp－＞next＝NULL；
temp－＞next＝p；
returntrue；
｝
／／獲取鏈表長度（不包括頭節點）
intSize＿List（Node＊head）｛
Node＊temp＝head；
intsize＝0；
while（temp－＞next）｛
temp＝temp－＞next；
size＋＋；
｝
returnsize；
｝
／／鏈表的三種排序（選擇，插入，冒泡）
boolSort＿List（Node＊head）｛
intt＝0；
intsize＝Size＿List（head）；
／／選擇排序
／＊for（Node＊temp＝head－＞next；temp！＝NULL；temp＝temp－＞next）｛
for（Node＊p＝temp；p！＝NULL；p＝p－＞next）｛
if（temp－＞data＞p－＞data）｛
printf（＂換％d和％d＼n＂，temp－＞data，p－＞data）；
t＝temp－＞data；
temp－＞data＝p－＞data；
p－＞data＝t；
｝
｝
｝＊／
／／插入排序
／＊for（Node＊temp＝head－＞next－＞next；temp！＝NULL；temp＝temp－＞next）｛
for（Node＊p＝head；p－＞next！＝NULL；p＝p－＞next）｛
if（p－＞next－＞data＞temp－＞data）
｛
printf（＂換％d和％d＼n＂，temp－＞data，p－＞next－＞data）；
t＝temp－＞data；
temp－＞data＝p－＞next－＞data；
p－＞next－＞data＝t；
｝
｝
｝＊／
／／冒泡排序
for（Node＊temp＝head－＞next；temp－＞next！＝NULL；temp＝temp－＞next）｛
for（Node＊p＝head－＞next；p－＞next！＝NULL；p＝p－＞next）｛
if（p－＞data＞p－＞next－＞data）｛
t＝p－＞data；
p－＞data＝p－＞next－＞data；
p－＞next－＞data＝t；
｝
｝
｝
return0；
｝
(1)c語言鏈表排序演算法擴展閱讀：
return表示把程序流程從被調函數轉向主調函數並把表達式的值帶回主調函數，實現函數值的返回，返回時可附帶一個返回值，由return後面的參數指定。
return通常是必要的，因為函數調用的時候計算結果通常是通過返回值帶出的。如果函數執行不需要返回計算結果，也經常需要返回一個狀態碼來表示函數執行的順利與否（-1和0就是最常用的狀態碼），主調函數可以通過返回值判斷被調函數的執行情況。

❷ 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語言實現！

順序存儲的線性表的演算法
#include "stdio.h"
#include "stdlib.h"
#define Status int
#define OVERFLOW 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 100
typedef int ElemType;
typedef struct list
{ElemType elem[MAXSIZE];
int length;
}SqList;
void InitList(SqList &L){
L.length=0;
}
/*建立順序表*/
void CreateList(SqList &L)
{
int i;
printf("input the length");
scanf("%d",&L.length);//輸入表長
for(i=1;i<=L.length;i++)
scanf("%d",&L.elem[i-1]);//輸入元素
}
//順序表的遍歷
void printdata(ElemType e){
printf("%4d",e);
}
void Traverse(SqList L,void (*visit)(ElemType e))
{ int i;
printf("The elements of the lists are:\n");
for(i=1;i<=L.length;i++){
if (i%10==0)printf("\n");//每行顯示10個元素
visit(L.elem[i-1]);//輸出表中元素
}
printf("\n");
}

//有序順序表L中插入元素e使序列仍有序
void Insert(SqList &L,ElemType e)
{int i,j;
if (L.length==MAXSIZE)exit(OVERFLOW);//表滿,不能插入
for(i=1;i<=L.length&&L.elem[i-1]<=e;i++);//向後查找
for(j=L.length;j>=i;j--)
L.elem[j]=L.elem[j-1];//元素後移
L.elem[i-1]=e;//插入e
L.length=L.length+1;//表長加1
}
//建立遞增有序的順序表
void CreateList_Sorted(SqList &L)
{int i,num;
ElemType e;
L.length=0;
printf("Create a sorted list,Input the length of the list\n");
scanf("%d",&num);
printf("Input the data %d numbers\n",num);
for(i=1;i<=num;i++){
scanf("%d",&e);
Insert(L,e);
}
}
/*Merge two sorted lists*/
void MergeList(SqList La,SqList Lb,SqList &Lc)
{int *pa,*pb,*pc;
if (La.length+Lb.length>MAXSIZE) exit(OVERFLOW);
else
{pa=La.elem;pb=Lb.elem;pc=Lc.elem;
while (pa<La.elem+La.length&&pb<Lb.elem+Lb.length)
*pc++=(*pa<=*pb)?*pa++:*pb++;/*公共部分合並*/
while (pa<La.elem+La.length) *pc++=*pa++;
/*R1表的剩餘部分放到R的後部*/
while (pb<Lb.elem+Lb.length) *pc++=*pb++;
/*R2表的剩餘部分放到R的後部*/
Lc.length=La.length+Lb.length;/*R表長*/
}
}
//判斷元素是否對稱，對稱返回TRUE 否則返回FALSE
Status Symmetric(SqList L)
{int low,high;
low=0;
high=L.length-1;
while(low<high)
if (L.elem[low]==L.elem[high]){low++;high--;}
else return(FALSE); return(TRUE); }
//順序表的主函數部分
//#include "seqlist.h"
void main()
{SqList L1,L2,L;
int select;
ElemType e;
do{printf("\n1 insert 2 merge");
printf("\n3 symmetric 0 exit \n");
printf("Please select(0--3)\n");
scanf("%d",&select);
switch(select){
case 1:
InitList(L);
CreateList_Sorted(L);
Traverse(L,printdata);
printf("\nInput the element of inserted\n");
scanf("%d",&e);
Insert(L,e);
Traverse(L,printdata);
break;
case 2:
InitList(L1);
CreateList_Sorted(L1);
Traverse(L1,printdata);
InitList(L2);
CreateList_Sorted(L2);
Traverse(L2,printdata);
InitList(L);
MergeList(L1,L2,L);
Traverse(L,printdata);
break;
case 3:
InitList(L);
CreateList(L);
Traverse(L,printdata);
if (Symmetric(L)) printf("Yes!\n"); else printf("Not\n");
break;
case 0:break;
default:printf("Error! Try again!\n");
}
}while(select);
}

/*單向鏈表的有關操作示例*/
/*類型定義及頭文件部分,文件名為sllink.h*/
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;//元素實際類型
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList; //定義結點、指針類型名
//頭插法建立無序鏈表
void CreateList(LinkList &L){
LinkList p;
ElemType e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("頭插法建立鏈表，以0結束\n");
scanf("%d",&e);
while(e){
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=L->next;
L->next=p;
scanf("%d",&e);
}
}
/*非遞減有序單向鏈表L插入元素e序列仍有序*/
void Insert_Sort(LinkList &L,ElemType e){
LinkList p,s;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
p=L;
while(p->next&&p->next->data<=e)
p=p->next;/*查找插入位置*/
s->next=p->next; /*插入語句*p結點後插入*s結點*/
p->next=s;
}
/*建立遞增有序的單向鏈表*/
void Create_Sort(LinkList &L){
ElemType e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("建立有序表，輸入任意個整型數據以0結束\n");
scanf("%d",&e);
while(e){
Insert_Sort(L,e);
scanf("%d",&e);
}
}
/*單向鏈表的遍歷*/
void Traverse(LinkList L){
LinkList p;
printf("遍歷鏈表");
for(p=L->next;p;p=p->next)
printf("%5d",p->data);
printf("\n");
}
/*在單向鏈表刪除元素e*/
void Delete(LinkList &L,ElemType e){
LinkList p,q;
p=L;
q=L->next;
while(q&& q->data!=e){//查找元素的刪除位置
p=q;
q=q->next;
}
if(!q) printf("\nnot deleted");/*未找到元素e*/
else {p->next=q->next;/*找到刪除*/
free(q);}
}
/*單向鏈表的逆置*/
void exch(LinkList &L){
LinkList p,s;
p=L->next;
L->next=NULL;
while(p){
s=p;
p=p->next;
s->next=L->next;
L->next=s;
}
}
/*兩個非遞減有序單向鏈表合並後仍為非遞減序列*/
void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc){
LinkList p,q,s,rear;
p=La->next;
q=Lb->next;
Lc=rear=La;
free(Lb);
while(p&&q){
if (p->data<q->data) {s=p;p=p->next; }
else {s=q;q=q->next; }
rear->next=s;/*較小元素插入表尾*/
rear=rear->next;
}
if (p) rear->next=p; else rear->next=q;
}

/*主函數部分,文件名為sllink.c*/
//#include "sllink.h"
void main(){
LinkList La,Lb,Lc;
ElemType e;
int select;
do{
printf(" 1 建立無序表，再刪除指定元素\n");
printf(" 2 建立遞增有序表，再逆置\n");
printf(" 3 建立兩個遞增有序表，將它們和並為一個仍遞增表\n");
printf(" 0 退出，請輸入選項(0-3)\n");
scanf("%d",&select);
switch(select){
case 0:
break;
case 1:
CreateList(La);
Traverse(La);
printf("輸入需刪除的元素\n");
scanf("%d",&e);
Delete(La,e);
Traverse(La);
break;
case 2:
Create_Sort(La);
Traverse(La);
exch(La);
printf("The list that is exchaged\n");
Traverse(La);
break;
case 3:
Create_Sort(La);Traverse(La);
Create_Sort(Lb);Traverse(Lb);
MergeIncrease(La,Lb,Lc);Traverse(Lc);
break;
default:
printf("輸入選項錯誤，請重新輸入！\n");
}

}while(select);
}
這些內容不知道能不能幫助到你。

❹ c語言數據結構（雙向鏈表排序）

#include<stdio.h>
#include<malloc.h>

#define ElemType int

int count=0;

typedef struct DulNode
{
ElemType data;
DulNode *prior;
DulNode *next;
}DulNode,*DulLinkList;

//初始化鏈表，結束後產生一個頭結點指針
void InitDLList(DulLinkList *L)
{
(*L)=(DulLinkList)malloc(sizeof(DulNode));
(*L)->next=*L;
(*L)->prior=(*L)->next;
}
//對鏈表進行插入操作
void ListInsert(DulLinkList *L)
{
int i=0,n;
ElemType temp;
DulNode *s,*p;
p=(*L)->next;
printf("請輸入插入元素數量：\n");
scanf("%d",&n);
count=n;
printf("請輸入%d個自然數\n",n);
while(i<n)
{
scanf("%d",&temp);
s=(DulNode*)malloc(sizeof(DulNode));
s->data=temp;
while((p!=(*L))&&(p->data<temp))//查找所要插入的位置
{
p=p->next;
}

s->prior=p->prior;//新節點的插入
s->next=p;
p->prior->next=s;
p->prior=s;

p=(*L)->next;//將指針回指到鏈表第一個非空節點，主要是為了下次查找插入位置
i++;
}
}
void Display(DulLinkList L)
{
DulNode *p;
p=L->next;
printf("雙向鏈表中的數據為:\n");
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void Sort(DulLinkList *L)
{
ElemType temp;
DulNode *p,*q;
p=(*L)->next;
q=(*L)->prior;
if(count%2!=0)
q=q->prior;
p=p->next;

while(p!=q)
{
temp=p->data;
p->data=q->data;
q->data=temp;

p=p->next;

if(p!=q) //第二題只需交換節點數據
q=q->prior;//這幾個if else語句需要仔細
else
break;
if(p!=q)
p=p->next;
else
break;
if(p!=q)
q=q->prior;
else
break;
}

}
void main()
{
DulLinkList L;
InitDLList(&L);//初始化鏈表
ListInsert(&L);//順序插入數據
Display(L);//顯示結果
Sort(&L);//第二題操作
Display(L);//第二題輸出結果
}