范文一:數據結構實訓報告

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站 一、 實訓目的

《數據結構》實訓是信息管理與信息系統專業集中實踐性環節之一,其目的就是要達到理論與實際應用相結合,使學生能夠根據數據對象的特性,學會數據組織的方法,能把現實世界中的實際問題在計算機內部表示出來,并培養良好的程序設計技能。

題目一:鏈表操作

一、線性鏈表的存儲結構及算法設計

1、設計目的

(1)掌握線性表的在順序結構和鏈式結構實現。

(2)掌握線性表在順序結構和鏈式結構上的基本操作。

2、設計內容和要求

利用順序表鏈表的插入運算建立線性鏈表,然后實現鏈表的查找、插入、刪除、計數、輸出、排序、逆置等運算(查找、插入、刪除、查找、計數、輸出、排序、逆置要單獨寫成函數),并能在屏幕上輸出操作前后的結果。

3、算法設計

a、線性表的建立

LinkList CreateList_L( )

{

//逆位序輸入n個元素的值,建立帶表頭結點的單鏈線性表L

LNode *p;

LinkList L;

int i,n;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL; //先建立一個帶頭結點的單鏈表

printf("輸入要建立鏈表的元素個數: n");

scanf("%d",&n);

printf("輸入鏈表元素值:n");

for(i=n;i>0;i--)

{

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

p=(LinkList)malloc(sizeof(LNode)); //生成新結點

scanf("%d",&p->data); //輸入元素值

p->next=L->next;

L->next=p; //插入表頭

}

printf("輸入的鏈表元素為:n");

Output(L);

return L;

}//CreateList_L

b、線性鏈表的查找

Status GetElem_L(LinkList L)

