回顾C语言指针和链表.docx
- 文档编号:7326779
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:37
- 大小:447.56KB
回顾C语言指针和链表.docx
《回顾C语言指针和链表.docx》由会员分享,可在线阅读,更多相关《回顾C语言指针和链表.docx(37页珍藏版)》请在冰点文库上搜索。
回顾C语言指针和链表
回顾C语言:
指针和链表
§1.结构体
1.声明结构体类型
struct结构体名
{
成员列表
}
例:
structstudent
{
intnum;
charname[20];
intage;
floatscore;
}
2.定义变量
(1).先定义类型再定义变量
如:
类型如上定义,变量定义为:
structstudentstudent1,student2
(2).定义类型的同时定义变量
struct结构体名
{
成员列表
}变量列表;
(3).注:
成员也可是结构体变量
如:
structdate
{
intmonth;
intday;
intyear;
}
structstudent
{
intnum;
…
structdatebirthday;
}student1,student2;
(4).结构体类型变量的引用
1>.不能将一个结构体变量作为一个整体进行输入和输出;如以下错误:
printf("%d,%s,%c,%d,%f,%s",student1)
只能引用单个成员,如下:
结构体变量名.成员名
2>.如果成员本身又是一个结构体,则要用若干个成员运算符,一级一级地找到最低的一级成员:
student1.birthday.year
3>.对成员变量可以像对普通变量一样进行各种运算
student1.age++;
4>.可以引用成员的地址,也可以引用结构体变量的地址
scanf("%d",&student1.num);
printf("%d",&student1);
§2.指针
1.变量的指针和指向变量的指针变量
(1).基本概念
变量的指针就是变量的地址
(2).指针变量的定义
专门用来存放另一变量的地址的变量,称为指针变量。
它的值为指针(地址)。
inti,j;
int*pointer1,*pointer2;
pointer1=&i;
pointer2=&j;
注:
一个指针变量只能指向同一个类型的变量.
(3).指针变量的引用.
inta;
int*p;
a=10;
p=&a;
prinf("%d",*p);
请指出以下的含义:
1>&*p
2>*&a
3>*p++相当于*(p++)
(4).例:
输入a和b,按先大后小顺序输出
main()
{
int*p1,*p2,*p,a,b;
scanf("%d,%d",&a,&b);
p1=&a;p2=&b;
if(a
{
p=p1;p1=p2;p2=p;
}
printf("a=%d,b=%d\n",a,b);
printf("max=%d,min=%d\n",*p1,*p2)
}
2.指针变量做函数参数
要用函数实现两个变量值的交换,该如何实现?
(1).实现方案1:
swap(intx,inty)
{
intt;
t=x;x=y;y=t;
}
调用形式:
swap(a,b)
结论:
不能实现
(2).实现方案2:
改变指针形参的值
swap(int*p1,int*p2)
{
int*p;
p=p1;p1=p2;p2=p;
}
调用形式:
swap(&a,&b)
结论:
不能实现
(3).实现方案3:
交换*p1,*p2的值
swap(int*p1,int*p2)
{
int*p;
*p=*p1;//有错
*p1=*p2;
*p2=*p;
}
(4).实现方案4:
swap(int*p1,int*p2)
{
int*p;
p=*p1;*p1=*p2;*p2=p;
}
调用形式:
swap(&a,&b)
结论:
成功
3.数组的指针
(1).概念
数组的指针是数组的起始地址
数组元素的指针是数组元素的地址.
(2).inta[10];
int*p;
p=&a[0];等价p=a;
(3).通过指针引用数组元素
如上定义:
1>.*p=1;//数组第0个元素赋值为1
2>.p+i和a+i就是&a[i]
3>.*(p+i)或*(a+i)是a[i]
4>.例:
输入数组全部元素。
main()
{
inta[10];
int*p,i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(p=a;p<(a+10);p++)
printf("%d",*p);
}
5>.注意指针变量的当前值。
main()
{
int*p,i,a[10];
p=a;
for(i=0;i<10;i++)
scanf("%d",p++);
p=a;
for(i=0;i<10;i++,p++)
printf("%d",*p);
}
6>.概念问题:
如果有inta[10];
int*p=a;
则:
1.p++;//p指向a[1]
2.*p++;//作用是先得到*p,然后再使p+1=>p
3.*(p++);//先取*p的值,p再加1,和2等同
*(++p);//先使p+1,再取*p
4.(*p)++;//即(a[0])++
(4).数组作函数参数
如果函数中将数组的值改变,那么在调用该函数的地方,数组值也变了。
(具体略)
4.指向结构体类型数据的指针
(1).指向结构体变量的指针
main()
{
structstudent
{
intnum;
floatscore;
}
structstudentstu,*p;
p=&stu;
stu.num=10;
stu.score=89.5;
printf("%d,%f",(*p).num,(*p).score)
}
注:
(*p).num等价p->num
(2).指向结构体数组的指针
structstudentstu[3]={{101,75},{102,89.5},{103,92}};
structstudent*p;
for(p=stu;p printf("%d,%f\n",p->num,p->score) (3).用指向结构体的指针作函数参数 用指针作实参,将结构体变量的地址传给形参,避免大量数据的复制。 §3.用指针处理链表 1.概述: (1).结点定义: structstudent { intnum; floatscore; structstudent*next; } (2).分配和释放结点空间 void*malloc(sizeof(structstudent));//在系统内存中分配存储单元,并返回该空间的基址 free(p);//将指针变量p所指示的存储空间,回收到系统内存空间中去 (3)链表的概念 用线性链表存储线性表时,数据元素之间的关系是通过保存直接后继元素的存储位置来表示的。 1010 1012 1014 1016 1018 1020 1022 1024 1026 内存中保存的信息如下: a4 a3 a1 a2 0 1010 1024 1014 图示表示如下: 2.建立链表 (1).写一函数建立一学生单向链表(从尾部插入) intn; structstudent*create() { structstudent*head; structstudent*p1,*p2; n=0; p1=p2=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); head=NULL; while(p1->num! =0)//num为0,意味着用户输入结束 { n=n+1; if(n==1)//创建第一个结点 head=p1; else p2->next=p1; p2=p1;//p2始终指向最后一个结点(即尾指针) p1=(structstudent*)malloc(sizeof(structstudent));//p1指向新结点 scanf("%d,%f",&p1->num,&p1->score); } p2->next=NULL;//切记: 最后一个结点的next赋值为NULL returnhead; } (2).从头部开始插入 将while循环改成: while(p1->num! =0) { p1->next=head; head=p1; p1=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); } 则变成以下形式: structstudent*create() { structstudent*head; structstudent*p1,*p2; n=0; p1=p2=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); head=NULL; while(p1->num! =0) { p1->next=head; head=p1; p1=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); } returnhead; } head (3).有头结点的链表 1>.在单链表的第一个结点之前附设一个结点,称为头结点. 增加头结点有什么好处? 请看后面的例子。 2>.从尾部插入生成链表 structstudent*create() { structstudent*head,*p1,*p2; p1=p2=(structstudent*)malloc(sizeof(structstudent)); head=p1;//p1指向头结点 p1=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); while(p1->num! =0) { p2->next=p1; p2=p1; p1=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); } p2->next=NULL; returnhead; } 3>.如果头结点在主函数生成并传给create函数,则create()函数可不返回值。 即: voidcreate(structstudent*head)//create返回void { structstudent*p1,*p2; p2=head; p1=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); while(p1->num! =0) { p2->next=p1; p2=p1; p1=(structstudent*)malloc(sizeof(structstudent)); scanf("%d,%f",&p1->num,&p1->score); } p2->next=NULL; } main() { structstudent*head; head=(structstudent*)malloc(sizeof(structstudent)); head->next=NULL;//只有一个头结点,是空链表 create(head);//生成链表 //对链表操作,比如输出链表元素 } 3.遍历链表(两种应用举例) (1).输出: p=head; while(p! =NULL) { printf("%d,%f\n",p->num,p->score); p=p->next; } (2).求长度 p=head; k=0; while(p) { k++; p=p->next; } printf("thelengthis%d",k); 4.查找元素(查找学生) structstudent*Locate(structstudent*head,structstudentstu) { structstudent*p; p=head; while(p&&p->num! =stu.num)//注意循环结束条件 等价于 p=p->next; returnp; } 5.删除结点 1>.删除p所指的结点 程序实现: q->next=p->next; free(p);//该语句用来释放占用的内存资源,即使没这个语句,结点也被从链表中删除 2>.程序 structstudent*DeleteNode(structstudent*head,structstudent*p) {//针对不带头结点的链表做删除操作 //程序功能: head指向链表,删除p所指向的结点 structstudent*q; if(p==head) { head=p->next; } else { q=head; while(q->next! =p) q=q->next; q->next=p->next; } free(p); returnhead; } 3>.删除指定内容的结点 structstudent*DeleteNode(structstudent*head,intnum) {//删除学号等于num的结点 structstudent*p1,*p2; if(head==NULL) { printf("NULLlist"); returnhead; } p1=head; while(num! =p1->num&&p1->next! =NULL) { p2=p1; p1=p1->next; } if(num==p1->num) { if(p1==head) head=p1->next; else p2->next=p1->next; free(p1); } else printf("notbeenfound! "); returnhead; } 4>删除指定位置的结点。 要求: 在单链表中,删除第i个位置的结点。 算法提示: 从第一个位置往后查找第i个位置的结点,找到后执行删除操作。 注意: 考虑算法时需要考虑i是否合法。 6.插入结点 (1).后插: 插在指定结点p的后面 程序实现: q->next=p->next; p->next=q; (2).前插 1>.插在指定结点p的前面 该如何用程序实现? 2>.程序 structstudent*InsertNode(structstudent*head,structstudent*p,structstudent*s) {//程序功能: 将s所指向的结点插在p所指向结点的前面 structstudent*q; if(p==head)//插在第一个结点前面 { s->next=head; head=s; } else { q=head; while(q->next! =p) q=q->next; q->next=s; s->next=p; } returnhead; } (3).有序插入(按学生num由小到大顺序排列) structstudent*InsertNode(structstudent*head,structstudent*stu) {//stu指向待插入的结点,要求插入后保持num由小到大有序 structstudent*p0,*p1,*p2; p1=head; p0=stu; if(head==NULL) { p0->next=head; head=p0; } else { while((p0->num>p1->num)&&(p1->next! =NULL)) { p2=p1; p1=p1->next; } if(p0->num<=p1->num) { if(head==p1) head=p0; else p2->next=p0; p0->next=p1; } else { p1->next=p0; p0->next=NULL; } } returnhead; } (4)如何在指定位置(比如第i个位置)插入结点呢? 7.逆置单链表 structstudent*Invertlist(structstudent*head) { structstudent*p,*s; p=head; head=NULL; while(p) { s=p; p=p->next; s->next=head; head=s; } returnhead; } §4.用线性表表示集合 首先定义: typedefstructstudentLNode; typedefstructstudent*List; 1.已知利用LA和LB分别表示两个集合A和B,求A=A∨B ListUnion(Listla,Listlb) { LNode*p,*q; if(! la) { la=lb; returnla; } while(lb! =NULL) { p=lb; lb=lb->next; q=la; while(q! =NULL&&q->num! =p->num) q=q->next; if(q==NULL) { p->next=la; la=p; } else free(p); } returnla; } 2.已知线性表LA表示的集合A中含有重复元素,试构造一个纯集合(不含重复元素) voidPurge(Listla) { //算法: //p指向链表中结点,如果从头部到p扫描, //找到了和p内容相同的结点,则删除p所指向的结点。 //p从头部遍历到链表的尾部 LNode*p,*q,*r; if(la==NULL) return; r=la; p=r->next; while(p! =NULL) { q=la; while(q! =p&&q->num! =p->num) q=q->next; if(q! =p) {//如果找到了和p内容相同的结点,则删除p r->next=p->next; free(p); p=r->next; } else {如果没找到,则p和r同时往后移,r始终指向p的前趋 r=p; p=p->next; } } } 3.求集合的差: 假设集合A用单链表LA表示,集合B用单链表LB表示,设计算法求两个集合的差,即A-B。 算法思想: 由集合运算的规则可知,集合的差A-B中包含所有属于集合A而不属于集合B的元素。 具体做法是,对于集合A中的每个元素e,在集合B的链表LB中进行查找,若存在与e相同的元素,则从LA中将其删除。 voidDifference(ListLA,ListLB) {//注意: LA和LB均带头结点。 请注意带头结点时删除结点和不带头结点时删除结点的代码的区别 pre=LA;p=LA->next; while(p! =NULL) {q=LB->next; while(q! =NULL&&q->data! =p->data)q=q->next; if(q! =NULL) {r=p;pre->next=p->next;p=p->next;free(r); } else{pre=p;p=p->next;} } } 4.判别两个集合A和B是否相等。 算法: (1).将A复制到C (2).对B的每一个元素,删除C中与之相等的结点。 如果找不到相等的元素,则A和B不等。 (3).由第 (2)步后如果C不为空,则A! =B,否则A==B。 §5.有序表 1.用有序表表示集合,试构造纯集合 算法: 在有序表中,因为所有元素按顺序排列,所以如果结点相同,则必定相邻。 只要遍历链表,对每一个结点,查看紧接其后的结点是否与其相等,如果相等,则删除其后的结点。 voidPurge(Listla) { LNode*p,*q; if(la->next==NULL) return; p=la; q=p->next; while(p) { if(q) { if(p->num==q->num) { p->next=q->next; free(q); q=p->next; } else { p=q; q=p->next; } } else p=q; } } 2.有序表的合并 (1).ListMerge(Listla,Listlb) {//算法: 将lb的元素插入到la合适的位置上,返回la即可 //la,lb有头结点 LNode*pa,*pb,*pc; Listlc; pa=la->next; pb=lb->next; lc=pc=la;//用la的头结点做lc的头结点 while(pa&&pb) { if(pa->num<=pb->num) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->nex
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回顾 语言 指针