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;
   }
}
    评论
    解决 无用
    打赏 举报

报告相同问题？

提交

相关推荐 更多相似问题