线性表之单链表编程系列复习题+834考点复习

痛定思痛。 2022-01-21 07:11 88阅读 0赞

834数据结构单链表考纲要求：

*   单链表的算法：生成先进先出单链表（尾插法），后进先出单链表（头插法）
 *   单链表的算法：生成不带表头的递增有序单链表，生成带表头的递增有序单链表
 *  单链表的算法：在指定位置插入一个新结点；删除指定值的结点；在指定位置删除一个结点；
 *  单链表的合并：两个递增有序的单链表合并成一个递增有序的单链表

--------------------

**1、建立单链表**

**LinkList**类型声明；

typedef struct LNode
    {
        ElemType data;      //数据域
        struct LNode *next;  
    }LinkList;              //用于声明单链表节点的类型

头插法：生成的链表中节点的顺序和原数组元素的顺序相反

void CreateListF(LinkList *&L,ElemType a[],int n)
    {
        LinkList *s;
        int i ;
        L=(LinkList *)malloc(sizeof(LinkList));   //创造头节点
        L->next=NULL;
        for(i=0;i<n;i++)
        {
            s=(LinkList *)malloc(sizeof(LinkList));  //创造新节点
            s->data=a[i];
            //头插法插入
            s->next=L->next;
            L->next=s;
        }
    }

尾插法：需增加一个尾节点指针r，初始时指向头节点，后一直指向当前链表的最后一个节点

LinkList *s,*r;
        int i ;
        L=(LinkList *)malloc(sizeof(LinkList));   //创造头节点
        L->next=NULL;
        r=L;                         //初始时尾指针指向头节点
        for(i=0;i<n;i++)
        {
            s=(LinkList *)malloc(sizeof(LinkList));  //创造新节点
            s->data=a[i];
            //尾插法插入
            r->next=s;
            r=s;   //r=r->next;
        }

**2、插入节点（指针s指向待插入的节点）**

主体语句为：

s->next=p->next;
    
    p->next=s;

3、**删除节点**

先找到待删除节点的前一个节点指针，修改其指向，再删除节点

p->next=p->next->next;

4、**有序单链表的归并算法**

答：将两个次序相同的有序链表L1、L2归并为一个有序链表L3，在空间复杂度为O(1)条件下实现

void merge(LinkList *L1,LinkList *L2,LinkList *&L3)
    {
        LinkList *p=L1->next,*q=L2->next;
        L3=L1;                         //将L1的头节点作为L3的头节点
        free(L2);                     //释放L2的头节点
        r=L3;
        while(p!=NULL&&q!=NULL)
        {
            if(p->data<q->data)        //链*p
            {
                r->next=p;
                r=r->next;
                p=p->next;
            }
            else                      //链*q  
            {
                r->next=q;
                r=r->next;
                q=q->next;
            }
        }
         //将未遍历的余下节点链接到L3中
        if(q!=NULL)                
            p=q;
        r->next=p;
    }

5、**编程题1：有一个有序单链L(从小到大排序)**

**设计算法使插入一个元素为x的节点后，该表仍然有序**

**答：思路---**首先新建节点s，用循环遍历链表查找节点的插入位置，用pre指针指向（“接收”）待插入位置，最后用头插法插入，不可用尾插法，因为后面可能还有节点

void inorderList(LinkList *&L,ElemType x)
    {
        LinkList *s,*pre,*p;
        s=(LinkList *)malloc(sizeof(LinkList));
        s->data=x;
        s->next=null;
        
        pre=L;
        p=pre->next;
        //查找待插入位置
        while(p!=null&&p->data<x)
        {
            pre=p;
            p=p->next;
        }
        s->next=pre->next;
        pre->next=s;
    }

6、**编程题2：有线性表L，其中n![\\geqslant][geqslant]2，带头节点**

**设计一个算法将其就地逆置（不使用其他辅助空间）**

**答：思路---**其实很简单，就是变相的插入节点，先将头节点L的next域设置为空—>使其成为新的空表，后用头插法插入节点

void Reverse(LinkList *&L)
    {
        LinkList *p=L->next,*q;
        L->next=null;
        while(p!=null)
        {
            q=p->next;         //用q临时保存*p的后继节点
            p->next=L->next;   //头插法
            L->next=p;
            p=q;               //用*p继续遍历
        }
    }

7、**编程题3：单链表L，其中n>=2，带头节点,其Elemtype类型为int  
设计一个算法使链表所有元素递增有序**

**答：思路---**采用直接插入排序法，即每次拿出一个节点与余下的每个节点比较，找出其最终位置，并用头插法插入....直到所有节点都找到在有序序列中的最终位置，此时链表有序

void sort(LinkList *&L)
    {
        LinkList *p=L->next,*pre,*r;
        r=p->next;
        
       // p->next=null;
        p=r;
        while(p!=null)
        {
            r=p->next;
            pre=L;
            while(pre->next!=null&&pre->next->data<p->data)
            {
                pre=pre->next;                             //寻找待插入的*p节点*pre
            }
            p->next=pre->next;                             //头插法：在表中有序排列下节点的最终位置
            pre->next=p;
            p=r;                                         //继续遍历余下节点
        }
    }

8、**编程题4：已知3个单链表A、B和C中的节点均依元素值递增有序排列（但可能含有两个以上值相同的节点）**

**设计一个算法对A链表进行如下操作：使操作后的表A仅留下3个表公共的数据元素的节点，且没有值相同的节点，并释放所有无用节点，限定算法的时间复杂度为O(m+n+p)，其中m，n，p分别为3个表的长度**

**答：思路---**将表A中重复的节点删除，后用A的头节点构建一个空的新链表。  遍历A中的每个节点，判断它是否在单链表B、C中，若在，链接到新表末尾，否则删除并释放其空间，同时在比较的过程中释放B和C的所有节点的空间

void pub(LinkList *&A,LinkList *B,LinkList *C)
    {
        LinkList *pa,*pb,*pc,*q,*r;
        pa=A->next;
        while(pa!=null&&pa->next!=null)
        {
            q=pa->next;
            if(pa->data==q->data)
            {
                pa->next=q->next;       //删除A中的重复元素
                free(q);   
            }
        }
        
        pa->next=null;
        pa=A->next;
        r=A;                           //r始终指向新表的尾节点
        r->next=null;
        
        pb=B->next;
        pc=C->next;
        while(pa!=null)
        {
            while(pb!=null&&pb->data<pa->data)
            {
                q=pb;                      //B中遍历过且不满足条件的节点即可删除并释放
                pb=pb->next;
                free(q);
            }
            while(pc!=null&&pc->data<pa->data)
            {
                q=pc;
                pc=pc->next;
                free(q);
            }
            //即刻比较
            if(pb!=null&&pc!=null&&pa->data==pb->data&&pa->data==pc->data)
            {
                r->next=pa;
                r=pa;
                pa=pa->next;
            }
            else
            {
                q=pa;
                pa=pa->next;        //*pa不是公共点，删除并释放空间
                free(q);
            }
        }
        r->next=null;              //新链表建成
    }

[geqslant]: https://private.codecogs.com/gif.latex?%5Cgeqslant