第一篇：數(shù)據(jù)結(jié)構(gòu)上機作業(yè)

實驗一 線性表

一、實驗題

線性表的應用———多項式計算

二、程序設(shè)計思路

包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路一鏈式存儲：

1.void InitPoly(LNode *&p)初始化多項式 2.void TraversePoly(LNode *&p)遍歷多項式 3.void ClearPoly(LNode *&p)清除多項式

4.void InsertPoly(LNode *&p, double a, int e)插入一項 5.void DeletetPoly(LNode *&p,int pos)

刪除一項

6.double PolySum(LNode *&p, double x)

多項式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2)

多項式相加 順序存儲：

1.void InitPoly1(SeqList &L)初始化多項式 2.void ClearPoly1(SeqList &L)清除多項式 3.void TraversePoly1(SeqList L)

遍歷多項式

4.bool InsertPoly1(SeqList &L, ElemType item)插入一項 5.double PolySum1(SeqList L,double x)

多項式求值 6.bool DeleteList1(SeqList &L,int pos)

刪除一項

7.SeqList PolyAdd1(SeqList &L1,SeqList& L2)

多項式相加

三、源程序代碼

#include #include #include #include “Linkpoly.h” #include “Seqpoly.h” void main(){ cout<<“現(xiàn)在進行第一次測試。（鏈表表示）”<>n;cout<<“請依次輸入要測試的各項的系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly(pa, a, e);//插入一項 pa=pa->next;} pa=pa->next;cout<<“該多項式為:”;TraversePoly(pa);//輸出多項式 cout<>a;cin>>e;cin>>pos;if(DeletetPoly(pa, a, e, pos)){ cout<<“刪除成功！現(xiàn)在多項式為:”;TraversePoly(pa);cout<>x;sum=PolySum(pa, x);cout<<“該多項式的值為:”<>n;cout<<“請輸入該多項式的各項系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly(pb, a, e);//插入一項 pb=pb->next;} pb=pb->next;pp=PolyAdd(pa, pb);cout<<“兩多項式相加后得到的多項式為:”;TraversePoly(pp);cout<>n;cout<<“請依次輸入要測試的各項的系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly1(s, a, e);} cout<<“該多項式為:”;TraversePoly1(s);cout<>a;cin>>e;cin>>pos;if(DeletetPoly1(s, a, e, pos)){ cout<<“刪除成功！現(xiàn)在多項式為:”;TraversePoly1(s);cout<>x;sum=PolySum1(s, x);cout<<“該多項式的值為:”<>n;cout<<“請輸入該多項式的各項系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly1(t, a, e);//插入一項 } q=PolyAdd1(s, t);cout<<“兩多項式相加后得到的多項式為:”;TraversePoly1(q);cout<next=p;return true;} void TraversePoly(NodeType *p)//輸出多項式 { NodeType *h=p->next;if(h!=p){ cout<coef<<“*”<<“X”<<“^”<exp;h=h->next;} while(h!=p){ if(h->coef>0)cout<<“+”;cout<coef<<“*”<<“X”<<“^”<exp;h=h->next;} } void ClearPoly(NodeType *&p)//清除多項式 { NodeType *cp,*np;cp=p->next;while(cp!=p){ np=cp->next;delete cp;cp=np;} p->next=p;} bool InsertPoly(NodeType *&p, float a, int e)//插入一項 { NodeType *h;if((h=new NodeType)==NULL)return false;h->coef=a;h->exp=e;h->next=p->next;p->next=h;return true;} bool DeletetPoly(NodeType *&p, float a, int e, int pos)//一項

{ if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){

刪除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多項式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多項式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->expexp){ InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;} else{ InsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;} } while(a!=p1){ InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;} while(b!=p2){ InsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;} return c;} Seqploy.h: #define MaxSize 10000 struct ListType{ float *list;int size;};void InitPoly1(ListType &p)//初始化多項式 { p.list=(float*)malloc(MaxSize*sizeof(float));if(p.list==NULL){ cout<<“動態(tài)可分配的儲存空間用完，退出運行！”<0){ cout<<“+”;cout<

輸出多項式 } void ClearPoly1(ListType &p)//清除多項式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//項

