- 相關(guān)推薦
c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)實(shí)驗(yàn)報(bào)告;專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程;學(xué)號(hào):____201240703061_____;班級(jí):_________軟件二班________;姓名:________朱海霞__________;指導(dǎo)教師:___劉遵仁_____________;青島大學(xué)信息工程學(xué)院;2013年10月;實(shí)驗(yàn)1;實(shí)驗(yàn)題目：順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除;實(shí)驗(yàn)?zāi)?
數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 實(shí)驗(yàn)報(bào)告
專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程
學(xué)號(hào):____201240703061___________________
班級(jí):_________軟件二班______________
姓名:________朱海霞______________
指導(dǎo)教師:___劉遵仁________________
青島大學(xué)信息工程學(xué)院
2013年10月
實(shí)驗(yàn)1
實(shí)驗(yàn)題目：順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除
實(shí)驗(yàn)?zāi)康模?
了解和掌握線性表的邏輯結(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){
L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem) return -1;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(Sqlist&L,int i,int e){
if(i<1||i>L.length+1) return ERROR;
if(L.length==L.listsize){
int *newbase;
newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase) return -1;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int *p,*q;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(Sqlist &L,int i,int e){
int *p,*q;
if(i<1||i>L.length)return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
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<10;i++)
ListInsert_Sq(L,i,a[i-1]);
for(i=0;i<9;i++)
printf(" %d",L.elem[i]);
printf(" ");//插入9個(gè)數(shù)
ListInsert_Sq(L,3,24);
for(i=0;i<10;i++)
printf(" %d",L.elem[i]);
printf(" ");//插入一個(gè)數(shù)
int e;
ListDelete_Sq(L,2, e);
for(i=0;i<9;i++)
printf(" %d",L.elem[i]);//刪除一個(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)康模?
了解和掌握線性表的邏輯結(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[8]={'A','C','E','F','H','J','Q','U'}; int i,j;
InitList_L(L);
for(i=1,j=0;i<=8,j<8;i++,j++) ListInsert_L(L,i,a[j]);
p=L->next;
while(p!=NULL){
printf("%c ",p->data); p=p->next;
}//插入八個(gè)字符printf(" ;實(shí)驗(yàn)結(jié)果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會(huì)：;單鏈表是通過(guò)掃描指針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ì)：
單鏈表是通過(guò)掃描指針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)康模?
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è)從鍵盤(pán)輸入的字符串，判斷其是否為回文�；匚募凑葱蛳嗤�。如
“abba”是回文，而“abab”不是回文。
實(shí)驗(yàn)主要步驟
(1)數(shù)據(jù)從鍵盤(pán)讀入;
(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(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))
exit(OVERFLOW); // 存儲(chǔ)分配失敗
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int StackEmpty(SqStack S)
{ // 若棧S為空棧，則返回TRUE，否則返回FALSE
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int Push(SqStack &S, int e)
{ // 插入元素e為新的棧頂元素
if(S.top-S.base>=S.stacksize) // 棧滿，追加存儲(chǔ)空間
{
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base)
exit(OVERFLOW); // 存儲(chǔ)分配失敗
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*(S.top)++=e;
return OK;
}
int Pop(SqStack &S,int &e)
{ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERROR if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
int main(){
SqStack s;
int i,e,j,k=1;
char ch[N] = {0},*p,b[N] = {0};
if(InitStack(s)) // 初始化棧成功
{
printf("請(qǐng)輸入表達(dá)式: ");
gets(ch);
p=ch;
while(*p) // 沒(méi)到串尾
Push(s,*p++);
for(i=0;i
if(!StackEmpty(s)) {// 棧不空
Pop(s,e); // 彈出棧頂元素
b[i]=e;
}
}
for(i=0;i
if(ch[i]!=b[i])
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ù)操作設(shè)計(jì)和實(shí)現(xiàn)
實(shí)驗(yàn)?zāi)康模?
掌握二叉樹(shù)的定義、性質(zhì)及存儲(chǔ)方式，各種遍歷算法。
實(shí)驗(yàn)要求：
采用二叉樹(shù)鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹(shù)的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。
實(shí)驗(yàn)主要步驟：
1、分析、理解程序。
2、調(diào)試程序，設(shè)計(jì)一棵二叉樹(shù)，輸入完全二叉樹(shù)的先序序列，用#代表虛結(jié)點(diǎn)(空指針)，如ABD###CE##F##，建立二叉樹(shù)，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。
程序代碼:
實(shí)驗(yàn)結(jié)果：
心得體會(huì)：
實(shí)驗(yàn)5
實(shí)驗(yàn)題目：圖的遍歷操作
實(shí)驗(yàn)?zāi)康模?
掌握有向圖和無(wú)向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu);掌握DFS及BFS對(duì)圖的遍歷操作;了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。
實(shí)驗(yàn)要求：
采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu)，完成有向圖和無(wú)向圖的DFS和BFS操作。
實(shí)驗(yàn)主要步驟：
設(shè)計(jì)一個(gè)有向圖和一個(gè)無(wú)向圖，任選一種存儲(chǔ)結(jié)構(gòu)，完成有向圖和無(wú)向圖的DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)的操作。
1. 鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定義最大頂點(diǎn)數(shù)
typedef struct{
char vexs[MaxVertexNum]; //頂點(diǎn)表
int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，可看作邊表 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[i]=a; //讀入頂點(diǎn)信息，建立頂點(diǎn)表
}
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges[i][j]=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[i][j]=1;;G->edges[j][i]=1;//若為;//=========定義標(biāo)志向量，為全局變量=;typedefenum{FALSE,TRUE}B;Booleanvisited[MaxVertex;//========DFS：深度優(yōu)先遍歷的遞歸算;voidDFSM(MGraph*G,inti);{//以Vi為出發(fā)點(diǎn)
G->edges[i][j]=1;
G->edges[j][i]=1; //若為無(wú)向圖，矩陣為對(duì)稱矩陣;若建立有向圖，去掉該條語(yǔ)句 }
}
//=========定義標(biāo)志向量，為全局變量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========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)開(kāi)始廣度優(yōu)先遍歷
printf(" ");
}
2. 鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)
#include"stdio.h"
#include"stdlib.h"
#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[MaxVertexNum]; //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[i].vertex=a; //讀入頂點(diǎn)信息
G->adjlist[i].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[i].firstedge;
G->adjlist[i].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[j].firstedge;
G->adjlist[j].firstedge=s; //將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部
}
}
//=========定義標(biāo)志向量，為全局變量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========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)康模?
掌握二分查找法的工作原理及應(yīng)用過(guò)程，利用其工作原理完成實(shí)驗(yàn)題目中的內(nèi)容。。
實(shí)驗(yàn)要求：
編寫(xiě)程序構(gòu)造一個(gè)有序表L，從鍵盤(pán)接收一個(gè)關(guān)鍵字key，用二分查找法在L中查找key，若找到則提示查找成功并輸出key所在的位置，否則提示沒(méi)有找到信息。。
實(shí)驗(yàn)主要步驟：
1. 建立的初始查找表可以是無(wú)序的，如測(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)康模?
掌握各種排序方法的基本思想、排序過(guò)程、算法實(shí)現(xiàn)，能進(jìn)行時(shí)間和空間性能的分析，根據(jù)實(shí)際問(wèn)題的特點(diǎn)和要求選擇合適的排序方法。
實(shí)驗(yàn)要求：
實(shí)現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運(yùn)行速度。
實(shí)驗(yàn)主要步驟：
程序代碼
實(shí)驗(yàn)結(jié)果：
心得體會(huì)：
【c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告】相關(guān)文章：
C數(shù)據(jù)結(jié)構(gòu)面試題 以及答案07-13
C語(yǔ)言實(shí)驗(yàn)報(bào)告《綜合實(shí)驗(yàn)》07-03
上海交通大學(xué)軟件工程專業(yè)C、C++、數(shù)據(jù)結(jié)構(gòu)、電路系統(tǒng)以及離散結(jié)構(gòu)的課件07-09
華為C/C++筆試題07-11
經(jīng)典C/C++面試題07-11
騰訊公司招聘c/c++筆試題07-13
華為C/C++筆試題系列二07-11
C/C++面試題目集錦07-13