第一篇：數據結構實驗報告

浙江師范大學

實 驗 報 告

學 院： 數理與信息工程學院 專 業： 計算機科學與技術 姓 名： 楊富生 學 號： 201531910137 課程名稱： 數據結構 指導教師： 鐘發榮 實驗時間： 2016-06-15

2016年6月15日

實驗一

1.實驗要求

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

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

2.實驗內容

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

#include typedef int elemtype;#define maxsize 10 int del(int A[],int n,elemtype x,elemtype y){ int i=0,k=0;while(i=x&&A[i]<=y)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;i

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

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

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

for(i=0;i

”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 生成兩個多項式PA和PB，求他們的和，輸出“和多項式”。typedef struct node {int exp;float coef;struct node *next;}polynode;polynode *polyadd(polynode *pa,polynode *pb){ polynode *p,*q,*pre,*r;float x;p=pa->next;q=pb->next;pre=pa;while((p!=NULL)&&(q!=NULL))

if(p->exp>q->exp)

{

r=q->next;

q->next=p;

pre->next=q;

pre=q;

q=r;

}

}

else if(p->exp==q->exp){

x=p->coef+q->coef;

if(x!=0)

{p->coef=x;

s=p;

}

else

{pre->next=p->next;

free(p);

}

p=pre->next;

r=p;

q=q->next;

free(r);} else

if(p->expexp)

{

pre=p;

p=p->next;

}

if(q!=NULL)

pre->next=q;

free(pb);2.4 設計一個統計選票的算法，輸出每個候選人的得票結果。

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

a[i]=0;nodetype *head;head=create();sat(head,a);printf(“候選人:”);for(i=1;i<=N;i++)printf(“%3d”,i);printf(“n得票數n”);for(i=1;i<=N;i++)

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

3.實驗心得體會

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

實驗二

1.實驗要求

1.1 了解棧和隊列的特性，以便靈活運用。1.2 熟練掌握棧和有關隊列的各種操作和應用。

2.實驗內容

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;

實驗三

1.實驗要求

1.1 掌握二叉樹，二叉樹排序數的概念和存儲方法。1.2 掌握二叉樹的遍歷算法。

1.3 熟練掌握編寫實現樹的各種運算的算法。2.實驗內容

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 編寫遞歸算法，求二叉樹中以元素值為X的結點為根的子數的深度。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);9 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));} 3.實驗心得體會

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

#include #include #define len sizeof(struct node)#define null 0 typedef struct node{ int data;int ltag,rtag;struct node *lchild,*rchild;}Treenode;Treenode *pre=null;Treenode *creat(){ Treenode *bt;int n;scanf(“%d”,&n);if(n!=0){

bt=(Treenode *)malloc(len);

bt->data=n;bt->ltag=0;bt->rtag=0;

bt->lchild=creat();

