[c study]链表练习小记

c程序设计，chapter11

链表操作

链表单位 struct student

1.创建动态链表

p1:指向当前创建的结点

p2:指向链表末尾

从键盘读入新节点，0，0表示输入结束，每次输入，创建新的结点(p1指向),并且将p2后移。

struct student *create()
{
       struct student *head;
       struct student *p1;
       struct student *p2;
       p1=(struct student *)malloc(LEN);
       p2=(struct student *)malloc(LEN);
       p1=p2;
       head=NULL;
       scanf("%d,%d",&p1->number,&p1->score);
       while(p1->number!=0)
       {
           n=n+1;
           if(n==1) head=p1;
           else p2->next=p1;
           p2=p1;
           p1=(struct student *)malloc(LEN);（动态创建）
           scanf("%d,%d",&p1->number,&p1->score);
       }
       p2->next=NULL;
       return (head);
}

 

2.链表删除操作

p1:寻找待删除节点

p2:指向待删除节点的前一个节点

从头指针开始搜索，移动指针，遇到符合条件的节点即删除。

注意程序的周全性：如果实参头指针为空，提示操作不可执行。

struct student *del(struct student *head,int num)
{
     if(head==NULL)
        printf("the list is null \n");
     struct student *p1,*p2;
     p1=p2=head;
     int flag;
     while(p1->next!=NULL)
     {
        if(p1->number==num)
        {
           n=n-1;
           flag=1;
           if(p1==head)
           {
              head=p1->next;
              p1=p2->next;
           }
           else
           {
               p2->next=p1->next;
               p1=p2->next;
           }
        }
       else
       {
          p2=p1;
          p1=p1->next;
       }
       
     }
     if(p1->number==num)
        p2->next=NULL;
     if(flag==0)
        printf("can not find the node \n");
     return (head);
}

3.链表插入操作

p1:寻找插入位置（插入在此位置的前面）

p2:指向插入位置的前一个节点

while循环移动指针寻找插入位置

三种特殊情况：

head为空

插入位置为链表头

插入位置为在链表尾后

struct student *insert(struct student *head,struct student *newstu)
{
     struct student *p1,*p2;
     p1=head;
     p2=head;
     n=n+1;
     if(head==NULL)
     {
        head=newstu;
        newstu->next=NULL;
    
     }
     while((p1->next!=NULL)&&(newstu->number>p1->number))
     {
        p2=p1;
        p1=p1->next; 
     }
     if(p1==head)
     {
        newstu->next=p1;
        head=newstu;
   
     }
     else if(newstu->number>=p1->number)
     {
                                 
         p1->next=newstu;
         newstu->next=NULL;
     }
     else
     {
         p2->next=newstu;
         newstu->next=p1;
     }
     return (head);
}

 

4.链表打印

void print(struct student *head)
{
     struct student *p1;
     p1=head;
     if(head==NULL)
       printf("list empty\n");
     else
       printf("the %d records are:\n",n);
     while(p1!=NULL)
     {
        printf("%d,%d\n",p1->number,p1->score);
        p1=p1->next;
     }
}

 

5.测试

int main()
{
    struct student *head,*stu;
    int del_num;
    printf("input records:\n");
    head=create();
    print(head);
    printf("input the deleted number:\n");
    scanf("%d",&del_num);
    head=del(head,del_num);
    print(head);
    printf("input the inserted record:\n");
    stu=(struct student *)malloc(LEN);
    scanf("%d,%d",&stu->number,&stu->score);
    head=insert(head,stu);
    print(head);
    _getch();
}