数据结构第五版——第二章课后实验题

已更新到实验七


实验题1~5我直接放在自己的复习教程里了

其实完全抄书上的也能实现,不过看起来有点别扭

主要是书上C和C++混用看起来挺乱的

也不是说书上的不行

程序的运行效率应该是比我重写的要好

我用C++的流和类重写了一遍,没有再用引用(*&看着太累了)

下面是传送门

实验一 顺序表

实验二 单链表

实验三 双链表

实验四和实验五 循环链表


实验六:以给定值x为基准把单链表分割为两部分

所有小于x的结点排在大于或等于x的结点之前

我看了一下网上的题目描述都有加上一句保持原来链表顺序不变

我们这里并没有做这样的要求

所以我觉得可以直接在这个链表上做文章就行了

新建一个数组,先存入小于x的再存入大于等于x的值

重新根据这个数组来创立单链表就完成了

#include<iostream>

typedef int Elemtype;
using namespace std;

struct Node{
    Elemtype data;
    Node *next;
};//单链表里的最小结点

class List{
    public:
        List();
        void CreateList(Elemtype a[],int n);
        void Divide(Elemtype x);
        void OutputElem();

    private:	
        Node *head;
    
};

List::List(){
    head = NULL;
}//初始化单链表 

void List::CreateList(Elemtype a[],int n){
    Node *p,*q;
    head = new Node;
    q = head;

    for(int i=0;i<n;i++){
        p = new Node;
        p->data = a[i];
        q->next = p;
        q = p;
    } 
    q->next = NULL;
}//创建单链表 

void List::Divide(Elemtype x){
    Elemtype Mid[5];
    int i=0;
    
    Node *current = head->next;
    
    while(current != NULL){
        if(current->data < x){
            Mid[i] = current->data;
            i++;
        }
        current = current->next;
    }
    
    current = head->next;
    
    while(current != NULL){
        if(current->data >= x){
            Mid[i] = current->data;
            i++;
        }
        current = current->next;
    }
    
    CreateList(Mid,5);
    cout<<"所有小于x的结点将排在大于或等于x的结点之前" <<endl;
}

void List::OutputElem(){
    Node *current = head->next;
    
    cout<<"该单链表含有元素";
    while(current != NULL){
        cout<<current->data<<" ";
        current = current->next;
    }
    cout<<endl;
}//输出元素 

int main(){
    
    Elemtype a[5]={3,4,1,2,5};
    List h;
    h.CreateList(a,5);
    h.OutputElem();
    h.Divide(3);
    h.OutputElem();
    
}

下部分省略单链表部分(用include包含进来)

实验七:将两个单链表合并成一个单链表

总之是把两个长度可能不一样的表给连到一起,注意是交错的

例如1,2,3,4,5和6,7,8,9,10

最后出来的结果就是1,6,2,7,3,8,4,9,5,10

#include<iostream> 
#include"listnode.cpp"

void Merge(List a, List b, List &c) {
    
    Node* p = a.head->next;
    Node* q = b.head->next;
    c.head = new Node;
    Node* r = c.head;
    
    while (p!=NULL && q!=NULL)
    {	 
        r->next = p;
        r = p;
        p = p->next;
        r->next = q;
        r = q;
        q = q->next;
    }
    r->next = NULL;
    if(p==NULL){
        r->next = q;
    }else if(q==NULL){
        r->next = p;
    }
}

int main() {

    Elemtype a[5] = { 1,2,3,4,5 };
    Elemtype b[8] = { 6,7,8,9,10,11,12,13 };

    List p;
    List q;
    List r;

    p.CreateList(a, 5);
    p.OutputElem();
    q.CreateList(b, 8);
    q.OutputElem();
    Merge(p, q, r);
    r.OutputElem();
}

 

发表评论

您的电子邮箱地址不会被公开。