单链表实验报告.doc

单链表实验报告正式版

计算机与信息技术学院综合性、设计性实验报告

专业：网络工程 年级/班级：大二 2021—2021学年第一学期
课程名称
数据结构
指导教师
李四
学号姓名
16083240XX张三
项目名称
单链表的基本操作
实验类型
综合性/设计性
实验时间

实验地点
216机房

一、 实验目的
（1）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。
二、 实验仪器或设备
（1）硬件设备：CPU为Pentium 4以上的计算机，内存2G以上
（2）配置软件：Microsoft Windows 7与VC++6.0
三、 总体设计（设计原理、设计方案及流程等）
设计原理：
单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。
设计方案：
采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。
设计流程：
1. 引入所需的头文件；
2. 定义状态值；
3. 写入顺序表的各种操作的代码；
写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输入值是否非法，从而执行相应的程序
四、 实验步骤（包括主要步骤、代码分析等）
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // srand( ) ,rand( ),exit(n)
#include<malloc.h> // malloc( ),alloc( ),realloc( )等
#include<limits.h> // INT_MAX等
#include<string.h>
#include<ctype.h>
#include<math.h> // floor(),ceil( ),abs( )
#include<iostream.h> // cout,cin
#include<time.h> // clock( ),CLK_TCK,clock_t
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedefint Status; // Status是函数的类型,
//其值是函数结果状态代码，如OK等
typedefintElemType;
typedefstructLNode
{
ElemType data; //结点的数据域
structLNode *next; //结点的指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
//初始化单链表
算法步骤：
1. 生成新结点作为头结点，用头指针L指向头结点。
2. 头结点的指针域置空。
Status InitList_L(LinkList &L)
{
L=new LNode; //生成新结点作为头结点，用头指针L指向头结点；
L->next=NULL; //头结点的指针域置空
return OK;
}
//单链表的取值
算法步骤：
1. 用指针P指首元结点，用j做计数器初值赋为1.
2. 从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有到达序号为i的结点，则循环执行以下操作：
P指向下一结点；
计数器j相应加1；
3.退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR，否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。
Status GetElem_L(LinkList L, inti, ElemType &e)
{
LinkList p;
int j;
p=L->next;
j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}

//单链表的按值查找
算法步骤：
1. 用指针p指首元结点。
2. 从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点。
3. 返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
intLocateElem_L(LinkListL,ElemType e)
{
LinkList p;
int j;
p=L->next;
j=1;
while(p&&p->data!=e)
{
p=p->next;
j++;
}
if(p) return j;
else return 0;
}
//单链表的插入
算法步骤：
1. 查找结点ai-1并由指针p指向该结点。
2. 生成一个新结点*s。
3. 将新结点*s的数据域置为e。
4. 将新结点*s的指针域指向结点ai。
5. 将结点*p的指针域指向新结点*s。
Status ListInsert_L(LinkList &L,inti,ElemType e)
{
LinkList p=L,s;
int j=0;
while(p&&(j<i-1))
{
p=p->next;
++j;
}
if(!p||j>i-1)
{
return ERROR;
}
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
//单链表的删除
1. 查找结点ai-1并由指针p指向该结点。
2. 临时保存待删除结点ai的地址在q中，以备释放。
3. 将结点*p的指针域指向ai的直接后继结点。
4. 释放结点ai的空间。
Status ListDelete_L(LinkList &L,inti)
{
LinkList p=L,q;
int j=0;
while((p->next)&&(j<i-1))
{
p=p->next;
++j;
}
if((!p->next)||(j>i-1))
{
return ERROR;
}
q=p->next;
p->next=q->next;
delete q;
return OK;
}
//单链表的输出
算法步骤：
1. 将指针p指向L的next域。
2. 输出p指针的数据。
3. 将指针p后移。
4. 循环第2,3步，直到p指针为空（NULL）。
voidListPrint_L(LinkList L)
{
LinkList p;
p=L->next;
do
{
printf("%5d",p->data);
p=p->next;
}while(p);
}
void main()
{
inti,n,e;
LinkList L;
if(InitList_L(L));
printf("单链表创建成功！\n");
printf("请输入您要输入的数据个数n:\n");
scanf("%d",&n);
printf("请输入您要输入的数据：\n");
for(i=1;i<=n;i++)
{
scanf("%d",&e);
ListInsert_L(L,i,e);
}
printf("当前单链表的内容为：\n");
ListPrint_L(L);
printf("\n");
printf("请输入您要插入的数据e及其位置i，使用空格键隔开:\n");
scanf("%d %d",&e,&i);
if(ListInsert_L(L,i,e))
{
printf("当前单链表的内容为：\n");
ListPrint_L(L);
}
else
{
printf("i值越界！\n");
}
printf("\n");
printf("请输入您要取的数据序号：\n");
scanf("%d",&i);
if(GetElem_L(L,i,e))
{
printf("第%d位数据的值为:%d\n",i,e);
}
else
{
printf("i值越界！\n");
}
printf("请输入要查找的数据值：\n");
scanf("%d",&e);
if(!LocateElem_L(L,e))
{
printf("查无此值!\n");
}
else
{
printf("数据%d在%d号位置\n",e,LocateElem_L(L,e));
}
printf("请输入要删除的数据的序号：\n");
scanf("%d",&i);
if(ListDelete_L(L,i))
{
printf("删除后单链表的内容为：\n");
ListPrint_L(L);
}
else
{
printf("输入有误！");
}
printf("\n");
}
五、 结果分析与总结

图1
结果分析：
如图1所示，输入正确数据时，程序各个功能执行正常。设置输入数据个数为5，可以输入5个数据，按回车后，可以显示我们当前单链表中的数据内容。继续输入下一指令：输入要插入的数据及位置，使用空格键隔开，回车后，可以看到已经成功插入。继续输入所取的数据序号，可以查找该数据的值。输入要查找的数据，可以返回该数据的位置。输入要删除的数据，可以返回删除该元素后的单链表的内容。
总结：
在单链表中，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域；其中存储数据元素的域称为数据域；存储直接后继的域称为指针域。
教师签名：

年 月 日
实习报告
题目：设计一个哈希表，完成相应的建表和查表程序
班级：1503013 姓名：李睿元 学号：15030130073 完成日期：2021.12.04

一、 需求分析
1. 假设人名为中国人名的汉语拼音形式；
2. 待填入哈希表的姓名共有30个，去平均查找长度的上限为2；
3. 哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；
4. 取读者周围较熟悉的30个人的姓名。
二、 概要设计
1. 抽象数据类型的定义：
（1）人名数据表：
typedef struct Node
{
char name[20];
int key;
}Node,NodeList[MAX];

（2）哈希表：
typedef struct hashtable
{
char* name;
int key;
int conflict_time;
}HashTable[hashlen];
（3） 变量：
#define P 61//随机数值
#define MAX 30//人数
#define hashlen 61//哈希表长
2. 主要函数的实现：
（1）哈希函数：
int Hash(int key)
（2） 关键字获得：
int GetKey(char str[])
（3） 文件流中读取姓名：
void GetName(NodeList &L,int i,FILE* fp)
（4） 哈希表的初始化：
void InitialHashTable(HashTable &ht)
（5） 伪随机探测序列的生成：
void CreatConfilctArray(int n[])
（6）哈希表的生成：
void CreatHashTable(HashTable &ht,NodeList L,int* n)
（7） 哈希表的查询：
void SearchHashTable(HashTable ht,int* n,char get_name[])
三、 详细设计
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define P 61//随机数值
#define MAX 30//人数
#define hashlen 61//哈希表长

typedef struct Node
{
char name[20];
int key;
}Node,NodeList[MAX];
typedef struct hashtable
{
char* name;
int key;
int conflict_time;
}HashTable[hashlen];

int Hash(int key)
{
return key%P;
}

int GetKey(char str[])
{
int t=0;
char *s=str;
while(*s)
{
t += *s;
s++;
}
return t;
}

void GetName(NodeList &L,int i,FILE* fp)
{
/*printf("请以拼音形式输入第%d个姓名:",i);
scanf("%s",L[i].name);
L[i].key=GetKey(L[i].name); */
fscanf(fp,"%s",L[i].name);
L[i].key=GetKey(L[i].name);
//printf("\n");
}

void InitialHashTable(HashTable &ht)
{
int n=0;
while(n<hashlen)
{
ht[n].conflict_time=0;
ht[n].name=NULL;
ht[n].key=0;
n++;
}
}

void CreatConfilctArray(int n[])
{
//n=(int*)malloc(50*sizeof(int));
int i=0,j=0;
while(i<50)
{
n[i]=rand()%(hashlen+1);
for(;j<i;j++)
{
if(n[i]==n[j])
{
j=0;
n[i]=rand()%(hashlen+1);
continue;
}
}
i++;
}
}

void CreatHashTable(HashTable &ht,NodeList L,int* n)
{
//CreatConfilctArray(n);

int i=0;
int t;
while(i<MAX)
{
t=Hash(L[i].key);
if(ht[t].conflict_time==0)
{
ht[t].name=L[i].name;
ht[t].conflict_time++;
ht[t].key=L[i].key;
printf("姓名：%s key值：%d 表内存储位置：%d\n",L[i].name,L[i].key,t);
}
else
{
int m=0;
int d=(t+n[m])%hashlen;
while(ht[d].conflict_time!=0)
{
ht[d].conflict_time++;
m++;
d=(t+n[m])%hashlen;
}
ht[d].name=L[i].name;
ht[d].conflict_time++;
ht[d].key=L[i].key;
printf("姓名：%s key值：%d 表内存储位置：%d\n",L[i].name,L[i].key,d);
}
i++;
}
}

void SearchHashTable(HashTable ht,int* n,char get_name[])
{
//printf("请输入要查询的姓名：");
//char get_name[20];
int p=-1;
int s_time=1;
//scanf("%s",get_name);

int h,k;
int t;
k=GetKey(get_name);
t=h=Hash(k);

while(1)
{
/*if(ht[h].conflict_time==0&&ht[h].key!=k)
{
printf("表中未找到无此人！\n");
break;
}
else if(ht[h].key==k)
{
printf("已找到%s，表内存储位置：%d\n",get_name,h);
break;
}
else
{
p++;
h=n[p];
}*/
if(ht[h].name==NULL)
{
printf("表中未找到无此人！\n");
break;
}
else if(strcmp(ht[h].name,get_name)==0)
{
printf("已找到%s，表内存储位置：%d，查找次数:%d\n",get_name,h,s_time);
break;
}
else
{
p++;
h=(t+n[p])%hashlen;
s_time++;
}
}
}

int main()
{
//printf("请输入建表所需的三十个人名！\n");
int i,j;
NodeList L;
HashTable ht;
InitialHashTable(ht);
char get_name[20]={0};
int rand_n[50];
CreatConfilctArray(rand_n);
FILE* fp;
fp=fopen("name.txt","r");

for(i=0;i<30;i++)
{
GetName(L,i,fp);
}

fclose(fp);

CreatHashTable(ht,L,rand_n);
printf("\n");
printf("--------------哈希表建表完成-------------");
printf("\n");

while(1)
{
get_name[20]={0};
printf("请输入要查找的人名(输入“***”表示结束程序):");
scanf("%s",get_name);
printf("关键字：%d ",GetKey(get_name));
if(strcmp(get_name,"***")==0)
break;

SearchHashTable(ht,rand_n,get_name);
}

return 0;
}
四、 调试分析
1. 哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录；
2. 除留余数法对于p的选择很重要，经过分析后的选择是p为小于等于m的最大素数，最终选择了61；
3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。
五、 用户手册
1. 本程序的运行环境为Windows操作系统，执行文件为hashtable.exe；
2. 本程序的输入的名字存储在name.txt文件中；

3. 程序进入后已经完成哈希表的构建并进行展示，用户只需进行相应的查找；

六、 测试数据
1. 挑选表中已有的十个姓名进行测试
（xiaoli,zhuangshuangshuang,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wangkun）

与上方的哈希表进行对比完全匹配。

2. 选择5个没有在表中的名字进行查表操作：
（lovetianqi,tianjiejie,jiwang,beijing,heheda）

HUNANUNIVERSITY

课程实习报告

题 目： 哈希表
学生姓名 唐鹏
学生学号202108080216
专业班级 物联2班
指导老师吴帆
完 成 日 期2021年4月2日

一、 需 求 分 析：
1. 本程序来自于图书馆靠书名来检索想要查找的书问题。
2. 本程序要求：
（1）根据输入建立图书名称表，采用创建散列表实现。
（2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。
二、 哈希表简介
结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。
* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。
* 综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”， 作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子(load factor)不超过75%，查找效率最高。
* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
程序设计流程
程序思想
(一) 哈希函数unsigned int hash_BKDE(char *str)生成映射地址，成为散列表的编号。
(二) 哈希表HashTable::HashTable()通过数组储存元素
(三) 插入函数void HashTable::insert(char*c)插入字符串，先计算要插入字符串生成的映射地址，然后在相应的地址插入，如果没有空位查找空位插入。
(四) 查找函数bool HashTable::find(char*c)进行查找，先计算要生成字符串的地址，再到散列表中进行查找比较。
(五) 主函数main（）
1) 输入：输入散列表内容和要查找的数据个数和数据
2) 输出模块：散列表查找的结果。
3) 建散列表并查找：建立散列表并递归查找
流程图

