cl二级C-指针和链表jsleyx.docVIP

Author: 铁沙船指针和链表1.结构体1.声明结构体类型 struct 结构体名成员列表例: struct student int num; char name20; int age; float score;2.定义变量 (1).先定义类型再定义变量如:类型如上定义,变量定义为：struct student student1,student2 (2).定义类型的同时定义变量 struct 结构体名成员列表变量列表; (3).注:成员也可是结构体变量 如：struct date int month; int day; int year;struct studentint num; struct date birthday; 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).指针变量的定义 专门用来存放另一变量的地址的变量，称为指针变量。它的值为指针(地址)。int i,j; int *pointer1,*pointer2;pointer1=&i;ipointer1jPointer2pointer2=&j; 注:一个指针变量只能指向同一个类型的变量. (3).指针变量的引用. int a;int *p;a=10;p=&a;prinf(%d,*p);请指出以下的含义:1 &*p2 *&a3 *p+ 相当于*(p+) (4).例:输入a和b,按先大后小顺序输出 main() int *p1,*p2,*p, a, b; scanf(%d,%d,&a,&b); p1=&a; p2=&b; if(a.*p=1; /数组第0个元素赋值为1 2.p+i和a+i就是&ai 3.*(p+i)或*(a+i)是ai 4.例：输入数组全部元素。 main() int a10; int *p,i; for(i=0;i10;i+) scanf(%d,&ai); for(p=a;p.注意指针变量的当前值。 main() int *p,i,a10; p=a; for(i=0;i10;i+) scanf(%d,p+); p=a; for(i=0;i.概念问题： 如果有int a10; int *p=a; 则： 1p+; /p指向a1 2*p+; /作用是先得到*p,然后再使p+1=p 3*(p+); /先取*p的值，p再加1，和2等同 *(+p); /先使p+1，再取*p 4(*p)+; /即(a0)+(4).数组作函数参数 如果函数中将数组的值改变，那么在调用该函数的地方，数组值也变了。（具体略） 4指向结构体类型数据的指针 (1).指向结构体变量的指针 main() struct student int num; float score; struct student stu, *p; p=&stu; stu.num=10; stu.score=89.5; printf(%d,%f,(*p).num,(*p).score) 注：(*p).num等价p-num (2).指向结构体数组的指针 struct student stu3=101,75,102,89.5,103,92; struct student *p; for(p=stu;pnum,p-score) (3).用指向结构体的指针作函数参数 用指针作实参，将结构体变量的地址传给形参，避免大量数据的复制。3.用指针处理链表1概述： 存储数据元素存储后继结点 存储地址数据域指针域 (1).结点定义： struct student int num; float score; struct student *next; (2).分配和释放结点空间void *malloc(sizeof(struct student); /在系统内存中分配存储单元，并返回该空间的基址free(p); /将指针变量p所指示的存储空间，回收到系统内存空间中去p结点p调用free(p)之前调用free(p)之后（3）链表的概念用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的。101010121014101610181020102210241026内存中保存的信息如下：a4a3a1a2 0101010241014 图示表示如下：ai-1aia2a1ai+1head2建立链表 (1).写一函数建立一学生单向链表（从尾部插入） int n;struct student *create() struct student *head; struct student *p1,*p2; n=0; p1=p2=(struct student*)malloc(sizeof(struct student); 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=(struct student*)malloc(sizeof(struct student); /p1指向新结点 scanf(%d,%f,&p1-num,&p1-score); p2-next=NULL; /切记：最后一个结点的next赋值为NULL return head; (2).从头部开始插入 将while循环改成： while(p1-num!=0) p1-next=head; head=p1; p1=(struct student*)malloc(sizeof(struct student); scanf(%d,%f,&p1-num,&p1-score);则变成以下形式：struct student *create() struct student *head; struct student *p1,*p2; n=0; p1=p2=(struct student*)malloc(sizeof(struct student); scanf(%d,%f,&p1-num,&p1-score); head=NULL; while(p1-num!=0) p1-next=head; head=p1; p1=(struct student*)malloc(sizeof(struct student); scanf(%d,%f,&p1-num,&p1-score);return head;这里为什么不需要把最后一个结点的next赋值为NULL？head (3).有头结点的链表1.在单链表的第一个结点之前附设一个结点，称为头结点.ai-1aia2a1ai+1 nan 头结点 增加头结点有什么好处？请看后面的例子。2.从尾部插入生成链表 struct student *create() struct student *head,*p1,*p2; p1=p2=(struct student*)malloc(sizeof(struct student); head=p1;/p1指向头结点 p1=(struct student*)malloc(sizeof(struct student); scanf(%d,%f,&p1-num,&p1-score); while(p1-num!=0)由于插入位置不可能在最前面，所以这里比没有头结点时大大简化 p2-next=p1; p2=p1; p1=(struct student*)malloc(sizeof(struct student); scanf(%d,%f,&p1-num,&p1-score); p2-next=NULL; return head;3遍历链表（两种应用举例） (1).输出： p=head;while(p!= NULL) printf(%d,%fn,p-num,p-score); p=p-next;遍历的关键语句：while(p!= NULL)/do somethingp=p-next; (2).求长度 p=head;k=0;while(p) k+; p=p-next;printf(the length is %d,k);4查找元素（查找学生） struct student *Locate(struct student *head,struct student stu) struct student *p; p=head; while(p&p-num!=stu.num) /注意循环结束条件等价于while(p)if (p-num = stu.num)break;p=p-next; p=p-next; return p;5删除结点 1.删除p所指的结点headzyxwpq删除前 yxzpheadq删除后w这是删除结点的关键语句。不论什么时候，要删除一个结点，我们可以先用p指向该结点，然后想办法用q指向它的前趋，调用这个语句即可删除该结点。但，如果p是第一个结点，也就是没前趋时，该怎么办？程序实现： q-next = p-next; free(p); /该语句用来释放占用的内存资源，即使没这个语句，结点也被从链表中删除 2.程序 struct student *DeleteNode(struct student *head,struct student *p)/针对不带头结点的链表做删除操作/程序功能：head指向链表，删除p所指向的结点 struct student *q; if(p=head) head=p-next; else q=head; while(q-next!=p) q=q-next; q-next=p-next; free(p); return head; 3.删除指定内容的结点 struct student *DeleteNode(struct student *head,int num)/删除学号等于num的结点 struct student *p1,*p2; if(head= NULL) printf(NULL list); return head; 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(not been found!); return head;6插入结点 (1).后插：插在指定结点p的后面wwheadzyxpheadyxzpaq 程序实现：这是将结点插在另一个结点之后的关键语句。 q-next=p- next; p- next =q; (2).前插 1.插在指定结点p的前面wwheadzyxpheadyxzpaq该如何用程序实现？ 2.程序 struct student *InsertNode(struct student *he