bt->rchild=creat();} else bt=null;return bt;} void preorder1(Treenode *t){ if(t!=null){

printf(“%4d”,t->data);

preorder1(t->lchild);

preorder1(t->rchild);} } void preorder2(Treenode *t){ if(t!=null){

preorder2(t->lchild);

printf(“%4d”,t->data);

preorder2(t->rchild);} } void preorder3(Treenode *t){ if(t!=null){

preorder3(t->lchild);

preorder3(t->rchild);

printf(“%4d”,t->data);} } void InThread(Treenode *T){ Treenode *p;p=T;if(p){ InThread(p->lchild);if(!p->lchild){ p->ltag=1;p->lchild=pre;} if(!pre->rchild){ pre->rtag=1;pre->rchild=p;} pre=p;InThread(p->rchild);} } Treenode *inorderthreading(Treenode *T){ Treenode *Thre;Thre=(Treenode *)malloc(sizeof(Treenode)Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->rtag=1;pre->rchild=Thre;Thre->rchild=pre;return Thre;} void InThrTravel(Treenode *Thre){ Treenode *p;p=Thre->lchild;while(p!=Thre){ while(p->ltag==0)p=p->lchild;printf(“%4d”,p->data);while(p->rtag==1 && p->rchild!=Thre){ p=p->rchild;printf(“%4d”,p->data);} p=p->rchild;}printf(“n”);} void main(){ Treenode *tree;int i;printf(“建立二叉樹:n”);tree=creat();printf(“請選擇遍歷二叉樹的方法:nn1.先根序遍歷.n2.中根序遍歷.n3.后根序遍歷.n”);scanf(“%d”,&i);while(i>3 && i<1){

scanf(“%d”,&i);} switch(i){ case 1:preorder1(tree);break;case 2:preorder2(tree);break;case 3:preorder3(tree);break;} printf(“n中根序線索遍歷:n”);tree=inorderthreading(tree);InThrTravel(tree)

實驗四

#include #include #define null 0 #define n 4 #define m 2*n-1 typedef struct { int weight;int parent,llink,rlink;}node;typedef struct { int start;char bits[n+1];}codetype;typedef struct { char c;codetype code;}element;node tree[m+1];void inithafumantree(node tree[]){ int i;for(i=0;i<=m;i++){

tree[i].parent=0;

tree[i].llink=0;

tree[i].rlink=0;} } void inputweight(node tree[]){ int i;printf(“請輸入各結點的權值:n”);for(i=1;i<=n;i++){

printf(“第%d個結點的權值:”,i);

scanf(“%d”,&tree[i].weight);} } void select(int pre,int *min1,int *min2){ int i;*min1=*min2 = 0;for(i=1;i= tree[i].weight){ *min2 = *min1;*min1 = i;} else if(tree[*min2].weight>tree[i].weight)*min2=i;} } } void sethuftree(node tree[m+1]){ int i,x1,x2;printf(“構造哈夫曼樹.nn”);inithafumantree(tree);inputweight(tree);for(i=n+1;i<=m;i++){

select(i-1,&x1,&x2);

tree[x1].parent=i;

tree[x2].parent=i;

tree[i].llink=x1;

tree[i].rlink=x2;

tree[i].weight=tree[x1].weight+tree[x2].weight;} void encode(node tree[],element table[]){ int i,s,f;codetype c;for(i=1;i<=n;i++){

table[i].c=tree[i].weight;

c.start=n+1;s=i;

while(f=tree[s].parent)

{ c.bits[--c.start]=(s==tree[f].llink)?'0':'1';s=f;}

table[i].code=c;} void main(){ int i;element table[n+1];sethuftree(tree);encode(tree,table);printf(“n輸出Huffman編碼n”);for(i=1;i<=n;i++){ printf(“n %c :”,table[i].c);puts(table[i].code.bits);} }

實驗五

#include #include #define MAX 1000 #define MAXN 100 typedef struct{ char vexs[MAXN];int edges[MAXN][MAXN];int n,e;}MGraph;void createmgraph(MGraph *g){ int i,j,k,w;char Node='a';printf(“nPlease input n:”);scanf(“%d”,&g->n);printf(“Please input e:”);scanf(“%d”,&g->e);for(j=0;jn;j++)g->vexs[j]=Node++;for(i=0;in;i++)

for(j=0;jn;j++)

if(i==j)g->edges[i][j]=0;

else g->edges[i][j]=MAX;

for(k=0;ke;k++){

printf(“Input i,j,w:(eg.0,1,5)n”);

scanf(“%d,%d,%d”,&i,&j,&w);

g->edges[i][j]=w;

printf(“nThe graph is: nn”);

printf(“t ”);

for(k=0;kn;k++){

printf(“%3c”,g->vexs[k]);

if(k==g->n-1)printf(“nn”);

}

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

printf(“t%c ”,g->vexs[i]);

for(j=0;jn;j++)

if(g->edges[i][j]==MAX)printf(“%3c”,MAX-923);

else printf(“%3d”,g->edges[i][j]);

printf(“n”);

} void main(){ MGraph *g;g=(MGraph *)malloc(sizeof(MGraph));createmgraph(g);getchar();}

實驗六

1.實驗要求

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

1.2 掌握遍歷圖的遞歸和非遞歸的算法。1.3 理解圖的有關算法。

2.實驗內容

2.1 寫出將一個無向圖的鄰接矩陣轉換成鄰接表的算法。void mattolist(int a[][],adjlist b[],int n)

{ for(i=0;i

for(i=0;i

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;

} }

2.2 以鄰接表作存儲結構，給出拓撲排序算法的實現。typedef struct vexnode { VertexType vertex;int in;ArecNodeTp * fristarc;}AdjList[vnum];typedef struct graph { AdjList adjlist;int vexnum,arcnum;}GraphTp;Top_Sort(GraphTp g){ LstackTp *p;int m,i,v;initStack(S);for(i=0;i

if(g.adjlist[i].in==0)/*if(w的入度==0)*/

push(S,&v);/*w入S棧*/

} }

m=0;whlie(!EmptyStack(S)){ Pop(S,&v)//S出棧->v

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的下一個鄰接點*/ } } if(m

實驗七

#include #include #define NULL 0 #define maxsize 100 typedef struct node { int data;struct node *left,*right;}dnode;int n=0;void sort(dnode *t,int c)//將c插入到二叉排序樹中 { dnode *p;if(c>=t->data)

if(t->right==NULL)

{ p=(dnode *)malloc(sizeof(dnode));

p->data=c;

p->left=NULL;p->right=NULL;

t->right=p;

}

else sort(t->right,c);if(cdata)

if(t->left==NULL)

{ p=(dnode *)malloc(sizeof(dnode));

p->data=c;p->left=NULL;p->right=NULL;t->left=p;

}

else sort(t->left,c)dnode *creat(){ dnode *ht;int x;ht=(dnode *)malloc(sizeof(dnode));printf(“創建二叉排序樹(以0結束輸入):”);scanf(“%d”,&x);ht->data=x;n++;ht->left=NULL;ht->right=NULL;scanf(“%d”,&x);while(x>0){

sort(ht,x);n++;

scanf(“%d”,&x);} return ht;} int find(dnode *b,int x,dnode *a[]){ dnode *stack[maxsize],*p;int top;a[1]=NULL;

if(b!=NULL){ top=1;stack[top]=b;while(top>0){ p=stack[top];top--;if(p->left->data==x || p->right->data==x)a[1]=p;if(p->data==x){a[0]=p;return 1;} if(p->right!=NULL){ top++;stack[top]=p->right;} if(p->left!=NULL){ top++;stack[top]=p->left;} } } a[0]=p;} dnode *delet(dnode *t){ dnode *p,*q,*s,*f,*a[2];int flag=0,x;p=(dnode *)malloc(sizeof(dnode));f=(dnode *)malloc(sizeof(dnode));printf(“請輸入要刪除的結點:”);scanf(“%d”,&x);find(t,x,a);p=a[0];f=a[1];if(p==NULL){printf(“NO FIND!n”);exit(0);} if(p->left==NULL)s=p->right;else if(t->right=NULL)s=p->left;else{ q=p;s=p->left;while(s->right!=NULL)

{q=s;s=s->right;}

if(q==p)q->left=s->left;

else q->right=s->left;p->data=s->data;free(s);flag=1;if(flag==0){ if(f==NULL)t=s;else if(f->left==p)f->left=s;

else f->right=s;} return t;} void inorder(dnode *t){ if(t!=NULL){ inorder(t->left);printf(“%4d”,t->data);inorder(t->right);} } void main(){ dnode *h;h=creat();printf(“中序遍歷二叉排序樹:”);inorder(h);printf(“n”);h=delet(h);

inorder(h);printf(“n”);}

實驗八

1.實驗要求

1.1 掌握順序查找、二分法查找、分塊查找和哈希表查找的算法。1.2 能運用線性表的查找方法解決實際問題。2.實驗內容

2.1 編寫一個算法，利用二分查找算法在一個有序表中插入一個元素X，并保持表的有序性。

#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<=m+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<=m;i++)

scanf(“%d”,data+i);return m;} /**********************************************************/ int search(int *data,int low,int high)/*遞歸查找插入位置*/ { int mid;if(low>high)return low;/*沒有找到插入數據，返回low*/ else{

mid=(low+high)/2;

if(*(data+mid)==*data)retun mid;/*找到插入數據，返回mid*/

else if(*(data+mid)<*data)

else if(*()data+mid)>*data)} 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);*(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

(p+k)->key=dat a[m*k];

(p+k)->addr=m*k;

for(j=m*k;j

if(data[j]>(p+k)->key)

(p+k)->key=data[j];/*塊的最大關鍵字*/ } return p;} int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分塊查找*/ { int low=0,high=m-1,mid,i;int b=n/m;/*每塊有b個元素*/ while(low<=high){/*塊間折半查找*/

mid=(low+high)/2;

if((list+mid)->key>=k)

high=mid+1;

else low=mid+1;} if(low

for(i=(list+low)->addr;i<=(list+low)->adder+b-1&&rectab[i]!=k;i++);

if(i<=(list+low)->addr+b-1)

return i;

else return-1;} 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));} 3.實驗心得體會

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

