《关于单链表的操作》由会员分享,可在线阅读,更多相关《关于单链表的操作(7页珍藏版)》请在金锄头文库上搜索。
1、关于单链表的操作单向链表结构描述示例: struct linklist int data;struct linklist *next; ; struct linklist *head;单链表的建立 在链表的操作中用到的几个函数: (1)malloc(size)在内存的动态存储区申请一个长度为 size 字节的连续 空间。并将此存储空间的起始地址作为函数值返回。malloc 函数的原型为:void *malloc(unsigned int size) 函数值为指针(地址),这个指针是指向 void 类型的,也就是不规定指向 任何具体的类型。如果内存缺乏足够大的空间进行分配,则 malloc 的函
2、数值为 “空指针”。 (2)calloc(n, size)在内存的动态存储区申请 n 个长度为 size 字节的 连续空间,函数返回值为分配空间的首地址。若此函数未被成功执行,函数返 回值为 0。函数返回值为该空间的首地址。其函数原型为:void *calloc(unsigned int n,unsigned int size) (3)free(p)释放由指针 p 所指向的存储单元,而所释放的存储单元的大 小是最近一次调用 malloc()函数或 calloc()函数时所申请的存储空间。fr ee 函数的原型为:void free(void *ptr) 系统可以回收所释放的空间,另行分配作为它
3、用。 (4)realloc 函数。其函数的原型为:void realloc(void *ptr,unsigned int size) 其作用是将 ptr 所指向的存储区(原先用 malloc 函数分配的)的大小改为 size 个字节。可以使原先分配区扩大和缩小。它的函数返回值是一个指针,即 新的存储区的首地址。 例 1 使用表首插入法表首插入法建立链表。 表首插入法建立链表,这种方法的特点是:新产生的结点作为新的表头插 入链表。 #include void main() struct linklist int data;struct linklist *next; ; struct linkl
4、ist *head,*p; /*head 头指针,p 申请单元指针*/ head=NULL; /*空链表*/*申请空间,并将指针 p 强制转换成所指向的结构体类型*/ p=(struct linklist*)malloc(sizeof(struct linklist); scanf(“%d“, scanf(“%d“, if(head=NULL) printf(“n list null!n“); return(head); p1=head; while(num!=p1-num p1=p1-next; if(p1!=NULL)printf(“find:%d,%6.2fn“,p1-num, p1-s
5、core); else printf(“%d not found!n“,num); 说明:一般查找操作总是与其它相关操作相联系的。如:插入、删除操作 等,故在查找的过程中,设置了两个工作指针 p2 与 p1,p1 指向要查找的结点 ,p2 指向要查找结点的左边的一个结点。以方便进行插入和删除操作。 例 3 假设链表结点信息包括学生学号、成绩,结点定义如下: typedef struct plist int no; float score; struct plist *next; plist; 设已经建立了两个具有上述结构的链表,且两个链表都是以学号升序排列 ,要求编写一个函数,将两个链表(按升
6、序)合并。 算法: 函数应有两个链表指针形参:p1, p2 指向它们各自的表头; 最初链表的头指针 head=NULL,新链表的当前结点指针 p=NULL; 产生新链表的头结点; 当两个链表的指针均没指向表尾,则依次选择两个链表中的结点并入到 新链表中; 当某一个链表已到表尾,则将另一个链表的剩余部分直接链接到新链表 的表尾。 完成此功能的程序为: plist *merge(plist *p1, plist *p2) /*p1 与 p2 分别为两个链表的头指针*/ plist *p, *head; if(p1-nono ) head=p=p1; p1=p1-next; /*产生新链表的头结点*
7、/ else head=p=p2; p2=p2-next; while(p1!=NULL /*p1 指示的结点并入到新链表*/ p=p1; /*p1 指向新链表的表尾*/ p1=p1-next; /*p1 指向后继*/ else p-next=p2; /*p2 指示的结点并入到新链表*/ p=p2; p2=p2-next; /*p2 指向后继*/ if(p1!=NULL) /*p1 没有到达表尾*/ p-next=p1; /*p1 指示的链表后部分链接新链表的表尾*/ else p-next=p2; /*p2 指示的链表后部分链接新链表的表尾*/ return head; 循环 while(p
8、1!=NULL &p2!=NULL)终止时,表示有 p1 指示的链表为空或 p 2 所指示的链表为空,再只将另一非空的链表(p2 指示的链表或 p1 所指示的链 表)链入到新链表中即可。 例 4 用链表实现若干学生的成绩处理,求出学生人数、每个学生的总成 绩及平均成绩。 算法: 每个学生包括姓名与 8 门课程成绩,用一链表存放,总成绩、平均成绩 亦存放于链表。 若输入学生姓名为“x”,则数据结束。建立成绩链表的同时求出学生人 数(链表结点数)、每个学生的总成绩及平均成绩。 建立成绩链表和输出成绩链表,分别用函数完成。 程序如下: #include #define NULL 0 struct l
9、inkllist char *name;float cj8;float tcj, avcj;struct linklist *next; ; int num; void main() struct linklist *creathead();void print();struct linklist *h;h=creathead( );/*调用 creathead()函数建立成绩链表,返回头指针*/printf(“%d 个学生成绩数据: n“, num);print(h); /*调用 print( )函数输出成绩链表*/ struct linklist *creathead() /*头插法建立成
10、绩链表*/ struct linklist *head,*p;int i;num=1;p=(struct linklist *)malloc(sizeof(struct linklist);scanf(“%s“,p-name);p-tcj=0;for(i=0;icji);p-tcj+=p-cji; p-avcj=p-tcj/8; head=NULL; while(strcmp(p-name,“x“)!=0) p-next=head;head=p;num+; p=(struct linklist *)malloc(sizeof(struct linklist) ;scanf(“%s“,p-nam
11、e);if(p-name!=x)for(i=0;icji);p-tcj+=p-cji; p-avcj=p-tcj/8;return(head); void print(struct linklist *head) /*输出成绩链表*/ struct linklist *p;p=head;while(p!=NULL)printf(“%s“, p-name);for(i=0; icji);printf(“%8.2f, %8.2f“, p-tcj, p-avcj);p=p-next; 注意两点: 将链表作为参数传递进函数,只需将链表表头指针传递进函数。函数的 形参对应实参的头指针。 对链表的访问用循环条件控制,循环的条件是结点的指针域非空。