範文齋

請輸入關鍵字詞

熱門搜索排行

位置：首頁 > 行政範文 > 報告

c數據結構實驗報告

報告1.02W

數據結構(C語言版)實驗報告;專業：計算機科學與技術、軟件工程;學號:____201240703061_____;班級:_________軟件二班________;姓名:________朱海霞__________;指導教師:___劉遵仁_____________;青島大學信息工程學院;2013年10月;實驗1;實驗題目：順序存儲結構線性表的插入和刪除;實驗目

c數據結構實驗報告

數據結構(C語言版) 實驗報告

專業：計算機科學與技術、軟件工程

學號:____201240703061___________________

班級:_________軟件二班______________

姓名:________朱海霞______________

指導教師:___劉遵仁________________

青島大學信息工程學院

2013年10月

實驗1

實驗題目：順序存儲結構線性表的插入和刪除

實驗目的：

瞭解和掌握線性表的邏輯結構和順序存儲結構，掌握線性表的基本算法及相關的時間性能分析。

實驗要求：

建立一個數據域定義爲整數類型的線性表，在表中允許有重複的數據;根據輸入的數據，先找到相應的存儲單元，後刪除之。

實驗主要步驟：

1、分析、理解給出的示例程序。

2、調試程序，並設計輸入一組數據(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：根據輸入的數據，找到相應的存儲單元並刪除，顯示錶中所有的數據。

程序代碼:

#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;

th=0;

size=LIST_INIT_SIZE;

return OK;

}

int ListInsert_Sq(Sqlist&L,int i,int e){

if(i<1||i>th+1) return ERROR;

if(th==size){

int *newbase;

newbase=(int*)realloc(,(size+LISTINCREMENT)*sizeof(int));

if(!newbase) return -1;

=newbase;

size+=LISTINCREMENT;

}

int *p,*q;

q=&([i-1]);

for(p=&([th-1]);p>=q;--p)

*(p+1)=*p;

*q=e;

++th;

return OK;

}

int ListDelete_Sq(Sqlist &L,int i,int e){

int *p,*q;

if(i<1||i>th)return ERROR;

p=&([i-1]);

e=*p;

q=+th-1;

for(++p;p<=q;++p)

*(p-1)=*p;

th;

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",[i]);

printf(" ");//插入9個數

ListInsert_Sq(L,3,24);

for(i=0;i<10;i++)

printf(" %d",[i]);

printf(" ");//插入一個數

int e;

ListDelete_Sq(L,2, e);

for(i=0;i<9;i++)

printf(" %d",[i]);//刪除一個數

printf(" ");

return 0;

}

實驗結果：

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

心得體會：

順序存儲結構是一種隨機存取結構，存取任何元素的時間是一個常數，速度快;結構簡單，邏輯上相鄰的元素在物理上也相鄰;不使用指針，節省存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續的存儲空間;插入元素可能發生溢出;自由區中的存儲空間不能被其他數據共享 實驗2

實驗題目：單鏈表的插入和刪除

實驗目的：

瞭解和掌握線性表的邏輯結構和鏈式存儲結構，掌握單鏈表的基本算法及相關的時間性能分析。

實驗要求：

建立一個數據域定義爲字符類型的單鏈表，在鏈表中不允許有重複的字符;根據輸入的字符，先找到相應的結點，後刪除之。

實驗主要步驟：

3、分析、理解給出的'示例程序。

4、調試程序，並設計輸入數據(如：A，C，E，F，H，J，Q，M)，測試程序的如下功能：不允許重複字符的插入;根據輸入的字符，找到相應的結點並刪除。

5、修改程序：

(1) 增加插入結點的功能。

(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;

}//插入八個字符printf(" ;實驗結果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會：;單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯;實驗3;實驗題目：棧操作設計和實現;實驗目的：;1、掌握棧的順序存儲結構和鏈式存儲結構，以便在實;2、掌握棧的特點，即後進先出和先進先出的原則;3、掌握棧的基本運算，如：入棧與出棧

}

}//插入八個字符 printf(" "); i=2; int e; ListInsert_L(L,i,'B'); p=L->next; while(p!=NULL){ printf("%c ",p->data); p=p->next; }//插入一個字符 printf(" "); i=3; ListDelete_L(L,i,e); p=L->next; while(p!=NULL){ printf("%c ",p->data); p=p->next; } printf(" "); return 0;