第二篇：數據結構實驗報告

注意：實驗結束后提交一份實驗報告電子文檔

電子文檔命名為“學號+姓名”，如：E01214058宋思怡

《數據結構》實驗報告

（一）學號：姓名：專業年級：

實驗名稱：線性表

實驗日期：2014年4月14日

實驗目的：

1、熟悉線性表的定義及其順序和鏈式存儲結構；

2、熟練掌握線性表在順序存儲結構上實現基本操作的方法；

3、熟練掌握在各種鏈表結構中實現線性表基本操作的方法；

4、掌握用 C/C++語言調試程序的基本方法。

實驗內容：

一、編寫程序實現順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：

（1）初始化順序表L；

（2）依次在L尾部插入元素-1,21,13,24,8；

（3）輸出順序表L；

（4）輸出順序表L長度；

（5）判斷順序表L是否為空；

（6）輸出順序表L的第3個元素；

（7）輸出元素24的位置；

（8）在L的第4個元素前插入元素0；

（9）輸出順序表L；

（10）刪除L的第5個元素；

（11）輸出順序表L。

源代碼

調試分析（給出運行結果界面）

二、編寫程序實現單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：

????

????

小結或討論:

（1）實驗中遇到的問題和解決方法

（2）實驗中沒有解決的問題

