c單鏈表排序演算法

A. 計算機二級c語言考些什麼

公共基礎知識
基本要求
1. 掌握演算法的基本概念。
2. 掌握基本數據結構及其操作。
3. 掌握基本排序和查找演算法。
4. 掌握逐步求精的結構化程序設計方法。
5. 掌握軟體工程的基本方法，具有初步應用相關技術進行軟體開發的能力。
6. 掌握數據的基本知識，了解關系資料庫的設計。
考試內容
一、 基本數據結構與演算法
1. 演算法的基本概念；演算法復雜度的概念和意義（時間復雜度與空間復雜度）。
2. 數據結構的定義；數據的邏輯結構與存儲結構；數據結構的圖形表示；線性結構與非線性結構的概念。
3. 線性表的定義；線性表的順序存儲結構及其插入與刪除運算。
4. 棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。
5. 線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。
6. 樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和後序遍歷。(前序、中序和後序遍歷有考到，每年都有)
7. 順序查找與二分法查找演算法；基本排序演算法（交換類排序，選擇類排序，插入類排序）。
二、 程序設計基礎
1. 程序設計方法與風格。
2. 結構化程序設計。
3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態性。
三、 軟體工程基礎
1. 軟體工程基本概念，軟體生命周戎概念，軟體工具與軟體開發環境。
2. 結構化分析方法，數據流圖，數據字典，軟體需求規格說明書。
3. 結構化設計方法，總體設計與詳細設計。
4. 軟體測試的方法，白盒測試與黑盒測試，測試用例設計，軟體測試的實施，單元測試、集成測試和系統測試。
5. 程序的調試，靜態調試與動態調試。
四、 資料庫設計基礎
1. 資料庫的基本概念：資料庫，資料庫管理系統，資料庫系統。
2. 數據模型，實體聯系模型及E-R圖，從E-R圖導出關系數據模型。
3. 關系代數運算，包括集合運算及選擇、投影、連接運算，資料庫規范化理論。
4. 資料庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。
考試方式
1、 公共基礎的考試方式為筆試，與C語言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的筆試部分合為一張試卷。公共基礎部分佔全卷的30分。
2、 公共基礎知識有10道選擇題和5道填空題。
C語言程序設計
基本要求
1.熟悉TURBO C集成環境。
2.熟練掌握結構化程序設計的方法，具有良好的程序設計風格。
3.掌握程序設計中簡單的數據結構和演算法。
4.TURBO C的集成環境下，能夠編寫簡單的C程序，並具有基本的糾錯和調試程序的能力。
考試內容
一、C語言的結構
1.程序的構成，MAIN函數和其他函數。
2.頭文件，數據說明，函數的開始和結束標志。
3.源程序的書寫格式
4.C語言的風格。
二、數據類型及其運算(基礎)
1.C的數據類型（基本類型，構造類型，指針類型，空類型）及其定義方法。
2.C運算符的種類、運算優先順序和結合性。
3.不同類型數據間的轉換與運算。
4.C表達式類型（賦值表達式、算術表達式、關系表達式、邏輯表達式、條件表達式、逗號表達式）和求值規則。
三、基本語句(基礎)
1.表達式語句，空語句，復合語句。
2.數據的輸入和輸出，輸入輸出函數的調用。
3.復合語句。
4.GOTO語句和語句標號的使用。(這個了解即可)
四、選擇結構程序設計
1.用if語句實現選擇結構。(基礎)
2.用switch語句實現多分支選擇結構。(筆試有)
3.選擇結構的嵌套。
五、循環結構程序設計 (基礎)
1.for 循環結構。
2.while和do while循環結構。
3.continue語句和break語句。
4.循環的嵌套。(基礎)
六、數組的定義和引用
1.一維數組和多維數組的定義、初始化和引用。
2.字元串與字元數組。
七、函數 (基礎)
1.庫函數的正確調用。
2.函數的定義方法。
3.函數的類型和返回值。
4.形式參數與實在參數,參數值的傳遞。
5.函數的正確調用,嵌套調用,遞歸調用。
6.局部變數和全局變數。
7.變數的存儲類別(自動、靜態、寄存器、外部),變數的作用域和生存期。
8.內部函數與外部函數。
八、編譯預處理 (基礎，筆試有考到宏替換)
1.宏定義:不帶參數的宏定義;帶參數的宏定義。
2.「文件包含」處理。
九、指針 (這個很重要，上機題有這方面的)
1.指針與指針變數的概念,指針與地址運算符。
2.變數、數組、字元串、函數、結構體的指針以及指向變數、數組、字元串、函數、結構體的指針變數。通過指針引用以上各類型數據。
3.用指針作函數參數。
4.返回指針值的指針函數。
5.指針數組,指向指針的指針,MAIN函數的命令行參數。
十、結構體(即「結構」)與共用體(即「聯合」)
1.結構體和共用體類型數據的定義方法和引用方法。
2.用指針和結構體構成鏈表,單向鏈表的建立、輸出、刪除與插入。
十一、位運算
1.位運算符的含義及使用。
2.簡單的位運算。
十二、文件操作(了解，上級題有，只要知道什麼意思就行了)
只要求緩沖文件系統(即高級磁碟I/O系統),對非標准緩沖文件系統(即低級磁碟I/O系統)不要求。
1.文件類型指針(FILE類型指針)。
2.文件的打開與關閉(fopen,fclose)。
3.文件的讀寫(fputc,fgetc,fputs,fgets,fread,frwite,fprintf,fscanf函數),文件的定位(rewind,fseek函數)。
PS：分為筆試和機試兩部份，機試有三道題，一道改錯，一道補充，一道綜合，筆試中有30分公共基礎知識，為數據結構，資料庫，網路和電腦常識方面的問題，有70分選擇題，30分填空題，難點為數組，指針，也為重點
全國計算機等級考試調整方案
關於二級
考試科目：新增二級Delphi語言程序設計，加上原有的二級C等六個科目，二級共七個科目。二級科目分成兩類，一類是語言程序設計（C、C++、Java、Visual Basic、Delphi），另一類是資料庫程序設計（Visual FoxPro、Access）。
考核內容：二級定位為程序員，考核內容包括公共基礎知識和程序設計。所有科目對基礎知識作統一要求，使用統一的公共基礎知識考試大綱和教程。二級公共基礎知識在各科筆試中的分值比重為30%（30分）。程序設計部分的比重為70%（70分），主要考查考生對程序設計語言使用和編程調試等基本能力。
考試形式：二級所有科目的考試仍包括筆試和上機考試兩部分。二級C筆試時間由120分鍾改為90分鍾，上機時間由60分鍾改為90分鍾。所有二級科目的筆試時間統一為90分鍾，上機時間統一為90分鍾。
系統環境：二級各科目上機考試應用軟體為：中文專業版Access 2000、中文專業版Visual Basic 6.0、中文專業版Visual FoxPro 6.0、Visual C++ 6.0，二級C上機應用軟體由Turbo C 2.0改為 Visual C++6.0，二級Java由現在的Java JDK 1.4.2改為專用集成開發環境「NetBeans 中國教育考試版2007」（有關網站將提供免費下載），二級Delphi使用Delphi7.0版本。