實驗結果：

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

心得體會：

單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯一標識點鏈表的存在;插入和刪除元素快捷，方便。

實驗3

實驗題目：棧操作設計和實現

實驗目的：

1、掌握棧的順序存儲結構和鏈式存儲結構，以便在實際中靈活應用。

2、掌握棧的特點，即後進先出和先進先出的原則。

3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結構和鏈式存儲結構上的實現。

實驗要求：

迴文判斷：對於一個從鍵盤輸入的字符串，判斷其是否爲迴文。迴文即正反序相同。如

“abba”是迴文，而“abab”不是迴文。

實驗主要步驟

(1)數據從鍵盤讀入;

(2)輸出要判斷的字符串;

(3)利用棧的基本操作對給定的字符串判斷其是否是迴文，若是則輸出“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; // 在棧構造之前和銷燬之後，base的值爲NULL int *top; // 棧頂指針

int stacksize; // 當前已分配的存儲空間，以元素爲單位

} SqStack;

int InitStack(SqStack &S)

{ // 構造一個空棧S

if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))

exit(OVERFLOW); // 存儲分配失敗

=;

ksize=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(>=ksize) // 棧滿，追加存儲空間

{

=(int *)realloc(,(ksize+STACKINCREMENT)*sizeof(int)); if(!)

exit(OVERFLOW); // 存儲分配失敗

=+ksize;

ksize+=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[N] = {0},*p,b[N] = {0};

if(InitStack(s)) // 初始化棧成功

{

printf("請輸入表達式: ");

gets(ch);

p=ch;

while(*p) // 沒到串尾

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;

}

實驗結果：

請輸入表達式：

abcba

輸出：YES!

心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進後出的性質，這個固有性質使棧成爲程序設計中的有用工具。

實驗4

實驗題目：二叉樹操作設計和實現

實驗目的：

掌握二叉樹的定義、性質及存儲方式，各種遍歷算法。

實驗要求：

採用二叉樹鏈表作爲存儲結構，完成二叉樹的建立，先序、中序和後序以及按層次遍歷的操作，求所有葉子及結點總數的操作。

實驗主要步驟：

1、分析、理解程序。

2、調試程序，設計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結點(空指針)，如ABD###CE##F##，建立二叉樹，求出先序、中序和後序以及按層次遍歷序列，求所有葉子及結點總數。

程序代碼:

實驗結果：

心得體會：

實驗5

實驗題目：圖的遍歷操作

實驗目的：

掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構;掌握DFS及BFS對圖的遍歷操作;瞭解圖結構在人工智能、工程等領域的廣泛應用。

實驗要求：

採用鄰接矩陣和鄰接鏈表作爲圖的存儲結構，完成有向圖和無向圖的DFS和BFS操作。

實驗主要步驟：

設計一個有向圖和一個無向圖，任選一種存儲結構，完成有向圖和無向圖的DFS(深度優先遍歷)和BFS(廣度優先遍歷)的操作。

1. 鄰接矩陣作爲存儲結構

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 100 //定義最大頂點數

typedef struct{

char vexs[MaxVertexNum]; //頂點表

int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，可看作邊表 int n,e; //圖中的頂點數n和邊數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); //輸入頂點數和邊數

scanf("%c",&a);

printf("Input Vertex string:");

for(i=0;in;i++)

{

scanf("%c",&a);

G->vexs[i]=a; //讀入頂點信息，建立頂點表

}

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)的頂點序號

G->edges[i][j]=1;;G->edges[j][i]=1;//若爲;//=========定義標誌向量，爲全局變量=;typedefenum{FALSE,TRUE}B;Booleanvisited[MaxVertex;//========DFS：深度優先遍歷的遞歸算;voidDFSM(MGraph*G,inti);{//以Vi爲出發點

G->edges[i][j]=1;

G->edges[j][i]=1; //若爲無向圖，矩陣爲對稱矩陣;若建立有向圖，去掉該條語句 }

}