（3）體會和提高

第三篇：數據結構實驗報告

南京信息工程大學實驗（實習）報告

實驗（實習）名稱數據結構實驗（實習）日期 2011-11-2得分指導教師周素萍

系公共管理系專業信息管理與信息系統年級10級班次1姓名常玲學號2010230700

3實驗一順序表的基本操作及C語言實現

【實驗目的】

1、順序表的基本操作及 C 語言實現

【實驗要求】

1、用 C 語言建立自己的線性表結構的程序庫，實現順序表的基本操作。

2、對線性表表示的集合，集合數據由用戶從鍵盤輸入（數據類型為整型），建立相應的順序表，且使得數據按從小到大的順序存放，將兩個集合的并的結果存儲在一個新的線性表集合中，并輸出。

【實驗內容】

1、根據教材定義的順序表機構，用 C 語言實現順序表結構的創建、插入、刪除、查找等操作；

2、利用上述順序表操作實現如下程序：建立兩個順序表表示的集合（集合中無重

復的元素），并求這樣的兩個集合的并。

【實驗結果】

[實驗數據、結果、遇到的問題及解決]

一． Status InsertOrderList(SqList &va,ElemType x)

{

}

二． Status DeleteK(SqList &a,int i,int k)

{//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x

}

//注意i的編號從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK;

