头像

heiyou


访客:2820

离线:3天前



heiyou
15天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return nullptr;
        ListNode *fast, *slow;
        fast = head, slow = head;
        //fast指针一次走2步,slow一次走一步
        slow = slow->next;
        fast = fast->next;
        if(fast->next) fast = fast->next;
        else return nullptr;
        //第一次相遇:first==slow
        while(fast != slow)
        {
            slow = slow->next;
            fast = fast->next;
            if(fast && fast->next) fast = fast->next;
            else return nullptr;
        }
        cout << slow->val << endl;
        //slow回到起点,第二次相遇的节点就是入口
        slow = head;
        while(fast != slow)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};



heiyou
15天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p, *q;
        p = headA, q = headB;
        while(p != q)
        {
            if(p) p = p->next;
            else p = headB;
            if(q) q = q->next;
            else q = headA;
        }

        if(p) return p;
        else return nullptr;
    }
};



heiyou
15天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(!head || m == n) return head;
        ListNode* dummy = new ListNode(0, head);

        //first走到第m个节点的前一个节点
        ListNode* first = dummy;
        for(int i = 0; i < m - 1; i ++)
            first = first->next;
        ListNode* begin = first->next;

        ListNode* a, *b;
        //分析可以知道,begin一定有next
        a = begin->next;    
        for(int i = 0; i < n - m; i ++)
        {
            b = begin;
            begin = a;
            a = begin->next;
            begin->next = b;
        }

        first->next->next = a;
        first->next = begin;
        return dummy->next;
    }
};



heiyou
16天前
//迭代
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return head;
        ListNode* first, *second, *third;
        first = head;
        third = first->next;
        while(third)
        {
            second = first;
            first = third;
            third = first->next;
            first->next = second;
        }
        head->next = NULL;
        return first;
    }
};
//递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};



heiyou
16天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* before, *last;
    void swap(ListNode* p)
    {
        before->next = p->next;
        p->next->next = p;
        p->next = last;
    }

    ListNode* swapPairs(ListNode* head) {
        if(!head) return head;
        ListNode* head1 = new ListNode(0, head);
        before = head1;
        ListNode* first = head;
        while(first->next)
        {
            last = first->next->next;
            swap(first);
            //更新before
            before = first;
            //更新first
            first = first->next;
            if(!first) break;
        }
        return head1->next;
    }
};


活动打卡代码 LeetCode 61. Rotate List

heiyou
16天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int n = 1;
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || k == 0) return head;
        ListNode* num = head;
        while(num->next) num = num->next, n ++;
        k %= n;
        if(!k) return head;
        ListNode* first = head;
        ListNode* second, * third;
        int t = n - k - 1;
        while(t --) first = first->next;
        third = first->next;
        second = third;
        while(second->next) second = second->next;
        first->next = second->next;
        second->next = head;
        head = third;
        return head;
    }
};



heiyou
16天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode* p = head;
        while(p->next)
        {
            if(p->val == p->next->val) p->next = p->next->next;
            else p = p->next;
        }
        return head;
    }
};



heiyou
17天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};



heiyou
26天前

/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode
next;
* ListNode(int x) : val(x), next(NULL) {}
* };
/
class Solution {
public:
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode * dummy = new ListNode(-1);
dummy->next = head;

    ListNode * first, * second;
    first = second = dummy;
    while(n --) second = second->next;
    while(second->next) 
    {
        first = first->next;
        second = second->next;
    }
    first->next = first->next->next;
    return dummy->next;
}

};




heiyou
1个月前
编译原理实验,完整程序的递归下降分析,生成四元式
文法:LittleC文法,需要实现if else 和 while do以及赋值语句的翻译