{ p.list[e]=a;if(p.size

{ int i,n;if(p.size==0){ cout<<“多項式為空,刪除無效!”<

插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值

{ double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//項式相加

{ ListType p;InitPoly1(p);float coef;

多項式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四實驗結(jié)果分析

五.心得體會 對于結(jié)構(gòu)體的認識增加了，對于動態(tài)存儲也有了更多的認識，也是在不知不覺中提高了。

實驗二 字符串的操作

一、實驗題目——字符串的操作

二、程序設(shè)計思路

采用定長順序存儲表示，由用戶創(chuàng)建串s和串t，實現(xiàn)在串s中下標為pos的字符之前插入串t。

三、源程序代碼

#define MAXLEN 10 typedef struct {

/*串結(jié)構(gòu)定義*/

char ch[MAXLEN];

int len;}SString;void createstring(SString *s)

/*創(chuàng)建串s*/ { int i,j;char c;printf(“input the length of the string:”);

scanf(“%d”,&j);

for(i=0;i

{

printf(“input the %d:”,i+1);

fflush(stdin);

scanf(“%c”,&c);

s->ch[i] = c;

} s->len = j;} void output(SString *s)

/*輸出串s*/ {

int i;for(i=0;ilen;i++)

printf(“%c

”,s->ch[i]);

printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下標為pos的字符之前插入串t */ {

int i;if(pos<0 || pos>s->len)

/*插入位置不合法*/

return(0);

if(s->len + t->len<=MAXLEN)

/*插入后串長≤MAXLEN*/ {

for(i=s->len + t->len-1;i>=t->len + pos;i--)

s->ch[i]=s->ch[i-t->len];/*將下標為pos的字符后的元素往后移動t->len個長度*/

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

s->ch[i+pos]=t->ch[i];

/*將串t從下標為pos位置開始插入到串s*/

s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/

{

for(i=MAXLEN-1;i>t->len+pos-1;i--)

s->ch[i]=s->ch[i-t->len];

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

s->ch[i+pos]=t->ch[i];

/*將串t從下標為pos位置開始插入到串s*/

s->len=MAXLEN;

}

else

/*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/

{

for(i=0;i

s->ch[i+pos]=t->ch[i];

/*直接從下標為pos的位置按順序插入串t*/

s->len=MAXLEN;

}

return(1);} } void main(){

SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0)

printf(“insert error!”);else {

printf(“after insert:n”);

output(str1);} }

四、實驗結(jié)果

五、實驗體會

通過本次實驗，我加深了對串數(shù)據(jù)結(jié)構(gòu)的理解。在串的定長順序存儲結(jié)構(gòu)中，按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。在存儲方式中，結(jié)點大小的選擇和順序存儲方式的格式選擇一樣都很重要，它直接影響著串處理的效率。

實驗三

一、實驗題目——非遞歸算法對二叉樹進行中前序遍歷

二、程序設(shè)計思路

創(chuàng)建一棵10個節(jié)點構(gòu)造的完全二叉樹，并對其進行前、中、后序遍歷。

三、源程序代碼

#define STUDENT EType #define SType SType

#define HeadEType int

#include #include

//定義數(shù)據(jù)結(jié)構(gòu)類型

struct STUDENT { char name[8];int age;char number[15];char address[20];};

struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree;

typedef struct { BinaryTreeNode *ptr;bool status;}SType;

typedef struct { SType *element;int top;int MaxSize;}Stack;

void CreatStack(Stack &S, int MaxStackSize){// 構(gòu)造一個最大容量為MaxStackSize 的堆棧

S.MaxSize = MaxStackSize;

S.element = new SType[S.MaxSize];

S.top =-1;}

bool IsEmpty(Stack &S){// 判斷堆棧S是否為空

if(S.top ==-1)

return true;

return false;}

bool IsFull(Stack &S){// 判斷堆棧S是否為空

if(S.top == MaxSize-1)

return true;

return false;}

bool Push(Stack &S , SType &x){// x進s棧，返回進棧后的狀態(tài)值

if(IsFull(S))

return false;

S.top++;

S.element[S.top] = x;

return true;}

bool Pop(Stack &S , SType &x){// 將s棧頂?shù)闹等≈義中，返回出棧后的狀態(tài)值

if(IsEmpty(S))

return false;

x = S.element[S.top];

S.top--;

return true;}

BinaryTreeNode

*MakeNode(EType &x)

{//構(gòu)造結(jié)點

BinaryTreeNode *ptr;

ptr = new BinaryTreeNode;

if(!ptr)return NULL;

ptr->data = x;

ptr-> LChild = NULL;

ptr-> RChild = NULL;

return

ptr;}

void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 聯(lián)接root，left, right所指的結(jié)點指針為二叉樹

root->LChild=left;

root->RChild=right;}

void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉樹前序遍歷非遞歸的算法

Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大

CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧

while(q||!IsEmpty(S)){

if(q)

{

cout<data.name<<“ ”;//訪問“根”節(jié)點

ele.ptr=q;

Push(S,ele);//節(jié)點指針進棧，以后回溯時在退棧

q=q->LChild;//指針指向剛剛被訪問的“根”節(jié)點的左子樹

}

else

//當左子樹為空時，利用堆?；厮?/p>

if(!IsEmpty(S))

{

Pop(S,ele);//退?；厮?/p>

q=ele.ptr;//指針重新指向剛剛被訪問的“根”節(jié)點

q=q->RChild;//指針指向該回溯節(jié)點的右子樹

} } }

void InOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的中序遍歷非遞歸的算法

Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大

CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧

while(q ||!IsEmpty(S)){

while(q)//找到最左邊的子樹

{

ele.ptr=q;

Push(S,ele);//指針非空時，將當前的“根”節(jié)點指針進棧，用于以后回溯

q=q->LChild;//指針繼續(xù)指向該“根”節(jié)點的左子樹

}

if(!IsEmpty(S))//當左子樹為空時，進行退?；厮?/p>

{

Pop(S,ele);//從堆棧中回溯節(jié)點指針（節(jié)點還未訪問）

q=ele.ptr;

cout<data.name<<“ ”;//訪問回溯的“根”節(jié)點

q=q->RChild;//指針向回溯的節(jié)點右子樹推進

} } }

void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的后序遍歷非遞歸的算法

Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大

CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧

while(q ||!IsEmpty(S)){

if(q)//找最左邊的子樹

{

ele.ptr=q;

ele.status=false;//進棧前標記為第一次進棧

Push(S,ele);

q=q->LChild;//指針繼續(xù)向左推進

}

else

if(!IsEmpty(S))//直到左子樹為空時，退棧回溯

{

Pop(S,ele);//從堆棧中彈出回溯節(jié)點（還未訪問）

q=ele.ptr;//q指向當前回溯節(jié)點

if(ele.status)//判斷節(jié)點進棧標志，是否對其進行訪問

{

cout<data.name<<“ ”;//訪問回溯節(jié)點

q=NULL;//將q設(shè)為空，為了繼續(xù)退棧

}

else

{

ele.status=true;//改變回溯節(jié)點的進棧標記，以便再次進棧

Push(S,ele);

q=q->RChild;//指針向該回溯節(jié)點的右孩子推進

}

} } }

//主函數(shù) void main(){ BinaryTreeNode *ptr[11];

char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){

strcpy(x[11-i].name,Name[11-i]);

ptr[11-i]=MakeNode(x[11-i]);//構(gòu)造10個二叉樹節(jié)點

}