B. 拓撲排序

1、堆棧

棧是一種特殊的線性表，插入或刪除棧元素的運算只能在表的一端進行，稱運算的一端為棧頂，另一端稱為棧底。隊列也是一種特殊的線性表（基本操作都是線性操作的子集）。

特點：後進先出

棧又稱為「後進先出」的線性表，簡稱LIFO表。

棧的鏈式實現是以鏈表作為棧的存儲結構，並在這種存儲結構上實現棧的基本運算。棧的鏈式實現稱為鏈棧。

2、有向無環圖

描述含有公共子式的表達式的有效工具；

描述一項工程或系統的進行過程的有效工具。

3、一些概念

通常我們把計劃、施工過程、生產流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。這些活動完成時，整個工程也就完成了。

我們用一種有向圖來表示這些工程、計劃等，在這種有向圖中，頂點表示活動，有向邊表示活動的優先關系，這種用頂點表示活動，用弧來表示活動間的優先關系的有向圖叫做頂點表示活動的網路(ActireOnVertices)簡稱為AOV網。

拓撲排序：

假設G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列vl，v2，…，vn稱做一個拓撲序列(TopologicalOrder)，當且僅當該頂點序列滿足下列條件：若在有向圖G中存在從頂點vi到vj的一條路徑，則在頂點序列中頂點vi必須排在頂點vj之前。通常，在AOV網中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序掘虧(TopologicalSort)。

在AOV網中不應該出現有向環。因為環的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。