三．// 將合并逆置后的結果放在C表中，并刪除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅指針 // 保存pb的前驅指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data

data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當前最小結點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結點插入A表表頭 A->next=qa;

}

} pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;

順序表就是把線性表的元素存儲在數組中，元素之間的關系直接通過相鄰元素的位置來表達。

優點：簡單，數據元素的提取速度快；

缺點：（1）靜態存儲，無法預知問題規模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n）

求兩個集合的并集

該算法是求兩個集合s1和s2的并集，并將結果存入s引用參數所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數集合中得到并集。

第四篇：數據結構實驗報告

數據結構實驗報告

一． 題目要求

1）編程實現二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷；

3）每次對樹的修改操作和遍歷操作的顯示結果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案

對于前三個題目要求，我們用一個程序實現代碼如下 #include #include #include #include “Stack.h”//棧的頭文件，沒有用上

typedefintElemType;

//數據類型 typedefint Status;

//返回值類型 //定義二叉樹結構 typedefstructBiTNode{ ElemType

data;

structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數

if(T==NULL){

T =(BiTree)malloc(sizeof(BiTNode));

T->data=key;

T->lChild=T->rChild=NULL;

return 1;} else if(keydata){ InsertBST(T->lChild,key);} else if(key>T->data){

InsertBST(T->rChild,key);} else

return 0;} BiTreeCreateBST(int a[],int n){//創建二叉樹函數 BiTreebst=NULL;inti=0;while(i

//數據域

InsertBST(bst,a[i]);

i++;} returnbst;} int Delete(BiTree&T)

{

BiTreeq,s;

} if(!(T)->rChild){ //右子樹為空重接它的左子樹

q=T;T=(T)->lChild;free(q);}else{

if(!(T)->lChild){ //若左子樹空則重新接它的右子樹

q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){

q=s;s=s->rChild;}

(T)->data=s->data;//s指向被刪除結點的前驅

if(q!=T)

q->rChild=s->lChild;

else

q->lChild=s->lChild;

free(s);} } return 1;

//刪除函數，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{

if(key==(T)->data)return Delete(T);

else{

if(key<(T)->data)

returnDeleteBST(T->lChild,key);

else

returnDeleteBST(T->rChild,key);

} } } intPosttreeDepth(BiTree T){//求深度

inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else

return 0;

} void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i

”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){

while(NULL!=p)

{

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

stack[num++]=p;

p=p->lChild;

}

num--;

p=stack[num];

p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root;

} intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){

stack[num++]=p;

p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL;

while(NULL!=p||num>0){

while(NULL!=p)

{

stack[num++]=p;

p=p->lChild;

}

p=stack[num-1];

if(NULL==p->rChild||have_visited==p->rChild)

{

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

num--;

have_visited=p;

p=NULL;

}

else

{

p=p->rChild;

} } printf(“n”);}

int main(){//主函數

printf(“

---------------------二叉排序樹的實現-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節點個數:”);scanf(“%d”,&num);printf(“依次輸入這些整數（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i

scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“

***********************按提示輸入操作符************************:”);printf(“n”);printf(“

1:插入節點

2:刪除節點

3:打印二叉樹

4:非遞歸遍歷二叉樹

5:退出”);scanf(“%d”,&j);

switch(j){

case 1:

printf(“輸入要插入的節點:”);

scanf(“%d”,&T);

InsertBST(bst,T);

printf(“插入成功!”);printf(“樹狀圖為:n”);

printtree(bst,layer);

break;

case 2:

}

printf(“輸入要刪除的節點”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4:

printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst);

printf(“后序遍歷:n”);

PostOrderNoRec(bst);

printf(“樹狀圖為:n”);

printtree(bst,layer);

break;case 5:

printf(“程序執行完畢!”);

return 0;} goto loop;} return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結構變為 typedefintElemType;