//=========定義標誌向量，爲全局變量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度優先遍歷的遞歸算法======

void DFSM(MGraph *G,int i)

{ //以Vi爲出發點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣

給出你的編碼

//===========BFS：廣度優先遍歷=======

void BFS(MGraph *G,int k)

{ //以Vk爲源點對用鄰接矩陣表示的圖G進行廣度優先搜索

給出你的編碼

//==========主程序main =====

void main()

{

int i;

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //爲圖G申請內存空間

CreatMGraph(G); //建立鄰接矩陣

printf("Print Graph DFS: ");

DFS(G); //深度優先遍歷

printf(" ");

printf("Print Graph BFS: ");

BFS(G,3); //以序號爲3的頂點開始廣度優先遍歷

printf(" ");

}

2. 鄰接鏈表作爲存儲結構

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 50 //定義最大頂點數

typedef struct node{ //邊表結點

int adjvex; //鄰接點域

struct node *next; //鏈域

}EdgeNode;

typedef struct vnode{ //頂點表結點

char vertex; //頂點域

EdgeNode *firstedge; //邊表頭指針

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是鄰接表類型 typedef struct {

AdjList adjlist; //鄰接表

int n,e; //圖中當前頂點數和邊數

} ALGraph; //圖類型

//=========建立圖的鄰接表=======

void CreatALGraph(ALGraph *G)

{

int i,j,k;

char a;

EdgeNode *s; //定義邊表結點

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d,%d",&G->n,&G->e); //讀入頂點數和邊數

scanf("%c",&a);

printf("Input Vertex string:");

for(i=0;in;i++) //建立邊表

{

scanf("%c",&a);

G->adjlist[i]ex=a; //讀入頂點信息

G->adjlist[i]tedge=NULL; //邊表置爲空表

}

printf("Input edges,Creat Adjacency List ");

for(k=0;ke;k++) { //建立邊表

scanf("%d%d",&i,&j); //讀入邊(Vi，Vj)的頂點對序號

s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結點

s->adjvex=j; //鄰接點序號爲j

s->next=G->adjlist[i]tedge;

G->adjlist[i]tedge=s; //將新結點*S插入頂點Vi的邊表頭部

s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=i; //鄰接點序號爲i

s->next=G->adjlist[j]tedge;

G->adjlist[j]tedge=s; //將新結點*S插入頂點Vj的邊表頭部

}

}

//=========定義標誌向量，爲全局變量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度優先遍歷的遞歸算法======

void DFSM(ALGraph *G,int i)

{ //以Vi爲出發點對鄰接鏈表表示的圖G進行DFS搜索

給出你的編碼

//==========BFS：廣度優先遍歷=========

void BFS(ALGraph *G,int k)

{ //以Vk爲源點對用鄰接鏈表表示的圖G進行廣度優先搜索

給出你的編碼

//==========主函數===========

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(" ");

}

實驗結果：

1. 鄰接矩陣作爲存儲結構

2. 鄰接鏈表作爲存儲結構

心得體會：

實驗6

實驗題目：二分查找算法的實現

實驗目的：

掌握二分查找法的工作原理及應用過程，利用其工作原理完成實驗題目中的內容。。

實驗要求：

編寫程序構造一個有序表L，從鍵盤接收一個關鍵字key，用二分查找法在L中查找key，若找到則提示查找成功並輸出key所在的位置，否則提示沒有找到信息。。

實驗主要步驟：

1. 建立的初始查找表可以是無序的，如測試的數據爲{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2. 給出算法的遞歸和非遞歸代碼;

3. 如何利用二分查找算法在一個有序表中插入一個元素x，並保持表的有序性?

程序代碼

實驗結果：

心得體會：

實驗7

實驗題目：排序

實驗目的：

掌握各種排序方法的基本思想、排序過程、算法實現，能進行時間和空間性能的分析，根據實際問題的特點和要求選擇合適的排序方法。

實驗要求：

實現直接排序、冒泡、直接選擇、快速、堆、歸併排序算法。比較各種算法的運行速度。

實驗主要步驟：

程序代碼

實驗結果：

心得體會：


標籤：實驗報告 數據結構

相關文章