判定網中是否存在環的方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都出現在它的拓撲有序序列中，則該AOV網中一定不存在環。

4、拓撲排序的演算法思想

輸入AOV網路。令n為頂點個數。

（1）在AOV網路中選一個沒有直接前驅的頂點，並輸出之；

（2）從圖中刪去該頂點,同時刪去所有它發出的有向邊；

重復以上步驟，直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網路中必定存在有向環。

5、拓撲排序演算法的C語言描述

在實現拓撲排序的演算法中，採用鄰接表作為有向圖的存儲結構，每個頂點設置一個單鏈表，每個單鏈表有一個表頭結點，在表頭結點中增加一個存放頂點入度的域count，這些表頭結點構成一個數組。

為了避免重復檢測入度為0的點，另設一棧存放所有入度為0的點。

對於有n個頂點和e條邊的有向圖而言，for循環中建立入度為0的頂點棧時間為O（n）；若在拓撲排序過程中不出現有向環，則判擾神每個頂點出棧、入棧和入度減1的操作在while循環語句中均執行e次，因此拓撲排序總的時間花費為O(n+e)。

6、拓撲排序演算法的C語言實現

#include"stdio.h"

#defineMAX_VERTEX_NUM20

#include"conio.h"

#include"stdlib.h"

#defineSTACK_INIT_SIZE16

#defineSTACKINCREMENT5

typedef intSElemType;

typedefcharVertexType;

typedefstruct