//將節(jié)點鏈接域填值，構(gòu)造一個二叉樹

//這里構(gòu)造的是一棵有10個節(jié)點的完全二叉樹

for(int j=1;j<5;j++){

MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//該完全二叉樹構(gòu)造完畢

//***********對已構(gòu)造的完全二叉樹進行前序非遞歸遍歷************// cout<<“對該二叉樹進行前序遍歷結(jié)果：”<

//***********對已構(gòu)造的完全二叉樹進行中序非遞歸遍歷************// cout<

//***********對已構(gòu)造的完全二叉樹進行中序非遞歸遍歷************// cout<

四、實驗結(jié)果分析

五、實驗總結(jié)

二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現(xiàn)。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現(xiàn)，非遞歸后序遍歷實現(xiàn)起來相對來說要難一點。

實驗四

一、實驗題目——深度優(yōu)先算法實現(xiàn)圖的遍歷

二、程序設(shè)計思路

以鄰接矩陣或鄰接表為存儲結(jié)構(gòu)，以用戶指定的頂點為起始點，實現(xiàn)無向連通圖的深度優(yōu)先，并輸出遍歷的結(jié)點序列。首先，根據(jù)用戶輸入的頂點總數(shù)和邊數(shù)，構(gòu)造無向圖，然后以用戶輸入的頂點為起始點，進行深度優(yōu)先，并輸出遍歷的結(jié)果。

三、源程序代碼

#include #define MaxVerNum 50 struct edgenode { int endver;int inform;edgenode* edgenext;

};struct vexnode

{ char vertex;edgenode* edgelink;};struct Graph

{ vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//隊列的定義及相關(guān)函數(shù)的實現(xiàn) struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL)

return;if(Q->rear==NULL)

Q->front=Q->rear=q;else {

Q->rear->next=q;

Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL)

return;if(Q->front==Q->rear){

*e=Q->front->nData;

Q->front=Q->rear=NULL;} else {

*e=Q->front->nData;

Q->front=Q->front->next;} } //創(chuàng)建圖

void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“請輸入頂點數(shù)和邊數(shù):”<>G->vexnum>>G->arcnum;cout<<“開始輸入頂點表:”<vexnum;i++){

cin>>G->adjlists[i].vertex;

G->adjlists[i].edgelink=NULL;} cout<<“開始輸入邊表信息:”<arcnum;k++){

cout<<“請輸入邊對應的頂點:”;

cin>>i>>j;

p1=new edgenode;

p1->endver=j;

p1->edgenext=G->adjlists[i].edgelink;

G->adjlists[i].edgelink=p1;

p2=new edgenode;

p2->endver=i;

p2->edgenext=G->adjlists[j].edgelink;

G->adjlists[j].edgelink=p2;

//因為是無向圖，所以有兩次建立邊表的過程

} }

//------------------------------深度優(yōu)先遍歷 void DFS(Graph *G,int i,int visit[]){ cout<adjlists[i].vertex<<“ ”;visit[i]=1;edgenode *p=new edgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){

DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度優(yōu)先遍歷 { cout<<“該圖的深度優(yōu)先遍歷結(jié)果為:”<vexnum;i++){

visit[i]=0;//全部初始化為0，即未訪問狀態(tài)

} int m;for(i=0;ivexnum;i++){

if(G->adjlists[i].vertex==c)//根據(jù)字符查找序號

{

m=i;

DFS(G,i,visit);

break;

} } //繼續(xù)訪問未被訪問的結(jié)點

for(i=0;ivexnum;i++){

if(visit[i]==0)

DFS(G,i,visit);} cout<front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL){

int e=0;

DeQueue(Q,&e);

cout<adjlists[e].vertex<<“ ”;

visit[e]=1;

edgenode* p=new edgenode;

p=G->adjlists[e].edgelink;

if(p)

{

int m=p->endver;

if(m==0)

{

EnQueue(Q,m);

while(visit[m]==0)

{

p=p->edgenext;

if(p==NULL)

break;

m=p->endver;

EnQueue(Q,m);

}

}

}

} } void BFStraversal(Graph *G,char c){ cout<<“該圖的廣度優(yōu)先遍歷結(jié)果為:”<vexnum;i++){

visited[i]=0;} int m;for(i=0;ivexnum;i++){

if(G->adjlists[i].vertex==c)

{

m=i;

BFS(G,i,visited);

break;

} } //繼續(xù)訪問未被訪問的結(jié)點

for(i=0;ivexnum;i++){

if(visited[i]==0)

BFS(G,i,visited);} cout<>ch;DFStraversal(G,ch);BFStraversal(G,ch);}

四、實驗結(jié)果及分析

五、實驗總結(jié)

