《数据结构》实验课期末考试-向日葵屋

《数据结构》实验课期末考试

#代码是直接从提交的答题卡上复制的，可能格式啥有错
#运行结果当时要求用自己的姓名就不粘过来了

题目：
1、（30分）利用自己的姓名拼音字母建立一个单链表（带头结点），注意，如果链表存在已知字母，则不能插入。输入格式样例：
请输入姓名：LIMING
建立的单链表输出为：L->I->M->N->G->^
注：
（1）输入自己姓名拼音，大写全拼，中间无空格；
（2）如果链表长度小于5（不含），则在单链表尾部，反复插入单个字母A，直到链表长度等于5为止。
2、在1所建立的单链表基础上，采用两种方法实现如下功能：查找单链表倒数第2个元素，并输出元素值。
（1）（30分）第一种方法（常规思路）：求出单链表长度（Length），然后通过idx = Length-N+1（N为倒数位置序号），得到idx值，再从头遍历单链表，直到遍历到idx即可。
对应实现函数void GetReverseValue1(LinkList L,int n,char &value)//value为返回的查找元素值
（2）（40分）第二种方法：要求不能采用第一种方法的思路（第一种方法需采用两次遍历，即一次用于求单链表长度，另外一次用于查找idx），且仅采用一次遍历即可得到倒数第2个元素的值。
对应实现函数void GetReverseValue2(LinkList L,int n,char &value)//value为返回的查找元素值
最终输出样式为（以LIMING为例）：
第一种方法（常规思路）单链表倒数第2个元素值为：N
第二种方法单链表倒数第2个元素值为：N

源码：

#include<iostream>
#include<string>
using namespace std;
typedef struct Lnode {
    char data;
    struct Lnode* next;
}Lnode,*Linklist;
//建立单链表
bool initlist(Linklist& L,string n) {
    Linklist p,s;
    L = new Lnode;
    L->next = NULL;
    p = L;
    for (char i : n) {
        s = new Lnode;
        s->data = i;
        p->next = s;
        p = p->next;
    }
    p->next = NULL;
    return true;
}
//显示单链表
void display(Linklist L) {
    Linklist p=L->next;
    while (p!= NULL) {
        cout << p->data << "->";
        p = p->next;
    }
    cout << "^"<< endl;
}
void GetReverseValue1(Linklist L, int n, char& value) {
    //求单链表长度
    Linklist p = L->next;
    int len=0;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    //计算序号
    int idx;
    idx = len - n + 1;
    //查找元素
    p = L;
    for (int i = 0; i < idx; i++) {
        p = p->next;
    }
    value = p->data;
}
void GetReverseValue2(Linklist L, int n, char& value) {
    Linklist p = L, s = L;
    //s指针先移动k步
    for (int i = 0; i < n; i++) {
        s = s->next;
    }
    //一次遍历
    while (s != NULL) {
        s = s->next;
        p = p->next;
    }
    value = p->data;
}
int main() {
    Linklist L;
    string name;
    char value1,value2;
    cout << "输入姓名：";
    cin >> name;
    if (initlist(L, name)) {
        cout << "建立的单链表输出为：" ;
        display(L);
        cout << endl;
    };
    GetReverseValue1(L,2,value1);
    cout << "第一种方法（常规思路）单链表倒数第2个元素值为：" << value1 << endl;
    GetReverseValue2(L, 2, value2);
    cout << "第二种方法单链表倒数第2个元素值为：" << value2 << endl;
    return 0;
}