{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;

//我們依然用鄰接表來作圖的存儲結構

typedefstructArcNode{

intadjvex;

struct李歷ArcNode*nextarc;

intinfo;

}ArcNode; //表結點類型

typedefstructVNode{

VertexTypedata;

intcount;

ArcNode*firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];//頭結點

typedefstruct{

AdjListvertices; //鄰接表

intvexnum,arcnum;

}ALGraph;

intInitStack(SqStack&S)

{

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(-1);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return1;

}//InitStack

intPush(SqStack&S,SElemTypee)

{

if((S.top-S.base)>=S.stacksize)

{

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(-1);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}//if

*(S.top)=e;

S.top++;

return1;

}//Push

intPop(SqStack&S,SElemType&e)

{

if(S.top==S.base)return0;

--S.top;

e=*S.top;

return1;

}//Pop

intStackEmpty(SqStack&S)

{

if(S.top==S.base)return1;

elsereturn0;

}//StackEmpty

intLocateVex(ALGraphG,charu)

{

inti;

for(i=0;i<G.vexnum;i++)

{if(u==G.vertices[i].data)returni;}

if(i==G.vexnum){printf("Erroru! ");exit(1);}

return0;

}

voidCreateALGraph_adjlist(ALGraph&G)

{

inti,j,k,w;

charv1,v2,enter;

ArcNode*p;

printf("Inputvexnum&arcnum: ");

scanf("%d",&G.vexnum);

scanf("%d",&G.arcnum);

printf("InputVertices(以回車隔開各個數據): ");

for(i=0;i<G.vexnum;i++)

{ scanf("%c%c",&enter,&G.vertices[i].data);//注意點，解說

G.vertices[i].firstarc=NULL;

}//for

printf("InputArcs(v1,v2,w)以回車分開各個數據: ");

for(k=0;k<G.arcnum;k++)

{

scanf("%c%c",&enter,&v1);

scanf("%c%c",&enter,&v2);

//scanf("%d",&w);

i=LocateVex(G,v1);

j=LocateVex(G,v2);

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

//p->info=w;

p->nextarc=G.vertices[i].firstarc;//前插法,即每次都插入到頭結點的後面

G.vertices[i].firstarc=p;

printf("Next ");

}//for

return;

}//CreateALGraph_adjlist

voidFindInDegree(ALGraph&G)

{

inti,j;

for(i=0;i<G.vexnum;i++)

{

G.vertices[i].count=0;

}//for

for(j=0;j<G.vexnum;j++)

{

//G.vertices[i].count++;

for(ArcNode*p=G.vertices[j].firstarc;p;p=p->nextarc)

G.vertices[p->adjvex].count++;

}//for

}//FindInDegree

intTopoSort(ALGraph&G)

{

SqStackS;

FindInDegree(G);

InitStack(S);

for(inti=0;i<G.vexnum;i++)

if(G.vertices[i].count==0)Push(S,i);

intcountt=0;

while(!StackEmpty(S))

{

inti,m;

m=Pop(S,i);

printf("%c",G.vertices[i].data);++countt;

for(ArcNode*p=G.vertices[i].firstarc;p;p=p->nextarc)

{ intk;

k=p->adjvex;

if(!(--G.vertices[k].count))Push(S,k);

}//for

}//while

if(countt<G.vexnum)return0;

elsereturn1;

}//TopoSort

intmain()

{

ALGraphG;

CreateALGraph_adjlist(G);

TopoSort(G);

return1;

}

7、malloc函數和realloc函數

realloc:void*realloc(void*block,size_tsize)，將block所指存儲塊調整為大小size，返回新塊的地址。如能滿足要求，新塊的內容與原塊一致；不能滿足要求時返回NULL，此時原塊不變。

C. 採用單鏈表作存儲結構，編寫一個採用選擇排序演算法進行升序排序的函數。 單鏈表的結構如下：

下面大體介紹一下基本思想：由於是遞增的單鏈表：0->0->0->0 這種結構不能逆向反問；所以直接做操作是很不好實現的；所以我第一步是將兩鏈表的指針反轉，這樣就使原來兩鏈表由遞增序列變成了遞減序列；第二步在根據合並排序的思想，將兩個鏈合並； 思路比較簡單，你一看因該能明白，我用C++實現了一下想法，代碼如下：#include <iostream>using namespace std;const int N = 8;struct Node};void Print(Node* p)while(p); cout << endl;}void Create(Node*& List) }}void Sort(Node*& List) }}void Converse(Node*& List) //將鏈表中指針逆向,實際上就是將遞增序列變為遞減序列 List = q; q->next = p;}void Merge(Node*& List1, Node*&List2, Node*& List3) else } //將剩餘的直接接過去即可； if(p == 0) tail->next = q; else tail->next = p;}int main()

D. 常見查找和排序演算法

查找成功最多要n 次，平均（n+1）/2次， 時間復雜度為O(n) 。
優點：既適用順序表也適用單鏈表，同時對表中元素順序無要求，給插入帶來方便，只需插入表尾即可。
缺點：速度較慢。

改進：在表尾設置一個崗哨，這樣不用去循環判斷數組下標是否越界，因為最後必然成立。

適用條件：

二分查找的判定樹不僅是二叉排序樹，而且是一棵理想平衡樹。 時間復雜度為O(lbn) 。

循環實現

遞歸實現

待排序的元素需要實現 Java 的 Comparable 介面，該介面有 compareTo() 方法，可以用它來判斷兩個元素的大小關系。

從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。

選擇排序需要 ~N2/2 次比較和 ~N 次交換，==它的運行時間與輸入無關==，這個特點使得它對一個已經排序的數組也需要這么多的比較和交換操作。

從左到右不斷 交換相鄰逆序的元素 ，在一輪的循環之後，可以讓未排序的最大元素上浮到右側。

在一輪循環中，如果沒有發生交換，那麼說明數組已經是有序的，此時可以直接退出。

每次都 將當前元素插入到左側已經排序的數組中 ，使得插入之後左側數組依然有序。

對於數組 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交換相鄰元素，令逆序數量減少 1，因此插入排序需要交換的次數為逆序數量。

==插入排序的時間復雜度取決於數組的初始順序，如果數組已經部分有序了，那麼逆序較少，需要的交換次數也就較少，時間復雜度較低==。

對於大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大於 1。

希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最後令 h=1，就可以使得整個數組是有序的。

希爾排序的運行時間達不到平方級別，使用遞增序列 1, 4, 13, 40, ... 的希爾排序所需要的比較次數不會超過 N 的若干倍乘於遞增序列的長度。後面介紹的高級排序演算法只會比希爾排序快兩倍左右。

歸並排序的思想是將數組分成兩部分，分別進行排序，然後歸並起來。

歸並方法將數組中兩個已經排序的部分歸並成一個。

將一個大數組分成兩個小數組去求解。

因為每次都將問題對半分成兩個子問題，這種對半分的演算法復雜度一般為 O(NlogN)。

先歸並那些微型數組，然後成對歸並得到的微型數組。

取 a[l] 作為切分元素，然後從數組的左端向右掃描直到找到第一個大於等於它的元素，再從數組的右端向左掃描找到第一個小於它的元素，交換這兩個元素。不斷進行這個過程，就可以保證左指針 i 的左側元素都不大於切分元素，右指針 j 的右側元素都不小於切分元素。當兩個指針相遇時，將切分元素 a[l] 和 a[j] 交換位置。

快速排序是原地排序，不需要輔助數組，但是遞歸調用需要輔助棧。

快速排序最好的情況下是每次都正好將數組對半分，這樣遞歸調用次數才是最少的。這種情況下比較次數為 CN=2CN/2+N，復雜度為 O(NlogN)。

最壞的情況下，第一次從最小的元素切分，第二次從第二小的元素切分，如此這般。因此最壞的情況下需要比較 N2/2。為了防止數組最開始就是有序的，在進行快速排序時需要隨機打亂數組。

因為快速排序在小數組中也會遞歸調用自己，對於小數組，插入排序比快速排序的性能更好，因此在小數組中可以切換到插入排序。

最好的情況下是每次都能取數組的中位數作為切分元素，但是計算中位數的代價很高。一種折中方法是取 3 個元素，並將大小居中的元素作為切分元素。

對於有大量重復元素的數組，可以將數組切分為三部分，分別對應小於、等於和大於切分元素。

三向切分快速排序對於有大量重復元素的隨機數組可以在線性時間內完成排序。

快速排序的 partition() 方法，會返回一個整數 j 使得 a[l..j-1] 小於等於 a[j]，且 a[j+1..h] 大於等於 a[j]，此時 a[j] 就是數組的第 j 大元素。

可以利用這個特性找出數組的第 k 大的元素。

該演算法是線性級別的，假設每次能將數組二分，那麼比較的總次數為 (N+N/2+N/4+..)，直到找到第 k 個元素，這個和顯然小於 2N。

堆中某個節點的值總是大於等於其子節點的值，並且堆是一顆完全二叉樹。

堆可以用數組來表示，這是因為堆是完全二叉樹，而完全二叉樹很容易就存儲在數組中。位置 k 的節點的父節點位置為 k/2，而它的兩個子節點的位置分別為 2k 和 2k+1。這里不使用數組索引為 0 的位置，是為了更清晰地描述節點的位置關系。

在堆中，當一個節點比父節點大，那麼需要交換這個兩個節點。交換後還可能比它新的父節點大，因此需要不斷地進行比較和交換操作，把這種操作稱為上浮。

類似地，當一個節點比子節點來得小，也需要不斷地向下進行比較和交換操作，把這種操作稱為下沉。一個節點如果有兩個子節點，應當與兩個子節點中最大那個節點進行交換。

將新元素放到數組末尾，然後上浮到合適的位置。

從數組頂端刪除最大的元素，並將數組的最後一個元素放到頂端，並讓這個元素下沉到合適的位置。

把最大元素和當前堆中數組的最後一個元素交換位置，並且不刪除它，那麼就可以得到一個從尾到頭的遞減序列，從正向來看就是一個遞增序列，這就是堆排序。

一個堆的高度為logN，因此在堆中插入元素和刪除最大元素的復雜度都為 logN。

對於堆排序，由於要對 N 個節點進行下沉操作，因此復雜度為 NlogN。

堆排序是一種原地排序，沒有利用額外的空間。

現代操作系統很少使用堆排序，因為它無法利用局部性原理進行緩存，也就是數組元素很少和相鄰的元素進行比較和交換。

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，==計數排序要求輸入的數據必須是有確定范圍的整數==。

當輸入的元素是 n 個 0 到 k 之間的整數時，它的==運行時間是 O(n + k)==。計數排序不是比較排序，排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的范圍（等於待排序數組的最大值與最小值的差加上1），這使得計數排序對於數據范圍很大的數組，需要大量時間和內存。比較適合用來排序==小范圍非負整數數組的數組==。

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

同時，對於桶中元素的排序，選擇何種比較排序演算法對於性能的影響至關重要。

當輸入數據均勻分配到每一個桶時最快，當都分配到同一個桶時最慢。

實間復雜度N*K

快速排序是最快的通用排序演算法，它的內循環的指令很少，而且它還能利用緩存，因為它總是順序地訪問數據。它的運行時間近似為 ~cNlogN，這里的 c 比其它線性對數級別的排序演算法都要小。

使用三向切分快速排序，實際應用中可能出現的某些分布的輸入能夠達到線性級別，而其它排序演算法仍然需要線性對數時間。