实验07 指针

第1篇一、实验目的1. 理解指针在排序算法中的应用。

2. 掌握几种常见的排序算法（如冒泡排序、选择排序、插入排序等）的指针实现方式。

3. 比较不同排序算法的效率，分析其优缺点。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容本次实验主要实现了以下排序算法：1. 冒泡排序2. 选择排序3. 插入排序以下是对每种排序算法的具体实现和性能分析。

1. 冒泡排序（1）算法原理冒泡排序是一种简单的排序算法。

它重复地遍历待排序的序列，比较每对相邻的元素，如果它们的顺序错误就把它们交换过来。

遍历序列的工作是重复地进行，直到没有再需要交换的元素为止。

（2）指针实现```cppvoid bubbleSort(int arr, int len) {for (int i = 0; i < len - 1; i++) {for (int j = 0; j < len - 1 - i; j++) {if ((arr + j) > (arr + j + 1)) {int temp = (arr + j);(arr + j) = (arr + j + 1);(arr + j + 1) = temp;}}}}```（3）性能分析冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

当待排序序列基本有序时，冒泡排序的性能较好。

2. 选择排序（1）算法原理选择排序是一种简单直观的排序算法。

它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

（2）指针实现```cppvoid selectionSort(int arr, int len) {for (int i = 0; i < len - 1; i++) {int minIndex = i;for (int j = i + 1; j < len; j++) {if ((arr + j) < (arr + minIndex)) {minIndex = j;}}int temp = (arr + i);(arr + i) = (arr + minIndex);(arr + minIndex) = temp;}}```（3）性能分析选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

C语⾔教材第七章指针实验第七章指针第⼀部分知识训练【知识要点】1. 地址与指针指针变量的概念：⽤⼀个变量专门来存放另⼀个变量的地址。

2. 指向变量的指针变量指针变量的形式：基类型 *指针变量名；&: 取地址运算符；*：指针运算符。

3. 指针与数组引⽤⼀个数组元素可以⽤下标法和指针法；可以⽤数组名作函数的参数。

4.指针与函数函数指针变量定义的⼀般形式为：类型说明符 (*指针变量名)();⼀个函数的返回值可以是⼀个函数。

【典型习题与解析】5. char * const p;char const * pconst char *p上述三个有什么区别？【解析】char * const p; //常量指针，p的值不可以修改；char const * p；//指向常量的指针，指向的常量值不可以改；const char *p； //和char const *p。

6. main(){int a[5]={1,2,3,4,5};int *ptr=(int *)(&a+1);printf("%d,%d",*(a+1),*(ptr-1));}输出结果是什么？【解析】答案：输出：2,5*(a+1）就是a[1]，*(ptr-1)就是a[4],执⾏结果是2，5。

&a+1不是⾸地址+1，系统会认为加⼀个a数组的偏移，是偏移了⼀个数组的⼤⼩（本例是5个int）。

1)&a是数组指针，其类型为 int (*)[5];⽽指针加1要根据指针类型加上⼀定的值，不同类型的指针+1之后增加的⼤⼩不同。

2)a是长度为5的int数组指针，所以要加 5*sizeof(int)，所以ptr实际是a[5]，但是prt与(&a+1)类型是不⼀样的(这点很重要)，所以prt-1只会减去sizeof(int*) a,&a的地址是⼀样的，但意思不⼀样。

3)a是数组⾸地址，也就是a[0]的地址，&a是对象（数组）⾸地址，a+1是数组下⼀元素的地址，即a[1],&a+1是下⼀个对象的地址，即a[5]。

