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

缺乏、安全感 2023-01-01 07:51 157阅读 0赞

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

**题目：**  
**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;
    }