This paper studies the electric vehicle (EV) charging scheduling problem of a park-and-charge system with the objective to minimize the EV battery charging degradation cost while satisfying the battery charging characteristic. First, we design the operating model of the system while taking the interests of both customers and parking garage into consideration. Subsequently, a battery degradation cost model is devised to capture the characteristic of battery performance degradation during the charging process. Taking into account the developed battery degradation cost model, EV charging scheduling problem is explored and a cost minimization problem is formulated. To make the problem tractable, we investigate the features of the problem and decompose the problem into two subproblems. A vacant charging resource allocation algorithm and a dynamic power adjustment algorithm are proposed to obtain the optimal solution of cost minimization. Several simulations based on realistic EV charging settings are conducted to evaluate the effectiveness and applicability of the proposed methods in discussed charging scenarios. Simulation results exhibit the superior performance of the proposed algorithms in achieving the most degradation cost reduction and the lowest peak power load compared with other benchmark solutions, which is beneficial for both customers and charging operators.