示意） ， 表示 这 块 空 间 的开始 ， 二 是从 起 始地 址 开始 的空 间 大小， 这两个特征一起确定了一个变量 ； ②作 为内存的一块 存储空 间， 自然可以存储不同的值 ， 会变化 ； ③变量的声 明 是提出分配存储空间的要求 ，没有分配空间，当然不能存 值， 不能使用 ； ④为 了在程序中方便使用变量 ， 变量可以取 个名字， 即变 量名 。
教 育 教 学 论 坛
ＥＤ Ｕ ＣＡ ＴＩ ＯＮ Ｔ ＥＡ ＣＨ Ｉ Ｎ Ｇ Ｆ ＯＲ ＵＭ
Ｊ ａＦ Ｉ ． ２ Ｏ１ ４
Ｎ Ｏ． ４
【 学 法 指 导 】
数据 结构实验 中指针相关问题
孔
（ 云南大学
兵， 陈红梅 ， 袁 国武
信息学院 ， 云南 昆明 ６ ５ ０ ０ ９ １ ）
要 的概 念 。在 Ｃ 语言 中， 指 针 的应 用 非 常灵 活 ， 对 于 程序 设 计初学者来说比较难掌握 ， 更谈不上灵活合理的应用。《 数 据结构》 中（ 注： 文 中的讨论围绕严蔚敏老师的《 数据结构》 Ｃ 语 言版教材四 ） ， 为 了实 现 数 据 的存 储 结 构 ， 指 针 在 线 性 表、 树 和 图 的存储 中都有 重 要 的应 用 ， 可 以说 ， 数据 结 构 的 实验绕 不 开指 针 的应用 ， 如 果学 生 掌握不 好指 针 ， 是 无法 进 行 数据 结构 实验 学 习 的 。 教 学 中注 意到 ，学 生 的主要 问题 是对 指针 的本 质缺 乏 清晰的理解 ， 知其然不知其所以然 ， 导致在应用时只会依葫 芦 画瓢 ，不会 灵活 应用 。针 对学 生理 解 和应用 中的难点 问
一
后 同 样 需 要 给 该 变 量 分 配 一 块 存 储 空 间， 只是 该 空 间 存 储 的 内容有 点 特 殊 ， 是 个 地址 。②获 取数

Ｃ++上机实验报告实验名称：指针专业班级：姓名：学号：实验日期：目录1.实验目的2.实验内容3.程序代码4.调试结果5.实验心得1.实验目的（1）通过实验进一步掌握指针的概念，会定义和使用指针变量；（2）能正确使用数组的指针和指向数组的指针变量；（3）能正确使用字符串的指针和指向字符串的指针变量；（4）能正确使用引用型变量。

2.实验内容编程序并上机调试运行程序（要求用指针或引用处理）。

（1）输入3个整数，按由小到大的顺序输出。

编译一个程序，用指针变量作为参数。

（2）在上题的基础上将程序改为：输入3个字符串，按由小到大的顺序输出。

（3）用引用指针变量作为形参，实现3个整数由小到大输出。

（4）有n个人围成一圈，顺序排号。

从第1个人开始报数（从1~3报数），凡是到3的人退出圈子，问最后留下的人原来排在第几号。

（5）在主函数中输入10个字符串。

用另一个函数最它们排序。

然后在主函数输出这10个已排好的字符串。

要求用以下方法编程：Ⅰ.指向一维数组的指针座函数参数；Ⅱ.用string数组方法。