本次試驗采用的是鄰接表的方式實現(xiàn)圖的深度優(yōu)先遍歷和。對于深度優(yōu)先遍歷，主要是采用遞歸的方式。試驗本身問題不是太大，但要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數(shù)據(jù)的輸入有問題，結(jié)果當然也就不可能正確了。只有正確的輸入數(shù)據(jù)，建立圖，才能得出正確的遍歷結(jié)果。

第二篇：《數(shù)據(jù)結(jié)構(gòu)》上機作業(yè)——實驗報告(六)

“計算機軟件技術(shù)基礎(chǔ)”課程實驗報告

（六）實驗名稱：數(shù)據(jù)庫及SQL語言

班級_______ 姓名__________ 學號______實驗日期：

實驗機時：3 學時實驗成績：

-----------------

一.實驗目的：

1、學習數(shù)據(jù)庫設(shè)計的一般過程及相關(guān)技術(shù)；

2、學習access數(shù)據(jù)庫管理系統(tǒng)；

3、掌握數(shù)據(jù)庫的輸入、查詢、更新操作。

二.實驗內(nèi)容：

1、需求陳述：某校圖書館要建立一個圖書數(shù)據(jù)管理系統(tǒng)。該圖書館的圖書（書名、分類號、作者、出版社）存放在不同的借閱室（室名），讀者（姓名、系名、類別）在書架上找到所需圖書后，可以到服務臺辦理借閱（借閱時間）。

設(shè)計要求：

? 分析需求，建立數(shù)據(jù)庫的概念模型；

? 將概念模型轉(zhuǎn)換為關(guān)系模型（注意：是否需要作規(guī)范化處理）； ? 寫出創(chuàng)建基本表的SQL語句；

? 寫出以下查詢要求的SQL語句：

（1）所有“高等數(shù)學習題集”書的信息；

（2）讀者“李林”借了什么書？

（3）“社會學原理”在哪個借閱室？

2、在access數(shù)據(jù)庫管理系統(tǒng)中建立所設(shè)計的關(guān)系表；

3、向各表中輸入一組實驗數(shù)據(jù)（元組）（注意：關(guān)系完整性）；

4、對數(shù)據(jù)庫進行查詢。

三.實驗結(jié)果：

1、實體-關(guān)系圖；

2、數(shù)據(jù)庫表；

3、創(chuàng)建基本表的語句；

4、查詢語句。

第三篇：《數(shù)據(jù)結(jié)構(gòu)》上機作業(yè)——實驗報告(五)[推薦]

“計算機軟件技術(shù)基礎(chǔ)”課程實驗報告

（五）實驗名稱：排序算法

班級_______ 姓名__________ 學號______實驗日期：

實驗機時：3 學時實驗成績：

-----------------

一.實驗目的：

1、掌握主要排序算法的思想和實現(xiàn)技術(shù)。

二.實驗內(nèi)容：

1、設(shè)計一程序，要求：輸入學生“軟件技術(shù)基礎(chǔ)”課的成績（學

號、姓名、平均成績、總學分）；按總學分對學生數(shù)據(jù)進行排序。（要求：實現(xiàn)任選3種排序算法）

三.程序：

1、程序規(guī)范（輸入數(shù)據(jù)、功能、輸出數(shù)據(jù)）

2、設(shè)計分析（數(shù)據(jù)表示、算法）

3、C源代碼（電子版）

四.程序調(diào)試：

第四篇：數(shù)據(jù)結(jié)構(gòu)上機實驗報告

數(shù)據(jù)結(jié)構(gòu)實驗報告

課程 數(shù)據(jù)結(jié)構(gòu) _ 院 系

專業(yè)班級 實驗地點

姓 名 學 號

實驗時間 指導老師

數(shù)據(jù)結(jié)構(gòu)上機實驗報告1

一﹑實驗名稱：

實驗一——鏈表

二﹑實驗目的：

1.了解線性表的邏輯結(jié)構(gòu)特性；

2.熟悉鏈表的基本運算在順序存儲結(jié)構(gòu)上的實現(xiàn)，熟練掌握鏈式存儲結(jié)構(gòu)的描述方法；

3.掌握鏈表的基本操作（建表、插入、刪除等）4.掌握循環(huán)鏈表的概念，加深對鏈表的本質(zhì)的理解。5.掌握運用上機調(diào)試鏈表的基本方法

三﹑實驗內(nèi)容：

（1）（2）（3）（4）創(chuàng)建一個鏈表 在鏈表中插入元素 在鏈表中刪除一個元素 銷毀鏈表 四﹑實驗步驟與程序

#include #include typedef struct LNode {int data;struct LNode *next;}Lnode, *LinkList;//假設(shè)下面的鏈表均為帶頭結(jié)點。void CreatLinkList(LinkList &L,int j){//建立一個鏈表L,數(shù)據(jù)為整數(shù)，數(shù)據(jù)由鍵盤隨機輸入。

LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L;

cout<<“請輸入一個鏈表：”<

for(int i=0;i

{

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

cin>>p->data;

p->next=q->next;

q->next=p;

q=p;

} } int PrintLinkList(LinkList &L){//輸出鏈表L的數(shù)據(jù)元素

LinkList p;

} void LinkListLengh(LinkList &L){//計算鏈表L的數(shù)據(jù)元素個數(shù)。int i=0;p=L->next;if(L->next==NULL){

} cout<<“鏈表的數(shù)據(jù)元素為:”;while(p)

{

cout<

data<<“ ”;

p=p->next;} cout<<“鏈表沒有元素!”<

} LinkList p;p=L->next;while(p){

i++;

p=p->next;

} cout<<“鏈表的數(shù)據(jù)元素個數(shù)為:”<

