第9章 链表.ppt

C++语言程序设计; 0050; 0050; 0050; 0050; 0050;算法分析: 假设输入的学号为0时，表示建立链表的过程结束，该结点不应链接到链表中。根据题目要求，链表中结点数据应采用结构体类型来描述。 同时定义三个指针变量head，p1，p2，它们都是结构类型的指针变量。结构指针变量head的初值为NULL(即等于0),此时是空链表(head不指向任何结点,链表中无结点)，当链表建成后，应使head指向第一个结点。;建立链表的过程: ①首先利用malloc函数，在内存中开辟一个存储空间,用来存放新结点。使p1,p2都指向该存储空间,然后从键盘上输入一个学生的数据进行判断,如果输入的p1-num不等于0，而且是第一个结点数据（n＝1）,则把p1的值赋给head(head=p1),这样，结构指针head就指向了链表中的第一个结点。; ; ; ; ; ; ; ; ;struct student * creat( ) { student *head,*p1,*p2; int n=0; 　 head = NULL; //在没有创建任何结点时，表头指向空 p1 = （ struct student * ）malloc(sizeof(struct student)); //创建一个新结点 -------（1） 　 p2 = p1; 　 　 scanf(“%ld%f”,p1-num,p1-score); /*输入第一个结点的学生数据*/; ;　while(p1-num != 0) // ------------（2） 　{ n ++; 　 if (n == 1) head = p1; // 将链表中第一个新建结点作为表头 else{ p2-next = p1; p2 = p1; } 　 p1 = new(student); // 新建一个结点 　 cinp1-nump1-score; } delete p1; 　 p2-next =NULL; return head;　 //返回表头指针 }//end creat; ; ; ; ; 输出链表就是将链表中各结点的数据依次输出。首先要知道链表第一个结点的地址，也就是要知道表头结点head的值,然后依次通过各结点next的值找到下一个结点，就可以依次输出所有结点的数据，直到链表的尾结点为止。; ; ; 对链表的删除操作是把某个结点从链表中摘除,并不是真正从内存中将这个结点删除掉，使它脱离原来的链表，解除原来的链接关系。; 执行过程：设两个指针p1和p2,先使p1指向第一个结点。如果p1所指的结点不是要删除的结点,就将p2指向p1所指的结点(p2=p1),然后将p1指向下一个结点(p1=p1-next)。再继续判断p1所指的结点是不是要删除的结点,如此重复,直到找到要删除的结点并将其删除或是检查完全部链表为止。; ; ;struct student *dele(struct student *head, long num) { struct student *p1, *p2; if (head==NULL) { printf(list null\n); return head; } p1=head; while(p1-num!=nump1-next!=NULL) { p2=p1; p1=p1-next; }//查找位置 if (num==p1-num) { if(p1==head) head=p1-next; else p2-next=p1-next; printf(delete:%ld\n,num); n=n-1; } //删除成功，记录个数减一 else printf(“%ld not been found!\n”,num); return(head); }; 对链表的插入是指将一个结点插入到一个已有的链表中。为简单起见，假设有一个学生链表，各结点已按其成员学号（num）的值由小到大顺序排列，现在要插入一个学生的结点，要求按学号的顺序插入。 ; 过程实现：;