3.程序代码（1）#include<iostream>using namespace std;int main(){void swap(int *p1,int *p2);int n1,n2,n3;int *p1,*p2,*p3;cout<<"input three integers n1,n2,n3:";cin>>n1>>n2>>n3;p1=&n1;p2=&n2;p3=&n3;if(n1>n2) swap(p1,p2);if(n1>n3) swap(p1,p3);if(n2>n3) swap(p2,p3);cout<<"Now,the order is:"<<n1<<" "<<n2<<" "<<n3<<endl; return 0;}void swap(int *p1,int *p2){int p;p=*p1;*p1=*p2;*p2=p;}（2）Ⅰ.用字符数组方法的源程序#include<iostream>using namespace std;int main(){void swap(char *,char *);char str1[20],str2[20],str3[30];cout<<"input three line:"<<endl;gets(str1);gets(str2);gets(str3);if(strcmp(str1,str2)>0) swap(str1,str2); if(strcmp(str1,str3)>0) swap(str1,str3); if(strcmp(str2,str3)>0) swap(str2,str3); cout<<endl<<"Now,the order is:"<<endl; cout<<str1<<endl<<str2<<endl<<str3<<endl; return 0;}void swap(char *p1,char *p2){char p[20];strcpy(p,p1);strcpy(p1,p2);strcpy(p2,p);}Ⅱ.用string方法的源程序（程序中使用了指针和引用）#include<iostream>#include<string>using namespace std;int main(){void change(string &,string &);string str1=" ",str2=" ",str3=" ";char *p1=&str1[0],*p2=&str2[0],*p3=&str3[0];cout<<"input three line:"<<endl;gets(p1);gets(p2);gets(p3);if(str1>str2) change(str1,str2);if(str1>str3) change(str1,str3);if(str2>str3) change(str2,str3);cout<<endl<<"Now,the order is:"<<endl;cout<<str1<<endl<<str2<<endl<<str3<<endl; return 0;}void change(string &st1,string &st2) {string st;st=st1;st1=st2;st2=st;}（3）#include<iostream>using namespace std;int main(){void exchange(int *,int *,int *);int a,b,c,*p1,*p2,*p3;cin>>a>>b>>c;p1=&a;p2=&b;p3=&c;exchange(p1,p2,p3);cout<<a<<" "<<b<<" "<<c<<endl;return 0;}void exchange(int *q1,int *q2,int *q3){void swap(int *,int *);if( *q1> *q2) swap(q1,q2);if( *q1> *q3) swap(q1,q3);if( *q2> *q3) swap(q2,q3);}void swap(int *pt1,int *pt2){int temp;temp=*pt1;*pt1=*pt2;*pt2=temp;}（4）#include<iostream>using namespace std;int main(){int i,k,m,n,num[50],*p;cout<<"input number of person:n="; cin>>n;p=num;for(i=0;i<n;i++)*(p+i)=i+1;i=0;k=0;m=0;while(m<n-1){if(*(p+i)!=0) k++;if(k==3){*(p+i)=0;k=0;m++;}i++;if(i==n) i=0;}while(*p==0)p++;cout<<"The last one is NO."<<*p<<endl; return 0;}（5）Ⅰ.指向一维数组的指针最函数参数的源程序#include<iostream>using namespace std;int main(){void sort(char (*p)[6]);int i;char str[10][6];char (*p)[6];cout<<"input 10 strings:"<<endl;for(i=0;i<10;i++)cin>>str[i];p=str;sort(p);cout<<"Now,the sequence is:"<<endl; for(i=0;i<10;i++)cout<<str[i]<<endl;return 0;}void sort(char (*s)[6]){int i,j;char temp[6],*t=temp;for(i=0;i<9;i++)for(j=0;j<9-i;j++)if(strcmp(s[j],s[j+1])>0){strcpy(t,s[j]);strcpy(s[j],s[+j+1]);strcpy(s[j+1],t);}}Ⅱ.用string数组方法的源程序#include<iostream>#include<string>using namespace std;int main(){void sort(string*);int i;string str[10],*p=str;cout<<"input 10 strings:"<<endl;for(i=0;i<10;i++)cin>>str[i];sort(p);cout<<"Now,the sequence is:"<<endl; for(i=0;i<10;i++)cout<<str[i]<<endl;return 0;}void sort(string *s){int i,j;string temp;for(i=0;i<9;i++)for(j=0;j<9-i;j++)if(s[j]>s[j+1]){temp=s[j];s[j]=s[+j+1];s[j+1]=temp;}}4.调试结果（1）input three integers n1,n2,n3:54 -12 2 Now,the order is:-12 2 54（2）input three lines:I study very hard.C language is very interesting.He is a professor.Now,the order is:C language is very interesting.He is a professor.I study very hard.（3）12 6 876 12 87（4）input number of person:n=8The last one is No.7（5）input 10 strings: Now,the sequence is:China BurmaJapan ChinaKorea EgyptEgypt GhanaNepal ItalyBurma JapanGhana KoreaSudan LibyaItaly NepalLibya Sudan5.实验心得指针同数组一样，是C++中一个重要的概念，一个重要的知识点。