数据结构实验报告
本科实验报告
课程名称：
数据结构（C 语言版）
实验项目：
线性表、树、图、查找、内排序
实验地点：
明向校区实验楼 208
专业班级：
学号：
学生姓名：
指导教师：
杨永强
2019 年
1 月 10 日
实验名 称
实验一
线性表
实验目的和要求
本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。
实验内容
1．设顺序表 A 中的数据元素递增有序，试写一程序，将 x 插入到顺序表的适当位置上，使该表仍然有序。
2．用单链表 ha 存储多项式 A（x ）=a 0 +a 1 x 1 +a 2 x 2 +…+a n x n (其中 a I 为非零系数)，用单链表 hb 存储多项式 B（x ）=b 0 +b 1 x 1 +b 2 x 2 +…+b m x m (其中 b j 为非零系数)，要求计算 C（x ）= A（x ）+B（x ），结果存到单链表 hc 中。试写出程序。
主要仪器设备
台式或笔记本电脑 实验记录( ( 写出实验内容中 (1)(2) 的运行结果和程序代码 )( 可分栏或加页) )
1. #include <stdio.h>
#include <stdlib.h> #include <string.h>
#define OK 1 #define OVERFLOW -1
typedef char ElemType;
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10
typedef struct LNode{ //顺序表节点结构
ElemType *elem;//存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
int InitList (SqList &L){//构造线性表
L.elem=(ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem) exit(OVERFLOW);
printf ("输入线性表：");
gets(L.elem);
L.length=strlen(L.elem);
L.listsize=LIST_INIT_SIZE;
return OK; }
int ListInsert_Sq(SqList &L,ElemType x){//将元素 X 插入在适当位置
if(L.length>=L.listsize){
ElemType *newbase=(ElemType *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType)) ;
if(!newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int i=-1;//插入元素的位置
for(int j=0;j<strlen(L.elem);j++){
if(x<L.elem[j]) {
i=j;break;
}
}
if(i==-1) i=strlen(L.elem);
//printf("i=%d\n",i);
ElemType *q ;
q=L.elem+i;//q 为插入位置
for(ElemType *p=(L.elem+L.length-1);p>=q;--p){
*(p+1)=*p;//插入位置及之后元素右移
}
*q=x;
L.length++;
return OK;
}
void PrintLinkList(SqList L){//输出顺序表
for(int i=0;i<L.length;i++){
printf("%c",L.elem[i]);
}
} int main(void){
SqList L;
InitList (L);
//PrintLinkList(L);
ElemType x;
printf ("输入插入元素：");
scanf("%c",&x);
ListInsert_Sq(L,x);
printf ("线性表为：");
PrintLinkList(L);
return 0; }
#include <stdio.h>
#include <stdlib.h> #include <string.h> #define OK 1
typedef struct{//项的表示，多项式的项作为 LinkList 的数据元素
float coef;//系数
int expn;//指数
}term,ElemType;
typedef struct LNode{ //单链表节点结构
ElemType data;
struct LNode *next; }LNode, *LinkList;
typedef LinkList polynomial;
int CreatLinkList(polynomial &P,int n){ //创建多项式
P = (polynomial)malloc(sizeof(LNode));
polynomial q=P;
q->next=NULL;
polynomial s;
for(int i = 0; i < n; i++){
s = (polynomial)malloc(sizeof(LNode));
scanf("%f%d",&(s->data.coef),&(s->data.expn));
q->next = s;
s->next = NULL;
q=q->next;
}
return OK; } 运行结果
2. void PrintfPolyn(polynomial P){
polynomial q;
for(q=P->next;q;q=q->next){
if(q->data.coef!=1)
printf("%g",q->data.coef);
if(q->data.expn)
printf("%c%c%d","x","^",q->data.expn);
else printf("%g",q->data.coef);
if(q->next) printf(" + ");
}
printf("\n"); }
void AddPolyn(polynomial &Pa,polynomial &Pb,polynomial &Pc) {
polynomial qa,qb,qc;
qa=Pa->next;
qb=Pb->next;
qc=Pc;
//qa、qb、qc 分别指向 Pa、Pb、Pc 的当前结点
while(qa&&qb){
if((qa->data.expn)<(qb->data.expn)){
qc->next=qa;qc=qa;
qa=qa->next;
}
if((qa->data.expn)>(qb->data.expn)){
qc->next=qb;qc=qb;
qb=qb->next;
}
if((qa->data.expn)==(qb->data.expn)){
qa->data.coef+=qb->data.coef;
if(qa->data.coef!=0.0){
qc->next=qa;qc=qa;qa=qa->next;
polynomial b=qb;
qb=qb->next;free(b);
}
else{//删除 qa qb 当前指向节点 qa qb 后移
polynomial da,db;
da=qa;db=qb;
qa=qa->next;
qb=qb->next;
free(da);free(db);
if(!qa->next&&!qb->next)
qc->next=NULL;
}
}
}
qc->next=qa?qa:qb;
free(Pa);
free(Pb); }
int main(void){
int a,b;
polynomial Pa,Pb,Pc;
printf("分别输入多项式 A 和多项式 B 的元素个数:");
scanf("%d%d",&a,&b);
printf("输入多项式 A：");
CreatLinkList(Pa,a);
printf("输入多项式 B：");
CreatLinkList(Pb,b);
CreatLinkList(Pc,0);
printf("A(x) = ");
PrintfPolyn(Pa);
printf("B(x) = ");
PrintfPolyn(Pb);
AddPolyn(Pa,Pb,Pc);
printf("C(x) = ");
PrintfPolyn(Pc);
return 0; } 运行结果
遇到的问题和解决方法
对线性表的基本操作不熟悉，查找课本，多次运用，加深理解，以便能够将各种操作及其应用运用到程序中。
不能只看课本，要自己动手写程序，在实践中加深理解。
实验名称
实验二
树
实验目的和要求
熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。
实验内容
编写递归算法，计算二叉树中叶子结点的数目。
主要仪器设备
台式或笔记本电脑 实验记录( ( 写出实验内容中 (1)(2) 的运行结果和程序代码 )( 可分栏或加页) )
#include <stdio.h> #include <stdlib.h>
#define OK 1 #define OVERFLOW -1
typedef char TElemType;
typedef struct BiTNode { //结点结构
TElemType data;
struct BiTNode
*lchild, *rchild; //左右孩子指针 }BiTNode, *BiTree;
//按先序序列建立二叉树 int CreateBiTree(BiTree &T){
TElemType 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
int Leaf(BiTree T) {
if(T==NULL)
return 0;
if(!T->lchild && !T->rchild)
return 1;
return Leaf(T->lchild)+Leaf(T->rchild);
} int main(){
BiTree T; //declaration
printf("\n 输入树: \n");
//用例:ABD..EH...CF.I..G..\n
CreateBiTree(T); //创建
printf("\n 叶子结点树为 : ");
int n=Leaf(T);
printf("%d\n",n);
return 0; } 运行结果
遇到的问题和解决方法
对递归理解不够到位，写关于递归的算法有困难。通过查找资料，请教同学解决问题。
心得体会
要培养自己的动手实践能力。
实验名称
实验三
图
实验目的和要求
熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。
实验内容
试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点V i 到 V j 顶点的路径(i≠j)。
主要仪器设备
台式或笔记本电脑 实验记录( ( 写出实验内容中 (1)(2) 的运行结果和程序代码 )( 可分栏或加页) )
#include <stdio.h> #include <stdlib.h>
#define MAX_VERTEX_NUM 30
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc; }ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum; }ALGraph;
creat_DG_ALGraph(ALGraph *G){
int i,j,k;ArcNode *p;
p=NULL;
printf("分别输入结点数、边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("输入结点:\n");
for(i=0;i<G->vexnum;i++)
{
scanf("%d",&G->vertices[i].data);
G->vertices[i].firstarc=NULL;
}
/*for(i=0;i<G->vexnum;i++)
printf("%d ",G->vertices[i].data);
printf("\n");*/
for(k=0;k<G->arcnum;k++){
p=(ArcNode*)malloc(sizeof(ArcNode));
printf("输入边 <i,j>: ");
scanf("%d,%d", &i, &j);
printf("\n");
p->adjvex = j;
p->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=p;
}
}
int exist_path_DFS(ALGraph G,int i,int j){
ArcNode *p;
int k,visited[MAX_VERTEX_NUM];
p=NULL;
if(i==j) return 1;
else {visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{k=p->adjvex;
if(!visited[k]&&exist_path_DFS(G,k,j));
}
} }
int main(void){
ALGraph *G;
int i,j;
G=NULL;
creat_DG_ALGraph(G);
printf("输入要查找的路径（从 i 到 j）:\n");
scanf("%d%d",&i,&j);
if(exist_path_DFS(*G,i,j)) printf("Exist the path!");
else printf("Not exist the path");
return 0; } 遇到的问题和解决方法
不熟悉图的存储结构和有关算法的实现。
心得体会
要多看课本掌握基本知识。
实验名称
实验四
查找
实验目的和要求
通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。
实验内容
1． 编写程序实现下面运算：在二叉排序树中查找关键字为 key 的记录。
2. 试将折半查找的算法改写成递归算法。
主要仪器设备
台式或笔记本电脑 实验记录( ( 写出实验内容中 (1)(2) 的运行结果和程序代 码 )( 可分栏或加页) )
1. #include<stdio.h>
#include<stdlib.h>
#define FALSE 0 #define TURE 1
typedef struct BiTNode
{
int key;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
int SearchBST(BiTree T,int key,BiTree f,BiTree &p )//查找
{
if(!T)
{p=f;return FALSE;}
else if (key==T->key) {p=T;return TURE;}
else if(key<T->key) SearchBST(T->lchild,key,T,p);
else SearchBST(T->rchild,key,T,p);
}
int InsertBST(BiTree &T,int key)//插入
{
if(!T)
{
T=(BiTree)malloc(sizeof(BiTNode));
T->key=key;
T->lchild=(T)->rchild=NULL;
}
if(key==T->key) return FALSE;
if(key>T->key) InsertBST(T->rchild,key);
else InsertBST(T->lchild,key);
}
int main(void)
{
int e,n;
BiTree T=NULL,f,p;
printf("输入长度：");
scanf("%d",&n);
printf("输入关键字：");
while(n--)
{
scanf("%d",&e);
InsertBST(T, e);
}
printf("输入要查找元素：");
scanf("%d",&e);
if(SearchBST(T,e,f,p)) printf("查找成功\n");
else printf("查找失败\n");
return 0;
} 运行结果
2. #include <stdio.h> #include <stdlib.h>
#define OK 1 #define OVERFLOW -1
#define LIST_INIT_SIZE 100
//顺序表初始分配量 #define LISTINCREMENT 10
//分配增量
typedef int KeyType;
typedef struct{//元素结构
KeyType key; //主键
//…
//其他 }SElemType;
typedef struct{//顺序查找表结构
SElemType *elem;
int listsize;
int length; }SSTable;
int PrintSqList(SSTable &ST){//输出顺序表
printf("Sequenlial List.\nPos\tKey\n");
for(int i = 1; i <= ST.length; i++)
printf("%5d\t%5d\n", i, ST.elem[i]);
return OK; }//PrintSSTable
int InitSSTable(SSTable &ST, SElemType value[], int n){ //初始化顺序表
ST.elem = (SElemType *)malloc(LIST_INIT_SIZE * sizeof(SElemType));
if(!ST.elem) exit(OVERFLOW);
ST.listsize = LIST_INIT_SIZE;
ST.length = n;
SElemType *p = &ST.elem[1]; //elem[0]作为"哨兵"
for(int i = 0; i < n; i++) *p++ = value[i];
return OK; }//InitSSTable
//折半查找 int Search_Bin ( SSTable ST, KeyType key, int low, int high ){
if(low<=high){
int mid=(low+high)/2;
if(ST.elem[mid].key==key) return mid;
if(ST.elem[mid].key>key) return Search_Bin(ST,key,low,mid-1);
if(ST.elem[mid].key<key) return Search_Bin(ST,key,mid+1,high);
}
else return 0; }
int main(void){
SSTable ST; //声明
SElemType value[] = {12,23,28,35,37,39,50,60,78,90};//用例
InitSSTable(ST, value, (sizeof(value))/(sizeof(SElemType))); //初始化
PrintSqList(ST); //输出
KeyType key = 23; //关键字
printf("key=%d \t pos=%d\n", key, Search_Bin(ST, key,1,(sizeof(value))/(sizeof(SElemType)))); //折半查找
key = 58;
printf("key=%d \t pos=%d\n", key, Search_Bin(ST, key,1,(sizeof(value))/(sizeof(SElemType)))); //折半查找
}
运行结果
遇到的问题和解决方法
不熟悉树的存储结构和有关算法的实现。
心得体会
要多看课本掌握基本知识。
实验名称
实验五
内部排序
实验目的和要求
通过本次实验，掌握线性表的排序方法，并分析时间复杂度。
实验内容
设计一个用链表表示的直接选择排序算法，并用程序实现。
算法说明：已知待排序初始序列用单链表存贮，头指针 head 指向第一个结点，从这个待排序列中找出最小结点，插入 head 之后，用 r 来指示。r 以前为已排序序列，r 以后为未排序序列。再从未排序序列中找出最小结点插入 r 的后面，让 r 指向这个结点。反复执行这个过程，直到排好序。
主要仪器设备
台式或笔记本电脑 实验记录( ( 写出实验内容中 (1)(2) 的运行结果和程序代码 )( 可分栏或加页) )
#include <stdio.h>
#include <stdlib.h> #include <string.h>
#define OK 1
typedef int ElemType; typedef struct LNode{ //单链表节点结构
ElemType
data;
struct LNode
*next; }LNode, *LinkList;
int CreatLinkList(LinkList &L, int n){ //创建带头单链表
L = (LinkList)malloc(sizeof(LNode));
ElemType e;
L->next = NULL;
LinkList p;
for(int i = 0; i < n; i++){
scanf("%d",&e);
p = (LinkList)malloc(sizeof(LNode));
p->data = e;
p->next = L->next;
L->next = p;
}
return OK; }//CreatLinkList
void PrintList (LinkList L){//输出单链表
LinkList p;
for(p=L->next; p; p=p->next)
printf("%d ",p->data); }//PrintList void SelectMinKey(LinkList L,LinkList &q){//选择最小关键字
LinkList p;
q=(LinkList)malloc(sizeof(LNode));
q->data=10000;
for(p=L->next; p; p=p->next){
if((p->data)<(q->data)) q=p;
} }//SelectMinKey
void SlectSort (LinkList &L){//选择排序
LinkList head,r,p,q;
head=L->next;
r=L;
p=(LinkList)malloc(sizeof(LNode));
for(int i=1;r->next->next;i++){
SelectMinKey(r,q);
//printf("%d ",q->data);
p->data=q->data;
q->data=r->next->data;
r->next->data=p->data;
r=r->next;
printf("第%d 次排序:",i);
PrintList(L);
printf("\n");
} }//SlectSort
int main(void){
LinkList L,q;
int n;
printf("输入链表长度:");
scanf("%d",&n);
printf("输入链表:");
CreatLinkList(L,n);
/*PrintList(L);
printf("\n");*/
SlectSort(L);
printf("排序后链表:");
PrintList(L);
return 0; } 运行结果
遇到的问题和解决方法
对插入过程和算法不熟悉，程序的细节方面处理不到位。
心得体会
要多看课本，理解知识，多动手写程序。