LittleC文法
![sp20200701_151953_303.png](https://cdn.acwing.com/media/article/image/2020/07/01/28324_47b207e6bb-sp20200701_151953_303.png) 

测试用例
![sp20200701_151813_957.png](https://cdn.acwing.com/media/article/image/2020/07/01/28324_1ea23b28bb-sp20200701_151813_957.png) 


#include <iostream>
#include <cstdio>
#include <sstream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <iomanip>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;

string keyword[7] = {"if", "else", "for", "while", "do", "int", "main"};   //关键字表
string variable[100];                                                      //标识符表
int sum_variable;
set<string> follow;
struct token{
    string val;     //单词具体值
    int type;       //单词的种别码(10是标识符,20是常数,30是关键字,41是加法,42是乘法,43是关系运算符,50是界符)
    int line;       //行号
};
struct Quad{      //定义四元式
    string result;
    string arg1;
    string arg2;
    string op;
}quad[100];

FILE *fin, *fout;    //文件流
int line = 1;        //当前的行号
int flag;            //判断是否从文件读取字符成功
string buff;         //用于存放单词
token new_word;      //单词

int quad_index = 0;  //四元式总数
int e;               //错误次数
char ch;             //从字符串形式的源程序获取的字符
int f;               //表达式中间运算符的个数
int flag1, flag2;
string op, arg1, arg2, result;
string a[200];
int a_num = 1;
int tI = 1;          //定义当前是t几了,比如t1,t2,t3;
stack<int> back_number1, back_number2, back_number3;     //用于回填的栈

int P();
int B();
int Decls();
int Decl();
int Stmts();
int Stmt();
int Sub_Stmt();
int F();
int F1();
int I();
string Expr();    //表达式
string Expr();
string Expr1(string str1);
string Term(string str1, string op1);
string Term1(string str1);
string Factor();
int J();
int TJ();
void showTable();

void getQuad(string op1, string str1, string str2, string res)  //构造四元式
{
    quad[quad_index].op = op1;
    quad[quad_index].arg1 = str1;
    quad[quad_index].arg2 = str2;
    quad[quad_index].result = res;
    quad_index ++;
}

string to_str(int a)     //整型转变为string型
{
    string s;
    while(a) s += '0' + a%10, a /= 10;
    reverse(s.begin(), s.end());
    return s;
}

string newT()            //创建临时变量
{
    int t = tI ++;
    return "t" + to_str(t);
}

void printFour()             //输出四元式
{
    ofstream out("ygro.txt");
    int i;
    for(i=0;i<quad_index;i++)
   {
      cout<<i<<":\t("<<quad[i].op<<",\t"<<quad[i].arg1<<",\t"<<quad[i].arg2<<",\t"<<quad[i].result<<")"<<endl;
      out<<i<<":\t("<<quad[i].op<<",\t"<<quad[i].arg1<<",\t"<<quad[i].arg2<<",\t"<<quad[i].result<<")"<<endl;
   }
}

void error(string s) //输出错误信息
{
    cout << "第" << new_word.line << "行出错!\t";
    cout << s << endl;
    e ++;
}

void is_decleared(string a)       //检查变量是否被声明
{
    int i;
    for(i = 0; i < sum_variable; i ++)
    {
        if(a == variable[i])
            break;
    }
    if(i > sum_variable)             //没有在声明变量表中找到
    {
        cout << "第" << new_word.line << "行出错!\t";
        cout << new_word.val << " 没有被声明!" << endl;
        e ++;
    }
}

int getWord()                    //词法分析
{
    if(!flag) ch = getc(fin);
    while(ch == ' ' || ch == '\n' || ch == '\t')     //跳过换行,缩进,空格
    {
        if(ch == '\n') line ++;
        ch = getc(fin);
        flag = 1;
    }
    if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))      //识别标识符,它可能是变量,也可能是关键字
    {
        buff = "";      //清空buff
        do{
            buff += ch;
            ch = getc(fin);
            flag = 1;
        }while((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'));
        new_word.val = buff;
        new_word.line = line;
        int k;
        for(k = 0; k < 7; k ++){
            if(new_word.val == keyword[k])
                break;
        }
        if(k < 7)      //在关键字表中
             new_word.type = 30;            //关键字种别码30
        else
             new_word.type = 10;            //标识符种别码10
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch >= '0' && ch <= '9')         //整数
    {
        buff = "";
        do{
            buff += ch;
            ch = getc(fin);
            flag = 1;
        }while(ch >= '0' && ch <= '9');
        new_word.val = buff;
        new_word.type = 20;                 //整数种别码20
        new_word.line = line;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
    {
        buff = "";
        buff += ch;
        ch = getc(fin);
        flag = 1;
        new_word.val = buff;
        if(ch == '+' || ch == '-')
           new_word.type = 41;
        else
           new_word.type = 42;
        new_word.line = line;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch == '=' || ch == '<' || ch == '>' || ch =='!')
    {
        buff = "";
        buff += ch;
        ch = getc(fin);
        flag = 1;
        if(ch == '=')
        {
            buff += ch;
            ch = getc(fin);
            flag = 1;
        }
        new_word.val = buff;
        new_word.type = 43;           //关系运算符种别码是43
        new_word.line = line;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch == ',' || ch == ';' || ch == '(' || ch == ')' || ch == '{' || ch == '}')
    {
        buff = "";
        buff += ch;
        new_word.val = buff;
        new_word.type = 50;           //界符的种别码是50
        ch = getc(fin);
        flag = 1;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else
    {
        new_word.type = 0;             //错误类型单词
        new_word.val += " ";
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
}

void init()
{
    follow.insert("+");    //定义Term1的follow集
    follow.insert("-");
    follow.insert(")");
    follow.insert(";");
    follow.insert("==");
    follow.insert(">=");
    follow.insert("<=");
    follow.insert(">");
    follow.insert("<");
}

int P() //(){分程序}
{
    getWord();  //{
    if(new_word.val != "{")
    { error("缺少'{'");}
        getWord();  //int
        B();
        //getWord();
    //if(new_word.val != "} ")
    //{ error("缺少'}'");}
    op="go";
    arg1="";
    arg2="";
    result="";
    getQuad(op, arg1, arg2, result);
    cout<<"语法检查完成,共发现"<<e<<"个错误。"<<endl;
    return 0;
}

int B()
{
    Decls();     //变量声明
    Stmts();
    return 0;
}

int Decls()
{
    Decl();
    if(new_word.val != ";") error("缺少;");
    getWord();
    if(new_word.val == "int") Decls();
    return 0;
}

int Decl()
{
    if(new_word.val != "int") error("缺少int");
    getWord();
    variable[++ sum_variable] = new_word.val;
    F();       //标识符表
    return 0;
}

int F()
{
    if(new_word.type == 10) getWord();
    F1();
    return 0;
}

int F1() //标识符
{
    if(new_word.val == ";") return 0;
    if(new_word.val != ",") error("标识符错误!");
    getWord();
    variable[++ sum_variable] = new_word.val;
    if(new_word.type != 10) error("标识符错误!");
    getWord();
    F1();
    return 0;
}

int Stmts()
{
    Stmt();         //语句
    Sub_Stmt();     //子语句
    return 0;
}

int Sub_Stmt()
{
    if(new_word.val == "}")
    {
        return 0;            //表示一个语句的结束
    }
    if(new_word.val == ";")
    {
        getWord();
        Stmt();
        Sub_Stmt();
    }
    if(new_word.type == 10 || new_word.type == 30)   //右递归
    {
        Stmt();
        getWord();
        if(new_word.type == 10 || new_word.type == 30)
            Stmt();
        //Sub_Stmt();
    }
    if(new_word.type == 0)
        return 0;
    //else error("语句错误!");
    return 0;
}

int Stmt()
{
    if(new_word.type == 10)  //10表示的是标识符,判定为赋值语句
    {
        is_decleared(new_word.val);
        result = new_word.val;
        getWord();
        op = new_word.val;  //op是‘=’
        I();                //赋值语句,需要识别到';'这一块
        arg2 = "";          //arg2设置为空, arg1设置为I产生的表达式
        getQuad(op, arg1, arg2, result);
        return 0;
    }
    if(new_word.val == "if")  //if E then S1 else S2 或者是 if E then S1
    {
        getWord();
        J();                  //if对应的条件语句
        return 0;
    }
    if(new_word.val == "while") //while(E) do S
    {
        getWord();     //new_word=(
        getWord();
        int quad_while = quad_index;      //记录while的标号
        TJ();
        int S_next = back_number1.top();
        back_number1.pop();
        getQuad(op, arg1, arg2, result);

        getWord();     //new_word={
        getWord();
        Stmts();       //S, 语句块
        getQuad("go", "", "", to_str(quad_while));    //goto while
        //回填E.false
        quad[S_next].result = to_str(quad_index);
        getWord();
    }
    if(new_word.type == 0) return 0;
}

int I()        //赋值语句
{
    if(new_word.val != "=") error("缺少=");
    getWord();
    arg1 = Expr();
    return 0;
}

string Expr() {
    string res, str1;
    str1 = Term("", "");
    res = Expr1(str1);
    return res;
}

string Expr1(string str1) {
    string res, str2;
    if(new_word.val == "+" || new_word.val == "-")
    {
        string t = "";
        t += new_word.val;
        getWord();
        str2 = Term(str1, t);
        res = Expr1(str2);
    }
    else if(new_word.val != ")" && new_word.val != ";" && new_word.type != 43)  //new_word.val不在Expr1的follow集中
        error("表达式错误");
    else return str1;
    return res;
}

string Term(string str1, string op1) {  //传递过来的属性是操作运算符+或者-,运算对象
    string res, str2;
    string str3 = Factor();            //Factor产生的字符
    if(new_word.val == "*" || new_word.val == "/")         //Term1非空
    {
        str2 = Term1(str3);
        if(op1.size())
        {
            res = newT();              //返回的中间变量
            getQuad(op1, str1, str2, res);
        }
        else
            res = str2;
    }
    else                               //Term1不考虑错误,为空
    {
        if(str1.size())                //传进来的str1不是""
        {
            res = newT();
            getQuad(op1, str1, str3, res);
        }
        else return str3;
    }
    return res;
}

string Term1(string str1) {
    string res, str2;
    if(new_word.val == "*" || new_word.val == "/")
    {
        string t = newT();
        string op1 = "";
        op1 += new_word.val;                     //记录操作运算符
        getWord();
        str2 = Factor();
        getQuad(op1, str1, str2, t);   //t是中间变量
        if(new_word.val == "*" || new_word.val == "/")    //非空
            res = Term1(t);
        else
        {
            return t;
        }
    }
    else if(follow.count(new_word.val) > 0)   //new_word.val是Term1的follow集
    {
        return res;
    }
    else if(follow.count(new_word.val) == 0)  //new_word.val不在Term1的follow集 + - ) #, 一定出现错误
       error("表达式错误");
    return res;
}

string Factor() {
    string res = "";
    if(new_word.type == 10 || new_word.type == 20)      //new_word是标识符或者常数
       {
           res += new_word.val;
           getWord();
           return res;
       }
    else if(new_word.val == "(")
    {
        getWord();
        res += Expr();
        if(new_word.val == ")") getWord();
        else error("表达式错误");
    }
    else error("表达式错误");
    return res;
}

int J()
{
    if(new_word.val != "(") error("缺少(");
    getWord();
    TJ();
    getQuad(op, arg1, arg2, result);                     //生成E.false
    if(new_word.val != ")") error("缺少)");
    op = "", arg1 = "", arg2 = "", result = "";          //更新为空
    getWord();
    Stmt();                                              //表达式E.true对应的执行语句
    if(new_word.val == ";") getWord();
    if(new_word.val == "else")                           //表示存在else
    {
        //出现了else, E.true对应的执行语句执行完毕之后要跳转到S.next
        back_number2.push(quad_index);
        getQuad("go", "", "", "");          //goto S.next
        //回填E.false
        quad[back_number1.top()].result = to_str(quad_index);
        back_number1.pop();
        //执行else后面的语句
        getWord();
        Stmt();
        //回填S.next
        quad[back_number2.top()].result = to_str(quad_index);
        back_number2.pop();
    }
    else                                                 //表示不存在else,回填E.false
    {
        quad[back_number1.top()].result = to_str(quad_index);
        back_number1.pop();
    }
    return 0;
}

int TJ() //生成E.false
{
    arg1 = Expr();
    if(new_word.val == ">") op = "j<=";
    if(new_word.val == "<") op = "j>=";
    if(new_word.val == ">=") op = "j<";
    if(new_word.val == "<=") op = "j>";
    if(new_word.val == "==") op = "j!=";
    if(new_word.val == "!=") op = "j==";
    if(new_word.type != 43) error("缺少关系运算符");
    getWord();
    arg2 = Expr();
    back_number1.push(quad_index);
    return 0;
}

void showTable()
{
    cout << "---------标识符表---------";
    cout << endl;
    for(int i = 1; i <= sum_variable; i ++)
        cout << variable[i] << "  ";
    cout << endl;
}

int main()
{
    if((fin = fopen("input.txt", "r")) == NULL)
    {
        printf("\n 读入文件错误! \n");
        return 0;
    }
    init();
    P();
    if(e == 0)
    {
        showTable();
        printFour();
    }
    else
        cout << "语法存在错误!" << endl;
    return 0;
}



执行结果:
![sp20200701_152032_200.png](https://cdn.acwing.com/media/article/image/2020/07/01/28324_5febb6f4bb-sp20200701_152032_200.png)