數據結構演算法實現及解析c
① 數據結構（C語言版） 中一題目的演算法
/***
*
*題目：已知
線性表
中的元素以值遞增有序排列，並以
單鏈表
做存儲結構。試寫一高效的演算法，
*
刪除表中所有值大於
mink
且小於
maxk
的元素（若表中存在這樣的元素）,同時釋放
*
被刪除節點空間，並分析你的演算法的
時間復雜度
（注意：mink
和
maxk
是給定的兩個
*
參變數，它們的值可以和表中的元素相同，也可以不同）
*
****/
#include
#include
#include
"DynaLinkList.h"
void
DelMminMax(LinkList
*L,
int
min,
int
max)
{
LinkList
p
=
(*L)->next,
q
=
(*L),
r;
while
(p
&&
p->data
<=
min)
{
q
=
p;
p
=
p->next;
}
while
(
p
&&
p->data
<
max)
{
r
=
p;
p
=
p->next;
q->next
=
p;
free(r);
}
}
//演算法的時間復雜度為O(n)
int
main()
{
LinkList
L;
ElemType
e,
min,
max;
InitList(&L);
printf("輸入8個元素建立線性表L(元素遞增有序):\n");
for
(int
i=1;
i<=8;
i++)
{
scanf("%d",
&e);
ListInsert(&L,
i,
e);
}
printf("表L是：\n");
ListTraverse(L,
visit);
printf("請輸入待刪除的元素的區間是(min,max):\n");
scanf("%d%d",
&min,
&max);
DelMminMax(&L,min,max);
printf("刪除(%d,%d)之間的元素後表L是：\n",min,max);
ListTraverse(L,
visit);
return
0;
}
② 數據結構與演算法分析：C語言描述的內容簡介
《數據結構與演算法分析:C語言描述(原書第2版)》內容簡介：書中詳細介紹了當前流行的論題和新的變化，討論了演算法設計技巧，並在研究演算法的性能、效率以及對運行時間分析的基礎上考查了一些高級數據結構，從歷史的角度和近年的進展對數據結構的活躍領域進行了簡要的概括。由於《數據結構與演算法分析:C語言描述(原書第2版)》選材新穎，方法實用，題例豐富，取捨得當。《數據結構與演算法分析:C語言描述(原書第2版)》的目的是培養學生良好的程序設計技巧和熟練的演算法分析能力，使得他們能夠開發出高效率的程序。從服務於實踐又鍛煉學生實際能力出發，書中提供了大部演算法的C程序和偽碼常式，但並不是全部。一些程序可從互聯網上獲得。
《數據結構與演算法分析:C語言描述(原書第2版)》是《Data Structures and Algorithm Analysis in C》一書第2版的簡體中譯本。原書曾被評為20世紀頂尖的30部計算機著作之一，作者Mark Allen Weiss在數據結構和演算法分析方面卓有建樹，他的數據結構和演算法分析的著作尤其暢銷，並受到廣泛好評．已被世界500餘所大學用作教材。
在《數據結構與演算法分析:C語言描述(原書第2版)》中，作者更加精煉並強化了他對演算法和數據結構方面創新的處理方法。通過C程序的實現，著重闡述了抽象數據類型的概念，並對演算法的效率、性能和運行時間進行了分析。
全書特點如下：
●專用一章來討論演算法設計技巧，包括貪婪演算法、分治演算法、動態規劃、隨機化演算法以及回溯演算法
●介紹了當前流行的論題和新的數據結構，如斐波那契堆、斜堆、二項隊列、跳躍表和伸展樹
●安排一章專門討論攤還分析，考查書中介紹的一些高級數據結構
●新開辟一章討論高級數據結構以及它們的實現，其中包括紅黑樹、自頂向下伸展樹。treap樹、k-d樹、配對堆以及其他相關內容
●合並了堆排序平均情況分析的一些新結果
《數據結構與演算法分析:C語言描述(原書第2版)》是國外數據結構與演算法分析方面的標准教材，介紹了數據結構(大量數據的組織方法)以及演算法分析(演算法運行時間的估算)。《數據結構與演算法分析:C語言描述(原書第2版)》的編寫目標是同時講授好的程序設計和演算法分析技巧，使讀者可以開發出具有最高效率的程序。 《數據結構與演算法分析:C語言描述(原書第2版)》可作為高級數據結構課程或研究生一年級演算法分析課程的教材，使用《數據結構與演算法分析:C語言描述(原書第2版)》需具有一些中級程序設計知識，還需要離散數學的一些背景知識。
③ 數據結構如何通過C語言來實現，請舉例說明，盡可能詳細
數據的結構無非就是表：線性表、鏈表，棧，隊列，串，數組，樹、二叉樹，圖，這幾種。
常用的使用指針，或數組建立數據結構，然後對其進行插入、刪除、查找、排序等操作。
以下是C語言實現的循環隊列：
#include<stdio.h>
#include<stdlib.h>
#define MAX_QSIZE 5
struct SqQueue
{ QElemType *base; // 初始化的動態分配存儲空間
int front; // 頭指針，若隊列不空，指向隊列頭元素
int rear; // 尾指針，若隊列不空，指向隊列尾元素的下一個位置
};
// bo3-4.cpp 循環隊列(存儲結構由c3-3.h定義)的基本操作(9個)
void InitQueue(SqQueue &Q)
{ // 構造一個空隊列Q。在教科書第64頁
Q.base=(QElemType*)malloc(MAX_QSIZE*sizeof(QElemType));
if(!Q.base) // 存儲分配失敗
exit(OVERFLOW);
Q.front=Q.rear=0;
}
void DestroyQueue(SqQueue &Q)
{ // 銷毀隊列Q，Q不再存在
if(Q.base) // 隊列Q存在
free(Q.base); // 釋放Q.base所指的存儲空間
Q.base=NULL; // Q.base不指向任何存儲單元
Q.front=Q.rear=0;
}
void ClearQueue(SqQueue &Q)
{ // 將隊列Q清為空隊列
Q.front=Q.rear=0;
}
int QueueEmpty(SqQueue Q)
{ // 若隊列Q為空隊列，則返回TRUE；否則返回FALSE
if(Q.front==Q.rear) // 隊列空的標志
return TRUE;
else
return FALSE;
}
int GetHead(SqQueue Q,QElemType &e)
{ // 若隊列Q不空，則用e返回Q的隊頭元素，並返回OK；否則返回ERROR
if(Q.front==Q.rear) // 隊列空
return ERROR;
e=Q.base[Q.front]; // 將隊頭元素的值賦給e
return OK;
}
int EnQueue(SqQueue &Q,QElemType e)
{ // 插入元素e為隊列Q的新的隊尾元素。在教科書第65頁
if((Q.rear+1)%MAX_QSIZE==Q.front) // 隊列滿
return ERROR;
Q.base[Q.rear]=e; // 將e插在隊尾
Q.rear=(Q.rear+1)%MAX_QSIZE; // 隊尾指針+1後對MAX_QSIZE取余
return OK;
}
int QueueLength(SqQueue Q)
{ // 返回隊列Q的元素個數，即隊列的長度。在教科書第64頁
return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
}
int DeQueue(SqQueue &Q,QElemType &e) // 在教科書第65頁
{ // 若隊列Q不空，則刪除Q的隊頭元素，用e返回其值，並返回OK；否則返回ERROR
if(Q.front==Q.rear) // 隊列空
return ERROR;
e=Q.base[Q.front]; // 將隊頭元素的值賦給e
Q.front=(Q.front+1)%MAX_QSIZE; // 移動隊頭指針
return OK;
}
void QueueTraverse(SqQueue Q,void(*visit)(QElemType))
{ // 從隊頭到隊尾依次對隊列Q中每個元素調用函數visit()
int i=Q.front; // i最初指向隊頭元素
while(i!=Q.rear) // i指向隊列Q中的元素
{ visit(Q.base[i]); // 對i所指元素調用函數visit()
i=(i+1)%MAX_QSIZE; // i指向下一個元素
}
printf("\n");
}
void main()
{
int j;
int i=0,m;
int d;
SqQueue Q;
InitQueue(Q); // 初始化隊列Q，失敗則退出
printf("初始化隊列後，隊列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
printf("請輸入整型隊列元素(不超過%d個)，-1為提前結束符：",MAX_QSIZE-1);
do
{ scanf("%d",&d); // 由鍵盤輸入整型隊列元素
if(d==-1) // 輸入的是提前結束符
break; // 退出輸入數據循環
i++; // 計數器+1
EnQueue(Q,d); // 入隊輸入的元素
}while(i<MAX_QSIZE-1); // 隊列元素的個數不超過允許的范圍
printf("隊列長度為%d，",QueueLength(Q));
printf("現在隊列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
printf("連續%d次由隊頭刪除元素，隊尾插入元素：\n",MAX_QSIZE);
for(m=1;m<=MAX_QSIZE;m++)
{ DeQueue(Q,d); // 刪除隊頭元素，其值賦給d
printf("刪除的元素是%d，請輸入待插入的元素：",d);
scanf("%d",&d); // 輸入要入隊的元素給d
EnQueue(Q,d); // 將d入隊
}
m=QueueLength(Q); // m為隊列Q的長度
printf("現在隊列中的元素為");
QueueTraverse(Q,print); // 從隊頭到隊尾依次對隊列Q的每個元素調用函數print()
printf("共向隊尾插入了%d個元素。",i+MAX_QSIZE);
if(m-2>0)
printf("現在由隊頭刪除%d個元素，",m-2);
while(QueueLength(Q)>2)
{ DeQueue(Q,d); // 刪除隊頭元素，其值賦給d
printf("刪除的元素值為%d，",d);
}
j=GetHead(Q,d); // 將隊頭元素賦給d
if(j) // 隊列Q不空
printf("現在隊頭元素為%d\n",d);
ClearQueue(Q); // 清空隊列Q
printf("清空隊列後，隊列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
DestroyQueue(Q); // 銷毀隊列Q
}
④ 數據結構與演算法分析 —— C 語言描述：開放定址法
分離鏈接散列演算法的缺點是需要指針，由於給新單元分配地址需要時間，因此這就導致演算法的速度多少有些緩慢，同時演算法實際上還要求實現另一種數據結構。除使用鏈表解決沖突外，開放定址散列法（open addressing hashing）是另外一種用鏈表解決沖突的方法。在開放定址散列演算法系統中，如果有沖突發生，那麼就要嘗試選擇另外的單元，直到找出空的單元為止。更一般地，單元 相繼試選，其中 ，且 。函數 F 是沖突解決方法，因為所有的數據都要置入表內，所以開放定址散列法所需要的表要比分離鏈接散列用的表大。一般說來，對開放定址散列演算法來說，裝填因子應該低於 。開放定址散列法有三種常用的沖突解決辦法：
在線性探測法中，函數 F 是 的線性函數，典型的情形是 。這相當於逐個探測每個單元（必要時可以繞回）以查找出一個空空單元。即插入一個第一個沖突關鍵字，它將被放入下一個空閑地址，即地址 0，該地址是開放的。之後插入的沖突關鍵字，會對表進行試選，只要表足夠大，總能夠找到一個自由單元，但是如此花費的時間是相當多的。更糟的是，即使表相對較空，這樣占據的單元也會開始形成一些區塊，其結果稱為一次聚集（primary clustering），於是，散列到區塊中的任何關鍵字都需要多次試選單元才能解決沖突，然後該關鍵字被添加到相應的區塊中。
可以證明，使用線性探測的預期探測次數對於插入和不成功的查找來說大約為 ，而對於成功的查找來說則是 。略加思考不難得出，成功查找應該比不成功查找平均花費較少的時間。
如果聚算不算是問題，那麼對應的公式就不難得到。我們假設有一個很大的表，並設每次探測都與前面的探測無關。對於隨機沖突解決辦法而言，這些假設是成立的，並且當 不是非常接近 1 時也是合理的。首先，我們導出在一次不成功查找中探測的期望次數，而這正是直到我們找到一個空單元的探測次數。由於空單元所佔的份額為 ，因此我們預計要探測的單元數是 。一次成功查找的探測次數等於該特定元素插入時所需要的探測次數。當一個元素被插入時，可以看成是一次不成功查找的結果。因此，我們可以使用一次不成功查找的開銷來計算一次成功查找的平均開銷。
需要指出， 在 0 到當前值之間的變化，因此早期的插入操作開銷較少，從而降低平均開銷。我可以通過使用積分計算插入時間平均值的方法來估計平均值，如此得到
這些公式顯然優於線性探測相應的公式，聚集不僅是理論上的問題，而且實際上也發生在具體的實現中。線性探測的預計探測次數與 呈正比，即 越小，插入操作平均次數越少。
平方探測是消除線性探測中一次聚集問題的沖突解決辦法。平方探測就是沖突函數為二次函數的探測方法。流行的選擇是 。
對於線性探測，讓元素幾乎填滿散列表並不是個好主意，因為此時表的性能會降低。對於平方探測情況甚至更糟：一旦表被填滿超過一半，當表的大小不是素數時甚至在表被填滿超過一半之前，就不能保證一次找到一個空單元了。這是因為最多有一半的表可以用作解決沖突的備選位置。
定理：如果使用平方探測，且表的大小是素數，那麼當表至少有一半是空的時候，總能夠插入一個新的元素。
哪怕表有比一半多一個的位置被填滿，那麼插入都有可能失敗（雖然這是非常難以見到的，但是把它記住很重要。）。另外，表的大小是素數也非常重要，如果表的大小不是素數，則備選單元的個數可能會銳減。
在開放定址散列表中，標準的刪除操作不能施行，因為相應的單元可能已經引起過沖突，元素繞過它存在了別處。例如，如果我們刪除一個沖突的中間元素，那麼實際上所有其他的 Find 常式都將不能正確運行。因此，開放定址散列表需要懶惰刪除，雖然在這種情況下並不存在真正意義上的懶惰。
開放定址散列表的類型聲明如下，這里，我們不用鏈表數組，而是使用散列表項單元的數組，與在分離鏈接散列中一樣，這些單元也是動態分配地址的。
初始化開放定址散列表的常式如下，由分配空間（第1～10行）及其後將每個單元的 Info 域設置為 Empty 組成。
使用平方探測散列法的 Find 常式如下。如果分裂鏈接散列法一樣， 將返回 Key 在散列表中的位置。如果 Key 不出現，那麼 Find 將返回最後的單元。該單元就是當需要時，Key 將被插入的地方。此外，因為被標記了 Empty，所以表達 Find 失敗很容易。為了方便起見，我們假設散列表的大小至少為表中元素個數的兩倍，因此平方探測方法總能夠實現。否則，我們就要在第 4 行前測試 。在下面的常式中，標記為刪除的那些元素被認為還在表內，這可能引起一些問題，因為該表可能提前過滿。
第 4～6 行為進行平方探測的快速方法。由平方解決函數的定義可知， ，因此，下一個要探測的單元可以用乘以 2（實際上就是進行一位二進制移位）並減 1 來確定。如果新的定位越過數組，那麼可以通過減去 TableSize 把它拉回到數組范圍內。這比通常的方法要快，因為它避免了看似需要的乘法和除法。注意一條重要的警告：第 3 行的測試順序很重要，切勿改變它。
下面的常式是插入。正如分離鏈接散列方法那樣，若 Key 已經存在，則我們就什麼也不做。其他工作只是簡單的修改。否則，我們就把要插入的元素放在 Find 常式指出的地方。
雖然平方探測排除了一次聚集，但是散列到同一位置上的那些元素將探測相同的備選單元。這叫做二次聚集（secondary clustering）。二次聚集是理論上的一個小缺憾，模擬結果指出，對每次查找，它一般要引起另外的少於一半的探測。
雙散列（double hashing）能夠解決平方探測中的二次聚集問題，不過也需要花費另外的一些乘法和除法形銷。對於雙散列，一種流行的選擇是 。這個公式是說，我們將第二個散列函數應用到 X 並在距離 , 等處探測。 選擇的不好將會是災難性的。
在雙散列時，保證表的帶下為素數是非常重要的。假設我們在插入一個關鍵字的時候，發現它已經引發沖突，就會選擇備選位置，如果表的大小不是素數，那麼備選單元就很有可能提前用完。然後，如果雙散列正確實現，則模擬表明，預期的探測次數幾乎和隨機沖突解決方法的情形相同。這使得雙散列理論上很有吸引力，不過，平方探測不需要使用第二個散列函數，從而在實踐中可能更簡單並且更快。
⑤ C語言數據結構的一個順序表演算法,求分析bug
#include<stdio.h>
typedef int datatype;
const int maxsize=100; //modify
typedef struct{
datatype data[maxsize];
int n;
}sqlist;
int main()
{
//在一個遞增數列中插入一個x後仍是一個遞增數列
sqlist L;
sqlist *p;
p=&L;
int insert(sqlist *L,datatype x,int i);
int locate(sqlist *L,datatype x);
void print(sqlist *L);
datatype x;
int j;
int i;
printf("input the number of the sqlist's length\n");
scanf("%d",&j);
p->n=j;
for(i=0;i<j;i++)//輸入數列
scanf("%d",&p->data[i]);
printf("input the x");
scanf("%d",&x);//插入x
insert(p,x,locate(p,x)) ;
print(p);//輸出
return 0;
}
int insert(sqlist *L,datatype x,int i) {
//將x插入到順序表L的第i個位置上
int j;
if(L->n==maxsize)
{return -1;}
if(i<1 || i>L->n+1)
{return 0;}
for(j=L->n;j>=i;j--)
L->data[j]=L->data[j-1]; //結點後移
L->data[i-1]=x;//插入x，第i個結點的數組下標是i-1
L->n++; //修改表長
return 1; //插入成功
}
int locate(sqlist *L,datatype x) {
int i;
i=1;
while(i<=L->n && L->data[i-1]<=x) i++;
if(i<=L->n) return i; //找到
else return L->n; //未找到
}
void print(sqlist *l){
for(int i=0;i<l->n;i++)
printf("%d ",l->data[i]);
}
⑥ 數據結構與演算法分析 C++
你說的是中序線索二叉樹的插入和刪除
#include<stdio.h>
#include"malloc.h"
#include"windows.h"
#definemaxsize20//規定樹中結點的最大數目
typedefstructnode{//定義數據結構
intltag,rtag;//表示child域指示該結點是否孩子
chardata;//記錄結點的數據
structnode*lchild,*rchild;//記錄左右孩子的指針
}Bithptr;
Bithptr*Q[maxsize];//建隊，保存已輸入的結點的地址
Bithptr*CreatTree(){//建樹函數，返回根指針
charch;
intfront,rear;
Bithptr*T,*s;
T=NULL;
front=1;rear=0;//置空二叉樹
printf("建立一棵二叉樹，請輸入結點信息： ");
printf("請輸入新的結點信息，@為空結點，#為結束標志：");
ch=getchar()();//輸入第一個字元
while(ch!='#')//判斷是否為結束字元
{
s=NULL;
if(ch!='@')//判斷是否為虛結點
{
s=(Bithptr*)malloc(sizeof(Bithptr));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
}
rear++;
Q[rear]=s;//將結點地址加入隊列中
if(rear==1)T=s;//輸入為第一個結點為根結點
else
{
if(s!=NULL&&Q[front]!=NULL)//孩子和雙親結點均不是虛結點
if(rear%2==0)
Q[front]->lchild=s;
elseQ[front]->rchild=s;
if(rear%2==1)front++;
}getchar()();
printf("請輸入新的結點信息，@為空結點，#為結束標志：");
ch=getchar()();
}
returnT;
}
voidInorder(Bithptr*T)//中序遍歷
{
if(T)
{
if(T->ltag!=1)Inorder(T->lchild);
printf("→%c",T->data);
if(T->rtag!=1)Inorder(T->rchild);
}
}
Bithptr*pre=NULL;
voidPreThread(Bithptr*root)//中序線索化演算法，函數實現
{
Bithptr*p;
p=root;
if(p){
PreThread(p->lchild);//線索化左子樹
if(pre&&pre->rtag==1)pre->rchild=p;//前驅結點後繼線索化
if(p->lchild==NULL)
{
p->ltag=1;
p->lchild=pre;
}
if(p->rchild==NULL)//後繼結點前驅線索化
p->rtag=1;
pre=p;
PreThread(p->rchild);
}
}
voidPrintIndex(Bithptr*t)//輸出線索
{
Bithptr*f;
f=t;
if(f)
{
if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)printf("【%c】",f->data);//如果是第一個結點
if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data);//如果此結點有前驅就輸出前驅和此結點
if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data);//如果此結點有前驅也有後繼，就輸出後繼
elseif(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果沒有前驅，就輸出此結點和後繼
printf(" ");
if(f->ltag!=1)PrintIndex(f->lchild);
if(f->rtag!=1)PrintIndex(f->rchild);
}
}
Bithptr*SearchChild(Bithptr*point,charfindnode)//查找孩子結點函數
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if(point->data==findnode)returnpoint;
else
if(point->ltag!=1){point1=SearchChild(point->lchild,findnode);if(point1!=NULL)returnpoint1;}
if(point->rtag!=1){point2=SearchChild(point->rchild,findnode);if(point2!=NULL)returnpoint2;}
returnNULL;
}
else
returnNULL;
}
Bithptr*SearchPre(Bithptr*point,Bithptr*child)//查找父親結點函數
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))returnpoint;//找到則返回
else
if(point->ltag!=1)
{
point1=SearchPre(point->lchild,child);
if(point1!=NULL)
returnpoint1;
}
if(point->rtag!=1)
{
point2=SearchPre(point->rchild,child);
if(point2!=NULL)
returnpoint2;
}
returnNULL;
}
else
returnNULL;
}
voidInsert(Bithptr*root)
{
charch;
charc;
Bithptr*p1,*child,*p2;
printf("請輸入要插入的結點的信息:");
scanf("%c",&c);
scanf("%c",&c);
p1=(Bithptr*)malloc(sizeof(Bithptr));//插入的結點信息
p1->data=c;
p1->lchild=NULL;
p1->rchild=NULL;
p1->rtag=0;
p1->ltag=0;
printf("輸入查找的結點信息:");
scanf("%c",&ch);
scanf("%c",&ch);
child=SearchChild(root,ch);//查孩子結點的地址
if(child==NULL){
printf("沒有找到結點 ");
system("pause");
return;
}
elseprintf("發現結點%c ",child->data);
if(child->ltag==0)//當孩子結點有左孩子的時候
{
p2=child;
child=child->lchild;
while(child->rchild&&child->rtag==0)//找到左子樹下，最右結點
child=child->rchild;
printf("發現結點%c ",child->data);
p1->rchild=child->rchild;//後繼化
p1->rtag=1;
child->rtag=0;
child->rchild=p1;//連接
p1->lchild=child;//前驅化
p1->ltag=1;
}
else//當孩子結點沒有左孩子的時候
{
p1->lchild=child->lchild;//前驅化
child->ltag=0;
p1->ltag=1;
child->lchild=p1;
p1->rchild=child;
p1->rtag=1;
}
printf(" 插入結點操作已經完成，並同時完成了線索化的恢復 ");
}
⑦ C語言編寫數據結構查找演算法
實驗五 查找的實現
一、 實驗目的
1．通過實驗掌握查找的基本概念；
2．掌握順序查找演算法與實現；
3．掌握折半查找演算法與實現。
二、 實驗要求
1． 認真閱讀和掌握本實驗的參考程序。
2． 保存程序的運行結果，並結合程序進行分析。
三、 實驗內容
1、建立一個線性表，對表中數據元素存放的先後次序沒有任何要求。輸入待查數據元素的關鍵字進行查找。為了簡化演算法，數據元素只含一個整型關鍵字欄位，數據元素的其餘數據部分忽略不考慮。建議採用前哨的作用，以提高查找效率。
2、查找表的存儲結構為有序表，輸入待查數據元素的關鍵字利用折半查找方法進行查找。此程序中要求對整型量關鍵字數據的輸入按從小到大排序輸入。
一、順序查找
順序查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請輸入您想輸入的%d個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{
i++;
}
if(i==s->length)
{
printf("該表中沒有您要查找的數據！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
順序查找的運行結果：
二、折半查找
折半查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請由大到小輸入%d個您想輸入的個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("該表中沒有您要查找的數據!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。