三.实验源程序：
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
unsigned int hash_BKDE(char *str)//哈希函数，题目给出
{
//初始种子 seed 可取31 131 1313 13131 131313 etc..
unsigned int seed = 131;
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
double k=(double)(rand()%999)/1000; //随机生成小数随机数 0<k<1
unsigned int hash_rand(unsigned int value) //value<2^32 ，将转化地址转化为seed
{
double a=k*value;
double n=(a-(int)a)*64; //取小数部分与2^5相乘
unsigned int seed=(int)n;
return seed;
}
unsigned int Hash(char*str) //生成最终的地址映射即计算散列地址位置
{
return hash_rand(hash_BKDE(str));
}
class HashTable//哈希表类
{
public:
HashTable();
~HashTable();
void insert(char*c);
bool find(char*c);
private:
char**Arr; //二维数组用于保存字符串 书名
int ArrSize; //散列表单元个数 在此为2^15=32768
};

HashTable::HashTable()
{
ArrSize=32768;
Arr=new char*[64];
for(int i=0;i<64;i++)
{
Arr[i]=new char[100];
Arr[i]=NULL;
}
}
HashTable::~HashTable()
{
for(int i=0;i<64;i++)
delete[]Arr[i];
delete []Arr;
}
void HashTable::insert(char*c)//插入到哈希表
{
unsigned int pos=Hash(c);//计算散列地址位置
while(Arr[pos]!=NULL)
pos=(pos+1); //解决冲突的办法，寻找空位，向后面挪动一个
Arr[pos]=c; //插入存储
}
bool HashTable::find(char*c)//查找
{
unsigned int pos=Hash(c); //计算散列地址
while(Arr[pos]!=NULL) //非空时进行查找 比较
{
if(Arr[pos]==c)return true;
pos=(pos+1); //寻找下一地址，如果运行这一步，这说明之前产生了冲突
}
return false;
}
int main()
{
bool a[20];
char *c1=new char[100];
HashTable H;
cout<<"输入字符串个数n：\n";
int n;
cin>>n;
cout<<"输入n个字符串：\n";
for(int i=1;i<=n;i++)
{
cin>>c1;
H.insert(c1);//直接插入到散列表的数组中
}
cout<<"输入待查的字符串个数m：\n";
int m;
cin>>m;
cout<<"输入要查找的字符串:"<<endl;
for(int j=0;j<m;j++)
{
cin>>c1;
a[j]=H.find(c1);//bool量
}
cout<<"查找结果(yes表示存在，no表示不存在)：\n";
for(int k=0;k<m;k++)
if(a[k])
cout<<"yes\n";
else
cout<<"No\n";
return 0;
}
四、实验截图

五、实验感想
本次的实验首先要弄清楚哈希表，然后弄清楚最关键的两个模块，插入和查找。
插入模块中，首先要有哈希函数生成映射地址，要有哈希表保存元素，然后就是自己设定的解决冲突的办法，这个程序是采用向下挪动一个办法，直到找到为空的地方保存。在查找中也是，先要通过哈希函数生成映射地址，通过这个地址参看哈希表中时候有元素，考虑到会有冲突的产生，那么必须那么必须要通过循环查找，要么找到元素，否则直到为空跳出查找。这也是这个程序的难点所在。总体来说，哈希表对于提高储存和查找效率方面有很大的提升。实验难度不是很大。
浙江工贸职业技术学院实验报告
2021-2021学年第一学期
系别电子系 班级 学号 姓名
实验课程电工电子技术 实验日期 指导老师林烨
实验项目名称万用表的使用
实验目的/仪器10%
实验内容与步骤40%
实验数据图表40%
结论10%
总分

一、实验目的：
1、掌握色标电阻阻值识别。
2、掌握数显式万用表在测量线性电阻、直流电压、直流电流及交流电压电流的方法。
3、了解模拟电路试验箱的使用。

二、实验仪器：
模拟电路实验箱 万用表

三、实验内容与步骤：
实验电路图

（注意：按照电路图规范画图）

步骤一：用万用表测量电阻
用万用表的电阻档分别测量线性电阻R1、R2、R3、R4、R5，Rg的阻值，并将可调节电阻Rw调至120Ω。
电阻
R1
R2
R3
R4
R5
Rg
Rw
标称值（Ω）

120Ω
实测值（Ω）

步骤二：用万用表测量直流电流：
将A闭合，接通DC12V电源，用万用表测量1、5两点之间的电流。（注意单位）：
I15＝A
用导线连接2、5，接通DC12V电源，用万用表测量流经A点的电流。（注意单位）：
IA＝A

步骤三：用万用表测量直流电压：

UBC
UBD
UDC
测量值

四、思考题
1、写出数显用万用表测量电阻的三个步骤。

2、用万用表测量电流要注意哪些事项？