LinkList p,s;int j=0;p=L;

while(p&&j

} if(!p||j>i-1){ p=p->next;++j;

}

} cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//刪除鏈表L的第I個數(shù)據(jù)元素。

LinkList p,q;int j=0;p=L;while(p->next&&j

} if(!(p->next)||j>i-1){ p=p->next;++j;

}

} cout<<“刪除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//銷毀鏈表L。

LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q;

free(p);} p=q;

free(L);

cout<<“鏈表已經(jīng)被銷毀!”<

LinkList L;

int i,j,x;cout<<“第一次數(shù)據(jù)結(jié)構(gòu)上機實驗—鏈表”<>j;

CreatLinkList(L,j);

LinkListLengh(L);

PrintLinkList(L);

cout<<“在第幾個元素前插入:”;cin>>i;cout<<“輸入插入的元素:”;cin>>x;

InsertLinkList(L,i,x);

LinkListLengh(L);

PrintLinkList(L);

cout<<“輸入刪除元素的位置:”;cin>>i;

DeleteLinkList(L,i);

LinkListLengh(L);

PrintLinkList(L);

cout<<“銷毀程序后為:”<

DestroyLinkList(L);} 五﹑實驗結(jié)果

六﹑實驗心得體會：

鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動態(tài)地進行存儲分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表中每一個元素稱為“結(jié)點”，每個結(jié)點都應包括兩個部分：一為用戶需要用的實際數(shù)據(jù)，二為下一個結(jié)點的地址。

實驗的程序設(shè)計規(guī)劃（實現(xiàn)的功能、分幾個模塊、子函數(shù)）（1）編寫鏈表創(chuàng)建子函數(shù)void CreatLinkList(L,j)（2）編寫鏈表插入子函數(shù) int InsertLinkList(LinkList &L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList &L)（4）編寫鏈表刪除子函數(shù) int DeleteLinkList(LinkList &L,int i)（5）編寫鏈表銷毀子函數(shù)void DestroyLinkList(LinkList &L)（6）編寫主函數(shù)Main()，通過功能菜單調(diào)用子函數(shù)（7）編譯調(diào)試程序

經(jīng)過多次的調(diào)試，修改，實驗結(jié)果終于正確了，在這個過程中，經(jīng)歷了不知道怎么進行聲明區(qū)的編寫如包含文件，宏定義，函數(shù)聲明，全局變量聲明，結(jié)構(gòu)體等的定義等的結(jié)合，到學會了使用先把程序主要規(guī)劃為四個部分來寫就簡單多了，第一，定義；第二，寫所要調(diào)用的子函數(shù)；第三，寫主函數(shù)，調(diào)用子函數(shù)；第四就是程序的編譯與調(diào)試，修改。數(shù)據(jù)結(jié)構(gòu)實驗需要我們對每個程序的算法有深刻的理解，才能應用到實際中去，因此我們需要在做實驗之前要熟悉實驗的內(nèi)容，且先把所要實驗的程序?qū)懗鰜?，在實驗中就可以查找錯誤并加以改正，這是一個成長的過程。

數(shù)據(jù)結(jié)構(gòu)上機實驗報告一﹑實驗名稱：

實驗二—隊列

二﹑實驗目的： 1.掌握隊列這種抽象數(shù)據(jù)類型的特點, 掌握棧與隊列在實際問題中的應用和基本編程技巧,并能在相應的問題中選用它;2.熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別是隊滿和隊空的描述方法；

3．掌握棧與隊列的數(shù)據(jù)類型描述及特點；

4.掌握棧的順序和鏈式存儲存表示與基本算法的實現(xiàn)； 5.掌握隊列的鏈式存儲表示與基本操作算法實現(xiàn);6.按照實驗題目要求，獨立完成實際程序的編寫編寫、調(diào)試和運行，并通過用例數(shù)據(jù)的運行過程抓獲相關(guān)屏面驗證程序設(shè)計的正確性； 7.認真書寫實驗報告，并按時提交。

三﹑實驗內(nèi)容：

對順序循環(huán)隊列，常規(guī)的設(shè)計方法是使用対尾指針和對頭指針，對尾指針用于指示當前的対尾位置下標，對頭指針用于指示當前的対頭位置下標?，F(xiàn)要求：

（1）掌握棧和隊列的特點，即后進先出和先進先出的原則。（2）設(shè)計一個使用對頭指針和計數(shù)器的順序循環(huán)隊列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空；

（3）編寫主函數(shù)進行測試。

四﹑實驗步驟與程序

#include #include #include

#define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){

} Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){

} void EnQueue(LinkQueue &Q,int e){

} int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“該鏈隊為空:”);else printf(“該鏈隊不為空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入隊成功”,e);

} if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p;