{

//L為帶頭節點的單鏈表的頭指針

//當第i個元素存在時。其賦值給e并返回OK,否則返回ERROR

int i,j,e;

LNode *p;

printf("所有的鏈表元素為:n");

Output(L);

printf("n輸入要查找的元素位置:n");

scanf("%d",&i);

p=L->next;

j=1;

while(p&&j

{

//順指針向后查找,直到p指向第i個元素或p為空

p=p->next;

j++;

}

if(!p||j>i)

{

return ERROR;//第i個元素不存在

printf("查找的元素不存在n");

}

e=p->data; //取第i個元素

printf("查找的元素為:n %d",e);

return OK;

}//GetElem_L

c、線性鏈表的插入

Status ListInsert_L(LinkList &L)

{

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

//在帶頭結點的單鏈線性表L中第i個位置之前插入元素e

LNode *p,*s;

int i,j,e;

printf("插入之前的鏈表元素為:n");

Output(L);

p=L->next;

j=1;

printf("n輸入要插入元素的位置:n");

scanf("%d",&i);

printf("輸入要插入的元素 e:n");

scanf("%d",&e);

printf("插入的元素為 e: n %dn",e);

while(p&&j {

p=p->next;

++j;

} //尋找第i-1個結點

if(!p||j>i-1)return ERROR; //i小于1或者大于表長+1

s=(LinkList)malloc(sizeof(LNode)); //生成新結點

s->data=e;

s->next=p->next; //插入L中

p->next=s;

printf("插入之后的元素為:n");

Output(L);

return OK;

}//LinkInsert_L

d、線性鏈表的刪除

Status ListDelete_L(LinkList&L)

{

//在帶頭結點的單鏈線性表L中,刪除第i個元素,并由e返回其值

int i,j,e;

LNode *p,*q;

printf("輸出刪除之前的元素:n");

Output(L);

printf("n輸入要刪除的元素位置:n");

scanf("%d",&i);

p=L;

j=0;

while(p->next&&j {

//尋找第i個結點,并由p指向其前驅

p=p->next;

++j;

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

}

if(!(p->next)||j>i-1)

{

return ERROR; //刪除位置不合理q=p->next

printf("刪除位置不合理或輸入錯誤");

}

q=p->next;

p->next=q->next; //刪除并釋放結點

e=q->data;

free(q);

printf("刪除之后的元素為:n");

Output(L);

return OK;

}//ListDelete_L

e、線性鏈表的逆置

void InvertList_L(LinkList L)

{//鏈表的逆置

LNode *p,*q,*s;

printf("逆置前的鏈表元素為:n");

Output(L);

p=L->next;

q=p->next;

p->next=NULL;

while(q->next!=NULL)

{

s=q->next;

q->next=p;

p=q;

q=s;

}

q->next=p;

L->next=q;

printf("n逆置后的鏈表元素為:n");

Output(L);

}

f、線性鏈表的輸出

void Output(LinkList L) {

LNode *p;

int j;

p=L->next;

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

while(p)

{

printf("%d ",p->data);

p=p->next;

++j;

}

}

g、線性鏈表的排序

void SortList_L(LinkList L)

{//鏈表排序

int t;

LNode *p,*q;

printf("排序前的鏈表元素為:n");

Output(L);

p=L->next;

q=p->next;

while(q)

{

while(q)

{

if(p->data>=q->data)

{

t=p->data;

p->data=q->data;

q->data=t;

}

q=q->next;

}

p=p->next;

q=p->next;

}

printf("n由小到大排序后的鏈表元素為:n");

Output(L);

}//SortList_L

4、源代碼

#include #include #define ERROR 0 //出錯 #define OK 1 //正確 typedef int Status; typedef int ElemType; typedef struct LNode

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

{

ElemType data;

struct LNode *next; }LNode,*LinkList;

LinkList L;

void Output(LinkList L) {

LNode *p;

int j;

p=L->next;

while(p)

{

printf("%d ",p->data);

p=p->next;

++j;

}

}

LinkList CreateList_L() {

//逆位序輸入n個元素的值,建立帶表頭結點的單鏈線性表L

LNode *p;

LinkList L;

int i,n;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL; //先建立一個帶頭結點的單鏈表

printf("輸入要建立鏈表的元素個數: n");

scanf("%d",&n);

printf("輸入鏈表元素值:n");

for(i=n;i>0;i--)

{

p=(LinkList)malloc(sizeof(LNode)); //生成新結點

scanf("%d",&p->data); //輸入元素值

p->next=L->next;

L->next=p; //插入表頭

}

printf("輸入的鏈表元素為:n");

Output(L);

return L;

}//CreateList_L

Status GetElem_L(LinkList L)

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

{

//L為帶頭節點的單鏈表的頭指針

//當第i個元素存在時。其賦值給e并返回OK,否則返回ERROR

int i,j,e;

LNode *p;

printf("所有的鏈表元素為:n");

Output(L);

printf("n輸入要查找的元素位置:n");

scanf("%d",&i);

p=L->next;

j=1;

while(p&&j

{

//順指針向后查找,直到p指向第i個元素或p為空

p=p->next;

j++;

}

if(!p||j>i)

{

return ERROR;//第i個元素不存在

printf("查找的元素不存在n");

}

e=p->data; //取第i個元素

printf("查找的元素為:n %d",e);

return OK;

}//GetElem_L

Status ListInsert_L(LinkList &L)

{

//在帶頭結點的單鏈線性表L中第i個位置之前插入元素e

LNode *p,*s;

int i,j,e;

printf("插入之前的鏈表元素為:n");

Output(L);

p=L->next;

j=1;

printf("n輸入要插入元素的位置:n");

scanf("%d",&i);

printf("輸入要插入的元素 e:n");

scanf("%d",&e);

printf("插入的元素為 e: n %dn",e);

while(p&&j {

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

p=p->next;

++j;

} //尋找第i-1個結點

if(!p||j>i-1)return ERROR; //i小于1或者大于表長+1

s=(LinkList)malloc(sizeof(LNode)); //生成新結點

s->data=e;

s->next=p->next; //插入L中

p->next=s;

printf("插入之后的元素為:n");

Output(L);

return OK;

}//LinkInsert_L

Status ListDelete_L(LinkList&L)

{

//在帶頭結點的單鏈線性表L中,刪除第i個元素,并由e返回其值

int i,j,e;

LNode *p,*q;

printf("輸出刪除之前的元素:n");

Output(L);

printf("n輸入要刪除的元素位置:n");

scanf("%d",&i);

p=L;

j=0;

while(p->next&&j {

//尋找第i個結點,并由p指向其前驅

p=p->next;

++j;

}

if(!(p->next)||j>i-1)

{

return ERROR; //刪除位置不合理q=p->next

printf("刪除位置不合理或輸入錯誤");

}

q=p->next;

p->next=q->next; //刪除并釋放結點

e=q->data;

free(q);

printf("刪除之后的元素為:n");

Output(L);

return OK;

}//ListDelete_L

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

Status CountList_L(LinkList L)

{//計數

LNode *p;

int i;

i=0;

p=L->next;

while(p)

{

p=p->next;

i++;

}

printf("鏈表元素個數為:%d",i);

return i;

}

void InvertList_L(LinkList L)

{//鏈表的逆置

LNode *p,*q,*s;

printf("逆置前的鏈表元素為:n");

Output(L);

p=L->next;

q=p->next;

p->next=NULL;

while(q->next!=NULL)

{

s=q->next;

q->next=p;

p=q;

q=s;

}

q->next=p;

L->next=q;

printf("n逆置后的鏈表元素為:n");

Output(L);

}

void SortList_L(LinkList L)

{//鏈表排序

int t;

LNode *p,*q;

printf("排序前的鏈表元素為:n");

Output(L);

p=L->next;

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

q=p->next;

while(q)

{

while(q)

{

if(p->data>=q->data)

{

t=p->data;

p->data=q->data;

q->data=t;

}

q=q->next;

}

p=p->next;

q=p->next;

}

printf("n由小到大排序后的鏈表元素為:n");

Output(L);

}//SortList_L

void main()

{

int i;

printf("n?????????????【請建立鏈表】?????????????n");

L=CreateList_L();

Loop:

printf("n?????????【功能菜單】?????????n");

printf("? ?n");

printf("? 1. 建立鏈表 ?n");

printf("? 2. 插入元素 ?n");

printf("? 3. 查找鏈表元素 ?n");

printf("? 4. 刪除鏈表元素 ?n");

printf("? 5. 逆置鏈表元素 ?n");

printf("? 6. 鏈表元素排序 ?n");

printf("? 7. 輸出鏈表元素 ?n");

printf("? 8. 計算元素個數 ?n");

printf("? 0. 退出 ?n");

printf("? ?n");

printf("????????????????????????n");

printf("【選擇功能】:");

scanf("%d",&i);

switch(i)

{

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

case 0: break;

case 1: CreateList_L();goto Loop;

case 2: ListInsert_L(L);goto Loop;

case 3: GetElem_L(L);goto Loop;

case 4: ListDelete_L(L);goto Loop;

case 5: InvertList_L(L);goto Loop;

case 6: SortList_L(L);goto Loop;

case 7: Output(L);goto Loop;

case 8: CountList_L(L); goto Loop;

default: printf("n輸入錯誤,請重新輸入n");goto Loop;

}

}

題目二:二叉樹的基本操作

一、二叉鏈表存儲結構及算法設計

1、設計目的

(1)掌握二叉樹的概念和性質;

(2)掌握任意二叉樹存儲結構;

(3)掌握任意二叉樹的基本操作。

2、設計內容和要求

對任意給定的二叉樹(頂點數自定)建立它的二叉鏈表存儲結構,并利用棧的五種基本運算(置空棧、進棧、出棧、取棧頂元素、判棧空)實現二叉樹的先序、中序、后序三種遍歷,輸出三種遍歷的結果。

3、算法設計

a、二叉樹先序遍歷

Status PreOrderTraverse(BiTree T)

{//先序遍歷二叉樹

if(T)

{

printf("%c ",T->data);

PreOrderTraverse(T->Lchild);

PreOrderTraverse(T->Rchild);

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

}

return OK;

}//PreOrderTraverse

b、二叉樹中序遍歷

Status InOrderTraverse(BiTree T) {//中序遍歷二叉樹

if(T)

{

InOrderTraverse(T->Lchild);

printf("%c ",T->data);

InOrderTraverse(T->Rchild);

}

return OK;

}

c、二叉樹后序遍歷

Status PostOrderTravese(BiTree T) {//后序遍歷二叉樹

if(T!=NULL)

{

PostOrderTravese(T->Lchild);

PostOrderTravese(T->Rchild);

printf("%c ",T->data);

}

return OK;

}

d、二叉樹深度

Status BiTreeDepth(BiTree T) { //二叉樹深度

int depth=0,depthLeft=0,depthRight=0;

if ( !T)

depth = 0;

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

else

{

depthLeft = BiTreeDepth(T->Lchild );

depthRight= BiTreeDepth(T->Rchild );

depth =1+(depthLeft > depthRight ?depthLeft : depthRight);

}

return depth;

}

e、計算葉子數

Status CountLeaf(BiTree T) {//計算葉子數

int num1,num2,num;

num1=0;num2=0;num=0;

if(!T)

return ERROR;

else

{

if(!(T->Lchild)&&!(T->Rchild))

return OK;

num1=CountLeaf(T->Lchild);

num2=CountLeaf(T->Rchild);

}

num=num1+num2;

return num;

}

f、度為1的二叉樹結點

Status OneNode(BiTree T)

{ //度為1的二叉樹結點

int i=0;

if(T!=NULL)

{

OneNode(T->Lchild);

OneNode(T->Rchild);

if((T->Lchild==NULL&&T->Rchild!=NULL)||(T->Lchild!=NULL&&T->Rchild==NULL))

i++;

return i+1;

}

return OK;

}

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

g、二叉樹總結點數

Status CountNumNode(BiTree T) {

int num=0;

if(!T)

{

return ERROR;

}

if (T)

{

CountNumNode(T->Lchild);

CountNumNode(T->Rchild);

}

num=CountNumNode(T->Lchild)+CountNumNode(T->Rchild)+1;

return num;

}

3.源代碼

#include

#include

#define ERROR 0 //出錯

#define OK 1 //正確

#define OVERFLOW 2 //溢出

typedef char TElemType; typedef int Status;

typedef struct BiTNode

{

TElemType data;

struct BiTNode *Lchild,*Rchild; //左右孩子指針; }BiTNode,*BiTree;

BiTree T;

//***********建立二叉樹***************// Status CreateBiTree(BiTree &T) {//按先序次序輸入二叉樹中結點的值(一個字符),空格字符表示空樹, //構造二叉鏈表表示的二叉樹T

char ch;

scanf("%c",&ch);

if(ch==' ')T=NULL;

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站 else

{

if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch; //生成根結點

CreateBiTree(T->Lchild); //構造左子樹

CreateBiTree(T->Rchild); //構造右子樹

}

return OK;

}//CreateBiTree

//**************先序遍歷二叉樹***************// Status PreOrderTraverse(BiTree T) {//先序遍歷二叉樹

if(T)

{

printf("%c ",T->data);

PreOrderTraverse(T->Lchild);

PreOrderTraverse(T->Rchild);

}

return OK;

}//PreOrderTraverse

//****************中序遍歷二叉樹********************// Status InOrderTraverse(BiTree T) {//中序遍歷二叉樹

if(T)

{

InOrderTraverse(T->Lchild);

printf("%c ",T->data);

InOrderTraverse(T->Rchild);

}

return OK;

}

//**********后序遍歷二叉樹*****************// Status PostOrderTravese(BiTree T) {//后序遍歷二叉樹

if(T!=NULL)

{

PostOrderTravese(T->Lchild);

PostOrderTravese(T->Rchild);

printf("%c ",T->data);

}

return OK;

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站 }

//******************計算二叉樹的深度*****************// Status BiTreeDepth(BiTree T) { //二叉樹深度

int depth=0,depthLeft=0,depthRight=0;

if ( !T)

depth = 0;

else

{

depthLeft = BiTreeDepth(T->Lchild );

depthRight= BiTreeDepth(T->Rchild );

depth =1+(depthLeft > depthRight ?depthLeft : depthRight);

}

return depth;

}

//***************計算葉子數**************// Status CountLeaf(BiTree T)

{//計算葉子數

int num1,num2,num;

num1=0;num2=0;num=0;

if(!T)

return ERROR;

else

{

if(!(T->Lchild)&&!(T->Rchild))

return OK;

num1=CountLeaf(T->Lchild);

num2=CountLeaf(T->Rchild);

}

num=num1+num2;

return num;

}

//*************度為1 的二叉樹結點****************// Status OneNode(BiTree T)

{ //度為1的二叉樹結點

int i=0;

if(T!=NULL)

{

OneNode(T->Lchild);

OneNode(T->Rchild);

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站 if((T->Lchild==NULL&&T->Rchild!=NULL)||(T->Lchild!=NULL&&T->Rchil

d==NULL))

i++;

return i+1;

}

return OK;

}

//*****************計算總結點數***************// Status CountNumNode(BiTree T) {

int num=0;

if(!T)

{

return ERROR;

}

if (T)

{

CountNumNode(T->Lchild);

CountNumNode(T->Rchild);

}

num=CountNumNode(T->Lchild)+CountNumNode(T->Rchild)+1;

return num;

}

//*****************主函數********************// void main()

{

int i;

printf("n????????????????【請建立二叉樹】???????

?????????n");

printf("請輸入要建立的結點n");

CreateBiTree(T);

Loop:

printf("n?????????【功能菜單】?????????n");

printf("? ?n");

printf("? 1. 建立二叉樹 ?n");

printf("? 2. 先序遍歷二叉樹 ?n");

printf("? 3. 中序遍歷二叉樹 ?n");

printf("? 4. 后序遍歷二叉樹 ?n");

printf("? 5. 二叉樹深度 ?n");

printf("? 6. 二叉樹結點數 ?n");

printf("? 7. 二叉樹葉子數 ?n");

printf("? 8. 二叉樹度為1的結點 ?n");

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站

printf("? 0. 退出 ?n");

printf("? ?n");

printf("????????????????????????n");

printf("【選擇功能】:");

scanf("%d",&i);

switch(i)

{

case 0: break;

case 1: CreateBiTree(T);goto Loop;

case 2: PreOrderTraverse(T);goto Loop;

case 3: InOrderTraverse(T);goto Loop;

case 4: PostOrderTravese(T);goto Loop;

case 5: printf("二叉樹深度為:n %d",BiTreeDepth(T));goto Loop;

case 6: printf("二叉樹總結點數為:n %d",CountNumNode(T));goto Loop;

case 7: printf("二叉樹葉子數為:n %d",CountLeaf(T));goto Loop;

case 8: printf("二叉樹度為1的結點數為:n %d",OneNode(T)); goto Loop;

default: printf("n輸入錯誤,請重新輸入:n");goto Loop;

}

}

實習總結

緊張的兩周數據結構實訓很快就過去了,通過這兩周的實踐學習,不僅使我們鞏固了以前的知識并在此基礎上還對數據結構的特點和算法有了更深的了解,使我們在這門課程的實際應用上也有了一個提高。

首先這兩周的學習,使我們在鞏固了原有的理論知識上,又培養了靈活運用和組合集成所學過知識及技能來分析、解決實際問題的能力,使我們體會到自身知識和能力在實際中的應用和發揮。其次,它激發了我們創新意識,開發創造的能力和培養溝通能力。

其次,讓我們進一步熟悉了數據結構的設計應用。每一處編碼都是在反復的熟悉數據結構的結構特性,及其語法、函數和程序設計思想的過程,對我們數據結構的學習和提高很有益處,并且使我們明白了程序設計過程,如解決一些實際問題,從解決實際問題的角度,第一要了解這個問題的基本要求,即輸入、輸出、完成從輸入到輸出的要求是什么;第二,從問題的要害入手,從前到后的解決問題的每個方面,即從輸入開始入手,著重考慮如何從輸入導出輸出,在這個過程

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳~ 更多精彩內容請關注本站 中,可確定所需的數據結構的基本類型——線性表、棧、隊列、串、數組、廣義表、樹和二叉樹以及圖等,然后確定處理過程——算法,通過在編譯環境中的編譯與調試,可到最終的程序。

最后,在這次的實訓過程中,我們深刻的認識到了自己在學習方面的不足之處,我知道我還有太多的基本的思想沒有真正的理解,當然我們不會灰心,我們會在以后的日子里努力彌補我們的不足。

從最初的查閱資料到最后的程序的成功運行,兩個星期的時間讓我們經歷了很多,也收獲了很多。經過這次課程設計,我們不僅學到了很多知識和技能,更重要的是我們學會了如何運用所學知識去解決實際問題。

總之,兩個星期的課程設計讓我們受益匪淺。我們深深認識到,數據結構是計算機程序設計的重要理論技術基礎,它是計算機科學的核心課程。要學好一門學科,沒有刻苦鉆研的精神是不行的,只有在不斷的嘗試中,經歷失敗,從失敗中總結經驗,然后再不斷的嘗試,才能獲得成功。

參考文獻

1.《C++程序設計》,清華大學出版社,

2.《數據結構,C語言版,》,清華大學出版社,

3.《數據結構,C語言版,》,中國鐵道出版社,

專業好文檔為您整理~謝謝使用~請雙擊清除頁眉頁腳

范文二:《數據結構》實訓報告

實驗一 線性表

1. 實驗要求

1.1 掌握數據結構中線性表的基本概念。

1.2 熟練掌握線性表的基本操作:創建、插入、刪除、查找、輸出、求長度及合并并運算在順序存儲結構上的實驗。

1.3 熟練掌握鏈表的各種操作和應用。

2. 實驗內容

2.1 編寫一個函數,從一個給定的順序表A 中刪除元素值在x 到y 之間的所有元素,要求以較高效率來實現。

2.2 試寫一個算法,在無頭結點的動態單鏈表上實現線性表插入操作

2.3 設計一個統計選票的算法,輸出每個候選人的得票結果。

3. 實驗代碼

2.1代碼:

#include

typedef int elemtype;

#define maxsize 10

int del(int A[],int n,elemtype x,elemtype y)

{

int i=0,k=0;

while(i{if(A[i]>=x&&A[i]

k++;

else

A[i-k]=A[i];

i++;

}

return(n-k);

}

void main()

{

int i,j;

int a[maxsize];

printf("輸入%d個數:n",maxsize);

for(i=0;iscanf("%d,",&a[i]);

j=del(a,maxsize,1,3);

printf("輸出刪除后剩下的數:n");

for(i=0;iprintf("%d "n,a[i]);

}

2.2代碼:

INSERT(L,i,b)。

void Insert(Linklist &L,int i,elemtype x)

{

if(!L)

{

L=(Linklist)malloc(sizeof(Lnode));

(*L).data=x;(*L).next=NULL;

}

else

{

if(i==1)

{

s=(Linklist)malloc(sizeof(Lnode));

s->data=x;s->next=L;L=s;

}

else

{

p=L;j=1;

while(p&&j{j++;p=p->next;}

if(p||j>i-1)

return error;

s=(Linklist)malloc(sizeof(Lnode));

s->data=x;s->next=p->next;p->next=s;

}

}

}

2.3代碼:

typedef int elemtype

typedef struct linknode

{

elemtype data;

struct linknode *next;

}nodetype;

nodetype *create()

{

elemtype d;

nodetype h=NULL,*s,*t;

int i=1;

printf("建立單鏈表:n");

while(1)

{

printf("輸入第%d個結點數據域",i);

scanf("%d",&d);

if(d==0)break;

if(i==1)

{

h=(nodetype *)malloc(sizeof(nodetype));

h->data=d;h->next=NULL;t=h;

}

else

{

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

s->data=d;s->next=NULL;t->next=s;

t=s;

}

i++;

}

return h;

}

void sat(nodetype *h,int a[])

{

nodetype *p=h;

while(p!=NULL)

{

a[p->data]++;

p=p->next;

}

}

void main()

{

int a[N+1],i;

for(i=0;ia[i]=0;

nodetype *head;

head=create();

sat(head,a);

}

printf("候選人:"); for(i=1;i

4. 實驗小結

線性表是最簡單的、最常用的一種數據結構,是實現其他數據結構的基礎。

實驗二 棧與隊列

1. 實驗要求

1.1 了解棧和隊列的特性,以便靈活運用。

1.2 熟練掌握棧和有關隊列的各種操作和應用。

2. 實驗內容

2.1 設一個算術表達式包括圓括號,方括號和花括號三種括號,編寫一個算

法判斷其中的括號是否匹配。

3. 實驗代碼

2.1代碼:

#include

#include

#include

#define NULL 0

typedef struct list

{

char str;

struct list *next;

}list;

void push(char,list *);

int pop(char.list *);

void deal(char *str);

main(void)

{

char str[20];

printf("n請輸入一個算式:n");

gets(str);

deal(str);

printf("正確!");

getchar();

return 0;

}

void deal(char *str)

{

list *L;

L=(list *)malloc(sizeof(list));

if(!L)

{

printf("錯誤!");

exit(-2);

}

L->next=NULL;

while(*str)

{

if(*str=='('||*str=='['||*str=='{')

push(*str,L);

else

if(*str==')'||*str==']'||*str=='}')

if(pop(*str,L))

{puts("錯誤, 請檢查!");

puts("按回車鍵退出");

getchar();exit(-2);

}

str++;

}

if(L->next)

{

puts("錯誤, 請檢查!");

puts("按任意鍵退出");

getchar();exit(-2);

}

}

void push(char c,list *L)

{

list *p;

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

if(!p)

{

printf("錯誤!");

exit(-2);

}

p->str=c;

p->next=L->next;

L->next=p;

}

#define check(s) if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L)

{

list *p;

if(L->next==NULL)return 1;

switch(c)

{

case')':check('(') break;

case']':check('[') break;

case'}':check('{') break;

}

return 1;

4. 實驗小結

棧和隊列是最基礎的一種數據結構之一,為實現其他數據結構的奠定基石。

實驗三 樹

1. 實驗要求

1.1 掌握二叉樹,二叉樹排序數的概念和存儲方法。

1.2 掌握二叉樹的遍歷算法。

1.3 熟練掌握編寫實現樹的各種運算的算法。

2. 實驗內容

2.1 編寫程序,求二叉樹的結點數和葉子數。

2.2 編寫遞歸算法,求二叉樹中以元素值為X 的結點為根的子數的深度。

2.3 編寫程序,實現二叉樹的先序,中序,后序遍歷,并求其深度。

3. 實驗代碼

2.1代碼:

#include

#include

struct node{

char data;

struct node *lchild,*rchild;

}bnode;

typedef struct node *blink;

blink creat()

{

blink bt;

char ch;

ch=getchar();

if(ch==' ') return(NULL);

else

{

bt=(struct node *)malloc(sizeof(bnode));

bt->data=ch;

bt->lchild=creat();

bt->rchild=creat();

}

return bt;

}

int n=0,n1=0;

void preorder(blink bt)

{

if (bt)

{

n++;

if(bt->lchild==NULL&&bt->rchild==NULL)

n1++;

preorder(bt->lchild);

preorder(bt->rchild);

}

}

void main()

{

blink root;

root=creat();

preorder(root);

printf("此二叉數的接點數有:%dn",n);

printf("此二叉數的葉子數有:%dn",n1);}

2.2代碼:

int get_deep(bitree T,int x)

{

if(T->data==x)

{

printf("%dn",get_deep(T));

exit 1;

}

else

{

if(T->lchild)get_deep(T->lchild,x);

if(T->rchild)get_deep(T->rchild,x);

}

int get_depth(bitree T)

{

if(!T)return 0;

else

{

m=get_depth(T->lchild);

n=get_depth(T->rchild);

return(m>n?m:n)+1;

}

}

2.3代碼:

#include

#include

struct node{

char data;

struct node *lchild,*rchild;

}bnode;

typedef struct node *blink;

blink creat()

{

blink bt;

char ch;

ch=getchar();

if(ch==' ') return(NULL);

else

{

bt=(struct node *)malloc(sizeof(bnode));

bt->data=ch;

bt->lchild=creat();

bt->rchild=creat();

}

return bt;

}

void preorder(blink bt)

{

if (bt)

{

printf("%c",bt->data);

preorder(bt->lchild);

preorder(bt->rchild);

}

}

void inorder(blink bt)

{

if(bt)

{

inorder(bt->lchild);

printf("%c",bt->data);

inorder(bt->rchild);

}

}

void postorder(blink bt)

{

if(bt)

{

postorder(bt->lchild);

postorder(bt->rchild);

printf("%c",bt->data);

}

}

int max(int x,int y)

{

if(x>y)

return x;

else

return y;

}

int depth(blink bt)

{

if (bt)

return 1+max(depth(bt->lchild),depth(bt->rchild));

else

}

{ return 0; void main()

blink root;

root=creat(); printf("n"); printf("按先序排列:");

preorder(root);printf("n");

printf("按中序排列:");

inorder(root);printf("n");

printf("按后序排列:");

postorder(root);printf("n");

} printf("此二叉數的深度是:"); printf("depth=%dn",depth(root));

4. 實驗小結

通過本章學習實驗,對樹有了初步的認識。樹就是一種非線性的數據結構,描述了客觀世界中事物之間的層次關系。這種結構有著廣泛的應用,一切具有層次關系的問題都可以用樹來表示。

實驗四 圖

1. 實驗要求

1.1 熟悉圖的各種存儲方法。

1.2 掌握遍歷圖的遞歸和非遞歸的算法。

1.3 理解圖的有關算法。

2. 實驗內容

2.1 寫出將一個無向圖的鄰接矩陣轉換成鄰接表的算法。

2.2 以鄰接表作存儲結構,給出拓撲排序算法的實現。

3. 實驗代碼

2.1代碼:

void mattolist(int a[][],adjlist b[],int n) /*n為圖的結點個數*/

{

for(i=0;ifor(i=0;i

}

2.2代碼:

typedef struct vexnode

{

VertexType vertex; int in;/*增加一個入度域*/ ArecNodeTp * fristarc; for(j=n-1;j>=0;j--) if(a[i][j]!=0) {p=(arcnodetp *)malloc(sizeof(arcnodetp));/*產生鄰接點*/ p->adjvex=j; p->nextare=b[i].firstare; b[i].firstarc=p; }

}AdjList[vnum];

typedef struct graph

{

AdjList adjlist; int vexnum,arcnum;

}GraphTp;

Top_Sort(GraphTp g)

{

LstackTp *p;/*建立入度為0的頂點棧S*/

int m,i,v;

initStack(S);

} for(i=0;iv printf("%d",v);/*輸出v*/ m++; p=g.adjlist[i].fristarc;/*p=圖g 中頂點v 的第一個鄰接點*/ while(p!=NULL){//p存在 } (g.adjlist[p->adjvex].in)--;/*p的入度--*/ if(g.adjlist[p->adjvex].in==0)/*if(p的入度==0)*/ Push(S,p->adjvex);/*p入S 棧*/ p=p->nextarc;/*p=圖g 中的頂點v 的下一個鄰接點*/

4. 實驗小結

通過本章學習實驗,對圖有了具體的認識。圖也是一種非線性的數據結構,這種結構有著廣泛的應用,一切具有關系的問題都可以用圖來表示。

實驗五 查找

1. 實驗要求

1.1 掌握順序查找、二分法查找、分塊查找和哈希表查找的算法。

1.2 能運用線性表的查找方法解決實際問題。

2. 實驗內容

2.1 編寫一個算法,利用二分查找算法在一個有序表中插入一個元素

X ,并保持表的有序性。

2.2 根據給定的數據表,先建立索引表,然后進行分塊查找。

3. 實驗代碼

2.1代碼:

#include

#include

#define MAXNUM 20

int input(int *);/*輸入數據*/

int search(int *,int,int);/*查找插入位置*/

void plug(int *,int,int);/*插入數據*/

void main(void)

{

int data[MAXNUM],m; int insert=1; m=input(data); printf("Input the insert num:"); scanf("%d",data); insert=search(data,1,m);/*返回插入位置*/

plug(data,insert,m);

for(insert=1;insert

printf("%3d",*(data+insert));

getch();

}

int input(int *data)

{

int i,m;

printf("nInput the max num:");

scanf("%d",&m);

printf("input datan");

for(i=1;i

scanf("%d",data+i);

return m;

}

int search(int *data,int low,int high)/*遞歸查找插入位置*/

{

int mid;

if(low>high) return low;/*沒有找到插入數據,返回low*/

else{

}

search(data,low,high);

}

void plug(int *data,int insert,int m)

{

int i;

for(i=m;i>insert;i--)

*(data+i+1)=*(data+i); mid=(low+high)/2; if(*(data+mid)==*data) retun mid;/*找到插入數據,返回mid*/ else if(*(data+mid)*data)

*(data+insert)=*data

}

2.2代碼:

#include

#include

#include

#definr N 18 /*元素個數*/

#definr Blocknum 3 /*分塊數*/

typedef struct indexterm

{

int key;/*最大關鍵字*/

int addr;/*塊的起始地址*/

}index; /*索引表數據類型*/

index * CreateList(int data[],int n)/*建索引表*/

{

index *p;

int m,j,k;

m=n/BlockNum;/*分為BlockNum 塊,每塊有m 個元素*/

p=(index *)malloc(BlockNum *sizeof(index));

for(k=0;k

}

return p;

}

int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分塊查找*/ {

int low=0,high=m-1,mid,i;

(p+k)->key=dat a[m*k]; (p+k)->addr=m*k; for(j=m*k;j(p+k)->key) (p+k)->key=data[j];/*塊的最大關鍵字*/

int b=n/m;/*每塊有b 個元素*/

while(low

}

if(lowfor(i=(list+low)->addr;iadder+b-1&&rectab[i]!=k;i++);

}

return -1;

}

void main()

{

int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; int key;

index *list;

printf("please input key:n");

scanf("%d",&key);

list=CreateList(record,N);

printf("data postion id %dn",BlockSearch(list,record,N,BlockNum,key)); } if(iaddr+b-1) return i; mid=(low+high)/2; if((list+mid)->key>=k) high=mid+1; else low=mid+1; else return -1;

4. 實驗小結

通過本章的學習,對排序有較高層次的理解與認識,從平時的練習中可以看出排序是數據處理中經常用到的重要運算。有序的順序表可以采用查找效率較高的折半查找法,而無序的順序表只能用效率較低的順序查找法。

范文三:數據結構實訓報告

山東科技大學泰山科技學院

課程實訓說明書

課程: 數據結構

系部名稱: 信息工程系 專業班級:

學生姓名: 徐志宏 ___

學 號:

指 導 教 師: 學 校: 2015年7月22日

目錄

第一章 課程設計性質與目的..................................4

第二章 設計內容及基本要求............................5

第三章 詳細設計說明......................................... 11

3.1 項目一............................................................. 7

3.2 項目二............................................................ 16

3.3 項目三.......................................................... 26

第四章 實訓總結.................................................. .37

附錄 (參考文獻、核心代碼)

第一章 課程設計性質與目的

《數據結構》實訓是信息管理與信息系統專業集中實踐性環節之一,其目的就是要達到理論與實際應用相結合,使學生能夠根據數據對象的特性,學會數據組織的方法,能把現實世界中的實際問題在計算機內部表示出來,并培養良好的程序設計技能。

鏈表和順序表操作的設計目的: 1.掌握線性表的在順序結構和鏈式結構實現。 2.掌握線性表在順序結構和鏈式結構上的基本操作。

二叉樹操作的設計目的: 1.掌握二叉樹的概念和性。2. 掌握任意二叉樹存儲結構。 3.掌握任意二叉樹的基本操作。

第二章 設計內容及基本要求

一、實驗實訓的基本要求是:

本實訓面向應用,以解決實際問題為主。題目以選用學生相對比較熟悉的為宜,要求通過本實訓,理解有關數據結構的基本概念、不同數據類型的存儲和基本操作的算法實現,理解數據類型的邏輯結構及物理存儲結構, 通過自己設計,編程、調試、測試、能夠基本掌握在不同存儲結構下的算法實現及算法優化,樹立并培養系統規范開發的理念。實訓中學生要將相關課程中學到的知識、思想和理念盡量應用在實訓中。結束后要按規定提交代碼和各種文檔。

實訓基本步驟:

1. 選題

設計的課題盡量結合教學、科研的實際課題,規模、大小適當,具有一定復雜度。應根據題目大小、難度確定是否分組,組內成員人數。

2. 數據結構及算法設計

根據需求分析,選擇合理的數據結構及設計相應的算法。

3. 編碼

根據已設計的數據結構和算法,編寫代碼。

4. 測試

按照系統測試的原則、方法和步驟,對系統進行測試。測試中應形成測試報告。

5. 編寫實訓報告

實訓說明書,內容及要求如下:

(1) 封面

(2) 成績評定

(3) 目錄

(4) 說明書正文,主要內容包括:

一、 設計題目

二、 運行環境(軟、硬件環境)

三、 數據結構及算法設計的思想

四、 數據結構及算法設計

五、 源代碼

六、 運行結果分析

七、 實習總結(收獲及體會)

參考資料:附錄(核心代碼)。

二、設計內容 項目一:順序表操作

1、設計目的

(1)掌握線性表的在順序結構上的實現。

(2)掌握線性表在順序結構上的基本操作

2、設計內容和要求

利用順序表的插入運算建立順序表,然后實現順序表的查找、插入、刪除、計數、輸出、排序、逆置等運算(查找、插入、刪除、查找、計數、輸出、排序、逆置要單獨寫成函數),并能在屏幕上輸出操作前后的結果。

項目二:鏈表操作

1、設計目的

(1)掌握線性表的在鏈式結構上的實現。

(2)掌握線性表在鏈式結構上的基本操作

2、設計內容和要求

利用鏈表的插入運算建立鏈表,然后實現鏈表的查找、插入、刪除、計數、輸出、排序、逆置等運算(查找、插入、刪除、查找、計數、輸出、排序、逆置要單獨寫成函數),并能在屏幕上輸出操作前后的結果。

項目三:二叉樹的基本操作

1、設計目的

(1)掌握二叉樹的概念和性質

(2)掌握任意二叉樹存儲結構。

(3)掌握任意二叉樹的基本操作。

2、設計內容和要求

(1)對任意給定的二叉樹(頂點數自定)建立它的二叉鏈表存儲結構,并利用棧的五種基本運算(置空棧、進棧、出棧、取棧頂元素、判棧空)實現二叉樹的先序、中序、后序三種遍歷,輸出三種遍歷的結果。

(2) 求二叉樹高度、結點數、度為1的結點數和葉子結點數。

第三章 詳細設計說明

項目一:

順序表操作:

考查知識點:(1)利用順序表的插入運算建立順序表;

(2)實現順序表的查找、插入、刪除、計數、輸出、排序、逆置等運算(查找、插入、刪除、查找、計數、輸出、排序、逆置要單獨寫成函數);

(3)能夠在屏幕上輸出操作前后的結果。

一、算法

1. 創建:#define LIST_INIT_SIZE 100

#define LISTINCREMENT 20

typedf struct{

Elem Type *elem;

int length;

int listsize;

}SqList;

Status InitList.Sq(SqList&L){

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);

L.lengh=0;

L.listsize=LIST_INIT_SIZE;

return Ok;

}//InitList_Sq

2. 插入:Status ListInsert_Sq(SqList&L,int i,ElemType e){//插入

if(iL.length+1)return ERROR;

if(L.length>=L.listsize){

newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]);//q指示插入位置

for(p=&(L.elem[L.length-1);p>=q;--p)*(p+1)=*p;

*q=e

++L.length;

return OK;

}//ListInsert_Sq

3. 刪除:Status ListDelete_Sq(SqList &L,nt i,ElemType&e){

if((iL.length))return ERROR;

p=&(L.elem[i-1]);

e=*p;

q=L.elem+L.length-1;//表尾元素的位置

for(++p;p

--L.length;//表長減1

return OK;

}//ListDelete_Sq

4. 查找:Int LocateElem_Sq(SqList L,ElemType e,

Status (*compare)(ElemType ,

ElemType )){

i=1;

p=L.elem;

while(i

if(i

else return 0;

}//LocateElem_Sq

二、源代碼

#include

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

typedef int ElemType;

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 20

typedef struct { //查找

}SqList; int length; int listsize;

int InitList_Sq(SqList &L) {

L.list = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (!L.list) exit (OVERFLOW); // 存儲分配失敗

int i,y;

L.length = 0;

L.listsize = LIST_INIT_SIZE;

printf("請輸入元素個數:");

scanf("%d",&y); printf("請輸入元素:n"); for(i=0;ireturn OK;

} // InitList_Sq

//*****************輸出函數******************

void output_Sq(SqList &L)

{

}

//*****************插入*********************

Status ListInsert_Sq(SqList &L){ printf("輸出順序表n"); for(int i=0;i

int i,e; printf("請輸入插入位置i:"); scanf(" %d",&i); if(i L.length + 1) return ERROR; if(L.length >= L.listsize){ newbase = (ElemType *)realloc(L.list, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.list = newbase; L.listsize += LISTINCREMENT; } q = &(L.list[i-1]); // q指示插入位置 for (p = & (L.list[L.length-1]); p >= q; --p)*(p+1) = *p; // 插入位置及之后的元素右移

printf("輸入插入數值e: "); scanf("%d",&e); *q = e; ++L.length; printf("輸出插入之后的順序表:"); for( i=0;i} // ListInsert_Sq

//*****************刪除*********************

int ListDelete_Sq(SqList &L){

ElemType *p,*q; int i,e;

printf("請輸入你要刪除的元素位序:"); scanf("%d",&i); if ((i L.length)) return ERROR; p = & (L.list[i-1]); e = *p; q = L.list + L.length - 1; // 表尾元素的位置

printf("刪除的元素值為: %dn",e);

for (++p; p

*(p-1) = *p;

--L.length;

for( i=0;iprintf("%d ",L.list[i]);

printf("n");

return OK;

} // ListDelete_Sq

//******************查找********************

Status LocateElem_Sq(SqList L){

int e,i;

printf("請輸入你要查找元素的數值:

scanf("%d",&e);

printf("你要查找元素的位序為: ");

for(i=0;i{

if(e==L.list[i])

printf("%d ",i+1);

}

printf("n");

return 0;

} ");

//************排序(由小到大)*************

void Print_Sq(SqList &L)

{int t;

}

//*****************計數********************

void ListLength_Sq(SqList L){

}

//*****************逆置********************

void inverse_Sq(SqList &L)

{

int t,i; for(i=0;iL.list[i+1]) {t=L.list[i];L.list[i]=L.list[i+1];L.list[i+1]=t;} printf("輸出排序(由小到大)表n"); for(int i=0;i} //*****************退出*********************

int Quit_Sq(SqList L)

{

}

//****************主函數********************

void main()

{

SqList L; int i; printf(" 1. 構造 n"); printf(" 2. 插入 n"); printf(" 3. 刪除 n"); printf(" 4. 排序 n"); printf(" 5. 計數 n"); printf(" 6. 查找 n"); printf(" 7. 逆置 n"); printf(" 8. 輸出 n"); printf(" 9. 退出 n"); for(;;) { printf("Please choose 1 to 9 :n"); scanf("%d",&i); switch(i) { case 1:InitList_Sq(L);break; case 2:ListInsert_Sq(L); break; exit (0); return 0;

} case 4:Print_Sq(L); break; case 5:ListLength_Sq(L); break; case 6:LocateElem_Sq(L);break; case 7:inverse_Sq(L);break; case 8:output_Sq(L);break; case 9: Quit_Sq(L);break; default:printf("輸入有誤"); } }

三、操作結果

項目二:

鏈表操作

考查知識點:(1)利用鏈表的插入運算建立鏈表;

(2)實現鏈表的查找、插入、刪除、計數、輸出、排序、逆置等運

算(查找、插入、刪除、查找、計數、輸出、排序、逆置要單獨寫

成函數);

(3)能夠在屏幕上輸出操作前后的結果。

一、算法

1. 創建:

void CreateList_L(LinkList &L){ //逆序輸入n 個元素的值,建立帶頭結點的單鏈線性表L 。

L=(LinkList)malloc(sizeof(LNode));//生成新的結點

L->next=NULL;

//先建立一個帶頭結點的單鏈表

for(i=n;i>0;--i)

{

p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);

p->next = L->next;L->next = p; //插入到表頭

}

}//CreateList L

2. 插入:

Status ListInsert_L(LinkList &L,int i ,ElemType e){ //插入 p=L;j=0;

while(p&&j{

p=p->next;

++j;

}

if(!p||j>i)return ERROR;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

3. 刪除:

Status ListDelete_L(LinkList &L,int &e){ //刪除

j=0;

p=L;

while(p->next && jp=p->next;

++j;

}

if(!(p->next)||j>i-1)

return ERROR;

q=p->next;

p->next=q->next;

e=q->data;

free(q);

return OK;

}//ListDelete_L

4. 查找:

Status GetElem_L(LinkList L,int i , ElemType &e) //查找 {

p=L->next;

j=1;

while(p && j

{

p=p->next;

j++;

}

if(!p||j>1)retun ERROR

e=p->data;

retun OK;

}//GetElem.L

二、源代碼

#include

#include

#define OK 1

#define ERROR 0

typedef struct LNode

{

int data;

struct LNode * next;

}LNode, * LinkList;

//逆序輸入n 個元素的值,建立帶頭結點的單鏈線性表L 。 void CreateList_L(LinkList &L){

int i,x;

LNode *p=NULL;

L=(LinkList)malloc(sizeof(LNode));//生成新的結點

L->next=NULL; //先建立一個帶頭結點的單鏈表 printf("請輸入結點個數:");

scanf("%d",&x);

printf("請輸入各結點元素的值為:");

for(i=x;i>0;--i) //逆序輸入x 個元素的值

{

p=(LinkList)malloc(sizeof(LNode));

scanf("%d",&p->data);

p->next = L->next;L->next = p; //插入到表頭

}

p=L->next; //將p 指向頭結點

//輸出已創建的鏈表

printf("逆序輸出鏈表為:n");

while(p)

{

printf("%d ",p->data);

p=p->next;

}

}

//*****************插入*******************

int ListInsert_L(LinkList &L){

LNode *p,*s;

int j=0,e,i;

p=L;

printf("請輸入所要插入的位置:");

scanf("%d",&i);

printf("請輸入所要插入的數:");

scanf("%d",&e);

while(p&&j{

p=p->next;

++j;

}

if(!p||j>i-1)

printf("輸入數據有誤, 請輸入數值在1 -- x+1之間輸入"); s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

p=L ->next;

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("n");

return OK;

}

//*****************刪除********************

int ListDelete_L(LinkList &L,int &e){

LNode *p,*q;

int i,j=0;

p=L;

printf("請輸入要刪除的第幾個結點:");

scanf("%d",&i);

while(p->next && jp=p->next;

++j;

}

if(!(p->next)||j>i-1)

printf("輸入的數值錯誤或刪除位置不合理");

q=p->next;

p->next=q->next;

e=q->data;

free(q);//釋放被刪除結點

printf("被刪除結點的數值為: %dn",e);

p=L ->next;

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("n");

return OK;

}

//******************計數********************

void CountList_L(LinkList &L)

{

int i=0;

LNode *p=L->next;

while(p)

{i++;

p=p->next;}

printf("結點個數為:%dn",i);

}

//*****************查找*******************

int LocateElem_L(LinkList L)

{

LinkList p=L;

int i,j=0;

printf("請輸入要查找的數的序號:");

scanf("%d",&i);

while(p && j

{

p=p->next;

j++;

}

if(j!=i||!p)

{

printf("參數i 錯或單鏈表不存在");

return(NULL);

}

printf("你查找的第 %d 個結點的數值為 %dn",i,p->data); return OK;

}

//*******************排序******************* void SortList_L(LinkList L)

{

int i,j,t,k = 0;

LNode *p = L->next,*q;

while(p)

{

k++;

p=p->next;

}

p=L->next; q=p->next; //初始化

for(i=0;i{

p = L->next;

for(j=0,p;jnext)

{

q = p->next;

if(p->data > q->data) //升序

{

t=p->data;

p->data=q->data;

q->data=t;

}

}

}

p=L->next;

printf("輸出升序的鏈表為:n");

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("n");

}

//*******************輸出***************

void OutputList_L(LinkList L)

{

LNode *p;

p=L->next;

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("n");

}

//*******************逆置****************

int ReverseList_L(LinkList &L)

{

LNode *p ,*q;

p=L->next;

q=p->next;

L->next=NULL;

while(p->next)

{

p->next=L->next;

L->next=p;

p=q;

q=q->next;

}

p->next=L->next;

L->next=p;

printf("逆置后的鏈表結果為:");

for(p=L->next;p;p=p->next)

printf("%d ",p->data);

printf("n");

return 0;

}

//***************主函數**************

int main()

{

LinkList L=NULL;

int i,e;

printf("逆序輸入創建一個鏈表并實現下列功能n");

printf(" 1. 創建 n");

printf(" 2. 插入 n");

printf(" 3. 刪除 n");

printf(" 4. 計數 n");

printf(" 5. 查找 n");

printf(" 6. 排序 n");

printf(" 7. 輸出 n");

printf(" 8. 逆置 n");

for(;;)

{

printf("請在1-8功能中選擇一個: ");

scanf("%d",&i);

//************函數調用*************

switch(i)

{

case 1:CreateList_L(L); break;

case 2:ListInsert_L(L); break;

case 3:ListDelete_L(L,e); break;

case 4:CountList_L(L); break;

case 5:LocateElem_L(L); break;

case 6:SortList_L(L); break;

case 7:OutputList_L(L); break;

case 8:ReverseList_L(L); break;

default:printf("輸入錯誤");

}

}

printf("n");

return 0;

}

三、操作結果

項目三:

二叉樹的操作:

一、考查知識點:1. 對任意給定的二叉樹(頂點數自定)建立它的二叉鏈表存儲

結構;

2. 利用棧的五種基本運算(置空棧、進棧、出棧、取棧頂元素、

判棧空)實現二叉樹的先序、中序、后序三種遍歷,輸出

三種遍歷的結果。

3. 求二叉樹高度、結點數、度為1的結點數和葉子結點數。

二、算法:

1. 創建二叉樹:

Status Createbitree(bitree &t) //功能1:構建二叉樹的二叉鏈表

{ scanf(& ch); //按先序遍歷建立二叉樹 if(ch==’’)

T=NULL;

else

{

if(!(T=(BiTNde)malloc(sizeof(BiTNode))))exit(OVERFLOW); }

T->data=ch;

Createbitree(t->lchild);

Createbitree(t->rchild);

}

Return OK;

}//CreatBiTree

2. 先序遍歷: Status PreOrderTraverse(Bitree T,Status(* visit)(TElemType) )

{//采用二叉鏈表存儲結構,Visit 是對數據元素操作的應用函

if(T)

{ if(Visist(T->data))

if (PreOrderTraverse(p->lchild,Visit));

if PreOrderTraverse(p->rchild,Visit));

}

return OK;

return ERROR;

}elese returnOK;

}// PreOrderTraverse

3. 中序遍歷:Status InOrderTraverse(Bitree T,Status(* Visit)(TElemType) ){ InitStack(s);Push (S,T);

While(!StackEmpty(s){

While(GetTop(s,p)&&p)Push(S,p->lchild);

Pop(S,p);

If(!StackEmpty(s)){

Pop(s,p);if (!Visit(p->data))retu ERROR;

Push(S,p->rchild);

}//if

}//While

Retun OK;

}// InOrderTraverse

二、源代碼

#include

#include

#include

#define true 1

#define false 0

#define ok 1

#define error 0

#define overflow -2

typedef void status;

typedef char BTtype;

typedef char Stype;

typedef struct BTnode {//定義二叉樹存儲結構

BTtype data;

struct BTnode *lc,*rc;

}BTnode,*BTtree;

typedef struct{//定義棧的存儲結構

Stype *base;

Stype *top;

int stacksize;

} Sqstack;

int max(int a,int b){

return a>b?a:b;

}

char Creat(BTtree &t){//創建

char ch;

//printf("按順序輸入二叉樹各節點的值:");

scanf("%c",&ch);

if(ch==' ') t=NULL;

else {

if(!(t=(BTtree )malloc(sizeof(BTnode)))){

printf("創建失敗。。");

exit(overflow);

}

t->data=ch;

Creat(t->lc);

Creat(t->rc);

}

return ok;

}

char orderx(BTtree &t){//先序

BTtree p=t;

if(p){

printf("%c",p->data);

orderx(p->lc);

orderx(p->rc);

}

return 0;

}

char orderz(BTtree &t){//中序

BTtree p=t;

if(p){

orderz(p->lc);

printf("%c",p->data);

orderz(p->rc);

}

return 0;

}

char orderh(BTtree &t){//后序

BTtree p=t;

if(p){

orderh(p->lc);

orderh(p->rc);

printf("%c",p->data);

}

return 0;

}

int Depth(BTtree t){//求深度

int d,dl,dr;

if(!t) d=0;

else{

dl=Depth(t->lc);

dr=Depth(t->rc);

d=max(dl,dr)+1;

}

return d;

}

int Nodes(BTtree &t){//結點數

int num1,num2;

if(t==NULL)

return 0;

else{

num1=Nodes(t->lc);

num2=Nodes(t->rc);

return (num1+num2+1);

}

}

void Degree(BTtree t,int &n){//度為1的結點個數

//int n=0;

if(t){

if((t->lc && !t->rc) || (!t->lc && t->rc))

n++;

Degree(t->lc,n);

Degree(t->rc,n);

}

}

void Leaves(BTtree &t,int &yz){//葉子數

//int yz=0;

if(t){

if((!t->lc) && (!t->rc))

yz++;

Leaves(t->lc,yz);

Leaves(t->rc,yz);

}

//return yz;

}

void Quit(){//退出

exit(0);

}

int main(){

BTtree t;

int yz=0;

int n=0;

int x;//用于case 或if

printf("需先按順序輸入二叉樹各節點的值:");

if(Creat(t)) printf("創建成功!n");

printf("1、先序n2、中序n3、后序n4、求深度n5、求結點數n6、

求度為一的結點數n7、求葉子數n8、退出n");

/*for(;;){

printf("請選擇1-9:");

scanf("%d",&x);

switch(x){

case 1:printf("按順序輸入二叉樹各節點的值:"); Creat(t);

printf("創建成功!n"); break;

case 2:printf("先序遍歷二叉樹:");

orderx(t);

printf("n");break;

case 3:printf("中序遍歷二叉樹:");

orderz(t);

printf("n");break;

case 4:printf("后序遍歷二叉樹:");

orderh(t);

printf("n");break;

case 5:printf("二叉樹的深度為:%dn",Depth(t));break; case 6:printf("二叉樹的節點數

為:%dn",Nodes(t));break;

case 7:Leaves(t,yz);

printf("葉子數為:%dn",yz);break;

case 8:Degree(t,n);

printf("度為1的節點個數為:%dn",n);break; case 9:Quit(); break;

default:printf("輸入錯誤");

}

}*/

for(;;){

printf("請選擇1-8:");

scanf("%d",&x);

/*if(x=1){

printf("按順序輸入二叉樹各節點的值:");

Creat(t); printf("創建成功!n");

}else*/

if(x==1){

printf("先序遍歷二叉樹:");

orderx(t);

printf("n");

}else if(x==2){

printf("中序遍歷二叉樹:");

orderz(t);

printf("n");

}else if(x==3){

printf("后序遍歷二叉樹:");

orderh(t);

printf("n");

}else if(x==4){

printf("二叉樹的深度為:%dn",Depth(t)); }else if(x==5){

printf("二叉樹的節點數為:%dn",Nodes(t)); }else if(x==6){

Degree(t,n);

printf("度為1的節點個數為:%dn",n); }else if(x==7){

Leaves(t,yz);

printf("葉子數為:%dn",yz);

}else if(x==8){

Quit();

}else printf("輸入有誤。。n");

}

/*printf("按順序輸入二叉樹各節點的值:");

if(Creat(t)) printf("創建成功!n");

printf("先序遍歷二叉樹:");

orderx(t);

printf("n");

printf("中序遍歷二叉樹:");

orderz(t);

printf("n");

printf("后序遍歷二叉樹:");

orderh(t);

printf("n");

printf("二叉樹的深度為:%dn",Depth(t));

printf("二叉樹的節點數為:%dn",Nodes(t));

Degree(t,n);

printf("度為1的節點個數為:%dn",n);

Leaves(t,yz);

printf("葉子數為:%dn",yz);*/

return 0;

}

三、操作結果

第四章 實訓總結 通過這次實訓,我把在課本上所學到的理論知識,運用到了實際的編程當中,也讓我受益頗深。在這個為期兩周的實訓中, 我發覺到了自己的弱項和不足項, 也經過努力去克服了它們.

最深刻的總結成一個公式:學了?學會了?會用了,有些東西自己利用所學的地只是遠遠不能用算法很好的表達出來, 只能借助于書本, 互聯網查找資料, 甚至以前老師所給做的筆記才能勉強完成. 有些不足還是.

在開始的時候困難是很大的, 于是乎我并沒有急于開工, 我先翻閱書本查找了有關知識點進行溫習熟悉, 然后翻閱有關筆記, 上網查找資料. 之后我才開始編寫算法, 實現目標這個過程中不免與同學進行交流合作. 這個鋪橋的工作完成了. 下面的’’路’’也就好修了.

附錄

參考文獻:

(1)《C 程序設計(第二版)》,譚浩強編,清華大學出版社,1999

年1月。

(2)《C 語言程序設計題解與上機指導》,譚浩強編,清華大學

出版社,2000年11月。

(3)數據結構C 語言版,嚴蔚敏,吳偉民編著,清華大學出版

社,1997年4月。

范文四:數據結構實訓報告

山東科技大學泰山科技學院

課程實訓說明書

課程:數據結構(C

題目:單鏈表、二叉樹

院 系: 信 息 工 程 系

2015年 12月 18 日

專業班級: 計算機科學與技術 學 號: 學生姓名: 指導教師:

語言版)

目錄

一、設計題目············································1 課程設計題一:鏈表操作 1、設計目的 2、設計內容和要求

課程設計題二:二叉樹的基本操作 1、設計目的 2、設計內容和要求

二、運行環境(軟、硬件環境)····························1 1、軟件環境 2、硬件環境

三、數據結構及算法設計的思想 ··························2 課程設計題一:鏈表操作

課程設計題二:二叉樹的基本操作

四、數據結構及算法設計·································4 課程設計題一:鏈表操作 課程設計題二:二叉樹的基本操作

五、源代碼 ············································6 課程設計題一:鏈表操作 課程設計題二:二叉樹的基本操作

六、運行結果分析 ······································16 課程設計題一:鏈表操作

1、利用鏈表的插入運算建立線性鏈表(頭插法) 2、鏈表的查找 3、鏈表的插入 4、鏈表刪除 5、鏈表的計數 6、鏈表的輸出 7、鏈表的排序 8、鏈表的逆置

課程設計題二:二叉樹的基本操作 1、建立二叉樹(先序) 2、二叉樹的先序遍歷 3、二叉樹的中序遍歷 4、二叉樹的后序遍歷 5、求二叉樹的高度 6、求二叉樹的結點數 7、求二叉樹的度為1的結點數 8、求二叉樹的葉子結點數

七、實習總結(收獲及體會)································22

一、設計目的

課程設計題一:鏈表操作

1、設計目的

(1)掌握線性表的在順序結構和鏈式結構實現。 (2)掌握線性表在順序結構和鏈式結構上的基本操作。 2、設計內容和要求

(1)利用鏈表的插入運算建立線性鏈表,然后實現鏈表的查找、插入、刪除、計數、輸出、排序、逆置等運算(查找、插入、刪除、計數、輸出、排序、逆置要單獨寫成函數),并能在屏幕上輸出操作前后的結果。

課程設計題二:二叉樹的基本操作

1、 設計目的

(1)掌握二叉樹的概念和性質 (2)掌握任意二叉樹存儲結構。 (3)掌握任意二叉樹的基本操作。 2、設計內容和要求

(1)對任意給定的二叉樹(頂點數自定)建立它的二叉鏈表存儲結構,并利用棧的五種基本運算(置空棧、進棧、出棧、取棧頂元素、判棧空)實現二叉樹的先序、中序、后序三種遍歷,輸出三種遍歷的結果。 (2)求二叉樹高度、結點數、度為1的結點數和葉子結點數。

二、 運行環境(軟、硬件環境)

1、軟件環境

Microsoft Visual C++ 6.0 2、硬件環境 計算機一臺

處理器:Intel(R) Core(TM) i3-4010U CPU @ 1.70GHz 1.70GHz

三、 數據結構及算法設計的思想

課程設計題一:鏈表操作

(1)定義一個創建鏈表的函數,通過該函數可以創建一個鏈表,并為下面的函數應用做好準備。( 因為每個新生成的結點的插入位置在表尾,則算法中必須維持一個始終指向已建立的鏈表表尾的指針。)

(2)定義一個遍歷查找(按序號差值)的算法,通過此算法可以查找到鏈表中的每一個結點是否存在。 (單鏈表是一種順序存取的結構,為找第 i 個數據元素,必須先找到第 i-1 個數據元素。因此,查找第 i 個數據元素的基本操作為:移動指針,比較 j 和 i 。令指針 p 始終指向線性表中第 j 個數據元素。設單鏈表的長度為 n ,要查找表中第 i 個結點,僅當 1≤i ≤n 時,i 的值是合法的。)

(3)定義插入結點的算法,通過定義這個算法,并結合這查找前驅和后繼的算法便可以在連鏈表的任意位置進行插入一個新結點。(在鏈表中插入結點只需要修改指針。但同時,若要在第 i 個結點之前插入元素,修改的是第 i-1 個結點的指針。因此,在單鏈表中第 i 個結點之前進行插入的基本操作為:找到線性表中第i-1個結點,然后修改其指向后繼的指針。) (4)定義刪除結點的操作,這個算法用于對鏈表中某個指定位置的結點的刪除工作。(在單鏈表中刪除第 i 個結點的基本操作為:找到線性表中第i-1個結點,修改其指向后繼的指針。)

(5)定義一個計數的算法,通過此算法可以統計鏈表中結點的個數。 (6)定義輸出鏈表的算法,通過對第一步已經定義好的創建鏈表函數的調用,在這一步通過調用輸出鏈表的函數算法來實現對鏈表的輸出操作。 (7)定義一個排序(冒泡排序)的算法,通過此算法對表中元素按照一定順序進行排列。

(8)定義一個逆置單鏈表的操作,通過定義此算法,可以逆置輸出單鏈表。(將原鏈表中的頭結點和第一個元素結點斷開(令其指針域為空),先構成一個新的空表,然后將原鏈表中各結點,從第一個結點起,依次插入這個新表的頭部(即令每個插入的結點成為新的第一個元素結點))

課程設計題二:二叉樹的基本操作

(1)定義二叉樹鏈表:二叉樹的鏈式存儲方式下每個結點包含3個域,分別記錄該結點的屬性值及左右子樹的位置。其左右子樹的位置是通過指針方式體現,其中Ichild 是指向該結點左子樹的指針,rchild 為指向該結點右子數的指針。

結點結構:

(2)二叉樹的創建:根據先序遍歷結果建立二叉樹,將第一個輸入的結點作為二叉樹的根結點,后繼輸入的結點序列是二叉樹左右子樹先序遍歷的結果,由它們生成二叉樹的左子數;再接下來輸入的結點序列為二叉樹右子樹先序遍歷的結果,應該由它們生成二叉樹的右子樹。而由二叉樹左子樹先序遍歷的結果生成二叉樹的左子樹和由二叉樹右子樹先序遍歷的結果生成二叉樹的右子樹的過程均與由整棵二叉樹的先序遍歷結果生成該二叉樹的過程完全相同,只是所處理的對象范圍不同,所以可以用遞歸方式實

現之。使用CreatBitree 建立一顆二叉樹時,必須按其先序遍歷的順序輸入結點的值,遍歷過程中遇到空子樹時,必須使用“#”代替。 例如:ABC##DE#G##F###

(3)二叉樹的先序遍歷:首先訪問根結點;然后按照先序遍歷的方式訪問根結點的左子樹;再按照先序遍歷的方式訪問根結點的右子數。

(4)二叉樹的中序遍歷:首先按照中序遍歷的方式訪問根結點的左子樹;然后訪問根結點;最后按照中序遍歷的方式訪問根結點的右子樹。 (5)二叉樹的后序遍歷:首先按照后序遍歷的方式訪問根結點的左子樹;然后按照后序遍歷的方式訪問根結點的右子樹;最后訪問根結點。 (6)求二叉樹的高度:二叉樹T ,如果T 為空,則高度為0;否則,其高度為其左子樹的高度和右子樹的高度的最大值再加1。

(7)求二叉樹的結點數:二叉樹T ,若T 為空,則T 中所含結點的個數為0;否則,T 中所含結點個數等于左子樹中所含結點個數加上右子樹中所含結點的個數再加1。

(8)求二叉樹度為1的結點數:二叉樹T ,若T 為空,則T 中度為1的結點數為0;否則,T 所含度為1的結點數等于左子樹不為空右子樹為空和左子樹為空右子樹不為空的結點個數之和。

(9)求二叉樹的葉子結點數:求二叉樹中葉子結點的個數,即求二叉樹的所有結點中左、右子數均為空的結點個數之和。

四、 數據結構及算法設計

課程設計題一:鏈表操作

typedef struct LNode//線性表的單鏈表存儲結構

void CreatList_L(LinkList &L,int n);//頭插法建表 (逆序建表)

void GetElem_L(LinkList &L);//按序號查值

Status ListInsert_L(LinkList &L,int i,ElemType e);//插入 Status ListDelete_L(LinkList &L,int i,ElemType &e);//刪除 void ListLength(LinkList &L);//計數 void PrintList(LinkList &L);//輸出 void ListSort(LinkList &L);//冒泡排序 void OpposeList(LinkList &L);//逆置

課程設計題二:二叉樹的基本操作

typedef struct BiTNode//------二叉樹的二叉鏈表存儲結構---------

Status CreateBiTree(BiTree &T)//建立二叉樹的存儲結構 —— 二叉鏈表(先序)。

Status PreOrderTraverse (BiTree &T,Status (*Visit)(ElemType e))//先序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實現

Status InOrderTraverse (BiTree &T,Status (*Visit)(ElemType e))//中序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實現

Status PostOrderTraverse (BiTree &T,Status (*Visit)(ElemType e))//后序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實現 Status Visit(ElemType e)// 對二叉樹中的數據元素訪問 int BiTreeDepth(BiTree &T)//求二叉樹的高度 int CountNode(BiTree &T)//二叉樹的結點數 int NodeOne(BiTree &T)//二叉樹中度為1的結點數 int CountLeaf (BiTree &T) //統計二叉樹葉子結點

五、 源代碼

課程設計題一:鏈表操作

#include #include #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType;

typedef struct LNode{ ElemType data;

struct LNode *next;

}LNode,*LinkList; int i,j,k; LinkList L,p,q,s,r,head;

void CreatList_L(LinkList

&L,int n);//頭插法建表 (逆序建表)

void GetElem_L(LinkList

&L);//按序號查值

Status ListInsert_L(LinkList

&L,int i,ElemType e);//插入

Status ListDelete_L(LinkList

&L,int i,ElemType &e);//刪除

void ListLength(LinkList

&L);//計數

void PrintList(LinkList &L);//

輸出

void ListSort(LinkList &L);//冒泡排序

void OpposeList(LinkList

&L);//逆置

void CreatList_L(LinkList &L,int n){//逆位序輸入n 個元素的值,建立帶表頭結點的單鏈線性表L 。

L=(LinkList)malloc(sizeof(L

Node));

L->next=NULL;

//先建立一個帶頭結點的單鏈表 for(i=n;i>0;--i){

p=(LinkList)malloc(sizeof(LNode));//生成新結點

scanf("%d",&p->data); //輸入元素值

p->next=L->next; //插到表頭

L->next=p;

}

}//頭插法建表 (逆序建表)

void GetElem_L(LinkList &L){//L為帶頭接點的單鏈表的頭指針。當第i 個元素存在時,其賦值給e 并返回ERROR int i,e; p=L->next;

j=1; //初始化,p 指向第

一個結點,j 為計時器

printf("請輸入查找位

置:n");

scanf("%d",&i);

while(p&&j

后查找,直到p 指向第i 個元素或p 為空 p=p->next; ++j; }

if(!p||j>i)

printf("第%d個元素不存

在!",i); //第i 個元素不存在

e=p->data;

//取第i 個元素

printf("查找結果

為:%dn",e);

}//按序號查值

Status ListInsert_L(LinkList &L,int i,ElemType e){//在帶頭接點的單鏈線性表L 中第i 個位置之前插入元素e p=L; j=0;

printf("請輸入插入位

置:n");

scanf("%d",&i); while(p&&jnext;

++j;

} //

尋找第i-1個結點 if(!p||j>i-1)

return ERROR; //i

小于1或者大于表長加1

s=(LinkList)malloc(sizeof(L

Node)); //生成新結點

printf("請輸入插入元

while(p->next&&j素:n");

scanf("%d",&e);

//尋找第i 個結點,并命令p 指向其前趨

s->data=e; p=p->next;

//插入L 中 s->next=p->next; p->next=s;

printf("插入后的鏈表為:

n"); PrintList(L);

return OK; }//插入

Status ListDelete_L(LinkList &L,int i,ElemType &e){//在帶頭接點的單鏈線性表L 中,刪除第i 個元素,并由e 返回其值 p=L; j=0;

printf("請輸入刪除元素位

置:n");

scanf("%d",&i);

++j; }

if(!(p->next)||j>i-1)

return ERROR; //刪除位置不合理 q=p->next;

p->next=q->next; //刪除并釋放結點 e=q->data; free(q);

printf("刪除后的鏈表為:

n"); PrintList(L);

return OK; }//刪除

void ListLength(LinkList &L){ p=L;

int j=0;

//線性鏈表最后一個結點的

指針為空 while((p->next)!=NULL) { j++; p=p->next;

}

printf("單鏈表總共有%d個

元素n",j); printf("n"); }//計數

void PrintList(LinkList &L) { p=L->next; if(p==NULL)

printf("n 鏈表為空!"); else while(p)

{

printf("%d ",p->data); p=p->next; }

printf("n");

}//輸出

void ListSort(LinkList &L)//排序 { int t; int count=0; p=L->next; while(p) {

count++; p=p->next; }

for(i=0;i

p=L->next;

for(j=0;jp->next) {

if(p->data >

p->next->data) { t=p->data;

p->data=p->next->data;

p->next->data=t;

} } }

printf("排序后的鏈表為:

n"); p = L->next; while(p)

{

printf("%d ",p->data); p=p->next; }

printf("n");

}//冒泡排序(升序)

void OpposeList(LinkList &L){ p=L; p=p->next; L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q;

}

printf("逆置后的鏈表為:n"); PrintList(L); }//逆置

int main() {

int a,n,e;

printf("************【請先建立單鏈表】************n");

printf("請輸入元素個數

值:n"); scanf("%d",&n);

printf("請輸入%d個元

素:n",n); CreatList_L(L,n);

for(;;) {

printf("--------------請選擇如下操作碼------------n"); printf("n");

printf("*****-----------【1】查找------------*****n");

printf("*****-----------【2】插

入------------*****n");

printf("*****-----------【3】刪

除------------*****n");

printf("*****-----------【4】計

break; break; break; break; break;

case 3: ListDelete_L(L,i,e);

數------------*****n");

printf("*****-----------【5】輸

case 4: ListLength(L);

出------------*****n");

printf("*****-----------【6】排

case 5: PrintList(L);

序------------*****n");

printf("*****-----------【7】逆

case 6: ListSort(L);

置------------*****n");

printf("******************************************n"); scanf("%d",&a); switch(a) { break; break;

case 7: OpposeList(L);

default:printf("選擇錯誤!n");

} } return 0;

case 1: GetElem_L(L);

}

case 2: ListInsert_L(L,i,e);

課程設計題二:二叉樹的基本操作

#include #include #define OK 1 #define ERROR 0

#define OVERFLOW 0 typedef char ElemType; typedef int Status; typedef int TElemType;

//------二叉樹的二叉鏈表存儲結構---------

typedef struct BiTNode{ TElemType data;

struct BiTNode

*lchild,*rchild; }BiTNode,*BiTree; char ch;

//建立二叉樹的存儲結構 —— 二叉鏈表(先序)。 Status CreateBiTree(BiTree &T){ //按先序次序輸入二叉樹結點的值(一個字符),空格字符表示空樹,構造二叉樹鏈表表示的二叉樹T 。 scanf("%c",&ch); if(ch=='#') T=NULL; else{

if(!(T=(BiTNode*)malloc(si

zeof(BiTNode)))) exit(OVERFLOW);

T->data=ch;

//生成根結點

CreateBiTree(T->lchild);

//構造左子樹

CreateBiTree(T->rchild);

//構造右子樹 } return 0;

}

//先序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實現 Status PreOrderTraverse (BiTree &T,Status (*Visit)(ElemType e)) {

if(T){ if(!Visit(T->data)) return ERROR;

PreOrderTraverse(T->lchild,Visit); PreOrderTraverse(T->rchild,Visit); }

return OK; }

//中序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實現

Status InOrderTraverse (BiTree &T,Status (*Visit)(ElemType e)) {

if(T){

}

Status Visit(ElemType e){

InOrderTraverse(T->lchild,Visit); // 對二叉樹中的數據元素訪問 if(e=='新手怎么买彩票