c语言链表.docx

1、c语言链表#include stdio.h#include malloc.h /*包含动态内存分配函数的头文件*/#define N 10 /*N为人数*/typedef struct nodechar name20.struct node *link.stud.stud * creat(int n) /*建立单链表的函数，形参n为人数*/stud *p,*h,*s. /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/int i. /*计数器*/if(h=(stud *)malloc(sizeof(stud)=NULL) /*分配空间并检测*/printf(不能分

2、配内存空间!).exit(0).h-name0=0. /*把表头结点的数据域置空*/h-link=NULL. /*把表头结点的链域置空*/p=h. /*p指向表头结点*/for(i=0.in.i )if(s= (stud *) malloc(sizeof(stud)=NULL) /*分配新存储空间并检测*/printf(不能分配内存空间!).exit(0).p-link=s. /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/printf(请输入第%d个人的姓名,i 1).scanf(%s,s-name). /*在当前结点s的数据域中存储姓名*/s-link=NU

3、LL.p=s.return(h).main()int number. /*保存人数的变量*/stud *head. /*head是保存单链表的表头结点地址的指针*/number=N.head=creat(number). /*把所新建的单链表表头地址赋给head*/假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可。(p-link=s;s-link=q)，这样就完成了插入操作。下例是应用插入算法的一个例子：#include stdio.h#include

4、 malloc.h#include string.h#define N 10typedef struct nodechar name20;struct node *link;stud;stud * creat(int n) /*建立单链表的函数*/stud *p,*h,*s;int i;if(h=(stud *)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);h-name0=0;h-link=NULL;p=h;for(i=0;in;i+)if(s= (stud *) malloc(sizeof(stud)=NULL)printf(不能分配内

5、存空间!);exit(0);p-link=s;printf(请输入第%d个人的姓名:,i+1);scanf(%s,s-name);s-link=NULL;p=s;return(h);stud * search(stud *h,char *x) /*查找函数*/stud *p;char *y;p=h-link;while(p!=NULL)y=p-name;if(strcmp(y,x)=0)return(p);else p=p-link;if(p=NULL)printf(没有查找到该数据!);void insert(stud *p) /*插入函数，在指针p后插入*/char stuname20;s

6、tud *s; /*指针s是保存新结点地址的*/if(s= (stud *) malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);printf(请输入你要插入的人的姓名:);scanf(%s,stuname);strcpy(s-name,stuname); /*把指针stuname所指向的数组元素拷贝给新结点的数据域*/s-link=p-link; /*把新结点的链域指向原来p结点的后继结点*/p-link=s; /*p结点的链域指向新结点*/main()int number;char fullname20; /*保存输入的要查找的人的姓名*/

7、stud *head,*searchpoint;number=N;head=creat(number); /*建立新链表并返回表头指针*/printf(请输入你要查找的人的姓名:);scanf(%s,fullname);searchpoint=search(head,fullname); /*查找并返回查找到的结点指针*/insert(searchpoint); /*调用插入函数*/链表操作:建立、插入、删除、查找、倒置、删除等基本操作/喜洋洋制作#include#includetypedefstructLNode intdata; structLNode *next;LNode,*Llist

8、;LNode *creat_head();/创建一个空表void creat_list(LNode *,int);/创建一个长度为n的线性链表voidinsert_list(LNode *,int,int);/插入一个元素intdelete_list(LNode *,int);/删除一个元素intfound_list(LNode *,int);/链表查询void reverse(LNode *);/倒置整个链表voiddelete_whole(LNode *);/删除整个链表voidprint_list(LNode *);/打印链表main() LNode *head; int n,n2; i

9、ntx,i;int b; char temp1,temp2;head=creat_head();printf(请输入链表的节点个数n=);scanf(%d,&n);printf(n请输入数据：n);creat_list(head,n);/创建链表 print_list(head);printf(n*n); printf(n下面进行链表插入元素n); printf(n请输入您需要插入的元素x=);scanf(%d,&x);printf(n请输入即将插入的位置 i=);scanf(%d,&i);insert_list(head,x,i);/插入元素print_list(head);printf(n

10、*n); printf(n下面进行链表删除元素n); printf(n请输入即将删除元素的位置：i=);scanf(%d,&i);b=delete_list(head,i);/删除元素print_list(head);printf(nn成功删除元素：%d,b);printf(n*n); printf(n下面进行链表查询n); printf(n请输入即将查询的元素：x=);scanf(%d,&n2);if(found_list(head,n2)0) /链表查询 printf(找到了，在第%d的位置上,found_list(head,n2);else printf(没有找到!);printf(n*

11、n);printf(n是否倒置整个链表？Y/Nn); fflush(stdin); scanf(%c,&temp1);if(Y=temp1) /倒置链表 reverse(head); print_list(head);printf(n*n); printf(n是否删除整个链表？Y/Nn);fflush(stdin); scanf(%c,&temp2);if(Y=temp2) /删除链表 delete_whole(head);printf(n成功删除整个链表n);/创建一个空链表LNode *creat_head() LNode *p;p=(Llist)malloc(sizeof(LNode);

12、 if(NULL=p) printf(内存申请失败！); else p-next=NULL;return(p); /创建一个长度为n的线性链表voidcreat_list(LNode *head,int n) LNode *p,*q; inti; p=head;for(i=1;idata); q-next=NULL; p-next=q; p =q; /插入一个元素voidinsert_list(LNode *head,intx,inti )int j=0; LNode *p,*s; p=head;while(p!=NULL)&(jnext; j+; if(p=NULL) exit(0);s=(

13、Llist)malloc(sizeof(LNode); if(NULL=p) printf(内存申请失败！); else s-data=x; s-next=p-next; p-next=s; /删除一个元素intdelete_list(LNode *head,inti)LNode *p,*q; int j=0; int x;p=head;while(p!=NULL)&(jnext; j+; if(p=NULL) exit(0);q=p-next; p-next=q-next; x=q-data; free(q); q=NULL; return(x);/删除整个链表voiddelete_whol

14、e(LNode *head) LNode *p,*q; p=head; while(p!=NULL) q=p-next; free(p); p=q; /倒置链表void reverse(LNode *head) LNode *p,*s,*t; p=head; s=p-next; while(s-next!=NULL)/主要置换过程 t=s-next; s-next=p; p=s; s=t; s-next=p; head-next-next=NULL;/收尾 head-next=s;/赋头 /打印链表voidprint_list(LNode * head) LNode *p; for(p=head-next;p!=NULL;) printf(%d ,p-data); p=p-next; /链表查询intfound_list(LNode *head,int n) LNode *p; inti=1;for(p=head-next;p!=NULL;) if(n=p-data) returni; i+; p=p-next; if(NULL=p) return 0;