return OK;void DeQueue(LinkQueue &Q){

} void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“隊首元素刪除成功”);

} if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;printf(“隊首元素為:%d”,p->data);void OutQueue(LinkQueue &Q){

} void LengthQueue(LinkQueue &Q){

int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;while(p!=Q.rear->next){

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

} printf(“該隊列的長度為:%d”,f);else {

} p=Q.front->next;while(p!=Q.rear->next){

} printf(“該隊列的長度為:%d”,f);p=p->next;f++;void main(){

system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************鏈隊列功能菜單***********************n”);printf(“1:初始化鏈隊列，2:判斷鏈隊列是否為空, 3:進入隊列，4:取出隊首元素n”);printf(“5:輸出該隊列的所有元素,6:輸出該隊列的長度，7:結(jié)束程序，8:清屏n”);

while(flag){

printf(“n請輸入操作符:”);scanf(“%d”,&i);switch(i){ case 1:

int e,n,k;printf(“請輸入隊列的長度:”);scanf(“%d”,&n);printf(“請輸入隊列的元素:”);for(e=1;e<=n;e++){

} printf(“初始化鏈隊成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q);

break;case 3:

int j;printf(“請輸入要進入隊列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5:

printf(“該隊列的元素為:”);OutQueue(Q);break;

case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break;

} } 五﹑實驗結(jié)果

六﹑實驗心得體會：

程序主要構(gòu)造了主函數(shù)main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等調(diào)用函數(shù)，實現(xiàn)了隊列的創(chuàng)立，隊列是否為空的判斷，入隊和出隊等功能。

通過此次實驗，加深了對隊列的存儲結(jié)構(gòu)的了解，同時也對程序設(shè)計能力有了提高，加深了對隊列先進先出性質(zhì)的理解，它允許在表的一端進行插入，在另一端刪除元素，這和我們?nèi)粘Ｉ钪械呐抨犑且恢碌?，最早進入隊列的元素最早離開。我們往往寫不出程序，這其中的原因我覺得是對程序的結(jié)構(gòu)不是很了解，對實驗的內(nèi)容也不熟練的結(jié)果，數(shù)據(jù)結(jié)構(gòu)給我們許多程序的算法和模型，對我們寫程序的思維有很大的鍛煉，我們應珍惜每次上機實驗的機會去實踐課堂上所學的東西并從中發(fā)現(xiàn)問題，從而達到提升寫程序的能力。

數(shù)據(jù)結(jié)構(gòu)上機實驗報告一﹑實驗名稱：

實驗三—二叉樹的遍歷

二﹑實驗目的：

1、熟悉二叉樹的結(jié)構(gòu)特性，了解相應的證明方法；

2、掌握二叉樹的生成，掌握二叉樹的定義和存儲表示，學會建立一棵特定二叉樹的方法；

3、理解二叉樹的三種遍歷方法：先序遍歷、中序遍歷和后序遍歷；

4、學會編寫實現(xiàn)樹的各種操作的算法。

二、實驗內(nèi)容：

1、使用類定義實現(xiàn)二叉樹，補充完整所缺的函數(shù)，并實現(xiàn)創(chuàng)建和遍歷二叉樹的基本操作；

2、編程實現(xiàn)在二叉鏈表這種存儲方式下，實現(xiàn)二叉的遍歷，可采用遞歸或者非遞歸實現(xiàn)，遍歷算法為在先序、中序和后序遍歷算法。

三、實驗步驟與程序：

#include #include #include typedef struct BiTNode { char data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;//定義結(jié)點類型 BiTree CreateBiTree()//創(chuàng)建樹 { char p;BiTree T;scanf(“%c”,&p);if(p==' ')T=NULL;else { T=(BiTNode *)malloc(sizeof(BiTNode));//為結(jié)點開辟空間 T->data=p;T->lchild=CreateBiTree();T->rchild=CreateBiTree();} return(T);}

void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函數(shù) {

printf(“------------二叉樹的遍歷-------------n”);printf(“請輸入要遍歷的數(shù)：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍歷:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍歷:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍歷:”);printf(“n”);PostOrder(Ta);} 五﹑實驗結(jié)果

六﹑實驗心得體會：

實驗的程序設(shè)計規(guī)劃（實現(xiàn)的功能、分幾個模塊、子函數(shù)）（1）先序遍歷遞歸算法函數(shù)：void PreOrder(BiTree T)（2）中序遍歷遞歸算法函數(shù)：void InOrder(BiTree T)（3）后續(xù)遍歷遞歸算法函數(shù)：void PostOrder(BiTree T)（4）主函數(shù)的實現(xiàn)：void main()

在實驗前我認真閱讀關(guān)于二叉樹的實現(xiàn)的內(nèi)容，為編程實現(xiàn)第一步，本次實驗通過按上述的實驗步驟一步步實現(xiàn)的，實驗過程中出現(xiàn)了一些錯誤，經(jīng)過一步步的調(diào)試，修改錯誤，得到了二叉樹的遍歷用遞歸運算的方法的程序。通過這個實驗，我體會到了理解數(shù)據(jù)結(jié)構(gòu)的重要性，這有真正理解了定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來不是很復雜，這使我更進一步理解了函數(shù)遞歸調(diào)用并得到靈活運用；在實現(xiàn)算法上，從算法的效率看，遞歸方法書寫形式較為簡潔，更為直觀，一般具有較好的空間效率。

總之，不管做什么實驗，我們在做實驗前都要先預習，對所做的實驗有較深的理解，在做實驗的時候需要很嚴謹，仔細的查找錯誤，從而能在實驗中收獲知識，提升自己。

數(shù)據(jù)結(jié)構(gòu)上機實驗報告4 一﹑實驗名稱：

實驗四—查找

二﹑實驗目的：

1、熟悉掌握順序表的查找方法；

2、熟練掌握二叉排序樹的構(gòu)造方法和查找算法

3、掌握描述查找過程的判定樹的構(gòu)造方法，以及按照定義計算各種查找方法在等概率情況下查找成功時的平均查找長度；

4、學會定義線性表的儲存類型，實現(xiàn)C++程序的基本結(jié)構(gòu)對線性表的一些基本操作和具體的函數(shù)定義；

5、掌握順序表的基本操作，實現(xiàn)順序表的查找的等基本運算；

6、掌握對于多函數(shù)程序的輸入，編輯，調(diào)試和運算過程。

二、實驗內(nèi)容：

1、實現(xiàn)順序表的查找算法

2、關(guān)于衡量查找的主要操作—查找的查找平均效率的平均長度的討論。

三、實驗步驟與程序：

#include #define MAX_SIZE 100 typedef struct{ int key;}element;

element list[MAX_SIZE];

int seqsearch(element list[],int searchnum,int num);int main(){

int i,num,searchnum,k;

printf(“---------------數(shù)據(jù)結(jié)構(gòu)查找實驗-------------n”);printf(“請輸入數(shù)據(jù)元素的個數(shù)：”);scanf(“%d”,&num);printf(“請輸入數(shù)據(jù)的元素：n”);for(i=0;i

printf(“請輸入要查詢的數(shù)據(jù)元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查詢元素的下標為：”);printf(“%dn”,k);} else printf(“查詢元素不存在。n”);} return 0;}

