10.5.2 链表的操作VIP

1、LOGOLOGO链表的基本操作（建立、输出、插入新结点、删除结点）Teacher teaching designCONTENTS 目 录链表的创建链表的结点插入链表的结点删除链表的输出创建单向链表PART 01 定义链表的数据结构。创建一个空表将新结点的指针成员赋值为空。若是空表，将新结点连接到表头；若是非空表，将新结点接到表尾。判断一下是否有后续结点要接入链表，若有转到3 )，否则结束。12344创建单向链表利用malloc( )函数向系统申请分配一个结点。5分两步走一是先把头指针head赋值给新结点的指针成员，让新结点成为第一个结点；再把新结点的地址赋给头指针head成为链表的第一个结点。

2、链首入链方式是将新结点的地址赋值给最后一个结点的指针成员，因此设置一个尾指针rear指针链表的最后一个结点，为新结点作准备。将新结点入链后，新结点成为最后一个结点，不断更新尾指针的指向，让rear指向新入链的结点。链尾入链创建单向链表建立一条单向链表并输出各结点的值，链表除了有一个指针成员之外，只有一个整型成员，数据由用户输入。(采用链首入链的方式)添加标题内容struct number int n; struct number *next; ; /*定义链表的数据结构*/#define LEN sizeof(struct number) /*宏定义*/struct number *creat

3、（） /*建立链表函数*/ struct number *head,*p;/*定义指向链表的指针变量*/ int a;char ch; head=NULL;printf(“是否输入结点的数据？(Y/N)”); while(toupper(ch=getche()=Y)/*循环一次，连接一个结点*/ p=(struct number *)malloc(LEN);/*分配新结点单元*/ printf(“n输入”); scanf(“%d”,&p-n); p-next=head; /*新结点指向原来的首结点*/ head=p; /*新结点成为新的首结点*/ printf(“是否继续输入结点的数据

4、？(Y/N)”);return (head);创建单向链表struct node /*链表节点的结构* / int num; struct node *next; ;struct node *creat(struct node *head) /*函数返回的是与结点相同类型的指针*/struct node *p1,*p2;p1=p2=(struct node*) malloc(sizeof(struct node); /*申请新结点*/scanf(%d,&p1-num) ; / * 输入结点的值* /p1-next=NULL; / * 将新结点的指针置为空* /while(p1-num0

5、) / * 输入节点的数值大于0 * /if (head=NULL) head=p1; / * 空表，接入表头* /else p2-next=p1; / * 非空表，接到表尾* /p2 = p1 ;p1=(struct node *)malloc(sizeof(struct node); 申/请* 下一个新节点*/scanf(%d,&p1-num); / *输入结点的值* /return head; /*返回链表的头指针* /创建一个存放正整数（输入-999做结束标志）的单链表在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后

6、，要返回一个链表头结点的地址，即头指针。采用链尾入链的方式struct number *creat() struct number *head,*p,*rear; int count=0; char ch; head=NULL;reat=NULL;printf(“是否输入结点的数据？(Y/N)”);while(toupper(ch=getche()=Y)/*循环一次，连接一个结点*/ p=(struct number *)malloc(LEN);/*分配新结点单元*/ printf(“n输入”); scanf(“%d”,&p-n); p-next=NULL; if(count=0) h

7、ead=p; rear=p else rear-next=p; rear=p; count+;printf(“是否继续输入结点的数据？(Y/N)”);return head;链表的插入PART 02structint num; /*学生学号* /char str20; /*姓名* /struct node *next; ;首先定义链表的结构链表的插入链表的插入有三种情况插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表，则插入的节点依次与表中节点相比较，找到插入位置。由于插入的节点可能在链表的头，会对链表的头指针造成修改，所以定义插入节点的函数的返回值定义为返回结构体类型的指针

8、。链表的插入if (nnum) / *找到插入位置* /if (head=p2) / * 插入位置在表头* /head=p1;p1-next=p2;else /*插入位置在表中* /p3-next=p1;p1-next=p2;else /*插入位置在表尾* /p2-next=p1;p1-next=NULL;return(head); / * 返回链表的头指针* /结点的插入函数struct node *insert(head,pstr,n) struct node *head; / *链表的头指针* /char *pstr;int n; struct node *p1,*p2,*p3;p1=(

9、struct node*)malloc(sizeof(struct node);strcpy(p1-str,pstr); / * 写入节点的姓名字串* /p1-num=n; / * 学号* /p2=head;if (head=NULL) / * 空表* / head=p1; p1-next=NULL;/ *新节点插入表头* / else /*非空表* /while(np2-num&p2-next!=NULL)p3=p2 ;p2=p2-next; / * 跟踪链表增长* /在前例形成链表的基础上，插入一个新结点，则需要先定位其插入点。例：生成一个结点并输入其成员n的值，将其插入到已建好链

10、表中第一个值大于新结点n值的结点前面。链表的插入（第二种情形）插入的结点位置在最后语句是：p-next=NULL;表示将新结点的指针域成员置为NULL；q1-next=p;或者q2-next-next=p;让前一个结点指向新结点；（第一种情形）插入的结点在中间位置，则插入语句为：p-next=q1;表示让新结点指向后一个结点；q2-next=p;表示让前一个结点指向新结点；链表的删除PART 03为了删除单链表中某个结点，可设置两个活动指针，从链首到链尾搜索待删的结点的前驱结点，然后将此前驱结点的指针域指向待删结点的后继结点，最后释放被删结点所占存储空间即可。链表的删除struct numbe

11、r *delete(struct number *head) struct number *p1,*p2,*q1,*q2; p1=head; q1=head; while(q1!=NULL) if（p1-nq1-n） p1=q1;p2=q2; q2=q1; q1=q1-next; if(p1=head) head=p1-next;/*要删除的是第一个结点*/ else p2-next=p1-next;/*待删结点的前一个结点指向待删结点的后一个结点。*/ return (head);删除函数编写在链表中搜索成员n值最小的结点，将该结点删除链表的删除void delete_node(struct

12、 node *h，int i)/*在带头结点的单链表中删除第i个结点*/struct node *p,*q;int k=0; p=h;while (p!=NULL&knext;k+;if (k!=i-1) printf(“删除结点的位置i不合法”);else q=p-next; p-next=q-next; free(q);在带头结点的单链表中，删除其第i个结点，如果第i个结点不存在，则输出信息：“删除结点的位置i不合法。链表的删除案例分析交流提升PART 04建立如图所示的存储结构（即每个节点两个域，data是数据域，next是指向节点的指针域，请将定义补充完整）。struct no

13、de char data;_; ;解析1struct node * next;答案2添加标题内容链表中结点的数据类型通常是结构体类型，除了各种类型的数据成员外，必须有一个特殊的成员：指向相同结构体数据的指针变量以下程序运行后的输出结果是（ ）。struct NODE int num; struct NODE *next;main() struct NODE s3=1, 0,2, 0,3, 0, *p, *q, *r; int sum=0; s0.next=s+1;s1.next=s+2;s2.next=s; p=s; q=p-next; r=q-next; sum+=q-next-num;sum+=r-next-next-num; printf(%dn, sum); 案例分析 交流提升已知head指向单链表的第一个节点，以下程序调用函数print输出这一单向链表。请在选择正确内容填空。struct student int info; struct student *link; ; void print(struct student * he