原创 线性表 及在ucos中的应用 1(链表)

2. 单链表

2.1单链表的结点结构

typedef struct node

{

      int  nodedata;

      struct node  *next;

}linklist;

2.2建立单链表

(1) 头插法

 linklist * Creatlist_Frontinsert()

{

char ch,i;

      linklist *head,*p;

      head=NULL;        //head指向空

      ch=getchar();     //获得第一个字符

      for(i=0;i<10;i++)

      {

            p= (linklist *)malloc(sizeof(linklist));     //给新链表的node分配空间

            p->nodedata=ch;                    //给 .nodedata 赋值

            p->next=head;                       //头插法，把P放到head前面

            head=p;   //head 再指向P，即上一句中p为头，这一句再把head作为头

            ch=getchar();                        //获得每一次的字符

      }

   return   head;                             //返回头指针

}

(2)尾插法

 linklist * Creatlist_Endinsert1()

{

      char ch,i;

      linklist *head,*p, *end;

      head=NULL;

      end=NULL;

      ch=getchar();

      for(i=0;i<10;i++)

      {

            p= (linklist *)malloc(sizeof(linklist));

            p->nodedata=ch;

            if(head==NULL)                   

            {

                  head=p;         //如果链表是空的，直接head指向P                 

            }

            else

            {

                  end->next=p;       //如果链表不是空的，那么尾指针的.next指向P

            }

      end=p; //尾指针end 指向p,尾指针后移了，因为尾指针始终指向最后一个node

            ch=getchar();

      }

      if(end!=NULL)

      {

            end->next = NULL;       //非空链表的话尾指针的.next指向NULL。  

                                          //    空链表本来就指向NULL，就不在重新说明了

      }

   return   head;

}

上面的尾插法有点复杂了，考虑了空和非空链表的情况，如果给链表带一个头结点（实际什么都不干），那么就会简单很多。

(3) 尾插法(带头结点的)

 linklist * Creatlist_Endinsert2()

{

      char ch,i;

      linklist *head,*p, *end;

      head = (linklist *)malloc(sizeof(linklist));          //申请空间建立头结点

      end=head;         //end 初始化指向head

      ch=getchar();

      for(i=0;i<10;i++)

      {

            p= (linklist *)malloc(sizeof(linklist));

            p->nodedata=ch;

            end->next = p;

            end=p;

            ch=getchar();

      }

      end->next = NULL;

      return head;

}

2.3 插入运算

int  ListInsert(linklist *head,int i, int x)

{

      int j=0;

      linklist *p;   //用于查找

      linklist *s;  //用于指向插入的结点

      p=head;

      while(j<i-1&&p->next!=NULL)</i-1&&p->

      {

            p=p->next; //沿链表逐个扫描，直到i-1 ，P这个时候指向要插入的位置的前一个

            j++;

      }

      if(j!=i-1) 

      {

          return 0;

      }

      s=(linklist *)malloc(sizeof(linklist));

      s->nodedata=x;

      s->next=p->next;

      p->next = s;

      return 1;

}

2.4删除运算

int ListDelete(linklist *head,int i)

{

      int j=0;

      linklist *p;   //用于查找

      linklist *s;  //用于指向要删除的结点

      p=head;

      while(j<i-1&&p->next!=NULL)</i-1&&p->

      {

            p=p->next; //沿链表逐个扫描，直到i-1 ，P这个时候指向要要删除节点的前一个

            j++;

      }

      if((j!=i-1)||p->next == NULL) 

      {

          return 0;

      }

      s=p->next;

      p->next=s->next;

      free(s);

      return 1;

}

单链表特点：只有后继没有前趋