int seqsearch(element list[],int searchnum,int num){ int j;

list[num].key=searchnum;

for(j=0;list[j].key!=searchnum;j++);return j

六﹑實驗心得體會：

實驗的程序設(shè)計規(guī)劃為先寫一個主函數(shù)int main()，再寫一個查找的子函數(shù)int seqsearch(element list[],int searchnum,int num)，主函數(shù)通過調(diào)用子函數(shù)的方法實現(xiàn)程序的設(shè)計。

所謂“查找”即為在一個眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄），通過本次實驗，我更進一步的了解數(shù)據(jù)結(jié)構(gòu)程序?qū)嶒炘O(shè)計實現(xiàn)算法的基本模型，和算法實現(xiàn)等基本內(nèi)容，學會了順序表的查找方法。

數(shù)據(jù)結(jié)構(gòu)上機實驗報告5 一﹑實驗名稱：

實驗五—內(nèi)部排序

二﹑實驗目的：

1、通過實現(xiàn)下述實驗內(nèi)容，學習、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況，并加以靈活應用。

2、掌握各種排序時間復雜度的分析方法。

二、實驗內(nèi)容：

1、插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。

2、快速排序：首先選擇一個基準，將記錄分割為兩部分，左支小于或等于基準，右支則大于基準，然后對兩部分重復上述過程，直至整個序列排序完成。

3、討論各種內(nèi)部排序方法的基本思路，算法特點，排序過程及它們的時間復雜度的分析。

三、實驗步驟與程序：