//數據類型 typedefstring SlemType;

typedefint Status;

//返回值類型 //定義二叉樹結構 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no;

//數據域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數不是key,而是另外三個

intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數

if(T==NULL){

T =(BiTree)malloc(sizeof(BiTNode));

T->no=no;T->name=name;T->score=score;

T->lChild=T->rChild=NULL;

return 1;} else if(nono){ InsertBST(T->lChild,no,score,name);} else if(key>T->data){

InsertBST(T->rChild,no,score,name);} else

return 0;} 其他含參函數也類似 即可完成50個信息存儲

用數組存儲50個信息，查看以往代碼

#include #include using namespace std;class student{ private: intnum;string name;int ob1;int ob2;intara;public: void set(inta,stringb,intc,int d);void show();int average();};void student ::set(inta,stringb,intc,int d){ num=a;name=b;ob1=c;ob2=d;ara=(c+d)/2;} void student::show(){ cout<<“學號：”<

int main(){ cout<<“ 歡迎來到學生管理系統”<>numlock;switch(numlock){ case 0: cout<<“輸入想查詢的學號”<>i;if(i==j){ cout<<“該學號信息已被刪除”<>j;delete[j]ptr;cout<<“刪除成功”<>k;if(k!=j){

cout<<“該學號信息已經存在，添加失敗”<

break;} cout<<“重新輸入添加的學號”<>q;cout<<“輸入姓名”<>w;cout<<“輸入科目一的成績”<>e;cout<<“輸入科目二的成績”<>r;ptr[k].set(q,w,e,r);break;case 3: for(m=1;m<20;m++){

for(int n=m+1;n<20;n++){

if(ptr[m].average()

student a;

a=ptr[m];

ptr[m]=ptr[n];

ptr[n]=a;

}}

ptr[m].show();} break;case 4: cout<<“謝謝使用”<

二叉排序樹儲存數據界面（儲存學生信息略）

創建二叉樹：

插入節點：

刪除節點：

非遞歸遍歷：

退出：

數組儲存學生信息界面

分析查找效率：

因為二叉樹查找要創建二叉樹，而數組查找只創建一個數組，二叉樹的創建時間比較長，所以對于數據量較少的情況下數組的查找效率比較高。但當數據量增加時，二叉樹的查找優勢就顯現出來。所以數據量越大的時候，二叉樹的查找效率越高。

四． 總結與改進

這個實驗工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進。

一開始打算用棧實現非遞歸，但是根據書里面的偽代碼發現部分是在C++編譯器里運行不了的（即使補充了頭文件和數據的定義），所以之后參考了網上的數組非遞歸，發現其功能和棧相似。

遞歸遍歷的實現比非遞歸的遍歷真的簡單很多。

開始時只看到前三問，所以沒有寫到儲存學生數據的代碼，里面還可以用clock（）函數加一個計算查找所要數據時間的代碼，讓二叉樹查找與數組查找到效率比較更加直觀。

第五篇：數據結構實驗報告

實驗報告4 排序

一、實驗目的

1、掌握常用的排序方法，并掌握用高級語言實現排序算法的方法。

2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用。

3、了解各種方法的排序過程及其依據的原則，并掌握各種排序方法的時間復雜度的分析方法。

二、實驗要求及內容

要求編寫的程序所能實現的功能包括：

1、從鍵盤輸入要排序的一組元素的總個數

2、從鍵盤依次輸入要排序的元素值

3、對輸入的元素進行快速排序

4、對輸入的元素進行折半插入排序

三、實驗代碼及相關注釋

#include using namespace std;#include “malloc.h”

typedef struct { int key;}RedType;

typedef struct { RedType r[100];int length;}SqList;

//1 快速排序的結構體

typedef struct {

int data[100];

int last;}Sequenlist;//2 折半插入排序的結構體

int Partition(SqList &L, int low, int high)

//1 尋找基準

{

L.r[0]=L.r[low];//子表的第一個記錄作基準對象

int pivotkey = L.r[low].key;//基準對象關鍵字 while(low

while(low= pivotkey)--high;

L.r[low] = L.r[high];//小于基準對象的移到區間的左側

while(low

L.r[high] = L.r[low];//大于基準對象的移到區間的右側 }

L.r[low] = L.r[0];return low;}

void QuickSort(SqList &L, int low, int high)

//1 快速排序 { //在序列low-high中遞歸地進行快速排序

if(low < high)

{

int pivotloc= Partition(L, low, high);

//尋找基準

QuickSort(L, low, pivotloc-1);//對左序列同樣遞歸處理

QuickSort(L, pivotloc+1, high);//對右序列同樣遞歸處理

} }

Sequenlist *Sqlset()

//2 輸入要折半插入排序的一組元素

{

Sequenlist *L;

int i;

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

L->last=0;

cout<<“請輸入要排序的所有元素的總個數：”;

cin>>i;

cout<

cout<<“請依次輸入所有元素的值：”;

if(i>0)

{

for(L->last=1;L->last<=i;L->last++)

cin>>L->data[L->last];

L->last--;

}

return(L);}

middlesort(Sequenlist *L)

//2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]data[mid])

high=mid-1;//插入點在前半區

else

low=mid+1;//插入點在后半區

}

for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0];//插入 } return 0;}

int main(){ gg: cout<<“請選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout<

if(m==1){ SqList L;int n;cout<<“請輸入要排序的所有元素的總個數：”;cin>>n;cout<

cin>>L.r[i].key;

} cout<

QuickSort(L,1,L.length);

for(int j=1;j<=L.length;j++)

{

cout<

}

cout<

cout<

}

if(m==2){

Sequenlist *L;

int i;

L=Sqlset();

cout<

middlesort(L);

cout<<“折半插入排序后為：”;

for(i=1;i<=L->last;i++)

{

cout<data[i]<<“ ”;

}

cout<

cout<

goto gg;}

if(m==3){

exit(0);

cout<

四、重要函數功能說明

1、Sequenlist *Sqlset()

輸入要折半插入排序的一組元素

2、int Partition(SqList &L, int low, int high)

尋找快速排序的基準

3、void QuickSort(SqList &L, int low, int high)

快速排序

4、middlesort(Sequenlist *L)

折半插入排序

五、程序運行結果

下圖僅為分別排序一次，可多次排序，后面有相關截圖：

六、實驗中遇到的問題、解決及體會

1、起初編寫快速排序的程序時，我是完全按照老師PPT上的算法敲上去的，然后建立了一個SqList的結構體，調試運行時出現錯誤，仔細查看才意識到Partition函數中L中應該包含元素key，而我建立結構體時沒有注意，然后我將key這個元素補充進去，繼續調試，又出現錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經寫了函數定義，為什么會這樣，當我又回過頭來閱讀程序時，我發現QuickSort函數中調用了Partition函數，但是我的Partition函數的定義在QuickSort函數的后面，于是我將Partition函數放到了QuickSort函數的前面，再次調試運行，就可以正常運行，得出結果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。

運行程序錯誤截圖：

2、本來我是編寫了兩個程序，分別實現快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現所需功能的前提下，多想問題，看是否能使程序更加實用簡便。

修改程序前兩個運行結果截圖

（兩個程序，調試運行兩次，每次只能進行一次排序）

1、快速排序程序運行結果截圖：

2、折半插入排序程序結果截圖：

程序重要模塊修改截圖：

修改程序后運行截圖：

（一個程序，調試運行一次，可多次進行不同序列的不同排序）