JJLin.
2021-11-08 18:14
采纳率: 100%
浏览 73

逐个输出单链表中所有数据元素。

  1. 定义一个单链表类(参照P45-P48),在此基础上添加如下成员函数:
    (1)编写一个成员函数:逐个输出单链表中所有数据元素。
    (2)编写一个成员函数:单链表定位操作。其定位功能为:在单链表中查找是否存在数据元素x,如果存在,返回单链表中和x值相等的第1个数据元素的序号(序号从0开始编号);如果不存在,返回-1。
    (3)编写一个成员函数:删除单链表中所有值为x的元素。
    (4)编写一个成员函数:就地逆置单链表中的数据元素。
    (5)编写一个成员函数:将单链表中数据元素就地排序。所谓就地排序是指在排序过程中利用原有的结点,不额外增加新结点。
    (6)编写一个成员函数:在单链表有序的前提下,插入一个数据元素x,要求插入后的单链表中数据元素从小到大有序排列。
  2. 将1按要求编写完成后,编写代码进行测试。
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

  • 2023预备级研究生 2021-11-09 11:58
    最佳回答
    定义一个单链表类
    typedef struct node
    { int data;
      struct node *next;
    }linklist;
    (1)逐个输出单链表中所有数据元素。
    void Printlist(linklist *q)
    {
      while(q)
      {
        printf("%d ",q->data);
        q=q->next;
      }
    }
    (2)单链表定位操作。其定位功能为:在单链表中查找是否存在数据元素x,如果存在,返回单链表中和x值相等的第1个数据元素的序号(序号从0开始编号);如果不存在,返回-1。
    int ListLocate_L(linkList L, ElemType x)
    {
        linkList p=L;
        int i=0;
        while(p->next!=0)
        {
           if(p->next->data==x){
               return i;
          } else{
           p=p->next;
           i++;
        } 
        return -1;
    ] 
    (3)删除单链表中所有值为x的元素。
    void delete_X(linkList L,int x){
        linkList p = L->next, pre = L, q; //p指针从第一个元素结点开始,pre指针从头结点开始
        while(p != NULL){
            if(p->val == x){
                q = p; //复制给辅助指针q用来释放空间
                p = p->next; //p往后遍历
                pre->next = p; //将pre->next指向当前p
                free(q); //上一个值为X的元素已经从链表中删除,释放结点空间
            } else {
                p = p->next; // 这里注意 p 和 pre都要后移,因为pre始终是p的前驱
                pre = pre->next;
            }
        }
    }
    
    (4)就地逆置单链表中的数据元素。
    linklist *InverseLinklist(linklist *q)
    {
         linklist *p,*head;
          p=head->next;
         if(p!=NULL) {
           p=p->next;
           head->next->next=NULL;       
         }
         while(p!=NULL){
           q=p->next;
           p->next=head->next;
           head->next=p;
           p=q;            
      }  
    }
    (5)将单链表中数据元素就地排序。所谓就地排序是指在排序过程中利用原有的结点,不额外增加新结点。
    
    void SortSingleList(listlist *head)
    {
        listlist *pre=head,*p=pre->next,*q,*r;    //pre指向head,p指向第一个元素
        q=p->next; //q指向待比较节点
        p->next=NULL;    //第一个节点next截止 NULL
        while(q!=NULL)
        {
            while(pre->next!=NULL && q->data>pre->next->data)//查找插入点的前驱节点
                pre=pre->next;
            r=q->next;    //保存待比较的下一个节点
     
            q->next=pre->next; 
            pre->next=q;    //插入节点
            
            pre=head;    //恢复pre的head
            q=r;    //q指向下一个待比较节点
        }
    }
    
    (6)在单链表有序的前提下,插入一个数据元素x,要求插入后的单链表中数据元素从小到大有序排列。
    linklist  *Insert(linklist *head,int x)
    {
         linklist  *s,*q;
         s=(linklist*)malloc(sizeof(linklist));
         s->data=x;
         q=head;
         if(q->data>x){
           s->next=q;
           head=s;
        }else{
          while(q!=NULL)
         {
            if(q->next->data>x){
              s->next=q->next;
              q->next=s;
              break;                
            }      
         q=q->next;
         }
        q=head;
       }
    }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题