#include void main(){

} int x;void charu();void kuaisu();printf(“----------內(nèi)部排序---------n”);printf(“

1、插入排序：n”);printf(“

2、選擇排序：n”);printf(“請根據(jù)序號選擇：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m;

printf(“插入排序n”);

printf(“請輸入個您想排序的數(shù)據(jù):n”);

for(i=0;i<7;i++)scanf(“%d”,&a[i]);

for(j=1;j<7;j++)

{ m=a[j];

for(i=j-1;i>=0;i--)

{

if(a[i]

break;

else a[i+1]=a[i];

}

a[i+1]=m;

}

printf(“排序成功:”);

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

printf(“ %d”,a[i]);

printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key;

key=L[first];

while(left

{ while((left=key))

right--;

if(left

L[left++]=L[right];

while((left

left++;

if(left

L[left]=key;

return left;

}

quick_sort(int L[],int first,int end)

{ int split;

if(end>first)

{ split=quick(first,end,L);

quick_sort(L,first,split-1);

quick_sort(L,split+1,end);

}

} void kuaisu(){

int a[7],i;

printf(“快速排序n”);

printf(“請輸入個您想排序的數(shù)據(jù):n”);

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

scanf(“%d”,&a[i]);

quick_sort(a,0,9);

printf(“排序成功:”);

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

printf(“ %d”,a[i]);

printf(“n”);} 五﹑實驗結(jié)果：

六﹑實驗心得體會：

排序的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，從新排成按關(guān)鍵字有序的序列；直接插入排序的穩(wěn)定性比快速排序高，且算法較簡單。本次實驗運用到的是插入排序和快速排序。

第五篇：數(shù)據(jù)結(jié)構(gòu)上機實驗報告

實習報告

題 目 : 實現(xiàn)一個約瑟夫環(huán)程序

班級：031021姓名：王帥學號：03102076

一、需求分析

1． 本演示程序中，利用單向循環(huán)鏈表存儲結(jié)構(gòu)存儲約瑟夫環(huán)數(shù)據(jù)（即n個人的編號和密碼）。

2． 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運算結(jié)果顯示在其后。

3． 程序執(zhí)行的命令包括：

1)構(gòu)造單向循環(huán)鏈表；2）進行數(shù)值的輸入，并作判斷分析；3）約瑟夫算法的實現(xiàn)與結(jié)果輸出；4）結(jié)束。

4． 測試數(shù)據(jù)

m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序為6，1，4，7，2，1，3，5）。

二、概要設(shè)計

1．單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：

ADT List｛

數(shù)據(jù)對象：D=｛ai | ai?正整數(shù)，I=1，2，......，n,n≥0｝數(shù)據(jù)關(guān)系：R1=｛< ai-1，ai > |，ai-1，ai?D,I=1，2，......，n｝基本操作：

Init List(&L)

操作結(jié)果：構(gòu)造一個空的線性表L。

List Insert(&L,i,e)

初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L長度加1。List Delete(&L,i,&e)

初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個元素，并用e返回其值，L長度減1。

2． 程序包含四個模塊：

1）主程序模塊：

void main()

{

初始化；

for（;;）

{}

while（命令=開始）

{

接受命令；

處理命令；

}

for（;;）

{ }

}

2）有序表單元模塊——實現(xiàn)有序表的抽象數(shù)據(jù)類型；

3）節(jié)點結(jié)構(gòu)單元模塊——定義有序表的節(jié)點結(jié)構(gòu)；

4）數(shù)據(jù)輸入分析模塊——判斷輸入數(shù)據(jù)正確有效；

各模塊之間的調(diào)用關(guān)系如下：

主程序模塊

↓

有序表結(jié)構(gòu)模塊

↓

節(jié)點結(jié)構(gòu)單元模塊

↓

數(shù)據(jù)輸入分析模塊

三、詳細設(shè)計

1、結(jié)點類型，指針類型

TypedefstructLNode{

int code,date;//code 為人所在位置 date為人持有的密碼 struct LNode *next;

};// 結(jié)點類型，指針類型

2、構(gòu)造單向循環(huán)鏈表

struct LNode *p,*head,*q;//定義頭節(jié)點，和指針

for(i=2;i<=n;i++)

{

struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配

新結(jié)點空間

s->code=i;

input(s->date);

p->next=s;

p=p->next;

}

p->next=head;//根據(jù)輸入的人數(shù)，進行單項循環(huán)鏈表的創(chuàng)建，p指向最后一個結(jié)點，并與頭節(jié)點鏈接，形成單項循環(huán)鏈表

3、約瑟夫環(huán)的程序?qū)崿F(xiàn)部分

while(n!=1)//判斷輸入人數(shù)，如為1則直接輸出結(jié)果，不循環(huán)

{

for(i=1，m=m%n;i

{

p=p->next;

}

q=p->next;//找到要刪除節(jié)點

p->next=q->next;//找到要刪除節(jié)點的后繼，并連接新環(huán)m=q->date;//找到下一個密碼

printf(“%d”,q->code);

free(q);//釋放已刪除節(jié)點空間

n--;//鏈表長度減一

}

printf(“%d”,p->code);//約瑟夫環(huán)的結(jié)果輸出

4、其他函數(shù)代碼

數(shù)值的輸入限制

int input()

{

int y,k,z=0;

char c;//元素類型

char a[4];//數(shù)組初始化

if(!z)//輸入判斷，確定位數(shù)字或控制字符且位置和密碼不為零 {

for(y=0;y<4;y++)

{

c=getch();

if(c>=48&&c<=57)//確定為輸入數(shù)字

{a[y]=c;

putch(c);

}

else

{

y--;

if(c=='r')//確定輸入為控制字符 即回車或者刪除

break;

else

if(c==8)

{a[y]='n';

y--;}

continue;

}

}

k=atoi(a);//確定最終輸入數(shù)字的值

printf(“n”);

z=k;

if(z==0)

printf(“ERROR!The number couldn't be 0!n”);// 輸入為零，重新輸入 }

return(k);//數(shù)值的返回

5、函數(shù)的調(diào)用關(guān)系圖反映程序?qū)哟谓Y(jié)構(gòu)

Main→input

四、調(diào)試分析

1、早期程序只寫了約瑟夫環(huán)的實現(xiàn)部分，沒有對輸入數(shù)據(jù)進行篩選，調(diào)試的時候會經(jīng)常出錯。比如是輸入字母，或者輸入0，大于32767溢出；

2、早期的循環(huán)過程中沒有進行優(yōu)化，導致循環(huán)次數(shù)過多，浪費時間；

3、為了輸出時美觀，分別在input和main函數(shù)主體內(nèi)做了兩次，輸入非零的判斷，浪費了資源；

4、算法的時空分析

為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數(shù)字，但是做的是do……while循環(huán)，復雜度為o（1）;

當n大于1時：

在數(shù)據(jù)輸入中，鏈表的創(chuàng)建是for循環(huán)，時間復雜度為o（n-1）

在約瑟夫環(huán)實現(xiàn)程序中，為for循環(huán)。時間復雜度為o（m%n-1）

當n=1時，復雜度為o（1）。

五、用戶手冊

用戶根據(jù)提示，先輸入起始密碼m，然后輸入人數(shù)n，再根據(jù)人數(shù)，分別輸入每個人的密碼date，數(shù)值均不能為0，否則會提示重新輸入，輸入為字母則自動丟棄，輸入錯誤可用刪除鍵進行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數(shù)字大于9999，則第五位自動轉(zhuǎn)換為下一個數(shù)字的起始位，依此類推）。

當n個數(shù)字全部輸入完畢，則自動顯示結(jié)果，按任意鍵則退出本程序。

六、測試結(jié)果

第一組：m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，出列順序為6，1，4，7，2，1，3，5。

第二組： m 的初值為30；n=8，7個人的密碼依次為：5，1，6，9，4，7，2，3，出列順序為6，5，2，3，7，1，4，8。

第三組 : m 的初值為15；n=6，7個人的密碼依次為：5，3，4，7，6，9，出列順序為3，1，2，6，4，5。

七、附錄

源程序頭文件名清單：

#include “malloc.h”//內(nèi)存空間分配頭文件

#include “stdio.h”//輸入輸出函數(shù)頭文件

#include “stdlib.h”//input函數(shù)中字符串轉(zhuǎn)短整形函數(shù)的頭文件 #include “conio.h”//最后顯示結(jié)果、清屏函數(shù)頭文件