第一篇：c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
數(shù)據(jù)結(jié)構(gòu)(C語言版)實(shí)驗(yàn)報(bào)告;專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程;學(xué)號(hào):____XX40703061_____;班級(jí):_________軟件二班________;姓名:________朱海霞__________;指導(dǎo)教師:___劉遵仁_____________;青島大學(xué)信息工程學(xué)院;XX年10月;實(shí)驗(yàn)1;實(shí)驗(yàn)題目：順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除;實(shí)驗(yàn)?zāi)?/p>
數(shù)據(jù)結(jié)構(gòu)(C語言版)實(shí)驗(yàn)報(bào)告
專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程
學(xué)號(hào):____XX40703061___________________
班級(jí):_________軟件二班______________
姓名:________朱海霞______________
指導(dǎo)教師:___劉遵仁________________
青島大學(xué)信息工程學(xué)院
XX年10月
實(shí)驗(yàn)1
實(shí)驗(yàn)題目：順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除
實(shí)驗(yàn)?zāi)康模?/p>
了解和掌握線性表的邏輯結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)，掌握線性表的基本算法及相關(guān)的時(shí)間性能分析。
實(shí)驗(yàn)要求：
建立一個(gè)數(shù)據(jù)域定義為整數(shù)類型的線性表，在表中允許有重復(fù)的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù)，先找到相應(yīng)的存儲(chǔ)單元，后刪除之。
實(shí)驗(yàn)主要步驟：
1、分析、理解給出的示例程序。
2、調(diào)試程序，并設(shè)計(jì)輸入一組數(shù)據(jù)(3，-5，6，8，2，-5，4，7，-9)，測(cè)試程序的如下功能：根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲(chǔ)單元并刪除，顯示表中所有的數(shù)據(jù)。
程序代碼:
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW-2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
int* elem;
int length;
int listsize;
}Sqlist;
int InitList_Sq(Sqlist &L){
=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!)return-1;
=0;
=LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(Sqlist&L,int i,int e){
if(i+1)return ERROR;
if(==){
int *newbase;
newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int));
if(!newbase)return-1;
=newbase;
+=LISTINCREMENT;
}
int *p,*q;
q=&();
for(p=&();p>=q;--p)
*(p+1)=*p;
*q=e;
++;
return OK;
}
int ListDelete_Sq(Sqlist &L,int i,int e){
int *p,*q;
if(i)return ERROR;
p=&();
e=*p;
q=+;
for(++p;p *(p-1)=*p;
--;
return OK;
}
int main(){
Sqlist L;
InitList_Sq(L);//初始化
int i,a={3,-5,6,8,2,-5,4,7,-9};
for(i=1;i ListInsert_Sq(L,i,a);
for(i=0;i printf(“ %d”,);
printf(“ ”);//插入9個(gè)數(shù)
ListInsert_Sq(L,3,24);
for(i=0;i printf(“ %d”,);
printf(“ ”);//插入一個(gè)數(shù)
int e;
ListDelete_Sq(L,2, e);
for(i=0;i printf(“ %d”,);//刪除一個(gè)數(shù)
printf(“ ”);
return 0;
}
實(shí)驗(yàn)結(jié)果：
3，-5,6,8,2，-5,4,7，-9
3，-5,24,6,8,2，-5,4,7，-9
3,24,6,8,2，-5,4,7，-9
心得體會(huì)：
順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時(shí)間是一個(gè)常數(shù)，速度快;結(jié)構(gòu)簡(jiǎn)單，邏輯上相鄰的元素在物理上也相鄰;不使用指針，節(jié)省存儲(chǔ)空間;但是插入和刪除元素需要移動(dòng)大量元素，消耗大量時(shí)間;需要一個(gè)連續(xù)的存儲(chǔ)空間;插入元素可能發(fā)生溢出;自由區(qū)中的存儲(chǔ)空間不能被其他數(shù)據(jù)共享 實(shí)驗(yàn)2
實(shí)驗(yàn)題目：?jiǎn)捂湵淼牟迦牒蛣h除
實(shí)驗(yàn)?zāi)康模?/p>
了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時(shí)間性能分析。
實(shí)驗(yàn)要求：
建立一個(gè)數(shù)據(jù)域定義為字符類型的單鏈表，在鏈表中不允許有重復(fù)的字符;根據(jù)輸入的字符，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。
實(shí)驗(yàn)主要步驟：
3、分析、理解給出的示例程序。
4、調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)(如：A，C，E，F(xiàn)，H，J，Q，M)，測(cè)試程序的如下功能：不允許重復(fù)字符的插入;根據(jù)輸入的字符，找到相應(yīng)的結(jié)點(diǎn)并刪除。
5、修改程序：
(1)增加插入結(jié)點(diǎn)的功能。
(2)建立鏈表的方法有“前插”、“后插”法。
程序代碼:
#include
#include
#define NULL 0
#define OK 1
#define ERROR 0
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
int InitList_L(LinkList &L){
L=(LinkList)malloc(sizeof(LNode));L->next=NULL;
return OK;
} int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s;
int j;
p=L;j=0;
while(p&&j
p=p->next;++j;
}
if(!p||j>i-1)
return ERROR;
s=(LinkList)malloc(sizeof(LNode));s->data=e;
s->next=p->next;
p->next=s;
return OK;
} int
ListDelete_L(LinkList&L,int
i,int &e){ LinkList p,q;
int j;
p=L;j=0;
while(p->next&&j
p=p->next;++j;
}
if(!(p->next)||j
return ERROR;
q=p->next;p->next=q->next;e=q->data;free(q);
return OK;
}
int main(){
LinkList L,p;
char a={'A','C','E','F','H','J','Q','U'};int i,j;
InitList_L(L);
for(i=1,j=0;i p=L->next;
while(p!=NULL){
printf(“%c ”,p->data);p=p->next;}//插入八個(gè)字符
printf(“;實(shí)驗(yàn)結(jié)果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會(huì)：;單鏈表是通過掃描指針P進(jìn)行單鏈表的操作;頭指針唯;實(shí)驗(yàn)3;實(shí)驗(yàn)題目：棧操作設(shè)計(jì)和實(shí)現(xiàn);實(shí)驗(yàn)?zāi)康模?
1、掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí);
2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則;
3、掌握棧的基本運(yùn)算，如：入棧與出棧
}
}//插入八個(gè)字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B');
p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一個(gè)字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);return 0;
實(shí)驗(yàn)結(jié)果：
A C E F H J Q U
A B C E F H J Q U
A B E F H J Q U
心得體會(huì)：
單鏈表是通過掃描指針P進(jìn)行單鏈表的操作;頭指針唯一標(biāo)識(shí)點(diǎn)鏈表的存在;插入和刪除元素快捷，方便。
實(shí)驗(yàn)3
實(shí)驗(yàn)題目：棧操作設(shè)計(jì)和實(shí)現(xiàn)
實(shí)驗(yàn)?zāi)康模?/p>
1、掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。
2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。
3、掌握棧的基本運(yùn)算，如：入棧與出棧等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。
實(shí)驗(yàn)要求：
回文判斷：對(duì)于一個(gè)從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如
“abba”是回文，而“abab”不是回文。
實(shí)驗(yàn)主要步驟
(1)數(shù)據(jù)從鍵盤讀入;
(2)輸出要判斷的字符串;
(3)利用棧的基本操作對(duì)給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。
程序代碼:
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW-2
#define N 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
int *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL int *top;// 棧頂指針
int stacksize;// 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位
} SqStack;
int InitStack(SqStack &S)
{ // 構(gòu)造一個(gè)空棧S
if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))
exit(OVERFLOW);// 存儲(chǔ)分配失敗
=;
=STACK_INIT_SIZE;
return OK;
}
int StackEmpty(SqStack S)
{ // 若棧S為空棧，則返回TRUE，否則返回FALSE
if(==)
return TRUE;
else
return FALSE;
}
int Push(SqStack &S, int e)
{ // 插入元素e為新的棧頂元素
if(>=)// 棧滿，追加存儲(chǔ)空間
{
=(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!)
exit(OVERFLOW);// 存儲(chǔ)分配失敗
=+;
+=STACKINCREMENT;
}
*()++=e;
return OK;
}
int Pop(SqStack &S,int &e)
{ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERROR if(==)
return ERROR;
e=*--;
return OK;
}
int main(){
SqStack s;
int i,e,j,k=1;
char ch = {0},*p,b = {0};
if(InitStack(s))// 初始化棧成功
{
printf(”請(qǐng)輸入表達(dá)式: “);
gets(ch);
p=ch;
while(*p)// 沒到串尾
Push(s,*p++);
for(i=0;i
if(!StackEmpty(s)){// 棧不空
Pop(s,e);// 彈出棧頂元素
b=e;
}
}
for(i=0;i
if(ch!=b)
k=0;
}
if(k==0)
printf(”NO!“);
else
printf(”輸出:“)
printf(”YES!“);
}
return 0;
}
實(shí)驗(yàn)結(jié)果：
請(qǐng)輸入表達(dá)式：
abcba
輸出：YES!
心得體會(huì)：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進(jìn)后出的性質(zhì)，這個(gè)固有性質(zhì)使棧成為程序設(shè)計(jì)中的有用工具。
實(shí)驗(yàn)4
實(shí)驗(yàn)題目：二叉樹操作設(shè)計(jì)和實(shí)現(xiàn)
實(shí)驗(yàn)?zāi)康模?/p>
掌握二叉樹的定義、性質(zhì)及存儲(chǔ)方式，各種遍歷算法。
實(shí)驗(yàn)要求：
采用二叉樹鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。
實(shí)驗(yàn)主要步驟：
1、分析、理解程序。
2、調(diào)試程序，設(shè)計(jì)一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)(空指針)，如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。
程序代碼:
實(shí)驗(yàn)結(jié)果：
心得體會(huì)：
實(shí)驗(yàn)5
實(shí)驗(yàn)題目：圖的遍歷操作
實(shí)驗(yàn)?zāi)康模?/p>
掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu);掌握DFS及BFS對(duì)圖的遍歷操作;了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。
實(shí)驗(yàn)要求：
采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。
實(shí)驗(yàn)主要步驟：
設(shè)計(jì)一個(gè)有向圖和一個(gè)無向圖，任選一種存儲(chǔ)結(jié)構(gòu)，完成有向圖和無向圖的DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)的操作。
1.鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)
#include”“
#include”“
#define MaxVertexNum 100 //定義最大頂點(diǎn)數(shù)
typedef struct{
char vexs;//頂點(diǎn)表
int edges;//鄰接矩陣，可看作邊表 int n,e;//圖中的頂點(diǎn)數(shù)n和邊數(shù)e
}MGraph;//用鄰接矩陣表示的圖的類型
//=========建立鄰接矩陣=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf(”Input VertexNum(n)and EdgesNum(e): “);
scanf(”%d,%d“,&G->n,&G->e);//輸入頂點(diǎn)數(shù)和邊數(shù)
scanf(”%c“,&a);
printf(”Input Vertex string:“);
for(i=0;in;i++)
{
scanf(”%c“,&a);
G->vexs=a;//讀入頂點(diǎn)信息，建立頂點(diǎn)表
}
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges=0;//初始化鄰接矩陣
printf(”Input edges,Creat Adjacency Matrix “);
for(k=0;ke;k++){ //讀入e條邊，建立鄰接矩陣
scanf(”%d%d“,&i,&j);//輸入邊(Vi，Vj)的頂點(diǎn)序號(hào)
G->edges=1;;G->edges=1;//若為;//=========定義標(biāo)志向
量，為
全
局
變
量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1;
G->edges=1;//若為無向圖，矩陣為對(duì)稱矩陣;若建立有向圖，去掉該條語句 }
}
//=========定義標(biāo)志向量，為全局變量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited;
//========DFS：深度優(yōu)先遍歷的遞歸算法======
void DFSM(MGraph *G,int i)
{ //以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣
給出你的編碼
//===========BFS：廣度優(yōu)先遍歷=======
void BFS(MGraph *G,int k)
{ //以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索
給出你的編碼
//==========主程序main =====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph));//為圖G請(qǐng)內(nèi)存空間
CreatMGraph(G);//建立鄰接矩陣
printf(”Print Graph DFS: “);
DFS(G);//深度優(yōu)先遍歷
printf(” “);
printf(”Print Graph BFS: “);
BFS(G,3);//以序號(hào)為3的頂點(diǎn)開始廣度優(yōu)先遍歷
printf(” “);
}
2.鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)
#include”“
#include”“
#define MaxVertexNum 50 //定義最大頂點(diǎn)數(shù)
typedef struct node{ //邊表結(jié)點(diǎn)
int adjvex;//鄰接點(diǎn)域
struct node *next;//鏈域
申
}EdgeNode;
typedef struct vnode{ //頂點(diǎn)表結(jié)點(diǎn)
char vertex;//頂點(diǎn)域
EdgeNode *firstedge;//邊表頭指針
}VertexNode;
typedef VertexNode AdjList;//AdjList是鄰接表類型 typedef struct {
AdjList adjlist;//鄰接表
int n,e;//圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
} ALGraph;//圖類型
//=========建立圖的鄰接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s;//定義邊表結(jié)點(diǎn)
printf(”Input VertexNum(n)and EdgesNum(e): “);
scanf(”%d,%d“,&G->n,&G->e);//讀入頂點(diǎn)數(shù)和邊數(shù)
scanf(”%c“,&a);
printf(”Input Vertex string:“);
for(i=0;in;i++)//建立邊表
{
scanf(”%c“,&a);
G->adjlist.vertex=a;//讀入頂點(diǎn)信息
G->adjlist.firstedge=NULL;//邊表置為空表
}
printf(”Input edges,Creat Adjacency List “);
for(k=0;ke;k++){ //建立邊表
scanf(”%d%d“,&i,&j);//讀入邊(Vi，Vj)的頂點(diǎn)對(duì)序號(hào)
s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成邊表結(jié)點(diǎn)
s->adjvex=j;//鄰接點(diǎn)序號(hào)為j
s->next=G->adjlist.firstedge;
G->adjlist.firstedge=s;//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i;//鄰接點(diǎn)序號(hào)為i
s->next=G->adjlist.firstedge;
G->adjlist.firstedge=s;//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部
}
}
//=========定義標(biāo)志向量，為全局變量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited;
//========DFS：深度優(yōu)先遍歷的遞歸算法======
void DFSM(ALGraph *G,int i)
{ //以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索
給出你的編碼
//==========BFS：廣度優(yōu)先遍歷=========
void BFS(ALGraph *G,int k)
{ //以Vk為源點(diǎn)對(duì)用鄰接鏈表表示的圖G進(jìn)行廣度優(yōu)先搜索
給出你的編碼
//==========主函數(shù)===========
void main()
{
int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf(”Print Graph DFS: “);
DFS(G);
printf(” “);
printf(”Print Graph BFS: “);
BFS(G,3);
printf(” ");
}
實(shí)驗(yàn)結(jié)果：
1.鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)
2.鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)
心得體會(huì)：
實(shí)驗(yàn)6
實(shí)驗(yàn)題目：二分查找算法的實(shí)現(xiàn)
實(shí)驗(yàn)?zāi)康模?/p>
掌握二分查找法的工作原理及應(yīng)用過程，利用其工作原理完成實(shí)驗(yàn)題目中的內(nèi)容。
實(shí)驗(yàn)要求：
編寫程序構(gòu)造一個(gè)有序表L，從鍵盤接收一個(gè)關(guān)鍵字key，用二分查找法在L中查找key，若找到則提示查找成功并輸出key所在的位置，否則提示沒有找到信息。
實(shí)驗(yàn)主要步驟：
1.建立的初始查找表可以是無序的，如測(cè)試的數(shù)據(jù)為{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。
2.給出算法的遞歸和非遞歸代碼;
3.如何利用二分查找算法在一個(gè)有序表中插入一個(gè)元素x，并保持表的有序性?
程序代碼
實(shí)驗(yàn)結(jié)果：
心得體會(huì)：
實(shí)驗(yàn)7
實(shí)驗(yàn)題目：排序
實(shí)驗(yàn)?zāi)康模?/p>
掌握各種排序方法的基本思想、排序過程、算法實(shí)現(xiàn)，能進(jìn)行時(shí)間和空間性能的分析，根據(jù)實(shí)際問題的特點(diǎn)和要求選擇合適的排序方法。
實(shí)驗(yàn)要求：
實(shí)現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運(yùn)行速度。
實(shí)驗(yàn)主要步驟：
程序代碼
實(shí)驗(yàn)結(jié)果：
心得體會(huì)：
第二篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
注意：實(shí)驗(yàn)結(jié)束后提交一份實(shí)驗(yàn)報(bào)告電子文檔
電子文檔命名為“學(xué)號(hào)+姓名”，如：E01214058宋思怡
《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告
（一）學(xué)號(hào)：姓名：專業(yè)年級(jí)：
實(shí)驗(yàn)名稱：線性表
實(shí)驗(yàn)日期：2014年4月14日
實(shí)驗(yàn)?zāi)康模?/p>
1、熟悉線性表的定義及其順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；
2、熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法；
3、熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表基本操作的方法；
4、掌握用 C/C++語言調(diào)試程序的基本方法。
實(shí)驗(yàn)內(nèi)容：
一、編寫程序?qū)崿F(xiàn)順序表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：
（1）初始化順序表L；
（2）依次在L尾部插入元素-1,21,13,24,8；
（3）輸出順序表L；
（4）輸出順序表L長(zhǎng)度；
（5）判斷順序表L是否為空；
（6）輸出順序表L的第3個(gè)元素；
（7）輸出元素24的位置；
（8）在L的第4個(gè)元素前插入元素0；
（9）輸出順序表L；
（10）刪除L的第5個(gè)元素；
（11）輸出順序表L。
源代碼
調(diào)試分析（給出運(yùn)行結(jié)果界面）
二、編寫程序?qū)崿F(xiàn)單鏈表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：
????
????
小結(jié)或討論:
（1）實(shí)驗(yàn)中遇到的問題和解決方法
（2）實(shí)驗(yàn)中沒有解決的問題
（3）體會(huì)和提高
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
南京信息工程大學(xué)實(shí)驗(yàn)（實(shí)習(xí)）報(bào)告
實(shí)驗(yàn)（實(shí)習(xí)）名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)（實(shí)習(xí)）日期 2011-11-2得分指導(dǎo)教師周素萍
系公共管理系專業(yè)信息管理與信息系統(tǒng)年級(jí)10級(jí)班次1姓名常玲學(xué)號(hào)2010230700
3實(shí)驗(yàn)一順序表的基本操作及C語言實(shí)現(xiàn)
【實(shí)驗(yàn)?zāi)康摹?/p>
1、順序表的基本操作及 C 語言實(shí)現(xiàn)
【實(shí)驗(yàn)要求】
1、用 C 語言建立自己的線性表結(jié)構(gòu)的程序庫，實(shí)現(xiàn)順序表的基本操作。
2、對(duì)線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應(yīng)的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個(gè)集合的并的結(jié)果存儲(chǔ)在一個(gè)新的線性表集合中，并輸出。
【實(shí)驗(yàn)內(nèi)容】
1、根據(jù)教材定義的順序表機(jī)構(gòu)，用 C 語言實(shí)現(xiàn)順序表結(jié)構(gòu)的創(chuàng)建、插入、刪除、查找等操作；
2、利用上述順序表操作實(shí)現(xiàn)如下程序：建立兩個(gè)順序表表示的集合（集合中無重
復(fù)的元素），并求這樣的兩個(gè)集合的并。
【實(shí)驗(yàn)結(jié)果】
[實(shí)驗(yàn)數(shù)據(jù)、結(jié)果、遇到的問題及解決]
一． Status InsertOrderList(SqList &va,ElemType x)
{
}
二． Status DeleteK(SqList &a,int i,int k)
{//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的編號(hào)從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 將合并逆置后的結(jié)果放在C表中，并刪除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅(qū)指針 // 保存pb的前驅(qū)指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲(chǔ)在數(shù)組中，元素之間的關(guān)系直接通過相鄰元素的位置來表達(dá)。 優(yōu)點(diǎn)：簡(jiǎn)單，數(shù)據(jù)元素的提取速度快； 缺點(diǎn)：（1）靜態(tài)存儲(chǔ)，無法預(yù)知問題規(guī)模的大小，可能空間不足，或浪費(fèi)存儲(chǔ)空間；（2）插入元素和刪除元素時(shí)間復(fù)雜度高——O（n） 求兩個(gè)集合的并集 該算法是求兩個(gè)集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復(fù)制到s中，然后把s2中的每個(gè)元素依次插入到集合s中，當(dāng)然重復(fù)的元素不應(yīng)該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對(duì)應(yīng)的實(shí)際參數(shù)集合中得到并集。 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 一． 題目要求 1）編程實(shí)現(xiàn)二叉排序樹，包括生成、插入，刪除； 2）對(duì)二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷； 3）每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信息(至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng)),對(duì)比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對(duì)于前三個(gè)題目要求，我們用一個(gè)程序?qū)崿F(xiàn)代碼如下 #include typedefintElemType; //數(shù)據(jù)類型 typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//創(chuàng)建二叉樹函數(shù) BiTreebst=NULL;inti=0;while(i //數(shù)據(jù)域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子樹為空重接它的左子樹 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子樹空則重新接它的右子樹 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被刪除結(jié)點(diǎn)的前驅(qū) if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數(shù)，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函數(shù) printf(“ ---------------------二叉排序樹的實(shí)現(xiàn)-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節(jié)點(diǎn)個(gè)數(shù):”);scanf(“%d”,&num);printf(“依次輸入這些整數(shù)（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創(chuàng)建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示輸入操作符************************:”);printf(“n”);printf(“ 1:插入節(jié)點(diǎn) 2:刪除節(jié)點(diǎn) 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節(jié)點(diǎn):”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“樹狀圖為:n”); printtree(bst,layer); break; case 2: } printf(“輸入要?jiǎng)h除的節(jié)點(diǎn)”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst); printf(“后序遍歷:n”); PostOrderNoRec(bst); printf(“樹狀圖為:n”); printtree(bst,layer); break;case 5: printf(“程序執(zhí)行完畢!”); return 0;} goto loop;} return 0;對(duì)于第四小問，要儲(chǔ)存學(xué)生的三個(gè)信息，需要把上面程序修改一下，二叉樹結(jié)構(gòu)變?yōu)?typedefintElemType; //數(shù)據(jù)類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數(shù)據(jù)域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數(shù)不是key,而是另外三個(gè) intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含參函數(shù)也類似 即可完成50個(gè)信息存儲(chǔ) 用數(shù)組存儲(chǔ)50個(gè)信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學(xué)生管理系統(tǒng)”< cout<<“該學(xué)號(hào)信息已經(jīng)存在，添加失敗”< break;} cout<<“重新輸入添加的學(xué)號(hào)”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“謝謝使用”< 二叉排序樹儲(chǔ)存數(shù)據(jù)界面（儲(chǔ)存學(xué)生信息略） 創(chuàng)建二叉樹： 插入節(jié)點(diǎn)： 刪除節(jié)點(diǎn)： 非遞歸遍歷： 退出： 數(shù)組儲(chǔ)存學(xué)生信息界面 分析查找效率： 因?yàn)槎鏄洳檎乙獎(jiǎng)?chuàng)建二叉樹，而數(shù)組查找只創(chuàng)建一個(gè)數(shù)組，二叉樹的創(chuàng)建時(shí)間比較長(zhǎng)，所以對(duì)于數(shù)據(jù)量較少的情況下數(shù)組的查找效率比較高。但當(dāng)數(shù)據(jù)量增加時(shí)，二叉樹的查找優(yōu)勢(shì)就顯現(xiàn)出來。所以數(shù)據(jù)量越大的時(shí)候，二叉樹的查找效率越高。 四． 總結(jié)與改進(jìn) 這個(gè)實(shí)驗(yàn)工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進(jìn)。 一開始打算用棧實(shí)現(xiàn)非遞歸，但是根據(jù)書里面的偽代碼發(fā)現(xiàn)部分是在C++編譯器里運(yùn)行不了的（即使補(bǔ)充了頭文件和數(shù)據(jù)的定義），所以之后參考了網(wǎng)上的數(shù)組非遞歸，發(fā)現(xiàn)其功能和棧相似。 遞歸遍歷的實(shí)現(xiàn)比非遞歸的遍歷真的簡(jiǎn)單很多。 開始時(shí)只看到前三問，所以沒有寫到儲(chǔ)存學(xué)生數(shù)據(jù)的代碼，里面還可以用clock（）函數(shù)加一個(gè)計(jì)算查找所要數(shù)據(jù)時(shí)間的代碼，讓二叉樹查找與數(shù)組查找到效率比較更加直觀。 實(shí)驗(yàn)報(bào)告4 排序 一、實(shí)驗(yàn)?zāi)康?/p> 1、掌握常用的排序方法，并掌握用高級(jí)語言實(shí)現(xiàn)排序算法的方法。 2、深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。 3、了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。 二、實(shí)驗(yàn)要求及內(nèi)容 要求編寫的程序所能實(shí)現(xiàn)的功能包括： 1、從鍵盤輸入要排序的一組元素的總個(gè)數(shù) 2、從鍵盤依次輸入要排序的元素值 3、對(duì)輸入的元素進(jìn)行快速排序 4、對(duì)輸入的元素進(jìn)行折半插入排序 三、實(shí)驗(yàn)代碼及相關(guān)注釋 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的結(jié)構(gòu)體 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的結(jié)構(gòu)體 int Partition(SqList &L, int low, int high) //1 尋找基準(zhǔn) { L.r[0]=L.r[low];//子表的第一個(gè)記錄作基準(zhǔn)對(duì)象 int pivotkey = L.r[low].key;//基準(zhǔn)對(duì)象關(guān)鍵字 while(low while(low L.r[low] = L.r[high];//小于基準(zhǔn)對(duì)象的移到區(qū)間的左側(cè) while(low L.r[high] = L.r[low];//大于基準(zhǔn)對(duì)象的移到區(qū)間的右側(cè) } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列l(wèi)ow-high中遞歸地進(jìn)行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //尋找基準(zhǔn) QuickSort(L, low, pivotloc-1);//對(duì)左序列同樣遞歸處理 QuickSort(L, pivotloc+1, high);//對(duì)右序列同樣遞歸處理 } } Sequenlist *Sqlset() //2 輸入要折半插入排序的一組元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“請(qǐng)輸入要排序的所有元素的總個(gè)數(shù)：”; cin>>i; cout< cout<<“請(qǐng)依次輸入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入點(diǎn)在前半?yún)^(qū) else low=mid+1;//插入點(diǎn)在后半?yún)^(qū) } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“請(qǐng)選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“請(qǐng)輸入要排序的所有元素的總個(gè)數(shù)：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后為：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函數(shù)功能說明 1、Sequenlist *Sqlset() 輸入要折半插入排序的一組元素 2、int Partition(SqList &L, int low, int high) 尋找快速排序的基準(zhǔn) 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序運(yùn)行結(jié)果 下圖僅為分別排序一次，可多次排序，后面有相關(guān)截圖： 六、實(shí)驗(yàn)中遇到的問題、解決及體會(huì) 1、起初編寫快速排序的程序時(shí)，我是完全按照老師PPT上的算法敲上去的，然后建立了一個(gè)SqList的結(jié)構(gòu)體，調(diào)試運(yùn)行時(shí)出現(xiàn)錯(cuò)誤，仔細(xì)查看才意識(shí)到Partition函數(shù)中L中應(yīng)該包含元素key，而我建立結(jié)構(gòu)體時(shí)沒有注意，然后我將key這個(gè)元素補(bǔ)充進(jìn)去，繼續(xù)調(diào)試，又出現(xiàn)錯(cuò)誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經(jīng)寫了函數(shù)定義，為什么會(huì)這樣，當(dāng)我又回過頭來閱讀程序時(shí)，我發(fā)現(xiàn)QuickSort函數(shù)中調(diào)用了Partition函數(shù)，但是我的Partition函數(shù)的定義在QuickSort函數(shù)的后面，于是我將Partition函數(shù)放到了QuickSort函數(shù)的前面，再次調(diào)試運(yùn)行，就可以正常運(yùn)行，得出結(jié)果了。這讓我懂得，編程一定要認(rèn)真仔細(xì)，不可大意馬虎，否則又會(huì)花很多時(shí)間回過頭來檢查修改程序，得不償失。 運(yùn)行程序錯(cuò)誤截圖： 2、本來我是編寫了兩個(gè)程序，分別實(shí)現(xiàn)快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實(shí)現(xiàn)不同的功能，從鍵盤輸入功能選項(xiàng)m，if（m==1），可以進(jìn)行快速排序，if（m==2），可以進(jìn)行折半插入排序，于是我繼續(xù)思考，我是否可以在一次運(yùn)行程序中，多次對(duì)含有不同元素的序列進(jìn)行排序，于是我用了goto語句，每次排序一次后，自動(dòng)循環(huán)到選擇語句，當(dāng)不需要在排序的時(shí)候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實(shí)用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實(shí)現(xiàn)所需功能的前提下，多想問題，看是否能使程序更加實(shí)用簡(jiǎn)便。 修改程序前兩個(gè)運(yùn)行結(jié)果截圖 （兩個(gè)程序，調(diào)試運(yùn)行兩次，每次只能進(jìn)行一次排序） 1、快速排序程序運(yùn)行結(jié)果截圖： 2、折半插入排序程序結(jié)果截圖： 程序重要模塊修改截圖： 修改程序后運(yùn)行截圖： （一個(gè)程序，調(diào)試運(yùn)行一次，可多次進(jìn)行不同序列的不同排序）第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
點(diǎn)擊咨詢 